Dr Andrzej Kmiecik
Zakład Logiki i Epistemologii
Instytut Filozofii i Socjologii UKW
w Bydgoszczy
ul. Ogińskiego 16
Wykład 8
Klasyczny rachunek zdań (3)
Zwróćmy uwagę na to, że reguł pierwotnych się nie dowodzi. Każda dyscyplina
naukowa przyjmuje pewne pojęcia pierwotne, posiada pewne założenia filozo-
ficzne. Logika zakłada, że istnieją znaki. A te, jak wiadomo z definicji znaku –
muszą być poznawalne zmysłowo. W tym sensie u podstaw logiki leży pewna
epistemologia: zakłada się poznawalność zmysłową jej wyrażeń.
Założenia dodatkowe w założeniowym dowodzie twierdzeń rachunku zdań
Ten rodzaj dowodu wprowadza się, aby uniknąć oddzielnego dowodzenia twier-
dzeń pomocniczych
1
. Każdy taki dowód daje się przekształcić na dowód prze-
prowadzony wg reguł pierwotnych systemu założeniowego. Odpowiada on jed-
nak potocznym dowodom
Ex.
Z przesłanki
Jeśli pojadę nad jezioro, to będę pływał i będę wiosłował
wyprowadzić wniosek
Jeśli pojadę nad jezioro, to będę pływał i jeśli pojadę nad jezioro,
to będę wiosłował
I.
Reguła dołączania implikacji do dowodu głosi, że jeżeli w dowodzie na
podstawie dodatkowego założenia
ϕ
otrzymamy wyrażenie
ψ
, to do dowodu
wolno dołączyć implikację
ϕ→ψ
, jako wiersz o pojedynczej numeracji
2
.
Ex.
((p
∨
q)
→
r)
→
((p
→
r)
∧
(q
→
r)) (z prawa dod. poprzedników)
Dowód
1.
(p
∨
q)
→
r)
z.
1.1
p
z.d.
1.2
p
∨
q
DA: 1.1
1
L. Borkowski: Logika formalna, PWN, Warszawa 1978, s. 52-53
2
Elementy logiki matematycznej i teorii mnogości, s. 32.
1.3
r
RO: 1, 1.2
2.
p
→
r
1.1
→
1.3
2.1
q
z.d.
2.2
p
∨
q
DA: 2.1
2.3
r
RO: 1, 2.2
3.
q
→
r
2.1
→
2.3
(p
→
r)
∧
(q
→
r) DK: 2, 3
Uwaga 1
Z założenia dodatkowego
ϕ
i wyrażeń otrzymanych na podstawie tego wyraże-
nia, z wyjątkiem końcowego wniosku
ϕ→ψ
, nie wolno korzystać w dalszych
częściach dowodu.
Uwaga 2
Każdy wiersz otrzymany na podstawie wiersza o podwójnym numerze otrzymu-
je podwójną numerację.
Wiersz otrzymany na podstawie reguły dołączania implikacji do dowodu uzy-
skuje numer pojedynczy.
Uwaga 3
Dzięki regule dołączania implikacji do dowodu unikamy wprowadzania do sys-
temu zbytecznych tez pomocniczych.
II.
Reguła obalania dodatkowych założeń głosi, że jeżeli założenie dodatko-
we prowadzi do sprzeczności, to można do dowodu dołączyć wyrażenie z nim
sprzeczne jako wiersz o pojedynczym numerze.
Ex.
~(p
∨
q)
→
(~p
∧
~q)
Dowód
1.
~(p
∨
q)
z.
1.1
p
z.d.
1.2
p
∨
q
DA: 1.1
2.
~p
1.1
→
sprz: 1, 1.2 (w dowodzie pojawiły się dwa
wyrażenia sprzeczne w wierszach 1, oraz 1.2)
2.1
q
z.d.
2.2
p
∨
q
DA: 2.1
3.
~q
2.1
→
sprz: 1, 2.2 (w dowodzie pojawiły się dwa
wyrażenia sprzeczne w wierszach 1, oraz 2.2)
~p
∧
~q
DK: 2, 3
Rozwinięcie dowodu
1.1
p
z.d.
1.2
p
∨
q
DA: 1.1
1.3
(p
∨
q)
∧
~(p
∨
q)
DK: 1, 1.2
2.
p
→
(p
∨
q)
∧
~(p
∨
q) 1.1
→
1.3
3.
~((p
∨
q)
∧
~(p
∨
q))
podstawienie prawa ~(p
∧
~p)
4.
~p
mod. tol. 2, 3
4.1
q
z.d.
itd.
Inaczej można przeprowadzić dowód korzystając z twierdzeń pomocniczych
~(p
∨
q)
→
~p
~(p
∨
q)
→
~q
III.
Założeniowy dowód rozgałęziony
Rozgałęziony założeniowy dowód wprost wyrażenia implikacyjnego jest
zakończony jeśli otrzymamy w nim
ϕ
n
na podstawie każdego z dodatkowych za-
łożeń, których alternatywa należy do dowodu lub może być do niego dołączona
jako podstawienie jakiejś tezy logicznej.
Ex.
((p
∨
q)
∧
r)
≡
((p
∧
r)
∨
(q
∧
r)) (Borkowski, Logika formamalna, s. 54)
a)
((p
∨
q)
∧
r)
→
((p
∧
r)
∨
(q
∧
r))
Dowód
1. p
∨
q
z.
2.
r
z.
1.1
p
z.d.
1.2
p
∧
r
DK: 1.1, 2
3.
p
→
(p
∧
r)
1.1
→
1.2
2.1
q
z.d.
2.2
q
∧
r
DK: 2.1, 2
4.
q
→
(q
∧
r)
2.1
→
2.2
(p
∧
r)
∨
(q
∧
r)
dyl. konstr. złoż.: 3, 4, 1
Prawo dodawania poprzedników
((p
→
r)
∧
(q
→
r))
≡
((p
∨
q)
→
r)
stąd reguła dylematu konstrukcyjnego
ϕ
1
→
ψ
ϕ
1
: p,
ϕ
2
: q,
ψ
: r
ϕ
2
→
ψ
ϕ
1
∨
ϕ
2
-------
ψ
Jeżeli w rozpisywaniu implikacji pojawi się wiersz zawierający alternatywę, to
stosujemy dowód rozgałęziony.
b) ((p
∧
r)
∨
(q
∧
r))
→
((p
∨
q)
∧
r)
Dowód rozgałęziony
1.
(p
∧
r)
∨
(q
∧
r)
z.
1.1 p
∧
r
zd.
1.2
p
OK: 1.1
1.3
r
OK: 1.1
1.4 p
∨
q
DA: 1.2
1.5
(p
∨
q)
∧
r
DK: 1.4, 1.3
2
(p
∧
r)
→
(p
∨
q)
∧
r
1.1
→
1.5
2.1
q
∧
r
zd.
2.2
q
OK: 2.1
2.3
r
OK: 2.1
2.4 p
∨
q
DA: 2.2
2.5
(p
∨
q)
∧
r
DK: 2.4, 2.3
3.
(q
∧
r)
→
(p
∨
q)
∧
r
2.1
→
2.5
(p
∨
q)
∧
r
dyl. konstr. złoż.: 2, 3, 1
Można też przeprowadzić ten dowód posługując się założeniowym dowodem
nie wprost.
b) ((p
∧
r)
∨
(q
∧
r))
→
((p
∨
q)
∧
r)
Dowód rozgałęziony
1.
(p
∧
r)
∨
(q
∧
r)
z.
2.
~((p
∨
q)
∧
r)
zdn.
1.1 p
∧
r
zd.
1.2
p
OK: 1.1
1.3
r
OK: 1.1
1.4 p
∨
q
DA: 1.2
1.5
(p
∨
q)
∧
r
DK: 1.4, 1.3
3.
(p
∧
r)
→
(p
∨
q)
∧
r
2.1
q
∧
r
zd.
2.2
q
OK: 2.1
2.3
r
OK: 2.1
2.4 p
∨
q
DA: 2.2
2.5
(p
∨
q)
∧
r
DK: 2.4, 2.3
4.
(q
∧
r)
→
(p
∨
q)
∧
r
sprzeczność:
1.1
→
1.5, 2
2.1
→
2.5, 2
Tzn., jeśli do wiersza 3 i wiersza 4 użyjemy modus tollens w związku z wier-
szem 2, to uzyskamy
3.
~(p
∧
r)
sprz.: 1.1
→
1.5, 2
4.
~(q
∧
r)
sprz.: 2.1
→
2.5, 2
5.
q
∧
r
OA: 1, 3
sprz.: 4, 5
Ex.
(~p
→
q)
→
(p
∨
q)
Dowód
1.
~p
→
q)
z.
1.1
~p
z.d.
1.2 q
RO: 1, 1.1
1.3
p
∨
q
DA: 1.2
2.
~p
→
(p
∨
q)
1.1
→
1.3
2.1
p
z.d.
2.2
p
∨
q
DA: 2.1
2.
p
→
(p
∨
q)
2.1
→
2.2
p
∨
q
1.1
→
1.3, 2.1
→
2.2, ~p
∨
p (pr. wył. śr.)
Mamy tu do czynienia z alternatywą założeń dodatkowych. Alternatywa ta jest
teza logiczną – prawem wyłączonego środka. Zwykle zakłada się ją domyślnie i
dlatego nie zapisuje się jej we wierszach dowodu. Prawo wyłączonego środka
jest często domyślnie stosowane w dowodach matematycznych
3
.
Definicja indukcyjna tezy n-tego rzędu w rachunku zdań
4
Tak jak poprzednio mówiliśmy o n-tym rzędzie wyrażenia rachunku zdań, tak
teraz będziemy mówić tezach n-tego rzędu.
Wśród tez rachunku zdań odróżniamy tezy rzędu 1, tezy rzędu 2, itd., ogólnie:
tezy rzędu n, gdzie n jest liczbą naturalną, n
≥
1.
Definicja tego pojęcia jest definicją indukcyjną i jest następująca:
1.
ϕ
jest tezą 1-go rzędu wttw, gdy, istnieje założeniowy dowód (wprost lub nie
wprost) wyrażenia
ϕ
, w którym dołączając nowe wiersze do dowodu korzysta-
my z reguł wymienionych w punkcie 2b opisu reguły tworzenia dowodu założe-
niowego (wprost lub nie wprost) (RO, DK, OK, DA, OA, DE, OE).
3
Elementy logiki matematycznej i teorii mnogości, s. 39
4
Elementy logiki matematycznej i teorii mnogości, s. 20.
2.
ϕ
jest tezą rzędu n wttw, gdy istnieje założeniowy dowód wyrażenia
ϕ
, w
którym korzystamy – wg warunku 2a opisu takiego dowodu – z tez co najwyżej
rzędu n-1, i gdy
ϕ
nie jest tezą rzędu niższego niż n.
3.
ϕ
jest tezą wttw, gdy, gdy istnieje taka liczba naturalna n, że
ϕ
jest tezą rzędu
n.
Uwaga
Definicje indukcyjne daje się sprowadzić do definicji normalnych. Trzeba jed-
nak wtedy skorzystać z dwóch następujących pojęć: 1) pojęcia zbioru zamknię-
tego ze względu na pewne operacje, 2) pojęciem najmniejszego zbioru o danej
własności
5
.
Szczegółowiej,
a) Wyrażenie ┌
ϕ
1
→
(
ϕ
2
→
[
ϕ
2
→
...
→
{
ϕ
n-1
→
ϕ
n
}...]) ┐, n
≥
2, jest tezą 1-go
rzędu wttw, gdy istnieje skończony ciąg wyrażeń, taki że
1. Każdy wyraz tego ciągu jest bądź jednym z wyrażeń
ϕ
1
,...,
ϕ
n
bądź jest uzy-
skany z wcześniejszych za pomocą reguł RO, DK, OK, DA, OA, DE, OE.
2. W ciągu tym występują dwa wyrażenia sprzeczne.
Ex.
Prawo wyłączonego środka nie jest tezą pierwszego rzędu, bo n=1
b) Wyrażenie┌
ϕ
1
→
(
ϕ
2
→
[
ϕ
2
→
...
→
{
ϕ
n-1
→
ϕ
n
}...]) ┐, n
≥
1, jest tezą k-
tego rzędu wttw, gdy istnieje skończony ciąg wyrażeń taki, że
1. Każdy wyraz tego ciągu jest bądź jednym z wyrażeń
ϕ
1
,...,
ϕ
n
2. bądź jest tezą rzędu mniejszego od k
3. bądź jest uzyskany z wcześniejszych za pomocą reguł RO, DK, OK, DA, OA,
DE, OE.
4. W ciągu tym występują dwa wyrażenia sprzeczne.
c)
ϕ
jest tezą wttw, gdy, gdy istnieje taka liczba naturalna n, że
ϕ
jest tezą rzędu
n.
5
Elementy logiki matematycznej i teorii mnogości, s. 121-122.