11.04.2014

p	q	P ^ q	P q	P q	P ≡ q	P v q	P q	P ↓ q	P / q
		Koniunkcja „i” „albo”	Implikacja „jeśli… to”, „O ile”	Implikacja odwrócona	Równoważność „wtedy i tylko wtedy gdy”	Alternatywa zwykła „lub”, „albo”	Alternatywa rozłączna „albo… albo”	Binegacja „ani… ani”	Dysjunkcja „bądź”
1	1	1	1	1	1	1	0	0	0
1	0	0	0	1	0	1	1	0	1
0	1	0	1	0	0	1	1	0	1
0	0	0	1	1	1	0	0	1	1

Wartość 1 – prawda
Wartość 0 - nieprawda

PRZYKŁAD

[(p v q) r] [p (q ^ r)]

Mamy dowieść, że zdanie nie jest prawdziwe (czyli, że nie jest tautologią). W przypadku implikacji może to nastąpić tylko w przypadku, gdy drugi jej człon będzie równy 0. Wtedy całość równania będzie wyglądała tak:
1 0
i to (zgodnie z tabelką) będzie równe 0 (czyli będzie nieprawdą - tautologią). Skoro zakładamy, że całość jest nieprawdą, to możemy sobie zanotować:

[(p v q) r] [p (q ^ r)]
zał. 0
\____________/ \____________/
1 0

czyli
(p v q) r = 1 p (q ^ r) = 0

Zaczniemy od dowiedzenia, że p (q ^ r) jest nieprawdą (0). Tak będzie łatwiej, bo implikacja jest fałszywa tylko w jednym przypadku, a prawdziwa w trzech przypadkach…
Czyli wiemy już, że p musi być prawdziwe (1), a q ^ r jest nieprawdziwe (0).
p = 1
Żeby dowiedzieć się jakie wartości przyjmują q oraz r będziemy musieli podstawić aktualne dane pod lewą „flankę” to jest (p v q) r [a więc będziemy mieli (1 v q) r], dlatego, że nie możemy tylko na podstawie prawej „flanki” ustalić wartości q oraz r (istniałyby 3 możliwości rozwiązań – według tabeli koniunkcji).
Nasza lewa strona (1 v q) r ma ostatecznie wynosić 1. Możemy rozpisać w postaci tabeli różne możliwości rozwiązań.

p	q	p v q		p v q	r	(p v q) r
1	1	1		1	1	1
1	0	1		1	0	0
0	1	1		0	1	1
0	0	0		0	0	1

Na podstawie tych tabel możemy wywnioskować, że r z pewnością nie będzie mogło równać się 0 (bo wtedy cała nasza lewa flanka będzie nieprawdziwa). Czyli r = 1.
Teraz znamy już dwie niewiadome. p = 1, r = 1. Nie znamy q. Jego wartość możemy poznać rozwiązując całość, podstawiając odpowiednie liczby. Na podstawie obecnych wiadomości:

[(1 v q) 1] [1 (q ^ 1)]

Interpretacja lewej strony głównej implikacji nie da nam równoznacznej odpowiedzi, na pytanie jaką wartość przyjmuje q, więc patrzymy na prawą stronę całości formuły.
Żeby 1 (q ^ 1) równało się 0, to q musi równać się 0, bo 1 (0 ^ 1), to 1 0 = 0, a 1 (1 ^ 1), to 1 1 = 1.

Podstawiając q = 0 lewej „flance” otrzymamy (1 v 0) 1, które w dalszej kolejności będzie wynosić 1 (bo zarówno 1 1 równa się 1, jak i 0 1 wynosi 1).

Sprawdzając całość:
[(p v q) r] [p (q ^ r)]
[(1 v 0) 1] [1 (0 ^ 1)]
1 [1 0]
1 0
0

Czyli udało nam się dowieść, że cała funkcja wynosi 0, a więc wniosek z tego taki, że nie jest tautologiczna.

ostatecznie
p = 1 q = 0 r = 1

Zadania


1) [(p ~q) ( ~q ~p)] ~ (p ^ q)
\_________________/ zał. 0 \_____/
1 0

Skoro ~ (p ^ q) równa się 0, to p ^ q równa się 1.
Koniunkcja jest prawdziwa tylko wtedy, gdy oba jej człony są prawdziwe, czyli
p = 1 oraz q = 1

