2.4. Функционально-полные системы функций

алгебры логики

Логические выражения, с помощью которых представляются дискретные устройства могут содержать любые функции одного и двух аргументов (2.1) и (2.2). В этом случае для построения электрических схем необходимо выполнить техническую реализацию всех функций алгебры логики, входящих в логические выражения. Задача технической реализации всех функций алгебры логики является достаточно сложной и дорогостоящей. Избавиться от этой сложной задачи позволяют функционально-полные системы функций алгебры логики.

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

• отрицание «НЕ»,

• конъюнкцию «И»,

• дизъюнкцию «ИЛИ».

Этот состав функций «И», «ИЛИ», «НЕ» является основным функционально-полным набором функций алгебры логики.

При построении электрических схем дискретных устройств достаточно широко используются еще два функционально-полных набора, каждый из которых содержит только одну функций «И-НЕ» либо «ИЛИ-НЕ».

Таким образом, в дальнейшем будем использовать следующие три функционально-полных набора:

1. «И», «ИЛИ», «НЕ»;

2. «И-НЕ»;

3. «ИЛИ-НЕ».

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

Для представления любого логического выражения любым функционально-полным набором необходимо сначала это выражение представить функционально полным набором «И», «ИЛИ», «НЕ» используя таблицу 1.6., а затем используя закон двойного отрицания и закон инверсии заданное выражение можно представить функционально-полным набором «И-НЕ» либо «ИЛИ-НЕ». Функционально-полные наборы называют базисами.

Пример 2.5. Представить логическое выражение ~базисом «И», «ИЛИ», «НЕ».

Для этого согласно таблице 1.6. сначала избавимся от операции неравнозначности, а затем от операции равнозначности. В результате получим:

~.

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

Для представления этого логического выражения базисом «И-НЕ» необходимо избавиться от операции ИЛИ (логического сложения). Для этого воспользуется сначала законом двойного отрицания и получим:

~.

По закону инверсии опустим нижнюю черту двойного отрицания на аргумент

~.

Таким образом в базисе «И-НЕ» присутствуют только две операции «И» (логическое умножение) и отрицание, которые реализуются одним логическим элементом.

Аналогично выполняется представление данного логического выражения базисом «ИЛИ-НЕ». Для этого необходимо избавиться от операции логического умножения.

~

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

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

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

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

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

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

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

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.

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

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

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

.

Полученная СДНФ совпадает с СДНФ примера 5.2.

Контрольные вопросы

1. Представить и пояснить тождества алгебры логики.

2. Представить и пояснить законы алгебры логики.

3. Доказать закон склеивания.

4. Доказать соотношения, вытекающие из теоремы разложения.

5. Что представляет собой функционально-полный набор функций алгебры логики?

6. Назвать возможные функционально-полные наборы (базисы) ФАЛ.

7. Дать определение ДНФ.

8. Что представляет собой элементарная конъюнкция?

9. Дать определение СДНФ.

10. Что представляет собой конституента единицы?

11. Какие существуют способы представления ДНФ в СДНФ?

12. Решить примеры упрощения логических выражений используя законы и тождества ФАЛ, а также соотношения, вытекающие из теоремы разложения

1. Решить пример представления заданных ФАЛ функционильно-полными наборами «И», «ИЛИ», «НЕ»; «И-НЕ»; «ИЛИ-НЕ»

13. Решить примеры представления заданных функций сначала в виде ДНФ, а затем в виде СДНФ