[Список тем]

Построение СКНФ и СДНФ интерпретацией

Для анализа работы и отладки логических схем используют совершенные формы алгебры логики СКНФ и СДНФ.

Определение 1
Элементарная конъюнкция (дизъюнкция) называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождения со знаком отрицания).

Определение 2
Правильная элементарная конъюнкция (дизъюнкция) называется полной относительно переменных X1,X2,..Xn, если каждая из этих пере менных входит в нее один и только один раз (возможно со знаком отрицания).

Определение 3
Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных X1...Xn, называется конъюнктивная нормальная форма, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильны и полны относительно переменных X1...Xn.

Определение 4
Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных X1...Xn, называется дизъюнктивная нормальная форма, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных X1...Xn.

Простейшим способом получения СДНФ и СКНФ является интерпретация, т.е. перебор всех возможных сочетаний значений аргументов функции и определение логического значения самой функции для каждого из этих сочетаний. Таблица истинности строится в порядке выполнения логичкеских опрераций в логическом выражении. Используя таблицы истинности логических операций, строим таблицу истинности для заданной формулы. Затем, исключаем промежуточные вычисления, оставляя множество значений логических переменных, участвующих в этой формуле, и результирующее значение этой формулы.
Пример 1
F(P,Q,R)=P→(QvR→(R→¬P))

P	Q	R	¬P	QvR	R→¬P	QvR→(R→¬P)	P→(QvR→(R→P))
1	1	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	0	1	0	1	0	0	0
1	0	0	0	0	1	1	1
0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1
0	0	1	1	1	1	1	1
0	0	0	1	0	1	1	1

P	Q	R	P→(QvR→(R→P))
1	1	1	0
1	1	0	1
1	0	1	0
1	0	0	1
0	1	1	1
0	1	0	1
0	0	1	1
0	0	0	1

1. Для построения СДНФ необходимо в таблице истинности для функции отметить все строки в которых функция истинна; для каждой такой строки образуем элементарную конъюнкцию таким образом, что если перемннная в строке таблицы истинности равна 0, то в элементарную конъюнкцию она включается со знаком отрицания; а если равна 1, то - без знака отрицания. Затем все элементарные конъюнкции соединяются знаком дизъюнкции.

   F(P,Q,R)=P→(QvR→(R→¬P))=

   (P&Q&¬R) v (P&¬Q&¬R) v (¬ P&Q&R) v (¬P&Q&¬R) v (¬P& ¬Q&R) v (¬P&¬ Q&¬R)
    

2. Для построения СКНФ необходимо в таблице истинности для функции отметить все строки в которых функция ложна; для каждой такой строки образуем элементарную дизъюнкцию таким образом, что если перемннная в строке таблицы истинности равна 0, то в элементарную дизъюнкцию она включается без знака отрицания; а если равна 1, то - со знаком отрицания. Затем все элементарные дизъюнкции соединяются знаком конъюнкции.

   F(P,Q,R)=P→(QvR→(R→¬P))=(¬Pv¬Qv¬R)&(¬PvQv¬R)

[Список тем]