Egzamin z logiki, 9 czerwca 2005

1. Skonstruowa´

c w rachunku sekwent´

ow dowody formu l

(a) (¬p → ¬q) → ((¬p → q) → p);

(b) ¬(p → q) ∧ ¬(q → r) → (p → r).

2. Kt´

ora z nast

,

epuj

,

acych implikacji jest tautologi

,

a:

(a) [∀x∃yR(x, y) → ∃x∀yR(y, x)] → ∃x∀y(R(x, y) → R(y, x))?

(b) ∃x∀y(R(x, y) → R(y, x)) → [∀x∃yR(x, y) → ∃x∀yR(y, x)]?

3. Poda´

c definicje nast

,

epuj

,

acych poj

,

e´

c:

(a) Warto´s´

c formu ly ϕ w strukturze A przy warto´sciowaniu ρ.

(b) Algebra wolna w klasie K o zbiorze wolnych generator´

ow X.

4. Symbol funkcyjny f jest dwuargumentowy.

Termy t

n

, dla n > 0,

s

,

a zdefiniowane tak: t

1

= f (x

1

, x

0

), t

n+1

= f (x

n+1

, t

n

). Oczywi´scie

F V (t

n

) = {x

0

, . . . , x

n

}. Przez Γ

m

oznaczymy zbi´

or wszystkich r´

owna´

n

postaci

”

t

n

= x

0

” dla n ≥ m. M´

owimy, ˙ze algebra A sygnatury Σ jest

fajna, je´sli A |= t

n

= x

0

dla pewnego n > 0. Natomiast algebra A jest

lepsza, gdy A |= Γ

m

dla pewnego m > 0.

(a) Kt´

ore z r´

owno´sci f (x, y) = f (z, y), f (x, y) = f (z, u), f (x, y) = y

s

,

a prawdziwe w ka˙zdej fajnej algebrze? A kt´

ore w ka˙zdej lepszej?

(b) Czy klasa algebr fajnych jest definiowalna r´

owno´sciowo? A klasa

algebr lepszych?

Rozwi

,

azania

Zadanie 1a:

p ` p

` ¬p, p

¬p → ¬q ` ¬p, p

p ` p

` ¬p, p

q ` ¬p, p

q ` q

q, ¬q `

q, ¬q ` p

¬p → ¬q, q ` p

¬p → ¬q, ¬p → q ` p

¬p → ¬q ` (¬p → q) → p

` (¬p → ¬q) → ((¬p → q) → p)

Zadanie 1b:

q ` q

q ` p → r, q

q ` q, p → r

q ` r, q, p → r

` q → r, q, p → r

p ` q → r, q, p → r

p ` q, q → r, p → r

` p → q, q → r, p → r

¬(p → q) ` q → r, p → r

¬(p → q), ¬(q → r) ` p → r

¬(p → q), ¬(p → q) ∧ ¬(q → r) ` p → r

¬(p → q) ∧ ¬(q → r), ¬(p → q) ` p → r

¬(p → q) ∧ ¬(q → r), ¬(p → q) ∧ ¬(q → r) ` p → r

