Алгебра логики и цифровые компьютеры

Автор: Аркадий Белоусов

• Введение
• Элементарные булевы функции
• Основные законы булевой алгебры
• Алгебры булевых функций
• Функция сложения по модулю 2 (xor)
• Оптимизация логических выражений
• Заключение
• Литература

Введение

Алгебра логики - предельно важная для цифровых компьютеров тема. И с точки зрения их устройства, схемотехники, и с точки зрения их функционирования и программирования поведения. Действительно, мало-мальски сложное действие невозможно без обратной связи, без анализа условий выполнения. Например, "ЕСЛИ нам хочется пить, ТО мы пьём, ИНАЧЕ мы даже не думаем об этом". "ЕСЛИ компьютер не работает И питание включено, ТО компьютер сгорел". "ЕСЛИ точка левее левой стороны квадрата ИЛИ правее правой, ТО точка расположена не в квадрате". "Ревёт ли зверь в лесу глухом, трубит ли рог, гремит ли гром...". "Кошелёк или жизнь".

Вот как трактует логику толковый словарь: "Логика - наука, изучающая способы обоснования суждений, доказательства, мышления и логического вывода. В математической логике используются для этого методы алгебры или теории алгоритмов". "Алгебра логики (булева алгебра) - раздел математики, изучающий методы оперирования логическими (булевыми) переменными, принимающими только два значения - истина и ложь. Предложен английским математиком Джорджем Булем". Добавим только, что помимо манипуляций константами "да" и "нет" логические переменные могут являться результатом применения к числам операторов отношения (меньше, больше, равно и т.п.).

В компьютерах булевы переменные представляются (кодируются) битами (разрядами двоичной системы счисления), где 1 обычно означает истину, а 0 - ложь. Вот ещё одно достоинство двоичной системы счисления! "Но да будет слово ваше: да, да; нет, нет; а что сверх этого, то от лукавого" (Евангелие от Матфея 5,37).

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

Теперь отвлечёмся от интерпретации логических переменных и сосредоточимся на логических функциях.

Элементарные булевы функции

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

Для функций одной переменной может существовать всего четыре различные булевы функции g₁, g₂, g₃ и g₄, представленные в следующей таблице:

x	g1	g2	g3	g4
0	0	0	1	1
1	0	1	0	1

Из таблицы следует, что функции g₁ и g₄ не зависят от аргумента и являются соответственно константами 0 и 1, а функция g₂ повторяет значение аргумента, т.е. g₂=x. Функция g₃ называется отрицанием или инверсией переменной x и обозначается как not(x).

Для функций двух переменных может существовать 16 (и только 16) различных функций. Таблица истинности этих функций следующая:

x1	x2	F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

В число этих функций входят 6 вырожденных функций (константы: F₀=0 и F₁₅=1; переменные: F₃=x₁ и F₅=x₂; инверсии: F₁₂=not x₁ и F₁₀=not x₂). Остальные функции с их обозначениями приведены ниже:

Функция	Название	Выражение через конъюнкцию, дизъюнкцию и отрицание	Читается как
F1	конъюнкция	x1 and x2	x1 и x2
F7	дизъюнкция	x1 or x2	x1 или x2
F6	сложение по модулю 2	(x1 and not x2) or (not x1 and x2)	x1 неравнозначно x2
F8	функция Пирса	not x1 and not x2	ни x1, ни x2
F9	эквивалентность	(not x1 and not x2) or (x1 and x2)	x1 равнозначно x2
F11	импликация	x1 or not x2	если x2, то x1
F14	штрих Шеффера	not x1 or not x2	неверно, что x1 и x2
F2	запрет по x2	x1 and not x2	неверно, что если x1, то x2
F4	запрет по x1	not x1 and x2	неверно, что если x2, то x1
F13	импликация	not x1 or x2	если x1, то x2 (x1 -> x2)

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

