Учеба и наука

• Всего ответов: 1


Валентина
3-й в
411 отзыв
Теорема 5
Любая логическая функция F, за исключением константы нуля, единственным образом представима в СДНФ.
Д-во:
Любая логическая функция характеризуется тем, что на k из 2ⁿ наборах, она принимает значение 1, а на остальных – 0. Конституэнта единицы  равна единице только на одном наборе, а на остальных – нули. Если для каждого из единичных наборов записать конституэнту единицы и объединить эти конституэнты знаком дизъюнкции, то получим логическую функцию, которая принимает единичные значения на тех же k наборах, что и исходная логическая функция. Такое представление логической функции единственно. Действительно, в противном случае должны присутствовать две или более различных конституэнт единицы на одном и том же наборе переменных, что в соответствии со следствием из теоремы 1, исключено. Константа 0 на всех наборах переменных равна 0. Поэтому ее нельзя представить с помощью конституэнт единицы, т.е. в СДНФ.
март 16, 2014 г.
Ответ понравился автору
Лучший ответ по мнению автора