Założeniowy system klasycznego rachunku zdań
LOGIKA
Dedukcja Naturalna
Robert Trypuz
Katedra Logiki KUL
5 maja 2011
Założeniowy system klasycznego rachunku zdań
PLAN WYKA
ADU
1 Przykład dowodów założeniowych
Przykład dowodów założeniowego wprost
Przykład dowodów założeniowego niewprost
2 Definicja założeniowego dowodu wprost
3 Reguły dołączania nowych wierszy do dowodu
Przykład założeniowego dowodu
4 Definicja założeniowego dowodu niewprost
Sprzeczność syntaktyczna
Przykłady założeniowego dowodu niewprost
Założeniowy system klasycznego rachunku zdań
PLAN WYKA
ADU
5 Reguły wtórne dołączania nowych wierszy do dowodu
Reguła opuszczania podwójnej negacji
Roszerzona reguła opuszczania alternatywy
Reguła modus tollendo tollens
Reguła negowania alternatywy
Reguła dołączania implikacji do dowodu
Reguła obalania dodatkowych założeń
Reguła rozgałęzionego dowodu wprost
Reguła rozgałęzionego dowodu niewprost
6 Metody algorytmiczne i pół-algorytmiczne
7 Udowodnij!
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
1 Wez
my dowolną liczbę n i załóżmy, że 231|n.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
1 Wez
my dowolną liczbę n i załóżmy, że 231|n.
2 Z założenia, że 231|n i
3|231, bo 2 + 3 + 1 jest podzielna przez 3
7|231, bo 1 " 1 + 3 " 3 + 9 " 2 = 28 jest podzielna przez 7
11|231, bo różnica pomiędzy sumą cyfr stojących na nieparzystych
miejscach (licząc od prawej strony!) i sumą cyfr stojących na
parzystych miejscach równa się 0
wynika, że: 3|n i 7|n i 11|n.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
1 Wez
my dowolną liczbę n i załóżmy, że 231|n.
2 Z założenia, że 231|n i
3|231, bo 2 + 3 + 1 jest podzielna przez 3
7|231, bo 1 " 1 + 3 " 3 + 9 " 2 = 28 jest podzielna przez 7
11|231, bo różnica pomiędzy sumą cyfr stojących na nieparzystych
miejscach (licząc od prawej strony!) i sumą cyfr stojących na
parzystych miejscach równa się 0
wynika, że: 3|n i 7|n i 11|n.
3 7|n i 11|n.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
1 Wez
my dowolną liczbę n i załóżmy, że 231|n.
2 Z założenia, że 231|n i
3|231, bo 2 + 3 + 1 jest podzielna przez 3
7|231, bo 1 " 1 + 3 " 3 + 9 " 2 = 28 jest podzielna przez 7
11|231, bo różnica pomiędzy sumą cyfr stojących na nieparzystych
miejscach (licząc od prawej strony!) i sumą cyfr stojących na
parzystych miejscach równa się 0
wynika, że: 3|n i 7|n i 11|n.
3 7|n i 11|n.
4 Zatem 77|n.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
2 Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
"
m m
m i n (n = 0), że 2 = , przy czym jest ułamkiem

n n
nieskracalnym.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
2 Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
"
m m
m i n (n = 0), że 2 = , przy czym jest ułamkiem

n n
nieskracalnym.
3 Zatem, m2 = 2n2.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
2 Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
"
m m
m i n (n = 0), że 2 = , przy czym jest ułamkiem

n n
nieskracalnym.
3 Zatem, m2 = 2n2.
4 Stąd, m2 jest liczbą parzystą.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
2 Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
"
m m
m i n (n = 0), że 2 = , przy czym jest ułamkiem

n n
nieskracalnym.
3 Zatem, m2 = 2n2.
4 Stąd, m2 jest liczbą parzystą.
5 m jest parzyste, tj. m = 2k.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
2 Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
"
m m
m i n (n = 0), że 2 = , przy czym jest ułamkiem

n n
nieskracalnym.
3 Zatem, m2 = 2n2.
4 Stąd, m2 jest liczbą parzystą.
5 m jest parzyste, tj. m = 2k.
6 Więc, 4k2 = 2n2.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
2 Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
"
m m
m i n (n = 0), że 2 = , przy czym jest ułamkiem

n n
nieskracalnym.
3 Zatem, m2 = 2n2.
4 Stąd, m2 jest liczbą parzystą.
5 m jest parzyste, tj. m = 2k.
6 Więc, 4k2 = 2n2.
7 Stąd, n2 jest liczbą parzystą.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
2 Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
"
m m
m i n (n = 0), że 2 = , przy czym jest ułamkiem

n n
nieskracalnym.
3 Zatem, m2 = 2n2.
4 Stąd, m2 jest liczbą parzystą.
5 m jest parzyste, tj. m = 2k.
6 Więc, 4k2 = 2n2.
7 Stąd, n2 jest liczbą parzystą.
8 n jest parzyste.
Założeniowy system klasycznego rachunku zdań
Przykład dowodów założeniowych
Przykład dowodów założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbą wymierną.
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
2 Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
"
m m
m i n (n = 0), że 2 = , przy czym jest ułamkiem

