Глава 6 вычислительные методы алгебры логики

Применение методов алгебры логики необходимо тогда, когда существенны не только количественные соотношения между величинами, характеризующими рассматриваемые процессы, но и связывающие их логические зависимости. При распознавании объектов эти методы используют в случаях, когда: 1) отсутствуют сведения о количественном распределении объектов по пространственным, временным, весовым, энергетическим или каким-либо другим интервалам в соответствующем пространстве признаков, а имеются лишь детерминированные логические связи между рассматриваемыми объектами и их признаками; 2) известны распределения объектов в пространстве признаков, законы распределения ошибок измерения величин, характеризующих отдельные объекты, но логические зависимости, связывающие признаки и классы объектов, сложны и не поддаются непосредственному анализу.

Примерами задач, для решения которых требуется применение методов алгебры логики, являются: распознавание типа объекта на основе данных наблюдения и известных априорных зависимостей между типами объектов и соответствующими признаками; установление различных совокупностей признаков распознаваемого объекта, учет которых наряду с уже известными приводил бы к определенному заключению о типе объекта; анализ информации, содержащейся в каком-либо докладе или сообщении и относящейся к определенным типам объектов, с целью определить, какие выводы можно сделать о данных объектах на основании полученного сообщения; выбор технической политики предприятия, направленной на достижение определенного экономического эффекта, если известны некоторые общие закономерности, связывающие, например, отдельные изменения в области технологии производства с расходами на рекламу, наличием запасов сырья и товаров, уровнем производительности труда, снижением себестоимости продукта и объемом сбыта; прогноз погоды; геологическая разведка; выявление закономерностей, связывающих определенные типы объектов и их признаки (задача обучения), и др.

Основные понятия алгебры логики

Алгебра логики — не пустое множество элементов, являющееся ее областью, вместе с некоторым заданным набором операций, которые можно совершать над элементами, не выходя за пределы области. Область алгебры логики состоит из множества высказываний — законченных предложений, которые могут иметь одно из двух значений истинности: либо быть истинными, либо быть ложными. Например, высказывание «пять — четное число» — ложное, а высказывание «логика — наука о законах мышления» — истинное. Высказывания обозначаются буквами А, В, С,..., К, X, Y; А₁ А₂,..., В_1, В₂,....

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

Конъюнкция. Операция логического умножения совершается, по крайней мере, над двумя высказываниями, соответствует комбинации этих высказываний с помощью слова «и» и обозначается знаком «×», например А × В читается «А и В». Высказывание А × В истинно тогда и только тогда, когда истинны высказывания А и В одновременно. Например, конъюнкция двух высказываний (самолет — это летательный аппарат) × (прямое попадание мощного снаряда в цель приводит к поражению цели) истинна, тогда как конъюнкция (три — четное число) • (применение танков целесообразно) ложна.

Дизъюнкция. Операция логического сложения совершается, по крайней мере, над двумя высказываниями, соответствует объединению этих высказываний с помощью слова «или» и обозначается знаком «+», например А + В читается «А или B». Высказывание А + В истинно, когда истинно либо только высказывание А, либо только высказывание В, либо истинны высказывания А и В одновременно. Например, дизъюнкция (танки могут остановить наступление пехоты) + (собака — насекомое) истинна. Высказывание А+В ложно тогда и только тогда, когда высказывание А ложно и высказывание В ложно.

Отрицание. Операция отрицания может совершаться над одним высказыванием, обозначается чертой над буквой, например `А, читается «не А». Высказывание `A истинно тогда и только тогда, когда высказывание А ложно *.

* Высказывания — элементы области алгебры логики, и поэтому наряду со словом «высказывание» далее часто будет употребляться термин «элемент».

В результате применения конъюнкции, дизъюнкции и отрицания к некоторому исходному набору элементов А, В, С,... возникают новые комбинированные элементы X, Y,..., которые называются булевыми* функциями от элементов А, В, С,.... Чтобы подчеркнуть зависимость функций от данных элементов, часто пишут: Х(А, В, С,...), Y(A, В, С,...)....

*Алгебра логики впервые была исследована Дж. Булем (1815—1864).

Рассмотрим две особо важные булевы функции: `А + В и А× В+`А`×В, выражающие определенные связи между элементами А и В.

Импликация (следование). Пусть высказывание `А + В истинно. Тогда в соответствии с определением дизъюнкции и отрицания заключаем, что если А истинно, то В тоже истинно, если В ложно, то А тоже ложно. Однако если В истинно, то А может быть как истинно, так и ложно. Такая зависимость между А и В называется импликацией, записывается в виде А® В и читается «если А, то В» или «из А следует В».

Эквивалентность. Пусть высказывание А×В+`А×`В истинно. Тогда из определения операций над высказываниями следует, что А та. В имеют одинаковые значения истинности, т. е. либо оба истинны, либо оба ложны. Такая зависимость между А и В называется эквивалентностью, записывается в виде А — В и читается «А эквивалентно В». Если А = В, то, какова бы ни была булева функция f(A, U, V,...), справедливо соотношение f(B, U, V,...) =f(B, U, V,...), что можно записать в виде

(6.1)

Среди всех булевых функций можно выделить функции, остающиеся истинными, безотносительно к тому, какие значения истинности принимают входящие в эти функции элементы, например а также (6.1). Такие функции называют универсально истинными или тавтологиями. Так как все тавтологии не различаются между собой с точки зрения значений истинности, то их обозначают I. Следовательно, можно записать и т. д. Отрицание 1, т. е. `1 — универсально ложный элемент; обозначается 0. Для любых X соотношения — тавтологии, так как не зависят от значения истинности X.

Необходимо отличать тавтологически истинные элементы от функций, которые истинны вследствие сделанных предположений или физических законов. Первые не несут никакой полезной информации, в то время как вторые накладывают определенные связи на входящие в них элементы. Например, если применительно к некоторой проблеме утверждается, что функция `А + В должна рассматриваться как истинная, т. е. `А + В= `1, то, как указывалось, это эквивалентно связи А®В. Аналогичный пример дает соотношение эквивалентности (А•В+`А• `В=`1) = (А = В). В дальнейшем будут рассматриваться другие возможные формы связей.

Основные правила алгебры логики следующие:

Данные формулы должны рассматриваться как тавтологии. Их справедливость может быть проверена вычислением значений истинности сложных высказываний в левой и правой частях равенства. Некоторые из этих формул могут быть выведены из других формул, например 19 устанавливается с помощью 3, 4, 6, 7, 12, 15 и 17 следующим образом: