Алгоритм построения ДНФ

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

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

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

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

6. СДНФ, СКНФ. Способы приведения к СДНФ, СКНФ.

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

Совершенная Конъюнктивная Нормальная Форма — это такая КНФ, которая удовлетворяет трём условиям:

• в ней нет одинаковых элементарных дизъюнкций
• в каждой дизъюнкции нет одинаковых пропозициональных букв
• каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

Способы приведения к СДНФ.

1. Составить таблицу истинности для данной функции;

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

3. Соединить все элементарные конъюнкции дизъюнкцией.

Способ приведения к СКНФ.

1. Составить таблицу истинности для данной функции;

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

3. Соединить все элементарные дизъюнкции конъюнкцией.

7. Законы логики

• Закон тождества
• Закон исключённого третьего
• Закон противоречия
• Закон достаточного основания
• Законы де Моргана
• Законы дедуктивных умозаключений
• Закон Клавия
• Законы деления

8.Упрощение формул логики с помощью равносильных преобразований.

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

9.Булевы векторы. Понятие булевой функции.

Булева функция— это функция, все аргументы и все значения которой принадле-жат множеству.

10.Представление булевой функции в виде МДНФ методом Квайна.

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

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

11.Операция двоичного сложения. Многочлен Жегалкина.

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

13. Важнейшие замкнутые классы.

Замкнутый класс в теории булевых функций — такое множество P функций алгебры логики, любая функция, которую можно выразить формулой с использованием функций множества P, снова входит в это же множество.

14..Основные понятия логики предикатов.

n-местный предикат – это отображение , где , а , элементы которого понимаются как «ложь» и «истина». Множество называется областью определения предиката и обозначается .

0-местный предикат называется высказыванием.

Подмножество области определения, состоящее из таких наборов переменных, при которых предикат принимает значение 1, называется областью истинности предиката и обозначается нами .

15. Логические операции над предикатами

Так как предикат принимает логические значения, то можно составлять логические формулы, переменными в которых будут предикаты. Эти формулы также будут предикатами. Часто их называют сложными предикатами.

16. Кванторные операции над предикатами

Квантор (все-)общности

Квантор существования

Квантор существования по переменной x ₁

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

17. Бинарные отношения. Свойства бинарных отношений.

В математике бинарным отношением называется подмножество декартова произведения двух множеств