Дискретная математика

75 либо ее некоторая часть является простой импликантой для f. Отсюда следует, что каждая простая импликанта совпадает с одной из собственных конституент единицы функции / или является частью какой-либо из этих конституент. Поэтому, чтобы найти простые импликанты для f , можно рассматривать собственные конетитуенты единицы функции, всевозможные их части и среди них отыскивать простые импликанты. Данный способ тоже громоздкий. Существуют и другае методы, один из них (метод Квайна) рассмотрим в следующем параграфе. Сокращенной д.н.ф. для булевой функции f(xi, х^, xj называется дизъюнкция всех простых импликант этой функции. Из определения следует, что для каждой функции / сокращенная д.н.ф. единственна. Теорема 3.17. Каждая булева функция /(xj, Xj, х,^ равносильна своей сокращенной д.н.ф. Доказательство. Пусть для /(х/, хг, ••, x J построена ее сокращенная д.н.ф.: (3.22) где Bj ~ простые импликанты функции. Покажем, что на каждом наборе значений переменных ху, Х2, ..., х,, значения функции и суммы (3.22) совпадают. Пусть на каком-то наборе значений переменных xj, Х2,..., Хд функция/=0. Каждое В,- является импликантой для /, поэтому на выбранном наборе Д =0 i<in), следовательно, и вся сумма (3.22) обращается в нуль. Далее, пусть f(ai, аг, ..., я,^=1. Тогда на наборе aj, аг, ..., равна 1 некоторая собственная конституента единицы функции f. Обозначим эту конституенту через К. Как уже показано, кансдая конституента единицы функции / либо сама является простой импликантой, либо будет простой импликантой ее некоторая собственная часть. Следовательно, некоторое В; из (3.22) совпадает с К, либо с её некоторой собственной частью. Если Д = К, то н а наборе а/, «п имеем Bi(ai, 02, a j = K(ai, а2, ..., Ял) если же Bt является собственной частью К, то, очевидно, Д =1 на этом наборе. Тогда сумма (3.22) примет значение 1 на наборе Й /, ог, «я- Теорема доказана. § 14. Метод Квайна получения сокращенной д.н.ф. Метод Квайна основан на преобразовании совершенной д.н.ф. с помощью операций неполного склеивания и поглощения. Операция склеивания (полного) определяется соотношением х&у vx&ly ~х. (3.23)