Logika dla informatyków/Ćwiczenia 4
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniaLink z wykładu 8 do cwiczenia 4. Nazwa linku: "c"
Ćwiczenie 1
Wykazać, że dla dostatecznie dużych
istnieje zdanie o randze kwantyfikatorowej , definiujące porządek liniowy o mocyĆwiczenie 2
Adaptując dowód Faktu #qqudowodnić, że struktury Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\{1-1/n | n=1,2,\dots\},\leq\>} oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\bigcup_{n=1}^\infty\{1-1/n,1+1/n,3-1/n\},\leq\>} , gdzie jest w obu wypadkach standardowym porządkiem liczb wymiernych, są elementarnie równoważne.
Wywnioskować stąd, że pojęcie dobrego porządku nie jest wyrażalne w logice pierwszego rzędu. (Zupełnie inny dowód tego faktu poznamy w Rozdziale 8.Ćwiczenie 3
Niech
będzie jednoargumentowym symbolem relacyjnym. Udowodnić, że klasa wszystkich takich struktur , że , nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.Ćwiczenie 4
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych) grafów
, w których istnieją dwa wierzchołki o równych sobie, skończonych stopniach, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.Ćwiczenie 5
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych) grafów
których każdy skończony podgraf jest planarny, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu. Ćwiczenie 6
Pokazać, że klasa wszystkich relacji równoważności, których wszystkie skończone klasy abstrakcji mają parzystą moc, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.
Ćwiczenie 7
Dane są dwie struktury relacyjne
Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} takie, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak A\models\var\varphi} i Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak B\not\models\var\varphi.} i nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Ich nośnikiem jest , relacja zachodzi wtedy i tylko wtedy, gdy , a relacja \wtw, gdyĆwiczenie 8
Dane są dwie sześcioelementowe struktury relacyjne
i nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Struktury są narysowane poniżej jako grafy skierowane: Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} takie, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak A\models\var\varphi} i Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak B\not\models\var\varphi.}