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

Wersja z 11:44, 22 wrz 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 soba 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 $𝔄 = < 𝒫 (A), \cup, \cap, \subseteq >$ , gdzie $\cup, \cap$ oraz $\subseteq$ 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 $Σ,$ ktore 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 $Δ \cup Δ^{'}$ 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ś $Δ \cup Δ^{'}$ 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 $Δ \cup Δ^{'}$ 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 $S p e c (\neg ψ)$ jest skończony.

@@ Linia 1: / Linia 1: @@
+Ćwiczenie 1<br>
+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 soba modele zbioru&nbsp;<math>\Delta.</math>
-\subsection*{Ćwiczenia}\begin{small}
+Ćwiczenie 2<br>
-#Wskazać przykład takiego zbioru <math>\Delta</math> zdań logiki pierwszego rzędu,że każde dwa jego \textit{przeliczalne} modele są izomorficzne, aleistnieją dwa \textit{nieprzeliczalne}, nieizomorficzne ze soba modelezbioru&nbsp;<math>\Delta.</math>
+Udowodnić, że dla każdej struktury skończonej <math>\mathfrak A</math> nad skończoną sygnaturą istnieje taki zbiór <math>\Delta</math> zdań pierwszego rzędu,że <math>\mathfrak A\models\Delta</math> i dla każdej struktury <math>\mathfrak B\models\Delta</math>zachodzi <math>\mathfrak B\cong\mathfrak A.</math>
-#Udowodnić, że dla każdej struktury skończonej <math>\strA</math> nad skończonąsygnaturą istnieje taki zbiór <math>\Delta</math> zdań pierwszego rzędu,że <math>\strA\models\Delta</math> i dla każdej struktury <math>\strB\models\Delta</math>zachodzi <math>\strB\cong\strA.</math>
-#Niech <math>\Sigma</math> będzie skończoną sygnaturą. Udowodnić, że dlakażdego zbioru zdań <math>\Delta</math> nad <math>\Sigma,</math> następujące dwa warunkisą równoważne
+Ćwiczenie 3<br>
-#*<math>\Delta</math> ma wyłącznie skończone modele.
+Niech <math>\Sigma</math> będzie skończoną sygnaturą. Udowodnić, że dla każdego zbioru zdań <math>\Delta</math> nad <math>\Sigma,</math> następujące dwa warunki są równoważne
-#*<math>\Delta</math> ma z dokładnością do izomorfizmu skończenie wiele modeli.
+*<math>\Delta</math> ma wyłącznie skończone modele.
+*<math>\Delta</math> ma z dokładnością do izomorfizmu skończenie wiele modeli.
+Ćwiczenie 4<br>
+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.
-\item Udowodnić, że klasa wszystkich struktur izomorficznych zestrukturą postaci \mbox{</math>\strA=\langle\mathcal{P}\begin{eqnarray*}A\end{eqnarray*},\cup,\cap,\subseteq\rangle</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.
+Ćwiczenie 5<br>
+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.
-\item Pokazać, że jeśli klasa <math>\mathcal{A}</math> struktur nad sygnaturą<math>\Sigma</math> jest aksjomatyzowalna pewnym zbiorem zdań logiki pierwszegorzę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\textit{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.
+Ćwiczenie 6<br>
+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.
-{\em Wskazówka:\/} Założyć, że pierwsza klasa jest aksjomatyzowalnaprzez <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.
-\item 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 istniejetakie zdanie <math>\var\varphi</math>, że <math>\Delta\models\var\varphi</math> oraz<math>\Delta'\models\lnot\var\varphi.</math>
+Ćwiczenie 7<br>
+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.
-{\em 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.
-\item Niech <math>Spec\begin{eqnarray*}\var\varphi\end{eqnarray*}</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ż dlakażdego <math>\var\varphi\in\Delta</math> zbiór <math>Spec\begin{eqnarray*}\lnot\var\varphi\end{eqnarray*}</math> jest skończony,oraz jeśli <math>\Delta\models\psi,</math> to także <math>Spec\begin{eqnarray*}\lnot\psi\end{eqnarray*}</math> jestskończony.
-\end{small}

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

Wersja z 11:44, 22 wrz 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia