Семантика пропозициональной логики
РЕЗЮМЕ
На этом занятии изучается семантика пропозициональной логики, в частности, присвоение значений истинности выражению и то, как они распространяются от одного выражения к другому через логические связки. Вводится понятие таблиц истинности и приводятся таблицы истинности для производных связок, таких как отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность и исключающая дизъюнкция. Также дается определение присвоения значений для множества атомарных выражений и объясняется, как это присвоение естественным образом распространяется на все выражения, которые можно построить из этого множества. В заключение рассматриваются определения корректных, удовлетворимых и неудовлетворимых выражений, а также приводятся примеры тавтологий и противоречий. Однако признается, что вычисление таблиц истинности для сложных выражений может быть неэффективным, поэтому упоминается поиск альтернативных методов для решения задач корректности или удовлетворимости.
ЦЕЛИ ОБУЧЕНИЯ:
По окончании этого занятия студент будет способен
- Объяснить семантику пропозициональной логики
- Использовать таблицы истинности для представления присвоения значений истинности выражениям в пропозициональной логике
- Моделировать выражение с присвоением в пропозициональной логике
- Применять семантические правила пропозициональной логики для определения, является ли выражение тавтологией, противоречием или контингентным
СОДЕРЖАНИЕ
О ПРИСВОЕНИИ ЗНАЧЕНИЙ ИСТИННОСТИ
СЕМАНТИКА ЛОГИЧЕСКИХ СВЯЗОК ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКИ
ПРИСВОЕНИЯ В ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКЕ
МОДЕЛИ В ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКЕ
ПРОБЛЕМА ЭФФЕКТИВНОСТИ В СЕМАНТИКЕ ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКИ
О Присвоении Значений Истинности
Ранее мы рассмотрели синтаксис и дедуктивные системы пропозициональной логики. Хотя это помогло нам понять, как выводить одни выражения из других, мы не говорили ничего о присвоении значений истинности. Поскольку мы уже обсудили все, что нужно знать о дедуктивных техниках в пропозициональной логике, начнем наше изучение семантики пропозициональной логики, где мы рассмотрим, как присвоения значений истинности распространяются от одного выражения к другому.
Семантика Логических Связок Пропозициональной Логики
Семантика логических связок вводится через таблицы истинности, так как они предоставляют простой и упорядоченный способ представления всех возможных присвоений для выражения.
Таблица Истинности Логической Связки «NOR»
Начнем с самой фундаментальной логической связки — отрицания совместного утверждения (NOR). Его таблица истинности выглядит следующим образом:
| \alpha | \beta | (\alpha\downarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Значения «1» и «0» соответствуют «истине» и «ложи» соответственно. Каждая строка таблицы истинности представляет возможное присвоение значения переменным (или атомарным выражениям), составляющим изучаемое выражение (или выражения). Аналогично, каждая колонка, содержащая выражение, сформированное этими переменными, показывает возможные результаты данных присвоений. Таким образом, интерпретация этой таблицы показывает, что \alpha\downarrow\beta истинно только тогда, когда \alpha и \beta одновременно ложны, и ложно в противном случае. Именно поэтому эта логическая связка называется отрицанием совместного утверждения.
Таблицы Истинности Производных Логических Связок
На основе семантики отрицания совместного утверждения можно вывести семантику остальных логических связок через их определения. Они следующие:
| Отрицание: | \neg \alpha | := | (\alpha\downarrow\alpha) |
| Дизъюнкция: | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| Конъюнкция: | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| Импликация: | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| Эквивалентность: | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| Исключающая дизъюнкция: | (\alpha \underline{\vee} \beta) | := | \neg(\alpha\leftrightarrow \beta) |
На основе этих определений можно вычислить таблицы истинности для остальных логических связок:
Отрицание
| \alpha | \neg \alpha |
| 0 | 1 |
| 1 | 0 |
Отсюда следует, что логическая связка «отрицание» имеет свойство инвертировать значение истинности выражения, на которое она применяется.
Дизъюнкция
| \alpha | \beta | (\alpha\vee\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Поэтому дизъюнкция (или просто «или») между двумя выражениями истинна, если хотя бы одно из выражений истинно, и ложна, когда оба выражения одновременно ложны.
Конъюнкция
| \alpha | \beta | (\alpha\wedge\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Следовательно, конъюнкция между двумя выражениями истинна, только если оба выражения одновременно истинны, и ложна в других случаях. Поэтому другое подходящее название для этой связки может быть «совместное утверждение».
Импликация
| \alpha | \beta | (\alpha\rightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Таким образом, таблица истинности импликации обобщает понятие о том, что истинное выражение может подразумевать только истинное выражение, но ложное выражение может подразумевать любое.
Эквивалентность
| \alpha | \beta | (\alpha\leftrightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Эквивалентность образует истинное выражение, если оба выражения, составляющие её, имеют одинаковые значения истинности, и ложное в других случаях.
Исключающая Дизъюнкция
| \alpha | \beta | (\alpha\underline{\vee}\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Исключающая дизъюнкция между двумя выражениями истинна, когда одно и только одно из выражений истинно, и ложна в других случаях.
Присвоения в Пропозициональной Логике
С учетом ранее описанного, у нас есть простое представление о том, что такое присвоение; однако для дальнейших разработок нам потребуется нечто более точное. Если S=\{A_1, A_2, \cdots, A_n\} это множество атомарных выражений, а \mathcal{F}(S) это множество всех выражений, которые можно построить из выражений в S, то имеем следующее определение:
ОПРЕДЕЛЕНИЕ: Присвоение на S это функция \mathcal{A}: S \longrightarrow \{0,1\}
Другими словами, присвоение на S определяет значение истинности для каждого атомарного выражения в S. Присвоение \mathcal{A} на S естественным образом распространяется на все элементы \mathcal{F}(S). Если у нас есть выражение F\in \mathcal{F}(S), то присвоение \mathcal{A} на S соответствует уникальной строке в таблице истинности F и \mathcal{A}(F) называется значением истинности F в этой строке.
Присвоение \mathcal{A} на S также может распространяться на некоторые выражения, не входящие в \mathcal{F}(S). Если F_0 это выражение, не входящее в \mathcal{F}(S), и S_0 это множество атомарных подвыражений F_0, то если все расширения \mathcal{A} для S\cup S_0 имеют одно и то же значение для F_0, то \mathcal{A}(F_0) определяется как это значение.
ПРИМЕР: Если A и B это атомарные выражения и \mathcal{A} это присвоение на \{A,B\}, определенное через \mathcal{A}(A)=1 и \mathcal{A}(B)=0, то имеем:
\mathcal{A}(A\wedge B)=0 и \mathcal{A}(A\vee B)=1
И хотя присвоение на переменную C не установлено, можно сказать:
\mathcal{A}(A\wedge (C\vee \neg C))=1 и \mathcal{A}(B\vee (C\wedge \neg C))=0
Это происходит с последними двумя выражениями, потому что, независимо от присвоения для C, всегда будет:
\mathcal{A}(C\vee\neg C)=1 и \mathcal{A}(C\wedge\neg C)=0
Что можно быстро проверить, рассчитав их таблицы истинности.
| C | \neg C | (C\wedge \neg C) | (C \vee \neg C) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
■ Конец Примера
Модели в Пропозициональной Логике
Рассмотрим присвоение \mathcal{A} для множества выражений S. Если F\in S таково, что \mathcal{A}(F)=1, то говорят, что присвоение \mathcal{A} моделирует F, или что выражение F поддерживается присвоением \mathcal{A}, и это записывается как
\mathcal{A}\models F.
И из этого выводятся следующие определения:
ОПРЕДЕЛЕНИЕ: Выражение называется корректным, если оно поддерживается любым присвоением. Если F корректно, то это записывается как \models F . Корректные выражения также называются тавтологиями.
ПРИМЕР: Выражение (C\vee \neg C), которое мы уже рассматривали, является тавтологией.
■ Конец Примера
ОПРЕДЕЛЕНИЕ: Выражение называется удовлетворимым, если оно поддерживается хотя бы одним присвоением. Удовлетворимые выражения, не являющиеся тавтологиями, называются контингентами.
ОПРЕДЕЛЕНИЕ: Выражение называется неудовлетворимым, если оно не поддерживается никаким присвоением. Неудовлетворимые выражения называются противоречиями. Если F это противоречие, то это записывается как \not\models F .
ПРИМЕР: Выражение (C\wedge \neg C), которое мы уже рассматривали, является противоречием..
■ Конец Примера
Примеры Тавтологий и Противоречий
Предположим, что мы хотим узнать, является ли выражение корректным или нет. Этот вопрос является задачей принятия решения в семантике пропозициональной логики. Задача принятия решения — это любая задача, которая, исходя из определенного ввода, возвращает «да» или «нет». Если нам дают выражение F и мы спрашиваем, корректно ли оно, то мы имеем задачу принятия решения, называемую задачей корректности. Аналогично, если мы спрашиваем, удовлетворимо ли выражение, то мы имеем задачу удовлетворимости. В пропозициональной логике таблицы истинности предлагают систематический подход к решению этих задач принятия решения: если все возможные значения истинности F равны «1», то F корректно; если только некоторые из них равны «1», то оно удовлетворимо; и наконец, если все они равны «0», то оно неудовлетворимо.
ПРИМЕР: Рассмотрим выражение ((A\wedge (A \rightarrow B)) \rightarrow B). Чтобы определить, является ли это выражение корректным, удовлетворимым или противоречивым, строим его таблицу истинности.
| A | B | (A\rightarrow B) | (A\wedge(A\rightarrow B)) | ((A\wedge(A\rightarrow B))\rightarrow B) |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Таким образом, мы видим, что ((A\wedge(A\rightarrow B))\rightarrow B) истинно для всех возможных присвоений, и, следовательно, является тавтологией.
■ Конец Примера
ПРИМЕР: Теперь рассмотрим выражение (((A\rightarrow B)\rightarrow A)\wedge \neg A). Его таблица истинности будет такой:
| A | B | (A\rightarrow B) | ((A\rightarrow B)\rightarrow A) | \neg A | (((A\rightarrow B)\rightarrow A)\wedge \neg A) |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Следовательно, это выражение является противоречием.
■ Конец Примера
Проблема Эффективности в Семантике Пропозициональной Логики
Теоретически, мы можем определить, является ли выражение корректным, контингентным или неудовлетворимым, просто вычислив его таблицу истинности, что не представляет особой сложности; к сожалению, легкость выполнения платится ценой эффективности. Если у нас есть выражение F, состоящее из n атомарных выражений, то нам придется вычислить таблицу истинности с 2^n строками; таким образом, если, например, F состоит из 23 атомарных выражений, то его таблица истинности будет иметь 8.388.608 строк, которые должны быть рассчитаны. Используя этот метод, несмотря на его механичность и простоту, вычисление быстро перестает быть осуществимым с увеличением сложности выражений. Поэтому одной из наших будущих целей будет поиск способа решения задач корректности или удовлетворимости без необходимости вычисления таблиц истинности. Поиск таких методов является одной из центральных задач любой логики.