Основы булевой математики

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

Y=f(X0, X1, ..., Xn-1).

Наиболее наглядно функция преобразования характеризуется таблицей, в строках которой каждой комбинации входных переменных X соответствует значение переменной Y. Её называют таблицей истинности.

Таблица 1

Основными логическими функциями являются логическое умножение (конъюнкция), логическое сложение (дизъюнкция) и логическое отрицание (инверсия). При логическом умножении входные переменные (две или более) соединяют союзом И (AND). Такую операцию обозначают /\ или знаком умножения (*). Функция Y1=X1*X2 принимает значение логической 1 только при равенстве 1 всех входных переменных. Если хоть одна переменная равна 0, то и выходная функция равна 0 (таблица 1).

При логическом сложении два и более высказываний соединяют союзом ИЛИ (OR). Обозначают эту операцию символом \/ или знаком сложения (+) Таблица истинности для дизъюнкции имеет такой вид.

Таблица 2

Высказывание (Х1+Х2) истинно, если истинно хоть одно из высказываний входящих в ее состав.

При логическом отрицании функция НЕ (NOT) значение выходной функции противоположно входной переменной (табл. 3). Эту операцию обозначают Х (читается "НЕ X").

Таблица 3

Конъюнкцией, дизъюнкцией и инверсией можно выразить любые другие более сложные операции над высказываниями. Поэтому система функций Y1=Х1*Х2, Y2=Х1+Х2 и Y3=-Х обладает функциональной полнотой. В качестве примера рассмотрим несколько функций, реализуемых с помощью элементов вычислительной техники. Равнозначностью (или эквивалентной) называют функцию Y двух аргументов X1 и Х2, которая принимает значениеY=1 при Х1=Х2=1 или при Х1=Х2=0. При различных значениях аргументов Х1≠Х2 значение функции Y=0. Можно показать, что функция Y имеет вид Y=X1*Х2+(-Х1)*(-Х2), что подтверждается подстановкой в выражение соответствующих значений аргументов. Неравнозначностью называют функцию Y двух аргументов X1 и Х2, принимающую значение 1 при Х1≠Х2, и значение 0 при Х1=Х2=0 или,. при Х1=Х2=1. В этом случае будем иметь Y=Х1*Х2+Х1*Х2. Операцию неравнозначности чаще называют суммированием по модулю 2 и обозначают Y=Х1(+)Х2. Существуют также функционально полные системы, состоящие лишь из одной функция. К ним, в частности, относятся функции И-НЕ (Y= -(Х1*Х2) и ИЛИ-НЕ (Y=-(Х1+Х2)), широко используемые при моделировании цифровых устройств. Приведем таблицу истинности функций И-НЕ и ИЛИ-НЕ двух переменных X1 и Х2.

Таблица 4

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