logika egz02 (1)

Wrocław 03-02-2003

EGZAMIN Z LOGIKI DLA INFORMATYKÓW

Uwaga:    Dla zwiększenia czytelności formuł rachunku zdań i rachunku

kwantyfikatorów w miejscach, w których nie prowadzi to do

niejednoznaczności, pominięto nawiasy!

Zad. 1. Wskaż prawdziwe stwierdzenia.

A)    Dane są płaszczyzna P. zbiór X okręgów na płaszczyźnie P oraz relacja R określona następująco: Dla każdej pary okręgów o, i o₂ ze zbioru X relacja o₁ R o₂ zachodzi wtedy i tylko wtedy, gdy o, i o₂ nie mają żadnego punktu wspólnego. Nie jest prawdą, że relacja R jest relacją równoważności.

B)    Dla relacji R zdefiniowanej w punkcie (A) nie jest prawdą, że relacja R jest zwrotna.

C)    Dane są płaszczyzna P. punkt A leżący na płaszczyźnie P oraz relacja S określona następująco: Dla każdej pary punktów s₁ i s₂ na płaszczyźnie P relacja s_f S s₂ zachodzi wtedy i tylko wtedy, gdy odległość punktu s, od punktu A jest nie mniejsza niż odległość punktu s₂ od punktu A. Nie jest prawdą, że relacja S jest relacją przechodnią.

D)    Dla relacji S zdefiniowanej w punkcie (C) nie jest prawdą, że relacja S wyznacza co najmniej jedną klasę abstrakcji.

Zad. 2. Dana jest teoria T oparta na języku rachunku zdań, zawierająca aksjomaty A₁, A£, reguły

zastępowania definicyjnego D-), D2 oraz reguły wnioskowania R-|, R2:

^A1^:	(Y=>(X=>(-,true)))	A2:	((-,X)o(X=>(-.false)))
Dr	false^(-itrue)	D2:	true=(-ifalse)
^Rr	(A => B) B	R2:	(AoB) B

Jest prawdą że:

A)    Teoria T jest sprzeczna

B)    Teoria T jest skończona

C)    Formuła true jest twierdzeniem teorii T

D)    Formuła false jest twierdzeniem teorii T

Zad. 3. Niech A, B, C będą dowolnymi zbiorami. Jest prawdą że:

A)    Jeśli card(A)=card(B) =n to card(AuB) = 2n

B)    (A\B) u C = C wtedy i tylko wtedy, gdy A=B

C)    2^A n 2^B - 2^{a, b}

D)    (A\B) n (B\A) = 0

Zad. 4. Niech A(z) oznacza formułę rachunku kwantyfikatorów, w której zmienna z ma wolne wystąpienie, wówczas formuła rachunku kwantyfikatorów F = Vx.(X(x)vY(x)) jest równoważna semantycznie formule:

A)    (-.3x.(X(x)aY(x)))

B)    (-,3x.(-.X(x)a-,Y(x)))

C)    (Vx.X(x))v(Vx.Y(x))

D)    ( -,Vx.(iX(x)a-.Y(x)))

Zad. 5. Dany jest zbiór klauzul S = {pv( -,r )v( -,t), tv( -,p )v( -,r), tv( -,q ), ( -,p )v( -^q )v( -.r), q, r}. Na podstawie tego zbioru można obliczyć następującą rezolwentę:

A)    pv( -,t)

B)    tv( -,p )

C)    ( ->q )v( ^r)

D)    pusta klauzula