Алексеев В. Б. - Дискретная математика - Элементарная конъюнкция

Разложение по одной переменной

Это следствие из предыдущей теоремы для 02:37

Теорема о совершенной дизъюнктивной нормальной форме 11:50


Это снова прошлая теорема, но

Из закона де Моргана истинна также

Теорема о совершенной конъюнктивная нормальная форме 23:28

Минимизация СДНФ (СКНФ)

Литерал 28:30

Литералом называется либо переменная, либо отрицание переменной
Т.е. , например — или

Элементарная конъюнкция (дизъюнкция) 29:25

Так называют конъюнкцию (дизъюнкцию) литералов от разных переменных
То есть такие выражения из конъюнкций (дизъюнкций) разных переменных; в них не может быть одновременно и сама переменная, и ее отрицание; все переменные входят в выражение в единичном количестве

Тогда вводим уже более серьезные определения: 30:26

Дизъюнктивная (конъюнктивная) нормальная форма

Так называется дизъюнкция (конъюнкция) различных элементарных дизъюнкций (конъюнкций)

— элементарная дизъюнкция; — элементарная конъюнкция; является как и элементарной конъюнкцией, так и элементарной дизъюнкцией

35:14 Нормальными называют только те формулы, у которых отрицание стоит только над отдельными переменными, а не целыми выражениями

Импликанта ФАЛ 38:13

Элементарная конъюнкция называется импликантой ФАЛ , если

Теорема 1 42:18

Если представлена в виде ДНФ, т.е. , тогда каждая является импликантой ФАЛ

Элементарные конъюнкции, содержащиеся друг в друге 52:01

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

54:11
Простая импликанта ФАЛ 55:24

Так называется элементарная конъюнкция , такая что сама она — импликанта , но она не содержит других импликант ФАЛ , отличных от

Любая импликанта ФАЛ содержит хотя бы одну простую импликанту 58:14

То есть, если у нас , то есть элементарные конъюнкции и являются импликантами . Однако, в них обоих содержится импликанта (притом простая) . Ее можно получить "вычекиванием" из исходных импликант

Сокращенная ДФН 1:03:24

Сокращенной ДНФ ФАЛ называется дизъюнкция всех простых импликант функции

Теорема 2 1:04:54

Сокращенная ДНФ ФАЛ реализует функцию

Interactive Graph
Table Of Contents
Алексеев В. Б. - Дискретная математика - Элементарная конъюнкция
Минимизация СДНФ (СКНФ)