$$\large{\begin{gather*}\Large {\color{#ff7800}(p \to q) \to r} \\ \\\begin{array}{c|l}1 & \neg(\neg p \lor q) \lor r \\2 & (\neg \neg p \land \neg q) \lor r \\3 & (p \land \neg q) \lor r \\4 & (p \lor r) \land (\neg q \lor r)\end{array}\end{gather*}}$$
Алгоритм получения конъюнктивной нормальной формы в алгебре логики
Как получить КНФ?
- Выразить все логические операции через конъюнкцию, дизъюнкцию и отрицание
- $$p \rightarrow q \leftrightarrow \neg p \vee q$$
- $$(p \leftrightarrow q) \leftrightarrow (\neg p \vee q) \wedge (p \vee \neg q)$$
- Раскрыть скобки в выражениях с отрицанием
- $$\neg (p \vee q) \leftrightarrow \neg p \wedge \neg q$$
- $$\neg (p \wedge q) \leftrightarrow \neg p \vee \neg q$$
- Избавиться от знаков двойного отрицания
- $$\neg \neg p \leftrightarrow p$$
- Применить к дизъюнкциям закон дистрибутивности и правила поглощения
- $$p \lor (q \land r) \leftrightarrow (p \lor q) \land (p \lor r)$$
