Штрих Шеффера

Стрелка Пирса

— отрицание

— конъюнкция

— дизъюнкция — импликация

-(X∨Y), 1+X+Y+XY;

Штрих Шеффера

— отрицание

— дизъюнкция

— конъюнкция

— константа 1

-(X*Y), 1+XY;

2. ДНФ и КНФ. Теоремы о совершенных ДНФ и КНФ.

Конъюнкция нескольких литералов называется элементарным конъюнктом

Примеры -

Элементарный конъюнкт называется полным, если он содержит все рассматриваемые переменные.

Дизъюнкция нескольких литералов называется элементарным дизъюнктом

Примеры -

Элементарный дизъюнкт называется полным, если он содержит все рассматриваемые переменные.

Дизъюнкция нескольких элементарных конъюнктов называется дизъюнктивной нормальной формой (ДНФ). Пример -

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

Конъюнкция нескольких элементарных дизъюнктов называется конъюнктивной нормальной формой (КНФ). Пример -

Конъюнкция нескольких полных элементарных дизъюнктов называется совершенной конъюнктивной нормальной формой (СКНФ).

Теорема. Для любой булевой функции f: B^n → B имеет место

Доказательство. Пусть f(x1, x2,..., xn) = 1. Тогда при σ1 = x1, σ2 = x2,..., σn = xn имеем

Поэтому правая часть (п.ч.) равна 1.

Пусть п.ч. равна 1. Тогда для некоторого (σ1, σ2,... σn) ∈ B^n, такого, что f(σ1, σ2,... σn) = 1, имеем

Значит для каждого значение , а это возможно только при xi = σi. Таким образом, f(x1, x2,..., xn) = 1.

Теорема. Для любой булевой функции f: B^n → B имеет место

Доказательство. Пусть f(x1, x2,..., xn) = 0. Тогда при σ1 = x1, σ2 = x2,..., σn = xn имеем Поэтому правая часть (п.ч.) равна 0.

Пусть п.ч. равна 0. Тогда для некоторого (σ1, σ2,... σn) ∈ B^n, такого, что f(σ1, σ2,... σn) = 0, имеем . Значит для каждого значение , а это возможно только при xi = σi. Таким образом, f(x1, x2,..., xn) = 0.

3. Минимальные ДНФ. Импликанты и простые импликанты, сокращенные ДНФ и тупиковые ДНФ. Алгоритм нахождения минимальной ДНФ.

ДНФ наименьшего веса называется минимальной. Весом ДНФ называется количество литералов,

входящих в ДНФ.

Элементарный конъюнкт называется импликантом булевой функции, если , для всех x1, x2,..., xn ∈ B.

Если K присутствует в ДНФ функции f, то K является импликантом f.

Импликант функции f называется простым импликантом, если ни одна его собственная часть не

является импликантом f.

Теорема. Каждый элементарный конъюнкт в минимальной ДНФ для булевой функции f является простым импликантом.

Доказательство. Пусть является минимальной ДНФ. Докажем, что K1 (например) является простым импликантом. Пусть не так: существует импликант K’, являющийся собственной частью K1. Тогда то есть получили ДНФ, с меньшим весом чем минимальная. Противоречие.

Следствие. Пусть P — множество всех простых импликантов булевой функции f. Тогда .

Доказательство. Пусть минимальная ДНФ. Тогда

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

Пусть P — множество всех простых импликантов f. ДНФ вида где S ⊆ P, называется тупиковой ДНФ, если для имеем

Теорема. Минимальная ДНФ является тупиковой.

Доказательство. Пусть минимальная ДНФ для f. Ясно, что вес будет еще меньше при