31. Понятие полинома логической функции(полинома Жегалкина). Понятие линейной логической функции.

Полином Жегалкина — полином(многочлен) над  , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики.

Полином Жегалкина представляет собой сумму по модулю два (операция Исключающее ИЛИ) произведений неинвертированных переменных, а также (если необходимо) константы 1. Формально полином Жегалкина можно представить в виде

или в более формализованном виде как

Примеры полиномов Жегалкина:

Термин «линейная функция», или, точнее, «линейная однородная функция», часто применяется для линейного отображения векторного пространства   над некоторым полем   в это поле, то есть для такого отображения  , что для любых элементов   и любых   справедливо равенство

причём в этом случае вместо термина «линейная функция» используются также термины линейный функционал и линейная форма — также означающие линейную однородную функцию определённого класса.

32. Понятие дизъюнктивной нормальной формой логической функции. Понятие мнимальной дизъюнктивной нормальной формы логической функции. Понятие простого импликанта. Понятие сокращенной дизъюнктивной нормальной формы логической функции.

Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.^[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем. Алгоритм построения ДНФ

1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

33. Минимизация логических функций методом Квайна.

Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.^[1][2][3] Преобразование функции можно разделить на два этапа:

• на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;

• на втором этапе — переход от сокращённой формы к минимальной форме.

Представим, что заданная функция   представлена в СДНФ. Для осуществления первого этапа преобразование проходит два действия:

1. Операция склеивания;

2. Операция поглощения.

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

Потом выполняется операция поглощения. Она основана на равенстве   (член   поглощает выражение  ). Вследствие этого действия из логического выражения вычёркиваются все члены, поглощаемые другими переменными, результаты которых получены в операции склеивания. Обе операции первого этапа могут выполняться до тех пор, пока это может быть осуществимо.