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
Reguły dołączania nowych wierszy do dowodu
Założeniowe dowody wprost – przykłady
4
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
8
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 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 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 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 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ą.
1
Zakładamy przeciwnie:
√
2 jest liczbą wymierną.
2
Z definicji liczby wymiernej wynika, że istnieją takie liczby naturalne
m i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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)
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 i n (n 6= 0), że
√
2 =
m
n
, przy czym
m
n
jest ułamkiem
nieskracalnym.
3
Zatem, m
2
= 2n
2
.
4
Stąd, m
2
jest liczbą parzystą.
5
m jest parzyste, tj. m = 2k.
6
Więc, 4k
2
= 2n
2
.
7
Stąd, n
2
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ż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ż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ż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ż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ż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ż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ż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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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
ϕ → ψ
ψ → ϕ
ϕ ≡ ψ
Klasyczny rachunek zdań (dedukcja naturalna)
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
ϕ → ψ
ψ → ϕ
ϕ ≡ ψ
Klasyczny rachunek zdań (dedukcja naturalna)
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
ϕ ≡ ψ
ϕ ≡ ψ
ϕ → ψ
ψ → ϕ
Klasyczny rachunek zdań (dedukcja naturalna)
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
ϕ ≡ ψ
ϕ ≡ ψ
ϕ → ψ
ψ → ϕ
Klasyczny rachunek zdań (dedukcja naturalna)
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
ϕ ≡ ψ
ϕ ≡ ψ
ϕ → ψ
ψ → ϕ
Klasyczny rachunek zdań (dedukcja naturalna)
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ż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ż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ż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ż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ż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ż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ż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ż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ż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ż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ż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ż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ż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)
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)
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)
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)
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ż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ż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ż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ż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ż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ż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)
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)
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)
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)
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)
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)
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
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
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
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
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
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
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
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
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 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 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 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
(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 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 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 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
(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 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 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 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
(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ł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ł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ł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)
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
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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
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 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 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ń
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ń
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ń
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ń
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)
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 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 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 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 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 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 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 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 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
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
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
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
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)
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 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 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 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 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 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 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 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 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 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 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
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
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
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
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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 pół-algorytymiczna
Metoda zerojedynkowa
metoda algorytmiczna
Klasyczny rachunek zdań (dedukcja naturalna)
Metody algorytmiczne i pół-algorytmiczne
Metody algorytmiczne i pół-algorytmiczne
Metoda założeniowa
metoda pół-algorytymiczna
Metoda zerojedynkowa
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 pół-algorytymiczna
Metoda zerojedynkowa
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)
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)
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)
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)
Pojęcie ”tezy” w KRZ II
To, że ϕ jest tezą zapisujemy symbolicznie jako ` ϕ.
Klasyczny rachunek zdań (dedukcja naturalna)
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)
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)
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)
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)
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)
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, że poniższe formuły są tezami KRZ (1)
1
p → p
2
p ≡ 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 𠪪p)
12
(p → q) ∧ (r → s) → (p ∧ r → q ∧ r )
Klasyczny rachunek zdań (dedukcja naturalna)
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) ≡ ¬p ∧ ¬q
6
p ∧ ¬p → q
7
¬(p ∧ q) ≡ 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 ≡ q) ≡ (p → q) ∧ (q → p)
13
q → (p → q)
Klasyczny rachunek zdań (dedukcja naturalna)
Udowodnij, że poniższe formuły są tezami KRZ (3)
1
p ∧ q → r ≡ p ∧ ¬r → ¬q
2
(p → q) ∧ ¬q → ¬p
3
(p → q) ≡ (¬q → ¬p)
4
¬(p ∧ q) ≡ ¬p ∨ ¬q
5
p → q ≡ ¬p ∨ q
6
p ∧ q → r ≡ p → (q → r )
7
(p → q) ∧ (q → r ) → r )
8
¬(p ∧ q) ≡ ¬p ∨ ¬q
9
p → q ≡ ¬p ∨ q
10
p ∧ q → r ≡ p → (q → r )
11
(p → q) ∧ (q → r ) → (p → r )
Document Outline
- Przykład dowodu załozeniowego wprost
- Przykład dowodu załozeniowego niewprost
- Załozeniowy dowód wprost
- Załozeniowy dowód niewprost
- Wtórne reguły dołaczania nowych wierszy do dowodu
- Metody algorytmiczne i pół-algorytmiczne
- Co to jest teza?
- Udowodnij!
Wyszukiwarka
Podobne podstrony:
03 Klasyczny rachunek zdań świat fcji prawdziwościowychid 4395
Logika, KLASYCZNY RACHUNEK ZDAŃ
03 Klasyczny rachunek zdań, świat fcji prawdziwościowych
1 Klasyczny Rachunek Zdań
Klasyczny rachunek zdań Adekwatność
Klasyczny rachunek zdań metoda 0 1
moduł 3 Klasyczny rachunek zdań, LOGIKA 2006
Modul 3 Klasyczny rachunek zdan
logika klasyczny rachunek zdan(1)
03 Klasyczny rachunek zdań świat fcji prawdziwościowychid 4395
więcej podobnych podstron