44. Импликанты, простые импликанты. Сокращенные, тупиковые, минимальные нормальные формы. Алгоритм Квайна построения мднф.

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

Формула φ(x₁,…,x_n) называется импликантой формулы ψ(x₁,…,x_n), если φ – элементарное произведение и , т.е для соответствующих формулам φ и ψ функций f_φ и f_ψ справедливо неравенство f_φ ≤f_ψ. Формула φ(x₁,…,x_n) называется импликантой функции f, если φ – импликанта СДНФ, представляющей f. Импликанта формулы ψ называется простой, если после отбрасывания любой литеры из φ не получается формула, являющаяся импликантой формулы ψ.

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

Любая булева функция, не являющаяся константой 0, представима в виде СкДНФ. СкДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из СкДНФ удалить все лишние импликанты, то получается Тупиковая ДНФ. Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает МинимальнуюДНФ.

Рассмотрим метод Квайна для нахождения МДНФ. Определим три операции:

1. операция полного склеивания

2. операция неполного склеивания

3. операция элементарного поглощения

Теорема Квайна: Если исходя из СДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то получится СкДНФ, т.е дизъюнкция всех простых импликант.

Для получения МДНФ из СкДНФ используется матрица Квайна, которая строится следующим образом: в заголовках столбцов таблицы записываются конституенты единицы СДНФ, а в заголовках строк – простые импликанты из СкДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. В ТДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, т.е каждый столбей матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве МНДФ берется ТДНФ, имеющая наименьшее число вхождений переменных.

В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения можно преобразовать для нахождения МКНФ.