Logika dla informatyków/Ćwiczenia 12: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m Zastępowanie tekstu – „\displaystyle ” na „” |
m Zastępowanie tekstu – „,</math>” na „</math>,” |
||
| Linia 21: | Linia 21: | ||
{{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>A_1=\{0,1\} | 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. | ||
}} | }} | ||
Aktualna wersja na dzień 09:25, 5 wrz 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.
