Лекция по дискретной математике №4. Принцип двойственности. СДНФ, СКНФ. Полином Жигалкина.

• В лекции рассматривается принцип двойственности для булевых функций.  

• Двойственная функция задается формулой, в которой отрицание берется над функцией и над каждой переменной.  

• Если функция задана вектором значений, то можно получить вектор значений двойственной функции, переписав вектор значений справа налево и меняя каждый элемент на противоположный.  

• Этот алгоритм легко распространяется на функции переменных.  

• Дизъюнкция, конъюнкция, эквивалентность, сложение по модулю два, штрих шефер и стрелка пирса имеют двойственные функции.  

• Если функция двойственная к другой функции, то двойственное к этой функции будет также двойственной к исходной функции.  

• Если функция задана формулой, то двойственную функцию можно найти, применяя определение двойственности.  

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

• Принцип основан на замене каждой функции на двойственную к ней и восстановлении скобок и связок.  

• Каждая булева функция, за исключением тождественно равной нулю, может быть задана формулой вида СДНФ.  

• Формула представляет собой дизъюнкцию конъюнкций, где конъюнкции включают все переменные в разных степенях (либо переменные, либо переменные с отрицанием).  

• Примеры: функция двух переменных с заданным столбцом значений и функция трех переменных.  

• В видео объясняется, как записать функцию в виде СДНФ (совершенной дизъюнктивной нормальной формы).  

• Для этого отмечаются наборы или строки, на которых функция равна единице, и записываются элементарные конъюнкции, в которые входят все переменные.  

• Затем все элементарные конъюнкции перемножаются, и получается формула, которая является СДНФ.  

• Также объясняется, как записать функцию в виде СКНФ (совершенной конъюнктивной нормальной формы).  

• Для этого отмечаются наборы или строки, на которых функция равна нулю, и записываются дизъюнкции, в которые входят все переменные.  

• Затем все дизъюнкции перемножаются, и получается формула, которая является СКНФ.  

• Доказывается, что любую булеву функцию можно задать формулой вида: .  

• Для этого рассматривается произвольный набор значений переменных и сравнивается значение функции, реализуемое этой формулой, с значением функции на этом наборе.  

• В результате получается, что функция может быть записана в виде СДНФ или СКНФ.  

• Булеву функцию можно представить в виде дизъюнкции по всем наборам, на которых функция равна единице, и конъюнкции по всем наборам, на которых функция равна нулю.  

• Доказательство основано на разложении функции по переменным и использовании теоремы о разложении.  

• Булеву функцию можно представить как конъюнкцию от дизъюнкции по всем наборам, на которых функция равна нулю.  

• Доказательство основано на использовании двойственной функции и принципа двойственности.  

• Элементарная конъюнкция ранга р - конъюнкция вида икс- один в степени сигма- один, икс- два в степени сигма- два, и т.д.  

• Дизъюнктивная нормальная форма - дизъюнкция различных элементарных конъюнкций.  

• Плену жигалкина - сумма по модулю 2 различных элементарных конъюнкций, в которых нет отрицания переменных.  

• Вводится понятие степени полинома Жигалкина, которая определяется как наибольшая из рангов элементарных конъюнкций, входящих в полином.  

• Для первого полинома Жигалкина степень равна трем, так как он содержит три элементарные конъюнкции ранга три.  

• Доказывается, что любую булеву функцию можно представить в виде полинома Жигалкина.  

• Рассматриваются дополнительные тождества, которые используются для преобразования функций в виде полинома Жигалкина.  

• Утверждается, что представление функции в виде полинома Жигалкина является единственным.  

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

• Функция может быть представлена в виде полинома Жигалкина, и это представление является единственным.  

• Полином Жигалкина - это сумма по модулю два элементарных конъюнкций, где коэффициенты равны 0 или 1.  

• Метод основан на получении канонического полинома Жигалкина и нахождении коэффициентов, используя равенство функции и полинома на каждом наборе значений булевых векторов.  

• Примером является функция от двух переменных, где коэффициенты найдены из равенства функции и полинома на каждом наборе значений.  

• Опускаем единичные коэффициенты и нулевые слагаемые, получаем полином Жигалкина в виде суммы элементарных конъюнкций с коэффициентами 0 или 1.