5.14: Семантичні поняття

Template:MathJaxZach

Дайте визначення структур для мов першого порядку, можна визначити деякі основні семантичні властивості та зв'язки між реченнями. Найпростішим з них є поняття дійсності пропозиції. Речення є дійсним, якщо воно задовольняється в кожній структурі. Допустимі речення - це ті, які задовольняються незалежно від того, як трактуються нелогічні символи в ньому. Тому дійсні речення також називаються логічними істинами —вони істинні, тобто задоволені, у будь-якій структурі і, отже, їх істинність залежить лише від логічних символів, що зустрічаються в них, і їх синтаксичної структури, але не від нелогічних символів або їх тлумачення.

Визначення$\PageIndex{1}$: Validity

Речення$A$ є дійсним$\Entails A$, якщо$\Sat{M}{A}$ для кожної структури$\Struct M$.

Визначення$\PageIndex{2}$: Entailment

Набір речень$\Gamma$ тягне за собою речення$A$$\Gamma \Entails A$, якщо для кожної структури$\Struct M$ з$\Sat{M}{\Gamma}$,$\Sat{M}{A}$.

Визначення$\PageIndex{3}$: Satisfiability

Набір пропозицій$\Gamma$ задовольняється, якщо$\Sat{M}{\Gamma}$ для якоїсь структури$\Struct M$. Якщо не$\Gamma$ задовольняється, його називають незадовільним.

Пропозиція$\PageIndex{1}$

Речення$A$ дійсне, якщо$\Gamma \Entails A$ для кожного набору речень$\Gamma$.

Доказ. Для прямого напрямку, нехай$A$ буде дійсним, і нехай$\Gamma$ буде набір речень. Нехай$\Struct M$ буде структура так, що$\Sat{M}{\Gamma}$. Так як$A$ діє$\Sat{M}{A}$, отже$\Gamma \Entails A$.

Для контрапозитивного зворотного напрямку нехай$A$ буде недійсним, тому існує структура$\Struct M$ с$\SatN{M}{A}$. Коли$\Gamma = \{ \ltrue \}$, так як$\ltrue$ діє,$\Sat{M}{\Gamma}$. Значить, існує така структура$\Struct M$, що$\Sat{M}{\Gamma}$ але$\SatN{M}{A}$, отже,$\Gamma$ не тягне за собою$A$. ◻

Пропозиція$\PageIndex{2}$

$\Gamma \Entails A$Якщо$\Gamma \cup \{\lnot A\}$ є незадовільним.

Доказ. Для прямого напрямку припустимо$\Gamma \Entails A$ і припустимо навпаки, що існує структура$\Struct M$ так, що$\Sat{M}{\Gamma \cup \{ \lnot A \}}$. Так як$\Sat{M}{\Gamma}$ і$\Gamma \Entails A$,$\Sat{M}{A}$. Крім того, так як$\Sat{M}{\Gamma\cup \{ \lnot A \}}$$\Sat{M}{\lnot A}$, так у нас є і те$\SatN{M}{A}$,$\Sat{M}{A}$ і інше, протиріччя. Значить, такого будови бути не може$\Struct M$, тому$\Gamma \cup \{ A \}$ є незадовільним.

Для зворотного напрямку, припустимо,$\Gamma \cup \{ \lnot A \}$ є незадовільним. Таким чином, для кожної структури$\Struct M$, або$\SatN{M}{\Gamma}$ або$\Sat{M}{A}$. Отже, для кожної структури$\Struct M$ з$\Sat{M}{\Gamma}$$\Sat{M}{A}$, так$\Gamma \Entails A$. ◻

Проблема$\PageIndex{1}$

1. Покажіть, що$\Gamma \Entails \bot$ iff$\Gamma$ є незадовільним.

2. Покажіть, що$\Gamma \cup \{A\} \Entails \bot$ якщо$\Gamma \Entails \lnot A$.

3. Припустимо,$c$ не відбувається в$A$ або$\Gamma$. Покажіть, що$\Gamma \Entails \lforall{x}{A}$ якщо$\Gamma \Entails \Subst{A}{c}{x}$.

Пропозиція$\PageIndex{3}$

Якщо$\Gamma \subseteq \Gamma'$ і$\Gamma \Entails A$, то$\Gamma' \Entails A$.

Доказ. Припустимо, що$\Gamma \subseteq \Gamma'$ і$\Gamma \Entails A$. Нехай$\Struct M$ буде таким, що$\Sat{M}{\Gamma'}$; потім$\Sat{M}{\Gamma}$, і з тих пір$\Gamma \Entails A$, ми отримуємо, що$\Sat{M}{A}$. Отже, коли завгодно$\Sat{M}{\Gamma'}$$\Sat{M}{A}$, так$\Gamma' \Entails A$. ◻

Теорема$\PageIndex{1}$: Semantic Deduction Theorem

$\Gamma \cup \{A\} \Entails B$іфф$\Gamma \Entails A \lif B$.

Доказ. Для прямого напрямку, нехай$\Gamma \cup \{ A \} \Entails B$ і нехай$\Struct M$ буде структура так, що$\Sat{M}{\Gamma}$. Якщо$\Sat{M}{A}$, то$\Sat{M}{\Gamma \cup \{ A \} }$, так як$\Gamma \cup \{ A \}$ тягне за собою$B$, отримуємо$\Sat{M}{B}$. Тому$\Sat{M}{A \lif B}$, так$\Gamma \Entails A \lif B$.

Для зворотного напрямку, нехай$\Gamma \Entails A \lif B$ і$\Struct M$ буде структура так, що$\Sat{M}{\Gamma \cup \{ A \}}$. Тоді$\Sat{M}{\Gamma}$, так$\Sat{M}{A \lif B}$, і з тих пір$\Sat{M}{A}$,$\Sat{M}{B}$. Отже, коли завгодно$\Sat{M}{\Gamma \cup \{ A \} }$$\Sat{M}{B}$, так$\Gamma \cup \{ A \} \Entails B$. ◻

Пропозиція$\PageIndex{4}$

$\Struct{M}$Дозволяти бути і структура, і$A(x)$ формула з однією вільною змінною$x$, і$t$ замкнутий член. Потім:

1. $A(t) \Entails \lexists{x}{A(x)}$

2. $\lforall{x}{A(x)} \Entails A(t)$

Доказ.

1. Припустимо$\Sat{M}{A(t)}$. Let $s$ be a variable assignment with $s(x) = \Value{t}{M}$. Then $\Sat[,s]{M}{A(t)}$ since $A(t)$ is a sentence. By Proposition 5.13.3, $\Sat[,s]{M}{A(x)}$. By Proposition 5.12.4, $\Sat{M}{\lexists{x}{A(x)}}$.

2. Вправа.

◻

Проблема$\PageIndex{2}$

Заповніть доказ Пропозиції$\PageIndex{4}$.