2.4. БУЛЕВА АЛГЕБРА

Логические функции, приведенные в табл. 2.1, можно рассматривать как элементарные операции над одной или двумя двоичными переменными. Функционально полная система таких операций образует на множестве двузначных переменных алгебру логики. Таких алгебр можно представить столько же, сколько наберется подходящих функционально полных систем. Но наиболее распространена булева алгебра, в которой в качестве основных операций приняты конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ).

Часто конъюнкцию и дизъюнкцию называют соответственно логическим произведением я суммой, а отрицание — инверсией. Используются также и -гие варианты обозначений: для конъюнкции , для дизъюнкции и Для отрицания . Чтобы избежать в сложных формулах лишних скобок, которые появляются при суперпозиции функций, установлен жесткий порядок выполнения операций — конъюнкция предшествует дизъюнкции. Свойства булевых операций И, ИЛИ, НЕ определяются таблицами соответствующих функций (см. табл. 2.1) и могут быть представлены в виде

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

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

Свойства булевой алгебры используются для преобразования и упрощения логических формул, а также для доказательства теоретических положений. Коммутативность и ассоциативность позволяют выполнять операции И и ИЛИ, группируя переменные в любом порядке. Первая форма дистрибутивности указывает на допустимость вынесения общего множителя за скобки, как в обычной алгебре. Но вторая форма в обычной алгебре аналога не имеет, что является одним из основных отличий ее от алгебры логики. Свойства отрицания подчеркивают взаимодополнительную природу логических переменных. Повторы переменной и константы позволяют избавляться от постоянных слагаемых и множителей или при необходимости вводить их. Двойное отрицание не изменяет переменную, что можно рассматривать как пустую операцию. На основе идемпотентности можно удалять повторяющиеся переменные, вследствие чего в булевой алгебре не имеют смысла показатели степени и числовые коэффициенты, что также существенно отличает ее от обычной алгебры. Законы Моргана позволяют свести отрицание сложного выражения к отрицанию отдельных переменных.

Таблица 2.3

(см. оригинал)

Последние четыре свойства (склеивание, поглощение, замещение и выявление) полезны при различных преобразованиях и упрощениях булевых формул.

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

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

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

Из выражения (2.1) также следует, что дуальная функция выражается как отрицание исходной функции, в которой каждая переменная замещена ее отрицанием:

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

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