Logika dla informatyków/Ćwiczenia 4

Linek z wykładu 8 do cwiczenia 4. Nazwa linku: "c"

Ćwiczenie 1

Wykazać, że dla dostatecznie dużych $q$ istnieje zdanie o randze kwantyfikatorowej $q$ definiujące porządek liniowy o mocy $2^q.$

Ć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 $\le$ 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 $R$ będzie jednoargumentowym symbolem relacyjnym. Udowodnić, że klasa wszystkich takich struktur $\mathfrak{𝔄}=⟨A,R⟩$, że $|R|=|A-R|$, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

Ćwiczenie 4

Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów $\mathfrak{𝔄}=⟨A,E⟩,$ 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 $\mathfrak{𝔄}=⟨A,E⟩,$ 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 $\mathfrak{𝔄}=⟨U,R^{\mathfrak{𝔄}}⟩$ i $\mathfrak{𝔅}=⟨U,R^{\mathfrak{𝔅}}⟩$ nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Ich nośnikiem jest $U=\{1,2,\dots ,15\}$, relacja $R^{\mathfrak{𝔄}}(x,y)$ zachodzi wtedy i tylko wtedy, gdy $x|y$, a relacja $R^{\mathfrak{𝔅}}(x,y)$ \wtw, gdy $x\equiv y(\mathrm{mod}2).$

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.}

Ćwiczenie 8

Dane są dwie sześcioelementowe struktury relacyjne $\mathfrak{𝔄}$ i $\mathfrak{𝔅}$ 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.}