пользователей: 21251
предметов: 10459
вопросов: 177801
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Разложенение функции по переменным. СДНФ. СКНФ

Элментарная коньюнкция - выражение вида x1(в степени сигма)...Xn(в степени сигма)

пример: Х1 НЕ(Х2) НЕ(Х3) Х4

НЕ(X)НЕ(Y)НЕ(Z)

Элементарная коньюнкция называется правильной, если любая переменная входит в нее не более одного раза. Полная элементарная коньюнкция относительно переменных х1,х2,х3...хn - это правильная элементарная коньюнкция, содержащая все элементы и они не повторяются.

Дизьюнктивная нормальная форма - дизьюнкция элементарнх коньюнкций

ПРимер: U(x,y,z) = НЕ(X)y\/НЕ(Y)\/НЕ(Х)НЕ(Y)Z\/YНЕ(Z)

Совершенная дизьюнктивная нормальная форма - это днф, в которой все элементарные коньюнкции полные и нет одинаковых

Получение нормальных форм:
F -> ДНФ -> КНФ -> СКНФ

          |

          \/

         СДНФ

Получение ДНФ:
1) Избавиться от всех сложений по модулую 2, импликаций и тд и выразить все через дизьюнкцию, коньюнкцию и отрицание

2) Избавиться от отрицаний, допускается отрицание над отдельными элементами

3) Раскрываем скобки

4) Избавляемся от повторений

Х /\ HE(X) = 0                              X /\ HE(X) /\ Y /\ Z = 0

X /\ X = X

Получение СДНФ:
1) домножаем на (X\/НЕ(Х) или Y\/НЕ(Y) или Z\/НЕ(Z), чтобы в каждом слагаемом присутствовали все элементы от которых зависит функция

2) Избавиться от повторяющихся эл. коньюнкций

Получение КНФ:
1) ОТ ДНФ мы должны перейти к КНФ :

    а) Упростить выражение по формулам поглощения:

           например X \/ XY = X

         XY \/ XHE(Y) = 1

    б) Переход к КНФ 

           X \/ YZ = (X \/ Y)(X \/ Z)

   в) Убрать повторяющиеся скобки и скобки, дающие еденицу, напр: (Y \/ HE(Y) \/ X) = 1

Переход от КНФ к СКНФ:
     а) В скобки, где нехватает переменных добавить XНЕ(X)  или YНЕ(Y) или ZНЕ(Z)

Затем упростить по формуле 

X \/ YZ = (X \/ Y)(X \/ Z)

Затем избавиться от повторений и 1.

Совершенная дизъюнктивная и конъюнктивная нормальная формы дают способ представления булевой функции через суперпозицию конъюнкции, дизъюнкции и отрицания если у нас есть таблица значений функции.

Чтобы получить совершенную дизъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 1 и записать для каждого из них конъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять с отрицанием, если 1 – без отрицания. Из получившихся конъюнкций надо построить дизъюнкцию.

Чтобы получить совершенную конъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 0 и записать для каждого из них дизъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять без отрицания, если 1 – с отрицанием. Из получившихся дизъюнкций надо построить конъюнкцию.


17.06.2015; 21:58
хиты: 166
рейтинг:0
Точные науки
математика
логика и основания математики
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь