26.27. Формы представления переключательных функций. Сднф. Скнф

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

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

Если логическая функция, зависящая от n переменных, записана в виде дизъюнкции элементарных конъюнкций ЭК₁ЭК₂...ЭК_r и хотя бы одна ЭК не содержит все n переменных, то такая форма задания называется дизъюнктивной нормальной формой (ДНФ). ДНФ – дизъюнкция конечного множества попарно различных элементарных конъюнкций.

Например: f(аbсd)=аbd.

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

• выполнить все операции инверсии, применяемые к логическим выражениям (группе переменных);

• раскрыть все скобки;

• в полученном выражении произвести все упрощения.

Например:

f(х₁х₂х₃)==

===

==.

Получили ДНФ функции f(х₁х₂х₃).

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

Пусть задана таблица истинности функции сложения по модулю 2 () (табл. 32).

Таблица 32

Таблица истинности

Тогда z(аb)= bа, т.е. это СДНФ.

Первый член СДНФ соответствует строке 01, второй – строке 10.

Элементарные конъюнкции, входящие в СДНФ функции, называются конституентами единицы (или минтермами). Конституента единицы обращается в 1 (истинна) на единственном наборе значений переменных. Так, подстановка входного набора 01 (база аb) обращает в 1 конституенту b (1=1). Если считать выражениеz(аb) уравнением, то наборы 01, 10 – его решения.

От СДНФ легко перейти к номерам рабочих наборов в различных системах. Так: z(аb)01₂10₂1₁₀2₁₀.

Аналогично по СДНФ можно получить рабочие наборы, считая остальные запрещенными: z(аb)=1,2[0,3].

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

Для преобразования ДНФ в СДНФ можно выполнить конъюнкцию каждой элементарной конъюнкции, не содержащую i-ю переменную, с тождественно истинным выражением . Таких переменных может быть несколько, будет несколько и тождественно истинных выражений. После этого раскрываются скобки и производятся необходимые упрощения.

Пример.

Получили СДНФ.

Имеется способ получения СДНФ из ДНФ с использованием обобщенного кода, в котором для обозначения недостающих переменных в соответствующих позициях используются знаки «–» (или «~» – «тильда»), а для остальных – символы 0,1.

Пример.

Функцию представим в виде: 00-0-1.

Тогда, подставляя вместо «–» всевозможные комбинации 0,1, получим:

Таким образом, получили номера 000, 001, 011, которые соответствуют членам СДНФ.

СДНФ переключательной функции, тождественно равной 1 (тождественно истинной), содержит 2ⁿ констинтуэнт (n – число переменных).

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

Выражение вида , содержащее множество попарно различных переменных или их инверсий, называется элементарной дизъюнкцией (ЭД).

Если переключательная функция, зависящая от n переменных, записана в виде конъюнкции элементарных дизъюнкций ЭД₁·ЭД₂·...·ЭД_r и хотя бы одна ЭД не содержит все n переменных, то такая форма задания называется конъюнктивной нормальной формой (КНФ). КНФ – конъюнкция конечного множества попарно различных элементарных дизъюнкций.

Например: f(аbсd)=а(с)(bd).

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

• заданную функцию инверсировать, получить ДНФ инверсной функции;

• ДНФ инверсной функции инверсировать еще раз, получить тождественную исходной функцию в КНФ;

• на каждом этапе следует производить необходимые упрощения.

Пример.

f(х₁х₂х₃)=;

(х₁х₂х₃)==

=;

(х₁х₂х₃)=.

Получили КНФ.

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

Пример.

f(х₁х₂х₃)=

=

=

Если все элементарные дизъюнкции, входящие в КНФ, содержат все n переменных, от которых зависит функция, то такая форма называется совершенной конъюнктивной нормальной (СКНФ).

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

Так, для функции сложения по модулю 2 (табл. 32) СКНФ имеет вид:

.

Элементарные дизъюнкции, входящие в СКНФ функции, называются конституентами нуля (макстермами).

Конституента нуля обращается в нуль на единственном наборе переменных, который является запрещенным (нулевым) набором функции. Например, для функции сложения по модулю 2 конституента нуля (аb) обращается в 0 на наборе 00, а конституента нуля – на наборе 11.

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

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

Для преобразования КНФ в СКНФ можно выполнить дизъюнкцию каждой элементарной дизъюнкции, не содержащей i-ю переменную, с тождественно ложным выражением . Таких недостающих переменных может быть несколько; тогда надо добавлять соответствующие тождественно истинные выражения. Затем применяется распределительный закон и производятся необходимые упрощения.

Например:

Соответствующие запрещенные наборы: 100, 110, 101, 111, 010 (база х₁х₂х₃).

Получим СДНФ и СКНФ ПФ, заданной десятичным номером №174₁₀.

Таблица истинности ПФ №174₁₀ показана в табл. 33

Таблица 33

Таблица истинности

СДНФ – совершенная дизъюнктивная нормальная форма:

СКНФ – совершенная конъюнктивная нормальная форма: