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.