Skip to main content
LibreTexts - Ukrayinska

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

  1. Last updated
  2. Save as PDF
  • Page ID
    53054

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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}\).