Logika dla informatyków/Ćwiczenia 12: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
m Zastępowanie tekstu – „\displaystyle ” na „” |
||
| Linia 16: | Linia 16: | ||
{{cwiczenie|4|d| | {{cwiczenie|4|d| | ||
Napisać zdanie <math> | Napisać zdanie <math>\Sigma_1^1</math>, którego wszystkimi modelami są | ||
dokładnie struktury skończone. | dokładnie struktury skończone. | ||
}} | }} | ||
{{cwiczenie|5|e| | {{cwiczenie|5|e| | ||
Napisać zdanie MSO, które definiuje język regularny składający się z tych wszystkich słów nad <math> | Napisać zdanie MSO, które definiuje język regularny składający się z tych wszystkich słów nad <math>A_1=\{0,1\},</math> w których liczba jedynek jest parzysta. | ||
}} | }} | ||
Wersja z 08:47, 28 sie 2023
Ć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-Löwenheima.
Ć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.
