Сокращенные, минимальные и тупиковые формы

Импликанты и имплициенты булевых функций

Приведение к КНФ

Приведение к ДНФ

Приведение логических функций

Дизъюнктивной нормальной формой называется формула, состоящая из дизъюнкции элементарных конъюнкций.

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

Примечание: у одной и той же функции может быть несколько ДНФ.

Приведение к ДНФ производится по следующему алгоритму:

· по правилу де Моргана все отрицания опускаются до переменных;

· раскрываются скобки;

· удаляются лишние конъюнкции и повторения переменных в конъюнкциях;

· с помощью законов 0 и 1 удаляются константы – единицы из конъюнкций, нули из дизъюнкций.

{Пример: Привести к ДНФ следующую логическую функцию двух переменных F (x₁, x₂) = ù (x₁ Ú x₂) (ù x₁ Ú ù x₂).

F (x₁, x₂) = ù (x₁ Ú x₂) (ù x₁ Ú ù x₂) = ù x₁ ù x₂ (ù x₁ Ú ù x₂) =

= ù x₁ ù x₂ ù x₁ Ú ù x₁ ù x₂ ù x₂ = ù x₁ ù x₂ Ú ù x₁ ù x₂ = ù x₁ ù x₂. }

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

Привести функцию к КНФ можно по аналогичному алгоритму как и к ДНФ. Кроме того, любую ДНФ можно привести к КНФ по правилу де Моргана.

Определение: булевая функция G (x₁, …, x_n) называется импликантой логической функции F (x₁, …, x_n), если для любого набора переменных, на котором G (x₁, …, x_n) = 1, справедливо и F (x₁, …, x_n) = 1.

Определение: булевая функция H (x₁, …, x_n) называется имплициентой логической функции F (x₁, …, x_n), если для любого набора переменных, на котором H (x₁, …, x_n) = 0, справедливо и F (x₁, …, x_n) = 0.

Таблица 2.11 – Импликанты функции 3-х переменных

х1 х2 х3	F	G1	G2	G3	G4	G5	G6	G7
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Функция F имеет семь импликант:

СДНФ: F = ù х₁ х₂ х₃ Ú х₁ х₂ ù х₃ Ú х₁ х₂ х₃ = G₇,

G₁ = х₁ х₂ х₃,

G₂ = х₁ х₂ ù х₃ ,

G₃ = х₁ х₂ ù х₃ Ú х₁ х₂ х₃ = х₁ х₂,

G₄ = ù х₁ х₂ х₃ ,

G₅ = ù х₁ х₂ х₃ Ú х₁ х₂ х₃ = х₂ х₃,

G₆ = ù х₁ х₂ х₃ Ú х₁ х₂ ù х₃ .

Определение: импликанта G булевой функции F, являющаяся элементарной конъюнкцией, называется простой импликантой, если никакая часть импликанты G не является импликантой функции F.

В нашем примере простые импликанты G₃ = х₁ х₂ и G₅ = х₂ х₃.

Определение: дизъюнкция любого числа импликант булевой функции F также является импликантой этой функции.

Все выше сказанное касается и имплициент, если мы рассматриваем логическую функцию исходя из СКНФ.

Определение: Любая булевая функция F эквивалентна дизъюнкции своих простых импликант. Такая форма булевой функции называется сокращенной дизъюнктивной нормальной формой.

В нашем случае сокращенная ДНФ: F = G₃ Ú G₅ = х₁ х₂ Ú х₂ х₃.

Определение: сокращенная ДНФ булевой функции называется тупиковой ДНФ, если в ней отсутствуют лишние простые импликанты.

Примечание: булевая функция может иметь несколько тупиковых ДНФ.

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

Примечание: минимальных ДНФ у логической функции также может быть несколько.

Аналогично определяются сокращенные, тупиковые и минимальные конъюнктивные нормальные формы.

Дата добавления: 2014-01-06