Основы булевой алгебры: True, False, XOR, NOR и логические символы
Все мы любим компьютеры. Они могут делать столько удивительных вещей. За пару десятилетий компьютеры произвели самую настоящую революцию почти во всех аспектах человеческой жизни.
Они могут справляться с задачами различной степени сложности, просто переворачивая нули и единицы. Просто удивительно, как такое простое действие может привести к такому уровню сложности.
Но я уверен, что вы все знаете, что такой сложности нельзя добиться (практически нельзя) простым случайным переворачиванием чисел. Но за этим стоит определенные логические рассуждения. Есть правила, которые определяют, как это все должно происходить. В данной статье мы обсудим эти правила и увидим, как они управляют «мышлением» компьютера.
Что такое булева алгебра?
Это правила, о которых я упоминал выше, описываются некой областью математики, называемой булевой алгеброй.
В своей книге 1854 года британский математик Джордж Буль предложил использовать систематический набор правил для работы со значениями истинности. Эти правила положили математическую основу для работы с логическими высказываниями. А эти основы привели к развитию булевой алгебры.
Для того, чтобы понять, что из себя представляет булева алгебра, сначала мы должны понять сходства и различия между ней и другими формами алгебры.
Алгебра в целом занимается изучением математических символов и операций, которые можно выполнять над этими символами.
Эти символы сами по себе ничего не значат. Они обозначают некую величину. Именно эти величины и придают ценность этим символам, и именно с этими величинами и выполняются операции.
Булева алгебра также имеет дело с символами и правилами, позволяющими выполнять различные операции над этими символами. Разница заключается в том, что эти символы что-то значат.
В случае обычной алгебры символы обозначают действительные числа. А в булевой алгебре они обозначают значения истинности.
На рисунке ниже представлен весь набор действительных чисел. Набор действительных чисел включает натуральные числа (1, 2, 3, 4, …) , положительные целые числа (все натуральные числа и 0 ), целые числа (…, -2, -1, 0, 1, 2, 3, …) и т.д. Обычная алгебра имеет дело со всем этим набором чисел.
Для сравнения, значения истинности состоят из набора, который включает в себя только два значения: True и False. Здесь я хотел бы отметить, что мы можем использовать любые другие символы для обозначения этих значений.
Например, в информатике, как правило, эти значения обозначают через 0 и 1 ( 0 используется в качестве False , 1 – в качестве True ).
Вы также можете сделать это более оригинальным способом, обозначая значения истинности какими-то другими символами, например, кошки и собаки или бананы и апельсины.
Суть здесь в том, что смысл этих значений останется неизменным, как бы вы их не обозначили. Но убедитесь, что вы не меняете символы в процессе выполнения операций.
Теперь вопрос в том, что если ( True и False ), ( 0 и 1 ) – это просто обозначения, то что же они пытаются обозначить?
Смысл, лежащий в основе значений истинности, исходит из области логики, где значения истинности используются для того, чтобы определить, является ли высказывание «Истинным» ( True ) или «Ложным» ( False ). Здесь значения истинности обозначают соответствие высказывания истине, то есть показывают, является ли высказывание истинным или ложным.
Высказывание – это просто некоторое утверждение, что-то вроде «Все кошки милые».
Если приведенное выше высказывание верно, то мы присваиваем ему значение истинности «Истина» ( True ) или «1», в противном случае мы присваиваем ему значение истинности «Ложь» ( False ) или «0».
В цифровой электронике значения истинности используются для обозначения состояний электронных схем «включено» и «выключено». Подробнее об этом мы поговорим позже в этой же статье.
Логические операции и таблицы истинности
Как и в обычной алгебре, в булевой алгебре также можно применять операции к значениям для получения некоторых результатов. Однако эти операции не похожи на операции в обычной алгебре, поскольку, как мы уже упоминали ранее, булева алгебра работает со значениями истинности, а не с действительными числами.
В булевой алгебре есть три основные операции.
OR: OR или «ИЛИ», также известная как дизъюнкция. Эта операция выполняется над двумя логическими переменными. Результатом операции OR будет 0 , если оба операнда равны 0 , иначе будет 1 .
Для того, чтобы более наглядно продемонстрировать принцип работы этой операции, визуализируем ее с помощью таблицы истинности.
Таблицы истинности дают нам хорошее представление о том, как работают логические операции. Также это удобный инструмент для выполнения логических операций.
| Переменная 1 | Переменная 2 | Результат |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
AND: AND или «И», также известная как конъюнкция. Эта операция выполняется над двумя логическими переменными. Результатом операции AND будет 1 , если оба операнда равны 1 , иначе будет 0 . Таблица истинности выглядит следующим образом.
| Переменная 1 | Переменная 2 | Результат |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
NOT: NOT или «НЕ», также известное как отрицание. Эта операция выполняется только над одной переменной. Если значение переменной равно 1 , то результатом этой операции будет 0 , и наоборот, если значение переменной равно 0 , то результатом операции будет 1 .
| Переменная 1 | Результат |
| 0 | 1 |
| 1 | 0 |
Булева алгебра и цифровые схемы
Булева алгебра после своего появления очень долго оставалась одним из тех понятий в математике, которые не имели какого-то значительного практического применения.
В 1930-х годах Клод Шеннон, американский математик, обнаружил, что булеву алгебру можно использовать в схемах, где двоичные переменные могут обозначать сигналы «низкого» и «высокого» напряжения или состояния «включено» и «выключено».
Эта простая идея создания схем с помощью булевой алгебры привела к развитию цифровой электроники, которая внесла большой вклад в разработку схем для компьютеров.
Цифровые схемы реализуют булеву алгебру при помощи логических элементов – схем, обозначающих логическую операцию. Например, элемент OR будет обозначать операцию OR. То же самое относится и к элементам AND и NOT.
Наряду с основными логическими элементами существуют и логические элементы, которые можно создать путем комбинирования основных логических элементов.
NAND: элемент NAND, или «И-НЕ», образован комбинацией элементов NOT и AND. Элемент NAND дает на выходе 0 , если на обоих входах 1 , в противном случае – 1 .
Элемент NAND обладает свойством функциональной полноты. Это означает, что любая логическая функция может быть реализована только с помощью элементов NAND.
| Вход 1 | Вход 2 | Результат |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR: элемент NOR, или «ИЛИ-НЕ», образован комбинацией элементов NOT и OR. Элемент NOR дает на выходе 1 , если на обоих входах 0 , в противном случае – 0 .
Элемент NOR, как и элемент NAND, обладает свойством функциональной полноты. Это означает, что любая логическая функция может быть реализована только с помощью элементов NOR.
| Вход 1 | Вход 2 | Результат |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Большинство цифровых схем построены с использованием элементов NAND и NOR из-за их функциональной полноты, а также из-за простоты изготовления.
Помимо элементов, рассмотренных выше, существуют также особые элементы, которые служат для определенных целей. Вот они:
XOR: элемент XOR, или «исключающее ИЛИ», — это особый тип логических элементов, который дает на выходе 0 , если оба входа равны 0 или 1 , в противном случае – 1 .
| Вход 1 | Вход 2 | Результат |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XNOR: элемент XNOR, или «исключающее ИЛИ-НЕ», — это особый тип логических элементов, который дает на выходе 1 , когда оба входа равны 0 или 1 , в противном случае – 0 .
| Вход 1 | Вход 2 | Результат |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Заключение
Итак, на этом мы можем закончить обсуждение булевой алгебры. Надеюсь, что к текущему моменту у вас сложилась неплохая картина того, что же такое булева алгебра. Это, конечно, далеко не все, что вам следует знать о булевой алгебре. В ней есть множество понятий и деталей, которые мы не обсудили в данной статье.
Лекции / Схемотехника ЭВМ. Лекция 01. Булева Алгебра
Глава 1. Введение в булеву алгебру Логика – это наука о законах и формах мышления, математическая же логика занимается применением формальных математических методов для решения логических задач. В цифровых устройствах чрезвычайно широко используется простейший раздел математической логики – исчисление высказываний или алгебра логики. Алгебру логики часто называют булевой алгеброй в честь английского математика Джорджа Буля, который в 1847 году опубликовал краткую брошюру «Математический анализ логики, сопровождаемый наброском исчисления дедуктивных рассуждений», а в 1854году вышел его основной труд «Исследование законов, на которых основаны математические теории логики и вероятностей». Базовым понятием булевой алгебры является понятие высказывания , под которым понимается любое утверждение, рассматриваемое только с точки зрения его истинности или ложности. В булевой алгебре не существует истинно-ложных или ложно-истинных высказываний. Высказывание можно рассматривать как логическую переменную, которая может принимать различные значения. Например, высказывание «сегодня понедельник» будет истинным в понедельник и ложным во все остальные дни недели. Исчисление высказываний как раз и основано на том, что их можно рассматривать как двоичные переменные, которые могут принимать одно из двух своих значений. Примерами двоичных логических переменных являются разряды чисел, представленных в двоичной системе счисления, замкнутый или разомкнутый контакт, наличие или отсутствие тока в цепи, высокий или низкий потенциал в ка- кой-либо точке схемы и т.п.
Высказывание называется простым , если значение его истинности не зависит от значений истинности других высказываний, и сложным , если значение его истинности зависит от других высказываний. Сложное высказывание можно рассматривать логической функцией, зависящей от простых высказываний и принимающей также два значения (истина, ложь). В свою очередь, сложные высказывания могут служить переменными (аргументами) еще более сложных функций, то есть при построении логических функций справедлив принцип суперпозиции . 1.1. Аксиомы булевой алгебры Булеву алгебру (БА) как математическую структуру представ-
| ляют совокупностью следующих объектов: | |
| БА = , | (1.1) |
где 0 – символ, обозначающий абсолютную ложь (константа «0»), 1 – символ, обозначающий абсолютную истину (константа «1») Примечание: здесь 0 и 1 не цифры, а символы, обозначающие ложь и истину. x i – i-я логическая переменная, от которой зависит какая-либо логическая функция. И – как минимум двухместная (то есть зависящая от двух переменных) логическая операция, определяемая как логическое произведение (другое название – конъюнкция) . Это такое сложное высказывание, которое истинно только в том случае, когда истинны высказывания, от которых оно зависит. В остальных случаях оно ложно. ИЛИ – как минимум двухместная логическая операция, определяемая как логическая сумма (другое название – дизъюнкция ). Это такое сложное высказывание, которое ложно только в том случае, когда
ложны высказывания, от которых оно зависит. В остальных случаях оно истинно. НЕ – одноместная логическая операция, определяемая как логи- ческое отрицание (другое название – инверсия ). = — отношение эквивалентности. Объекты (1.1) булевой алгебры определяются следующими аксиомами: х = 0, если х не равно 1; х = 1, если х не равно 0. (1.2) Аксиома (1.2) утверждает, что в булевой алгебре рассматриваются только двоичные переменные (закон исключенного третьего).
| 0 0 = 0 | 1 + 1 = 1 | |
| а) 0 1 = 1 0 = 0 | (1.3) | |
| б) 1 + 0 = 0 + 1 = 1 | ||
| 1 1 = 1 | 0 + 0 = 0 | |
Аксиомы (1.3, а ) определяют логическую операцию И. В качестве знака операции И, кроме точки, используются следующие знаки: ×, отсутствие знака, &, , Π. Аксиомы (1.3, б ) определяют логическую операцию ИЛИ. В качестве знака операции ИЛИ, кроме +, используются знаки: , Σ.
| = 1 | |||
| 0 | (1.4) | ||
| 1 = 0 | |||
Аксиома (1.4) определяет операцию логического отрицания. Отношение эквивалентности удовлетворяет следующим свой- ствам: — рефлексивности: х = х,
— симметричности: если х 1 = х 2 , то х 2 = х 1 , — транзитивности: если х 1 = х 2 и х 2 = х 3 , то х 1 = х 3 . Из свойств отношения эквивалентности следует принцип подстановки: если х 1 = х 2 , то в любом логическом выражении, содержащим х 1 , вместо него можно подставить х 2 . В результате будет получено эквивалентное выражение. 1.2. Основные законы булевой алгебры С помощью аксиом булевой алгебры можно доказать целый ряд законов методом перебора всех значений переменных. Если закон истинен, то с учетом аксиом (1.2 – 1.4) при подстановке любых значений переменных в обе части выражения, формулирующего закон, должно получиться тождество. Основные законы алгебры логики принято разбивать на три группы. 1. Законы одинарных элементов: а) законы универсального множества:
| x 1 = x | (1.5) | ||
| x + 1 = 1 | |||
| б) законы нулевого множества: | |||
| x 0 = 0 | (1.6) | ||
| x + 0 = x | |||
| 2. Законы отрицания: | |||
| а) закон двойного отрицания: | |||
| = x | (1.7) | ||
| x | |||
б) законы дополнительности:
| x | = 0 | |||
| x | (1.8) | |||
| x + x = 1 | ||||
в) законы двойственности (де Моргана):
| = | 1 + | 0 | |||||||||
| x 1 x 0 | x | x | (1.9) | ||||||||
| x 1 + x 0 = x 1 x 0 | |||||||||||
| 3. Комбинационные законы: | |||||||||||
| а) законы тавтологии (идемпотентности): | |||||||||||
| xxx K x = x | (1.10) | ||||||||||
| x + x +K+ x = x | |||||||||||
Отсюда следует, что булева алгебра является алгеброй без степеней и коэффициентов. б) переместительные законы (коммутативные):
| x x | = x | x | (1.11) | ||
| 1 | 0 | 0 1 | |||
| x 1 + x 0 = x 0 + x 1 | |||||
| в) сочетательные законы (ассоциативные): | |||||
| x 2 x 1 x 0 = ( x 2 x 1 ) x 0 = ( x 2 x 0 ) x 1 + ( x 1 x 0 ) x 2 | (1.12) | ||||
| x 2 + x 1 + x 0 = ( x 2 + x 1 ) + x 0 = ( x 2 + x 0 ) + x 1 = ( x 1 + x ) 0 + x 2 | |||||
| г) распределительные законы (дистрибутивные): | |||||
| первого рода – умножение относительно сложения: | |||||
| x 2 ( x 1 + x 0 ) = x 2 x 1 + x 2 x 0 | (1.13) | ||||
| второго рода – сложение относительно умножения: | |||||
| x 2 + x 1 x 0 = ( x 2 | + x 1 )( x 2 + x 0 ) | (1.14) | |||
В обычной алгебре не действуют законы тавтологии и распределительный закон второго рода. Обратите внимание, что аксиомы (1.3) за-
писаны с учетом закона двойственности. Если в любой строке одного из столбцов произвести взаимную замену 0 на 1 и операций И и ИЛИ, то получим аксиому в этой же строке другого столбца. 1.3. Следствия из основных законов булевой алгебры Прежде чем формулировать важнейшие следствия из основных законов булевой алгебры, рассмотрим некоторые новые понятия. Совокупность конкретных значений логических переменных, от которых зависит булева функция, называется набором логических переменных .
| Если булева функция зависит, например, от трех переменных | x 2 , x 1 |
| и x 0 , тогда x 2 = 0, x 1 = 1, x 0 = 1 является набором. Наборы | могут |
быть представлены различными способами. Указанный выше набор можно представить как x 2 , x 1 , x 0 , где знак инверсии говорит о том, что x 2 = 0 , а отсутствие знака инверсии — x 1 = x 0 = 1 . Тот же набор мож- но представить как 0,1,1 или просто 011. Рассматривая последнее представление как двоичное число, можно записать его в виде десятичного эквивалента 3 = 0 2 2 + 1 2 1 + 1 2 0 . Отсюда видно, что логическим переменным, как и разрядам двоичного числа, можно условно присво- ить арифметические «веса»: для x 0 вес будет 2 0 = 1 , для x 1 − 2 1 = 2 , для x 2 − 2 2 = 4 и т.д. Именно поэтому логические переменные удобно обозначать индексированными буквами, начиная с индекса 0 для младшей переменной, 1 для следующей переменной и т.д. до индекса n- 1, если функция зависит от n переменных. При таком обозначении индекс переменной совпадает с показателем степени основания двоичной сис-
темы счисления, т.е. характеризует вес переменной. Так для переменной x 5 вес будет равен 2 5 = 32 . Если функция алгебры логики зависит от n переменных, то все- го для них существует 2 n наборов, так как добавление одной переменной увеличивает число наборов в два раза. Одна переменная имеет два набора: 0 и 1, две переменные – четыре набора: 0 = 00, 1 = 01, 2 = 10, 3=11 и т.д. Десятичный эквивалент набора логических переменных называется номером набора . Наборы можно рассматривать как двоичные векторы Х i , где i – номер набора, однако надо помнить, они не являются векторами в классическом смысле, так как над ними нельзя выполнять векторные операции. Наборы можно представить в виде вершин n -мерного куба. Это представление здесь рассматриваться не будет. Число переменных, имеющих в наборе значение 1, называется весом набора (не путать с двоичным весом переменных). Вес набора удобно изображать римскими цифрами, так для n = 3 имеем: набор 000 с весом 0; наборы 001, 010, 100 с весом I, наборы 011, 101, 110 с весом II, и набор 111 с весом III. Двум любым наборам, в состав которых входят n переменных, ставится в соответствие целое число, которое называется расстоянием по Хэммингу . Это число совпадает с числом переменных, входящих в наборы различным образом. Расстояние обозначается d ( X i , Xj ) . Так для n = 4 имеем d ( X 1 , X 13 ) = d (0001,1101) = 2 , так как только переменные x 3 и x 2 входят в наборы различным обра- зом. Если d ( X i , X j ) = 1, то наборы называются соседними . Вес на-
бора равен расстоянию по Хэммингу от нулевого набора.
Расстояние по Хэммингу удовлетворяет следующим условиям: d ( X i , X j ) ≥ 0 , d ( X i , X j ) = 0 тогда и только тогда, когда X i = X j , d ( X i , X j ) = d ( X j X i ) , d ( X i , X j ) + d ( X j , X k ) ≥ d ( X i , X k ) . Полезно помнить, что d ( X i ,00 K 0) = n − d ( X i ,11 K 1) , где n – число переменных. Если наборы рассматривать как их десятичные эквиваленты, то для любых двух наборов можно ввести естественную или лексикогра- фическую упорядоченность или отношение порядка ( ≤ ) . Аксиомы отношения порядка: рефлексивность: X i ≤ X i ,
| антисимметричность: | если X i ≤ X j и X j ≤ X i , то |
| X i = X j , | |
| транзитивность: если | X i ≤ X j , а X j ≤ X k , то X i ≤ X k . |
Наиболее простым примером использования отношения полного линейного порядка является естественное расположение наборов пе-
| ременных в таблицах истинности функций алгебры логики. | ||||
| Рассмотрим | два | набора | переменных | |
| X / | = ( x n / − 1 , K , x i / , K , x 0 / ) | и X // | = ( x n // − 1 , K , x i // , K , x 0 // ) , где x i / и | |
| x i // | это одна и та же переменная x i , входящая соответственно в наборы | |||
x 3 x 2 x 1 x 0
| X / и | X // , таких, что удовлетворяется неравенство X i / ≤ X i // | для всех | ||||||
| i , т.е. | x / ≤ x // , x / | ≤ x // , x / | ≤ x // | и т.д. Тогда говорят, что выполнено | ||||
| 0 | 0 | 1 | 1 | 2 | 2 | |||
| отношение | предшествования | X / ≤ X // . Например, для | n = 3: | |||||
| 010 ≤ 110 . | ||||||||
Не все пары наборов находятся в отношении предшествования, например, 010 и 101, наборы одного веса др. Поэтому наборы в отношении предшествования являются лишь частично упорядоченными. Наборы, для которых отношение предшествования не выполняется, называются несравнимыми . Отношение предшествования используется для определения класса монотонных булевых функций. Логическое произведение любого числа переменных из конечного набора n переменных называется элементарным , когда сомножителями в нем являются либо переменные, либо их отрицания. Например, x 3 x 2 x 1 x 0 является элементарным, а ( x 3 + x 2 ) x 0 , x 3 x 2 x 1 x 0 — нет. Количество сомножителей в элементарном произведении назы- вается его рангом r . Так, для r = 4, а для r = 2. Логиче- ское произведение, являющееся функцией всех n переменных, называется конституентой единицы (составляющей единицы). Смысл этого термина будет пояснен позже. Для n переменных существует 2 n конституент единицы, причем на данном конкретном наборе лишь одна конституента единицы будет равна 1, все другие будут равны 0. Два элементарных произведения одинакового ранга r называются соседними , если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной перемен-
ной. Например, элементарные произведения x 2 x 1 x 0 и x 2 x 1 x 0 — сосед- ние, а x 2 x 1 x 0 и x 2 x 1 x 0 нет. Логическая сумма любого числа переменных их конечного набора n переменных называется элементарной , когда слагаемыми в ней являются либо переменные, либо их отрицания. Например, сумма x 3 + x 2 + x 1 + x 0 — элементарная, а суммы x 3 x 2 + x 0 , x 3 + x 2 x 1 + x 0 и x 3 + x 2 + x 1 + x 0 нет. Количество слагаемых в элементарной сумме называется ее рангом r . Так, для x 3 + x 2 + x 1 + x 0 r = 4, а для x 3 + x 0 r = 2. Логическая сумма, являющаяся функцией всех n переменных, называется конституентой нуля (составляющей нуля). Смысл этого термина будет пояс- нен позже. Для n переменных существует 2 n конституент нуля, причем на данном конкретном наборе лишь одна конституента нуля будет равна 0, все остальные будут равны 1. Две элементарные суммы одинакового ранга r называются соседними , если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Напри- мер, суммы x 2 + x 1 + x 0 и x 2 + x 1 + x 0 являются соседними, а x 2 + x 1 + x 0 и x 2 + x 1 + x 0 нет. Сформулируем теперь важнейшие следствия из основных законов булевой алгебры, представив их в виде следующих правил. Правило старшинства операций Пусть требуется определить значение истинности функции y = x 3 x 2 + x 3 x 1 + x 0 на наборе 11 (одиннадцать). Представив деся-
5.1 Булева алгебра
Булева алгебра состоит из множества B= <0,1>вместе с определенными на нем операциями дизъюнкции (V), конъюнкции ( ) и отрицания (~). Действие операций ( V ) и ( ) на символах 0 и 1 показаны в следующих таблицах Действие отрицания на 0 и 1 определяется следующим образом: 0 = 1 и 1 = 0. Переменные, которые могут принимать только два значения 0 и 1, называются булевыми. Тогда для них таблицы, определяющие действия операций p , p q , p q , будут иметь вид Эти таблицы напоминают таблицы истинности логических операций не , или и и . Действительно, мы можем легко трансформировать их в таблицы истинности, возникающие в логике высказываний, заменив булевы переменные р и q на высказывания Р и Q , и используя истинностные значения T и F вместо 1 и 0 соответственно. Таким образом, p заменяется на не P , p q – на P или Q , а p q – на P и Q . Поэтому в контексте булевой алгебры мы будем называть такого сорта таблицы таблицами истинности. Мы можем комбинировать булевы переменные с помощью операций , , ~ , получая булевы выражения так же, как мы строили составные высказывания из более простых, комбинируя их с помощью логических операций. Также как и в алгебре логики, мы полагаем, что два булевых выражения являются эквивалентными, если они имеют одинаковые таблицы истинности. Часто, вместо знаков операций , , ~ используют знаки + , ( умножение ) , ‘ (штрих – отрицание). В этих обозначениях законы алгебры логики, перенесенные на булевы переменные, имеют вид
Для проверки истинности законов булевой алгебры мы должны построить таблицы истинности для выражений левой и правой частей равенств. Пример . Докажем закон дистрибутивности: p ( q + r ) = p q + p r Построим таблицы истинности для левого и правого выражения, а также для промежуточных операндов Поскольку два последних столбца таблицы полностью совпадают, то и соответствующие им булевы выражения совпадают (эквивалентны). □ Схожесть названий и форм законов булевой алгебры и соответствующих законов алгебры логики и алгебры множеств, далеко не случайна. В таблице, приведенной ниже, показано соответствие между булевыми операциями, операторами логики высказываний и операциями над множествами.
| Логические | Операции над | Булевы |
| операторы | множествами | операции |
| не | – | ~,’ |
| или | U | , + |
| и | I | , • |
Чтобы в дальнейшем не обращаться к таблицам истинности при доказательстве эквивалентности булевых выражений, надо один раз убедиться в справедливости законов булевой алгебры и применять их при преобразовании булевых выражений. 3
Пример . Покажем, что булево выражение ( p q ) ( p + q ) эквивалентно p. Здесь удобно использовать кванторы для обозначения булевых операций. Имеем Булевой функцией от n булевых переменных p 1 ,р 2 ,…,p n называется функция f : B n → B . По-другому, результатом вычисления функции f ( p 1 , p 2 . p n ) , аргументы которой могут принимать только два значения 0 и 1, также является 0 или 1. Очевидно, что количество булевых функций n переменных конечно. Например, булевых функций одной переменной существует всего 4. Булевы функции от одной переменной – это отображения множества <0,1>в себя. Их можно рассматривать как унарные операции на множестве <0,1>. В следующей таблице приведены все четыре булевы функции от одной переменной.
| Значение аргумента | ||||||
| Название | Обозначение | 0 | 1 | |||
| функции | функции | |||||
| g 0 (x) | Нуль | 0 | 0 | 0 | ||
| g 1 (x) | Тождественная | x | 0 | 1 | ||
| g 2 (x) | Отрицание | -x,x’ , | x | 1 | 0 | |
| g 3 (x) | Единица | 1 | 1 | 1 | ||
Булевы функции от двух переменных можно рассматривать как бинарные операции на множестве <0,1>. В следующей таблице приведены все шестнадцать булевых функции от двух переменных. Для некоторых функций указаны используемые обозначения и названия.
| Переменная x | 0 | 0 | 1 | 1 | |
| Переменная y | 0 | 1 | 0 | 1 | |
| Название | Обозначение | ||||
| функции | функции | ||||
| Нуль | 0 | 0 | 0 | 0 | 0 |
| Конъюнкция | , | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | ||
| 0 | 0 | 1 | 1 | ||
| 0 | 1 | 0 | 0 | ||
| 0 | 1 | 0 | 1 | ||
| Сложение по | + , | 0 | 1 | 1 | 0 |
| модулю 2 | |||||
| Дизъюнкция | 0 | 1 | 1 | 1 | |
| Стрелка Пирса | ↓ | 1 | 0 | 0 | 0 |
| Эквивалентность | ~ , ≡ | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | ||
| 1 | 0 | 1 | 1 | ||
| 1 | 1 | 0 | 0 | ||
| Импликация | → , , | 1 | 1 | 0 | 1 |
| Штрих Шеффера | | | 1 | 1 | 1 | 0 |
| Единица | 1 | 1 | 1 | 1 | 1 |
Комбинируя перечисленные функции (с помощью суперпозиций), можно строить более сложные булевы функции, в том числе и большего числа переменных. Булевы отрицание, конъюнкция, дизъюнкция, импликация обладают свойствами, подобными тем, которыми обладают соответствующие логические операции. Формулы, содержащие кроме переменных (и скобок), только знаки функций дизъюнкции, конъюнкции и отрицания, будем называть булевыми формулами. Если задана булева функция, например, таблицей истинности, то обычно требуется ее представить с помощью булевых функций двух переменных. Наша ближайшая задача — показать, как произвольную булеву функцию можно представить с помощью бинарных операций , , ~ Рассмотрим булеву функцию m(p,q,r) от трех булевых переменных p,q и r с таблицей истинности, приведенной ниже
Функция m принимает значение 1 только на одном наборе значений аргументов. Такая функция называется минтермом или элементарной конъюнкцией. Ее можно выразить через булевы функции двух переменных следующим образом m ( p , q , r ) = p q r . Выражения такого типа называются элементарной конъюнкцией, если все входящие в него переменные p,q,…,r (или их отрицания) различны. Любой минтерм можно записать в виде элементарной конъюнкции, т.е. как конъюнкцию переменных p i или их отрицаний. Действительно, пусть m(p 1 ,p 2 ,…p r ) — минтерм. Тогда в последнем столбце таблицы истинности функции m будет стоять только одна единица. Возьмем строку таблицы истинности, соответствующую значению 1. Если в этой строке переменная p i =1 , то в элементарной конъюнкции, представляющей функцию m , участвует p i , а если p i =0 , то участвует p i . Например, для минтерма из последней таблицы значения переменных p, q, r равны 0, 1, 1. Это значит, что в элементарную конъюнкцию входят p , q и r , т.е. m ( p , q , r ) = p q r . Используя элементарные конъюнкции, можно записать произвольную булеву функцию как дизъюнкцию минтермов. Например, рассмотрим булеву функцию трех переменных f(р,q,r) с таблицей истинности следующего вида Единицы последнего столбца в этой таблице соответствуют трем минтермам. Запишем их и соединим операцией дизъюнкции 6
Очевидно, в той же форме можно записать булеву функцию с любым числом переменных. Выражение, представляющее булеву функцию как дизъюнкцию минтермов, называется дизъюнктивной нормальной формой (ДНФ). Описанный способ построения формулы по таблице применим к любой функции, не равной тождественно нулю. Т.е. единственной функцией, не имеющей ДНФ, является константа 0. Но ее можно представить булевой формулой p p . Можно также считать, что ДНФ тождественного нуля – это «пустая» дизъюнкция, не содержащая ни одного дизъюнктивного слагаемого. Повторим. Дизъюнктивной нормальной формой (ДНФ) булевой функции называется её представление в виде дизъюнкции некоторых элементарных конъюнкций. Любую булеву функцию можно представить в виде дизъюнкции минтермов. Значит, каждая булева функция может быть выражена через две функции двух аргументов: f 1 ( p , q ) = p q , f 2 ( p , q ) = p q и одной функции одной переменной f ( p ) = p . Множество функций, через которые можно выразить любую булеву функцию, называется полной системой функций.
| Итак, f 1 ,f 2 ,f 3 | — полная система функций. Однако можно ограничиться и | |||||||||||
| меньшим количеством функций. Например, | по закону де | Моргана | ||||||||||
| ( p q ) = | Следовательно p q = | |||||||||||
| . | . | Значит, любую | булеву | |||||||||
| p | q | p | q | |||||||||
функцию можно записать только с помощью двух операций и ~, т.е. < p q , p >— тоже полная система функций. Расплатой за малое количество операций, посредством которых записывается функция, становится громоздкость формул. Пример . Функция НЕ—И (обозначим ее как в алгебре логики через | )
| определяется формулой: | p | q = | p q | . Покажем, что < | >— полная система | ||||||||||||||||||||||||||
| функций. Для | этого | достаточно показать, что каждая из | функций | ||||||||||||||||||||||||||
| , p q , p q | может | быть выражена через НЕ—И . Ввиду закона | |||||||||||||||||||||||||||
| p | |||||||||||||||||||||||||||||
| идемпотентности | = | = p | p | (A) | ||||||||||||||||||||||||||
| p | p p | ||||||||||||||||||||||||||||
| По закону де Моргана | из ( A ) | = ( p | p ) ( q | q ) = ( p | p ) | ( q | q ) | |||||||||||||||||||||||||||
| p q = | = | ||||||||||||||||||||||||||||
| p | q | ||||||||||||||||||||||||||||
| Также | из ( A ) | = ( p | q ) | ( p | q ) | |||||||||||||||||||||||||||
| p q = | = | = | = s | s для s = p | q | ||||||||||||||||||||||||||
| p q | p | q | s | |||||||||||||||||||||||||||
| Таким образом, < | >— действительно полная система операций. | □ | ||||||||||||||||||||||||||||
Двойственной к булевой функции f(x,y,…,z) называется функция f * ( x , y . z ) = f ′ ( x ′ , y ′ . z ′ ) , которая получается отрицанием всех аргументов булевой функции f и последующим отрицанием результата. Из определения видно, что f ** =f . Функция называется самодвойственной , если f * =f . Из приведенной таблицы видно, что тождественная функция и отрицание самодвойственны, а дизъюнкция и конъюнкция – нет. Суперпозицией функций f 1 ,…,f m называется булева функция, полученная с помощью подстановок этих функций друг в друга на места переменных и, возможно, с помощью переименования переменных. Пример . Составить таблицу истинности функции h(x,y)=f 2 (y,y,f 1 (x,y,x)) , где булевы функции трех переменных f 1 и f 2 имеют следующие таблицы истинности Для составления таблицы функции h(х,у) запишем формулу, задающую функцию h(х,у) , выписав под символами переменных все наборы значений, которые эти переменные принимают, а под символами булевых функций выписав значения функций, соответствующие этим наборам. Заключительный столбец, задающий функцию h , обведём двойной рамкой.
| Итак, h(x,y) =(1111). | □ |
1.4. Основы булевой алгебры
Булева алгебра широко используется для описания функционирования некоторых из аппаратных средств компьютера, поскольку компьютер использует двоичную систему счисления, а логические переменные в булевой алгебре также принимают только два значения :истина и ложь. Булева алгебра названа в честь ее разработчика — английского математика 19 века Дж. Буля. Исходным понятием логики высказываний является простое высказывание, которое не определяется через другие понятия, так как является базовым. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание называют истинным, в противном случае – ложным. Так например, высказывание «8 — четное число» является истиной, а высказывание «СПб – столица Российской Федерации» — ложью.
Булева алгебра, называемая также алгеброй логики, оперирует с переменными, например Х и У, которые могут принимать только два значения: «истина» или «ложь», кодируемые посредством двоичных цифр 1 и 0 соответственно. Операции над этими переменными выполняются логическими элементами. Элемент реализует одну из трех основных логических операций: дизъюнкция, конъюнкция, отрицание, а также комбинацию данных операций.
Под логическим элементом компьютера понимают электронную схему, реализующую элементарную логическую функцию. Для кодирования состояний 1 и 0 в логических элементах соответствующие им сигналы представляют одним из двух уровней напряжения, например 2 вольта и 0 вольт. Высокий уровень напряжения соответствует значению 1-“истина”, а низкий – “ложь” . Каждый логический элемент имеет свое условное обозначение, которое определяет выполняемую логическую функцию.
Функционирование логического элемента представляют посредством таблиц истинности, в которых определены все сочетания возможных значений входных и выходных сигналов — результатов операции для каждой из входных комбинаций. Рассмотрим функционирование основных логических схем.
Логическая схема «И». Данная схема выполняет операцию конъюнкции (логическое умножение) двух или более входных сигналов. Представление схемы «И» на два входа Х и У показано на рис. 1.2.
Рис. 1.2. Логическая схема «И»
Таблица истинности данной схемы имеет следующий вид: