Question

Sprawdź, czy jest to tautologią.
(q⇒(r ∨ ~p) ) ⇒ ( (p ∧ q) ⇒ (r ∨ ~q))

Answer 1

Jeśli schemat jest tautologią oznacza to, że jest on prawdziwy bez względu na to jakie wartości logiczne przyjmą zdania p,q,r. Zatem jeśli uda znaleźć się chociaż jedno takie przyporządkowanie, dla którego schemat będzie fałszywy to nie będzie on tautologią.

[q⇒(r ∨ ~p) ] ⇒ [ (p ∧ q) ⇒ (r ∨ ~q) ]
 1 1 0 0 0 1    0    1 1 1   0   0 0  01

Zakładamy, że główna implikacja jest fałszywa. Implikacja jest fałszywa tylko wtedy, gdy poprzednik jest prawdziwy a następnik fałszywy. W nawiasie kwadratowym po prawej stronie mamy fałszywą implikację zatem koniunkcja jest prawdziwa a alternatywa fałszywa. Koniunkcja jest prawdziwa tylko wtedy, gdy oba zdania są prawdziwe. Alternatywa jest fałszywa tylko wtedy, gdy oba zdania są fałszywe. Z koniunkcji wiemy, że q jest prawdziwe zatem jego zaprzeczenie jest fałszywe i alternatywa też jest fałszywa.  Wracamy na lewą stronę i podstawiamy pozostałe wartości logiczne. Skoro r jest fałszywe tak samo jak zaprzeczenie p to alternatywa też jest fałszywa. Skoro poprzednik implikacji jest prawdziwy a następnik będący alternatywą fałszywy to oznacza, że cała implikacja nie może być prawdziwa. Pogrubiona jedynka oznacza, że nastąpiła sprzeczność a to oznacza, że nie ma takiego przyporządkowania, dla którego ten schemat mógłby być fałszywy a to oznacza, że mamy do czynienia z tautologią.