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ą.