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

28 Пример 6.1. Проверить является ли конъюнкция импликантом для заданной функции. Пусть ( , , ) f x y z xyz xyz   и пусть K=x y =x 1 y 0 . К=1  x=1, y=0. Поскольку f(1,0,z)=1  1  z  1  1  z = z  z  1 , то К=x y является импликантом функции f . Пример 6.2. Проверить является ли конъюнкция импликантом для заданной функции. Пусть f(x,y,z,t) = x y z  x y t и пусть K = x y = x 1 y 0 . К=1  x=1, y=0. Поскольку f(1,0,z,t) = z  t  1, т.к. если z=0 и t=0, то z  t=0, т.е. К=x y не является импликантом f. Теорема 6.1. Если формула  , реализующая функцию f , имеет вид 1 n i i k     , – ДНФ, то   i k , 1, i n  . Доказательство. Пусть в ДНФ функции k i =1 . Тогда k 1 1 k k k k n n 1 i 1             ... ... ... ... и, следовательно, f=1 . Определение. Импликант P функции f называется простым, если при удалении любой переменной из P полученная элементарная конъюнкция не является импликантом. В примере 6.1. xy – простой импликант, т.к. ни x ни y импликантами не являются. Теорема 6.2. Каждая функция f 0  представима в виде i i f P   , где P i – простые импликанты. Доказательство. Нужно показать, что f=1 тогда и только тогда, когда P 1 i i   . Очевидно, что если P 1 i i   , то f=1 . Пусть теперь для некоторого набора значений переменных f k 1 i i    . В этом случае k 1 i  , а из теоремы 6.1. следует, что k i – импликант. Сокращаем этот импликант до простого. Данную процедуру повторяем для всех наборов значений переменных, для которых f=1 .