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

Переключательные функции могут быть представлены различными способами. В табличной форме каждому из возможных наборов переменных ставится в соответствие значение функции (0 или 1). Табличный способ показателен и может быть применён для записи функции от любого числа переменных.

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

Нормальные формы.

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

Элементарные конъюнкции (дизъюнкции) - это конъюнкция (дизъюнкция), в которой конъюнктивно (дизъюнктивно) связываются отдельные переменные. Элементарные конъюкции - АС; A̅B; ABC; АB̅СD, а элементарные дизъюнкции - (AvB), (AvC̅); (AvBvC)

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

X_днф=ABvBCvAC̅

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

Х_кнф=(DvE)(EvF)(DvF)

Совершенные нормальные формы.

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

Совершенная дизъюнктивная нормальная форма (СДНФ) представления переключательной функции запись функции X в виде дизъюнкции конъюнкции, для которых значение функции равно "1".

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

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

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

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

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

Пример записи функции в СДНФ.

Имеется заданная таблица истинности. Запишем переключательную функцию в СДНФ для заданной таблицы 2.9

X_СНКФ = A̅B̅C̅vA̅BCvAB̅CvABC̅

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

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

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

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

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

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

X_СНКФ=(AvBvC̅)(AvB̅vC)(A̅vBvC)(A̅vB̅vC̅)