Wrocław, 1 grudnia 2015
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania  lista 9
1. Dane są funkcje logiczne wyrażone poniższymi tabelkami (0 oznacza wartość fałsz, 1 
prawda). Wyrazić te funkcje w postaci formuł zawierających tylko spójniki negacji,
koniunkcji i alternatywy.
a b c f(a, b, c) g(a, b, c)
0 0 0 0 1
1 0 0 1 1
0 1 0 1 0
1 1 0 1 0
0 0 1 0 0
1 0 1 0 0
0 1 1 0 1
1 1 1 1 1
2. Które zbiory spójników logicznych są zbiorami funkcjonalnie pełnymi:
a) {��, Ł�}
b) {��, ��}
c) {��, ��}
d) {false, ��}
e) {��, ��}
f) {true, ��}
g) {��, false}
3. Pokazać, że spójnik NAND(a, b) =def ��(a Ł� b) oraz spójnik NOR(a, b) =def ��(a �� b) są
spójnikami funkcjonalnie pełnymi.
4. Następujące formuły oraz ich negacje sprowadzić do koniunkcyjnej postaci normalnej:
a) ((a �� b) �� c) �� (b Ł� c)
b) ��(a Ł� b) �� (b �� ��c)
c) (a �� b) �� (b �� a)
5. Zdefiniować funkcje, które dla dowolnej formuły rachunku zdań wyznaczają:
a) liczbę wystąpień danej zmiennej w formule,
b) liczbę wystąpień danego spójnika logicznego w formule,
c) liczbę różnych zmiennych występujących w formule,
d) zbiór zmiennych występujących w formule,
e) zbiór spójników występujących w formule.
6. Udowodnić, że dla dowolnej formuły rachunku zdań zachodzą własności:
a) liczba nawiasów otwierających jest równa liczbie dwuargumentowych spójników
zdaniowych,
b) liczba nawiasów występujących w formule jest liczbą parzystą.