Wrocław, 25 listopada 2015
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania  lista 8
1. Niech a�, b� będą formułami rachunku zdań. Które z poniższych stwierdzeń są prawdziwe.
Jeżeli INTv(a� �� b�) = prawda, to:
a) INTv(a�) = prawda lub INTv(b�) = prawda
b) INTv(a�) = prawda oraz INTv(b�) = prawda
c) istnieje takie v różniące się od v wartościowaniem zmiennej x, że
INTv (a�) = prawda oraz INTv (a�) = prawda
d) dla każdego v różniącego się od v wartościowaniem zmiennej y, zachodzi
INTv (a�) = prawda oraz INTv (a�) = prawda
2. Niech a�, b� będą formułami rachunku zdań. Które z poniższych stwierdzeń są prawdziwe.
Jeżeli INTv(a� Ł� b�) = prawda to:
a) INTv(a�) = prawda oraz INTv(b�) = prawda
b) INTv(a�) = prawda lub INTv(b�) = prawda
c) istnieje takie v różniące się od v wartościowaniem zmiennej x, że
INTv (a�) = prawda oraz INTv (a�) = prawda
d) dla każdego v różniącego się od v wartościowaniem zmiennej y, zachodzi
INTv (a�) = prawda oraz INTv(a�) = prawda
3. Dane są formuły:
a) p �� (q �� p)
b) (p Ł� q) �� (��p �� ��q)
c) (p �� q) �� (��p Ł� ��q)
d) p �� (q Ł� r) �� (p Ł� q) �� (p Ł� r)
e) p Ł� (q �� r) �� (p Ł� q) �� (p Ł� r)
Które z tych formuł te są spełnialne, a które są tautologiami? Dla formuł które są
tautologiami wykazać to stosując najpierw metodę zerojedynkową, a następnie metodę
transformacyjną.
4. Dla formuł podanych poniżej wyznaczyć semantycznie równoważne formuły zapisane w
koniunkcyjnej postaci normalnej.
a) ((a �� b) �� c) �� (b Ł� c)
b) ��(a Ł� b) �� (b �� ��c)
c) (a �� b) �� (b �� a)