Следствие и семантическая эквивалентность

РЕЗЮМЕ
В этом уроке мы будем изучать следствие и семантическую эквивалентность в пропозициональной логике, что является естественным продолжением ранее пройденного материала. Мы узнаем, как вывести понятие семантического следствия из присвоений значений истинности и как эта идея связана с теоремой о выводимости. Кроме того, мы рассмотрим практические примеры использования таблиц истинности для получения полезных свойств, таких как устранение конъюнкции и введение дизъюнкции. Мы также исследуем понятие семантической эквивалентности и увидим, как оно связано с уже известными нам свойствами. Наконец, мы покажем, как использование моделей и методов вывода позволяет упростить изучение проблем семантического следствия и эквивалентности.

ЦЕЛИ ОБУЧЕНИЯ:
К концу этого урока студент сможет

Понять понятие семантического следствия.
Понять различные интерпретации символа ⊨.
Понять доказательство теоремы о выводимости в ее семантической версии и ее использование в изучении семантического следствия и эквивалентности.
Понять определение семантической эквивалентности и ее связь с значениями истинности.
Применить теорему о выводимости в ее семантической версии для преобразования задач следствия в задачи валидности.
Применить полезные свойства при использовании таблиц истинности для доказательства семантических эквивалентностей.
Применить законы поглощения, распределения и законы Де Моргана для упрощения сложных выражений.
Анализировать связь между моделями и выводами в изучении пропозициональной логики.

СОДЕРЖАНИЕ
ПРИСВОЕНИЯ И МОДЕЛИ
ТЕОРЕМА О ВЫВОДИМОСТИ (СЕМАНТИЧЕСКАЯ ВЕРСИЯ)
ИСПОЛЬЗОВАНИЕ ТЕОРЕМЫ О ВЫВОДИМОСТИ В ИССЛЕДОВАНИИ СЕМАНТИЧЕСКОГО СЛЕДСТВИЯ И ЭКВИВАЛЕНТНОСТИ
СЕМАНТИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬ И СВОЙСТВА
СИНТЕЗ

Изучение следствия и семантической эквивалентности является естественным продолжением того, что мы рассматривали при изучении семантики пропозициональной логики. Теперь мы рассмотрим, как из присвоений значений истинности выводится понятие семантического следствия и как на основе этого естественно появляется семантическая версия теоремы о выводимости. В результате будут показаны практические примеры использования таблиц истинности для получения некоторых полезных свойств. Все это также можно увидеть на YouTube канале.

Присвоения и модели

Сначала начнем с определения, которое имеет решающее значение для дальнейших разработок в этой статье, а именно с определения семантического следствия.

ОПРЕДЕЛЕНИЕ: Выражение

G

является следствием (семантическим) другого выражения

F

, если для каждого присвоения

\mathcal{A}

выполняется

$\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$

Это обозначается как $F\models G$ и читается как «выражение $F$ моделирует выражение $G$ » или « $G$ является следствием (семантическим) выражения $F$ .»

С этим определением на руках, мы должны заметить, что символ $\models$ на самом деле имеет несколько разных интерпретаций в зависимости от контекста:

$\mathcal{A} \models F$ означает, что $\mathcal{A}(F) = 1$ ; то есть « $\mathcal{A}$ моделирует $F$ .»
$G \models F$ означает, что если любое присвоение моделирует $G$ , то оно моделирует $F$ , и это читается как « $F$ является следствием $G$ .»
$\models F$ означает, что $F$ удерживается при любом присвоении; то есть $F$ является тавтологией.

Таким образом, несмотря на то, что символ $\models$ может иметь много интерпретаций, контекст не является двусмысленным.

Понятие семантического следствия близко к понятию «импликации», которое мы рассматривали ранее, в том смысле, что если выполняется $F\models G$ , то $\models (F\rightarrow G)$ . Фактически, это очень похоже на теорему о выводимости, которую мы рассматривали на нескольких занятиях назад.

Теорема о выводимости (семантическая версия)

[смотреть]

ТЕОРЕМА: Если

F

G

— произвольные выражения, то выполняется

$F\models G \Leftrightarrow \models (F\rightarrow G)$

Доказательство:

Доказательство этой теоремы легко получается при рассмотрении таблиц истинности

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

Если мы сосредоточимся на значении $F\models G$ , мы увидим, что это эквивалентно утверждению, что $\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$ , что, в свою очередь, то же самое, что сказать, что $\mathcal{A}\not\models F \vee \mathcal{A}\models G$ . Теперь, если заметить, что также $\mathcal{A}\not\models F$ эквивалентно $\mathcal{A}\models \neg F$ , то получаем, что $F\models G$ эквивалентно утверждению, что $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ . Теперь, если мы составим таблицу истинности для $F \rightarrow G$ и отметим зеленым цветом область, где выполняется $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ , то увидим следующее:

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

Из этого мы видим, что если $F\models G$ , то всегда $\models (F \rightarrow G)$ , и наоборот, что и является теоремой о выводимости и ее семантическим аналогом.

Предположим, что мы хотим узнать, является ли выражение $G$ следствием какого-либо другого выражения $F$ . Мы будем называть это задачей следствия. Используя приведенную выше теорему, эту задачу можно преобразовать в задачу валидности, потому что « $G$ является следствием $F$ , если и только если $(F\rightarrow G)$ является теоремой».

