Представление переключательных функций

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

f _СДНФ = .

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

f _СДНФ = .

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

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

f _СДНФ = .

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

f _СДНФ = .

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

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

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

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

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

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

Пусть переключательная функция f (А, В, С) задана таблицей истинности (табл. 3.5).

Запись этой переключательной функции в СДНФ будет иметь следующий вид:

F _СДНФ /

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

1. Составить макстермы для строк таблицы истинности, на которых функция уравна 0. Если значение переменной (a, b, c) в этой строке равно 1, то в макстерм записывается отрицание этой переменной.

2. Записать конъюнкцию составленных макстермов.

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

F _СКНФ = (a Ú b Ú c) Ù (a Ú b Ú ) Ù (a Ú Ú ) Ù ( Ú Ú ).

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

F _СДНФ = М ₀ Ú М ₁ Ú М ₃ Ú М ₇,

F _СКНФ = m _{2 m 4 m 5 m 6}.

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

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

Покажем переход от ДНФ к СДНФ на примере следующего выражения:

f (a, b, c) = a b Ú c.

Добавление в члены выражений недостающих аргументов (c Ú ) и (a Ú ) приведет к виду:

f (a, b, c) = a b (c Ú ) Ú c (a Ú ) = a b c Ú a b Ú a c Ú c.

Полученная форма является СДНФ.