Слыхали детскую байку о том, что у каждого из нас есть таинственный ДВОЙНИК? А ещё, говорят, есть параллельная вселенная, в которой всё точно также, как у нас, но только по другому и совсем наоборот? Давайте сегодня прольём свет на эти удивительные слухи! Недавно я уже делился тем, как объяснял смысл наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) для двух чисел, через кубики или слова. Для болтовни на прогулке это объяснение вполне подходит, но оно не даёт прямых подсказок...

В лекции приводятся определения основных классов булевых функций, а также формулируется теорема Поста о полноте. Класс самодвойственных функций. Пример 1. Используя принцип двойственности, запишем булеву функцию, двойственную заданной булевой функции, расставим в полученной булевой функции скобки, указывающие порядок выполнения действий. Пример 2. Несамодвойственная функция F = (01011001) задана вектором значений. Используя лемму о несамодвойственной функции, под­становкой вместо переменных x, y, z только переменную x и её отрицание получим одну из констант (0 либо 1)...