¬(p → q) ∧ ¬(q → r) ` p → r

¬(p → q) ∧ ¬(q → r) → (p → r)

2

Zadanie 2a: Lewa strona implikacji jest r´

ownowa˙zna formu lom:

• ¬∀x∃yR(x, y) ∨ ∃x∀yR(y, x);

• ∃x∀y¬R(x, y) ∨ ∃x∀yR(y, x);

• ∃x(∀y¬R(x, y) ∨ ∀yR(y, x));

• ∃x(∀y¬R(x, y) ∨ ∀zR(z, x));

• ∃x∀y(¬R(x, y) ∨ ∀zR(z, x));

• ∃x∀y∀z(¬R(x, y) ∨ R(z, x)).

Prawa strona jest r´

ownowa˙zna formule ∃x∀y(¬R(x, y) ∨ R(y, x)). Pozostaje

wi

,

ec zauwa˙zy´

c, ˙ze:

• Ka˙zda formu la postaci ∀y∀z ϕ(y, z) → ∀y ϕ(y, y) jest tautologi

,

a;

• Je´sli ϕ → ψ jest tautologi

,

a, to tak˙ze ∃x ϕ → ∃x ψ jest tautologi

,

a.

Zadanie 2b: Rozwi

,

azanie zadania u latwi przekszta lcenie formu ly do r´

owno-

wa˙znej postaci ∃x∀y(¬R(x, y) ∨ R(y, x)) → ∃x∀y¬R(x, y) ∨ ∃x∀yR(y, x).
Teraz latwo sprawdzi´

c, ˙ze ta formu la nie jest prawdziwa w modelu hR, =i.

Mamy bowiem na przyk lad R, {0/x} |= ∀y(¬R(x, y)∨R(y, x)), bo dla dowol-
nej liczby y albo 0 6= y albo y = 0. A wi

,

ec R |= ∃x∀y(¬R(x, y) ∨ R(y, x)).

Ale nie ma ani liczby r´

ownej wszystkim, ani liczby r´

o˙znej od wszystkich liczb

rzeczywistych, wi

,

ec R 6|= ∃x∀y¬R(x, y) ∨ ∃x∀yR(y, x).

Zadanie 3: Patrz materia ly do wyk ladu.

Zadanie 4a: Warto´s´

c termu t

n

przy warto´sciowaniu {a

n

/x

n

, . . . , a

0

/x

0

} b

,

e-

dziemy dla uproszczenia zapisywa´

c po prostu jako t

n

(a

n

, . . . , a

0

).

Poka˙zemy najpierw, ˙ze w algebrach fajnych prawdziwe jest r´

ownanie f (x, y) =

f (z, y), tj. ˙ze operacja f zale˙zy tylko od drugiego argumentu. Za l´

o˙zmy, ˙ze

w algebrze A prawdziwe jest r´

ownanie t

n

= x

0

. Wtedy a

0

= t

n

(a

n

, . . . , a

0

) =

t

n−1

(a

n

, . . . , f (a

1

, a

0

)) = f (a

n

, t

n−1

(a

n−1

, . . . , a

0

)), dla dowolnych a

0

, . . . , a

n

.

3

Zatem f (a

0
1

, a

0

) = f (a

0
1

, t

n

(a

n

, . . . , a

1

, a

0

)) = t

n

(a

0
1

, a

n

, . . . , a

2

, f (a

1

, a

0

)) =

f (a

1

, a

0

), dla dowolnych a

1

, a

0
1

.

Pozosta le dwa r´

ownania nie s

,

a prawdziwe na przyk lad w algebrze o elemen-

tach 0, 1 i 2, w kt´

orej f (a, b) = (b + 1) mod 3.

Natomiast w algebrach lepszych prawdziwe jest r´

ownanie f (x, y) = y, bo dla

dostatecznie du˙zego n mamy a

0

= t

n+1

(a

n

, . . . , a

0

) = t

n

(a

n

, . . . , f (a

1

, a

0

)) =

f (a

1

, a

0

). Oznacza to, ˙ze algebry lepsze to dok ladnie te algebry, w kt´

orych

f jest rzutowaniem na drug

,

a wsp´

o lrz

,

edn

,

a. (Rzutowanie spe lnia definicj

,

e

dla m = 1.) Ale rzutowanie na og´

o l nie jest funkcj

,

a sta l

,

a, wi

,

ec r´

ownanie

f (x, y) = f (z, u) nie jest prawdziwe w algebrach lepszych.

Zadanie 4b: Z powy˙zszego wynika, ˙ze klasa algebr lepszych jest definiowalna
r´

ownaniem f (x, y) = y. Natomiast klasa algebr fajnych nie jest definiowalna

r´

owno´sciowo, bo nie jest zamkni

,

eta ze wzgl

,

edu na produkty. Rozpatrzmy

algebry A

n

= hA

n

, f

n

i, gdzie A

n

= {0, . . . , n} oraz f

n

(a, b) = (b + 1) mod n.

Wtedy produkt Π

n∈N

A

n

nie jest fajny.

4