Дизъюнктивная нормальная форма ВИННИКОВ В. Э. МАОУ СШ «КОМПЛЕКС «ПОКРОВСКИЙ» - презентация

1 Дизъюнктивная нормальная форма ВИННИКОВ В. Э. МАОУ СШ «КОМПЛЕКС «ПОКРОВСКИЙ»

2 Допустим у нас есть некоторая логическая функция F(x, y, z), которая задана своей таблицей истинности логических переменных. То есть она напрямую зависит от их значений, но формула неизвестна XYZF

3 Попробуем её выразить формульно, на базе каких-либо логических операций XYZF На самом деле достаточно всего одной операции для формирования любой логической функции. Мы с вами будем пользоваться классическим набором: И, ИЛИ, НЕ Этого достаточно, чтобы любую логическую функцию выписать как логическое выражение.

4 Итак... Рассмотрим следующие логические выражения XYZFX*Y*Z Очевидно, x*y*z истинна, только в последней строке, во всех остальных случаях она ложна. То есть, казалось бы все эти выражения не похожи, но не совсем так, они похожи именно в последней строке. Более того у нас появился алгоритм, как вставить 1 в нужную строчку.

5 XYZFX*Y*Zне X*неY*нет Давайте теперь добавим выражение, чтобы было соответствие первой строке, истина, там получается умножение с отрицанием каждого элемента. НеX *неY* нет. В остальных строчках она ложна.

6 XYZFX*Y*ZнеX*неY*нетнеX*Y*нет Теперь нам нужно придумать такую функцию для третьей строки: получается нам подходит: неX*Y* нет

7 XYZFX*Y*ZнеX*неY*нетнеX*Y*нетX*неY*Z Наконец, для последней 1 подходит выражение X*неY*Z

8 Для удобства обозначим все умножения буквами A, B, C, D. Очевидно, что если мы сложим их, то получим значение, соответствующие столбцу F. То есть F =X*Y*Z+неX*неY*нет+неX*Y*нет+X*неY*Z XYZFABCDA+B+C+D

9 Выразить одну и туже функцию существует большое множество возможностей, например, если к получившейся у нас функции прибавить X*не X, то функция останется неизменной.

10 Попробуем упростить полученную функцию. 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)

11 Задание: Построить конъюнктивную нормальную форму, работая со строками с «0».