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

81 - в с.к.н.ф. раскрываем скобки, т.е. осуществляем преобразование т ип аД v-i » - в полученном выражении удаляем противоречия, проводим поглощения: А vA-A и А vAc&B~A. В результате придем к сокращенной д.н.ф. Так, для примера, рассмотренного в начале данного параграфа, с.к.н.ф. имеет вид: (xvlyv]z) &( Ixvyvz). Проведем указанные преобразования; (xv]yv]z)&(Ixvyvz)'- (xv]yvlz)&(Ixvyvz) ~ ~ x& Ix vx&yvx&z vlx& lyvy& lyvly&zvlxdc lzvy& ]zvz& ]z ~ ~ x&yvx&zvlx&lyvly&zvlx&lzvy&lz. Таким образом, сокращенная д.н.ф. найдена. § 17. Минимальные конъюнктивные нормальные формы Как и для д.н.ф., для к.н.ф. можно ввести аналоги понятий импликанты, простой импликанты, сокращенной, тупиковой и минимальной к.н.ф. Для нас представляют интерес только минимальные к.н.ф. и методы их нахождения. Так как остальные указанные понятия играют при этом роль посредников, то постараемся по возможности их избежать или, по крайней мере, не описывать их. Минимальной к.н.ф. булевой функции/называется к.н.ф., равносильная f , которая содержит наименьшее число вхождений переменных. Как и минимальную д.н.ф., минимальную к.н.ф. находят в следующей последовательности. Если функция / тождественно равна 1, то ее минимальной к.н.ф., очевидно, будет функция xvlx. Если функция / не тождественно равна 1, то сначала находят совершенную к.н.ф., по совершенной к.н.ф. - сокращенную к.н.ф., по сокращенной к.н.ф. - тупиковые к.н.ф. и из них выбирают минимальные к.н.ф. Мы не ввели определение сокращенной и тупиковой к.н.ф., не будем делать этого и далее, а только опишем процедуры (методы), позволяющие находить некоторые к.н.ф., которые можно считать сокращенными или тупиковыми по аналогии с дизъюнктивными формами. Нахоокдение сокращенной к.н.ф. Считаем, что для заданной функции уже найдена соверш:енная к.н.ф. В этой с.к.н.ф. выполняют всевозможные операции неполного склеивания и затем операции поглощения. Операция неполного склеивания определяется следующим образом: (х vy) &(х vl у)~х&(х vy)&(х vly), а операция поглощения-xc&(xvyj~x После выполнения этих операций будет получена сокращенная к.н.ф. Метод ттицентных матриц для нахождения минимальной к.н.ф. состоит в следующем. Имплицентная матрица представляет собой таблицу, в верхнюю строку которой записываются конституенты нуля, содержащиеся в