Тервер.asmАлгоритмыКомбалгJSMarkupHackWeb

Язык логики высказываний

Содержание:

Основными объектами логики высказываний являются высказывания и логические связки.

Высказывание

Под высказыванием будем понимать суждение, которое может быть истинно или ложно. Высказывания обозначаются латинскими буквами $A, B, C, $…, именуемыми логическими переменными или предметными символами \ литералами.

Логические связки

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

В данном случае, это:

  1. (¬) отрицание
  2. ($\and$) конъюнкция
  3. ($\or$) дизъюнкция
  4. ($\to$) импликация
  5. ($\leftrightarrow$) эквиваленция.

Существуют разные договоренности относительно приоритетов связок. Здесь и далее предполагаем, что связки даны по убыванию приоритета.

Так же в высказываниях могут присутствовать скобки для указания приоритетов. Лишние скобки можно опускать.

Формулы

В математической логике высказывания принято записывать в виде формул.

Атомарными формулами называются формулы, состоящие только из одного предметного символа (и ничего больше).

Определим множество всех формул по индукции:

  1. Логические константы 0, 1 являются формулами.
  2. Атомарные формулы являются формулами
  3. Если $F$ и $G$ - ФЛВ, то: ¬$F$ , $(F \and G)$, $(F \or G)$, $(F \to G)$, $(F \leftrightarrow G)$ также являются формулами.
  4. Других формул нет.

Язык, состоящий из этих формул, называется языком формальной логики.

Булева интерпретация

Булевой интерпретацией формулы $F$ называется отображение множества её логических переменных в множество логических констант.

Пусть $F$ - формула с множеством переменных $X$

Тогда $\phi : X \to {0, 1}$ - булева интерпретация $F$

Записывают $\phi = BInt(F)$

Две функции равны тогда и только тогда, когда их значения сопадают для любого набора аргументов.

Интерпретация

Значение булевой функции, при заданном наборе значений аргументов, называется интерпретацией формулы.

Какую-нибудь интепретацию формулы $F$ обозначают как $\phi(F)$

Примечание:

Эти два понятия очень схожи. Булева интерпретация - это функция. Интерпретация - это её отдельное значение. Кажется, запись $BInt(F)$ используется вместо $\forall \phi(F)$

Таким образом, если в формулу $F$ входит $n$ переменных, то $F$ имеет в точности $2^n$ попарно различных интерпретаций. Таблицу, в которой для каждой интерпретации указывается её значение, принятно называть таблицей истинности.

$F = (A \to B \and C) \and (¬A \to ¬B)$

A B C F
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 0
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 1

Как видим, формула может принимать разные значения в зависимости от интерпретации.

Тавтология и противоречие

Формула называется тавтологией, если при любой интепретации она истинна; или противоречием, если при любой интепретации - ложна.

Формула называется выполнимой, если для некоторой интерпретации она истинна.

Подформула

Подформулой атомарной формулы является она сама.

Подформулами формулы $¬F$ являются $¬F$ и все подформулы $F$.

Подформулами формул $F \and G, F \or G, F \to G, F \leftrightarrow G$ являются они сами и все подформулы формул $F$ и $G$.

Проще говоря, подформула - это “слитная” часть формулы, которая сама является формулой.

Например, формула $X \and Y \to X \or Z$ имеет 6 подформул:

$X, Y, Z, X \and Y, X \or Z, X \and Y \to X \or Z$