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
Wyszukiwarka
Podobne podstrony:
Fizjologia Cwiczenia 04 id 1743 Nieznany
cwiczenie nr 04 poprawione id 1 Nieznany
cwiczenie 04 id 125050 Nieznany
CwiczenieArcGIS 04 id 125939 Nieznany
Antropologia Cwiczenia 04 id 65 Nieznany (2)
Cwiczenie nr 04 Uklady dyspersy Nieznany
Fizjologia Cwiczenia 04 id 1743 Nieznany
711[04] Z2 04 Wykonywanie konse Nieznany (2)
AG 04 id 52754 Nieznany
04 Frytkiid 5022 Nieznany (2)
43 04 id 38675 Nieznany
04 pHid 5134 Nieznany (2)
Choroby skory koni cwiczenie id Nieznany
04 klimarczykid 5049 Nieznany (2)
cwiczenia zestaw2(1) Nieznany
CwiczenieNr1 WprowadzenieDoProg Nieznany
INF2 2009 Wykl 04 Zaoczne 4na1 Nieznany
04 Halasid 5030 Nieznany (2)
więcej podobnych podstron