Logika dla informatyków/Ćwiczenia 12: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 5: | Linia 5: | ||
}} | }} | ||
{{cwiczenie| | {{cwiczenie|2|b| | ||
Pokazać, że odpowiednik twierdzenia o zwartości nie zachodzi dla | Pokazać, że odpowiednik twierdzenia o zwartości nie zachodzi dla | ||
logiki drugiego rzędu. | logiki drugiego rzędu. | ||
}} | }} | ||
{{cwiczenie| | {{cwiczenie|3|c| | ||
Napisać zdanie MSO, którego wszystkie skończone modele to | Napisać zdanie MSO, którego wszystkie skończone modele to | ||
dokładnie te grafy, które są 3-kolorowalne. | dokładnie te grafy, które są 3-kolorowalne. | ||
}} | }} | ||
{{cwiczenie| | {{cwiczenie|4|d| | ||
Napisać zdanie <math>\displaystyle \Sigma_1^1</math>, którego wszystkimi modelami są | Napisać zdanie <math>\displaystyle \Sigma_1^1</math>, którego wszystkimi modelami są | ||
dokładnie struktury skończone. | dokładnie struktury skończone. | ||
}} | }} | ||
{{cwiczenie| | {{cwiczenie|5|e| | ||
Napisać zdanie MSO, które definiuje język regularny składający się z tych wszystkich słów nad <math>\displaystyle A_1=\{0,1\},</math> w których liczba jedynek jest parzysta. | Napisać zdanie MSO, które definiuje język regularny składający się z tych wszystkich słów nad <math>\displaystyle A_1=\{0,1\},</math> w których liczba jedynek jest parzysta. | ||
}} | }} | ||
Wersja z 20:21, 1 paź 2006
Ćwiczenie 1
Napisać zdanie logiki drugiego rzędu aksjomatyzujące pojęcie porządku ciągłego i wywnioskować stąd, że dla tej logiki nie zachodzi także dolne twierdzenie Skolema-Lowenheima.
Ćwiczenie 2
Pokazać, że odpowiednik twierdzenia o zwartości nie zachodzi dla logiki drugiego rzędu.
Ćwiczenie 3
Napisać zdanie MSO, którego wszystkie skończone modele to dokładnie te grafy, które są 3-kolorowalne.
Ćwiczenie 4
Napisać zdanie , którego wszystkimi modelami są dokładnie struktury skończone.
Ćwiczenie 5
Napisać zdanie MSO, które definiuje język regularny składający się z tych wszystkich słów nad w których liczba jedynek jest parzysta.
