Wrocław, 21 listopada 2012
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania  zestaw 7
1. Wskazać ciągi znaków, które są słowami języka rachunku zdań:
a) ((p �� q))
b) p �� q
c) q �� p �� (��(q, p))
2. Daną formułę rachunku zdań przedstawić w pełnej postaci z nawiasami, a
następnie określić zbiór wszystkich jej podformuł:
a) a Ł� b Ł� c �� d �� e �� ��f �� g �� h
b) a Ł� (b Ł� c �� d ) �� e �� (��f �� g) �� h
3. Przedstwić gramtykę G, która generuje język formalny rachunku zdań, czyli
L(G) = FORMRZ.
4. Podać algorytm, który dowolną formułę rachunku zdań zapisaną w postaci
wrostkowej transformuje na formułę zapisaną w postaci przedrostkowej.
5. Funktorem zdaniowym n-argumentowym nazywamy dowolną funkcję f o
sygnaturze:
f : {prawda, fałsz}n �� {prawda, fałsz}.
Jaka jest liczba takich funktorów n-argumentowych? Zdefiniować wszystkie
funktory jedno- i dwuargumentowe.
6. Która ze zdefiniowanych niżej relacji jest relacją równoważności na zbiorze formuł
rachunku zdań:
a) a� ~1 b� wtedy i tylko wtedy, gdy formuła a� �� b� jest spełniona,
b) a� ~2 b� wtedy i tylko wtedy, gdy formuła a� �� b� jest sprzeczna,
c) a� ~3 b� wtedy i tylko wtedy, gdy formuła a� �� b� jest spełniona dokładnie dla
połowy wartościowań zmiennych.
7. Niech g� będzie dowolnie ustaloną formułą rachunku zdań. Wykazać, że relacja zdefi-
niowana następująco:
a� ~ b� wtedy i tylko wtedy, gdy formuła g� �� (a� �� b� ) jest tautologią,
jest relacją równoważności na zbiorze formuł rachunku zdań.