Воробьёвы

(-:

№17. Про что нам не рассказывают в школах. Булева алгебра

КОЛОНКА РЕДАКТОРА

Братья!! Это NYRON вам пишет :((

У меня для вас две новости. Одна хорошая и одна плохая.

Плохая: простудифилис косит наши ряды. Двое из команды HI-TECH лежат в больнице. Еще двое - в таком же состоянии валяются дома...

Сегодня я сверстал для вас новую статью by Хемуль Советикус. Читайте, вникайте.

Cтатья нужная. Тем более - единственная в номере...

А теперь хорошая новость: блин! а ведь все равно - рассылка-то КАЖДОЕ ВОСКРЕСЕНЬЕ ВЫХОДИТ!!!

Уф... а теперь я буду думать, как-бы это мне доползти домой.....

АЛГЕБРА ЛОГИКИ И ЦИФРОВЫЕ КОМПЬЮТЕРЫ

Бредисловие

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

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

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

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

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

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

Для функций от одной переменной может существовать всего четыре различные булевы функции g1, g2, g3 и g4, представленные в следующей таблице:

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

Из таблицы следует, что функции g1 и g4 не зависят от аргумента и являются константами 0 и 1 соответственно, а функция g2 повторяет значение аргумента, т.е. g2=x. Функция g3 называется отрицанием или инверсией переменной 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 вырожденных функций (константы: f0=0 и f15=1, переменные: f3=x1 и f5=x2, инверсии: f12=not x1 и f10=not x2). Остальные функции с их обозначениями приведены ниже:

название выражение через
конъюнкцию, дизъюнкцию
и отрицание
читается как
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)

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

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

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

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

  1. закон двойного отрицания:
    • not not x = x
  2. закон коммутативности (от перестановки аргументов результат не меняется):
    • x1 or x2 = x2 or x1
    • x1 and x2 = x2 and x1
  3. закон ассоциативности (порядка вычислений):
    • x1 or (x2 or x3) = (x1 or x2) or x3
    • x1 and (x2 and x3) = (x1 and x2) and x3
  4. закон дистрибутивности (раскрытия скобок):
    • x1 or (x2 and x3) = (x1 or x2) and (x1 or x3)
    • x1 and (x2 or x3) = (x1 and x2) or (x1 and x3)
  5. правила де Моргана:
    • not (x1 or x2) = not x1 and not x2
    • not (x1 and x2) = not x1 or not x2
  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. закон поглощения:
    • x1 or (x1 and x2) = x1
    • x1 and (x1 or x2) = x1
  2. закон идемпотентности (повторное применение не даёт ничего нового):
    • x or x or ... or x = x
    • x and x and ... and x = x
  3. на основании закона дистрибутивности, а также 7-го и 6-го законов:
    • x1 or (not x1 and x2) = x1 or x2

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

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

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

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

  • not x, x1 and x2
  • not x, x1 or x2
  • x1'x2 (штрих Шеффера)
  • not x1 and not x2 (функция Пирса)
  • x1 xor x2 (сложение по модулю 2), x1 and x2, 1
  • x1 and not x2 (запрет по x2), 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%. В сленгах (например, языке авиадиспетчеров) избыточность ещё выше.

4. Функция сложения по модулю 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.

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

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

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

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

Одна из целей данной статьи - не только познакомить с представлением логики в компьютере, но и дать представление о том, как можно манипулировать логическими объектами. Одна из целей манипуляций - это оптимизация логических выражений, приведение булевых функций к такому виду, которое содержит наименьшее возможное число аргументов и операций над ними. Для примера ниже приведён фрагмент из программы на 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,
иначе если B < A и B < C то наименьшее - B,
иначе если C < A и C < B то наименьшее - C. 

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

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

Таким образом, после оптимизации мы получаем всего три сравнения вместо шести. Более того, хотя в лучшем случае (наименьшее A) оба примера дают одинаковое количество сравнений (два), в худшем случае (наименьшее C) для второго примера мы получаем также два сравнения вместо шести! Замечательный результат.

Пример сокращения, учитывающий особенности натурального ряда:

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

Эта конструкция сокращается до следующей:

    если 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 (студенты) - результат опроса.

    если not (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 рубля

Вариантов сокращения этого разбора несколько. Вот первый вариант с четырьмя ветвями:

    если not (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) переменные зависимы друг от друга:

    если not (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 опросов):

    если not (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):

    если not (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):

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

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

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

Заключение

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

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

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

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

Литература

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

АНОНС!

Анонс... Анонс? Анонс?? АНОНС?!?!