Булева алгебра

Логические функции, приведенные в табл. 2.1, можно рассматривать, как элементарные операции над одной или двумя двоичными переменными. Функционально полная система таких операций образует на множестве двузначных переменных алгебру логики. Таких алгебр можно представить столько же, сколько наберется подходящих функционально полных систем. Но наиболее распространена булева алгебра, в которой в качестве основных операций приняты конъюнкция х₁х₂ (И), дизъюнкция х₁+х₂ (ИЛИ) и отрицание `х (НЕ). Часто конъюнкцию и дизъюнкцию называют соответственно логическим произведением и суммой, а отрицание – инверсией. Используются также и другие варианты обозначений: для конъюнкции х₁Ù х₂, для дизъюнкции х₁Ú х₂ и для отрицания х^/. Чтобы избежать в сложных формулах лишних скобок, которые появляются при суперпозиции функций, установлен жесткий порядок выполнения операций – конъюнкция предшествует дизъюнкции. Свойства булевых операций И, ИЛИ, НЕ определяются таблицами соответствующих функций (см. табл. 2.1) и могут быть представлены в виде

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

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

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

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

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

С принципом дуальности непосредственно связано обобщение законов де Моргана на любое число переменных. Если функция j^*(х₁, х₂, …, х_n) дуальная функции j (х₁, х₂, …, х_n), то

`j (х<sub>1</sub>, х<sub>2</sub>, …, х<sub>n</sub>) = j<sup>*</sup>(`х₁, `х<sub>2</sub>, …, `х_n), (2.1)

откуда следует, что отрицание некоторой функции можно определить заменой в дуальной функции каждой переменной ее отрицанием. Пусть, например, задана функция y = x +`vz. Дуальная ей у<sup>*</sup> = х (v+`z) и, следовательно, `у =`х (`v + z).

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

j^*(х₁, х₂, …, х_n) =`j (`х₁, `х<sub>2</sub>, …, `х_n). (2.2)

Таблица 2.3

Свойство	Первая форма	Вторая форма
1. Коммутативность	х+у=у+х	ху=ух
2. Ассоциативность	х+(y+z)=(x+y)+z	x(yz)=(xy)z
3. Дистрибутивность	x(y+z)=xy+xz	x+yz=(x+y)(x+z)
4. Дополнение	x+x=1	xx=0
5. Повтор переменной	x+0=x	x1=x
6. Повтор константы	x+1=1	x0=0
7. Двойное отрицание	X=x	x=x
8. Идемпотентность	x+x=x	xx=x
9. Законы де Моргана	x+y=xy	xy=x+y
10. Склеивание	xy+xy=x	(x+y)(x+y)=x
11. Поглошение	x+xy=x	x(x+y)=x
12. Замещение	x+xy=x+y	x(x+y)=xy
13. Выявление	xy+xz=xy+xz+yz	(x+y)(x+z)= =(x+y)(x+z)(y+z)