ЛОГИЧЕСКИЕ ФУНКЦИИ И АЛГЕБРА ЛОГИКИ (БУЛЕВА АЛГЕБРА)

Логические функции и способы их записи

В устройствах цифровой электроники используются элементы, входные и выходные сигналы которых могут принимать лишь два значения: логической единицы «1» и логического нуля «О». Такие элементы, называемые логи­ческими, осуществляют простейшие операции с такими двоичными числами.

Для описания алгоритмов работы и структуры логичес­ких схем используют простую алгебру логики, или булеву алгебру, называемую по имени разработавшего ее в сере­дине XIX века ирландского математика Д. Буля. В ее ос­нове лежат три основные логические операции: логичес­кое отрицание, или операция НЕ (инверсия), логическое сложение, или операция ИЛИ (дизъюнкция) и логическое умножение, или операция И (конъюнкция).

Операция НЕ над переменной х записывается в виде .

Операция ИЛИ над двумя переменными х и у записы­вается в виде х + у, а операция И — в виде х • у.

Фактически каждая логическая операция задает функ­цию своих аргументов (переменных). Поэтому можно го­ворить о функциях дизъюнкции, конъюнкции и инверсии.

Число аргументов функций дизъюнкции и конъюнк­ции может быть произвольным (больше двух).

Некоторая логическая функция может быть задана в алгебраической форме или в виде таблицы истинности.

Алгебраическая форма, или булево выражение представ­ляет собой формулу, состоящую из логических переменных, связанными операциями И, ИЛИ и НЕ, например:

f(x₁, x₂, x₃)= x_1* x_2* x₃+(x₁₊ x₂) _* (x_1*x₃).

Как и в обычных алгебраических выражениях для за­дания порядка действий используются скобки. Предпола­гается, что выполнение операции И предшествует опера­ции ИЛИ.

Таблицей истинности называется таблица, содержащая все возможные комбинации значений входных перемен­ных и соответствующие им значения логической функции. Taк, для логической функции n переменных таблица ис­тинности содержит 2ⁿ строк и n + 1 столбцов, как показа­но в таблице на рис. 1.

Х1	Х2	-	Хn	f(x1,x2,..,xn)
0		-		f(0,0,...,0)
		-		f(0,0,...,1)
		-		f(1,1,...,1)

Рис. 1

Очевидно, что значение логической функции f(x₁,x₂,..,x_n) в каждой строке будет принимать значение 0 или 1 в зависимости от значений входных логических перемен­ных.

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

Таблицы истинности логический функций И, ИЛИ, НЕ приведены на Рис.2.

Функция И Функция ИЛИ Функция HE

Рис. 2

Построим таблицу истинности (Рис. 3) для выше приведенного булева выражения

f(x₁, x₂, x₃)= x_1* x_2* x₃+(x₁₊ x₂) _* (x_1*x₃).

Рис. 3

Чтобы построить таблицу, нужно вычислить значение функции f(x₁,x₂,x₃) для каждой из восьми комбинаций значений входных переменных.

Tак, например, при х₁=0. х₂ = 0. х₃=0. получим

f(0,0,0) = 0•0•0+(0+0)•(0+0)=0+0•(0+1)=0+0=0

Для x₁=1,x₂=1,x₃=1, получим

f (1,1,1)=1•1•1+(1+1)•(1+1)=1+1•(1+0)=1+1•1=1+1=1.

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

Для представления логической функции F в виде СДНФ необходимо составить сумму (дизъюнкцию) про­изведений (конъюнкций) значений логической функции F_i и минтермов m_i причем число слагаемых n равно чис­лу строк в таблице истинности, т. е.

Минтерм m_i —это логическое произведение всех пере­менных, причем переменные, равные нулю, записывают­ся с инверсией.

Так для таблицы истинности (см. Рис. 3) можно за­писать следующие миитермы:

Следовательно, логическая функция F, заданная табли­цей истинности, имеет следующую СДНФ:

F=m₁•0+m₂•0+m₃•1+m₄•0+m₅•1+m₆•1+m₇•1+m₈•1=

=x_1• x_2• x₃₊ x_1• x_2• x₃₊ x_1• x_2• x₃₊ x_1• x_2• x₃₊ x_1• x_2• x₃

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

Для представления логической функции F в виде СКНФ необходимо составить произведение (конъюнкцию) сумм (дизъюнкций) значений логической функции F_i и макстермов k_i, причем число произведений n равно числу строк в таблице истинности, т. е.

Макстeрм k_i— это логическая сумма всех переменных, причем переменные, равные 1, записываются с инверсией.

Так, для таблицы (см. Рис. 3) можно записать следу­ющие макcтермы:

Следовательно, логическая функция F, заданная табли­цей истинности, описывается следующей СКИФ:

Таким образом, для записи функции в виде СКНФ ис­пользуют следующее правило: следует записать столько конъюнктивных членов, представляющих собой дизъюн­кции (суммы) всех переменных, сколько раз функция при­нимает значение 0, причем переменные, равные единице, записываются с инверсией.

Основы алгебры логики

Рис. 4

Наиболее важные теоремы, отражающие основные соот­ношения алгебры логики, приведены в таблице (Рис. 4).

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

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