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 INT
v
(
) = prawda, to:
a) INT
v
(
) = prawda lub INT
v
(
) = prawda
b) INT
v
(
)=prawda oraz INT
v
(
) = prawda
c) istnieje takie v’ różniące się od v wartościowaniem zmiennej x, że
INT
v’
(
) = prawda oraz INT
v’
(
) = prawda
d) dla każdego v’ różniącego się od v wartościowaniem zmiennej y, zachodzi
INT
v’
(
) = prawda oraz INT
v’
(
) = prawda
2. Które z poniższych stwierdzeń są prawdziwe. Jeżeli INT
v
(
) = prawda to:
a) INT
v
(
) = prawda oraz INT
v
(
) = prawda
b) INT
v
(
) = prawda lub INT
v
(
) = prawda
c) istnieje takie v’ różniące się od v wartościowaniem zmiennej x, że
INT
v’
(
) = prawda oraz INT
v’
(
) = prawda
d) dla każdego v’ różniącego się od v wartościowaniem zmiennej y, zachodzi
INT
v’
(
) = prawda oraz INT
v
(
) = 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. Sprawdź (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
oraz
będą tautologiami rachunku zdań. Które z następujących formuł są tautolo-
giami rachunku zdań:
a)
b)
c)
d)
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 f
1
,
