Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - Вопрос 18

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 18


Функциональная полнота систем логических функций Выше рассмотрены два способа задания логических функций - табличный и формульный. Таблица истинности задает функцию непосредственно как соответствие между двоичными наборами и значениями функции на этих наборах. Этот способ универсален, т.е. пригоден для любой функции, однако громоздок. Формула -гораздо более компактный способ задания функции, однако она задает функцию через другие функции. Поэтому для любой системы функций E возникает естественный вопрос: всякая ли логическая функция представима формулой над E ? Иными словами, любую ли логическую функцию можно записать с помощью логических операций, входящих в систему E? Выше при построения по таблице истинности СовДНФ и СовКНФ было показано, что любая логическая формула может быть представима как булева, т.е. в системе Eo={-,/\,\/}, а алгебра, построенная таким образом, называется булевой алгеброй. Единственная функция, не имеющая СовДНФ, - это константа О. Но она может быть представлена булевой формулой 0 =х/\neх (закон противоречия). Не имеет СовКНФ константа 1, но ее можно записать как 1=х/\neх (закон исключенного третьего). Покажем, как решать этот вопрос для произвольной системы 2. Система E называется функциональна полной системой, если любая логическая функция может быть представима формулой над E, т.е. записана как комбинация функций из Е. Из сказанного следует, что система Eo={-,/\,\/} функционально полна. Функционально подпои будет и любая система £, через функции которой можно выразить отрицание, конъюнкцию и дизъюнкцию. Действительно, для любой логической функции f представляющую ее формулу над £ можно построить так: взять булеву формулу ддя f и все булевы операции в ней заменить формулами над E, представляющими эти операоди. Аналогичио доказывается и более общее утверждение: если все функции функционально полной системы S* представины формулами над системой E, то Е также функционально полна. В этом случае говорят, что E сводится к E*. Рассмотрим ряд примеров.

Пример 3.14. Доказать, что система E1={-,/\,} функционально полна. Решение. Действительно, из закона де Моргана и двойного отрицания следует, что в E1 недостающая до Eo дизъюнкция выражается через конъюнкцию и отрицание: x1vx2=NE(nex1/\x2) (3.22) т.е. может быть заменена на комбинацию конъюнкций и отрицаний, составляющих систему £/. В частности, в ней, как нетрудно убедиться, булева формула f1=x1/\ х2vnex2/\(x3vх1) (3.23) перейдет в формулу f1= NE(х1/\ x2)/\NE(nex2/\NE(nex3/\nex4)). Эта формула уже не может быть представлена комбинационной схемой, состоящей из последовательно и параллельно соединенных нормально разомкнутых и нормально замкнутых контактов.

Обсудить вопрос в студенческом форуме

 

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