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

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

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

Если логическая функция, зависящая от 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-ю переменную, с тождественно истинным выражением . Таких переменных может быть несколько, будет несколько и тождественно истинных выражений. После этого раскрываются скобки и производятся необходимые упрощения.