§ 14. Метод Квайна получения сокращенной д.н.ф.

Метод Квайна основан на преобразовании совершенной д.н.ф. с помощью операций неполного склеивания и поглощения.

Операция склеивания (полного) определяется соотношением

$x\&y ∨ x\&¬ y ~ x$

Считают, что два члена x&y и x&¬ y склеиваются по переменной y.

Операция поглощения определяется соотношением: x ∨ x&y ~ x. Говорят, что слагаемое x&y поглощается слагаемым x. Операция неполного склеивания определяется соотношением

$x\&y∨x\&¬ y~x∨x\&y∨x\&¬ y$

которое получается из (3.23), если учесть, что x~x∨x. Следовательно, при неполном склеивании, кроме слагаемого x, полученного в результате полного склеивания, остаются оба слагаемых, участвующих в склеивании.

Можно доказать следующую теорему.

Теорема 3.18 (теорема Квайна). Если в совершенной д.н.ф. булевой функции провести все операции неполного склеивания и затем все операции поглощения, то в результате получится сокращенная д.н.ф. этой функции.

Доказательство теоремы даёт правила нахождения сокращенной д.н.ф. Эти правила будут следующими.

Для заданной функции f(x1, x2, ..., xn) необходимо найти равносильную ей с.д.н.ф., в полученной с.д.н.ф. провести все возможные операции склеивания конституент единицы. В результате этих склеиваний получатся произведения, содержащие n-1 переменных. Склеиваться могут только произведения с одинаковым количеством переменных. В силу этого при дальнейшем склеивании не будут участвовать конституенты единицы, поэтому можно после всех склеиваний конституент единицы провести всевозможные операции поглощения. Затем выполняются всевозможные операции неполного склеивания слагаемых имеющих (n-1) множителей. После этого провести всевозможные операции поглощения и вновь выполнить всевозможные операции склеивания слагаемых содержащих (n-2) множителей и т.д.