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

77 f(x,y,z) ~x&yvx&y& J zvlx&y& Iz V lx& Iz ~x&yvlx& Iz. (3-24) В результате получили дизъюнкцию некоторых простых импликант исходной функции. Ясно, что при отбрасывании любой из двух импликант, входящих в (3.24), получим функцию, не равносильную исходной. Тупиковой д.п.ф. булевой функции / называется дизъюнкция простых импликант функции /, ни одну из которых исключить нельзя, и указанная дизъюнкция равносильна функции/ Некоторые булевы функции имеют несколько тупиковых форм, например, функция f(x,y,z)=l x&yvx&l yvx&zyy&z имеет две тупиковых д.н.ф.: Ix&yvx&lyvx&zvi Ix&yvx&lyvy&z. Минимальной д.н.ф. булевой функции называется д.н.ф.» равносильная этой функции и содержащая наименьшее возможное число вхождений переменных с отрицанием или без отрицания. Отметим, что в определении идет речь о минимальном числе вхождений переменных (с отрицанием или без отрицания), а не различных переменных. Например, д.н.ф. xScyvlxSclz содержит четыре вхолсдений переменных, но три различные переменные (х,у^). Теорема 3.19. Всякая минимальная д.н.ф. булевой функции/является её тупиковой д.н.ф. Доказательство. Пусть минимальная д.н.ф. некоторой функции имеет вид: f=CjvC2V...vC „, (3.25) где каждое С,- (1 <г<и) - элементарное произведение. Покажем, что каждое С, является простой импликантой заданной функции. Если / обращается в О при некоторых значениях своих аргументов, то, очевидно, и каждое С,- (1<i<n) принимает значение О, следовательно, каждое Ci является импликантой функции. Далее покажем, что эта импликанта простая, т.е. никакая собственная часть Ct (!.< i £ п) уже не является импликантой. Допустим, что, например, Ct (1 <А:<г) не является простой импликантой. Каждое С,- (1 <;'< п), в том числе и Q , по доказанному, является импликантой функции/ Т а к как по допущению Q не является простой импликантой (но импликанта для /), то некоторая ее часть будет простой импликантой для /. т.е. Ck может быть представлена в виде Q = , где Q - простая импликанта. Заменим правую часть (3.25) на равносильную: CjvC2V...vC „vCi!*.