Булевы функции_КНФ_ДНФ

1.

Перепишите в конспект
Скриншот вышлите на почту
[email protected]
P.S.: символ отрицания пишите над буквой в виде черты
19.04.2020
1

2.

Булевы функции
Преподаватель ОГБПОУ «СПК»
Дмитриева С.А.
19.04.2020
2

3.

Понятие булевых функций
• Значение формулы алгебры высказываний полностью
зависит от значения входящих в нее высказываний, ее
значение вычисляется однозначно. Поэтому формула
алгебры высказываний является функцией, значение
которой полностью определяется входящими в нее
элементарными высказываниями.
• В математической логике мы будем использовать
только логические переменные, которые принимают
значения либо 0 (ложь), либо 1 (истина).
• Функции, которые определены на этих переменных и
принимают значения 0 или 1, также
называются логическими или булевыми.
19.04.2020
3

4.

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

5.

Нормальная форма — свойство отношения в реляционной
модели данных, характеризующее его с точки зрения
избыточности, потенциально приводящей к логически
ошибочным результатам выборки или изменения данных.
Нормальная форма определяется как совокупность
требований, которым должно удовлетворять отношение.
Литерал — запись в исходном коде компьютерной
программы, представляющая собой фиксированное
значение. Литералами также называют представление
значения некоторого типа данных. Литералы представляют
собой константы, включаемые непосредственно в текст
программы.
19.04.2020
5

6.

П р и м е р ы
19.04.2020
6

7.

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

8.

Пример построения ДНФ
19.04.2020
8

9.

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

10.

Примеры и контрпример построения КНФ
19.04.2020
10

11.

Построение КНФ
Алгоритм построения КНФ
19.04.2020
11

12.

Пример построения КНФ
19.04.2020
12