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 – „,</math>” na „</math>,” |
||
| (Nie pokazano 2 wersji utworzonych przez 2 użytkowników) | |||
| Linia 2: | Linia 2: | ||
Napisać zdanie logiki drugiego rzędu aksjomatyzujące pojęcie porządku | 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 | ciągłego i wywnioskować stąd, że dla tej logiki nie zachodzi także | ||
dolne twierdzenie Skolema- | dolne twierdzenie Skolema-Löwenheima. | ||
}} | }} | ||
| 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. | ||
}} | }} | ||
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.
