Metoda 0-1 dowodzenia tautologii (logika)

Jeśli znasz już zasadę tworzenia zdań prostych np. koniunkcji, alternatywy etc, to czas poznać metodę dowodzenia. Jeżeli mamy zdanie:

p ⇒ (p ∨ (∼q))

Możemy postarać się dowieść prawdy twierdzenia p ⇒ (p ∨ (∼q)) [czyt. jeżeli p to p lub nie q]

Przygotowujemy tabelkę. W tabeli umieszczamy odpowiednio, po kolei:

• p
• q
• ∼q
• p ∨ (∼q)
• oraz całe zdanie złożone:  p ⇒ (p ∨ (∼q))

p	q	∼q	(p∨ (~q))	p⇒(p∨ (~q))
1	1	.	.	.
1	0	.	.	.
0	1	.	.	.
0	0	.	.	.

Przygotowaliśmy tabelkę i przyporządkowaliśmy wartości dla p i q. 

Teraz będziemy wpisywać wartości logiczne dla poszczególnych przypadków.

~q to zaprzeczenie dla q, więc bedzie miało przeciwną wartość. 

(p∨ (~q)) - teraz porównujemy pierwszą kolumnę tabeli i trzecią ze znakiem ∨.

:1 ∨ :0 = wartość logiczna :1 (dlatego należy pamiętać zasady w tabelkach dla zdań prostych)

teraz ostatnia kolumna - porównujemy czwartą i pierwszą kolumnę - :1 ⇒ :1 = wartość logiczna :1

p	q	∼q	(p∨ (~q))	p⇒(p∨ (~q))
1	1	0	1	1
1	0	.	.	.
0	1	.	.	.
0	0	.	.	.

Teraz robimy to samo z innymi kolumnami.

p	q	∼q	(p∨ (~q))	p⇒(p∨ (~q))
1	1	0	1	1
1	0	1	1	.
0	1	0	0	.
0	0	1	1	.

p	q	∼q	(p∨ (~q))	p⇒(p∨ (~q))
1	1	0	1	1
1	0	1	1	1
0	1	0	0	1
0	0	1	1	1

Skończyliśmy dowód. Teraz najważniejsza jest ostatnia kolumna tabeli.

Wyszły nam same wartości logiczne :1

Takie zjawisko nazywamy TAUTOLOGIĄ. 

Tautologia jest to wyrażenie, które jest prawdziwe na mocy swojej formy – budowy (dokładniej: które jest prawdziwe w każdej niepustej dziedzinie; zdanie zawsze prawdziwe)

Więc niezależnie od wartościowania p i q, zdanie będzie zawsze prawdziwe.

Jeśli w tabeli wyjdzie nam przymajmniej jedno zero, to zdanie nie będzie już tautologią. Oznacza to, że nie zawsze będzie prawdziwe.

Na początku dowody zero-jedynkowe wydają się skomplikowane, ale jeśli poćwiczysz - będziesz wkrótce robić je jak z automatu :)

Zadanie

Dowiedź prawdziwość zdań

1. p ∨ q ⇔ q ∨ p
2. ~(p ∨ q) ⇔ ~p ∧ ~q

Miłego dnia,

A. G.