dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 1 z 9
ODPOWIEDZI NA ZADANIA DOMOWE
Z WYKA
ADU IV
Uwaga! W ćwiczeniach mają Państwo używać nieskróconej metody zerojedynkowej  ze względu na żmudność
nie podejmuję tutaj trudu przedstawienia pełnych odpowiedzi na ćwiczenia wymagające jej zastosowania 
podaję tylko rezultaty osiągnięte przy zastosowaniu metody skróconej.
Ćwiczenie 23
(A) Schematy z ćwiczenia 7:
W poniższym ćwiczeniu  kontrprzykład znaczy tyle, co  kontrprzykład dla tautologiczności danego
zdania , co z kolei oznacza takie przypisanie wartości logicznej zmiennej p, aby dane zdanie było fałszywe.
(a) (b)
0 0 0 0 0 0
p '" p p (" p
kontrprzykład: v(p)=0 kontrprzykład: v(p)=0
sprawdzenie: 0 '" 0 = 0 sprawdzenie: 0 (" 0 = 0
(c) (d)
1 0 0 1 0 0
p p p a" p
kontrprzykład jest niemożliwy v(p)=0`" 1 kontrprzykład jest niemożliwy v(p)=0`" 1
TAUTOLOGIA TAUTOLOGIA
(e) (f)
0 0 0 0 01
p '" ~p p (" ~p
kontrprzykład dla v(p) = 0
kontrprzykład jest niemożliwy v(p)=0`" 1
sprawdzenie: 0 '" ~0 = 0 '" 1 = 0
TAUTOLOGIA
(g) (h)
0 1 1 10 0 1 1
~(p '" ~p) ~(p (" ~p)
kontrprzykład jest dla v(p)=1
kontrprzykład jest niemożliwy v(p)=0`" 1
sprawdzenie: ~(1 (" ~1) = ~(1 (" 0) = ~1=0
TAUTOLOGIA
(i) (j)
1 01 0 0 1 0 0 10
~(~p) p p ~(~p)
kontrprzykład jest niemożliwy v(p)=0`" 1 kontrprzykład jest niemożliwy v(p)=0`" 1
TAUTOLOGIA TAUTOLOGIA
(k) (l)
1 0 1 0 01 1 0 10 0 0
p (p ~p) p (~p p)
kontrprzykład dla v(p) = 1
kontrprzykład jest niemożliwy v(p)=0`" 1
sprawdzenie: 1 (1~1) = 1 (1 TAUTOLOGIA
0) = 1 0 = 0
dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 2 z 9
Schematy z ćwiczenia 8:
W poniższym ćwiczeniu  kontrprzykład znaczy tyle, co  kontrprzykład dla tautologiczności danego
zdania , co z kolei oznacza takie przypisanie wartości logicznej zmiennym p i q, aby dane zdanie było
fałszywe.
(a) (b)
1 1 0 0 1 0 1 0 0
(p '" q) p p (p '" q)
kontrprzykład dla v(p)=1, v(q) = 0
kontrprzykład jest niemożliwy v(p)=0`" 1
sprawdzenie: 1 (1 '" 0) = 1 0 = 0
TAUTOLOGIA
(c) (d)
0 1 1 0 0 1 0 0 0 0
(p (" q) p p (p (" q)
kontrprzykład dla v(p)=0, v(q) = 1
kontrprzykład jest niemożliwy v(p)=0`" 1
sprawdzenie: (0 (" 1) 0 = 1 0 = 0
TAUTOLOGIA
(e) (f)
10 0 0 1 1 1 10 0 0 0 1 1
~p ~(p '" q) ~p ~(p (" q)
kontrprzykład dla v(p) = 0, v(q) = 1
kontrprzykład jest niemożliwy v(p)=0`" 1
TAUTOLOGIA sprawdzenie: ~0 ~(0 (" 1) = 1 ~1 =
1 0 = 0
(g) (h)
1 1 10 0 0 1 0 10 0 0
(p '" ~p) q p (~p q)
kontrprzykład jest niemożliwy v(p)=0`" 1 kontrprzykład jest niemożliwy v(p)=0`" 1
TAUTOLOGIA TAUTOLOGIA
(B)
Por. ćwiczenie 24(A)
Ćwiczenie 24 (A)
(a) (b)
0
0 1 1 0 1 0 0 1 1 0 0 10 0 01
(p q) (q p) (p q) (~q ~p)
kontrprzykład dla v(p)=0, v(q)=1 kontrprzykład jest niemożliwy
TAUTOLOGIA
(c) (d)
0
1 1 0 1 1 0 0 0 1 1 1 1 0 0
[(p q) '" p] q [(p q) '" q] p
kontrprzykład jest niemożliwy kontrprzykład dla v(p)=0, v(q)=1
TAUTOLOGIA
dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 3 z 9
(e) (f)
1 0
(i) 1 0 1 0 1 1 1 (i) 0 0 0 0 0 1 0
(p '" q) a" (q '" p) (p (" q) a" (q (" p)
(ii) 1 1 1 0 1 0 1 (ii) 0 1 0 0 0 0 0
1 0
kontrprzykład jest niemożliwy kontrprzykład jest niemożliwy
TAUTOLOGIA TAUTOLOGIA
O ćwiczeniu (g)
Proszę zwrócić uwagę, że aby stwierdzić, że mamy do czynienia z tautologią konieczne jest wykazanie, że
we wszystkich możliwych przypadkach nie możemy znalez
ć kontrprzykładu. Aby stwierdzić, że mamy do
czynienia z tautologią musimy rozważyć wszystkie możliwości. Natomiast wystarczy znalez
ć choćby jeden
kontrprzykład (tylko w jednej z możliwości) i wystarczy on już do wykazania, że dany schemat tautologią
nie jest.  Nie musimy rozważać wszystkich możliwości do końca, jeśli jedna z nich okazuje się
kontrprzykładem. To uwaga, która nader przyda się przed podejściem do ćwiczenia (g)
(g)
Ponieważ mamy do czynienia z równoważnością, więc
0
poszukując kontrprzykładu tautologiczności tej
(i) 0 0 1 0 0 10 1 10
równoważności mamy do rozważenia dwie możliwości, w
~(p '" q) a" (~p '" ~q)
których równoważność byłaby fałszywa: (i) gdy pierwszy
(ii) 1 0 0 0
człon jest fałszywy, a drugi prawdziwy, (ii) gdy pierwszy
(ii-a) 1 1 0 0 0 01 0 10
człon jest prawdziwy a drugi fałszywy. W sytuacji (i),
(ii-b)
kontrprzykład jest niemożliwy. Sytuacja (ii) natomiast zdaje
(ii-c)
się wymuszać na nas rozważenie kolejnych (sic!) trzech
możliwości (zarówno bowiem koniunkcja p '" q, jak i
kontrprzykład dla v(p)=1, v(q)=0
koniunkcja ~p '" ~q, będą fałszywe w dokładnie trzech
sytuacjach): (ii-a) gdy v(p)=1, v(q)=0, (ii-b) gdy v(p)=0,
v(q)=1, (ii-c) gdy v(p)=0, v(q)=0. Na szczęście, okazuje
się, że kontrprzykład możemy już znalez
ć w sytuacji (ii-a).
Ponieważ można znalez
ć kontrprzykład wiemy, że schemat
ten nie jest tautologią i możemy zaprzestać dalszych
poszukiwań kolejnych kontrprzykładów w pozostałych
sytuacjach.
(i) Przypadek (i) jest przypadkiem, który ponownie zdaje się
wymuszać abyśmy uwzględnili aż trzy możliwości
(i) 0 1 0 1
(alternatywa jest prawdziwa aż w trzech sytuacjach).
(i-a)0 1 1 0 0 01 1 10
Niestety musimy go rozważyć, gdyż w przypadku (ii)
okazuje się być niemożliwym znalezienie kontrprzykładu.
~(p (" q) a" (~p (" ~q)
(ii) 1 0 0 0 0 01 0 01 Lecz i tutaj już sytuacja (i-a) generuje kontrprzykład, więc
1 możemy zaprzestać dalszych poszukiwań.
kontrprzykład dla v(p)=1, v(q)=0
(h) (j)
0 0
(i) 0 1 1 1 0 01 1 01 (i) 0 0 1 0 0 10 1 10
~(p '" q) a" (~p (" ~q) ~(p (" q) a" (~p '" ~q)
(ii) 1 1 0 1 0 01 0 01 (ii) 1 0 0 0 0 10 0 10
1 1
kontrprzykład jest niemożliwy kontrprzykład jest niemożliwy
TAUTOLOGIA TAUTOLOGIA
dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 4 z 9
Ćwiczenie 24(B)
W poniższym ćwiczeniu  kontrprzykład znaczy tyle, co  kontrprzykład dla kontrtautologiczności danego
zdania , co z kolei oznacza takie przypisanie wartości logicznej zmiennej p, aby dane zdanie było
prawdziwe.
(a) Rozważenie sytuacji (i) i (iii) pozwala ustalić jakie musiałyby
być wartości p i q od razu, więc od nich zaczynamy  okazuje się
1
jednakże, że w obydwu tych sytuacjach nie znajdujemy
~(p q) (p q)
kontrprzykładu. Musimy rozważyć sytuację (ii), która rozpada się
na kolejne trzy podprzypadki, na szczęście już pierwszy z nich
0
pozwala nam znalez
ć kontrprzykład dla kontrtautologiczności
(i) 1 1 0 0 1 1 1 0
danego schematu. Gdy v(p)=1 a v(q)=1 schemat ten jest
prawdziwy, nie jest więc kontrtautologią.
(ii) 0 1 1 1
(iia) 0 1 1 1 1 1 1 1
1
(iii) 0 1 0 0 1 1 0 0
kontrprzykład dla v(p)=1, v(q)=0
(b) (c)
1
0 1 0 0 1 0 1 0 0
(i) 1 1 0 0 1 1 1 0
~[(p q) (" (q p)
~(p q) a" (p q)
(ii) 0 1 1 0 1 1 0 0
kontrprzykład jest niemożliwy
0
KONTRTAUTOLOGIA
kontrprzykład jest niemożliwy
KONTRTAUTOLOGIA
(d) (e)
1 1 1
0
1 1 0 1 1 01 0 0
(p q) '" (~p q)
(p q) '" ~(~p (" q)
W tym momencie najlepiej jest rozważyć dwie
kontrprzykład jest niemożliwy sytuacje (a) gdy p jest prawdziwe, (b) gdy p jest
KONTRTAUTOLOGIA fałszywe. Ze względu jednak na kształt tego
schematu nasz werdykt nie będzie się dla tych
sytuacji różnił. (Proszę to uzasadnić.)
(a)
1 1 1 1 01 1 1
(p q) '" (~p q)
kontrprzykład dla v(p)=1, v(q)=1,
oraz dla v(p)=0, v(q) = 1
(f)
0 1 1 0 1
(p q) '" (p ~q)
kontrprzykład dla v(p)=0, v(q)=1 lub v(q)=0
dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 5 z 9
Ćwiczenie 25
(a) S jest kontrtautologią
Uzasadnienie. Negacja S, czyli Ą#~Sń# jest tautologią. Pomyślmy o matrycy logicznej dla negacji S  nie
wiemy co prawda ile ma rzędów (S jest schematem złożonym i składa się na niego pewna liczba
zmiennych, ale ile nie wiemy1), ale wiemy, że we wszystkich rzędach matrycy logicznej dla negacji S
mamy jedynki (ponieważ negacja S jest tautologią)  możemy sobie to obrazowo przedstawić:
Negacja S S
?
M
1 ?
1 ?
1 ?
?
M
gdzie  &  oznacza powielenie wartości negacji S. Teraz musimy się zapytać, jak przedstawiać się będą
wartości logiczne dla niezanegowanego S. Jeśli negacja S jest prawdziwa w pewnym rzędzie, to S musi
być fałszywe. A ponieważ negacja S jest prawdziwa we wszystkich rzędach, więc S musi być we
wszystkich rzędach fałszywe, a zatem musi być kontrtautologią.
Negacja S S
M M
1 0
1 0
1 0
M
M
(b) S jest tautologią
(c) S jest tautologią
Uzasadnienie. Znów przedstawmy sobie matrycę logiczną, o której niewiele wiemy (w szczególności nie
wiemy ile ma rzędów). Wiemy jednak, że mamy wziąć pod uwagę dowolną tautologię, nazwijmy ją T
(która będzie prawdziwa we wszystkich rzędach matrycy), oraz że koniunkcja S i T, tj. Ą#S '" Tń# jest
tautologią, tj. jest prawdziwa również we wszystkich rzędach:
Ą#
Dowolna Tautologia T S
S '" Tń#
?
M M
1 ? 1
1 ? 1
1 ? 1
?
M M
Czy możemy powiedzieć coś o tym, jakim schematem jest S? Wez
my pod uwagę dowolny rząd. Jaką
wartość logiczną musi mieć S aby koniunkcja S i prawdziwego w tym rzędzie T była prawdziwa? S musi
być w tym rzędzie prawdziwa. To znaczy jednakże, że S musi być prawdziwa w każdym rzędzie, a zatem S
jest tautologią.
1
Jeśli S składa się z jednej zmiennej to matryca ma 21 rzędów, czyli 2; jeśli S składa się z dwóch
zmiennych to matryca ma 22 rzędów, czyli 4; jeśli z trzech  to matryca ma 23 rzędów, czyli 8; itd.
dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 6 z 9
Ą#
Dowolna Tautologia T S
S '" Tń#
M M M
1 1 1
1 1 1
1 1 1
M M M
(d) S jest kontrtautologią
Uzasadnienie. Znów przedstawmy sobie matrycę logiczną. Wiemy jednak, że mamy wziąć pod uwagę
dowolny schemat, nazwijmy go X, oraz że koniunkcja S i X jest kontrtautologią, tj. jest fałszywa we
wszystkich rzędach:
Ą#
Dowolny schemat X S
S '" Xń#
?
M M
 ? 0
 ? 0
 ? 0
?
M M
gdzie    oznacza, że nie wiemy jaka jest wartość logiczna X. Ponieważ X jest dowolnym schematem,
może więc być albo tautologią, albo kontrtautologią, albo zdaniem niezdeterminowanym. Jeśli tak, to nie
możemy założyć, że jest prawdziwy w jakimkolwiek rzędzie (wykluczałoby to bowiem możliwość, że jest
kontrtautologią), ani że jest fałszywy w jakimkolwiek rzędzie (wykluczałoby to możliwość, że jest
tautologią). Czy jednakże pomimo tej niewielkiem informacji możemy powiedzieć coś o S? Wez
my pod
uwagę dowolny rząd. Jaką wartość logiczną musi mieć S aby koniunkcja S i X była fałszywa? S musi być
w tym rzędzie fałszywe. To znaczy jednakże, że S musi być fałszywe w każdym rzędzie, a zatem S jest
kontrtautologią.
Ą#
Dowolny schemat X S
S '" Xń#
M M M
 0 0
 0 0
 0 0
M M M
(e) Nie można ustalić
Uzasadnienie. Znów przedstawmy sobie matrycę logiczną. Wiemy jednak, że mamy wziąć pod uwagę
dowolną tautologię, nazwijmy ją T, oraz że alternatywa S i T jest tautologią, tj. jest prawdziwa we
wszystkich rzędach:
dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 7 z 9
Ą#
Dowolny Tautologia S
S (" Tń#
?
M M
1 ? 1
1 ? 1
1 ? 1
?
M M
Czy w takiej sytuacji możemy określić jednoznacznie, jakiego typu schematem musi być S? Nie.
Alternatywa jest bowiem prawdziwa wtedy i tylko wtedy, gdy przynajmniej jeden z jej członów jest
prawdziwy  ponieważ T jest zawsze prawdziwe, więc S mogłoby być nawet kontrtautologią a Ą#S (" Tń# i tak
będzie tautologią. Czy to jednak znaczy, że S jest kontrtautologią? Nie. S mogłoby być tautologią, i
wówczas Ą#S (" Tń# również byłoby tautologią. A gdyby S było schematem niezdeterminowanym, to Ą#S (" Tń#
tak czy owak będzie tautologią. Ą#S (" Tń# będzie tautologią niezależnie od typu schematu S.
Ą#
Dowolny Tautologia S
S (" Tń#
M M M
1  1
1  1
1  1
M M M
(f) S jest tautologią
(g) S jest kontrtautologią
Dane: Rozwiązanie:
Ą# Ą# Ą#
Dowolny schemat X S Dowolny schemat X S
~(S '" X)ń# ~(S '" X)ń# (S '" X)ń#
?
M M M M M M
 ? 1  0 1 0
 ? 1  0 1 0
 ? 1  0 1 0
?
M M M M M M
(h2 ) Pytanie (h) jest z
le postawione. Powinno być:  Negacja alternatywy S i dowolnego schematu jest
kontrtautologią
Dane: Rozwiązanie:
Ą# Ą# Ą#
Dowolny schemat X S Dowolny schemat X S
~(S (" X)ń# ~(S (" X)ń# (S (" X)ń#
?
M M M M M M
 ? 0  1 0 1
 ? 0  1 0 1
 ? 0  1 0 1
?
M M M M M M
dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 8 z 9
(i) Nie można ustalić
Dane: Rozwiązanie:
Ą# Ą# Ą#
Dowolna tautologia T S Dowolna tautologia T S
~(S (" T)ń# ~(S (" T)ń# (S (" T)ń#
?
M M M M M M
1 ? 0 1  0 1
1 ? 0 1  0 1
1 ? 0 1  0 1
?
M M M M M M
(j) S jest kontrtautologią
Dane: Rozwiązanie:
Ą# Ą# Ą#
Dowolna kontrtautologia K S Dowolna kontrtautologia K S
~(S (" K)ń# ~(S (" K)ń# (S (" K)ń#
?
M M M M M M
0 ? 1 0 0 1 0
0 ? 1 0 0 1 0
0 ? 1 0 0 1 0
?
M M M M M M
(k) S jest kontrtautologią
Dane: Rozwiązanie:
Ą# Ą#
Dowolny schemat X S Dowolny schemat X S
S Xń# S Xń#
?
M M M M M
 ? 1  0 1
 ? 1  0 1
 ? 1  0 1
?
M M M M M
(l) S jest tautologią
Dane: Rozwiązanie:
Ą# Ą#
Dowolny schemat X S Dowolny schemat X S
X Sń# X Sń#
?
M M M M M
 ? 1  1 1
 ? 1  1 1
 ? 1  1 1
?
M M M M M
(ł) nie można ustalić
Dane: Rozwiązanie:
Ą# Ą#
Dowolna tautologia T S Dowolna tautologia T S
S Tń# S Tń#
?
M M M M M
1 ? 1 1  1
1 ? 1 1  1
1 ? 1 1  1
?
M M M M M
dr Katarzyna Paprzycka, Logika  Zadanie domowe z wykładu IV Strona 9 z 9
(m) nie można ustalić
Dane: Rozwiązanie:
Ą# Ą#
Dowolna kontrtautologia K S Dowolna kontrtautologia K S
K Sń# K Sń#
?
M M M M M
0 ? 1 0  1
0 ? 1 0  1
0 ? 1 0  1
?
M M M M M
(n) S jest kontrtautologią
Dane: Rozwiązanie:
Ą# Ą#
Dowolna tautologia T S Dowolna tautologia T S
T a" Sń# T a" Sń#
?
M M M M M
1 ? 0 1 0 0
1 ? 0 1 0 0
1 ? 0 1 0 0
?
M M M M M
(o) S jest tautologią
Dane: Rozwiązanie:
Ą# Ą# Ą#
Dowolny schemat X Dowolna tautologia T S S
(S (" X) a" Tń# (S (" X) a" Tń# (S (" X)ń#
?
M M M M M M
 1 ? 1 1 1 1
 1 ? 1 1 1 1
 1 ? 1 1 1 1
?
M M M M M M