egzpopr2001.pdf

Egzamin z logiki, 06/09/2001

1. Niech bedzie sygnatur a składaj ac a sie z jednego jednoargumentowego

symbolu funkcyjnego f: Udowodnic, ze kazda algebra A sygnatury o

wiecej niz jednym elemencie ma nietrywialny (tzn. rózny od identycznosci)

homomorﬁzm h : A!A .

2. Niech zbiór X bedzie spektrum zdania ' sygnatury , tzn., niech X = fn 2

N = istnieje struktura A nad t.ze jAj = n i Aj= 'g:

Udowodnic, ze zbiór fm+n=m;n 2 Xg tez jest spektrum pewnego zdania

(w konstrukcji wolno powiekszyc sygnature o nowe symbole).

3. a) Skonstruowac algebre A i klase algebr

nad

dwoma róznymi niepustymi zbiorami wolnych generatorów G 1 ;G 2 takimi,

ze G 1 \G 2 = ;:

b) Skonstruowac algebre A i klase algebr

takie, ze A jest wolna w

nad

dokładnie jednym niepustym zbiorem wolnych generatorów.

4. Niech

bedzie klas a wszystkich grafów, sko nczonych i niesko nczonych,

które s a n -dzielne, dla pewnego n 2 N: Graf G jest n -dzielny jesli ist-

nieje podział jego zbioru wierzchołków G na niepuste i rozł aczne podzbiory

G 1 ;:::;G n tak, ze kazda z podstruktur indukowanych G jG i nie zawiera

zadnych krawedzi. Przykładowo, graf pełny o n wierzchołkach K n jest n -

dzielny, ale nie m -dzielny dla m < n:

Udowodnic, ze klasa

nie jest deﬁniowalna.

5. Niech W = hf0; 1g + ; W ; 0 W ; 1 W ;r W i bedzie struktur a, w której f0; 1g + to

zbiór wszystkich niepustych sko nczonych ci agów zerojedynkowych, W to

operacja konkatenacji ci agów ( hx 1 :::x n i W hy 1 :::y m i = hx 1 :::x n y 1 :::y m i;

0 W i 1 W to ci agi jednoelementowe h0i i h1i , zas r W jest relacj a jednoar-

gumentow a okreslon a przez r W (w) wtw. gdy kazdy preﬁks w zawiera nie

wiecej jedynek niz zer, a w całym ci agu w ilosc jednek i zer jest jednakowa.

Udowodnic, ze

Wj= 8x([9y 1 9y 2 9y 3 x = (y 1 y 2 ) y 3 ] !

[r(x) !9((y9z (r(y) ^r(z) ^x = yz)) _x = (0 y)) 1)]:

6. Niech N bedzie standardowym modelem arytmetyki, nad standardow a syg-

natur a, składaj ac a sie z symboli +;; 0; 1; :

Napisac formułe '(x) nad sygnatur a arytmetyki deﬁniuj ac a relacje „ x ma

nieparzyst a ilosc cyfr w rozwinieciu dziesietnym”, tzn. tak a, ze dla wszyst-

kich wartosciowa n v : X ! ! zachodzi równowaznosc Nj= '[v] wtw v(x)

ma nieparzyst a ilosc cyfr w rozwinieciu dziesietnym.

7. Niech Z 8 = hf0; 1;:::; 7g;S Z 8 ; 0 Z 8 i; gdzie S Z 8

jest operacj a nastepnika

modulo 8; zas 0 Z 8 to 0:

Prosze opisac wszystkie kongruencje algebry Z 8 :

8. Niech sygnatura algebraiczna składa sie z symboli stałych a;b;c i nie

zawiera innych symboli. Niech A i B bed a dwuelementowymi algebrami

sygnatury takimi, ze a A = b A 6= c A ; zas a B 6= b B = c B : Udowodnic,

ze kazda rozmaitosc algebr nad zawieraj aca jednoczesnie A i B zawiera

wszystkie algebry nad :

9. Niech c;d bed a dwoma symbolami pewnej sygnatury algebraicznej ; która

poza tym moze zawierac takze inne symbole funkcyjne, o róznych ilosciach

argumentów. Zbiór E równosci nad nazwiemy symetrycznym , gdy kazda

równosc t = s nalezy do E wtedy i tylo wtedy, gdy równosc otrzymana z

t = s przez (jednoczesn a) zamiane wyst apie n c na d oraz d na c; tez nalezy

do E:

Udowodnic, ze jesli zbiór równosci E nad jest symetryczny, to zbiór

ft = s = E j= t = sg tez jest symetryczny.

10. Rozstrzygn ac, czy f' 1 ;' 2 ;' 3 gj= f 1 ; 2 g:

' 1 : 8x 1 8x 2 E(x 1 ;x 2 ) ! E(x 2 ;x 1 )

' 2 : 8x:E(x;x)

' 3 : 9x 1 9x 2 9x 3 9x 4 9x 5

x i 6= x j

1i<j5

1 : 9x 1 9x 2 9x 3 E(x 1 ;x 2 ) ^E(x 2 ;x 3 ) ^E(x 3 ;x 1 )

2 : 9x 1 9x 2 9x 3 :(E(x 1 ;x 2 ) _E(x 2 ;x 3 ) _E(x 3 ;x 1 ))

Czas na rozwi azanie zada n to 3 godziny od chwili ich rozdania. Wolno uzywac

dowolnych notatek i podreczników, natomiast nie wolno sci agac.

Wszystkie zadania s a oceniane w skali 0-1-2-3 punkty, przy czym wazne jest

uzasadnienie odpowiedzi . Na pi atke trzeba 10 punktów (w tym 4 zadania na co

najmniej 2 punkty), na czwórke 8 punktów (w tym co najmniej 3 zadania na co naj-

mniej 2 punkty), a na trójke 5 punktów (w tym co najmniej 2 zadania na co najmniej

2 punkty lub jedno zadanie na 3 punkty). Kazdej osobie, która odda wiecej niz

cztery zadania, do wyniku zostan a policzone najsłabsze cztery sposród nich,

tak wiec nie opłaca sie oddawac wiecej niz czterech zada n.

Kazde zadanie prosze napisac na osobnej kartce, podpisanej imieniem, nazwiskiem

i numerem indeksu.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: