24. Разложение булевых функций в сднф и скнф.

Определение. Функцияотnаргументовназывается булевой функцией (или функцией алгебры логики), если каждому наборуона ставит в соответствие число.

Для задания булевых функциймы будем использовать таблицы, векторы, формулы и графики. Примем следующее обозначение:– это множество всех набо­ров, где.

Теорема.Каждую булеву функциюможно представить в виде дизъюнктивной формы:, где 1 ≤ m ≤ n.

Определение.Совершенная дизъюнктивная нормальная форма (СДНФ) функции – логическая сумма (дизъюнкция) нескольких слагаемых, каждое из которых является конъюнкциейnмножителей:.

С помощью СДНФ можно задать любую булеву функцию, кроме тождественного нуля.

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

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

Пример.Функция «голосования»всегда принимает то значение, которое принимает большинство её аргументов.

x y z	f (x,y,z)
0 0 0	0
0 0 1	0
0 1 0	0
0 1 1	1
1 0 0	0
1 0 1	1
1 1 0	1
1 1 1	1

Перейдя к табличному заданию этой функции, выделим те наборы, на которых она обращается в единицу. Это наборы (011), (101), (110) и (111). СДНФ функции «голосования» будет иметь четыре слагаемых:

.

На остальных четырех наборах функция h(x,y,z) обращается в ноль. СКНФ функции «голосования» будет иметь четыре множителя:

.

25. Минимизация днф и кнф методом эквивалентных преобразований.

Определение. Функцияотnаргументовназывается булевой функцией (или функцией алгебры логики), если каждому наборуона ставит в соответствие число.

Для задания булевых функциймы будем использовать таблицы, векторы, формулы и графики. Примем следующее обозначение:– это множество всех набо­ров, где.

Теорема.Каждую булеву функциюможно представить в виде дизъюнктивной формы:, где 1 ≤ m ≤ n.

Определение.Совершенная дизъюнктивная нормальная форма (СДНФ) функции – логическая сумма (дизъюнкция) нескольких слагаемых, каждое из которых является конъюнкциейnмножителей:.

С помощью СДНФ можно задать любую булеву функцию, кроме тождественного нуля.

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

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

Утверждение.ДНФ и КНФ отличаются от СДНФ и СКНФ тем, что в них не все переменные обязательно входят в каждое слагаемое (множитель).

Пример.Функция «голосования»всегда принимает то значение, которое принимает большинство её аргументов.

x y z	f (x,y,z)
0 0 0	0
0 0 1	0
0 1 0	0
0 1 1	1
1 0 0	0
1 0 1	1
1 1 0	1
1 1 1	1

Перейдя к табличному заданию этой функции, выделим те наборы, на которых она обращается в единицу. Это наборы (011), (101), (110) и (111). СДНФ функции «голосования» будет иметь четыре слагаемых:

.

На остальных четырех наборах функция h(x,y,z) обращается в ноль. СКНФ функции «голосования» будет иметь четыре множителя:

.

Минимальные ДНФ и КНФ можно получить путем преобразования совершенных ДНФ и КНФ с помощью тождеств.

СДНФ функции «голосования» можно привести к более простой дизъюнктивной форме: .

СКНФ функции «голосования» можно привести к более простой конъюнктивной форме, состоящей из трех множителей:.