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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 1: Linia 1:
 
{{Cwiczenie|1||
 
{{Cwiczenie|1||
Wskazać przykład takiego zbioru <math>\Delta</math> zdań logiki pierwszego rzędu,że każde dwa jego ''przeliczalne'' modele są izomorficzne, ale istnieją dwa ''nieprzeliczalne'', nieizomorficzne ze sobą modele zbioru&nbsp;<math>\Delta.</math>  
+
Wskazać przykład takiego zbioru <math>\Delta</math> zdań logiki pierwszego rzędu, że każde dwa jego ''przeliczalne'' modele są izomorficzne, ale istnieją dwa ''nieprzeliczalne'', nieizomorficzne ze sobą modele zbioru&nbsp;<math>\Delta.</math>  
 
}}
 
}}
  
Linia 14: Linia 14:
  
 
{{Cwiczenie|4||
 
{{Cwiczenie|4||
Udowodnić, że klasa wszystkich struktur izomorficznych zestrukturą postaci <math>\mathfrak A=< \mathcal{P}(A),\cup,\cap,\subseteq></math>, gdzie <math>\cup,\cap</math> oraz<math>\subseteq</math> są odpowiednio sumą, przecięciem i zawieraniem zbiorów,nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.
+
Udowodnić, że klasa wszystkich struktur izomorficznych zestrukturą postaci <math>\mathfrak A=< \mathcal{P}(A),\cup,\cap,\subseteq></math>, gdzie <math>\cup,\cap</math> oraz<math>\subseteq</math> są odpowiednio sumą, przecięciem i zawieraniem zbiorów, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.
 
}}
 
}}
  
 
{{Cwiczenie|5||
 
{{Cwiczenie|5||
Pokazać, że jeśli klasa <math>\mathcal{A}</math> struktur nad sygnaturą<math>\Sigma</math> jest aksjomatyzowalna pewnym zbiorem zdań logiki pierwszego rzędu, oraz jej dopełnienie składające się ze struktur sygnatury&nbsp;<math>\Sigma,</math> ktore nie należą do <math>\mathcal{A}</math> też jest aksjomatyzowalne, to każda z tych klas jest w istocie aksjomatyzowalna ''jednym'' zdaniem pierwszego rzędu.
+
Pokazać, że jeśli klasa <math>\mathcal{A}</math> struktur nad sygnaturą<math>\Sigma</math> jest aksjomatyzowalna pewnym zbiorem zdań logiki pierwszego rzędu, oraz jej dopełnienie składające się ze struktur sygnatury&nbsp;<math>\Sigma</math>, które nie należą do <math>\mathcal{A}</math> też jest aksjomatyzowalne, to każda z tych klas jest w istocie aksjomatyzowalna ''jednym'' zdaniem pierwszego rzędu.
  
 
''Wskazówka:'' Założyć, że pierwsza klasa jest aksjomatyzowalna przez <math>\Delta</math>, a druga przez&nbsp;<math>\Delta',</math> ale żaden skończony podzbiór<math>\Delta</math> nie jest aksjomatyzacją <math>\mathcal{A}.</math> Pokazać, że<math>\Delta\cup\Delta'</math> spełnia założenia twierdzenia o&nbsp;zwartości.
 
''Wskazówka:'' Założyć, że pierwsza klasa jest aksjomatyzowalna przez <math>\Delta</math>, a druga przez&nbsp;<math>\Delta',</math> ale żaden skończony podzbiór<math>\Delta</math> nie jest aksjomatyzacją <math>\mathcal{A}.</math> Pokazać, że<math>\Delta\cup\Delta'</math> spełnia założenia twierdzenia o&nbsp;zwartości.
Linia 26: Linia 26:
 
Pokazać następujące twierdzenie Robinsona: Jeśli<math>\Delta,\Delta'</math> są spełnialnymi zbiorami zdań nad pewną sygnaturą <math>\Sigma,</math> zaś <math>\Delta\cup\Delta'</math> nie jest spełnialny, to istnieje takie zdanie <math>\var\varphi</math>, że <math>\Delta\models\var\varphi</math> oraz<math>\Delta'\models\lnot\var\varphi.</math>
 
Pokazać następujące twierdzenie Robinsona: Jeśli<math>\Delta,\Delta'</math> są spełnialnymi zbiorami zdań nad pewną sygnaturą <math>\Sigma,</math> zaś <math>\Delta\cup\Delta'</math> nie jest spełnialny, to istnieje takie zdanie <math>\var\varphi</math>, że <math>\Delta\models\var\varphi</math> oraz<math>\Delta'\models\lnot\var\varphi.</math>
  
''Wskazówka:'' Pokazać, że jeśli teza nie zachodzi, to<math>\Delta\cup\Delta'</math> spełnia założenia twierdzenia o&nbsp;zwartości.
+
''Wskazówka:'' Pokazać, że jeśli teza nie zachodzi, to <math>\Delta\cup\Delta'</math> spełnia założenia twierdzenia o&nbsp;zwartości.
 
}}
 
}}
  
 
{{Cwiczenie|7||
 
{{Cwiczenie|7||
Niech <math>Spec(\var\varphi)</math> oznacza zbiór mocy wszystkich skończonych modeli formuły <math>\var\varphi.</math> Pokazać, że jeśli <math>\Delta</math> jest takim zbiorem zdań, iż dla każdego <math>\var\varphi\in\Delta</math> zbiór <math>Spec(\lnot\var\varphi)</math> jest skończony,oraz jeśli <math>\Delta\models\psi,</math> to także <math>Spec(\lnot\psi)</math> jest skończony.
+
Niech <math>Spec(\var\varphi)</math> oznacza zbiór mocy wszystkich skończonych modeli formuły <math>\var\varphi.</math> Pokazać, że jeśli <math>\Delta</math> jest takim zbiorem zdań, iż dla każdego <math>\var\varphi\in\Delta</math> zbiór <math>Spec(\lnot\var\varphi)</math> jest skończony, oraz jeśli <math>\Delta\models\psi,</math> to także <math>Spec(\lnot\psi)</math> jest skończony.
 
}}
 
}}

Aktualna wersja na dzień 10:55, 1 paź 2006

Ćwiczenie 1

Wskazać przykład takiego zbioru zdań logiki pierwszego rzędu, że każde dwa jego przeliczalne modele są izomorficzne, ale istnieją dwa nieprzeliczalne, nieizomorficzne ze sobą modele zbioru 

Ćwiczenie 2

Udowodnić, że dla każdej struktury skończonej nad skończoną sygnaturą istnieje taki zbiór zdań pierwszego rzędu,że i dla każdej struktury zachodzi

Ćwiczenie 3

Niech będzie skończoną sygnaturą. Udowodnić, że dla każdego zbioru zdań nad następujące dwa warunki są równoważne

  • ma wyłącznie skończone modele.
  • ma z dokładnością do izomorfizmu skończenie wiele modeli.

Ćwiczenie 4

Udowodnić, że klasa wszystkich struktur izomorficznych zestrukturą postaci , gdzie oraz są odpowiednio sumą, przecięciem i zawieraniem zbiorów, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

Ćwiczenie 5

Pokazać, że jeśli klasa struktur nad sygnaturą jest aksjomatyzowalna pewnym zbiorem zdań logiki pierwszego rzędu, oraz jej dopełnienie składające się ze struktur sygnatury , które nie należą do też jest aksjomatyzowalne, to każda z tych klas jest w istocie aksjomatyzowalna jednym zdaniem pierwszego rzędu.

Wskazówka: Założyć, że pierwsza klasa jest aksjomatyzowalna przez , a druga przez  ale żaden skończony podzbiór nie jest aksjomatyzacją Pokazać, że spełnia założenia twierdzenia o zwartości.

Ćwiczenie 6

Pokazać następujące twierdzenie Robinsona: Jeśli są spełnialnymi zbiorami zdań nad pewną sygnaturą zaś nie jest spełnialny, to istnieje takie zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Delta\models\var\varphi} orazParser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Delta'\models\lnot\var\varphi.}

Wskazówka: Pokazać, że jeśli teza nie zachodzi, to spełnia założenia twierdzenia o zwartości.

Ćwiczenie 7

Niech Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle Spec(\var\varphi)} oznacza zbiór mocy wszystkich skończonych modeli formuły Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi.} Pokazać, że jeśli jest takim zbiorem zdań, iż dla każdego Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\in\Delta} zbiór Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle Spec(\lnot\var\varphi)} jest skończony, oraz jeśli to także jest skończony.