Podstawiamy gotowe dane do całej formuły:
[(p ~q) ( ~q ~p)] ~ (p ^ q)
[(1 ~ 1) (~ 1 ~ 1)] ~ (1 ^ 1)
[(1 0) (0 0)] ~ 1
[0 1] 0
1 0
0

Czyli funkcja nie jest tautologiczna.

=============================================================================
2) [(p ≡ q) r] (p v r )
\________/ zał. 0 \__/
1 0

p v r = 0
więc p = 0 i r = 0

(p ≡ q) r musi się równać 1
więc …
(0 ≡ q) 0
(0 ≡ 0) 0
1 0
1

Czyli ostatecznie: p = 0, q = 1, r = 0

Funkcja nie jest tautologiczna.

=============================================================================

3) [(p q) ^ (p ↓r)] ~ (q ≡ r)
\____________/ zał. 0 \____/
1 0

~ (q ≡ r) = 0 czyli q ≡ r = 1
albo zarówno q i r = 1 albo zarówno q i r = 0

[(p q) ^ (p ↓r)] musi się równać 1
czyli p q = 1 i p ↓ r = 1

Żeby p ↓ r = 1 to zarówno p jak i q muszą równać się 0.
Czyli p = 0 i r = 0.
Żeby ~ (q ≡ r) = 0, to q musi wynosić 0.
Podstawiając dane zajdzie sprzeczność, bo:
[(p q) ^ (p ↓r)] ~ (q ≡ r)
[(0 0) ^ (0 ↓ 0)] ~ (0 ≡ 0)
[0 ^ 1] ~ 1
0 0
1

Funkcja jest tautologiczna (prawdziwa), bo zachodzi sprzeczność.

=============================================================================

4) ~ [~ (p ^ q) v (p ≡ ~ r)] (r ≡ s)
\_______________/ zał. 0 \__/
1 0

r ≡ s = 0 czyli albo r = 1 i s = 1, albo r = 0 i s = 0
~ [~ (p ^ q) v (p ≡ ~ r)] = 1
więc ~ (p ^ q) v (p ≡ ~ r) = 0
alternatywa jest fałszywa tylko gdy oba jej człony równają się 0, więc…
~ (p ^ q) = 0 i p ≡ ~ r = 0
czyli p ^ q = 1 (zachodzi to tylko wtedy, gdy oba człony = 1)
czyli p = 1 i q = 1

1 ≡ ~ r musi równać się 0 , więc r = 1, bo 1 ≡ 0 = 0.
przy r ≡ s, r ma być równe 1, czyli s = 0

Czyli ostatecznie:
p = 1, q = 1, r = 1, s = 0

~ [~ (p ^ q) v (p ≡ ~ r)] (r ≡ s)
~ [~ (1 ^ 1) v (1 ≡ ~ 1)] (1 ≡ 0)
~ [~ 1 v (1 ≡ 0)] 0
~ [ 0 v 0 )] 0
~ 0 0
1 0
0

Funkcja nie jest tautologiczna.

=============================================================================

5) [(p q) r] (r v ~ q)
\_________/ zał. 0 \____/
1 0

r v ~ q = 0
r = 0 a q = 1

(p q) r = 1
r = 0 więc p q musi równać się 0
q = 1 więc p = 0 i wtedy 0 1 = 1
a 1 0 = 0

gdyby p = 1 to wtedy 1 1 = 1
a 1 0 = 0

więc funkcja jest tautologiczna. Zachodzi sprzeczność.

=============================================================================

6) [(p ≡ q) ^ (r p)] (q v r)

[(p ≡ q) ^ (r p)] (q v r)
zał. 0
\_________________/ \_____/
1 0

(p ≡ q) = 1 (r p) = 1 q v r = 0
Sprzeczność.

żeby ^ była prawdziwa to obie wartości w nawiasach muszą równać się 1
czyli (p ≡ q) = 1 i (r p) = 1

wiemy już, że q v r musi równać się 0, a to następuje tylko w przypadkach, gdy q = 0 i r = 0
czyli q = 0 i r = 0
nie znamy teraz p.
p ≡ 0 = 1 , równowartość może zajść, gdy p będzie się równało 0

skoro p = 0, to 0 0 = 0, to znaczy, że zaszła sprzeczność (bo alternatywa rozłączna byłaby prawdziwa gdybyśmy mieli wartości albo 1 i 0, albo 0 i 1).

Funkcja jest tautologiczna, zaszła sprzeczność.