Использование теоремы о выводимости в изучении семантического следствия и эквивалентности

Из таблиц истинности можно сделать выводы о некоторых свойствах, которые напоминают ранее изученные.

ПРИМЕР: Показать с использованием таблиц истинности, что выполняются следующие свойства

Устранение конъюнкции:

(F\wedge G)\models F

Введение дизъюнкции:

F\models (F\vee G)

Противоречие:

(F\wedge\neg F)\models G

Решение: Используя теорему о выводимости, которую мы только что рассмотрели, мы можем преобразовать задачу следствия в задачу валидности.

Чтобы решить задачу Устранения конъюнкции, мы можем составить следующую таблицу истинности

$F$	$G$	$(F\wedge G)$	$((F\wedge G) \rightarrow F)$
$0$	$0$	$0$	$1$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$

Таким образом, мы показали, что $((F\wedge G)\rightarrow F)$ является тавтологией, и поэтому, согласно обратной теореме о выводимости, мы получаем, что $(F\wedge G) \models F$ .

Задача Введение дизъюнкции решается аналогично, создавая подходящую таблицу истинности

$F$	$G$	$(F\vee G)$	$(F\rightarrow(F\vee G))$
$0$	$0$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$
$1$	$1$	$1$	$1$

Здесь мы видим, что $(F\rightarrow (F\vee G))$ является тавтологией, и поэтому, согласно обратной теореме о выводимости, $F\models (F\vee G)$

И, наконец, свойство Противоречие доказывается с использованием того же метода

$F$	$\neg F$	$(F\wedge \neg F)$	$G$	$((F\wedge \neg F)\rightarrow G)$
$0$	$1$	$0$	$0$	$1$
$0$	$1$	$0$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$

С помощью этой таблицы истинности мы доказали, что $((F\wedge \neg F)\rightarrow G)$ является тавтологией, и поэтому, согласно обратной теореме о выводимости, $(F\wedge \neg F)\models G$ .

Семантическая эквивалентность и свойства

[смотреть]

ОПРЕДЕЛЕНИЕ: Если одновременно выполняются

F\models G

G\models F

, то говорят, что

F

G

являются семантически эквивалентными. Это обозначается как

F\equiv G

Следствием этого определения является то, что два выражения семантически эквивалентны, если и только если они имеют одинаковые значения истинности

ПРИМЕР: Можно показать с использованием таблиц истинности, что выполняются семантические эквивалентности симметрии.

(F\downarrow G) \equiv (G\downarrow F)

(F\vee G) \equiv (G\vee F)

(F\wedge G) \equiv (G\wedge F)

(F\leftrightarrow G) \equiv (G\leftrightarrow F)

(F\underline{\vee} G) \equiv (G\underline{\vee} F)

ПРИМЕР: Если

F

— произвольное выражение,

\top

— тавтология и

\bot

— противоречие, то с помощью таблиц истинности можно доказать следующие семантические эквивалентности

(F\wedge \top) \equiv F

(F\vee \top) \equiv \top

(F\wedge \bot) \equiv \bot

(F\vee \bot) \equiv F

Эти эквивалентности известны как законы поглощения.

ПРИМЕР: В семантике пропозициональной логики справедливы эквивалентности распределения конъюнкции и дизъюнкции.

(F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H))

(F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H))

ПРИМЕР: В семантике пропозициональной логики также справедливы Законы Де Моргана.

\neg(F\wedge G) \equiv (\neg F \vee \neg G)

\neg(F\vee G) \equiv (\neg F \wedge \neg G)

УПРАЖНЕНИЕ: Хорошим упражнением будет доказать с помощью таблиц истинности, что действительно выполняются семантические эквивалентности Законов Поглощения, Распределения и Законов Де Моргана.

ПРИМЕР: Доказать, используя семантические эквивалентности, следующую эквивалентность:

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D))$ .

Решение: Мы можем доказать эту эквивалентность, используя таблицы истинности, но если мы это сделаем, нам придется работать с выражением, содержащим 5 пропозициональных переменных, что означает необходимость составления таблицы истинности с

2^5 = 32

строками, и это было бы желательно избежать. Для достижения этой цели мы будем использовать уже показанные эквивалентности.

Во-первых, отметим, что $(E\vee \neg E)$ является тавтологией. Обозначим эту тавтологию как $\top$ . Тогда, используя законы поглощения, мы получаем

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B))$

Используя законы распределения, мы получаем

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B))$

Наконец, по симметрии

$((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D))$

Таким образом, следуя этим эквивалентностям, мы получаем эквивалентность

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D))$

что и требовалось доказать.

Синтез

Если рассмотреть развитие этого последнего примера, мы увидим, что с увеличением числа переменных сложность изучения задач семантического следствия и эквивалентности возрастает экспоненциально, если полагаться на таблицы истинности. Однако, как мы видели, из развития идеи модели возникает нечто аналогичное уже рассмотренным методам вывода. Эта связь между моделями и выводами будет рассмотрена в ближайшее время, и их комбинация, наконец, избавит нас от многочисленных головных болей при изучении логики.

Просмотры: 29

Семантическое следствие и эквивалентность