Способы представления булевых функций

1 способ Словесное описание функции

2 способ Табличный способ

Первый и второй способы рассмотрены ранее в разделе 3.1.

3 способ Алгебраический способ

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

Пример

Если каждое слагаемое содержит все переменные или их отрицания, имеем первую стандартную форму или совершенную дизъюнктивную нормальную форму.

Пример

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

Пример

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

Переход от таблицы к первой стандартной форме осуществляется следующим образом. Для каждого набора, на котором функция равна единице, записывается элементарное произведение всех переменных, причем если переменная в этом наборе принимает значение 0, то пишется его отрицание. Затем производится логическое сложение этих элементарных произведений. Иногда эту процедуру называют составлением структурной формулы по единицам.

Пример: Таблица 3.7

F_(A,B,C) = A*BC + AB*C + ABC* + ABC (3.1)

Формула (3.1) показывает, что функция F_(A,B,C) = 1 если любое слагаемое в правой части равно 1.

Для перехода ко второй стандартной форме необходимо для каждого набора, на котором функция равна нулю, составить элементарную сумму, причем, если переменная в этом наборе принимает значение 1, то пишется его отрицание. Затем эти элементарные суммы объединяются операцией логического умножения. Иногда такую процедуру называют составлением структурной формулы по нулям.

Для таблицы 3.7 получим:

F_(A,B,C) = (A + B + C) × (A + B + C*) × (A + B* + C) × (A* + B + C) (3.2)