Wrocław, 28 listopada 2012
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania  lista 8
1. 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. 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. Stosując metodę zerojedynkową wykazać, że następujące formuły są tautologiami:
a) p �� (q �� p)
b) (pŁ� q) �� (��p �� ��q)
c) (p �� q) �� (��p Ł� ��q)
4. Sprawdz
(w dowolny sposób), czy są tautologiami następujące formuły:
a) p �� (q Ł� r) �� (p Ł� q) �� (p Ł� r)
b) p Ł� (q �� r) �� (p Ł� q) �� (p Ł� r)
5. Niech a� oraz b� będą tautologiami rachunku zdań. Które z następujących formuł są tautolo-
giami rachunku zdań:
a) a� �� a�
b) a� �� b�
c) a� �� ��b�
d) ��a� �� b�
6. Dane są dwa dwuargumentowe funktory logiczne NAND oraz NOR zdefiniowane następu-
jąco:
NAND(a, b) = ��(a Ł� b)
oraz
NOR(a, b) = ��(a �� b).
Pokazać, w jaki sposób, za pomocą tych funktorów, można wyrazić spójniki logiczne negacji,
koniunkcji i alternatywy. Narysować sieci logiczne realizujące funkcje prawdziwościowe f1,
f2 zdefiniowane przedstawioną poniżej tabelą, w której symbolami 0 oraz 1 oznaczono od-
powiednio fałsz oraz prawdę.
a b f1(a,b) f2(a,b
0 0 1 1
0 1 0 0
1 0 1 1
1 1 0 1
7. Dana jest gramatyka G =df , gdzie:
S� =df {0, 1, @, #, +, *, (, )}
N =df {wyr, op_unarny, op_binarny}
P =df { wyr ::= 0 | 1| (wyr op_binarny wyr) | op_unarny wyr
op_binarny ::= + | *
op_unarny ::= @ | #}
S =df wyr
a) Podać przykład wyprowadzenia dowolnego słowa generowanego przez gramatykę G o
długości większej od 2.
b) Stosując zasadę rekursji strukturalnej zdefiniować funkcję left(a�), która dla dowolnego
napisu a���L(G) określa liczbę lewostronnych nawiasów występujących w napisie a�.
8. Przedstawić algorytm, który dla danej formuły rachunku zdań wyznacza spójnik główny, to
znaczy taki, który całą formułę dekomponuje na formuły składowe (jedną, gdy spójnikiem
głównym jest negacja, oraz dwie, gdy spójnikiem głównym jest spójnik binarny).