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

76 Считают, что два члена х&у и х& 1у скчеиваются по переменной у. Операция поглощения определяется соотношением: х vx&y~x. Говорят, что слагаемое х&у поглощается слагаемым х Операцш неполного склеивания определяется соотношением x&yvx& ]y~xvx&.yvx8c Ту, которое получается из (3.23), если учесть, что x~xvx. Следовательно, при неполном склеивании, кроме слагаемого х, полученного в результате полного склеивания, остаются оба слагаемых, участвующих в склеивании. Можно доказать следующую теорему. Теорема 3.18 (теорема Квайна). Если в совершенной д.н.ф. булевой функции провести все операции неполного склеивания и затем все операции поглощения, то в результате получится сокращенная д.н.ф. этой функции. Доказательство теоремы даёт правила нахождения сокращенной д.н.ф. Эти правила будут следующими. Для заданной функщги/fx;, Хг, .... х,) необходимо найти равносильную ей с.д.н.ф., в полученной с.д.н.ф. провести все возможные операции склеивания конституент единицы. В результате этих склеиваний пол>'чатся произведения, содержащие я-1 переменных. Склеиваться могут только произведения с одинаковым количеством переменных. В силу этого при дальнейшем склеивании не будут ^'частвовать конституенты единицы, поэтому можно после всех склеиваний.,^конституент единицы провести всевозможные операции поглощения. Затем выполняются всевозможные операции неполного склеивания слагаемых имеющих (и-1) множителей. После этого провести всевозможные операции поглощения и вновь выполнить всевозможные операции склеивания слагаемых содержашлх (и-2) множителей и т.д. § 15. Тупиковые и минимальные д.н.ф. Начнем с рассмотрения примера. Пусть задана функция, представленная в с.д.н.ф.-. f(x,y,z) =x&y&z vx&y& Iz vlx&y& Iz V lx& 1 у &.1 z. Найдем для этой функции сокращенную д.н.ф. Проведя операции склеивания и поглощения, получим f(x,y,z) ~x&yvy& ] z v]x& Iz. В полученной сокращенной д.н.ф. импликанту y&l z можно исключить. Действительно, умножив y&lz на xvlx (что не изменяет значений y&lz) и применив операцию поглощения, получим