Материал: Алгебра_кортежей

Таблица 1.6

Нетрудно убедиться, что 3-я и 6-я колонки табл. 1.6, соответствующие сравниваемым формулам, совпадают, что свидетельствует о равенстве формул.

Табличным способом, в частности, можно доказать, что импликацию можно выразить через дизъюнкцию и отрицание:

В алгебре логики, помимо описанных выше четырех основных операций ( , , , ), определено еще 12 различных логических связок. Эти дополнительные операции можно задать с помощью таблиц, аналогичных тем, которые были приведены выше (таблицы 1.1 1.4). Для того, чтобы выразить все функции алгебры логики, достаточно использовать лишь некоторые из них. Все остальные функции можно получить с помощью соответствующих формул (например, импликацию можно выразить с помощью отрицания и дизъюнкции, используя формулу X Y = X Y). Множество логических функций, достаточное для выражения всех остальных функций алгебры логики, называется функционально полным базисом. Например, таким базисом является множество логических функций { , , }. Алгебра логики, заданная в этом базисе, обозначается обычно B2 = <{0,1}, , , >. Как правило, для описания законов алгебры логики выбирается именно этот базис, причем сами законы можно разделить на две группы: 1) основные равносильности, соответствующие законам булевой алгебры; 2) равносильности, выражающие дополнительные логические операции через базисные.

Для иллюстрации законов второй группы приведем еще две дополнительные часто используемые операции. Это разделительное "ИЛИ" или

строгая дизъюнкция (обозначается символом " "), и эквивалентность

(обозначается символами " " или "~"). Их табличные определения даны в

30

Тогда, если возникает необходимость выразить дополнительные операциии ~, используя только основные, то применяются следующие формулы:

Проверить правильность этих преобразований можно табличным способом.

Возможно построить и другие функционально полные базисы. Так, установлено, что в базисе { , , } одна из операций – "лишняя", поскольку к функционально полным относятся базисы { , } и { , }. Для обоснования этого достаточно использовать один из законов де Моргана. Например, если выбрать в качестве базиса множество { , } логических функций, то конъюнкция двух произвольных атомов или формул выражается с помощью отрицания и дизъюнкции, если использовать равенство X Y = ( X Y).

Одним из функционально полных является базис { , }. Если выразить импликацию через дизъюнкцию и отрицание (X Y = X Y), то этот базис сводится к функционально полному базису { , }. В базисе { , } в последние годы принято строить аксиоматику исчисления высказываний – одного из разделов математической логики, изучающего общезначимые формулы

Формулы называются тождественно истинными (или общезначимыми, или тавтологиями), если при всех значениях входящих в них атомов они принимают значение 1 (истинно), и тождественно ложными, если при всех значениях входящих в них атомов они принимают значение 0 (ложно). Если формула не тождественно ложна, то это выполнимая формула. Если каждому атому, входящему в формулу, присвоить значение истинности (например, A = 0,

31

B = 1, C = 1), то набор этих равенств составляет (элементарную) подстановку данной формулы. Если при этом будет установлено, что для некоторой подстановки формула истинна, то такая подстановка называется выполняющей подстановкой.

Например, для формулы B A система равенств A = 1, B = 0 есть подстановка, но это не выполняющая подстановка (см. табл. 1.6).

Алгебру логики можно рассматривать как интерпретацию исчисления высказываний, поскольку она позволяет устанавливать тождественную истинность логических формул не с помощью символьных преобразований, а на основе алгебраических операций (уже упомянутый табличный способ). Табличным способом нетрудно проверить, что к тождественно истинным формулам относятся A A и B (A B), а к тождественно ложным – A A и (B A) ( A B). Кроме проверки общезначимости формул исчисления высказываний, табличный способ может применяться и для доказательства законов алгебры множеств. Рассмотрим это подробнее.

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

Теперь соответствие между формулами алгебры множеств и выражениями алгебры логики можно установить с помощью следующих правил:

1) все законы алгебры множеств, выраженные как равенство некоторого выражения универсуму, соответствуют общезначимой формуле алгебры логики (например, A A= U соответствует общезначимой формуле);

2) все законы алгебры множеств, выраженные как равенство некоторого выражения пустому множеству (например, A A = ) соответствуют тождественно ложной формуле алгебры логики;

3) если закон алгебры множеств устанавливает включение между двумя множествами, заданными определенными выражениями, то замена символа " " символом импликации ( ) в соответствующей формуле алгебры логики приводит к тому, что эта формула становится общезначимой;

32

4) законы алгебры множеств, выраженные в форме "если A, то B", записываются в алгебре логики как импликация (A B), при этом полученная формула общезначима.

В качестве примера выполним табличное доказательство одного из рассмотренных в предыдущем разделе законов сохранения алгебры множеств: если X Y, то для любого множества Z справедливо X Z Y Z.

С учетом приведенных выше правил соответствия этот закон в алгебре логики выражается формулой (X Y) ((X Z) (Y Z)). Ее общезначимость доказана табличным методом в табл. 1.9.

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

Несмотря на кажущуюся простоту, табличный метод обладает одним существенным недостатком: когда число переменных в формуле превышает 60, его использование для решения логических задач практически невозможно даже с помощью современной вычислительной техники. Число необходимых

33

вариантов в этом случае выражается формулой 2n, что означает известную многим исследователям логического вывода "экспоненциальную катастрофу". Было изобретено немало методов борьбы с этой катастрофой [Гэри, 1982]. Многие из них основаны на законах алгебры логики и алгебры множеств. Некоторые из методов приведены в главе 3. В настоящее время известно много частных случаев "труднорешаемых" задач логики и дискретной математики, решение которых не требует экспоненциального перебора вариантов. Но общего алгоритма, позволяющего при решении всех задач логического вывода избежать экспоненциальной катастрофы, пока не найдено. И даже не доказано существование или не существование такого алгоритма.

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

1.3.Булевы алгебры и системы логического вывода

1.3.1.Формальные системы

Описанные выше алгебраические системы имеют множество самостоятельных приложений. Например, алгебра логики применяется при исследовании релейно-контактных схем, а алгебра множеств – универсальное средство описания различного рода алгоритмов. Однако, в рамках формального подхода алгебраические системы в целом и булевы алгебры в частности традиционно воспринимаются лишь как модели или интерпретации некоторых формальных систем (алгебра множеств – как модель силлогистики Аристотеля, алгебра логики – как интерпретация исчисления высказываний). Возможно, в какой-то степени это объясняется историческими этапами формирования математики. Так, алгебра множеств была создана в процессе многовековых поисков математических оснований для силлогистики.

Рассмотрим понятия формальной системы и ее интерпретации более детально.

Математическая логика развивалась в XX веке как система, претендующая на то, чтобы выразить средствами ТФС все, имеющее отношение к

34