Стандартные формы функций алгебры логики

К стандартным формам функций алгебры логики относятся:

- дизъюнктивная нормальная форма (ДНФ),

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

- конъюнктивная нормальная форма (КНФ),

- совершенная конъюнктивная нормальная форма (СКНФ).

Наибольшее применение при синтезе и анализе дискретных устройств находят стандартные формы ДНФ и СДНФ. К этим формам предъявляются следующие требования:

1. Формы должны быть такими, чтобы ими можно было представить любую ФАЛ.

2. Алгоритм представления ФАЛ в этих формах не должен быть сложным.

3. Представленная в любой из указанных форм ФАЛ при необходимости должна легко поддаваться преобразованиям с целью упрощения (сокращению числа аргументов).

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

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

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

1. Путем преобразований (используя таблицу 1.6.) в заданном логическом выражении оставить только операции «И», «ИЛИ», «НЕ».

2. Опустить знаки отрицания непосредственно на аргументы.

3. Раскрыть скобки, если они имеют место.

4. Отбросить лишние аргументы в конъюнкциях согласно закону повторения.

5. Если имеют место одинаковые элементарные конъюнкции, то лишние отбросить.

Пример 2.6.

. Представить заданное логическое выражение в ДНФ.

Решается согласно алгоритма

1. Необходимо избавиться от операции равнозначности, используя таблицу 1.6.

2. Опускаются знаки отрицания непосредственно на аргументы

3. Раскрываются скобки

Лишних аргументов в конъюнкциях и повторяющихся конъюнкций нет.

Совершенной дизъюнкцией нормальной формой функций алгебры логики называется дизъюнкция конституент единицы.

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

в данном случае функция зависит от трех аргументов х ₁ х ₂ х ₃.

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

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

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

Пример 2.7. Преобразовать ДНФ в СДНФ.

Отсюда следует, что для преобразования ДНФ в СДНФ необходимо:

1. Все элементарные конъюнкции ДНФ умножить на тождества с недостающими аргументами.

2. Раскрыть скобки.

3. Отбросить лишние слагаемые (конституэнты единицы).

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

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

Таблица 2.4.

Таблица истинности заданной функции

Наборы аргументов	х ₁ х ₂	Конституэнты единицы
х ₁ х ₂ х ₃
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

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