Привести к совершенной дизъюнктивной и конъюнктивной нормальным формам:
X→Y&¬Y→¬X;
¬A&B→¬A&¬A&B→¬B;
¬X↔Y;
A&B→B&C;
X∨Y→X;
B↔¬C&A→B;
A∨¬C→B&C;
X↔Y→X∨Y;
B→¬A&C↔B;
A&B∨A∨B&¬A∨¬B.
Решение
Алгоритмы построения совершенных нормальных форм.
СДНФ:
составляется таблица истинности формулы;
выбираются строки, в которых формула принимает значение 1;
для каждой выбранной строки составляется конъюнкт — если переменная в строке принимает значение 1, то в конъюнкт включается сама переменная, если переменная в строке принимает значение 0, то в конъюнкт включается её отрицание;
образуем дизъюнкции всех построенных конъюнктов.
СКНФ:
составляется таблица истинности формулы;
выбираются строки, в которых формула принимает значение 0;
для каждой выбранной строки составляется дизъюнкт — если переменная в строке принимает значение 0, то в дизъюнкт включается сама переменная, если переменная в строке принимает значение 1, то в дизъюнкт включается её отрицание;
образуем конъюнкции всех построенных дизъюнктов.
1) X→Y&¬Y→¬X.
СДНФ — ¬X&¬Y∨¬X&Y∨X&Y;
СКНФ — ¬X∨Y.
2) ¬A&B→¬A&¬A&B→¬B.
СДНФ — A&B;
СКНФ — A∨B&A∨¬B&¬A∨B.
3) ¬X↔Y.
СДНФ — ¬X&Y∨X&¬Y;
СКНФ — X∨Y&¬X∨¬Y.
4) A&B→B&C.
СДНФ — ¬A&¬B&¬C∨¬A&¬B&C∨¬A&B&¬C∨¬A&B&C∨A&¬B&¬C∨A&¬B&C∨A&B&C;
СКНФ — ¬A∨¬B∨C.
5) X∨Y→X.
СДНФ — ¬X&¬Y∨X&¬Y∨X&Y;
СКНФ — X∨¬Y.
6) B↔¬C&A→B.
СДНФ — ¬A&¬B&C∨¬A&B&¬C∨A&B&¬C;
СКНФ — A∨B∨C&A∨¬B∨¬C&¬A∨B∨C&¬A∨B∨¬C&¬A∨¬B∨¬C.
7) A∨¬C→B&C.
СДНФ — ¬A&¬B&C∨¬A&B&C∨A&B&C;
СКНФ — A∨B∨C&A∨¬B∨C&¬A∨B∨C&¬A∨B∨¬C&¬A∨¬B∨C.
8) X↔Y→X∨Y.
СДНФ — ¬X&Y∨X&¬Y∨X&Y;
СКНФ — X∨Y.
9) B→¬A&C↔B.
СДНФ — ¬A&¬B&¬C∨¬A&B&C∨A&¬B&¬C;
СКНФ — A∨B∨¬C&A∨¬B∨C&¬A∨B∨¬C&¬A∨¬B∨C&¬A∨¬B∨¬C.
10) A&B∨A∨B&¬A∨¬B
СДНФ — ¬A&B∨A&¬B∨A&B;
СКНФ — A∨B.
на новый заказ в Автор24.
