Логические Функции. Основные понятия двоичной арифметики
Лекция 1.2
Логические Функции
Основные понятия двоичной арифметики
Любая информация (текстовая, звуковая, графическая, видео) для обработки в ЭВМ преобразуется в двоичный код. Один разряд двоичного кода соответствует единице информации и называется битом [Bit]. Группа из 8 двоичных разрядов называется байтом [Byte]. Также в цифровой технике встречается понятие слова [Word], под которым обычно по умолчанию понимается два байта (16 бит). Реже словом называют четыре и более байта, но в таком случае это специально оговаривается.
В ЭВМ информация, представленная двоичными числами, подвергается арифметической и логической обработке. Поэтому все двоичные константы, переменные, сигналы, операции и выражения, используемые в теории цифровых устройств, можно разделить на два типа:
1. логические (одноразрядные);
2. арифметические (многоразрядные).
В основе логических операций, реализуемых с помощью логических элементов (ЛЭ) и схем, лежит специальный математический аппарат – математическая логика и, прежде всего, алгебра логики (Булева алгебра) или вычисления высказываний.
Высказывание – это любое утверждение, о котором можно сказать одно из двух взаимоисключающих утверждений – “ложно” или “истинно”.
Простые логические высказывания могут быть объединены в логические выражения с помощью основных логических операций, отражающих их логические связи.
Проектирование экономичных логических схем осуществляется с помощью специального математического аппарата, содержащего регулярные методы выполнения некоторых важных этапов решения этой задачи. Этот аппарат предложен в середине 19 века английским математиком Джорджем Булем для исчисления высказываний в формальной логике и носит название алгебры Буля или булевой алгебры.
С появлением сложных переключаемых схем булева алгебра легла в основу теории схем, называемых логическими. Впервые возможность применения булевой алгебры для этих целей была показана независимо В. И. Шестаковым (1936 г.) и Клодом Шенноном (1938 г.).
Логическая (булева, двоичная) константа – это константа, которая занимает один разряд (бит) и всегда принимает только одно из двух постоянных значений: “0” (“ложь”) [False] или “1” (“правда”) [True].
В логике константа “0” может соответствовать отсутствию чего-либо (например, то же понятие “ложь” можно понять как “отсутствие правды”), а константа “1” – наличию чего-либо.
Логическая (булева) переменная отличается от константы только тем, что её значение со временем может меняться (т. е. оно не постоянно), причём в одно и то же время она может принимать только одно из двух значений: “0” или “1”.
Логические переменные обычно обозначаются через x, y, z или другие буквы латинского алфавита.
Другое определение логической: переменная х, которая может принимать то или иное значение из набора {0, 1}, называется логической.
Логический сигнал – это физический процесс, соответствующий конкретной логической константе или переменной. Из этого определения следует, что логический сигнал в общем случае может быть как постоянным, так и переменным.
В таком сигнале логическим уровням “0” и “1” соответствуют свои физические уровни в зависимости от способа кодирования (потенциальная, импульсная или смешанная), типа логики (положительная или отрицательная) и значений потенциалов уровней.
Логическая операция – это логическое действие, выполняемое над логическими константами и переменными, а также сигналами.
Результатом логической операции также может быть только одно из двух значений: “0” или “1”.
Логическое выражение – это выражение, составленное из логических констант, переменных, над которыми выполняются определённые логические операции. Результатом логического выражения является одно из двух значений: “0” или “1”.
Арифметические константы, переменные, сигналы, операции и выражения отличаются от логических только тем, что являются многоразрядными и занимают несколько бит, причём эти биты имеют чёткую иерархию: самый левый разряд является старшим, а самый правый – младшим.
Если задано конкретное число разрядов n, то число арифметических констант ограничено и равно N = 2n; если же число бит не оговорено, то количество двоичных чисел считается бесконечным.
Арифметические переменные и сигналы обозначаются через латинские буквы a, b, c и т. д.
Результатом арифметических операций в общем случае также является многоразрядное число, причём во время вычислений могут возникнуть следующие ситуации:
- перенос в старший разряд;
- заём (займ) из старшего разряда;
- ошибка переполнения разрядной сетки и т. д.
Нужно заметить, что даже самые сложные преобразования цифровой информации в конечном счёте сводятся к простейшим операциям над логическими переменными.
Логические функции и операции
Расширение понятия логической функции
Функция f (x1 , x2 , …, xm) логических переменных (аргументов) x1 , x2 , …, xm , которая также как и переменные может принимать значения только из набора {0, 1}, называется логической (переключательной, булевой) функцией [3].
Как и во всей математике, функция по сути также является переменной, значения которой зависят от других переменных (её аргументов).
Логические функции обозначаются обычно через y или F и записываются в виде
y = f (x1 , x2 , …, xm) или F = f (x1 , x2 , …, xm), (2.1)
или в виде отображения
, (2.2)
где E2 = {0, 1} – конечное множество, состоящее из двух элементов 0 и 1; – множество m-мерных векторов, составленных из m логических переменных. Значения этих векторов называются также двоичными наборами (комбинациями).
Таким образом, запись вида (2.2) обозначает, что каждому значению m-мерного вектора из {0, 1}m или соответствующего набора однозначно ставится в соответствие значение y{0, 1}.
Булевы функции определены на конечном множестве аргументов, каждый из которых принимает только два значения: 0 или 1. Поэтому булевы функции можно представить таблицей истинности, в которой перечисляются значения функции для каждого набора значений аргументов.
Несмотря на то, что количество булевых функций от любого заданного числа m логических переменных конечно, их слишком много, чтобы иметь запас преобразователей для любых встретившихся отображений. Поэтому основной задачей теории булевых функций является разработка систематического метода построения сложных функций из более простых.
В таблице истинности, описывающей булеву функцию, имеется k = 2m строк, соответствующих различным наборам значений аргументов. Этим k строкам можно сопоставить 2k различных столбцов, соответствующих различным функциям. Таким образом, число булевых функций N от m переменных с ростом m растёт весьма быстро:
. (2.3)
Множество булевых функций от m аргументов обозначается через Pm , также пишут, что N = | Pm |.
Говорят, что булева функция существенно зависит от переменной xi , если существует такой набор значений , что
.
В этом случае xi называют существенной переменной, в противном случае xi называют несущественной (фиктивной) переменной.
Пример 1. Пусть булевы функции f1(x1 , x2) и f2(x1 , x2) заданы следующими таблицами истинности (табл. 1).
|
Таблица 1
|
|
x1
|
x2
|
f1
|
f2
|
|
0
|
0
|
0
|
1
|
|
0
|
1
|
0
|
1
|
|
1
|
0
|
1
|
0
|
|
1
|
1
|
1
|
0
|
Для этих функций f1(0, 0) = f1(0, 1) = 0 и f1(1, 0) = f1(1, 1) = 1, f2(0, 0) = f2(0, 1) = 1 и f2(1, 0) = f2(1, 1) = 0, поэтому переменная x1 – существенная, а переменная x2 – несущественная. Как видно из таблицы, и , где чёрточка над переменной означает её логическое отрицание.
Две функции могут иметь различные логические выражения, но быть равными. По определению две булевы функции равны (тождественны, эквивалентны), если одна получается из другой введением (или удалением) несущественных переменных. Естественно, у равных функций будут одинаковые таблицы истинности. Поэтому иногда для определения тождественности функций проще выполнить сравнение их таблиц истинности, чем преобразование их логических выражений, по крайней мере первый способ является наиболее достоверным.
Логическая функция называется тривиальной, если она всегда принимает постоянное значение (является константой) или равна одной из своих переменных. В противном случае функция называется нетривиальной.
Тривиальная (т. е. простая, элементарная, примитивная, неоригинальная) функция – это такая функция, понимание которой не требует никаких объяснений.
Логические функции одной переменной
Существует четыре функции от одной логической переменной, т. к. согласно формуле (2.3) .
|
Таблица 2
|
|
x
|
f1
|
f2
|
f3
|
f4
|
|
0
|
0
|
0
|
1
|
1
|
|
1
|
0
|
1
|
0
|
1
|
Таблицы истинности всех четырёх функций одной переменной представлены в табл. 2.
Названия этих функций следующие: f1 = 0 – нуль, f2 = x – тождественная функция, f3 = – логические отрицание (инверсия, функция НЕ), f4 = 1 – единица. Как видно, для функций-констант f1 и f4 переменная x является фиктивной, а для функций f2 и f3 – существенной.
Три из приведённых выше функций являются тривиальными (константы “0” и “1”, а также тождественная функция); только последняя функция НЕ является нетривиальной.
На рис. 1 с помощью батарейки, генерирующей константу “1”, ключа x и лампочки F объясняется смысл тождественной функции и отрицания НЕ.
Рис. 1. Пояснение смысла тождественной функции (а)
и отрицания НЕ (б, в)
Из рис. 1, а видно, что когда ключ разомкнут (x = 0), цепь также разомкнута и лампочка не горит (F = 0); при замыкании ключа (x = 1) цепь замыкается, по ней начинает протекать ток и лампочка загорается (F = 1).
Иллюстрация операции НЕ требует небольшого усложнения схемы. В схеме на рис. 1, б использовано реле K. При разомкнутом ключе x (x = 0) реле выключено и управляемый им ключ замкнут, поэтому лампочка горит (F = 1). При замыкании ключа x (x = 1) реле срабатывает и размыкает ключ , из-за чего цепь лампочки разрывается, и она не будет гореть (F = 0).
Более простое объяснение смысла операции НЕ показано на рис. 1, в, где используется пара связанных ключей. При разомкнутом ключе x (x = 0) ключ наоборот замкнут, и лампочка горит (F = 1). При замыкании ключа x (x = 1) ключ размыкается, поэтому лампочка перестаёт гореть (F = 0).
Логические функции двух, трёх и более переменных
Количество функций двух переменных , а для трёх переменных имеем уже функций.
Таблицы истинности всех шестнадцати булевых функций двух переменных представлены в табл. 3.
Таблица 3
|
x1
|
x2
|
f1
|
f2
|
f3
|
f4
|
f5
|
f6
|
f7
|
f8
|
f9
|
f10
|
f11
|
f12
|
f13
|
f14
|
f15
|
f16
|
|
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
|
|
Фиктивные переменные
|
x1
x2
|
|
|
x2
|
|
x1
|
|
|
|
|
x1
|
|
x2
|
|
|
x1
x2
|
Для каждой функции в четырёх строках таблицы приведены её значения, соответствующие четырём возможным комбинациям аргументов x1 и x2 . В таблице для каждой функции показаны также фиктивные переменные, если они имеются.
Функция f1 называется нулём, а f16 – единицей, как и в случае функций одной переменной. Функции f4 , f6 , f11 и f13 не зависят от одного из аргументов: , , , . Для функций f4 и f13 переменная x1 является существенной, а x2 – несущественной; для функций f6 и f11 – всё наоборот.
Только оставшиеся десять функций являются полноценными нетривиальными функциями двух переменных.
Табл. 3 можно представить и в другом виде, выполнив её транспонирование, результатом чего является табл. 4, где в последнем столбце указаны также обозначения соответствующих логических операций.
Рассмотрим подробнее все нетривиальные функции двух переменных, а для некоторых из них и функции трёх аргументов. Для функций двух переменных дополнительно проведены иллюстрации, поясняющие смысл соответствующих логических операций.
Таблица 4
Функция
|
х1 х2
|
Обозначения
функций
|
|
|
00
|
01
|
10
|
11
|
|
|
f1
|
0
|
0
|
0
|
0
|
“0”
|
|
f2
|
0
|
0
|
0
|
1
|
|
|
f3
|
0
|
0
|
1
|
0
|
|
|
f4
|
0
|
0
|
1
|
1
|
x1
|
|
f5
|
0
|
1
|
0
|
0
|
|
|
f6
|
0
|
1
|
0
|
1
|
x2
|
|
f7
|
0
|
1
|
1
|
0
|
|
|
f8
|
0
|
1
|
1
|
1
|
|
|
f9
|
1
|
0
|
0
|
0
|
|
|
f10
|
1
|
0
|
0
|
1
|
|
|
f11
|
1
|
0
|
1
|
0
|
|
|
f12
|
1
|
0
|
1
|
1
|
|
|
f13
|
1
|
1
|
0
|
0
|
|
|
f14
|
1
|
1
|
0
|
1
|
|
|
f15
|
1
|
1
|
1
|
0
|
|
|
f16
|
1
|
1
|
1
|
1
|
“1”
|
Функция f2(x1, x2) = или или или называется конъюнкцией, логическим умножением или функцией И. Она принимает значение 1 только в том случае, когда все аргументы равны 1 (и x1 = 1, и x2 = 1), а значение 0 – во всех остальных случаях (когда хотя бы одна из переменных будет равна 0).
|
|
|
x1
|
x2
|
F
|
|
x1
|
x2
|
x3
|
F
|
|
|
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
|
|
|
0
|
1
|
0
|
|
0
|
0
|
1
|
0
|
|
|
|
1
|
0
|
0
|
|
0
|
1
|
0
|
0
|
|
|
|
1
|
1
|
1
|
|
0
|
1
|
1
|
0
|
|
|
|
|
|
|
|
1
|
0
|
0
|
0
|
|
|
|
|
|
|
|
1
|
0
|
1
|
0
|
|
|
|
|
|
|
|
1
|
1
|
0
|
0
|
|
|
|
|
|
|
|
1
|
1
|
1
|
1
|
Рис. 2. Логическая функция И
На рис. 2 поясняется смысл операции И. Видно, что по цепи потечёт ток и лампочка загорится (F = 1) только тогда, когда замкнуты оба ключа (и x1 = 1, и x2 = 1).
Функция И трёх и более переменных также принимает значение “1” только при единичных значениях всех её аргументов (и x1 = 1, и x2 = 1, и x3 = 1). Таблица истинности функции И имеет только одну “1” на последней комбинации.
Функция f8(x1, x2) = или называется дизъюнкцией, логическим сложением или функцией ИЛИ. Она принимает значение 1, если хотя бы один из аргументов или все равны 1 (или x1 = 1, или x2 = 1, или x1 = x2 = 1), а значение 0 – только при x1 = x2 = 0. Из рис. 3 видно, что по цепи лампочки потечёт ток и она загорится тогда, когда замкнут хотя бы один из ключей.
|
|
|
x1
|
x2
|
F
|
|
x1
|
x2
|
x3
|
F
|
|
|
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
|
|
|
0
|
1
|
1
|
|
0
|
0
|
1
|
1
|
|
|
|
1
|
0
|
1
|
|
0
|
1
|
0
|
1
|
|
|
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
|
|
|
|
|
|
|
1
|
0
|
0
|
1
|
|
|
|
|
|
|
|
1
|
0
|
1
|
1
|
|
|
|
|
|
|
|
1
|
1
|
0
|
1
|
|
|
|
|
|
|
|
1
|
1
|
1
|
1
|
Рис. 3. Логическая функция ИЛИ
Функция ИЛИ трёх и более переменных также принимает значение “1” при единичном значении любого из аргументов (или
x1 = 1, или x2 = 1, или x3 = 1, или x1 = x2 = x3 = 1). Таблица истинности функции ИЛИ имеет только один “0” на первой комбинации.
Функция f15(x1,x2) = или или или или называется штрихом Шеффера, функцией Шеффера или функцией И-НЕ. Она работает полностью противоположно операции И, поэтому принимает значение 0 только в том случае, когда все аргументы равны 1 (и x1 = 1, и x2 = 1), а значение 1 – в остальных случаях, т. е. когда хотя бы один из аргументов равен 0.
На рис. 4 поясняется смысл операции И-НЕ. Видно, что в цепи лампочки не будет течь ток и она не будет гореть (F = 0) только тогда, когда оба ключа замкнуты (и x1 = 1, и x2 = 1), т. к. при этом реле K срабатывает и размыкает свой ключ. Если же разомкнут хотя бы один из ключей (или x1 = 0, или x2 = 0, или x1 = x2 = 0), то реле не размыкает ключ в цепи лампочки и она горит (F = 1).
|
|
|
x1
|
x2
|
F
|
|
x1
|
x2
|
x3
|
F
|
|
|
|
0
|
0
|
1
|
|
0
|
0
|
0
|
1
|
|
|
|
0
|
1
|
1
|
|
0
|
0
|
1
|
1
|
|
|
|
1
|
0
|
1
|
|
0
|
1
|
0
|
1
|
|
|
|
1
|
1
|
0
|
|
0
|
1
|
1
|
1
|
|
|
|
|
|
|
|
1
|
0
|
0
|
1
|
|
|
|
|
|
|
|
1
|
0
|
1
|
1
|
|
|
|
|
|
|
|
1
|
1
|
0
|
1
|
|
|
|
|
|
|
|
1
|
1
|
1
|
0
|
Рис. 4. Логическая функция И-НЕ
Функция И-НЕ трёх и более переменных также принимает значение “0” только при единичных значениях всех её аргументов (и x1 = 1, и x2 = 1, и x3 = 1). Вообще таблица истинности функции И-НЕ имеет только один “0” на последней комбинации.
Функция f9(x1,x2) = или или называется функцией Пирса, стрелкой Пирса, а также функцией ИЛИ-НЕ. Она принимает значение 0, если хотя бы один из аргументов или все равны 1 (или x1 = 1, или x2 = 1, или x1 = x2 = 1), а значение 1 – только при x1 = x2 = 0. Из рис. 5 видно, что в цепи лампочки не будет течь ток и она не будет гореть (F = 0), если замкнут хотя бы
|
|
|
x1
|
x2
|
F
|
|
x1
|
x2
|
x3
|
F
|
|
|
|
0
|
0
|
1
|
|
0
|
0
|
0
|
1
|
|
|
|
0
|
1
|
0
|
|
0
|
0
|
1
|
0
|
|
|
|
1
|
0
|
0
|
|
0
|
1
|
0
|
0
|
|
|
|
1
|
1
|
0
|
|
0
|
1
|
1
|
0
|
|
|
|
|
|
|
|
1
|
0
|
0
|
0
|
|
|
|
|
|
|
|
1
|
0
|
1
|
0
|
|
|
|
|
|
|
|
1
|
1
|
0
|
0
|
|
|
|
|
|
|
|
1
|
1
|
1
|
0
|
Рис. 5. Логическая функция ИЛИ-НЕ
один из ключей (или x1 = 1, или x2 = 1, или x1 = x2 = 1), т. к. при этом реле K срабатывает и размыкает свой ключ. Если же оба ключа разомкнуты (и x1 = 0, и x2 = 0), то реле не размыкает ключ в цепи лампочки и она горит (F = 1).
Функция ИЛИ-НЕ трёх и более переменных также принимает значение “0” при единичном значении любого из аргументов (или x1 = 1, или x2 = 1, или x3 = 1, или x1 = x2 = x3 = 1). Таблица истинности функции ИЛИ имеет только одну “1” на первой комбинации.
Функция f7(x1,x2) = называется функцией сложения по модулю 2, а также исключающим ИЛИ, кольцевой суммой, нетождественностью, неэквивалентностью, нечётностью. Значения этой функции получаются по правилу суммы по модулю 2: 0 0 = 0, 0 1 = 1, 1 0 = 1, 1 1 = 0. Она принимает значение 1, когда только один из аргументов равен 1 (или только x1 = 1, или только x2 = 1) или когда сумма значений аргументов является нечётным числом, исключая тем самым одинаковые значения аргументов, т. к. при равных значениях переменных функция принимает значение 0.
|
|
|
x1
|
x2
|
F
|
|
x1
|
x2
|
x3
|
F
|
|
|
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
|
|
|
0
|
1
|
1
|
|
0
|
0
|
1
|
1
|
|
|
|
1
|
0
|
1
|
|
0
|
1
|
0
|
1
|
|
|
|
1
|
1
|
0
|
|
0
|
1
|
1
|
0
|
|
|
|
|
|
|
|
1
|
0
|
0
|
1
|
|
|
|
|
|
|
|
1
|
0
|
1
|
0
|
|
|
|
|
|
|
|
1
|
1
|
0
|
0
|
|
|
|
|
|
|
|
1
|
1
|
1
|
1
|
Рис. 6. Логическая функция Исключающее ИЛИ
Из рис. 6 видно, что в цепи лампочки будет течь ток и она будет гореть (F = 1) только тогда, когда переменные x1 и x2 будут иметь различные значения (только в этом случае лампочка будет подключена к батарее). При одинаковых значениях переменных лампочка будет замыкаться сама на себя и не будет гореть (F = 0).
Для трёх и более переменных такая функция будет иметь смысл только функции суммы по модулю 2 (кольцевой суммы) и нечётности. Например, значение функции будет равно 1, если сумма всех значений аргументов есть нечётное число, и 0 – если эта сумма является чётным числом.
Функция f10(x1,x2) = или или показывает равнозначность (эквивалентность, тождественность) аргументов x1, x2 . Она также называется функцией чётности. Эта функция принимает значение 1, только когда оба аргумента равны между собой (или x1 = x2 = 0, или x1 = x2 = 1) или когда сумма значений аргументов является чётным числом, поэтому можно сделать вывод, что она является обратной функцией для исключающего ИЛИ.
|
|
|
x1
|
x2
|
F
|
|
x1
|
x2
|
X3
|
F
|
|
|
|
0
|
0
|
1
|
|
0
|
0
|
0
|
1
|
|
|
|
0
|
1
|
0
|
|
0
|
0
|
1
|
0
|
|
|
|
1
|
0
|
0
|
|
0
|
1
|
0
|
0
|
|
|
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
|
|
|
|
|
|
|
1
|
0
|
0
|
0
|
|
|
|
|
|
|
|
1
|
0
|
1
|
1
|
|
|
|
|
|
|
|
1
|
1
|
0
|
1
|
|
|
|
|
|
|
|
1
|
1
|
1
|
0
|
Рис. 7. Логическая функция равнозначности (чётности)
Для получения схемы функции равнозначности (чётности) можно на схеме на рис. 6 поменять местами контакты любой из переменной, но только одной: либо для x1 , либо для x2 .
Из рис. 7 видно, что в цепи лампочки будет течь ток и она будет гореть (F = 1) только тогда, когда переменные x1 и x2 будут иметь одинаковые значения, т. к. только в этом случае лампочка будет подключена к батарее. При разных значениях переменных лампочка будет замыкаться сама на себя и не будет гореть (F = 0).
Для трёх и более переменных такая функция будет иметь смысл только функции чётности. Например, значение функции будет равно 1, если сумма всех значений аргументов есть чётное число, и 0 – если эта сумма – нечётное число.
Функция f12(x1, x2) = или – функция следования (импликация) от x2 к x1 , которая принимает значение 0 тогда и только тогда, когда x1 = 0, а x2 = 1.
Функция f14(x1, x2) = или – функция следования (импликация) от x1 к x2 , принимающая значение 0 тогда и только тогда, когда x1 = 1, а x2 = 0.
В табл. 5 и 2.6 отражены таблицы истинности этих двух функций-импликаций, которые имеют смысл только для двух аргументов.
Таблица 5 Таблица 6
|
x1
|
x2
|
F
|
|
x1
|
x2
|
F
|
|
0
|
0
|
1
|
|
0
|
0
|
1
|
|
0
|
1
|
0
|
|
0
|
1
|
1
|
|
1
|
0
|
1
|
|
1
|
0
|
0
|
|
1
|
1
|
1
|
|
1
|
1
|
1
|
Импликация Импликация
Функция f3(x1,x2) = или или или называется функцией запрета по x2 и характеризуется тем, что равенство x2 = 1 запрещает функции принимать значение “1” при любых значениях аргумента x1 , обнуляя тем самым функцию.
Функция f5(x1,x2) = или или или называется функцией запрета по x1 , т. к. равенство x1 = 1 запрещает функции принимать значение “1” при любых значениях аргумента x2 .
Таблица 7 Таблица 8
|
x1
|
x2
|
F
|
|
x1
|
x2
|
F
|
|
0
|
0
|
0
|
|
0
|
0
|
0
|
|
0
|
1
|
0
|
|
0
|
1
|
1
|
|
1
|
0
|
1
|
|
1
|
0
|
0
|
|
1
|
1
|
0
|
|
1
|
1
|
0
|
Функция запрета по x2 Функция запрета по x1
Эти две функции запрета, таблицы истинности которых приведены в табл. 7 и 2.8, также существуют только для случая двух переменных.
Приоритет логических операций
Кроме знаков операций, в алгебре Буля применяются знак “=” (равно) и скобки. Знак “равно” указывает, конечно, не количественное равенство, а то, что разделяемые им символы идентичны, поэтому сигналы слева от этого знака всюду можно заменить символами справа от него и наоборот. Например, если y1 = , y2 = , y3 = , а z = y1 + y2 + y3 , то можно записать
z = y1 + y2 + y3 = + + .
Суперпозиция булевых функций может быть записана как математическая формула, которую называют логической формулой.
Скобки, как и в обычной алгебре, применяются для дополнительного указания порядка выполнения (приоритета) операций. Для уменьшения числа скобок используется приоритет операций.
Приоритет (порядок выполнения) логических операций следующий:
- Вычисляются значения выражений внутри скобок;
- Выполняются отрицания над отдельными переменными (НЕ);
- Вычисляются конъюнкции (И, И-НЕ);
- Вычисляются дизъюнкции (ИЛИ, ИЛИ-НЕ);
- Вычисляются суммы по модулю 2 и функции равнозначности;
- Вычисляется импликация.
Заметим, что иногда знак отрицания ставится над целым выражением, не заключённым в скобки; в этом случае отрицание выполняется в последнюю очередь.
Пример 2. Логическая формула
,
с учётом правил приоритета может быть записана так:
.
Базисы и формы представления логических функций
Базис (функционально полный набор) – это множество логических функций, суперпозицией которых можно представить любую логическую формулу, т. е. полная система логических функций.
Базисы могут быть избыточными и минимальными. Например, система функций И, Или, НЕ (булев базис, базис Буля) – избыточный базис, так как при удалении из него некоторых функций (функции ИЛИ или функции И) система остаётся полной.
Минимальными базисами являются системы: 1) И, НЕ; 2) ИЛИ, НЕ; 3) И-НЕ (базис Шеффера); 4) ИЛИ-НЕ (базис Пирса). При удалении из таких базисов любой операции они перестают быть полными системами функций.
Одни и те же преобразования логических переменных можно задать в раз личных формах (базисах). Выбор базиса зависит от простоты реализации той или иной функции с помощью логических операций данной системы функций. Чаще всего используются базисы Шеффера и Пирса, т. к. они содержат только одну операцию, и для реализации сложной схемы нужен только один тип ЛЭ. В развитых сери ях стандартных интегральных схем (ИС) наряду с базовыми ЛЭ обычно имеется и ряд других, выполняющих другие логические операции.
В табл. 9 приведено несколько полезных свойств булевых функций НЕ, И, ИЛИ, формулы перехода между базисами И-НЕ и ИЛИ-НЕ (законы де Моргана), а также формулы перехода от операций импликация, тождественность и сумма по модулю 2 в базис Буля. Все приведённые соотношения можно легко проверить с помощью их таблиц истинности.
Таблица 9
|
№
|
Формулы
булевой алгебры
|
Формулы
в упрощённой записи
|
Название свойства
|
|
1
|
|
|
Коммутативность (перемена мест операндов)
|
|
2
|
|
|
Ассоциативность
(последовательность
выполнения операций)
|
|
3
|
|
|
Дистрибутивность (раскрытие скобок)
|
|
4
|
|
|
Законы исключённого третьего
|
|
5
|
|
|
Законы тождественных операндов
|
|
6
|
|
|
Законы поглощения
|
|
7
|
|
|
Свойства нуля
|
|
8
|
|
|
Свойства единицы
|
|
9
|
|
|
Свойство двойного
отрицания
|
|
10
|
|
|
Законы (формулы)
де Моргана
|
|
11
|
|
|
Свойство импликации
|
|
12
|
|
|
Свойства
эквивалентности
|
|
13
|
|
|
Свойства сложения по модулю два
|
Далее по возможности будем пользоваться упрощёнными обозначениями логических операций.
Докажем некоторые из приведённых свойств:
7. ;
;
12. ; ;
13. ; .
Введём понятие терма.
Терм – это дизъюнкция или конъюнкция любого числа переменных, взятых с отрицанием или без него. В терм в общем случае не обязательно должны входить все переменные, он даже может состоять только из одной переменной.
Термы, состоящие только из одной переменной, взятой с отрицанием или без него, называются первичными термами.
Ранг терма определяется количеством переменных, входящих в данный терм.
Терм в виде конъюнкции переменных, взятых с отрицанием или без него, называется конъюнктивным термом, конституентой единицы (любой такой терм, принимающий значение 1, автоматически приводит к единичному значению функции) или минтермом (для принятия функцией значения 1 требуется минимальное количество единичных термов, а точнее только один). Под минтермом обычно понимается конъюнктивный терм, содержащий все переменные логической функции.
Терм, являющийся дизъюнкцией логических переменных в прямом или инверсном виде, называется дизъюнктивным термом, конституентой нуля (любой такой терм, принимающий значение 0, автоматически приводит к нулевому значению функции) или макстермом (для принятия функцией значения 1 требуется максимальное количество единичных термов, а точнее всех термов). Под макстермом обычно понимается дизъюнктивный терм, содержащий все переменные логической функции.
Теорема 1. Любая логическая функция может быть представлена как суперпозиция только трёх функций: И, ИЛИ и НЕ.
Доказательство данной теоремы основано на лемме о дизъюнктивном разложении.
Лемма. Любая булева функция f (x1 , x2 , …, xm) от m переменных может быть представлена так:
. (2.4)
Действительно, при xi = 0 правая часть этой формулы принимает значение
;
аналогично при xi = 1 правая часть
.
Итак, правая часть формулы (2.4) при всех наборах аргументов совпадает с левой, что доказывает справедливость формулы (2.4).
Разложим функцию f (x1 , x2 , …, xm) последовательно по переменным x1 , x2 , …, xm :
Таким образом, любую булеву функцию можно представить как дизъюнкцию термов, каждый из которых представляет собой конъюнкцию всех переменных (с отрицаниями или без них) и значения этой функции на соответствующем конкретном наборе значений переменных.
Примем для {0, 1} x = при = 0 и x = x при = 1. Тогда окончательная форма представления любой булевой функции будет иметь вид:
. (2.5)
Поскольку значения функции на каждом конкретном наборе равны либо 0, либо 1, то в формуле (2.5) останутся только такие термы, которые соответствуют наборам переменных, на которых функция равна единице:
. (2.6)
Логические Функции. Основные понятия двоичной арифметики