Section 5.5 主合取范式
Objectives: 极大项
- 极大项的字母用M表示
- 若极小项是\(m_i \)，则极大项是\(M_i= {\color{Blue}{\neg}} m_i \)
- \(\displaystyle m_0 = \neg p \wedge \neg q \wedge \neg r \)
- \(\displaystyle M_0 = \neg( \neg p \wedge \neg q \wedge \neg r ) = p \vee q \vee r \)
- \(\displaystyle m_3 = \neg p \wedge q \wedge r \)
- \(\displaystyle M_3 = \neg( \neg p \wedge q \wedge r ) = p \vee \neg q \vee \neg r \)
Objectives: 主合取范式
- 主析取范式在样子上看是由不同极大项通过合取符连接而成
- 例如:\(M_1 {\color{Blue}{\wedge}} M_3 {\color{Blue}{\wedge}} M_6 \)
- 任何公式都有唯一的和它等值的主合取范式
- 从某公式的主合取范式中很容易看出原公式的成假赋值
- 例如：某公式的主合取范式是\(M_1 \wedge M_6 \)则其成假赋值是001和101
Objectives: 如何求主合取范式
- 主合取范式可以通过主析取范式求出
- 假设三个变量的主析取范式是:\(m_2 \vee m_4 \vee m_6 \)
- 则相应的主合取范式是:\(M_0 \wedge M_1 \wedge M_3 \wedge M_5 \wedge M_7 \)
- 在主析取范式中极小项出现的下标在主合取范式极大项中不出现
- 在主析取范式中极小项没出现的下标在主合取范式极大项中必出现
Exercises Exercises
1.
假设一个公式的主析取范式是\(m_1 \vee m_2 \vee m_5 \vee m_7 \vee m_6 \)
该公式的主合取范式是什么
2.
已知极小项\(m_2 = \neg p \vee q \vee \neg r \)
请写出极大项 \(M_2 \)的公式
Exercises Exercises
3.
若公式的主合取范式是\(M_0 \wedge M_3 \wedge M_4 \)则它的成假赋值是?
Answer
000,011,100