dm_tema_3

3. Алгебра логики 3.4 Нормальные формы булевых функций

Определение

Ïðè m = n элементарная конъюнкция называется конституентой единицы.

Определение

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

Определение

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

3. Алгебра логики 3.4 Нормальные формы булевых функций

Теорема

Любую булеву функцию, кроме константы 0, можно записать в виде ДНФ.

Доказательство.

Справедливо представление булевой функции в виде СДНФ

_

f (x1; : : : ; xn) = x1 1 : : : xn n :

f ( 1;:::;n)=1

3. Алгебра логики 3.4 Нормальные формы булевых функций

Пример

Функция задана таблицей значений

3. Алгебра логики 3.4 Нормальные формы булевых функций

Запишем СДНФ

f (x1; x2; x3) = x1x2x3 _ x1x2x3 _ x1x2x3 _ x1x2x3:

Применяя законы алгебры логики, получим ДНФ

f (x1; x2; x3) = x1x2 _ x1x3:

3. Алгебра логики 3.4 Нормальные формы булевых функций

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

x1 1 _ _ xmm ;

ãäå i 2 f0; 1g.

Элементарная дизъюнкция равна 0 только на наборе значений аргументов x1 = 1; : : : ; xm = m.

Определение

Ïðè m = n элементарная дизъюнкция называется конституентой нуля.

3. Алгебра логики 3.4 Нормальные формы булевых функций

Определение

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

Определение

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

3. Алгебра логики 3.4 Нормальные формы булевых функций

Теорема

Любую булеву функцию, кроме константы 1, можно записать в виде КНФ.

Доказательство.

Справедливо представление в виде СКНФ

;:::; )=0

Пример

f (x1; x2; x3) = (x1 _ x2 _ x3)(x1 _ x2 _ x3)(x1 _ x2 _ x3)(x1 _ x2 _ x3):

3. Алгебра логики 3.4 Нормальные формы булевых функций

Определение

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

Определение

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

3. Алгебра логики 3.4 Нормальные формы булевых функций

Теорема

Любую булеву функцию можно записать в виде СБНФ

Доказательство.

M

f (x1; : : : ; xn) = x1 1 : : : xn n :

f ( 1;:::;n)=1

Пример

f (x1; x2; x3) = x1x2x3 x1x2x3 x1x2x3 x1x2x3:

3. Алгебра логики 3.4 Нормальные формы булевых функций

Функции f; ^; 0; 1g образуют функционально полную систему

функций.

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

x1 x2 = x2 x1; x1(x2 x3) = x1x2 x1x3 x x = 0; x 0 = x; x = 1 x: