Klasyczny Rachunek Zdań (część III)
LOGIKA
Klasyczny Rachunek Zdań (część III)
Poprawność i pełność KRZ
Robert Trypuz
Katedra Logiki KUL
31 marca 2011
Klasyczny Rachunek Zdań (część III)
LOGIKA
Klasyczny Rachunek Zdań (część III)
Poprawność i pełność KRZ
Robert Trypuz
Katedra Logiki KUL
31 marca 2011
Klasyczny Rachunek Zdań (część III)
Zarys
1
2
Dowód trafności KRZ
3
Dowód pełności KRZ
4
Podsumowanie dowodów trafności i pełności KRZ
Klasyczny Rachunek Zdań (część III)
Zarys
1
2
3
Dowód pełności KRZ
4
Podsumowanie dowodów trafności i pełności KRZ
Klasyczny Rachunek Zdań (część III)
Tautologie i tezy
teza = wyrażenie +
dowód
prawo logiki (tautologia) = wyrażenie +
prawda
Klasyczny Rachunek Zdań (część III)
Tautologie i tezy
teza = wyrażenie +
dowód
prawo logiki (tautologia) = wyrażenie +
prawda
Klasyczny Rachunek Zdań (część III)
Trafność i pełność KRZ
Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.
Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.
KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:
` ϕ → ϕ
ϕ → ` ϕ
Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.
Klasyczny Rachunek Zdań (część III)
Trafność i pełność KRZ
Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.
Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.
KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:
` ϕ → ϕ
ϕ → ` ϕ
Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.
Klasyczny Rachunek Zdań (część III)
Trafność i pełność KRZ
Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.
Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.
KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:
` ϕ → ϕ
ϕ → ` ϕ
Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.
Klasyczny Rachunek Zdań (część III)
Trafność i pełność KRZ
Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.
Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.
KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:
` ϕ → ϕ
ϕ → ` ϕ
Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.
Klasyczny Rachunek Zdań (część III)
Trafność i pełność KRZ
Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.
Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.
KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:
` ϕ → ϕ
ϕ → ` ϕ
Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
Dowodzimy, że
dla ϕ będącego formułą KRZ zachodzi: ` ϕ →
ϕ
Dowód trafności KRZ jest indukcyjny:
1
Każda teza pierwszego rzędu KRZ jest tautologią KRZ.
2
Jeżeli wszystkie tezy KRZ rzędów od 1 do k są tautologiami KRZ, to
każda teza KRZ k-tego rzędu jest tautologią KRZ.
Klasyczny Rachunek Zdań (część III)
Przykład tezy 1-go rzędu
Dowód, że ` (¬p → q) ∧ ¬q → p
1.
(¬p → q) ∧ ¬q
z.
2.
¬p
z.d .n.
3.
¬p → q
OK : 1
4.
¬q
OK : 1
5.
q
RO : 3, 2
sprz. :4, 5
Wyrażenie dowodzone jest tezą pierwszego rzędu KRZ, bo istnieje ciąg:
1
(¬p → q) ∧ ¬q
2
¬p
3
¬p → q
4
¬q
5
q
który spełnia warunki definicji tezy pierwszego rzędu.
Klasyczny Rachunek Zdań (część III)
Przykład tezy 1-go rzędu
Dowód, że ` (¬p → q) ∧ ¬q → p
1.
(¬p → q) ∧ ¬q
z.
2.
¬p
z.d .n.
3.
¬p → q
OK : 1
4.
¬q
OK : 1
5.
q
RO : 3, 2
sprz. :4, 5
Wyrażenie dowodzone jest tezą pierwszego rzędu KRZ, bo istnieje ciąg:
1
(¬p → q) ∧ ¬q
2
¬p
3
¬p → q
4
¬q
5
q
który spełnia warunki definicji tezy pierwszego rzędu.
Klasyczny Rachunek Zdań (część III)
Przykład tezy 1-go rzędu
Dowód, że ` (¬p → q) ∧ ¬q → p
1.
(¬p → q) ∧ ¬q
z.
2.
¬p
z.d .n.
3.
¬p → q
OK : 1
4.
¬q
OK : 1
5.
q
RO : 3, 2
sprz. :4, 5
Wyrażenie dowodzone jest tezą pierwszego rzędu KRZ, bo istnieje ciąg:
1
(¬p → q) ∧ ¬q
2
¬p
3
¬p → q
4
¬q
5
q
który spełnia warunki definicji tezy pierwszego rzędu.
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą 1-go rzędu.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
wyprowadzamy dwa
wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Na przykład Reguła Odrywania:
RO
ϕ → ψ
ϕ
ψ
Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.
Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.
A zatem wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
nie mogą być (i nie są)
zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą 1-go rzędu.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
wyprowadzamy dwa
wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Na przykład Reguła Odrywania:
RO
ϕ → ψ
ϕ
ψ
Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.
Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.
A zatem wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
nie mogą być (i nie są)
zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą 1-go rzędu.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
wyprowadzamy dwa
wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Na przykład Reguła Odrywania:
RO
ϕ → ψ
ϕ
ψ
Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.
Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.
A zatem wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
nie mogą być (i nie są)
zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą 1-go rzędu.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
wyprowadzamy dwa
wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Na przykład Reguła Odrywania:
RO
ϕ → ψ
ϕ
ψ
Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.
Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.
A zatem wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
nie mogą być (i nie są)
zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą 1-go rzędu.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
wyprowadzamy dwa
wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Na przykład Reguła Odrywania:
RO
ϕ → ψ
ϕ
ψ
Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.
Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.
A zatem wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
nie mogą być (i nie są)
zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą 1-go rzędu.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
wyprowadzamy dwa
wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Na przykład Reguła Odrywania:
RO
ϕ → ψ
ϕ
ψ
Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.
Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.
A zatem wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
nie mogą być (i nie są)
zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą 1-go rzędu.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
wyprowadzamy dwa
wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Na przykład Reguła Odrywania:
RO
ϕ → ψ
ϕ
ψ
Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.
Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.
A zatem wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
nie mogą być (i nie są)
zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Czy istnieje taka wartość logiczna wyrażeń ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
przy której:
spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . ) jest
fałszywe?
Zobaczmy zatem kiedy ϕ jest fałszywe:
( ϕ
1
|{z}
P
→ ( ϕ
2
|{z}
P
→ ( ϕ
3
|{z}
P
→ (· · · → (ϕ
n−1
| {z }
P
→ ϕ
n
|{z}
F
) . . . )
Zauważmy, że ϕ
n
jest fałszywe, gdy ¬ϕ
n
jest prawdziwe.
A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
są zarazem prawdziwe, co nie jest możliwe,
gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są
prawdziwe, to wyrażenie ϕ
n
jest również prawdziwe. Ostatecznie
wyrażenie ϕ jest też prawdziwe. Q.E.D.
(quod erat demonstrandum)
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Czy istnieje taka wartość logiczna wyrażeń ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
przy której:
spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . ) jest
fałszywe?
Zobaczmy zatem kiedy ϕ jest fałszywe:
( ϕ
1
|{z}
P
→ ( ϕ
2
|{z}
P
→ ( ϕ
3
|{z}
P
→ (· · · → (ϕ
n−1
| {z }
P
→ ϕ
n
|{z}
F
) . . . )
Zauważmy, że ϕ
n
jest fałszywe, gdy ¬ϕ
n
jest prawdziwe.
A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
są zarazem prawdziwe, co nie jest możliwe,
gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są
prawdziwe, to wyrażenie ϕ
n
jest również prawdziwe. Ostatecznie
wyrażenie ϕ jest też prawdziwe. Q.E.D.
(quod erat demonstrandum)
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Czy istnieje taka wartość logiczna wyrażeń ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
przy której:
spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . ) jest
fałszywe?
Zobaczmy zatem kiedy ϕ jest fałszywe:
( ϕ
1
|{z}
P
→ ( ϕ
2
|{z}
P
→ ( ϕ
3
|{z}
P
→ (· · · → (ϕ
n−1
| {z }
P
→ ϕ
n
|{z}
F
) . . . )
Zauważmy, że ϕ
n
jest fałszywe, gdy ¬ϕ
n
jest prawdziwe.
A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
są zarazem prawdziwe, co nie jest możliwe,
gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są
prawdziwe, to wyrażenie ϕ
n
jest również prawdziwe. Ostatecznie
wyrażenie ϕ jest też prawdziwe. Q.E.D.
(quod erat demonstrandum)
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Czy istnieje taka wartość logiczna wyrażeń ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
przy której:
spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . ) jest
fałszywe?
Zobaczmy zatem kiedy ϕ jest fałszywe:
( ϕ
1
|{z}
P
→ ( ϕ
2
|{z}
P
→ ( ϕ
3
|{z}
P
→ (· · · → (ϕ
n−1
| {z }
P
→ ϕ
n
|{z}
F
) . . . )
Zauważmy, że ϕ
n
jest fałszywe, gdy ¬ϕ
n
jest prawdziwe.
A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
są zarazem prawdziwe, co nie jest możliwe,
gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są
prawdziwe, to wyrażenie ϕ
n
jest również prawdziwe. Ostatecznie
wyrażenie ϕ jest też prawdziwe. Q.E.D.
(quod erat demonstrandum)
Klasyczny Rachunek Zdań (część III)
Każda teza 1-go rzędu jest tautologią KRZ
Czy istnieje taka wartość logiczna wyrażeń ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
przy której:
spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . ) jest
fałszywe?
Zobaczmy zatem kiedy ϕ jest fałszywe:
( ϕ
1
|{z}
P
→ ( ϕ
2
|{z}
P
→ ( ϕ
3
|{z}
P
→ (· · · → (ϕ
n−1
| {z }
P
→ ϕ
n
|{z}
F
) . . . )
Zauważmy, że ϕ
n
jest fałszywe, gdy ¬ϕ
n
jest prawdziwe.
A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
są zarazem prawdziwe, co nie jest możliwe,
gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są
prawdziwe, to wyrażenie ϕ
n
jest również prawdziwe. Ostatecznie
wyrażenie ϕ jest też prawdziwe. Q.E.D.
(quod erat demonstrandum)
Klasyczny Rachunek Zdań (część III)
Każda teza k-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą k-go rzędu.
Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
i tez T
1
, . . . , T
m
rzędów
mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Tezy T
1
, . . . , T
m
na mocy założenia są wyrażeniami prawdziwymi.
Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są prawdziwe, to wyrażenie ϕ
n
jest również
prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.
Klasyczny Rachunek Zdań (część III)
Każda teza k-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą k-go rzędu.
Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
i tez T
1
, . . . , T
m
rzędów
mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Tezy T
1
, . . . , T
m
na mocy założenia są wyrażeniami prawdziwymi.
Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są prawdziwe, to wyrażenie ϕ
n
jest również
prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.
Klasyczny Rachunek Zdań (część III)
Każda teza k-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą k-go rzędu.
Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
i tez T
1
, . . . , T
m
rzędów
mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Tezy T
1
, . . . , T
m
na mocy założenia są wyrażeniami prawdziwymi.
Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są prawdziwe, to wyrażenie ϕ
n
jest również
prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.
Klasyczny Rachunek Zdań (część III)
Każda teza k-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą k-go rzędu.
Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
i tez T
1
, . . . , T
m
rzędów
mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Tezy T
1
, . . . , T
m
na mocy założenia są wyrażeniami prawdziwymi.
Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są prawdziwe, to wyrażenie ϕ
n
jest również
prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.
Klasyczny Rachunek Zdań (część III)
Każda teza k-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą k-go rzędu.
Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
i tez T
1
, . . . , T
m
rzędów
mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Tezy T
1
, . . . , T
m
na mocy założenia są wyrażeniami prawdziwymi.
Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są prawdziwe, to wyrażenie ϕ
n
jest również
prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.
Klasyczny Rachunek Zdań (część III)
Każda teza k-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą k-go rzędu.
Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
i tez T
1
, . . . , T
m
rzędów
mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Tezy T
1
, . . . , T
m
na mocy założenia są wyrażeniami prawdziwymi.
Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są prawdziwe, to wyrażenie ϕ
n
jest również
prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.
Klasyczny Rachunek Zdań (część III)
Każda teza k-go rzędu jest tautologią KRZ
Niech wyrażenie ϕ o postaci: ϕ
1
→ (ϕ
2
→ (· · · → (ϕ
n−1
→ ϕ
n
) . . . )
będzie tezą k-go rzędu.
Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.
Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ
1
, ϕ
2
, . . . , ϕ
n−1
, ¬ϕ
n
i tez T
1
, . . . , T
m
rzędów
mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.
Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.
Tezy T
1
, . . . , T
m
na mocy założenia są wyrażeniami prawdziwymi.
Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ
1
, ϕ
2
, . . . , ϕ
n−1
są prawdziwe, to wyrażenie ϕ
n
jest również
prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Dowód pełności składa się z dwóch części
1
dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:
jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.
2
dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i ϕ, to ` ϕ.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Dowód pełności składa się z dwóch części
1
dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:
jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.
2
dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i ϕ, to ` ϕ.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Dowód pełności składa się z dwóch części
1
dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:
jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.
2
dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i ϕ, to ` ϕ.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Dowód pełności składa się z dwóch części
1
dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:
jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.
2
dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i ϕ, to ` ϕ.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Dowód pełności składa się z dwóch części
1
dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:
jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.
2
dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i ϕ, to ` ϕ.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Dowód pełności składa się z dwóch części
1
dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:
jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.
2
dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i ϕ, to ` ϕ.
Klasyczny Rachunek Zdań (część III)
Ogólnie o koniunkcyjnej postaci normalnej
Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.
W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.
W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.
Klasyczny Rachunek Zdań (część III)
Ogólnie o koniunkcyjnej postaci normalnej
Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.
W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.
W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.
Klasyczny Rachunek Zdań (część III)
Ogólnie o koniunkcyjnej postaci normalnej
Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.
W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.
W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.
Klasyczny Rachunek Zdań (część III)
Ogólnie o koniunkcyjnej postaci normalnej
Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.
W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.
W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.
Klasyczny Rachunek Zdań (część III)
Ogólnie o koniunkcyjnej postaci normalnej
Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.
W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.
W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.
Klasyczny Rachunek Zdań (część III)
Koniunkcyjne postaci normalne
Definicja
Alternatywą elementarną jest:
każda zmienna zdaniowa,
każda negacja zmiennej zdaniowej,
każda n-składnikowa alternatywa zmiennych lub ich negacji (n > 1).
Definicja
Koniunkcyjną postacią normalną jest k-czynnikowa koniunkcja alternatyw
elementarnych.
Klasyczny Rachunek Zdań (część III)
Koniunkcyjne postaci normalne
Definicja
Alternatywą elementarną jest:
każda zmienna zdaniowa,
każda negacja zmiennej zdaniowej,
każda n-składnikowa alternatywa zmiennych lub ich negacji (n > 1).
Definicja
Koniunkcyjną postacią normalną jest k-czynnikowa koniunkcja alternatyw
elementarnych.
Klasyczny Rachunek Zdań (część III)
Koniunkcyjne postaci normalne
Definicja
Alternatywą elementarną jest:
każda zmienna zdaniowa,
każda negacja zmiennej zdaniowej,
każda n-składnikowa alternatywa zmiennych lub ich negacji (n > 1).
Definicja
Koniunkcyjną postacią normalną jest k-czynnikowa koniunkcja alternatyw
elementarnych.
Klasyczny Rachunek Zdań (część III)
KPN – przykłady
Tabela:
Przykłady KPN i non-KPN
KPN
non − KPN
p
¬¬p
p ∨ q
p ∨ p ∧ q
p ∧ (p ∨ q) ∧ (q ∨ r ∨ ¬p)
p → q
Klasyczny Rachunek Zdań (część III)
Formuła KRZ a KPN
Fakt
Każda formuła KRZ (zanotowana za pomocą zmiennych i co najwyżej
znaków ¬, →, ∧, ∨, ≡) jest równoważna pewnej koniunkcyjnej postaci
normalnej K.
Aby dowolną formułę ϕ KRZ przekształcić na KPN należy użyć
praw:
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
oraz wtórnej reguły ekstensjonalności:
ϕ ≡ ψ
ϕ ≡ ψ
χ
χ ≡ χ(ϕ//ψ)
χ(ϕ//ψ)
gdzie “χ(ϕ//ψ)” to wyrażenie, które powstaje z wyrażenia χ przez zastąpienie ϕ
przez ψ.
Klasyczny Rachunek Zdań (część III)
Formuła KRZ a KPN
Fakt
Każda formuła KRZ (zanotowana za pomocą zmiennych i co najwyżej
znaków ¬, →, ∧, ∨, ≡) jest równoważna pewnej koniunkcyjnej postaci
normalnej K.
Aby dowolną formułę ϕ KRZ przekształcić na KPN należy użyć
praw:
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
oraz wtórnej reguły ekstensjonalności:
ϕ ≡ ψ
ϕ ≡ ψ
χ
χ ≡ χ(ϕ//ψ)
χ(ϕ//ψ)
gdzie “χ(ϕ//ψ)” to wyrażenie, które powstaje z wyrażenia χ przez zastąpienie ϕ
przez ψ.
Klasyczny Rachunek Zdań (część III)
Formuła KRZ a KPN
Fakt
Każda formuła KRZ (zanotowana za pomocą zmiennych i co najwyżej
znaków ¬, →, ∧, ∨, ≡) jest równoważna pewnej koniunkcyjnej postaci
normalnej K.
Aby dowolną formułę ϕ KRZ przekształcić na KPN należy użyć
praw:
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
oraz wtórnej reguły ekstensjonalności:
ϕ ≡ ψ
ϕ ≡ ψ
χ
χ ≡ χ(ϕ//ψ)
χ(ϕ//ψ)
gdzie “χ(ϕ//ψ)” to wyrażenie, które powstaje z wyrażenia χ przez zastąpienie ϕ
przez ψ.
Klasyczny Rachunek Zdań (część III)
Od dowolnej formuły KRZ do jej KPN – przykład
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
Przykład
(p → q) ∧ p → q ≡ ¬((p → q) ∧ p) ∨ q ≡ ¬(p → q) ∨ ¬p ∨ q ≡
≡ p ∧ ¬q ∨ ¬p ∨ q ≡ (p ∨ ¬p ∨ q) ∧ (¬q ∨ ¬p ∨ q)
Klasyczny Rachunek Zdań (część III)
Od dowolnej formuły KRZ do jej KPN – przykład
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
Przykład
(p → q) ∧ p → q
≡ ¬((p → q) ∧ p) ∨ q ≡ ¬(p → q) ∨ ¬p ∨ q ≡
≡ p ∧ ¬q ∨ ¬p ∨ q ≡ (p ∨ ¬p ∨ q) ∧ (¬q ∨ ¬p ∨ q)
Klasyczny Rachunek Zdań (część III)
Od dowolnej formuły KRZ do jej KPN – przykład
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
Przykład
(p → q) ∧ p → q ≡ ¬((p → q) ∧ p) ∨ q
≡ ¬(p → q) ∨ ¬p ∨ q ≡
≡ p ∧ ¬q ∨ ¬p ∨ q ≡ (p ∨ ¬p ∨ q) ∧ (¬q ∨ ¬p ∨ q)
Klasyczny Rachunek Zdań (część III)
Od dowolnej formuły KRZ do jej KPN – przykład
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
Przykład
(p → q) ∧ p → q ≡ ¬((p → q) ∧ p) ∨ q ≡ ¬(p → q) ∨ ¬p ∨ q ≡
≡ p ∧ ¬q ∨ ¬p ∨ q ≡ (p ∨ ¬p ∨ q) ∧ (¬q ∨ ¬p ∨ q)
Klasyczny Rachunek Zdań (część III)
Od dowolnej formuły KRZ do jej KPN – przykład
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
Przykład
(p → q) ∧ p → q ≡ ¬((p → q) ∧ p) ∨ q ≡ ¬(p → q) ∨ ¬p ∨ q ≡
≡ p ∧ ¬q ∨ ¬p ∨ q
≡ (p ∨ ¬p ∨ q) ∧ (¬q ∨ ¬p ∨ q)
Klasyczny Rachunek Zdań (część III)
Od dowolnej formuły KRZ do jej KPN – przykład
1
` ¬¬ϕ ≡ ϕ,
2
` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,
3
` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,
4
` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),
5
` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),
6
` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ
Przykład
(p → q) ∧ p → q ≡ ¬((p → q) ∧ p) ∨ q ≡ ¬(p → q) ∨ ¬p ∨ q ≡
≡ p ∧ ¬q ∨ ¬p ∨ q ≡ (p ∨ ¬p ∨ q) ∧ (¬q ∨ ¬p ∨ q)
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tautologią?
Fakt
Koniunkcyjna postać normalna K jest tautologią wtedy i tylko wtedy gdy,
w każdej alternatywie elementarnej, która jest częścią K, przynajmniej
jedna zmienna zdaniowa występuje raz ze znakiem negacji, a raz bez
znaku negacji.
Dowód oczywisty, wystarczy spojrzeć i chwilę pomyśleć:
(p
i
1
∨ p
i
2
∨ · · · ∨
p
i
k
∨ · · · ∨
¬p
i
k
∨ · · · ∨ p
i
n1
) ∧ (p
j
1
∨ p
j
2
∨ · · · ∨
p
j
n
∨
· · · ∨
¬p
j
n
∨ · · · ∨ p
j
n2
) ∧ · · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨
p
l
m
∨ · · · ∨
¬p
l
m
∨ · · · ∨ p
l
nr
)
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tautologią?
Fakt
Koniunkcyjna postać normalna K jest tautologią wtedy i tylko wtedy gdy,
w każdej alternatywie elementarnej, która jest częścią K, przynajmniej
jedna zmienna zdaniowa występuje raz ze znakiem negacji, a raz bez
znaku negacji.
Dowód oczywisty, wystarczy spojrzeć i chwilę pomyśleć:
(p
i
1
∨ p
i
2
∨ · · · ∨
p
i
k
∨ · · · ∨
¬p
i
k
∨ · · · ∨ p
i
n1
) ∧ (p
j
1
∨ p
j
2
∨ · · · ∨
p
j
n
∨
· · · ∨
¬p
j
n
∨ · · · ∨ p
j
n2
) ∧ · · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨
p
l
m
∨ · · · ∨
¬p
l
m
∨ · · · ∨ p
l
nr
)
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tautologią?
Fakt
Koniunkcyjna postać normalna K jest tautologią wtedy i tylko wtedy gdy,
w każdej alternatywie elementarnej, która jest częścią K, przynajmniej
jedna zmienna zdaniowa występuje raz ze znakiem negacji, a raz bez
znaku negacji.
Dowód oczywisty, wystarczy spojrzeć i chwilę pomyśleć:
(p
i
1
∨ p
i
2
∨ · · · ∨
p
i
k
∨ · · · ∨
¬p
i
k
∨ · · · ∨ p
i
n1
) ∧ (p
j
1
∨ p
j
2
∨ · · · ∨
p
j
n
∨
· · · ∨
¬p
j
n
∨ · · · ∨ p
j
n2
) ∧ · · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨
p
l
m
∨ · · · ∨
¬p
l
m
∨ · · · ∨ p
l
nr
)
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
Fakt
Każda prawdziwa koniunkcyjna postać normalna K jest tezą
założeniowego systemu KRZ.
Należy pokazać, że:
` (p
i
1
∨ p
i
2
∨ · · · ∨
p
i
k
∨ · · · ∨
¬p
i
k
∨ · · · ∨ p
i
n1
) ∧ (p
j
1
∨ p
j
2
∨ · · · ∨
p
j
n
∨
· · · ∨
¬p
j
n
∨ · · · ∨ p
j
n2
) ∧ · · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨
p
l
m
∨ · · · ∨
¬p
l
m
∨ · · · ∨ p
l
nr
)
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
Fakt
Każda prawdziwa koniunkcyjna postać normalna K jest tezą
założeniowego systemu KRZ.
Należy pokazać, że:
` (p
i
1
∨ p
i
2
∨ · · · ∨
p
i
k
∨ · · · ∨
¬p
i
k
∨ · · · ∨ p
i
n1
) ∧ (p
j
1
∨ p
j
2
∨ · · · ∨
p
j
n
∨
· · · ∨
¬p
j
n
∨ · · · ∨ p
j
n2
) ∧ · · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨
p
l
m
∨ · · · ∨
¬p
l
m
∨ · · · ∨ p
l
nr
)
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
Fakt
Każda prawdziwa koniunkcyjna postać normalna K jest tezą
założeniowego systemu KRZ.
Należy pokazać, że:
` (p
i
1
∨ p
i
2
∨ · · · ∨
p
i
k
∨ · · · ∨
¬p
i
k
∨ · · · ∨ p
i
n1
) ∧ (p
j
1
∨ p
j
2
∨ · · · ∨
p
j
n
∨
· · · ∨
¬p
j
n
∨ · · · ∨ p
j
n2
) ∧ · · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨
p
l
m
∨ · · · ∨
¬p
l
m
∨ · · · ∨ p
l
nr
)
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
We¨
umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
Pokażemy, że to wyrażenie jest tezą:
1.
¬(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
k
∨ · · · ∨ ¬p
i
k
∨ · · · ∨ p
i
n1
)
z.d .n.
2.
¬p
i
1
NA : 1
3.
¬p
i
2
NA : 1
. . .
. . .
NA : 1
k + 1.
¬p
i
k
NA : 1
. . .
. . .
NA : 1
l .
¬¬p
i
k
NA : 1
. . .
. . .
NA : 1
n
1
.
¬p
i
n1
NA : 1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:
1.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
teza
2.
p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
teza
. . . .
. . .
teza
n
r
.
(p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
teza
(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
)∧
∧(p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
) ∧ . . .
· · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
n × DK : 1, 2, . . . , n
r
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:
1.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
teza
2.
p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
teza
. . . .
. . .
teza
n
r
.
(p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
teza
(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
)∧
∧(p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
) ∧ . . .
· · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
n × DK : 1, 2, . . . , n
r
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:
1.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
teza
2.
p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
teza
. . . .
. . .
teza
n
r
.
(p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
teza
(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
)∧
∧(p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
) ∧ . . .
· · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
n × DK : 1, 2, . . . , n
r
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:
1.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
teza
2.
p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
teza
. . . .
. . .
teza
n
r
.
(p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
teza
(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
)∧
∧(p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
) ∧ . . .
· · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
n × DK : 1, 2, . . . , n
r
Klasyczny Rachunek Zdań (część III)
Kiedy koniunkcyjna postać normalna jest tezą?
Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:
1.
p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
teza
2.
p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
teza
. . . .
. . .
teza
n
r
.
(p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
teza
(p
i
1
∨ p
i
2
∨ · · · ∨ p
i
n1
)∧
∧(p
j
1
∨ p
j
2
∨ · · · ∨ p
j
n2
) ∧ . . .
· · · ∧ (p
l
1
∨ p
l
2
∨ · · · ∨ p
l
nr
)
n × DK : 1, 2, . . . , n
r
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowódu pełności KRZ
Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj. ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:
ϕ ≡ K jest wyrażeniem prawdziwym (tj. ϕ ≡ K)
− − −− > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowódu pełności KRZ
Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj. ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:
ϕ ≡ K jest wyrażeniem prawdziwym (tj. ϕ ≡ K)
− − −− > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowódu pełności KRZ
Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj. ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:
ϕ ≡ K jest wyrażeniem prawdziwym (tj. ϕ ≡ K)
− − −− > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowódu pełności KRZ
Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj. ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:
ϕ ≡ K jest wyrażeniem prawdziwym (tj. ϕ ≡ K)
− − −− > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowódu pełności KRZ
Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj. ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:
ϕ ≡ K jest wyrażeniem prawdziwym (tj. ϕ ≡ K)
− − −− > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowódu pełności KRZ
Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj. ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:
ϕ ≡ K jest wyrażeniem prawdziwym (tj. ϕ ≡ K)
− − −− > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowódu pełności KRZ
Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj. ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:
ϕ ≡ K jest wyrażeniem prawdziwym (tj. ϕ ≡ K)
− − −− > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowódu pełności KRZ
Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj. ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:
ϕ ≡ K jest wyrażeniem prawdziwym (tj. ϕ ≡ K)
− − −− > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowodów trafności i pełności KRZ
Podsumowanie dowodów trafności i pełności KRZ
Definicja
System logiczny, który jest trafny i pełny nazywamy adekwatnym.
Fakt
KRZ jest systemem adekwatnym.
Fakt
Zbiory tez oraz tautologii KRZ są identyczne.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowodów trafności i pełności KRZ
Podsumowanie dowodów trafności i pełności KRZ
Definicja
System logiczny, który jest trafny i pełny nazywamy adekwatnym.
Fakt
KRZ jest systemem adekwatnym.
Fakt
Zbiory tez oraz tautologii KRZ są identyczne.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowodów trafności i pełności KRZ
Podsumowanie dowodów trafności i pełności KRZ
Definicja
System logiczny, który jest trafny i pełny nazywamy adekwatnym.
Fakt
KRZ jest systemem adekwatnym.
Fakt
Zbiory tez oraz tautologii KRZ są identyczne.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowodów trafności i pełności KRZ
Podsumowanie dowodów trafności i pełności KRZ
Definicja
System logiczny, który jest trafny i pełny nazywamy adekwatnym.
Fakt
KRZ jest systemem adekwatnym.
Fakt
Zbiory tez oraz tautologii KRZ są identyczne.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowodów trafności i pełności KRZ
Podsumowanie dowodów trafności i pełności KRZ
Definicja
System logiczny jest niesprzeczny wtedy i tylko wtedy, gdy wśród jego
tez nie występują dwa wyrażenia sprzeczne.
Fakt
KRZ jest systemem niesprzecznym.
Powyższy fakt wynika bezpośrednio z trafności KRZ oraz faktu, że dwa
wyrażenia sprzeczne nie są zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowodów trafności i pełności KRZ
Podsumowanie dowodów trafności i pełności KRZ
Definicja
System logiczny jest niesprzeczny wtedy i tylko wtedy, gdy wśród jego
tez nie występują dwa wyrażenia sprzeczne.
Fakt
KRZ jest systemem niesprzecznym.
Powyższy fakt wynika bezpośrednio z trafności KRZ oraz faktu, że dwa
wyrażenia sprzeczne nie są zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowodów trafności i pełności KRZ
Podsumowanie dowodów trafności i pełności KRZ
Definicja
System logiczny jest niesprzeczny wtedy i tylko wtedy, gdy wśród jego
tez nie występują dwa wyrażenia sprzeczne.
Fakt
KRZ jest systemem niesprzecznym.
Powyższy fakt wynika bezpośrednio z trafności KRZ oraz faktu, że dwa
wyrażenia sprzeczne nie są zarazem prawdziwe.
Klasyczny Rachunek Zdań (część III)
Podsumowanie dowodów trafności i pełności KRZ
Podsumowanie dowodów trafności i pełności KRZ
Definicja
System logiczny jest niesprzeczny wtedy i tylko wtedy, gdy wśród jego
tez nie występują dwa wyrażenia sprzeczne.
Fakt
KRZ jest systemem niesprzecznym.
Powyższy fakt wynika bezpośrednio z trafności KRZ oraz faktu, że dwa
wyrażenia sprzeczne nie są zarazem prawdziwe.
