Zadania ponizsze nalezy rozumiec nastepujaco: sa one ilustracja do tego, co
jest na wykladzie, a czesciowo przypomnieniem roznych rzeczy z logiki. Nie
zalezy mi na otrzymaniu napisanych rozwiazan, ale na tym, by ci, ktorzy nie
chodza na cwiczenia, zapoznali sie z rozwiazaniami tych zadan.

J.Ty.

1. Zapisac nastepujace zdanie Lincolna o wyborcach i politykach:

"You can fool some of the people all of the time, and all of the people
some of the time, but you cannot fool all of the people all of the time"

w logice pierwszego rzedu, w terminach relacji "You can fool person p at time
t".  

2. Pokazac, ze kazda struktura skonczona moze byc opisana z dokladnoscia
do izomorfizmu w logice pierwszego rzedu. Dokladnie, dla kazdej skonczonej
stryktury A nad skonczona sygnatura S istnieje zdanie f logiki pierwszego
rzedu takie, ze dla kazdej struktury B nad S, B|=f wtw B jest izomorficzne do
A.

3. Pokazac, ze w powyzszym zadaniu, jesli struktura zawiera w sobie relacje
liniowego porzadku na uniwersum, to zdanie f z poprzedniego zadania mozna
napisac uzywajac tylko trzech zmiennych (byc moze kwantyfikujac kazda po
wielekroc).


4. Pokazac, ze wielosortowa logika pierwszego rzedu daje sie interpretowac w
logice jednosortowej. (Prosze to zagadnienie przeczytac z notatek kolegow
i/lub kolezanki.)

5. Prosze udowodnic, ze gracz drugi wygrywa gre Ehrenfeuchta o m rundach na
dwoch dostatecznie duzych (ale skonczonych) lancuchach.