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

Пример. Легко убедиться, что ^ушцт f(x,y)=x&y является импликантой для f(x,y)=x^ у. Таюке легко видеть, что функция х=> у - и.мпликанта для f(x,y,z)=(ly^lx)vz. Функция (р(х,у)=х не является импликантой д л я и б о f(lfi)=0, а (р('1,0^=1. Очевидно, что функция, тождественно равная нулю (противоречие), является импликантой каждой булевой функции. Таюке очевидно, что каждая булева функция является импликантой функции, тождественно равной единице (тавтологии). Собственной частью произведения называют произведение, полученное исключением из данного произведения одного или нескольких сомножителей. Простьши гштикантачи булевой функции f называются такие элементарные произведения, которые сами являются импликантами функции /, но никакая собственная часть этих произведений не является импликантой этой функции. Например, если: x&y&z&lt с f(x,y,z,t), увс2 с f(x,y,z,t), у сг f(x,y,z,t), Z czr f(x,y,z,t), то y&z будет простой импликантой функции f(x,y,z,t). Выясним, как найти импликанты и простые импликанты для заданной функции f(xi,x2,.:,x,). Ясно, что можно рассмотреть все функции о т переменных и среди них выделить импликанты и простые импликанты для функции / Этот метод громоздкий и требует большого счета. Другой метод заключается в следующем. Построим для f(x],x2,...,xj таблицы истинности. Если / тождественна равна нулю, то ее импликантой является только функция, тождественно равная нулю. Если/тождественно равна единице, то любая булева функция - импликанта для нее. Пусть / не тождественно равна нулю, тогда она обращается в единицу, например, в строках к) .ki к, таблицы истинности. Для каждой из этих строк построим собственные конституенты единицы функции f . По построению каждая собственная конституента единицы Kj равна единице на наборе значений аргументов, записанных на /с-й строке, где f =l и Л]- = О на всех остальных наборах, в частности, и там, где/= 0. Следовательно, каждая собственная конституента единицы функции f является импликантой для нее. Да,пее для каждой из cipoK с номерами тит2,....тг (г=Т - s), отличными от к,.к} к,, построим по тем же правилам, что и ранее, конституенты единицы К J (О < J< г). Каждая такая конституента К) обращается в 1 на наборе, записанном в строке rrij, а функция/при этом равна О, следовательно, ни одно из К) не является импликантой для/i Таки.м образом, только собственная конституента единицы К, {\< i< г) функции/является импликантой для f , и эта собственная конституента сама