Klasyczny rachunek zdań Adekwatność

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 Wprowadzenie
Klasyczny Rachunek Zdań (część III)
Zarys
1 Wprowadzenie
2 Dowód trafności KRZ
Klasyczny Rachunek Zdań (część III)
Zarys
1 Wprowadzenie
2 Dowód trafności KRZ
3 Dowód pełności KRZ
Klasyczny Rachunek Zdań (część III)
Zarys
1 Wprowadzenie
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)
Wprowadzenie
Tautologie i tezy
teza = wyrażenie + dowód
Klasyczny Rachunek Zdań (część III)
Wprowadzenie
Tautologie i tezy
teza = wyrażenie + dowód
prawo logiki (tautologia) = wyrażenie + prawda
Klasyczny Rachunek Zdań (część III)
Wprowadzenie
Trafność i pełność KRZ
Klasyczny Rachunek Zdań (część III)
Wprowadzenie
Trafność i pełność KRZ
Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.
Klasyczny Rachunek Zdań (część III)
Wprowadzenie
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.
Klasyczny Rachunek Zdań (część III)
Wprowadzenie
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:
� �
� �
Klasyczny Rachunek Zdań (część III)
Wprowadzenie
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
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)
Dowód trafności KRZ
Przykład tezy 1-go rzędu
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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)
Dowód trafności KRZ
Każda teza 1-go rzędu jest tautologią KRZ
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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ł.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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)
Dowód trafności KRZ
Każda teza 1-go rzędu jest tautologią KRZ
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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?
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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 ( �2 ( �3 (� � � (�n-1 �n ) . . . )
P P P P F
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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 ( �2 ( �3 (� � � (�n-1 �n ) . . . )
P P P P 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.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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 ( �2 ( �3 (� � � (�n-1 �n ) . . . )
P P P P 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)
Dowód trafności KRZ
Każda teza k-go rzędu jest tautologią KRZ
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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 T1, . . . , Tm rzędów
mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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 T1, . . . , Tm 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.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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 T1, . . . , Tm 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 T1, . . . , Tm na mocy założenia są wyrażeniami prawdziwymi.
Klasyczny Rachunek Zdań (część III)
Dowód trafności KRZ
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 T1, . . . , Tm 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 T1, . . . , Tm 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 KRZ
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Dowód pełności KRZ
Dowód pełności składa się z dwóch części
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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:
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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. � a" K),
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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. � a" K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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. � a" 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
Ogólnie o koniunkcyjnej postaci normalnej
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Ogólnie o koniunkcyjnej postaci normalnej
Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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ą.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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)
Dowód pełności KRZ
Koniunkcyjne postaci normalne
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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).
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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)
Dowód pełności KRZ
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)
Dowód pełności KRZ
Formuła KRZ a KPN
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Formuła KRZ a KPN
Fakt
Każda formuła KRZ (zanotowana za pomocą zmiennych i co najwyżej
znaków Ź, , '", (", a") jest równoważna pewnej koniunkcyjnej postaci
normalnej K.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Formuła KRZ a KPN
Fakt
Każda formuła KRZ (zanotowana za pomocą zmiennych i co najwyżej
znaków Ź, , '", (", a") jest równoważna pewnej koniunkcyjnej postaci
normalnej K.
Aby dowolną formułę � KRZ przekształcić na KPN należy użyć
praw:
1 ŹŹ� a" �,
2 � '" � a" � '" �, � (" � a" � (" �,
3 � '" � (" � a" (� (" �) '" (� (" �), (� (" �) '" � a" � '" � (" � '" �,
4 � � a" Ź� (" � a" Ź(� '" Ź�),
5 � a" � a" (Ź� (" �) '" (Ź� (" �),
6 Ź(� '" �) a" Ź� (" Ź�, Ź(� (" �) a" Ź� '" Ź�
oraz wtórnej reguły ekstensjonalności:
� a" �
� a" � �
� a" �(�//�) �(�//�)
gdzie �(�//�) to wyrażenie, które powstaje z wyrażenia � przez zastąpienie �
przez �.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Od dowolnej formuły KRZ do jej KPN przykład
1 ŹŹ� a" �,
2 � '" � a" � '" �, � (" � a" � (" �,
3 � '" � (" � a" (� (" �) '" (� (" �), (� (" �) '" � a" � '" � (" � '" �,
4 � � a" Ź� (" � a" Ź(� '" Ź�),
5 � a" � a" (Ź� (" �) '" (Ź� (" �),
6 Ź(� '" �) a" Ź� (" Ź�, Ź(� (" �) a" Ź� '" Ź�
Przykład
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Od dowolnej formuły KRZ do jej KPN przykład
1 ŹŹ� a" �,
2 � '" � a" � '" �, � (" � a" � (" �,
3 � '" � (" � a" (� (" �) '" (� (" �), (� (" �) '" � a" � '" � (" � '" �,
4 � � a" Ź� (" � a" Ź(� '" Ź�),
5 � a" � a" (Ź� (" �) '" (Ź� (" �),
6 Ź(� '" �) a" Ź� (" Ź�, Ź(� (" �) a" Ź� '" Ź�
Przykład
(p q) '" p q
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Od dowolnej formuły KRZ do jej KPN przykład
1 ŹŹ� a" �,
2 � '" � a" � '" �, � (" � a" � (" �,
3 � '" � (" � a" (� (" �) '" (� (" �), (� (" �) '" � a" � '" � (" � '" �,
4 � � a" Ź� (" � a" Ź(� '" Ź�),
5 � a" � a" (Ź� (" �) '" (Ź� (" �),
6 Ź(� '" �) a" Ź� (" Ź�, Ź(� (" �) a" Ź� '" Ź�
Przykład
(p q) '" p q a" Ź((p q) '" p) (" q
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Od dowolnej formuły KRZ do jej KPN przykład
1 ŹŹ� a" �,
2 � '" � a" � '" �, � (" � a" � (" �,
3 � '" � (" � a" (� (" �) '" (� (" �), (� (" �) '" � a" � '" � (" � '" �,
4 � � a" Ź� (" � a" Ź(� '" Ź�),
5 � a" � a" (Ź� (" �) '" (Ź� (" �),
6 Ź(� '" �) a" Ź� (" Ź�, Ź(� (" �) a" Ź� '" Ź�
Przykład
(p q) '" p q a" Ź((p q) '" p) (" q a" Ź(p q) (" Źp (" q a"
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Od dowolnej formuły KRZ do jej KPN przykład
1 ŹŹ� a" �,
2 � '" � a" � '" �, � (" � a" � (" �,
3 � '" � (" � a" (� (" �) '" (� (" �), (� (" �) '" � a" � '" � (" � '" �,
4 � � a" Ź� (" � a" Ź(� '" Ź�),
5 � a" � a" (Ź� (" �) '" (Ź� (" �),
6 Ź(� '" �) a" Ź� (" Ź�, Ź(� (" �) a" Ź� '" Ź�
Przykład
(p q) '" p q a" Ź((p q) '" p) (" q a" Ź(p q) (" Źp (" q a"
a" p '" Źq (" Źp (" q
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Od dowolnej formuły KRZ do jej KPN przykład
1 ŹŹ� a" �,
2 � '" � a" � '" �, � (" � a" � (" �,
3 � '" � (" � a" (� (" �) '" (� (" �), (� (" �) '" � a" � '" � (" � '" �,
4 � � a" Ź� (" � a" Ź(� '" Ź�),
5 � a" � a" (Ź� (" �) '" (Ź� (" �),
6 Ź(� '" �) a" Ź� (" Ź�, Ź(� (" �) a" Ź� '" Ź�
Przykład
(p q) '" p q a" Ź((p q) '" p) (" q a" Ź(p q) (" Źp (" q a"
a" p '" Źq (" Źp (" q a" (p (" Źp (" q) '" (Źq (" Źp (" q)
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tautologią?
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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ć:
(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) '" (pj (" pj (" � � � (" pj ("
1 2 k k n1 1 2 n
� � � (" Źpj (" � � � (" pj ) '" � � � '" (pl (" pl (" � � � (" pl (" � � � (" Źpl (" � � � (" pl )
n n2 1 2 m m nr
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
Fakt
Każda prawdziwa koniunkcyjna postać normalna K jest tezą
założeniowego systemu KRZ.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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:
(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) '" (pj (" pj (" � � � (" pj ("
1 2 k k n1 1 2 n
� � � (" Źpj (" � � � (" pj ) '" � � � '" (pl (" pl (" � � � (" pl (" � � � (" Źpl (" � � � (" pl )
n n2 1 2 m m nr
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
. . . . . . NA : 1
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
. . . . . . NA : 1
k + 1. Źpi NA : 1
k
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
. . . . . . NA : 1
k + 1. Źpi NA : 1
k
. . . . . . NA : 1
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
. . . . . . NA : 1
k + 1. Źpi NA : 1
k
. . . . . . NA : 1
l. ŹŹpi NA : 1
k
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
. . . . . . NA : 1
k + 1. Źpi NA : 1
k
. . . . . . NA : 1
l. ŹŹpi NA : 1
k
. . . . . . NA : 1
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
. . . . . . NA : 1
k + 1. Źpi NA : 1
k
. . . . . . NA : 1
l. ŹŹpi NA : 1
k
. . . . . . NA : 1
n1. Źpi NA : 1
n1
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
. . . . . . NA : 1
k + 1. Źpi NA : 1
k
. . . . . . NA : 1
l. ŹŹpi NA : 1
k
. . . . . . NA : 1
n1. Źpi NA : 1
n1
sprz. : k + 1, l
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
We�my pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.
pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi
1 2 k k n1
Pokażemy, że to wyrażenie jest tezą:
1. Ź(pi (" pi (" � � � (" pi (" � � � (" Źpi (" � � � (" pi ) z.d.n.
1 2 k k n1
2. Źpi NA : 1
1
3. Źpi NA : 1
2
. . . . . . NA : 1
k + 1. Źpi NA : 1
k
. . . . . . NA : 1
l. ŹŹpi NA : 1
k
. . . . . . NA : 1
n1. Źpi NA : 1
n1
sprz. : k + 1, l
Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Kiedy koniunkcyjna postać normalna jest tezą?
Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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. pi (" pi (" � � � (" pi teza
1 2 n1
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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. pi (" pi (" � � � (" pi teza
1 2 n1
2. pj (" pj (" � � � (" pj teza
1 2 n2
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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. pi (" pi (" � � � (" pi teza
1 2 n1
2. pj (" pj (" � � � (" pj teza
1 2 n2
. . . . . . . teza
nr . (pl (" pl (" � � � (" pl ) teza
1 2 nr
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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. pi (" pi (" � � � (" pi teza
1 2 n1
2. pj (" pj (" � � � (" pj teza
1 2 n2
. . . . . . . teza
nr . (pl (" pl (" � � � (" pl ) teza
1 2 nr
(pi (" pi (" � � � (" pi )'"
1 2 n1
'"(pj (" pj (" � � � (" pj ) '" . . .
1 2 n2
� � � '" (pl (" pl (" � � � (" pl ) n � DK : 1, 2, . . . , nr
1 2 nr
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Podsumowanie dowódu pełności KRZ
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
Podsumowanie dowódu pełności KRZ
Załóżmy, że � jest wyrażeniem prawdziwym KRZ (tj. �).
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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 � a" K).
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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 � a" K).
Z powayższego otrzymujemy, że:
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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 � a" K).
Z powayższego otrzymujemy, że:
� a" K jest wyrażeniem prawdziwym (tj. � a" K)
- - -- > patrz dowód trafności!
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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 � a" K).
Z powayższego otrzymujemy, że:
� a" K jest wyrażeniem prawdziwym (tj. � a" K)
- - -- > patrz dowód trafności!
K jest wyrażeniem prawdziwym (tj. K).
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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 � a" K).
Z powayższego otrzymujemy, że:
� a" K jest wyrażeniem prawdziwym (tj. � a" 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).
Klasyczny Rachunek Zdań (część III)
Dowód pełności KRZ
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 � a" K).
Z powayższego otrzymujemy, że:
� a" K jest wyrażeniem prawdziwym (tj. � a" 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
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.
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.
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
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.
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.
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.

Wyszukiwarka

Podobne podstrony:
Klasyczny rachunek zdań metoda 0 1
Modul 3 Klasyczny rachunek zdan
logika klasyczny rachunek zdan(1)
Klasyczny rachunek zdań Dedukcja naturalna
01 Rachunek zdań
Rachunek zdan
rachunek zdan 6
rachunek zdan 3
04 Semantyka rachunku zdan
rachunek zdan 7
rachunek zdan 4
rachunek zdan 5
rachunek zdan 1
Marciszewski Witold 3Zadania z rachunku zdań
rachunek zdan 2
kasperski,logika pragmatyczna, WYBRANE TAUTOLOGIE RACHUNKU ZDAŃ
Jak rozstrzygać tautologie rachunku zdań

więcej podobnych podstron