Основными понятиями булевой алгебры являются понятия логической переменной и логической функции.
Логической переменной называется величина, которая может принимать одно из двух возможных состояний (значений), одно из которых обозначается символом “0”, другое – “1” (для обозначения состояний возможно применение и других символов, например, “Да” и “Нет” и др.). Сами двоичные переменные чаще обозначают символами х 1, х 2,… В силу определения логические переменные можно называть также двоичными переменными.
Логической (булевой) функцией (обычное обозначение – у) называется функция двоичных переменных (аргументов), которая также может принимать одно из двух возможных состояний (значений): “0” или “1”. Значение некоторой логической функции n переменных определяется или задается для каждого набора (сочетания) двоичных переменных. Количество возможных различных наборов, которые могут быть составлены из n аргументов, очевидно, равно . При этом, поскольку сама функция на каждом наборе может принимать значение “0” или “1”, то общее число возможных функций от n переменных равно .
Таким образом, множество состояний (значений), которые могут принимать как аргументы, так и функции, равно двум. Для этих состояний в булевой алгебре определяются отношение эквивалентности, обозначаемое символом равенства (=) и три операции: а) логического сложения (дизъюнкции), б) логического умножения (конъюнкции), в) логического отрицания (инверсии), обозначаемые соответственно символами:
+ или - операция дизъюнкции,
или или & - операция конъюнкции,
- операция инверсии (* - символ аргумента или функции).
Постулативно полагается, что при выполнении перечисленных операций отношения эквивалентности имеют вид:
а) 0 + 0 = 0, б) 0 × 0 = 0, в) = 1,
0 + 1 = 1, 0 × 1 = 0, = 0.
1 + 0 = 1, 1 × 0 = 0,
1 + 1 = 1; 1 × 1 = 1;
На основании постулатов (1) можно вывести следующие соотношения (законы) алгебры логики:
1. Законы одинарных элементов (универсального множества – а), нулевого множества – б), тавтологии – в)):
а) х + 1 = 1, б) х + 0 = х, в) х + х = х,
х × 1 = х; х × 0 = 0; х × х = х.
2. Законы отрицания (двойного отрицания – а), дополнительности – б), двойственности – в)):
а) б) в)
; .
3. Законы абсорбции или поглощения – а) и склеивания – б):
а) б)
Законы двойственности (3, в), называемые также законами деМоргана, были обобщены К. Шенноном на случай произвольного (n) числа аргументов.
Кроме законов, перечисленных выше и не имеющих аналогов в обычной алгебре (алгебре чисел), для алгебры логики справедливы законы обычной алгебры: коммутативные или переместительные, дистрибутивные или распределительные, ассоциативные или сочетательные.
Любая логическая функция у n двоичных переменных может быть задана таблично. Такие таблицы, получившие название таблиц истинности, содержат строк, в которые записываются все возможные двоичные наборы значений аргументов, а также соответствующее каждому из этих наборов значение функции.
Пример 1. Составить таблицу истинности логической функции у равнозначности (эквивалентности) трех двоичных переменных , т.е. функции, которая принимает единичное значение только при совпадении всех трех аргументов, ее образующих.
Решение. Сначала выпишем все возможные наборы (комбинации) трех переменных . Таких наборов, очевидно, 8. Чтобы не ошибиться при перечислении наборов аргументов, нужно сразу приучиться перечислять их единообразно – в виде возрастающей последовательности чисел, представленных в двоичной системе счисления. Для рассматриваемого примера наборы трех переменных нужно перечислить в следующем порядке: 000, 001, 010, 011, 100, 101, 110, 111 – итого восемь двоичных чисел – от 0 до 7.
Номер набора | Двоичные переменные | Логические функции |
х 1 х 2 х 3 | у | |
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
Таблица 1
Далее для каждого набора двоичных переменных определим, исходя из смысла ситуации, соответствующее значение функции. В результате получаем таблицу истинности логической функции "равнозначность трех двоичных переменных" (табл. 1).
Задание логической функции таблицей истинности не всегда удобно. При большом числе двоичных переменных (n ³ 6) табличный способ задания функции становится громоздким и теряет наглядность. Возможен и аналитический способ задания логических функций, который предусматривает запись функции в форме логического выражения, устанавливающего, какие логические операции над аргументами функции должны выполняться и в какой последовательности.
Алгебра логики предполагает возможность образования сложных функций, т.е. функций, аргументы которых являются функциями других двоичных аргументов. Например, если , а и , очевидно, что . Операция замены аргументов одной функции другими функциями называется суперпозицией функций. Эта операция дает возможность выразить сложную логическую функцию через более простые (элементарные).
Приведем описание некоторых, имеющих большое значение в цифровой технике, элементарных логических функций и ЛЭ, реализующих эти функции.
Функция “отрицание” – это функция одного аргумента (другие названия функции: инверсия, логическая связь НЕ). Аналитическая форма задания этой функции:
где - логическая функция, - аргумент.
Электронный ЛЭ, реализующий функцию “Отрицание” в виде определенных уровней электрических сигналов, называют инвертором или ЛЭ “НЕ”. Инвертор на схемах изображается, как показано на рис. 1, а. Вход ЛЭ слева, выход – справа. На выходной линии, в месте соединения ее с прямоугольником, изображается кружок – символ инверсии. На языке цифровой техники инверсия означает, что выходной сигнал (у) противоположен входному (х). Сказанное иллюстрирует рис. 1, б, на котором приведены временные диаграммы инвертора.
Рисунок 5- Инвертор: а) условное изображение;
б) временные диаграммы; в) таблица истинности
Функция “конъюнкция” – это функция двух или большего числа аргументов (другие названия функции: логическое умножение, логическая связь И). Аналитическая форма задания функции двух аргумент и :
или или .
Функция “конъюнкция” равна 1 тогда и только тогда, когда все ее аргументы равны 1. ЛЭ, реализующий функцию “Конъюнкция” называют конъюнктором или ЛЭ “И”. На рис. 6 приведены: условное графическое изображение двухвходового (а) и трехвходового (б) конъюнкторов; временные диаграммы (в) и таблица истинности (г) двухвходового конъюнктора.
ЛЭ “И” часто используют для управления потоком информации. При этом на один из его входов поступают сигналы, несущие некоторую информацию, а на другой – управляющий сигнал: пропустить информацию – 1, не пропустить – 0. ЛЭ “И”, используемый таким образом, называют вентиль.
Рисунок 6 - Конюнкторы
Функция “дизъюнкция” – это функция двух или большего числа аргументов (другие названия функции: логическое сложение, логическая связь ИЛИ). Функция равна 1, если хотя бы один из ее аргументов равен 1 (рис. 2, в). Обозначение функции “Дизъюнкция”:
или .
ЛЭ, реализующий функцию “дизъюнкция”, называют дизъюнктором или ЛЭ “ИЛИ”. Условное изображение и временные диаграммы ЛЭ “ИЛИ” приведены на рис. 7
Рисунок 7 – Дизъюнктер или ЛЭ «ИЛИ»
Функция “штрих Шеффера” (другое название функции – логическая связь “И-НЕ”) – это функция двух или большего числа аргументов. Таблица истинности функции “И-НЕ” представлена на рис. 8, б. Легко видеть, что это инверсия функции “И”, т.е. отрицание конъюнкции. Функция равна 1, если равен 0 хотя бы один из ее аргументов, функция равна 0 при равенстве всех аргументов 1.
Обозначение функции “И-НЕ”: .
Условное изображение ЛЭ, реализующего функцию “штрих Шеффера”, приведено на рис. 8, а.
Рисунок 8 – ЛЭ «И-НЕ» или функция «штрих Шеффера»