Wrocław, 6 grudnia 2012
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania  lista 9
1. Które zbiory spójników logicznych są zbiorami funkcjonalnie pełnymi:
a) {��, Ł�}
b) {��, ��}
c) {��, ��}
d) {false, ��}
e) {��, ��}
f) {true, ��}
g) {��, false}
2. Stosując metodę sekwentów Gentzena sprawdzić, które formuły są tautologiami:
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)
3. 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)
4. 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.
5. 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ą.