n n
nieskracalnym.
3 Zatem, m2 = 2n2.
4 Stąd, m2 jest liczbą parzystą.
5 m jest parzyste, tj. m = 2k.
6 Więc, 4k2 = 2n2.
7 Stąd, n2 jest liczbą parzystą.
8 n jest parzyste.
m
9 Podsumowując: m i n są liczbami parzystymi, a zatem jest
n
ułamkiem skracalnym, co jest sprzeczne z wierszem 2.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu wprost
Założeniowe dowody wprost
�1 (�2 (� � � (�n-1 �n) . . . ). (1)
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu wprost
Założeniowe dowody wprost
�1 (�2 (� � � (�n-1 �n) . . . ). (1)
Definicja
Założeniowy dowód wprost wyrażenia o postaci (1) tworzymy w sposób
następujący:
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu wprost
Założeniowe dowody wprost
�1 (�2 (� � � (�n-1 �n) . . . ). (1)
Definicja
Założeniowy dowód wprost wyrażenia o postaci (1) tworzymy w sposób
następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia
�1, �2, . . . , �n-1 jako założenia twierdzenia. Każde założenie
oznaczamy literą  z. w części opisowej wiersza.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu wprost
Założeniowe dowody wprost
�1 (�2 (� � � (�n-1 �n) . . . ). (1)
Definicja
Założeniowy dowód wprost wyrażenia o postaci (1) tworzymy w sposób
następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia
�1, �2, . . . , �n-1 jako założenia twierdzenia. Każde założenie
oznaczamy literą  z. w części opisowej wiersza.
2 Do dowodu można dołączać jako nowe wiersze:
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu wprost
Założeniowe dowody wprost
�1 (�2 (� � � (�n-1 �n) . . . ). (1)
Definicja
Założeniowy dowód wprost wyrażenia o postaci (1) tworzymy w sposób
następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia
�1, �2, . . . , �n-1 jako założenia twierdzenia. Każde założenie
oznaczamy literą  z. w części opisowej wiersza.
2 Do dowodu można dołączać jako nowe wiersze:
1 tezy uprzednio udowodnione,
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu wprost
Założeniowe dowody wprost
�1 (�2 (� � � (�n-1 �n) . . . ). (1)
Definicja
Założeniowy dowód wprost wyrażenia o postaci (1) tworzymy w sposób
następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia
�1, �2, . . . , �n-1 jako założenia twierdzenia. Każde założenie
oznaczamy literą  z. w części opisowej wiersza.
2 Do dowodu można dołączać jako nowe wiersze:
1 tezy uprzednio udowodnione,
2 wyrażenia uzyskane na podstawie dotychczasowych wierszy według
pierwotnych reguł dołączania nowych wierszy do dowodu.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu wprost
Założeniowe dowody wprost
�1 (�2 (� � � (�n-1 �n) . . . ). (1)
Definicja
Założeniowy dowód wprost wyrażenia o postaci (1) tworzymy w sposób
następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia
�1, �2, . . . , �n-1 jako założenia twierdzenia. Każde założenie
oznaczamy literą  z. w części opisowej wiersza.
2 Do dowodu można dołączać jako nowe wiersze:
1 tezy uprzednio udowodnione,
2 wyrażenia uzyskane na podstawie dotychczasowych wierszy według
pierwotnych reguł dołączania nowych wierszy do dowodu.
3 Dowód jest zakończony, jeśli w ostatnim jego wierszu występuje
wyrażenie �n. Zakończenie dowodu sygnalizujemy nie numerując
ostatniego wiersza.
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu I
Reguła odrywania
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu I
Reguła odrywania
RO � �
�
�
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu II
Reguła dołączania koniunkcji
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu II
Reguła dołączania koniunkcji
DK �
�
� '" �
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu III
Reguła opuszczania koniunkcji
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu III
Reguła opuszczania koniunkcji
(ta reguła ma dwa schematy)
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu III
Reguła opuszczania koniunkcji
(ta reguła ma dwa schematy)
OK � '" � � '" �
� �
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu IV
Reguła dołączania alternatywy
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu IV
Reguła dołączania alternatywy
(ta reguła ma dwa schematy)
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu IV
Reguła dołączania alternatywy
(ta reguła ma dwa schematy)
DA � �
� (" � � (" �
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu V
Reguła opuszczania alternatywy
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu V
Reguła opuszczania alternatywy
OA � (" �
Ź�
�
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu VI
Reguła dołączania równoważności
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu VI
Reguła dołączania równoważności
DE � �
� �
� a" �
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu VII
Reguła opuszczania równoważności
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu VII
Reguła opuszczania równoważności
(ta reguła ma dwa schematy)
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu VII
Reguła opuszczania równoważności
(ta reguła ma dwa schematy)
OE � a" � � a" �
� � � �
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Przykład założeniowego dowodu
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Przykład założeniowego dowodu
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
1. (p q) '" (q r) z.
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Przykład założeniowego dowodu
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
1. (p q) '" (q r) z.
2. p z.
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Przykład założeniowego dowodu
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
1. (p q) '" (q r) z.
2. p z.
3. p q OK : 1
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Przykład założeniowego dowodu
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
1. (p q) '" (q r) z.
2. p z.
3. p q OK : 1
4. q r OK : 1
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Przykład założeniowego dowodu
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
1. (p q) '" (q r) z.
2. p z.
3. p q OK : 1
4. q r OK : 1
5. q RO : 3, 2
Założeniowy system klasycznego rachunku zdań
Reguły dołączania nowych wierszy do dowodu
Przykład założeniowego dowodu
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
1. (p q) '" (q r) z.
2. p z.
3. p q OK : 1
4. q r OK : 1
5. q RO : 3, 2
r RO : 4, 5
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Założeniowe dowody niewprost
Definicja
Założeniowy dowód niewprost wyrażenia o postaci 1 tworzymy w sposób następujący:
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Założeniowe dowody niewprost
Definicja
Założeniowy dowód niewprost wyrażenia o postaci 1 tworzymy w sposób następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia �1, �2, . . . , �n-1
jako założenia twierdzenia. Każde założenie oznaczamy literą  z. w części
opisowej wiersza.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Założeniowe dowody niewprost
Definicja
Założeniowy dowód niewprost wyrażenia o postaci 1 tworzymy w sposób następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia �1, �2, . . . , �n-1
jako założenia twierdzenia. Każde założenie oznaczamy literą  z. w części
opisowej wiersza.
2 W n-tym wierszu dowodu wpisujemy wyrażenie Ź�n jako założenie dowodu
niewprost. Założenie to oznaczamy  z.d.n. w części opisowej wiersza.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Założeniowe dowody niewprost
Definicja
Założeniowy dowód niewprost wyrażenia o postaci 1 tworzymy w sposób następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia �1, �2, . . . , �n-1
jako założenia twierdzenia. Każde założenie oznaczamy literą  z. w części
opisowej wiersza.
2 W n-tym wierszu dowodu wpisujemy wyrażenie Ź�n jako założenie dowodu
niewprost. Założenie to oznaczamy  z.d.n. w części opisowej wiersza.
3 Do dowodu można dołączać jako nowe wiersze:
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Założeniowe dowody niewprost
Definicja
Założeniowy dowód niewprost wyrażenia o postaci 1 tworzymy w sposób następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia �1, �2, . . . , �n-1
jako założenia twierdzenia. Każde założenie oznaczamy literą  z. w części
opisowej wiersza.
2 W n-tym wierszu dowodu wpisujemy wyrażenie Ź�n jako założenie dowodu
niewprost. Założenie to oznaczamy  z.d.n. w części opisowej wiersza.
3 Do dowodu można dołączać jako nowe wiersze:
1 tezy uprzednio udowodnione,
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Założeniowe dowody niewprost
Definicja
Założeniowy dowód niewprost wyrażenia o postaci 1 tworzymy w sposób następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia �1, �2, . . . , �n-1
jako założenia twierdzenia. Każde założenie oznaczamy literą  z. w części
opisowej wiersza.
2 W n-tym wierszu dowodu wpisujemy wyrażenie Ź�n jako założenie dowodu
niewprost. Założenie to oznaczamy  z.d.n. w części opisowej wiersza.
3 Do dowodu można dołączać jako nowe wiersze:
1 tezy uprzednio udowodnione,
2 wyrażenia uzyskane na podstawie dotychczasowych wierszy według
pierwotnych reguł dołączania nowych wierszy do dowodu.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Założeniowe dowody niewprost
Definicja
Założeniowy dowód niewprost wyrażenia o postaci 1 tworzymy w sposób następujący:
1 W n - 1 pierwszych wierszach dowodu wypisujemy wyrażenia �1, �2, . . . , �n-1
jako założenia twierdzenia. Każde założenie oznaczamy literą  z. w części
opisowej wiersza.
2 W n-tym wierszu dowodu wpisujemy wyrażenie Ź�n jako założenie dowodu
niewprost. Założenie to oznaczamy  z.d.n. w części opisowej wiersza.
3 Do dowodu można dołączać jako nowe wiersze:
1 tezy uprzednio udowodnione,
2 wyrażenia uzyskane na podstawie dotychczasowych wierszy według
pierwotnych reguł dołączania nowych wierszy do dowodu.
4 Dowód jest zakończony gdy uzyskaliśmy w nim dwa wiersze sprzeczne.
Zakończenie dowodu sygnalizujemy pisząc  sprz. i podając numery wierszy
sprzecznych.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Sprzeczność syntaktyczna
Sprzeczność syntaktyczna
Wiersze sprzeczne są to wiersze o postaci � i Ź�.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Sprzeczność syntaktyczna
Sprzeczność syntaktyczna
Wiersze sprzeczne są to wiersze o postaci � i Ź�.
wyrażenie  p q jest sprzeczne z wyrażeniem  Ź(p q) ,
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Sprzeczność syntaktyczna
Sprzeczność syntaktyczna
Wiersze sprzeczne są to wiersze o postaci � i Ź�.
wyrażenie  p q jest sprzeczne z wyrażeniem  Ź(p q) ,
wyrażenie  p q nie jest sprzeczne z wyrażeniem  Źp q ,
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Sprzeczność syntaktyczna
Sprzeczność syntaktyczna
Wiersze sprzeczne są to wiersze o postaci � i Ź�.
wyrażenie  p q jest sprzeczne z wyrażeniem  Ź(p q) ,
wyrażenie  p q nie jest sprzeczne z wyrażeniem  Źp q ,
wyrażenie  p q nie jest sprzeczne z wyrażeniem  Ź(p '" Źq)
.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady I
Udowodnimy jedno z praw reductio ad absurdum.
(Źp p) p. (3)
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady I
Udowodnimy jedno z praw reductio ad absurdum.
(Źp p) p. (3)
1. Źp p z.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady I
Udowodnimy jedno z praw reductio ad absurdum.
(Źp p) p. (3)
1. Źp p z.
2. Źp z.d.n.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady I
Udowodnimy jedno z praw reductio ad absurdum.
(Źp p) p. (3)
1. Źp p z.
2. Źp z.d.n.
3. p RO : 1, 2
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady I
Udowodnimy jedno z praw reductio ad absurdum.
(Źp p) p. (3)
1. Źp p z.
2. Źp z.d.n.
3. p RO : 1, 2
sprz. : 2, 3
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
1. (Źp q) '" Źq z.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
1. (Źp q) '" Źq z.
2. Źp z.d.n.
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
1. (Źp q) '" Źq z.
2. Źp z.d.n.
3. Źp q OK : 1
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
1. (Źp q) '" Źq z.
2. Źp z.d.n.
3. Źp q OK : 1
4. Źq OK : 1
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
1. (Źp q) '" Źq z.
2. Źp z.d.n.
3. Źp q OK : 1
4. Źq OK : 1
5. q RO : 3, 2
Założeniowy system klasycznego rachunku zdań
Definicja założeniowego dowodu niewprost
Przykłady założeniowego dowodu niewprost
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
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
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguły wtórne dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguły wtórne dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Reguła wtórna jest to reguła, której wniosek można wyprowadzić z przesłanek
używając tylko reguł pierwotnych i tez systemu założeniowego.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguły wtórne dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Reguła wtórna jest to reguła, której wniosek można wyprowadzić z przesłanek
używając tylko reguł pierwotnych i tez systemu założeniowego.
Wprowadzenie każdej reguły pierwotnej powinien poprzedzić odpowiedni dowód.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguły wtórne dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Reguła wtórna jest to reguła, której wniosek można wyprowadzić z przesłanek
używając tylko reguł pierwotnych i tez systemu założeniowego.
Wprowadzenie każdej reguły pierwotnej powinien poprzedzić odpowiedni dowód.
Definicja
Reguła wnioskowania R:
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguły wtórne dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Reguła wtórna jest to reguła, której wniosek można wyprowadzić z przesłanek
używając tylko reguł pierwotnych i tez systemu założeniowego.
Wprowadzenie każdej reguły pierwotnej powinien poprzedzić odpowiedni dowód.
Definicja
Reguła wnioskowania R:
R �1
. . .
�n
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguły wtórne dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Reguła wtórna jest to reguła, której wniosek można wyprowadzić z przesłanek
używając tylko reguł pierwotnych i tez systemu założeniowego.
Wprowadzenie każdej reguły pierwotnej powinien poprzedzić odpowiedni dowód.
Definicja
Reguła wnioskowania R:
R �1
. . .
�n
�
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguły wtórne dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Reguła wtórna jest to reguła, której wniosek można wyprowadzić z przesłanek
używając tylko reguł pierwotnych i tez systemu założeniowego.
Wprowadzenie każdej reguły pierwotnej powinien poprzedzić odpowiedni dowód.
Definicja
Reguła wnioskowania R:
R �1
. . .
�n
�
jest regułą wtórną jeżeli istnieje założeniowy dowód niewprost implikacji
 �1 '" � � � '" �n � , w którym posługujemy się tylko regułami pierwotnymi
dołączania nowych wierszy do dowodu.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguły wtórne dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Reguła wtórna jest to reguła, której wniosek można wyprowadzić z przesłanek
używając tylko reguł pierwotnych i tez systemu założeniowego.
Wprowadzenie każdej reguły pierwotnej powinien poprzedzić odpowiedni dowód.
Definicja
Reguła wnioskowania R:
R �1
. . .
�n
�
jest regułą wtórną jeżeli istnieje założeniowy dowód niewprost implikacji
 �1 '" � � � '" �n � , w którym posługujemy się tylko regułami pierwotnymi
dołączania nowych wierszy do dowodu.
W praktyce dowodząc reguł wtórnych posługujemy się regułami pierwotnymi
oraz wszystkimi udowodnionymi do tej pory regułami wtórnymi.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła opuszczania podwójnej negacji
Reguły wtórne  przykłady I
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła opuszczania podwójnej negacji
Reguły wtórne  przykłady I
Reguła opuszczania podwójnej negacji
ON ŹŹ�
�
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła opuszczania podwójnej negacji
Reguły wtórne  przykłady I
Reguła opuszczania podwójnej negacji
ON ŹŹ�
�
Dowód tezy na której  oparta jest powyższa reguła ma postać:
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła opuszczania podwójnej negacji
Reguły wtórne  przykłady I
Reguła opuszczania podwójnej negacji
ON ŹŹ�
�
Dowód tezy na której  oparta jest powyższa reguła ma postać:
1. ŹŹp z.
2. Źp z.d.n.
sprz. : 1, 2
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Roszerzona reguła opuszczania alternatywy
Reguły wtórne  przykłady II
Roszerzona reguła opuszczania alternatywy
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Roszerzona reguła opuszczania alternatywy
Reguły wtórne  przykłady II
Roszerzona reguła opuszczania alternatywy
(ta reguła ma cztery schematy)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Roszerzona reguła opuszczania alternatywy
Reguły wtórne  przykłady II
Roszerzona reguła opuszczania alternatywy
(ta reguła ma cztery schematy)
OA � (" � � (" � Ź� (" � � (" Ź�
Ź� Ź� � �
� � � �
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Roszerzona reguła opuszczania alternatywy
Reguły wtórne  przykłady II
Roszerzona reguła opuszczania alternatywy
(ta reguła ma cztery schematy)
OA � (" � � (" � Ź� (" � � (" Ź�
Ź� Ź� � �
� � � �
Rozszerzona reguła OA głosi, że z alternatywy i negacji jednego z jej
składników możemy wyprowadzić drugi składnik.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła modus tollendo tollens
Reguły wtórne  przykłady III
Reguła modus tollendo tollens
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła modus tollendo tollens
Reguły wtórne  przykłady III
Reguła modus tollendo tollens
(ta reguła ma cztery schematy)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła modus tollendo tollens
Reguły wtórne  przykłady III
Reguła modus tollendo tollens
(ta reguła ma cztery schematy)
TOLL � � � Ź� Ź� � Ź� Ź�
Ź� � Ź� �
Ź� Ź� � �
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła modus tollendo tollens
Reguły wtórne  przykłady III
Reguła modus tollendo tollens
(ta reguła ma cztery schematy)
TOLL � � � Ź� Ź� � Ź� Ź�
Ź� � Ź� �
Ź� Ź� � �
Reguła modus tollendo tollens głosi, że z implikacji i wyrażenia
sprzecznego z jej następnikiem możemy wyprowadzić wyrażenie sprzeczne
z jej poprzednikiem.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła negowania alternatywy
Reguły wtórne  przykłady IV
Reguła negowania alternatywy
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła negowania alternatywy
Reguły wtórne  przykłady IV
Reguła negowania alternatywy
(ta reguła ma dwa schematy)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła negowania alternatywy
Reguły wtórne  przykłady IV
Reguła negowania alternatywy
(ta reguła ma dwa schematy)
NA Ź(� (" �) Ź(� (" �)
Ź� Ź�
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła negowania alternatywy
Reguły wtórne  przykłady IV
Reguła negowania alternatywy
(ta reguła ma dwa schematy)
NA Ź(� (" �) Ź(� (" �)
Ź� Ź�
Reguła negowania alternatywy głosi, że z negacji alternatywy można
wyprowadzić negację każdego ze składników alternatywy.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
Reguły wtórne  przykłady V
Definicja
Reguła dołączania implikacji do dowodu głosi, że jeśli w dowodzie na
podstawie założenia dodatkowego � w wierszu o numerze podwójnym
k.1 uzyskaliśmy wyrażenie � w wierszu o numerze k.n, to wolno nam
dołączyć do dowodu jako wiersz o kolejnym numerze pojedynczym
implikację � �. W części opisowej tego wiersza piszemy k.1 k.n.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
1.2. p (" q DA : 1.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
1.2. p (" q DA : 1.1
1.3. r RO : 1, 1.2
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
1.2. p (" q DA : 1.1
1.3. r RO : 1, 1.2
2. p r 1.1 1.3
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
1.2. p (" q DA : 1.1
1.3. r RO : 1, 1.2
2. p r 1.1 1.3
2.1. q z.d.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
1.2. p (" q DA : 1.1
1.3. r RO : 1, 1.2
2. p r 1.1 1.3
2.1. q z.d.
2.2. p (" q DA : 2.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
1.2. p (" q DA : 1.1
1.3. r RO : 1, 1.2
2. p r 1.1 1.3
2.1. q z.d.
2.2. p (" q DA : 2.1
2.3. r RO : 1, 2.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
1.2. p (" q DA : 1.1
1.3. r RO : 1, 1.2
2. p r 1.1 1.3
2.1. q z.d.
2.2. p (" q DA : 2.1
2.3. r RO : 1, 2.1
3. q r 2.1 2.3
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
1. p (" q r z.
1.1. p z.d.
1.2. p (" q DA : 1.1
1.3. r RO : 1, 1.2
2. p r 1.1 1.3
2.1. q z.d.
2.2. p (" q DA : 2.1
2.3. r RO : 1, 2.1
3. q r 2.1 2.3
(p r) '" (q r) DK : 2, 3
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
Reguła dołączania implikacji do dowodu
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
Reguła dołączania implikacji do dowodu
Wiersze o numerze podwójnym nie mogą kończyć dowodu
założeniowego, gdyż zostały uzyskane na podstawie dowolnie
wybranego założenia dodatkowego.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
Reguła dołączania implikacji do dowodu
Wiersze o numerze podwójnym nie mogą kończyć dowodu
założeniowego, gdyż zostały uzyskane na podstawie dowolnie
wybranego założenia dodatkowego.
Wyprowadzając nowe wiersze (o podwójnych numerach) na
podstawie założenia k.1 możemy odwoływać się do wszystkich
dotychczasowych wierszy o numerach pojedynczych oraz do wierszy
o numerach podwójnych uzyskanych na podstawie k.1.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
Reguła dołączania implikacji do dowodu
Wiersze o numerze podwójnym nie mogą kończyć dowodu
założeniowego, gdyż zostały uzyskane na podstawie dowolnie
wybranego założenia dodatkowego.
Wyprowadzając nowe wiersze (o podwójnych numerach) na
podstawie założenia k.1 możemy odwoływać się do wszystkich
dotychczasowych wierszy o numerach pojedynczych oraz do wierszy
o numerach podwójnych uzyskanych na podstawie k.1.
Dowód reguły dołączania implikacji do dowodu jest bardziej
skomplikowany od dowodów innych reguły ponieważ wymaga
dowiedzenia tzw. twierdzenia o dedukcji.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
Reguła dołączania implikacji do dowodu
Wiersze o numerze podwójnym nie mogą kończyć dowodu
założeniowego, gdyż zostały uzyskane na podstawie dowolnie
wybranego założenia dodatkowego.
Wyprowadzając nowe wiersze (o podwójnych numerach) na
podstawie założenia k.1 możemy odwoływać się do wszystkich
dotychczasowych wierszy o numerach pojedynczych oraz do wierszy
o numerach podwójnych uzyskanych na podstawie k.1.
Dowód reguły dołączania implikacji do dowodu jest bardziej
skomplikowany od dowodów innych reguły ponieważ wymaga
dowiedzenia tzw. twierdzenia o dedukcji.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Reguła obalania dodatkowych założeń
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Reguła obalania dodatkowych założeń
Jeżeli założenie dodatkowe prowadzi do sprzeczności, to można do
dowodu dołączyć wyrażenie z nim sprzeczne jako wiersz dowodu o
pojedynczym numerze.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Reguła obalania dodatkowych założeń
Jeżeli założenie dodatkowe prowadzi do sprzeczności, to można do
dowodu dołączyć wyrażenie z nim sprzeczne jako wiersz dowodu o
pojedynczym numerze.
Reguła ta jest regułą wtórną.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Reguła obalania dodatkowych założeń
Jeżeli założenie dodatkowe prowadzi do sprzeczności, to można do
dowodu dołączyć wyrażenie z nim sprzeczne jako wiersz dowodu o
pojedynczym numerze.
Reguła ta jest regułą wtórną.
Jeżeli z założenia dodatkowego � wyprowadzimy wyrażenia sprzeczne
� i Ź�, to na mocy reguły DK oraz reguły dołączania implikacji do
dowodu, nowym wierszem dowodu będzie wyrażenie � � '" Ź�
A następnie, na mocy prawa redukcji do absurdu:
(� � '" Ź�) Ź� oraz RO otrzymamy jako wiersz dowodu Ź�.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
1.1. p z.d.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
1.1. p z.d.
1.2. p (" q DA : 1.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
1.1. p z.d.
1.2. p (" q DA : 1.1
2. Źp 1.1 sprz.(1, 1.2)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
1.1. p z.d.
1.2. p (" q DA : 1.1
2. Źp 1.1 sprz.(1, 1.2)
2.1. q z.d.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
1.1. p z.d.
1.2. p (" q DA : 1.1
2. Źp 1.1 sprz.(1, 1.2)
2.1. q z.d.
2.2. p (" q DA : 2.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
1.1. p z.d.
1.2. p (" q DA : 1.1
2. Źp 1.1 sprz.(1, 1.2)
2.1. q z.d.
2.2. p (" q DA : 2.1
3. Źq 2.1 sprz.(1, 2.2)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
1.1. p z.d.
1.2. p (" q DA : 1.1
2. Źp 1.1 sprz.(1, 1.2)
2.1. q z.d.
2.2. p (" q DA : 2.1
3. Źq 2.1 sprz.(1, 2.2)
Źp '" Źq DK : 2, 3
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
Reguła rozgałęzionego dowodu wprost
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
Reguła rozgałęzionego dowodu wprost
Zgodnie z regułą rozgałęzionego dowodu wprost dowód wyrażenia:
�1 (�2 (� � � (�n-1 �n) . . . )
jest zakończony, jeżeli otrzymamy w nim wyrażenie �n na podstawie
każdego z dodatkowych założeń �1, . . . , �k, których alternatywa
należy do dowodu lub może być do niego dołączona jako
podstawienie tezy logicznej.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
Reguła rozgałęzionego dowodu wprost
Zgodnie z regułą rozgałęzionego dowodu wprost dowód wyrażenia:
�1 (�2 (� � � (�n-1 �n) . . . )
jest zakończony, jeżeli otrzymamy w nim wyrażenie �n na podstawie
każdego z dodatkowych założeń �1, . . . , �k, których alternatywa
należy do dowodu lub może być do niego dołączona jako
podstawienie tezy logicznej.
Reguła ta jest regułą wtórną.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
Reguła rozgałęzionego dowodu wprost
Zgodnie z regułą rozgałęzionego dowodu wprost dowód wyrażenia:
�1 (�2 (� � � (�n-1 �n) . . . )
jest zakończony, jeżeli otrzymamy w nim wyrażenie �n na podstawie
każdego z dodatkowych założeń �1, . . . , �k, których alternatywa
należy do dowodu lub może być do niego dołączona jako
podstawienie tezy logicznej.
Reguła ta jest regułą wtórną.
Na podstawie reguły dołączania implikacji do dowodu otrzymujemy
implikacje: �1 �n, . . . , �k �n.
Z implikacji tych oraz alternatywy �1 (" � � � (" �k na mocy tezy:
(�1 �n) '" � � � '" (�k �n) '" (�1 (" � � � (" �k) �n, wyprowadzamy
�n
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
3. p (" r z.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
3. p (" r z.
1.1. p z.d.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
3. p (" r z.
1.1. p z.d.
1.2. q RO : 1, 1.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
3. p (" r z.
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
3. p (" r z.
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
2.1. r z.d.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
3. p (" r z.
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
2.1. r z.d.
2.2. s RO : 2, 2.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
3. p (" r z.
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
2.1. r z.d.
2.2. s RO : 2, 2.1
2.3. q (" s DA : 2.2
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
1. p q z.
2. r s z.
3. p (" r z.
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
2.1. r z.d.
2.2. s RO : 2, 2.1
2.3. q (" s DA : 2.2
q (" s 1.1 1.3, 2.1 2.3, 3
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
Reguła rozgałęzionego dowodu niewprost
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
Reguła rozgałęzionego dowodu niewprost
Zgodnie z regułą rozgałęzionego dowodu nie wprost dowód
wyrażenia:
�1 (�2 (� � � (�n-1 �n) . . . )
jest zakończony, jeżeli otrzymamy w nim sprzeczności na podstawie
każdego z dodatkowych założeń �1, . . . , �k, których alternatywa
należy do dowodu lub może być do niego dołączona jako
podstawienie tezy logicznej.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
Reguła rozgałęzionego dowodu niewprost
Zgodnie z regułą rozgałęzionego dowodu nie wprost dowód
wyrażenia:
�1 (�2 (� � � (�n-1 �n) . . . )
jest zakończony, jeżeli otrzymamy w nim sprzeczności na podstawie
każdego z dodatkowych założeń �1, . . . , �k, których alternatywa
należy do dowodu lub może być do niego dołączona jako
podstawienie tezy logicznej.
Reguła ta jest regułą wtórną.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
Reguła rozgałęzionego dowodu niewprost
Zgodnie z regułą rozgałęzionego dowodu nie wprost dowód
wyrażenia:
�1 (�2 (� � � (�n-1 �n) . . . )
jest zakończony, jeżeli otrzymamy w nim sprzeczności na podstawie
każdego z dodatkowych założeń �1, . . . , �k, których alternatywa
należy do dowodu lub może być do niego dołączona jako
podstawienie tezy logicznej.
Reguła ta jest regułą wtórną.
Na podstawie reguły obalania dodatkowych założeń można dołączyć
do dowodu wyrażenia: Ź�1, . . . , Ź�k.
Z alternatywy �1 (" � � � (" �k i wyrażeń Ź�1, . . . , Ź�k-1
wyprowadzamy za pomocą reguły OA wyrażenie �k, sprzeczne z
wyprowadzonym uprzednio wyrażeniem Ź�k.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
3. Ź(q (" s) z.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
3. Ź(q (" s) z.
4. ŹŹ(p (" r) z.d.n.
5. p (" r ON : 4
1.1. p z.d.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
3. Ź(q (" s) z.
4. ŹŹ(p (" r) z.d.n.
5. p (" r ON : 4
1.1. p z.d.
1.2. q RO : 1, 1.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
3. Ź(q (" s) z.
4. ŹŹ(p (" r) z.d.n.
5. p (" r ON : 4
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
3. Ź(q (" s) z.
4. ŹŹ(p (" r) z.d.n.
5. p (" r ON : 4
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
2.1. r z.d.
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
3. Ź(q (" s) z.
4. ŹŹ(p (" r) z.d.n.
5. p (" r ON : 4
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
2.1. r z.d.
2.2. s RO : 2, 2.1
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
3. Ź(q (" s) z.
4. ŹŹ(p (" r) z.d.n.
5. p (" r ON : 4
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
2.1. r z.d.
2.2. s RO : 2, 2.1
2.3. q (" s DA : 2.2
Założeniowy system klasycznego rachunku zdań
Reguły wtórne dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
1. p q z.
2. r s z.
3. Ź(q (" s) z.
4. ŹŹ(p (" r) z.d.n.
5. p (" r ON : 4
1.1. p z.d.
1.2. q RO : 1, 1.1
1.3. q (" s DA : 1.2
2.1. r z.d.
2.2. s RO : 2, 2.1
2.3. q (" s DA : 2.2
sprz.1.1 sprz.(3, 1.3), 2.1 sprz.(3, 2.3)
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Metody algorytmiczne i pół-algorytmiczne
Metoda założeniowa Metoda zerojedynkowa
metoda pół-algorytymiczna metoda algorytmiczna
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Metody algorytmiczne i pół-algorytmiczne
Metoda założeniowa Metoda zerojedynkowa
metoda pół-algorytymiczna metoda algorytmiczna
Metoda algorytmiczna
Np. metoda zerojedynkowa, pozwala na rozwiązanie określonego
problemu w skończonej liczbie ściśle określonych kroków.
1 Jeżeli dowodzone wyrażenie jest prawem logiki, to metoda
zerojedynkowa pozwala w skończonej liczbie ściśle określonych
kroków stwierdzić, że jest to prawo logiki.
2 Jeżeli dowodzone wyrażenie nie jest prawem logiki, to metoda
zerojedynkowa pozwala w skończonej liczbie ściśle określonych
kroków stwierdzić, że nie jest to prawo logiki.
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Metody algorytmiczne i pół-algorytmiczne
Metoda założeniowa Metoda zerojedynkowa
metoda pół-algorytymiczna metoda algorytmiczna
Metoda półalgorytmiczna
Np. metoda założeniowa, pozwala na rozwiązanie danego problemu w
skończonej liczbie ściśle określonych kroków o ile tylko takie rozwiązanie
istnieje.
1 Jeżeli dowodzone wyrażenie jest prawem logiki, to metoda
założeniowa pozwala w skończonej liczbie ściśle określonych kroków
skonstruować dowód założeniowy tego wyrażenia, czyli stwierdzić, że
jest to prawo logiki.
2 Jeżeli jednak dowodzone wyrażenie nie jest prawem logiki, to
metoda założeniowa nie pozwala w skończonej liczbie ściśle
określonych kroków stwierdzić, że nie jest to prawo logiki.
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Pojęcie  tezy
Teza
Tezą jest każde wyrażenie dla którego istnieje dowód.
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Pojęcie  tezy
Teza
Tezą jest każde wyrażenie dla którego istnieje dowód.
Ponieważ pojęcie  dowodu jest relatywne względem teorii, pojęcie
 tezy jest relatywne względem teorii logicznej.
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Pojęcie  tezy
Teza
Tezą jest każde wyrażenie dla którego istnieje dowód.
Ponieważ pojęcie  dowodu jest relatywne względem teorii, pojęcie
 tezy jest relatywne względem teorii logicznej.
Mamy zatem tezy KRZ, tezy WRP, itd.
Teza KRZ
Tezą KRZ jest każde wyrażenie sensowne KRZ dla którego istnieje
założeniowy dowód niewprost.
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Pojęcie  tezy w KRZ II
To, że � jest tezą zapisujemy symbolicznie jako �.
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Indukcyjny charakter definicji tezy KRZ
Definicja tezy KRZ ma charakter indukcyjny ze względu na budowę
dowodu założeniowego niewprost:
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Indukcyjny charakter definicji tezy KRZ
Definicja tezy KRZ ma charakter indukcyjny ze względu na budowę
dowodu założeniowego niewprost:
 najpierw mówimy o tezach, dla których istnieją  proste dowody,
tj. dowody, które nie zakładają istnienia żadnych innych dowodów 
są to tezy pierwszego rzędu,
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Indukcyjny charakter definicji tezy KRZ
Definicja tezy KRZ ma charakter indukcyjny ze względu na budowę
dowodu założeniowego niewprost:
 najpierw mówimy o tezach, dla których istnieją  proste dowody,
tj. dowody, które nie zakładają istnienia żadnych innych dowodów 
są to tezy pierwszego rzędu,
 potem mówimy o pozostałych tezach, dla których nie istnieją
 proste dowody, tj. dowody, które nie zakładają istnienia żadnych
innych dowodów  są to tezy wyższych rzędów,
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Indukcyjny charakter definicji tezy KRZ
Definicja tezy KRZ ma charakter indukcyjny ze względu na budowę
dowodu założeniowego niewprost:
 najpierw mówimy o tezach, dla których istnieją  proste dowody,
tj. dowody, które nie zakładają istnienia żadnych innych dowodów 
są to tezy pierwszego rzędu,
 potem mówimy o pozostałych tezach, dla których nie istnieją
 proste dowody, tj. dowody, które nie zakładają istnienia żadnych
innych dowodów  są to tezy wyższych rzędów,
przysłówki  najpierw i  potem oznaczają w tym kontekście
porządek definiowania:
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Indukcyjny charakter definicji tezy KRZ
Definicja tezy KRZ ma charakter indukcyjny ze względu na budowę
dowodu założeniowego niewprost:
 najpierw mówimy o tezach, dla których istnieją  proste dowody,
tj. dowody, które nie zakładają istnienia żadnych innych dowodów 
są to tezy pierwszego rzędu,
 potem mówimy o pozostałych tezach, dla których nie istnieją
 proste dowody, tj. dowody, które nie zakładają istnienia żadnych
innych dowodów  są to tezy wyższych rzędów,
przysłówki  najpierw i  potem oznaczają w tym kontekście
porządek definiowania:
rozumienie tego, czym są tezy pierwszego rzędu, nie zakłada
rozumienia tego, czym są tezy wyższych rzędów,
Założeniowy system klasycznego rachunku zdań
Metody algorytmiczne i pół-algorytmiczne
Indukcyjny charakter definicji tezy KRZ
Definicja tezy KRZ ma charakter indukcyjny ze względu na budowę
dowodu założeniowego niewprost:
 najpierw mówimy o tezach, dla których istnieją  proste dowody,
tj. dowody, które nie zakładają istnienia żadnych innych dowodów 
są to tezy pierwszego rzędu,
 potem mówimy o pozostałych tezach, dla których nie istnieją
 proste dowody, tj. dowody, które nie zakładają istnienia żadnych
innych dowodów  są to tezy wyższych rzędów,
przysłówki  najpierw i  potem oznaczają w tym kontekście
porządek definiowania:
rozumienie tego, czym są tezy pierwszego rzędu, nie zakłada
rozumienia tego, czym są tezy wyższych rzędów,
rozumienie tego, czym są tezy jakiegoś wyższego rzędu, zakłada
rozumienie tego, czym są tezy niższych rzędów.
Założeniowy system klasycznego rachunku zdań
Udowodnij!
Udowodnij, że poniższe formuły są tezami KRZ (1)
1 p p
2 p a" p
3 p '" p p
4 p (" p p
5 p (" Źp
6 Ź(p '" Źp)
7 (p q) ((q r) (p r))
8 (p (" q) (Źq p)
9 (ŹŹp p)
10 (p ŹŹp)
11 (p a" ŹŹp)
12 (p q) '" (r s) (p '" r q '" r)
Założeniowy system klasycznego rachunku zdań
Udowodnij!
Udowodnij, że poniższe formuły są tezami KRZ (2)
1 (p q '" r) (p q) '" (p r)
2 (p (" q r) (p r) '" (q r)
3 (p Źp) Źp
4 (p q '" Źq) Źp
5 Ź(p (" q) a" Źp '" Źq
6 p '" Źp q
7 Ź(p '" q) a" p Źq
8 (p q) '" (r s) (p (" r q (" r)
9 (p r) '" (q r) '" (p (" q) r
10 (p q) '" (r s) '" (p (" r) (q (" s)
11 (p q) '" (r s) '" Ź(q (" s) Ź(p (" r)
12 (p a" q) a" (p q) '" (q p)
Założeniowy system klasycznego rachunku zdań
Udowodnij!
Udowodnij, że poniższe formuły są tezami KRZ (3)
1 q (p q)
2 p '" q r a" p '" Źr Źq
3 (p q) '" Źq Źp
4 (p q) a" (Źq Źp)
5 Ź(p '" q) a" Źp (" Źq
6 p q a" Źp (" q
7 p '" q r a" p (q r)
8 Ź(p '" q) a" Źp (" Źq
9 p q a" Źp (" q
10 p '" q r a" p (q r)
11 (p q) '" (q r) (p r)