Понятия нормальных форм (ДНФ,КНФ,СДНФ,СКНФ)

Понятия нормальных форм (ДНФ,КНФ,СДНФ,СКНФ)

 

Выполнил: Латухин Роман

Логической ( булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

 

Болевая функция

Определение ДНФ и КНФ

Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид где каждая формула - это элементарная конъюнкция. называется совершенной ДНФ, если в каждую из ее конъюнкций входят все переменных из Аналогично, формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций, т.е. , где каждая формула Dj (j=1,...,r) - это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую Dj входят все n переменных из

 

Формы нормальных функций

Дизъюнктивная нормальная форма (ДНФ) — представляет собой логическую сумму отдельных логических произведений аргументов взятых с инверсией или без нее.

Примером ДНФ является выражение:

 

 

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

Примером КНФ является следующее выражение:

 

x — логическая функция;

a2, a1, a0 — аргументы.

 

Примеры ДНФ,КНФ

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

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

 

Совершенная нормальная форма

Пример СДНФ:

 

 

Пример СКНФ:

 

Примеры СДНФ, СНКФ

Совершенная дизъюнктивная нормальная форма (СДНФ) отвечает следующим требованиям:

 

1) в ней нет двух одинаковых  элементарных конъюнкций;

 

2) ни одна элементарная конъюнкция  не содержит двух одинаковых  переменных;

 

3) ни одна элементарная конъюнкция  не содержит переменную вместе  с ее инверсией;

 

4) все конъюнкции имеют один  и тот же ранг.

 

СДНФ

 

1. Удобство получения.
2. Однозначность представления в этой форме любой ПФ.
3. Простота преобразований и упрощений.

 

  
СКНФ

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

Задана функция

 Надо преобразовать её в СДНФ.

 

Преобразование СКНФ И СДНФ

 

x3	x2	x1			a		b		x3	y
0	0	0	1	1	1	0	1	0	0	1
0	0	1	1	1	1	0	1	0	0	1
0	1	0	0	1	0	1	0	1	0	0
0	1	1	0	1	0	1	1	0	0	0
1	0	0	1	0	0	1	1	0	0	0
1	0	1	1	0	0	1	1	0	0	0
1	1	0	0	0	1	0	0	1	1	0
1	1	1	0	0	1	0	1	0	0	1

Второй способ преобразования функций общего вида в СДНФ (СКНФ) является аналитическим. Он связан с использованием следующих формул преобразования.

 

Преобразование СКНФ И СДНФ