Информатика и вычислительная техника

         

Аналитические формы представления логических функций


Табличное представление логических функций является весьма наглядным. Однако при большом числе n переменных (аргументов) оно становится очень громоздким и практически необозримым. Если для n = 2 число различных логических функций равно 16, то для n = 3 это число возрастает до 256.

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

Широкое распространение получили так называемые нормальные формы представления логических функций. В их основе лежат понятия элементарных дизъюнкций и конъюнкций.

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

FКНФ = (x ? y) & (x ? y).

110

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

PДНФ = х & y ? х & y.

Одну и ту же логическую функцию можно представить различными ДНФ и КНФ. Однозначность представления логических функций возможна при записи их в совершенных нормальных формах.

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

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

  • 1) по каждому набору двоичных переменных, при котором логическая функция принимает значение 1, составить элементарные конъюнкции;
  • 2) в элементарные конъюнкции записать без инверсии переменные, заданные единицей в соответствующем наборе, и с инверсией - переменные, заданные нулем;
  • 3) соединить элементарные конъюнкции знаком дизъюнкции.
    Конъюнктивная совершенная нормальная форма (КСНФ) образуется


конъюнкцией так называемых конституент 0 или макстермов. При этом макстермы представляют собой элементарные дизъюнкции переменных на тех наборах, на которых функция равна 0. Те переменные, которые в данном наборе равны 1 , записываются в макстерме с отрицанием (инверсией), а равные 0 - без отрицания (инверсии).

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

1) по каждому набору двоичных переменных, при котором данная функция принимает значение 0, составить элементарные дизъюнкции;

2) в элементарные дизъюнкции записать без инверсии переменные, заданные нулем в соответствующем наборе, а с инверсией - переменные, заданные единицей;

3) элементарные дизъюнкции соединить знаком конъюнкции.

Любая логическая функция, кроме функции, тождественно равной 0 (f ? 0), представима в ДСНФ, а любая функция, кроме f = 1 , представима в КСНФ.

111

Дизъюнкцией минтермов или конъюнкцией макстермов можно компактно представить, соответственно, в ДСНФ или КСНФ все 16 логических функций двух аргументов, как показано в табл. 5.2.

Таблица 5.2

ДСНФ и КСНФ логических функций двух аргументов

Таким образом, с использованием ДСНФ и КСНФ любая логическая функция представляется аналитическим выражением, в котором участвуют аргументы, связанные логическими операциями отрицания, дизъюнкции и конъюнкции.

112

110 :: 111 :: 112 :: Содержание


Содержание раздела