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

В результате выполнения любой операции над двоичными числами мы получаем новое двоичное число. Цифровое устройство, выполняющее это преобразование, можно представить, как некий функциональный преобразователь, на входы которого подаются разряды двоичного числа и на выходе также разряды двоичного числа. Можно условиться считать каждый разряд входного двоичного числа аргументом, а вырабатываемое на выходе число – функцией. Поскольку и те и другие в цифровой технике принимают только два возможных значения, то формально представить процедуру преобразования чисел удобно в терминах алгебры логики (Булева алгебра). Все аргументы и функции в этой алгебре принимают только два значения "Истинно" и "Ложно". Если поставить в соответствие истине единицу, а лжи – ноль, то можно в терминах этой алгебры записать любые преобразования, производимые над двоичными числами.

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

1. Эквивалентность (а=b). Смысл логических функций удобно

представлять в виде таблиц истинности. Для функции эквивалентности справедлива следующая таблица истинности, которая читается по строкам:

a	b

2. Инверсия или функция отрицания (не):

a	b

3. Дизъюнкция или операция логического сложения , (или).

Её значение ложно только в том случае, когда ложны все входные переменные.

a	b	y

4. Конъюнкция или логическая операция умножения

, (и). Её значение истинно только в том случае, если истинны все входные переменные.

a	b	y

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

Введем несколько терминов:

1. Конъюнкция нескольких логических переменных, каждая из которых может

однократно входить в эту конъюнкцию без инверсии или с инверсией, называется элементарным произведением.

2. Дизъюнкция нескольких элементарных произведений называется

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

3. Если логическая функция представлена в виде логических произведений

дизъюнкций, в каждой из которых любая из логических переменных встречается только один раз в прямой или инверсной форме, то форма называется нормальной конъюнктивной формой (КНФ).

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

4. Если в состав каждого из сомножителей в качестве слагаемых входят все

логические элементы, то такая форма называется совершенной конъюнктивной нормальной формой (СКНФ).

В следствии дуальности Булевой алгебры, СКНФ и СДНФ записи одной и той же функции выглядят совершенно различно, но в логическом смысле эквивалентны. Кроме того, используя правила преобразования логических функций, можно совершить переход от одной формы записи к другой. Из этих двух форм записи широко используется форма СДНФ, которая позволяет упростить процедуру минимизации логических функций.

Дата добавления: 2014-01-11