.02 Булевы функции. Таблицы истинности. Булев куб.
Ошибка.
Попробуйте повторить позже
a) Из теоремы о существовании СДНФ вывести, что любую (точнее, почти любую) булеву функцию можно разложить в виде
где 
.
Такой вид называется совершенной конъюнктивной нормальной формой функции 
.
b) Представить в СКНФ булеву функцию 
, заданную формулой
a) Поступим аналогично с СДНФ. Во-первых, очевидно, что если функция 
равна нулю только на
наборе 
, то
(просто-напросто левая и правая части равенства равны нулю одновременно, и равны единице
одновременно).
Но тогда верен и более общий факт. 
Любую
функцию 
можно представить в
виде
где 
.
Почему любая стоит в кавычках? Из этого правила есть ровно одно исключение. По аналогии с тем,
как в СДНФ не получится выразить тождественно нулевую функцию, в нашем случае, то есть в
СКНФ, не получится выразить тождественно единичную функцию. Все остальные - можно.
2. Как же выразить эту функцию
в СКНФ? Надо для начала составить её таблицу истинности.
А далее, чтобы выписать СКНФ нашей функции, мы должны просто написать конъюнкцию по всем
наборам, на которых 
равна 0 всевозможных дизъюнкций переменных или их отрицаний, причем в
дизъюнкцию переменная входит с отрицанием, если соответствующая координата в соответствующем
наборе равна единице. Получаем:
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
