Logika dla informatyków/Ćwiczenia 4: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
(Nie pokazano 2 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
Linek z wykładu 8 do cwiczenia 4. Nazwa linku: "c"
+
Link z wykładu 8 do cwiczenia 4. Nazwa linku: "c"
  
  
Linia 6: Linia 6:
 
{{cwiczenie|1|c|
 
{{cwiczenie|1|c|
 
Wykazać, że dla dostatecznie dużych <math>q</math> istnieje zdanie o randze  
 
Wykazać, że dla dostatecznie dużych <math>q</math> istnieje zdanie o randze  
kwantyfikatorowej <math>q</math> definiujące porządek liniowy o mocy <math>2^q.</math>  
+
kwantyfikatorowej <math>q</math>, definiujące porządek liniowy o mocy <math>2^q.</math>  
 
}}
 
}}
  
Linia 17: Linia 17:
 
Niech <math>R</math> będzie jednoargumentowym symbolem relacyjnym. Udowodnić, że klasa wszystkich takich struktur <math>\mathfrak A=\langle A,R\rangle</math>, że <math>|R|=|A- R|</math>, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.}}  
 
Niech <math>R</math> będzie jednoargumentowym symbolem relacyjnym. Udowodnić, że klasa wszystkich takich struktur <math>\mathfrak A=\langle A,R\rangle</math>, że <math>|R|=|A- R|</math>, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.}}  
  
{{cwiczenie|4||
+
{{cwiczenie|4|f|
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów <math>\mathfrak A=\langle A,E\rangle,</math> w których istnieją dwa wierzchołki o równych sobie, skończonych stopniach, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.}}  
+
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych) grafów <math>\mathfrak A=\langle A,E\rangle</math>, w których istnieją dwa wierzchołki o równych sobie, skończonych stopniach, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.}}  
  
 
{{cwiczenie|5||
 
{{cwiczenie|5||
Linia 34: Linia 34:
  
 
{{cwiczenie|8||
 
{{cwiczenie|8||
Dane są dwie sześcioelementowe struktury relacyjne <math>\mathfrak A</math> i <math>\mathfrak B</math> nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Struktury są narysowane poniżej jako grafy skierowane:  
+
Dane są dwie sześcioelementowe struktury relacyjne <math>\mathfrak A</math> i <math>\mathfrak B</math> nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Struktury są narysowane poniżej jako grafy skierowane:
 +
 
[[Grafika:ldi_cw8.gif]]
 
[[Grafika:ldi_cw8.gif]]
  
 
Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie <math>\var\varphi</math> takie, że <math>\mathfrak A\models\var\varphi</math> i <math>\mathfrak B\not\models\var\varphi.</math>}}
 
Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie <math>\var\varphi</math> takie, że <math>\mathfrak A\models\var\varphi</math> i <math>\mathfrak B\not\models\var\varphi.</math>}}

Aktualna wersja na dzień 13:16, 1 paź 2006

Link 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 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

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 i nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Struktury są narysowane poniżej jako grafy skierowane:

Ldi cw8.gif

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