Дизъюнктивная нормальная форма ВИННИКОВ В. Э. МАОУ СШ «КОМПЛЕКС «ПОКРОВСКИЙ»
Допустим у нас есть некоторая логическая функция F(x, y, z), которая задана своей таблицей истинности логических переменных. То есть она напрямую зависит от их значений, но формула неизвестна XYZF
Попробуем её выразить формульно, на базе каких-либо логических операций XYZF На самом деле достаточно всего одной операции для формирования любой логической функции. Мы с вами будем пользоваться классическим набором: И, ИЛИ, НЕ Этого достаточно, чтобы любую логическую функцию выписать как логическое выражение.
Итак... Рассмотрим следующие логические выражения XYZFX*Y*Z Очевидно, x*y*z истинна, только в последней строке, во всех остальных случаях она ложна. То есть, казалось бы все эти выражения не похожи, но не совсем так, они похожи именно в последней строке. Более того у нас появился алгоритм, как вставить 1 в нужную строчку.
XYZFX*Y*Zне X*неY*нет Давайте теперь добавим выражение, чтобы было соответствие первой строке, истина, там получается умножение с отрицанием каждого элемента. НеX *неY* нет. В остальных строчках она ложна.
XYZFX*Y*ZнеX*неY*нетнеX*Y*нет Теперь нам нужно придумать такую функцию для третьей строки: получается нам подходит: неX*Y* нет
XYZFX*Y*ZнеX*неY*нетнеX*Y*нетX*неY*Z Наконец, для последней 1 подходит выражение X*неY*Z
Для удобства обозначим все умножения буквами A, B, C, D. Очевидно, что если мы сложим их, то получим значение, соответствующие столбцу F. То есть F =X*Y*Z+неX*неY*нет+неX*Y*нет+X*неY*Z XYZFABCDA+B+C+D
Выразить одну и туже функцию существует большое множество возможностей, например, если к получившейся у нас функции прибавить X*не X, то функция останется неизменной.
Попробуем упростить полученную функцию. F =X*Y*Z+неX*неY*нет+неX*Y*нет+X*неY*Z= X*Z*(Y+неY)+неX*нет*(Y+неY)= X * Z + неX* нет = X=Z 1.Посмотрим, что можно вынести за скобки. X*Y*Z и X*неY*Z. 2. Второе пока остаётся на месте 3.Y+неY сокращается по закону исключённого третьего. 4. У нас получилась функция, которая не зависит от Y. 5. По эквивалентности получилось X = Z, то есть F(x,y,z)=(x=z)
Задание: Построить конъюнктивную нормальную форму, работая со строками с «0».