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

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

Например: у = bc + c + a для логической функции трех логических элементов. Здесь (bc,c, a) элементарная конъюнкция (это конъюнкция любого числа отдельных независимых переменных, входящих в данную дизъюнкцию с инверсией или без нее не более одного раза).

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

Например: у = a(a+)(+)(+) для логической функции трех логических переменных. Здесь (a+,++) элементарная дизъюнкция (это дизъюнкция любого числа отдельных независимых переменных, входящих в данную дизъюнкцию с инверсией или без нее не более одного раза).

Количество переменных в элементарной конъюнкции (дизъюнкции) определяет ее ранг.

Для каждой функции может существовать несколько дизъюнктивных и конъюнктивных нормальных форм (равносильных друг к другу).

Инверсия любой функции записанной в ДНФ (КНФ) приводит к форме записи в КНФ (ДНФ).

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

Например: логических переменных (n) – 3. Тогда конституенты единицы это: abc, bc, b.

В общем случае, если считать единицу логической функцией n переменных, то ее можно разложить на 2ⁿ конституент (составляющих), т.е. на 2ⁿ дизъюнктивно связанных элементарных конъюнкций n-го ранга, т.к. количество различных наборов значений n-двоичных переменных равно 2ⁿ.

Пример: n=2, тогда

1 =

Конституент единицы для некоторого набора значений 0 и 1 строится следующим способом. Каждая переменная в него входит без инверсии, если значения этой переменной в данном наборе = 1, или с инверсией, если значение этой переменной в данном наборе = 0.

Например, набору значений 00111 соответствует конституент единицы Таким образом, конституент единицы как функцияn переменных равняется 1 только на одном соответствующем ему наборе значений. На всех остальных наборах данный конституент единицы = 0.

Конституентом 0 для данного числа логических переменных называется дизъюнкция всех переменных взятых по одной с инверсией или без нее.

Для трех переменных конституент нуля: a+b+c; ;.

Конституент 0 для некоторого набора значений 0 и 1 строится следующим образом. Каждая переменная в него входит без инверсии, если значение этой переменной в данном наборе = 1. Например, набору значений 00111 соответствует конституент 0 – .

Аналогично каждый конституент нуля как функция n переменных равен 0 только на одном соответствующем ему наборе значений логических переменных. На всех остальных наборах данный конституент 0 = 1.

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

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

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

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

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

1. все операции выразить через операции конъюнкции, дизъюнкции и инверсии;

2. избавиться от инверсии над целыми выражениями, перейдя к форме, в которой имеются инверсии только отдельных переменных;

3. раскрыть скобки, применяя закон дистрибутивности;

4. привести конъюнкции (дизъюнкции) к элементарным.

От любой ДНФ можно перейти к СДНФ при помощи равносильных преобразований. Для этого необходимо:

1. ввести недостающие переменные в каждую конъюнкцию умножением ее на равносильность вида , где а – недостающая переменная;

2. раскрыть скобки, применяя коммуникативный закон (ab = ba);

3. избавиться от повторяющихся конъюнкций на основе правила ().

Пример:

–функция в виде ДНФ.

–функция в виде СДНФ.

Переход от КНФ к СКНФ осуществляется аналогично. Необходимо:

1. ввести недостающие переменные в каждую дизъюнкцию, используя закон противоречия (a – недостающая переменная);

2. произвести преобразования, применяя второй закон дистрибутивности ;

3. избавиться от повторяющихся дизъюнкций на основании правила а=а

Например

Теперь в выражении делаем подстановку А =, получаем. Для А=. Подставляем это выражение в исходное:и опять применяем закон дистрибутивности.

Получаем: .

Переход от СДНФ к СКНФ может быть реализован следующим образом:

1. найти не вошедшие в СДНФ конъюнкции;

2. составить функцию как дизъюнкцию этих конъюнкций;

3. взять инверсию от этой функции.

Например:

- определяем конституенты 1 не вошедшие в исходную СДНФ:

- промежуточная функция как дизъюнкция конституентов1:

- получаем искомую СКНФ:

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