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
,
f
2
zdefiniowane przedstawioną poniżej tabelą, w której symbolami 0 oraz 1 oznaczono od-
powiednio fałsz oraz prawdę.
a b f
1
(a,b) f
2
(a,b
0 0
1
1
0 1
0
0
1 0
1
1
1 1
0
1
7. Dana jest gramatyka G =
df
<
, N, P, S>, gdzie:
=
df
{0, 1, @, #, +, *, (, )}
N =
df
{wyr, op_unarny, op_binarny}
P =
df
{ wyr ::= 0 | 1| (wyr op_binarny wyr) | op_unarny wyr
op_binarny ::= + | *
op_unarny ::= @ | #}
S =
df
wyr
a) Podać przykład wyprowadzenia dowolnego słowa generowanego przez gramatykę G o
długości większej od 2.
b) Stosując zasadę rekursji strukturalnej zdefiniować funkcję left(
), która dla dowolnego
napisu
L(G) określa liczbę lewostronnych nawiasów występujących w napisie
.
8. Przedstawić algorytm, który dla danej formuły rachunku zdań wyznacza spójnik główny, to
znaczy taki, który całą formułę dekomponuje na formuły składowe (jedną, gdy spójnikiem
głównym jest negacja, oraz dwie, gdy spójnikiem głównym jest spójnik binarny).
Wyszukiwarka
Podobne podstrony:
Lista 2012 2
Lista 2012 9
Lista 2012 6
Lista 2012 4
Lista 2012 1
Lista 2012 5
Lista 2012 3
Lista 2012 11
Lista 2012 2
rachunek kosztlw dla inynierlw wiczenia lista 2 2012
więcej podobnych podstron