Klasyczny rachunek zdań (dedukcja naturalna)
Logika dla informatyków
Klasyczny rachunek zdań (część II)
DEDUKCJA NATURALNA
Robert Trypuz
Katedra Logiki KUL
25 marca 2011
Klasyczny rachunek zdań (dedukcja naturalna)
Plan wykładu
1 Przykład dowodu założeniowego wprost
2 Przykład dowodu założeniowego niewprost
3 Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Założeniowe dowody wprost  przykłady
4 Założeniowy dowód niewprost
Sprzeczność syntaktyczna
Założeniowe dowody niewprost  przykłady
5 Wtórne reguły dołączania nowych wierszy do dowodu
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 Co to jest teza?
8 Udowodnij!
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
1 Załóżmy, że 231|n.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
1 Załóżmy, że 231|n.
2 Wynika stąd, że 3|n i 7|n i 11|n.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
1 Załóżmy, że 231|n.
2 Wynika stąd, że 3|n i 7|n i 11|n.
3 7|n i 11|n.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu założeniowego wprost
Przykład dowodu założeniowego wprost
Każda liczba podzielna przez 231 jest podzielna przez 77.
1 Załóżmy, że 231|n.
2 Wynika stąd, że 3|n i 7|n i 11|n.
3 7|n i 11|n.
4 Zatem 77|n.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbÄ… wymiernÄ….
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu założeniowego niewprost
Przykład dowodu założeniowego niewprost
"
2 nie jest liczbÄ… wymiernÄ….
"
1 Zakładamy przeciwnie: 2 jest liczbą wymierną.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu 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Ä….
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu 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Ä….
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Przykład dowodu 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.
9 PodsumowujÄ…c: m i n sÄ… parzyste, co jest sprzeczne z wierszem 2.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Założeniowe dowody wprost
Õ1 (Õ2 (· · · (Õn-1 Õn) . . . ). (1)
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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:
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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:
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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,
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu I
Reguła odrywania
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu I
Reguła odrywania
RO Õ È
Õ
È
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu II
Reguła dołączania koniunkcji
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu II
Reguła dołączania koniunkcji
DK Õ
È
Õ '" È
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu III
Reguła opuszczania koniunkcji
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
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)
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
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 Õ '" È Õ '" È
Õ È
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu IV
Reguła dołączania alternatywy
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
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)
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
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 Õ È
Õ (" È Õ (" È
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu V
Reguła opuszczania alternatywy
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu V
Reguła opuszczania alternatywy
OA Õ (" È
ŹÕ
È
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
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" È
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Reguły dołączania nowych wierszy do dowodu
Reguły dołączania nowych wierszy do dowodu VII
Reguła opuszczania równoważności
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
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)
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
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" È
Õ È È Õ
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Założeniowe dowody wprost  przykłady
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Założeniowe dowody wprost  przykłady
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
1. (p q) '" (q r) z.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Założeniowe dowody wprost  przykłady
Założeniowe dowody wprost  przykłady
(p q) '" (q r) (p r). (2)
1. (p q) '" (q r) z.
2. p z.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Założeniowe dowody wprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Założeniowe dowody wprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Założeniowe dowody wprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód wprost
Założeniowe dowody wprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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:
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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:
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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,
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Sprzeczność syntaktyczna
Sprzeczność syntaktyczna
Wiersze sprzeczne sÄ… to wiersze o postaci È i ŹÈ.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Sprzeczność syntaktyczna
Sprzeczność syntaktyczna
Wiersze sprzeczne sÄ… to wiersze o postaci È i ŹÈ.
wyrażenie  p q jest sprzeczne z wyrażeniem  Ź(p q) ,
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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 ,
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód 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)
.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
Założeniowe dowody niewprost  przykłady I
Udowodnimy jedno z praw reductio ad absurdum.
(Źp p) p. (3)
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
Założeniowe dowody niewprost  przykłady I
Udowodnimy jedno z praw reductio ad absurdum.
(Źp p) p. (3)
1. Źp p z.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
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.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
1. (Źp q) '" Źq z.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
Założeniowe dowody niewprost  przykłady II
(Źp q) '" Źq p. (4)
1. (Źp q) '" Źq z.
2. Źp z.d.n.
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Założeniowy dowód niewprost
Założeniowe dowody niewprost  przykłady
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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Wtórne reguły dołączania nowych wierszy do dowodu
reguła wtórna dowód w pigułce
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Wtórne reguły 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:
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Wtórne reguły 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
È
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady I
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady I
Reguła opuszczania podwójnej negacji
ON ŹŹÕ
Õ
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
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ć:
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady II
Roszerzona reguła opuszczania alternatywy
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady II
Roszerzona reguła opuszczania alternatywy
(ta reguła ma cztery schematy)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady II
Roszerzona reguła opuszczania alternatywy
(ta reguła ma cztery schematy)
OA Õ (" È Õ (" È ŹÕ (" È Õ (" ŹÈ
ŹÕ ŹÈ Õ È
È Õ È Õ
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady III
Reguła modus tollendo tollens
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady III
Reguła modus tollendo tollens
(ta reguła ma cztery schematy)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady III
Reguła modus tollendo tollens
(ta reguła ma cztery schematy)
TOLL Õ È Õ ŹÈ ŹÕ È ŹÕ ŹÈ
ŹÈ È ŹÈ È
ŹÕ ŹÕ Õ Õ
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady IV
Reguła negowania alternatywy
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady IV
Reguła negowania alternatywy
(ta reguła ma dwa schematy)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguły wtórne  przykłady IV
Reguła negowania alternatywy
(ta reguła ma dwa schematy)
NA Ź(Õ (" È) Ź(Õ (" È)
ŹÕ ŹÈ
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
Reguła dołączania implikacji do dowodu
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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
(p (" q r) (p r) '" (q r). (5)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła dołączania implikacji do dowodu
Reguła dołączania implikacji do dowodu
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Reguła obalania dodatkowych założeń
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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ą.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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 ŹÈ.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła obalania dodatkowych założeń
Ź(p (" q) Źp '" Źq (6)
1. Ź(p (" q) z.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
Reguła rozgałęzionego dowodu wprost
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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ą.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu wprost
(p q) '" (r s) (p (" r q (" s) (7)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
Reguła rozgałęzionego dowodu niewprost
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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ą.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły dołączania nowych wierszy do dowodu
Reguła rozgałęzionego dowodu niewprost
(p q) '" (r s) (Ź(q (" s) Ź(p (" r)) (8)
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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.
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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
Klasyczny rachunek zdań (dedukcja naturalna)
Wtórne reguły 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)
Klasyczny rachunek zdań (dedukcja naturalna)
Metody algorytmiczne i pół-algorytmiczne
Metody algorytmiczne i pół-algorytmiczne
Metoda założeniowa Metoda zerojedynkowa
metoda pół-algorytymiczna metoda algorytmiczna
Klasyczny rachunek zdań (dedukcja naturalna)
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.
Klasyczny rachunek zdań (dedukcja naturalna)
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.
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
Pojęcie  tezy
Teza
Tezą jest każde wyrażenie dla którego istnieje dowód.
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
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.
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
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.
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
Pojęcie  tezy w KRZ II
To, że Õ jest tezÄ… zapisujemy symbolicznie jako Õ.
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
Indukcyjny charakter definicji tezy KRZ
Definicja tezy KRZ ma charakter indukcyjny ze względu na budowę
dowodu założeniowego niewprost:
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
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,
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
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,
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
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:
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
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,
Klasyczny rachunek zdań (dedukcja naturalna)
Co to jest teza?
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.
Klasyczny rachunek zdań (dedukcja naturalna)
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)
Klasyczny rachunek zdań (dedukcja naturalna)
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)
13 q (p q)
Klasyczny rachunek zdań (dedukcja naturalna)
Udowodnij!
Udowodnij, że poniższe formuły są tezami KRZ (3)
1 p '" q r a" p '" Źr Źq
2 (p q) '" Źq Źp
3 (p q) a" (Źq Źp)
4 Ź(p '" q) a" Źp (" Źq
5 p q a" Źp (" q
6 p '" q r a" p (q r)
7 (p q) '" (q r) 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)