METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
Istotą dowodu niewprost jest
Istotą dowodu niewprost jest
założenie, że badana funkcja nie
założenie, że badana funkcja nie
jest tautologią.
jest tautologią.
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
Istotą dowodu niewprost jest
Istotą dowodu niewprost jest
założenie, że badana funkcja nie
założenie, że badana funkcja nie
jest tautologią.
jest tautologią.
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
Jeżeli funkcja ma postać implikacji, to ma tę
Jeżeli funkcja ma postać implikacji, to ma tę
własność logiczną, że jest fałszywa, tylko gdy jej
własność logiczną, że jest fałszywa, tylko gdy jej
poprzednik jest prawdziwy, a następnik fałszywy.
poprzednik jest prawdziwy, a następnik fałszywy.
Stosując metodę opartą na dowodzie niewprost,
Stosując metodę opartą na dowodzie niewprost,
zakładamy, iż takie właśnie wartości przyjmuje
zakładamy, iż takie właśnie wartości przyjmuje
poprzednik i następnik badanej funkcji.
poprzednik i następnik badanej funkcji.
Następnie, zaczynając od poprzednika albo
Następnie, zaczynając od poprzednika albo
następnika, badamy, jakie wartości muszą przyjąć
następnika, badamy, jakie wartości muszą przyjąć
zmienne, aby poprzednik był prawdziwy bądź aby
zmienne, aby poprzednik był prawdziwy bądź aby
następnik był fałszywy.
następnik był fałszywy.
Po ustaleniu tych wartości podstawiamy je do
Po ustaleniu tych wartości podstawiamy je do
poprzednika bądź następnika, sprawdzając, czy
poprzednika bądź następnika, sprawdzając, czy
możliwe jest, aby poprzednik przyjął wartość
możliwe jest, aby poprzednik przyjął wartość
prawdy, a następnik fałszu.
prawdy, a następnik fałszu.
Jeżeli jest to możliwe, to badana funkcja nie jest
Jeżeli jest to możliwe, to badana funkcja nie jest
tautologią.
tautologią.
Jeżeli nie jest to możliwe, to badana funkcja jest
Jeżeli nie jest to możliwe, to badana funkcja jest
tautologią.
tautologią.
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
[ (p → q) . p ] → q
[ (p → q) . p ] → q
0
0
1
1
0
0
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
[ (p → q) . p ] → q
[ (p → q) . p ] → q
0
0
0
0
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
[ (p → q) . p ] → q
[ (p → q) . p ] → q
0
0
0
0
0 0
0 0
1 0
1 0
0
0
0
0
1
1
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
INNY PRZYKŁAD:
INNY PRZYKŁAD:
[ (p → q) .
[ (p → q) .
(p → r) ] → (q → p)
(p → r) ] → (q → p)
0
0
1
1
0
0
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
[ (p → q) . (p → r) ] → (q → p)
[ (p → q) . (p → r) ] → (q → p)
0
0
0
0
1
1
0
0
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
[ (p → q) . (p → r) ]
[ (p → q) . (p → r) ]
0 1 0 1
0 1 0 1
0 1 0 0
0 1 0 0
1 1
1 1
1
1
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
[ (p → q)
[ (p → q)
.
.
(p → r) ] → (q → p)
(p → r) ] → (q → p)
0
0
1
1
0
0
1
1
1
1
0
0
1
1
1
1
1
1
0
0
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
[ (p → q)
[ (p → q)
.
.
(p → r) ] → (q → p)
(p → r) ] → (q → p)
0 1 0 0
0 1 0 0
1 0
1 0
1 1
1 1
1
1
0
0
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
Jeżeli Zenek jest adwokatem, to Zenek
Jeżeli Zenek jest adwokatem, to Zenek
nie jest sędzią. A jeżeli Zenek jest
nie jest sędzią. A jeżeli Zenek jest
sędzią, to Zenek nie jest adwokatem.
sędzią, to Zenek nie jest adwokatem.
Zatem, jeśli Zenek jest sędzią, to
Zatem, jeśli Zenek jest sędzią, to
nieprawda, że Zenek jest adwokatem.
nieprawda, że Zenek jest adwokatem.
Zenek jest adwokatem.
Zenek jest adwokatem.
p
p
Zenek jest sędzią.
Zenek jest sędzią.
q
q
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
p → ~
p → ~
q
q
q
q
→ ~
→ ~
p
p
q
q
→ ~
→ ~
p
p
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
p → ~
p → ~
q
q
p → ~
p → ~
q
q
q
q
→ ~
→ ~
p
p
(
(
p → ~
p → ~
q
q
) . (q
) . (q
→ ~
→ ~
p)
p)
[(
[(
p → ~
p → ~
q
q
) . (q
) . (q
→ ~
→ ~
p)]
p)]
→
→
(q
(q
→ ~
→ ~
p)
p)
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
( … )
( … )
[ … ( … ) … ]
[ … ( … ) … ]
{ … [ … ( … ) … ] … }
{ … [ … ( … ) … ] … }
METODA OPARTA NA DOWODZENIU
METODA OPARTA NA DOWODZENIU
NIEWPROST
NIEWPROST
„
„
~
~
” „ . ” „ v ” „ / ” „ → ” „ ≡
” „ . ” „ v ” „ / ” „ → ” „ ≡
”
”