Section 5.3 等值演算求主析取范式
Objectives: 用等值演算求下面公式的主析取范式
- \(\displaystyle \neg (p \imp q) \vee \neg r\)
第一步:去掉"箭头".
\begin{gather*}
\neg (p \imp q) \vee \neg r \Iff \neg ( \neg p \vee q ) \vee \neg r
\end{gather*}
第二步:去掉括号外的否定.
\begin{gather*}
\neg ( \neg p \vee q ) \vee \neg r \Iff (p \wedge \neg q) \vee \neg r
\end{gather*}
第三步:找出各个析取项.
\begin{gather*}
{\color{blue}{(p \wedge \neg q)}} \vee {\color{green}{\neg r}}
\end{gather*}
第四步:利用“三律”补全每个析取项中缺少的字母.
排中律:\(\quad A \vee \neg A =1 \)
同一律 \(\quad A \wedge 1 = A \)
分配律 \((A \wedge B) \wedge (C \vee \neg C) = (A \wedge B \wedge C) \vee (A \wedge B \wedge \neg C) \)
\begin{equation*}
{\color{Blue}{p \wedge \neg q}}
\end{equation*}
\begin{equation*}
\Iff {\color{Blue}{p \wedge \neg q}} \wedge 1 \quad \text{同一律}
\end{equation*}
\begin{equation*}
\Iff {\color{Blue}{p \wedge \neg q}} \wedge (r \vee \neg r) \quad \text{ 排中律,ps:缺r补r }
\end{equation*}
\begin{equation*}
\Iff {\color{Blue}{ (p \wedge \neg q \wedge r ) \vee ( p \wedge \neg q \wedge \neg r ) }} \quad \text{分配律}
\end{equation*}
\begin{equation*}
\therefore {\color{Blue}{p \wedge \neg q}} \quad 包含两个极小项 m_4和m_5
\end{equation*}
\begin{equation*}
{\color{green}{\neg r}}
\end{equation*}
\begin{equation*}
\Iff \neg r \wedge 1 \wedge 1 \text{同一律}
\end{equation*}
\begin{equation*}
\Iff \neg r \wedge ( p \vee \neg p) \wedge (q \vee \neg q ) \quad \text{排中律,ps:缺q补q,缺p补p}
\end{equation*}
\begin{equation*}
\Iff (p \wedge q \wedge \neg r) \vee (p \wedge \neg q \wedge \neg r) \vee (\neg p \wedge q \wedge \neg r) \vee ( \neg p \wedge \neg q \wedge \neg r)
\quad \text{分配律}
\end{equation*}
\begin{equation*}
\therefore {\color{green}{\neg r}} \quad 包含四个极小项m_0,m_2,m_4,m_6
\end{equation*}
第5步: 将所有极小项用析取符号连接成主析取范式.
\begin{equation*}
m_0 \vee m_2 \vee m_4 \vee m_5 \vee m_6
\end{equation*}
\begin{equation*}
\Iff \Sigma ( 0,2,4,5,6 )
\end{equation*}