Основные операции над высказываниями

Для высказываний X и Y можно определить следующие основные логические операции.

1. Отрицание () – высказывание, которое истинно тогда и только тогда, когда X ложно. В разговорной речи высказыванию соответствуют фразы: “не X ”, “неверно, что X ”.

2. Конъюнкция () – логическим умножение. Высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания. В разговорной речи ей соответствует союз “и” ( – “ X и Y ”).

3. Дизъюнкция () – логическим сложение. Высказывание, которое ложно тогда и только тогда, когда ложны оба высказывания. В разговорной речи ей соответствует союз “или” ( – “ X или Y ”).

4. Импликация () – логическое следование. Высказывание, которое ложно тогда и только тогда, когда X – истинно, а Y – ложно. В разговорной речи импликации соответствуют следующие высказывания: “ X только тогда, когда Y ”, “из X следует Y ”, “если X то Y ”. При этом X – посылка, а Y – заключение.

5. Эквиваленция () – высказывание, которое истинно тогда и только тогда, когда истинностные значения высказываний X и Y совпадают. В разговорной речи эквиваленция соответствует высказываниям вида: “ X эквивалентно Y ”, “X тогда и только тогда, когда Y ”, “ X необходимо и достаточно для Y ”.

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

Таблица 1. Таблица истинности для логических операций

A	B
И	И	Л	Л	И	И	И	И
И	Л	Л	И	Л	И	Л	Л
Л	И	И	Л	Л	И	И	Л
Л	Л	И	И	Л	Л	И	И

 

При помощи операций возможно создавать комбинации из высказываний.

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

При вычислении по формуле учитывается приоритет логической операции. Перечисленные выше логические операции расположены в порядке убывания приоритета. Изменить порядок логических вычислений можно с помощью расстановки скобок.

Исходные высказывания могут быть постоянными, то есть иметь определенные значения “истина” или “ложь”. Если элементарное высказывание не имеет определенного значения, то это переменное высказывание. Например:

1) A:=”Джек лает”, B:=”Джек любит кости”

С:= (Джек лает и любит кости) – это постоянное высказывание

2) A(X):=”Собака (X) лает”, B(X):=”Собака (X) любит кости”

С(X):= (Собака с именем X лает и любит кости) – это переменное высказывание.

Пропозициональной формулой (ПФ) называется логическое выражение, содержащее переменные соответствующие логическим высказываниям, 0, 1 – константы и логические операции , , , , , называемые пропозициональными связками, скобки (,) используемые для определения приоритета операций. ПФ определяется индуктивно следующим образом:

1.Отдельно взятая переменная (высказывание) и константа (0, 1) – это ПФ.

2. Если A и B, составленные из допустимых символов – ПФ, то и , , , , , – тоже ПФ.

Никаких других ПФ, кроме образованных по правилу 2, нет.

Пример

– пропозициональная формула

– не пропозициональная формула

 

Таблицей истинности для ПФ является перечень значений данной ПФ при всех возможных значениях входящих в нее переменных.

Пропозициональная формула называется тавтологией, если на всех значениях входящих в нее переменных она равна 1. Обозначение: - пропозициональная формула А есть тавтология.

Приведем ряд тавтологий, могущих оказаться полезными при преобразовании высказываний:

Закон двойного отрицания: (1)

Закон исключенного третьего: (2)

Идемпотентность операций дизъюнкции и конъюнкции:

(3)

(4)

p из конъюнкции: (5)

p из дизъюнкции: (6)

Коммутативность операций дизъюнкции и конъюнкции:

(7)

(8)

Ассоциативность операций дизъюнкции и конъюнкции:

(9)

(10)

Разложение операций дизъюнкции и конъюнкции:

(11)

(12)

Правила де Моргана: (13)

(14)

Закон контрапозиции: (15)

Транзитивность импликации: (16)

Закон косвенного доказательства: (17)

Закон разбора случаев: (18)

Транзитивность эквиваленции: (19)

Закон противоположности: (20)

Представление единицы:

(21)

(22)

Представление нуля:

(23)

(24)

Представление импликации через дизъюнкцию и отрицание:

(25)

Представление эквиваленции:

(26)

(27)

(28)

Представление конъюнкции: (29)

Представление дизъюнкции: (30)