Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

30 Теорема 6.3. Пусть  – СДНФ функции f . Если  – импликант f , то все дополнения элементарной конъюнкции  по отношению к  входят в  . Доказательство. Пусть m m 2 2 1 1 i i i x x x     ...  – импликант функции f и пусть n 1 2 n 1 2 x x x     ...  является дополнением  по отношению к  . Предположим, что  не входит в  . Рассмотрим такой набор значений переменных, что  =1 , т.е. положим x i =  i , i=1,…,n . Тогда m 1 i m i 1       ,..., и  =1 , а  =0 поскольку  по предположению не входит в  . Но это противоречит тому, что  является импликантом f . Ч.т.д. Из теоремы следует, что объединяя в СДНФ  функции f соответствующим образом пары элементарных конъюнкций и применяя последовательно равенство      x x , можно в результате получить все простые импликанты функции f . Пример 6.4. Найти простые импликанты для функции f . Пусть f=xyzt  x yzt  x y zt. Первая и третья конъюнкции дают xyzt  x y zt = xzt. Вторая и третья конъюнкции дают x y z t  x y zt = x y z. Полученные выражения являются простыми импликантаим и, следовательно, f=xzt  x y z. Алгоритм Куайна и Мак-Клоски (перечисления простых импликантов) Систематизируем изложенную выше идею. 1) Выпишем для функции f СДНФ  . 2) В каждой элементарной конъюнкции все переменные будем записывать в одинаковом порядке. 3) Каждую конъюнкцию будем представлять в виде последовательности из 1, 0 и –, ставя на i-м месте 1,