Для записи штриха Шеффера в выражениях обычно используется апостроф (x₁'x₂), а для сложения по модулю 2 - слово xor (от eXslusive OR, "исключающее или", читается "ксор"). В ассемблерах конъюнкция, дизъюнкция и отрицание обычно записываются соответствующими английскими словами (and, or, not). В языках же высокого уровня эти функции могут обозначаться как словами (Паскаль), так и специальными знаками (в C использованы знаки "&", "|" и "~").

Иногда по аналогии с теорией множеств конъюнкция называется пересечением, а по аналогии с арифметикой в формулах используется знак умножения "*". Для дизъюнкции же используется знак сложения "+". И действительно - если вспомнить, как ведёт себя нуль в операциях умножения и сложения, а потом посмотреть на таблицы истинности конъюнкции и дизъюнкции, то можно найти много общего.

По этой причине в языках программирования приоритет конъюнкции обычно выше, чем приоритет дизъюнкции, и в выражении (x₁ or x₂ and x₃) подразумевается, что (x₂ and x₃) будет выполнено первым. В этой же статье, чтобы не вводить систему приоритетов, в выражениях с разными операциями скобки расставляются явно (см. таблицу обозначений выше) - только отрицание, как префиксная операция, должна выполняться первой.

Основные законы булевой алгебры

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

1. закон двойного отрицания: not not x = x
2. закон коммутативности (от перестановки аргументов результат не меняется):
   x₁ or x₂ = x₂ or x₁
   x₁ and x₂ = x₂ and x₁
   
3. закон ассоциативности (порядка вычислений):
   x₁ or (x₂ or x₃) = (x₁ or x₂) or x₃
   x₁ and (x₂ and x₃) = (x₁ and x₂) and x₃
   
4. закон дистрибутивности (раскрытия скобок):
   x₁ or (x₂ and x₃) = (x₁ or x₂) and (x₁ or x₃)
   x₁ and (x₂ or x₃) = (x₁ and x₂) or (x₁ and x₃)
   
5. правила де Моргана:
   not (x₁ or x₂) = not x₁ and not x₂
   not (x₁ and x₂) = not x₁ or not x₂
   
6. правила операций с константами 0 и 1:
   not 0 = 1, not 1 = 0,
   x or 0 = x, x or 1 = 1,
   x and 1 = x, x and 0 = 0
   
7. правила операций с переменной и её инверсией:
   x or not x = 1
   x and not x = 0
   

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

1. закон поглощения:
   x₁ or (x₁ and x₂) = x₁
   x₁ and (x₁ or x₂) = x₁
   
2. закон идемпотентности (повторное применение не даёт ничего нового):
   x or x or ... or x = x
   x and x and ... and x = x
   
3. на основании закона дистрибутивности, а также 7-го и 6-го законов:
   x₁ or (not x₁ and x₂) = x₁ or x₂

Алгебры булевых функций

Внимательный читатель может спросить: "а где функции от большего количества переменных? Почему все функции описывались через конъюнкцию, дизъюнкцию и отрицание?". Законные вопросы.

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

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

• not x, x₁ and x₂
• not x, x₁ or x₂
• x₁'x₂ (штрих Шеффера)
• not x₁ and not x₂ (функция Пирса)
• x₁ xor x₂ (сложение по модулю 2), x₁ and x₂, 1
• x₁ and not x₂ (запрет по x₂), 1

Не правда ли, замечательные функции - штрих Шеффера и функция Пирса? Их одних достаточно для построения всех прочих функций алгебры логики. Действительно:

	x1'x1 = not x1 or not x1 = not x1
	(x1'x1)'(x2'x2) = not (not x1 or not x1) or not (not x2 or not x2)
			= not not x1 or not not x2 = x1 or x2
	(x1'x2)'(x1'x2) = not (not x1 or not x2) or not (not x1 or not x2)
			= (x1 and x2) or (x1 and x2)= x1 and x2

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

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

Минимальность и избыточность - важные аспекты теории информации. Как факт: измерения избыточности русского языка дали около 80%. В сленгах (например, языке авиадиспетчеров) избыточность ещё выше.

Функция сложения по модулю 2 (xor)

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

x1	x2	and	or	xor
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

Почему xor называется "сложение по модулю 2"? Потому что так оно и есть: в двоичной системе 0+0=0, 0+1=1+0=1, 1+1=10, а по модулю 2 (остаток от деления на 2) последняя сумма как раз и даёт 0.

Включение функции xor в джентльменский набор вызвано её замечательными свойствами. Во-первых, при инвертировании одного из аргументов эта функция также инвертируется. Во-вторых, эта функция показывает, когда аргументы не равны (а при инвертировании одного из аргументов - когда равны). В-третьих, она позволяет проводить управляемое инвертирование: при нулевом аргументе другой аргумент не меняется, при единичном же значении второй аргумент инвертируется. Наконец, эта функция инволютивна (её повторное применение возвращает к исходному аргументу): если (x₃=x₁ xor x₂), то (x₃ xor x₁=x₂) и (x₃ xor x₂=x₁).

На последнем свойстве построен трюк с обменом значений двух переменных без использования третьей переменной (в C это записывается как "a^=b^=a^=b"). В графике эта функция применяется при выводе спрайтов на картинку - повторное её применение убирает спрайт с картинки. Также эта функция используется в криптографии - одна из схем заключается в наложении некоего кода на поток данных через функцию xor. Зашифрованный таким образом поток на исходный поток не похож, но может быть легко восстановлен повторным применением шифрующего кода.

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

x1	x2	x1	исключающее или	неравнозначность(несовпадение)	сложение по модулю 2	дизъюнкция (ИЛИ)
0	0	0	0	0	0	0
0	0	1	1	1	1	1
0	1	0	1	1	1	1
0	1	1	0	1	0	1
1	0	0	1	1	1	1
1	0	1	0	1	0	1
1	1	0	0	1	0	1
1	1	1	0	0	1	1

Несложно заметить, что инволютивность (при равенстве двух аргументов результат равен третьему) получается только для сложения по модулю 2. Поэтому, когда говорится о функции xor, обычно следует понимать именно сложение по модулю 2.

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

Оптимизация логических выражений

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

Вот пример фрагмента из программы на C со сложными условиями (здесь "&&", "||" и "!" - специальная форма конъюнкции, дизъюнкции и отрицания):

	if(dirFind == 0 || !ftime || notCHANGE){
		msg = "/c only when compare date/time";
		if(invert == 0 || notCHANGE && !arg){
			msg = "No date/time or attributes option";
			if(!notCHANGE || (arg | ftime)) msg = NULL;
		}
	}

Построим выражение, истинное, когда координаты точки находятся в границах квадрата (при условии, что абсцисса идёт слева направо, а ось ординат сверху вниз):

	ЕСЛИ	точка.X >= квадрат.левый.X	И
		точка.X <= квадрат.правый.X	И
		точка.Y >= квадрат.верхний.Y	И
		точка.Y <= квадрат.нижний.Y,
	ТО точка лежит в квадрате.

Выбрать наименьшее из трёх A, B, C:

	если A < B  и A < C  то наименьшее = A,
	если A >= B и B < C  то наименьшее = B,
	если A >= C и B >= C то наименьшее = C.

Внимание! Приведённый пример не оптимален. Сократим его, вынеся за скобки некоторые сравнения:

	если A < B то
		если A < C то наименьшее = A,
		иначе наименьшее = C.
	иначе
		если B < C то наименьшее = B,
		иначе наименьшее = C.

В оптимизированном примере всего три сравнения вместо шести. Более того, если в первом примере для достижения результата всегда выполняется шесть сравнений, то во втором примере всегда выполняется только два сравнения! Замечательный результат. Пример сокращения, учитывающий особенности натурального ряда:

	если x >= 1 то
		если x >= 0 то результат = 3*x
		иначе результат = -x
	иначе результат = x

Эта конструкция сокращается до следующей (если x >= 1, то x также >= 0):

	если x >= 1 то результат = 3*x иначе результат = x

Вот пример формального сокращения с учётом основных законов:

	(a and b) or (not a and b) or (a and not b)
	= ((a and b) or (not a and b)) or (a and not b)
	= ((a or not a) and b) or (a and not b)
	= (1 and b) or (a and not b) = b or (a and not b) = a or b

Иногда встречаются сложные разборы случаев (разновидность таблицы решений). Рассмотрим следующую таблицу расценок на билеты в бассейн. Здесь переменные A (возраст < 14 лет), B (возраст <= 18 лет), C (группа), D (студенты) - результаты опроса.

	если     a and not b                     то ошибка в опросе
	если     a and     b and     c and     d то 1 рубль
	если     a and     b and     c and not d то 1 рубль
	если     a and     b and not c and     d то 2 рубля
	если     a and     b and not c and not d то 2 рубля
	если not a and     b and     c and     d то 1 рубль
	если not a and     b and     c and not d то 2 рубля
	если not a and     b and not c and     d то 2 рубля
	если not a and     b and not c and not d то 3 рубля
	если not a and not b and     c and     d то 1 рубль
	если not a and not b and     c and not d то 3 рубля
	если not a and not b and not c and     d то 2 рубля
	если not a and not b and not c and not d то 4 рубля

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

	если a and not b 				то ошибка в опросе
	если c and ((a and b) or (not a and d))		то 1 рубль
	если (not c and ((a and b) or (not a and d)))
		or (not a and b and c and not d)	то 2 рубля
	если not a and not d and
		((b and not c) or (not b and c))	то 3 рубля
	если not a and not b and not c and not d	то 4 рубля

Вот вариант с сокращённым числом "задаваемых вопросов", хотя и с большим количеством ветвей. Основание - зависимость переменных A и B.

	если	 a and not b                     то ошибка в опросе
	если	 a           and     c           то 1 рубль
	если not a           and     c and     d то 1 рубль
	если	 a           and not c           то 2 рубля
	если not a and     b and     c and not d то 2 рубля
	если not a           and not c and     d то 2 рубля
	если not a and     b and not c and not d то 3 рубля
	если           not b and     c and not d то 3 рубля
	если           not b and not c and not d то 4 рубля

Выше разборы случаев независимы и все ветви можно отрабатывать одновременно. Последовательный разбор с выносом условий "за скобку" позволяет ещё больше сократить сложность разбора (глубина 9 при 12 вопросах):

	если a and not b	то ошибка в опросе
	иначе если a and c	то 1 рубль
	иначе если а		то 2 рубля
	иначе если c and d	то 1 рубль
	иначе если b and c	то 2 рубля
	иначе если d		то 2 рубля
	иначе если b		то 3 рубля
	иначе если c		то 3 рубля
	иначе			   4 рубля

Если продолжить вынос за скобки, то можно получить древовидный разбор (всего 11 вопросов, глубина 5):

	если a and not b то ошибка в опросе
	иначе если (a and b) or (not a and d) то
		если c то 1 рубль
		иначе	  2 рубля
	иначе если b and c		то 2 рубля
	иначе если not b and not c	то 4 рубля
	иначе				   3 рубля

Наконец, доведя вынос за скобки до конца, можно получить следующий разбор (всего 9 вопросов, глубина 6):

	      если a and not b то ошибка в опросе
	иначе если not d то
		если not c то
			      если a то 2 рубля
			иначе если b то 3 рубля
			иначе		4 рубля
		иначе
			      если a то 1 рубль
			иначе если b то 2 рубля
			иначе		3 рубля
	иначе
		если not c то 2 рубля
		иначе	      1 рубль

Обратите внимание! Помимо размера опросника сократилась и сложность его применения. Если в первом варианте при последовательном переборе ветвей в худшем случае (4 рубля) получается 50 вопросов (обращений к переменным), то в последнем варианте в худшем случае (например, "больше 14 лет и больше 18 лет, не студенты, группа") получается 6 вопросов. Сокращение в 8 раз!

К сожалению, до сих пор нет эффективных алгоритмов, целенаправленно и быстро минимизирующих функции и подбирающих наиболее экономичные схемы реализации заданных выражений. Найти гарантированно минимальное выражение произвольной функции можно лишь методом полного перебора вариантов различных способов группировки, а это реально осуществимо лишь при небольшом числе аргументов. С ростом же числа аргументов сложность минимизации растёт экспоненциально и быстро становится не под силу ни человеку, ни компьютеру. Но расстраиваться не стоит - на практике сложные, плохо оптимизируемые выражения встречаются не часто, а основные законы тождественных преобразований позволяют неплохо сократить сложность большинства выражений без особых усилий.

Заключение

Информация, вводимая в компьютер, состоит из условий (исходных данных) и программы решения (алгоритма) и уже содержит результат в потенциальном, скрытом виде. Соответственно, работа компьютера не даёт НОВОЙ информации и при преобразованиях КОЛИЧЕСТВО ИНФОРМАЦИИ остаётся неизменным, хотя сама информация может переходить в потенциальное состояние и обратно.

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

Причиной невозможности изменить величину информации в модели (системе, отражающей отдельные, ограниченные в нужном направлении стороны явлений), невозможности самообучения, является 4-й закон логики, сформулированный Лейбницем - закон "достаточного основания". Он явился первым вариантом закона сохранения информации.

Однако Джордж Буль, предложивший алгебру логики (из которой можно вывести и другие системы логики, включая классическую аристотелеву логику модусов), также установил изоморфность алгебры логики теории вероятностей: согласно определению, теория вероятностей есть булева алгебра с переменной нормой, изменяющейся от 0 до 1 (где 0 - ложь, 1 - истина, 1/2 - неопределённость). Именно в процессе изменения нормы увеличивается полнота и ценность информации, создаются условия для её накопления. Поэтому, кстати, столь большое внимание уделяется генераторам случайных чисел.

Литература

1. Н.П.Сергеев, Н.П.Вашкевич "Основы вычислительной техники", М.: Высш.шк., 1988
2. И.С.Потёмкин "Функциональные узлы цифровой автоматики", М.: Энергоатомиздат, 1988
3. Толковый словарь по вычислительным системам (Dictionary of Computing) - М.: Машиностроение, 1990. ISBN 5-217-00617-X
4. В.И.Першиков, В.М.Савинков "Толковый словарь по информатике". - М: Финансы и статистика, 1991. ISBN 5-279-00367-0
5. Ф.Л.Бауэр, Г.Гооз "Информатика. Вводный курс", в 2-х ч. Пер. с нем. - М.: Мир, 1990. ISBN 5-03-002099-3 (рус.)
6. Д.Э.Кнут "Искусство программирования", тт.1-3, 3-е изд.: Пер. с англ. - М.: Издательский дом "Вильямс", 2000. ISBN 5-8459-0080-8 (рус.)

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU