Упражнение 7

Тука сложи заглавие


страницата се нуждае от дописване/преглеждане


Първо ще разгледаме съждителни езици.
Те са като предикатните1, но нямат предикати :-)

$Var = \{x_1,....,x_n,...\}$

Дефиниция: Формула

1. променливите са формули
2. ако $\varphi, \psi$ - формули, тогава и $\neg \psi , (\varphi \land \psi ),(\varphi \lor \psi ),(\varphi \rightarrow \psi ),(\varphi \leftrightarrow \psi ),$ са формули

Семантика

$I$ - интерпретация
$I:Var \rightarrow \{t,f\}$, интерпретацията казва кои са верни
(може да е подмножество на $Var$ - т.е да показва кои променливи са верни (които не са от подмножеството са неверни))

Дефиниция интерпретация

$I \models \varphi$ - при интерпретация $I$ е вярна $\varphi$
$I \models x \leftrightarrow I(x) = t$
$I \models \neg x \leftrightarrow I(x) = f$
$I \models \varphi \And \psi \leftrightarrow I \models \psi$ и $I \models \varphi$
$I \models \varphi \lor \psi \leftrightarrow I \models \psi$ или $I \models \varphi$
$I \models \varphi \Rightarrow \psi \leftrightarrow$ ако $I \models \psi$ то $I \models \varphi$
(Горното вярно ли е? Ако I не е модел за phi то от формулата не можем да заключим нищо за psi. Тоест, според мен, е възможно I да е модел за psi но да не е за phi. Което сме записали на лекции е, че или I не е модел за phi или I е модел за psi. by espr1t)
$I \models \varphi \iff \psi \leftrightarrow I \models \psi$ т.с.т.к. $I \models \varphi$

Дефиниция тавтология

Бележим $\models \varphi$ и казваме, че $\varphi$ е тавтология, ако $\varphi$ е вярна при всяка интерпретация.

Още малко за интерпретацията

Ще записваме $\Sigma \models \Gamma$ където $\Sigma$ и $\Gamma$ са множества от формули, aко от $I \models \Sigma$ следва $I \models \Gamma$, т.е всеки модел на първото е модел на второто.
Принципно може вместо множества да пишем и просто единични формули $\varphi$ вместо $\{ \varphi \}$ - няма да се шашкате :)

$\varnothing \models \varphi$ - това означава, че $\varphi$ е вярно тогава, когато е вярно празното множество формули. Но празното множество е вярно при всяка интерпретация, следователно и $\varphi$ е вярна при всяка интерпретация. Т.е $\varphi$ е тавталогия. Записваме просто $\models \varphi$.

Дефиниция: логическо противоречие

Логическото противоречие е нещо като тавтологичен абсурд - т.е винаги грешно. Тоест когато не съшествува нито една интерпретация за която $I \models \varphi$, където $\varphi$ е формула. Казваме, че $\varphi$ е логическо противоречие.

Задача 1

Имаме
1.$\varphi$ не е логическо противоречие (т.е $\exists I_1 \models \varphi$)
2.$\psi$ не е тавтология (т.е $\exists I_2 \models \neg \psi$)
3.$\varphi \models \psi$ - всеки модел за $\varphi$ е модел и за $\psi$
Да се докаже, че $Var(\varphi) \cap Var(\psi) \neq \varnothing$

Решение:
Допускаме противното т.е., че $Var(\varphi) \cap Var(\psi) = \varnothing$

Построяваме си интерпретацията
$k(y) = \begin{cases} I_1(y), y \in Var(\varphi) \\ I_2(y), y \notin Var(\varphi) \end{cases}$
$k \models \varphi$ от 3. $k \models \psi$, но $k \models \neg \psi$ - противоречие, следователно сечението не е празно.

Сега ще говорим за предикатния случай (това дето го разглеждахме на лекции първите пъти).

Формули

Атомарни формули
Ако $p$ е $n$-местен предикатен символ, а $\tau_1,...,\tau_n$ - термове, тогава $p(\tau_1,..,\tau_n)$ - атомарна формула
1. Атомарните формули са функции.
2. Ако $\psi$ и $\varphi$ са формули, тогава и $\neg \varphi, \psi \land \varphi,\psi \lor \varphi, \psi \rightarrow \varphi,\psi \leftrightarrow \varphi$ са формули
Формули са и $\forall x \varphi, \exists x \varphi$

Структура

Семантична структура наричаме нареденото множество
$\mathcal{A}= \{A,I\}, A \neq \varnothing$
Бележим $|\mathcal{A}| = A$ това е универсумът на структурата, тоест обектите за който се говори в структурата, $A \neq \varnothing$
$I$ - интерпретация на обектите от универсумът.
$I(c) = c^{\mathcal{A}} \in A$, където $c$ - синтактичен обект, някакъв знак от $A$
$I(f) = f^{\mathcal{A}}:|\mathcal{A}|^n\rightarrow |\mathcal{A}|$ - $n$- местна функция съпоставя на $n$ елемента от $|\mathcal{A}|$ един елемент от $|\mathcal{A}|$
$I(p) = p^{\mathcal{A}} \subset A^n$

Оценка

$\upsilon : Var \rightarrow A$

Стойност на терм

$|| \tau ||^{\mathcal{A}}[\upsilon]$ - така бележим стойността на терма в структура $\mathcal{A}$ при оценка $\upsilon$
$|| x ||^{\mathcal{A}}[\upsilon] = \upsilon(x)$
$|| c ||^{\mathcal{A}}[\upsilon] = c^{\mathcal{A}}$
$|| f(\tau_1,..,\tau_n) ||^{\mathcal{A}}[\upsilon] = f^{\mathcal{A}}(|| \tau_1 ||^{\mathcal{A}},..,|| \tau_n||^{\mathcal{A}})$

Стойност на формула

$|| \tau_1 \doteq \tau_2 ||^{\mathcal{A}}[\upsilon] = || \tau_2 ||^{\mathcal{A}}[\upsilon] = || \tau_2 ||^{\mathcal{A}}[\upsilon]$
$|| p(\tau_1,...,\tau_n) ||^{\mathcal{A}}[\upsilon] = true \iff \langle || \tau_1 ||^{\mathcal{A}},..,|| \tau_n||^{\mathcal{A}} \rangle \in p^{\mathcal{A}}$
$|| \exists x \varphi ||^{\mathcal{A}}[\upsilon] \leftrightarrow$ съществува $a \in A$: $||\varphi||^{\mathcal{A}}[\upsilon_a^x] = true$
$|| \forall x \varphi ||^{\mathcal{A}}[\upsilon] \leftrightarrow$ за всяко $a \in A$: $||\varphi||^{\mathcal{A}}[\upsilon_a^x] = true$

Дефиниция (локално следване)

Нека $\Sigma, \Gamma$ са множества от предикатни формули. Ще казваме, че от $\Sigma$ локално следва $\Gamma$, ако

(1)
\begin{align} \forall \mathcal{A} \forall v (\mathcal{A} \underset{v}\models \Sigma \rightarrow \mathcal{A} \underset{v}\models \Gamma) \end{align}

Записваме $\Sigma \overset{l}\models \Gamma$.

Дефиниция (глобално следване)

Нека $\Sigma, \Gamma$ са множества от предикатни формули. Ще казваме, че от $\Sigma$ глобално следва $\Gamma$, ако

(2)
\begin{align} \forall \mathcal{A} (\mathcal{A} \models \Sigma \rightarrow \mathcal{A} \models \Gamma) \end{align}

което записано малко по-подробно (разписана дефиницията за "от структура следва множество формули"):

(3)
\begin{align} \forall \mathcal{A} (\forall v (\mathcal{A} \underset{v}\models \Sigma) \rightarrow \forall v(\mathcal{A} \underset{v}\models \Gamma) \end{align}

Записваме $\Sigma \overset{g}\models \Gamma$.

Забележка: Ако още не може да хванете тънката разлика: Локалното следване е по-силно: то казва че ако за дадена структура и оценка първото е вярно, то е вярно и второто. Глобалното следване казва, че ако в една структура е вярно първото (т.е за всички оценки е вярно), то в тази структура е вярно и второто (т.е за всички оценки е вярно и второто). Лесно се показва, че от локално следване следва глобално следване: ако си вземем една структура, и за всяка оценка е вярно първото, то от локалното следване следва, че за всяка оценка е вярно и второто. Следователно второто е вярно в структурата.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License