Алгебра высказываний (Булева алгебра)

Множеством высказываний является множество, состоящее из функций, заданных на множестве имен со значениями в двухэлементном множестве {//, 77}. Элементы последнего множества, например, в релейноконтактных и иных схемах, обозначают через 1 = И — истина (есть сигнал, ток) и 0=77-ложь (нет сигнала, тока). Все высказывания делят на два класса: простые, элементарные и составные, сложные. Сложные высказывания составляются из элементарных с помощью логических связок {логических операций).

Примеры: 2.1. 2 > 1 — простое истинное высказывание.

2.2. Если |я|<1, то а² > 1 — составное высказывание (ложное).

Высказывания мы будем обозначать прописными буквами латинского алфавита: элементарные высказывания буквами А, В, С, /?, сложные, соответственно, буквами S, Г,…, Z.

Операцией во множестве М ={А, В,С,…} всех высказываний называется всякая функция f (A_l9A₂₉…₉A") п переменных А_]9А₂, …, со значениями в этом же множестве М. Если п = 1, то операция называется унарной; если /? = 2, то J{A, В) называется бинарной операцией, и в общем случае, функция /7 переменных называется /7-арной операцией.

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

1. Единственная унарная логическая операция — отрицание с символом «-1» в метаязыке описывается так: слово «—iА» читается «не А» и означает отрицание высказывания А. Истинностная таблица операции отрицание имеет два столбца и две строки истинностных значений:

• 2. Четыре бинарные логические операции, с помощью каждой из которых образуется новое высказывание из двух высказываний, задаются следующим образом:
• 2.1. Конъюнкция &. высказывание А&В читается и означает А и В (совмещение высказываний: и Л, и В).
• 2.2. Дизъюнкция v: высказывание Aw В означает или А, или 5, а также и А, и В (союз или употребляется здесь в соединительном, а не в разъединительном смысле).
• 2.3. Импликация =>: высказывание А => В означает: если А, то В или А достаточно для В; или В следует из Л, или В необходимо для А. Последнее прочтение можно уточнить так: В необходимо для Л, но, возможно, не является достаточным.
• 2.4. Эквиваленция: высказывание А В означает следующее: А тогда и только тогда, когда 5, или А необходимо и достаточно для 5, и наоборот.

У бинарных логических операций отметим только несимметричность импликации и симметричность трех остальных. Истинностные таблицы бинарных логических операций содержат 2² = 4 строки истинностных значений:

Обратите внимание на 4-й и 5-й столбцы: из лжи следует «все, что угодно». Более того, справедливо следующее утверждение.

Теорема 2.1. ((А=>В) & (Л=>(—> В))) => (А = Л).

• Предположив противное, что А = Я, рассмотрим две возможности: 1) пусть В = И, тогдаiВ = Л. Теперь в силу А => (—iB) имеем И => Л, т. е. противоречие. Если же 2) В = Л, тогда из А => В имеем И => Л. Противоречие. Следовательно, наше предположение, что А = //, является ложным, т. е. справедливо заключение теоремы: А = Л. Ш

Здесь и ниже символы • и? означают начало и конец доказательства, соответственно.

Упражнение 2.1. Составьте истинностную таблицу сложного высказывания => ?)^v(((~В)о А)&ВУ}.

Указание. Введите промежуточные высказывания: Т =(А => В),

U = (-,?), Y = (U A), W =(Y & В), Z=(T v 5), тогда S = (-.Z). Подробная таблица будет содержать 2 + 6 = 8 столбцов и 2″ = 4 строки истинностных значений.

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

Соглашение 1 устанавливает приоритетность выполнения логических операций в такой последовательности —", &, V, =>, «>.

Теперь 5* 4 ->((А => 5) v (-, 5 А) & В).

Очевидно, что таблица истинности составного высказывания S содержит 2^т строк истинностных значений, если оно содержит т элементарных высказываний, т. е. S является функцией т аргументов.

Упражнение 2.2. Продолжить истинностную таблицу высказывания Z-n/lvMC^5oC:

Единственным ли образом можно выбрать здесь промежуточные высказывания S, Т, U и W, если известно, что U = SvT" ?

Истинностные таблицы логических операцийi, &, v, => и о можно было бы принять за способ определения этих операций без обращения к чьему-либо опыту.

Переменные с двумя значениями, например И и Л, а также функции этих переменных с тем же множеством значений называются булевыми. Мы будем их называть для краткости 6-переменными и 6-функциями (6-формулами).

Тождественно истинной или тавтологией называется «-формула, если при любом наборе значений ее 6-аргументов она принимает значение И, т. е. истина.

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

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

Две 6-формулы X и Y называются равносильными (метаязыковая запись равносильности: X = Y), если их значения совпадают при всех наборах их аргументов.

Нс все пять рассмотренных логических операций независимы. Они независимы в том смысле, что любую 6-формулу X можно преобразовать в равносильную ей 6-формулу, содержащую не более двух логических связок. Простейший пример: (HZ?)s ((H=>5) & (В => А)).

Справедливо следующее ниже общее предложение.

У тверждение 2.1. За базис логических операций можно принять любую из следующих пар логических связок: —. г/ &, —. и =>, —i и V.

Действительно, если за базис взять пару —> и л, то 1 )(A=>B)z (^AvB);

• 2) (A
• 3) (Л О 5^((-,/lv5)) &(-, BvA) j.

Доказательство равносильности 2) даст совпадение истинностных значений б-формул, А & В = Т и —1(—tAv—i B) = S:

Упражнение 2.3. Доказать равносильности 1) и 3).

Следующие четыре тавтологии выражают основные законы традиционной логики:

• 1) А=>А — закон тождества;
• 2) —I —1 А => А — закон двойного отрицания;
• 3) -I (А &-) А) — закон отрицания противоречия;
• 4) A vIА — закон исключенного третьего.

Продолжим этот список перечислением равносильностей:

• 5) А & В= В & А — коммутативность конъюнкции;
• 6) A v В =В v, А — коммутативность дизъюнкции;
• 7) (А & В) & С^А & (В & С)~ ассоциативность конъюнкции;
• 8) (A v В) v С = A v (В v С) — ассоциативность дизъюнкции;
• 9) А & (В v С)? (А & В)) v (А & С) — первый закон дистрибутивности;
• 10) Av (B & С) = (A v В) & (Av С) — второй закон дистрибутивности;
• 11) -,(AvB)sz-, A&-,?
• — законы О. де Моргана;
• 12) -,(А & B) sz-, Av-?
• 13) А &И = А]

f — законы поглощения.

14) АчЛ = А ].

При замене в перечисленных свойствах символа равносильности = эквиваленцией каждый закон превратится в тавтологию.

Всякое множество {А, В, С,…} с операциямиi, & и v, удовлетворяющими перечисленным выше равносильным высказываниям, называется алгеброй Буля. Дизъюнкцию v называют иногда сложением по аналогии с арифметикой чисел, а конъюнкцию & - умножением, последнее не совсем справедливо: в арифметике чисел второй закон дистрибутивности 10) не выполняется.