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

8 2 совершенной к.н.ф. этой функции, а в левый столбец - множитеяи, содержащиеся в со1фащенной к.н.ф. (которые называются простыми имплицентами). Клетки имплицентной матрицы, находящиеся на пересечении столбца с конституентой нуля, и строки с членом, который ее поглощает, отмечаются звездочками. Для построения минимальной к.н.ф. выбирают простые имппиценты, которые совместно накрывают звездочками (*) все столбцы и в совокупности содержат наименьшее возможное число вхождений переменных (с отрицаниями или без отрицаний). Пусть требуется найти минимальную к.н.ф, для функции; (xvyvz) & (lxvyvz)&(xvlyvz)&(xv]yvlz). Сокращенной к.н.ф,, как легко видеть, будет (yvz )&(xvz)&(xvl у). Построим имплицентную матрицу: xvyvz ]xvy\^ xvlyvz xvlyvlz yvz * xvz xvly * Видно, что имппиценты >'vz и a:v 7у покрывают символами * все столбцы имплицентной матрицы, следовательно, (yvz)&(xvly) является минимальной к.н.ф. § 18. Полнота системы функций. Теорема Поста Среди рассмотренных вопросов важными являлись вопросы о представимости булевых функций с помощью связок 7, &, v, либо 7, либо 7, V, и т.п. Всякий раз фактически речь цдла о возможности представить булевы функции с помощью только некоторых функций и суперпозиция последних. Иначе можно сказать, что из всевозможных булевых функций были выделены некоторые функции (pi,(p2,..., <pt, а затем выяснялось, можно ли любую булеву функцию представить как суперпозицию функций Система функций 0={(p,,(p2,...,q)iJ называется функционально полной, если всякая булева функция представима посредством суперпозиции функций из системы Ф. Из теоремы 3.14 или 3.15 следует, что любую булеву функцию можно представить с помощью формулы, содержащей только связки 1 , v. Следовательно, система функций (p;(AJ=] х, (р2(х,у)=х&у, (pi(x,y)=xvy является функциона^тьно полной системой функций. Эта полная система состоит из трех функций (одной одноместной и двух двуместных функций). Из теорем 3.14 и 3,6 следует, что каждая из функций (р(х,у)=х1 у и W(x,y)=x-ly образует полные системы, состоящие только из одной функции.