Logika dla informatyków/Ćwiczenia 8

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

\subsection*{Ćwiczenia}\begin{small}

  1. Wskazać przykład takiego zbioru zdań logiki pierwszego rzędu,że każde dwa jego \textit{przeliczalne} modele są izomorficzne, aleistnieją dwa \textit{nieprzeliczalne}, nieizomorficzne ze soba modelezbioru 
  2. Udowodnić, że dla każdej struktury skończonej Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA} nad skończonąsygnaturą istnieje taki zbiór zdań pierwszego rzędu,że Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA\models\Delta} i dla każdej struktury Parser nie mógł rozpoznać (nieznana funkcja „\strB”): {\displaystyle \strB\models\Delta} zachodzi Parser nie mógł rozpoznać (nieznana funkcja „\strB”): {\displaystyle \strB\cong\strA.}


  1. Niech będzie skończoną sygnaturą. Udowodnić, że dlakażdego zbioru zdań nad następujące dwa warunkisą równoważne
    • ma wyłącznie skończone modele.
    • ma z dokładnością do izomorfizmu skończenie wiele modeli.



\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 oraz są odpowiednio sumą, przecięciem i zawieraniem zbiorów,nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

\item Pokazać, że jeśli klasa struktur nad sygnaturą jest aksjomatyzowalna pewnym zbiorem zdań logiki pierwszegorzę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\textit{jednym} zdaniem pierwszego rzędu.


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

\item Pokazać następujące twierdzenie Robinsona: Jeśli są spełnialnymi zbiorami zdań nad pewną sygnaturą zaś nie jest spełnialny, to istniejetakie 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.}

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

\item Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle Spec\begin{eqnarray*}\var\varphi\end{eqnarray*}} 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ż dlakażdego Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\in\Delta} zbiór Parser nie mógł rozpoznać (błąd składni): {\displaystyle Spec\begin{eqnarray*}\lnot\var\varphi\end{eqnarray*}} jest skończony,oraz jeśli to także Parser nie mógł rozpoznać (błąd składni): {\displaystyle Spec\begin{eqnarray*}\lnot\psi\end{eqnarray*}} jestskończony.


\end{small}