Logika dla informatyków/Ćwiczenia 8

Z Studia Informatyczne
< Logika dla informatyków
Wersja z dnia 10:55, 1 paź 2006 autorstwa Dorota (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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