Podstawy logiki i teorii mnogości Ćwiczenie 4
---------------------------------------------------------------------------------------------------------------------------------------
– 1 –
ĆWICZENIE 4
Klasyczny Rachunek Zdań (KRZ): metoda tablic analitycznych, system aksjomatyczny S
(aksjomaty, reguła dowodzenia), dowód w systemie S z dodatkowym zbiorem założeń, tezy
systemu S, wtórne reguły dowodzenia, twierdzenie o dedukcji.
METODA TABLIC ANALITYCZNYCH
Reguły tworzenia drzewa dowodowego.
KRZ:
A
A
¬¬
¬¬
¬¬
¬¬
B
A
B
A
∧∧∧∧
((((
))))
B
A
B
A
¬
¬
¬
¬
¬
¬
¬
¬
∧∧∧∧
¬
¬
¬
¬
|
B
A
B
A
|
∨∨∨∨
((((
))))
B
A
B
A
¬
¬
¬
¬
¬
¬
¬
¬
∨∨∨∨
¬
¬
¬
¬
B
A
B
A
|
¬
¬
¬
¬
→
→
→
→
((((
))))
B
A
B
A
¬
¬
¬
¬
→
→
→
→
¬
¬
¬
¬
B
B
A
A
B
A
¬
¬
¬
¬
¬
¬
¬
¬
↔
↔
↔
↔
|
|
((((
))))
B
B
A
A
B
A
|
|
¬
¬
¬
¬
¬
¬
¬
¬
↔
↔
↔
↔
¬
¬
¬
¬
Wykorzystując powyższe reguły budujemy tablicę (drzewo) dla formuły
A
¬
¬
¬
¬
.
Metoda tablic analitycznych dla KRZ wykorzystuje postać apn formuły w następujący
sposób:
• każda z gałęzi drzewa reprezentuje koniunkcję formuł etykietujących znajdujące się na niej
wierzchołki,
• tablica reprezentuje alternatywę formuł (koniunkcji) reprezentowanych przez wszystkie jej
gałęzie.
Jeżeli każda gałąź tabeli zawiera pewną formułę wraz z jej negacją (gałąź zamknięta), to
formuła reprezentowana przez tablicę (dla KRZ równoważna logicznie formule wyjściowej)
jest kontrtautologią. Zatem formuła A jest tautologią.
Podstawy logiki i teorii mnogości Ćwiczenie 4
---------------------------------------------------------------------------------------------------------------------------------------
– 2 –
Aksjomatyczny system KRZ (system S).
Aksjomaty: podstawienia
A
p
/
,
B
q
/
,
C
r
/
formuł (A1) – (A12)
I. Aksjomaty implikacji
(A1)
((((
))))
p
q
p
→
→
→
→
→
→
→
→
(A2)
((((
))))
[[[[
]]]]
((((
)))) ((((
))))
[[[[
]]]]
r
p
q
p
r
q
p
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
II. Aksjomat negacji
(A3)
((((
)))) ((((
))))
q
p
p
q
→
→
→
→
→
→
→
→
¬
¬
¬
¬
→
→
→
→
¬
¬
¬
¬
III. Aksjomaty koniunkcji
(A4)
p
q
p
→
→
→
→
∧
∧
∧
∧
(A5)
q
q
p
→
→
→
→
∧
∧
∧
∧
(A6)
((((
)))) ((((
)))) ((((
))))
[[[[
]]]]
r
q
p
r
p
q
p
∧
∧
∧
∧
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
IV. Aksjomaty alternatywy
(A7)
q
p
p
∨
∨
∨
∨
→
→
→
→
(A8)
q
p
q
∨
∨
∨
∨
→
→
→
→
(A9)
((((
)))) ((((
)))) ((((
))))
[[[[
]]]]
r
q
p
r
q
r
p
→
→
→
→
∨
∨
∨
∨
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
V. Aksjomaty równoważności
(A10)
((((
)))) ((((
))))
q
p
q
p
→
→
→
→
→
→
→
→
↔
↔
↔
↔
(A11)
((((
)))) ((((
))))
p
q
q
p
→
→
→
→
→
→
→
→
↔
↔
↔
↔
(A12)
((((
)))) ((((
)))) ((((
))))
[[[[
]]]]
q
p
p
q
q
p
↔
↔
↔
↔
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
Reguła dowodzenia:
B
B
A
A
→
→
→
→
,
reguła odrywania MP (modus ponens)
Podstawy logiki i teorii mnogości Ćwiczenie 4
---------------------------------------------------------------------------------------------------------------------------------------
– 3 –
DEF.
Dowód w systemie S z dodatkowym zbiorem założeń
Γ
jest to skończony ciąg formuł, w
którym każda formuła jest
a) aksjomatem systemu S
lub b) dodatkowym założeniem
lub c) wnioskiem z poprzednich formuł na mocy MP.
Formuła A jest
dowodliwa
w systemie S z dodatkowym zbiorem założeń
Γ
, jeżeli w tym
systemie istnieje dowód, w którym ostatnią formułą jest formuła A.
Zapis:
A
S
−
−
−
−
|
Γ
Tezą (twierdzeniem)
systemu S nazywamy formułę dowodliwą bez dodatkowych założeń.
Zapis:
A
S
−
−
−
−
|
TW. O podstawianiu w tezach systemu S.
Jeżeli A jest tezą systemu S, to
[[[[
]]]]
n
n
B
p
B
p
A
/
,
,
/
1
1
K
jest tezą systemu S dla wszelkich
zmiennych
n
p
p
,
,
1
K
i formuł
n
B
B
,
,
1
K
.
DEF.
Schemat wnioskowania
B
A
A
n
,
,
1
K
nazywamy
wtórną regułą dowodzenia
systemu S, jeżeli
istnieje dowód formuły B w systemie S z dodatkowym zbiorem założeń
{{{{
}}}}
n
A
A
,
,
1
K
.
Wtórnymi regułami dowodzenia systemu S są:
a) reguła sylogizmu hipotetycznego b)
reguła komutacji
(SYL)
C
A
C
B
B
A
→
→
→
→
→
→
→
→
→
→
→
→
(KOM)
((((
))))
((((
))))
C
A
B
C
B
A
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
Podstawy logiki i teorii mnogości Ćwiczenie 4
---------------------------------------------------------------------------------------------------------------------------------------
– 4 –
TW. O dedukcji.
Niech
Γ
będzie dowolnym zbiorem formuł oraz A, B będą dowolnymi formułami.
Wtedy
B
A
B
A
S
S
→
→
→
→
−
−−
−
⇔
⇔
⇔
⇔
−
−−
−
|
|
,
Γ
Γ
Na twierdzeniu o dedukcji opierają się
dowody założeniowe
tez systemu S. Zamiast
dowodzić, że
B
A
S
→
→
→
→
−
−
−
−
|
wystarczy dowieść
B
A
S
−
−
−
−
|
, co zwykle jest łatwiejsze. Zatem
każdej tezie postaci
B
A →
→
→
→
odpowiada, zgodnie z definicją, reguła wtórna
B
A
. W ten właśnie
sposób dowodzimy twierdzenia warunkowe (jeżeli A, to B) w matematyce: zakładamy
poprzednik implikacji i wyprowadzamy stąd następnik implikacji.
Podstawy logiki i teorii mnogości Ćwiczenie 4
---------------------------------------------------------------------------------------------------------------------------------------
– 5 –
TEZY systemu S
(T1)
p
p →
→
→
→
−
−
−
−
|
(T2)
p
p ↔
↔
↔
↔
−
−
−
−
|
(T3)
p
q
q
p
∧
∧
∧
∧
→
→
→
→
∧
∧
∧
∧
−
−
−
−
|
(T4)
p
q
q
p
∧
∧
∧
∧
↔
↔
↔
↔
∧
∧
∧
∧
−
−
−
−
|
(T5)
p
q
q
p
∨
∨
∨
∨
→
→
→
→
∨
∨
∨
∨
−
−
−
−
|
(T6)
p
q
q
p
∨
∨
∨
∨
↔
↔
↔
↔
∨
∨
∨
∨
−
−
−
−
|
(T7)
((((
)))) ((((
)))) ((((
))))
[[[[
]]]]
r
p
r
q
q
p
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
−
−
−
−
|
prawo sylogizmu hipotetycznego
(T8)
((((
))))
q
p
p
→
→
→
→
→
→
→
→
¬
¬
¬
¬
−
−−
−
|
prawo Dunsa Szkota
(T9)
((((
))))
[[[[
]]]]
((((
))))
q
p
q
p
p
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
−
−−
−
|
prawo skracania
(T10)
((((
))))
[[[[
]]]]
((((
))))
[[[[
]]]]
r
p
q
r
q
p
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
−
−
−
−
|
(T11)
((((
)))) ((((
))))
r
p
r
q
p
→
→
→
→
→
→
→
→
→
→
→
→
∨
∨
∨
∨
−
−−
−
|
(T12)
((((
)))) ((((
))))
r
q
r
q
p
→
→
→
→
→
→
→
→
→
→
→
→
∨
∨
∨
∨
−
−−
−
|
(T13)
((((
))))
p
p
p
→
→
→
→
→
→
→
→
¬
¬
¬
¬
−
−
−
−
|
prawo Claviusa
(T14)
p
p →
→
→
→
¬¬
¬¬
¬¬
¬¬
−
−−
−
|
(T15)
p
p
¬¬
¬¬
¬¬
¬¬
→
→
→
→
−
−−
−
|
(T16)
((((
)))) ((((
))))
p
q
q
p
¬
¬
¬
¬
→
→
→
→
¬
¬
¬
¬
→
→
→
→
→
→
→
→
−
−−
−
|
prawo transpozycji prostej
(T17)
((((
)))) ((((
))))
[[[[
]]]]
q
q
p
q
p
→
→
→
→
→
→
→
→
¬
¬
¬
¬
→
→
→
→
→
→
→
→
−
−−
−
|
prawo wyczerpywania
(T18)
((((
))))
[[[[
]]]]
q
p
q
p
→
→
→
→
¬
¬
¬
¬
→
→
→
→
¬
¬
¬
¬
→
→
→
→
−
−
−
−
|
(T19)
((((
))))
q
p
q
p
∧
∧
∧
∧
→
→
→
→
→
→
→
→
−
−−
−
|
(T20)
((((
)))) ((((
)))) ((((
))))
[[[[
]]]]
r
p
q
p
r
q
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
−
−−
−
|
(T21)
((((
))))
q
p
q
p
∧
∧
∧
∧
¬
¬
¬
¬
↔
↔
↔
↔
¬
¬
¬
¬
∨
∨
∨
∨
¬
¬
¬
¬
−
−
−
−
|
(T22)
((((
))))
q
p
q
p
∨
∨
∨
∨
¬
¬
¬
¬
↔
↔
↔
↔
¬
¬
¬
¬
∧
∧
∧
∧
¬
¬
¬
¬
−
−−
−
|
(T23)
((((
)))) ((((
))))
q
p
q
p
∨
∨
∨
∨
¬
¬
¬
¬
↔
↔
↔
↔
→
→
→
→
−
−−
−
|
(T24)
((((
)))) ((((
))))
q
p
q
p
∨
∨
∨
∨
↔
↔
↔
↔
→
→
→
→
¬
¬
¬
¬
−
−
−
−
|
Podstawy logiki i teorii mnogości Ćwiczenie 4
---------------------------------------------------------------------------------------------------------------------------------------
– 6 –
Ćwiczenie 4: wiadomości i umiejętności
1.
Po ćwiczeniu 4 student powinien znać definicje pojęć podanych w nagłówku ćwiczenia
2.
Student powinien posiadać następujące umiejętności:
•
udowodnić, że dana formuła jest tautologią za pomocą metody tablic analitycznych
•
pokazać na wybranych przykładach na czym polega dowodzenie w systemie S
•
podać często stosowane reguły dowodzenia (oprócz MP) i udowodnić, że faktycznie
dana reguła dowodzenia jest wtórną regułą systemu S.
•
przeprowadzać dowody założeniowe tez systemu S