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 ” „ / ” „ → ” „ ≡

”

”