ZAD. 1.
Które ze zdefiniowanych relacji są relacjami równoważności
A)
❶X-zbiór osób zdających egzamin, o
1
,o
2
∈X;
o
1
R o
2
⇔o
1
jest tej samej płci co o
2
B)
⓪X-zbiór samochodów na parkingu s
1
,s
2
∈X;
s
1
R s
2
⇔s
1
różnica cen samochodów s
1
i s
2
jest mniejsza od K(pewna stała kwota)
C)
⓪X-zbiór krzeseł w sali, k
1
,k
2
∈X;
k
1
R k
2
⇔ k
2
znajduje się w odległości większej, niż r (pewna stała odległość) od k
1
D)
⓪X-zbiór funkcji zmiennej x, f
1
,f
2
∈X;
f
1
R f
2
⇔ ∃x●(f
1
(x)=f
2
(x))
ZAD. 2.
Niech R
1
,R
2
będą relacjami równoważności na zbiorze X. Wówczas relacjami równoważności są również relacje:
A)
⓪R
1
∪R
2
B)
⓪R
1
\R
2
C)
⓪R
1\
Y
2
, gdzie Y⊂X
D)
❶ (X
2
\R
1
) ∩R
2
ZAD. 3.
Niech A, B, C będą dowolnymi zbiorami. Prawdą jest, że:
A)
⓪card(A)=card(B)⇒A\B=∅
B)
⓪(A\B) ∪C=C⇔A=B
C)
❶2
A
∩2
B
=2
A∩B
D)
⓪(A\B)∪(B\A)=∅
ZAD. 4.
Dana jest funkcja f: X→Y całkowicie określona na X. Niech R⊆X² będzie relacją binarną na X określoną następująco: <x,y>∈R
wtedy i tylko wtedy, gdy f(x)=f(y). Wskaż, które z własności posiada relacja R:
A)
❶R jest relacją zwrotną
B)
⓪R jest relacją antysymetryczną
C)
❶R jest relacją spójną
ZAD. 5.
Dana jest gramatyka G=
df
<.,+,-,0,1,2,3,4,5},{S,R
1
,R
2
,X},P,S>,gdzie zbiór produkcji P jest zdefiniowany następująco:
P=
df
{S::=R
1
|R
2
|R
1
.R
2
R1::=XR
1
|X R
2
::=+R
1
|-R
1
X::=0|1|…|5}
Które z poniższych słów należy do języka L(G):
A)
⓪+012.
B)
⓪12.1.1
C)
⓪-0.000
D)
⓪000.123
ZAD. 6.
Niech formuły α i β będą tautologiami rachunku kwantyfikatorów. Które z poniższych formuł są również tautologiami rachunku
kwantyfikatorów:
A)
⓪¬α ∧¬ β
B)
❶¬α ∨ β
C)
❶α ⇔ β
D)
❶α ⇒ β
ZAD. 7.
Niech p,q,r będą zmiennymi zdaniowymi. Wskazać wyrażenia, które są tautologiami:
A)
❶ (p∨(q∧r)) ⇔ ((p∨q) ∧(p∨r))
B)
⓪(p⇒q) ⇔ (p∨¬q)
C)
⓪(((p∧q) ⇒r) ∧ ((p∧ q) ⇒¬r)) ⇒ (¬p∧ ¬q∧ ¬r)
ZAD. 8.
Jeżeli INT
v
(α⇒β)=F to zawsze zachodzi:
A)
❶INT
v
(α)=P oraz INT
v
(β)=F
B)
⓪INT
v
(α)=F lub INT
v
(β)=P
C)
⓪INT
v
(¬α∨β)=P
D)
⓪INT
v
(α ∨¬β)=F
ZAD. 9.
Wyrażenie p⇒q jest semantycznie równoważne wyrażeniu:
A)
⓪¬ (p∧q)
B)
❶¬ (p∧¬ q)
C)
❶ (p⇔q) ∨¬(q⇒p)
D)
⓪¬(p⇔p) ∧(q⇒p)
ZAD. 10. Zakładając, że x,y,z są zmiennymi indywiduowymi, p, q, r – symbolami predykatów, wskaż napisy, które są poprawnnie
zbudowanymi farmułami rachunku kwantyfikatorów:
A)
∀x∀y● p(x, z) ⇔x∈ {y:y≥z}
B)
∀x●¬(x⇔x)) ⇒ ∃y●¬(y⇔y))
C)
∀x∃y ●p(x) ⇒(∃z●q(x,y,z) ∧(¬r(y) ⇔r(y)))
D)
∀x(∃x●(p(x))∧(q(x)))
ZAD. 11. Zakładając, że P, Q są predykatami, x, y – zmiennymi indywiduowymi wskaż, które z poniższych formuł rachunku
kwantyfikatorów są tautologiami:
A)
(∀x●∀y●P(x,y))⇒∃x●∀y ●P(x,y)
B)
(¬∀x ●∀y ● P(x,y)∨ ∃x●∀y ●P(x,y)) ⇔(∀x●∀y●P(x,y) ∧∀x●∃x●¬P(x,y))
C)
(∀x●P(x)⇔Q(x))⇒(∀x●P(x)⇔∀x●Q(x))
ZAD. 12. Dana jest formuła ∃x●(P(x,y)∧Q(x,y)), system relacyjny SR=<A
SR
,R
1
,R
2
> oraz interpretacja danej formuły w systemie relacyjnym
SR oznaczona I. Jeżeli nośnik systemu relacyjnego A
SR
={a,b} i relacje: R
1
={<a,b>,<b,a>}, R
2
={<a,a>,<b,b>,<a,b>}, to:
A)
Dla I(P)=R
1
i I(Q)=R
2
oraz dla wartościowania v(x)=a i v(y)=a formuła jest spełniona
B)
Dla I(P)=R
1
i I(Q)=R
1
oraz dla wartościowania v(x)=a i v(y)=a formuła jest spełniona
C)
Dla I(P)=R
2
i I(Q)=R
1
oraz dla wartościowania v(x)=a i v(y)=a formuła nie jest spełniona
ZAD. 13. Poniższe drzewo ilustruje zostosowanie rachunku sekwencji dla sprawdzenia, czy formuła ¬ (α⇔ β) jest tautologią.
1)
→¬ (α⇒β), ¬ (β ⇒ α)
2)
α⇒β→ ¬ (β ⇒ α)
