【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 )

一. 相关概念 1. 简单 析取 合取 式 ( 1 ) 简单合取式

简单合取式 :

• 1.组成 : 命题变元 ( p p p ) 或 命题变元否定式 ( ¬ p \lnot p ¬p ) ;
• 2.概念 : 有限个 命题变元 或其 否定式 组成的合取式 , 称为 简单合取式 ;
• 3.示例 :
  • ① 单个命题变元 : p p p ;
  • ② 单个命题变元否定式 : ¬ p \lnot p ¬p
  • ③ 两个 命题变元 或其否定式 构成的合取式 : p ∧ ¬ q p \land \lnot q p∧¬q
  • ④ 三个 命题变元 或其否定式 构成的合取式 : p ∧ q ∧ r p \land q \land r p∧q∧r

( 2 ) 简单析取式

简单析取式 :

• 1.组成 : 命题变元 ( p p p ) 或 命题变元否定式 ( ¬ p \lnot p ¬p ) ;
• 2.概念 : 有限个 命题变元 或其 否定式 组成的析取式 , 称为 简单析取式 ;
• 3.示例 :
  • ① 单个命题变元 : p p p ;
  • ② 单个命题变元否定式 : ¬ p \lnot p ¬p
  • ③ 两个 命题变元 或其否定式 构成的析取式 : p ∨ ¬ q p \lor \lnot q p∨¬q
  • ④ 三个 命题变元 或其否定式 构成的析取式 : p ∨ q ∨ r p \lor q \lor r p∨q∨r

2. 极小项 ( 1 ) 极小项 简介

极小项 : 极小项 是 一种 简单合取式 ;

• 1.前提 ( 简单合取式 ) : 含有 n n n 个 命题变项 的 简单合取式 ;
• 2.命题变项出现次数 : 每个命题变项 均 以 文字 的 形式 在其中出现 , 且 仅出现 一次 ;
• 3.命题变项出现位置 : 第 i i i ( 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n ) 个文字出现在 左起 第 i i i 个位置 ;
  • n n n 是指命题变项个数 ;
• 4.极小项总结 : 满足上述三个条件的 简单合取式 , 称为 极小项 ;
• 5. m i m_i mi​ 与 M i M_i Mi​ 之间的关系 : ① ¬ m i    ⟺    M i \lnot m_i \iff M_i ¬mi​⟺Mi​ ② ¬ M i    ⟺    m i \lnot M_i \iff m_i ¬Mi​⟺mi​

( 2 ) 极小项 说明

关于 极小项 的 说明 :

• 1.极小项个数 : n n n 个 命题变元 会 产生 2 n 2^n 2n 个 极小项 ;
• 2.互不等值 : 2 n 2^n 2n 个极小项 均 互不等值 ;
• 3.极小项 : m i m_i mi​ 表示 第 i i i 个极小项 , 其中 i i i 是该极小项 成真赋值 的 十进制表示 ;
• 4.极小项名称 : 第 i i i 个极小项 , 称为 m i m_i mi​ ;

( 3 ) 两个命题变项 的 极小项

两个命题变项 p , q p, q p,q 的 极小项 :

• 1.先写出 极小项 名称 : 从 0 0 0 开始计数 , m 0 , m 1 , m 2 , m 3 m_0, m_1, m_2, m_3 m0​,m1​,m2​,m3​ ;
• 2.然后写出成真赋值 : 0 , 1 , 2 , 3 0,1,2,3 0,1,2,3 对应的二进制形式 , 即 00 , 01 , 10 , 11 00 , 01, 10, 11 00,01,10,11 ;
• 3.最后写公式 ( 简单合取式 ) :
  • ① 公式形式 : 公式是简单合取式 , p ∧ q p \land q p∧q , 其中 每个命题变项 p , q p,q p,q 之前都可能带着 否定符号 ¬ \lnot ¬ ;
  • ② 满足成真赋值 : 该公式需要满足 其 上述 00 , 01 , 10 , 11 00 , 01, 10, 11 00,01,10,11 赋值是成真赋值 , 即根据成真赋值 , 反推出其公式 ;
  • ③ 分析 : 成真赋值 为 0 , 0 0,0 0,0 , 合取符号 ∧ \land ∧ 两边都要为 真 , 赋值为 0 , 那么 对应命题变项 要带上 ¬ \lnot ¬ 符号 ;
  • ④ 对应 : 凡是 0 0 0 赋值的 , 带 ¬ \lnot ¬ 符号 ; 凡是 1 1 1 赋值的 , 对应 正常 命题变项 ;

公式成真赋值名称 ¬ p ∧ ¬ q \lnot p \land \lnot q ¬p∧¬q 0 0 0 \quad 0 00 m 0 m_0 m0​ ¬ p ∧ q \lnot p \land q ¬p∧q 0 1 0 \quad 1 01 m 1 m_1 m1​ p ∧ ¬ q p \land \lnot q p∧¬q 1 0 1 \quad 0 10 m 2 m_2 m2​ p ∧ q p \land q p∧q 1 1 1 \quad 1 11 m 3 m_3 m3​ ( 4 ) 三个命题变项 的 极小项

三个命题变项 p , q , r p, q, r p,q,r 的 极小项 :

• 1.先写出 极小项 名称 : 从 0 0 0 开始计数 , m 0 , m 1 , m 2 , m 3 , m 4 , m 5 , m 6 , m 7 m_0, m_1, m_2, m_3, m_4, m_5, m_6, m_7 m0​,m1​,m2​,m3​,m4​,m5​,m6​,m7​ ;
• 2.然后写出成真赋值 : 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 0,1,2,3,4,5,6,7 0,1,2,3,4,5,6,7 对应的二进制形式 , 即 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 000 , 001, 010, 011,100, 101, 110, 111 000,001,010,011,100,101,110,111 ;
• 3.最后写公式 ( 简单合取式 ) :
  • ① 公式形式 : 公式是简单合取式 , p ∧ q ∧ r p \land q \land r p∧q∧r , 其中 每个命题变项 p , q , r p,q,r p,q,r 之前都可能带着 否定符号 ¬ \lnot ¬ ;
  • ② 满足成真赋值 : 该公式需要满足 其 上述 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 000 , 001, 010, 011,100, 101, 110, 111 000,001,010,011,100,101,110,111 赋值是成真赋值 , 即根据成真赋值 , 反推出其公式 ;
  • ③ 分析 : 成真赋值 为 0 , 0 , 0 0,0,0 0,0,0 , 三个命题变项都要为 真 , 赋值为 0 , 那么对应命题变项要带上 ¬ \lnot ¬ 符号 ;
  • ④ 对应 : 凡是 0 0 0 赋值的 , 带 ¬ \lnot ¬ 符号 ; 凡是 1 1 1 赋值的 , 对应 正常 命题变项 ;

公式成真赋值名称 ¬ p ∧ ¬ q ∧ ¬ r \lnot p \land \lnot q \land \lnot r ¬p∧¬q∧¬r 0 0 0 0 \quad 0 \quad 0 000 m 0 m_0 m0​ ¬ p ∧ ¬ q ∧ r \lnot p \land \lnot q \land r ¬p∧¬q∧r 0 0 1 0 \quad 0 \quad 1 001 m 1 m_1 m1​ ¬ p ∧ q ∧ ¬ r \lnot p \land q \land \lnot r ¬p∧q∧¬r 0 1 0 0 \quad 1 \quad 0 010 m 2 m_2 m2​ ¬ p ∧ q ∧ r \lnot p \land q \land r ¬p∧q∧r 0 1 1 0 \quad 1 \quad 1 011 m 3 m_3 m3​ p ∧ ¬ q ∧ ¬ r p \land \lnot q \land \lnot r p∧¬q∧¬r 1 0 0 1 \quad 0 \quad 0 100 m 4 m_4 m4​ p ∧ ¬ q ∧ r p \land \lnot q \land r p∧¬q∧r 1 0 1 1 \quad 0 \quad 1 101 m 5 m_5 m5​ p ∧ q ∧ ¬ r p \land q \land \lnot r p∧q∧¬r 1 1 0 1 \quad 1 \quad 0 110 m 6 m_6 m6​ p ∧ q ∧ r p \land q \land r p∧q∧r 1 1 1 1 \quad 1 \quad 1 111 m 7 m_7 m7​ ( 5 ) 极小项 成真赋值 公式 名称 之间 的 转化 与 推演

极小项 成真赋值 公式 名称 之间 的 转化 与 推演 :

• 1.成真赋值 到 公式 之间的推演 : 公式 的 成真赋值列出 , 就是成真赋值 ; 根据成真赋值 写出 公式 , 0 对应的 命题变项 带 否定 ¬ \lnot ¬ , 1 对应 正常的命题变项 ;
• 2.名称 到 成真赋值 之间的 推演 : 这个 最简单 , 直接将 下标 写成 二进制形式 即可 ;
• 3.公式 到 名称 之间的 推演 : 直接推演 比较困难 , 必须通过 成真赋值 过渡一下 , 先写出 成真赋值 , 然后将其当做 二进制数 转为 十进制的下标即可 ;

3. 极大项 ( 1 ) 极大项 简介

极大项 : 极大项 是 一种 简单析取式 ;

• 1.前提 ( 简单析取式 ) : 含有 n n n 个 命题变项 的 简单析取式 ;
• 2.命题变项出现次数 : 每个命题变项 均 以 文字 的 形式 在其中出现 , 且 仅出现 一次 ;
• 3.命题变项出现位置 : 第 i i i ( 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n ) 个文字出现在 左起 第 i i i 个位置 ;
  • n n n 是指命题变项个数 ;
• 4.极大项总结 : 满足上述三个条件的 简单析取式 , 称为 极大项 ;

( 2 ) 极大项 说明

关于 极大项 的 说明 :

• 1.极大项个数 : n n n 个 命题变元 会 产生 2 n 2^n 2n 个 极大项 ;
• 2.互不等值 : 2 n 2^n 2n 个极大项 均 互不等值 ;
• 3.极大项 : m i m_i mi​ 表示 第 i i i 个极大项 , 其中 i i i 是该极大项 成假赋值 的 十进制表示 ;
• 4.极大项名称 : 第 i i i 个极大项 , 称为 M i M_i Mi​ ;
• 5. m i m_i mi​ 与 M i M_i Mi​ 之间的关系 : ① ¬ m i    ⟺    M i \lnot m_i \iff M_i ¬mi​⟺Mi​ ② ¬ M i    ⟺    m i \lnot M_i \iff m_i ¬Mi​⟺mi​

( 3 ) 两个命题变项的极大项

两个命题变项 p , q p, q p,q 的 极大项 :

• 1.先写出 极大项 名称 : 从 0 0 0 开始计数 , M 0 , M 1 , M 2 , M 3 M_0, M_1, M_2, M_3 M0​,M1​,M2​,M3​ ;
• 2.然后写出成假赋值 : 0 , 1 , 2 , 3 0,1,2,3 0,1,2,3 对应的二进制形式 , 即 00 , 01 , 10 , 11 00 , 01, 10, 11 00,01,10,11 ;
• 3.最后写公式 ( 简单析取式 ) :
  • ① 公式形式 : 公式是简单析取式 , p ∧ q p \land q p∧q , 其中 每个命题变项 p , q p,q p,q 之前都可能带着 否定符号 ¬ \lnot ¬ ;
  • ② 满足成假赋值 : 该公式需要满足 其 上述 00 , 01 , 10 , 11 00 , 01, 10, 11 00,01,10,11 赋值是成假赋值 , 即根据成假赋值 , 反推出其公式 ;
  • ③ 分析 : 成假赋值 为 0 , 0 0,0 0,0 , 合取符号 ∧ \land ∧ 两边都要为 假 , 赋值为 0 , 那么对应的命题变项是 正常的命题变项, 不带否定符号 ¬ \lnot ¬ ;
  • ④ 对应 : 凡是 1 1 1 赋值的 , 带 ¬ \lnot ¬ 符号 ; 凡是 0 0 0 赋值的 , 对应 正常 命题变项 ;

公式成假赋值名称 p ∨ q p \lor q p∨q 0 0 0 \quad 0 00 M 0 M_0 M0​ p ∨ ¬ q p \lor \lnot q p∨¬q 0 1 0 \quad 1 01 M 1 M_1 M1​ ¬ p ∨ q \lnot p \lor q ¬p∨q 1 0 1 \quad 0 10 M 2 M_2 M2​ ¬ p ∨ ¬ q \lnot p \lor \lnot q ¬p∨¬q 1 1 1 \quad 1 11 M 3 M_3 M3​ ( 4 ) 三个命题变项的极大项

三个命题变项 p , q , r p, q, r p,q,r 的 极大项 :

• 1.先写出 极大项 名称 : 从 0 0 0 开始计数 , M 0 , M 1 , M 2 , M 3 , M 4 , M 5 , M 6 , M 7 M_0, M_1, M_2, M_3, M_4, M_5, M_6, M_7 M0​,M1​,M2​,M3​,M4​,M5​,M6​,M7​ ;
• 2.然后写出成假赋值 : 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 0,1,2,3,4,5,6,7 0,1,2,3,4,5,6,7 对应的二进制形式 , 即 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 000 , 001, 010, 011,100, 101, 110, 111 000,001,010,011,100,101,110,111 ;
• 3.最后写公式 ( 简单析取式 ) :
  • ① 公式形式 : 公式是简单析取式 , p ∧ q ∧ r p \land q \land r p∧q∧r , 其中 每个命题变项 p , q , r p,q,r p,q,r 之前 都 可能 带着 否定符号 ¬ \lnot ¬ ;
  • ② 满足成假赋值 : 该公式需要满足 其 上述 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 000 , 001, 010, 011,100, 101, 110, 111 000,001,010,011,100,101,110,111 赋值是成假赋值 , 即根据成真赋值 , 反推出其公式 ;
  • ③ 分析 : 成假赋值 为 0 , 0 , 0 0,0,0 0,0,0 , 三个命题变项都要为 假 , 赋值为 0 , 那么对应命题变项 是正常的命题变项 , 不带否定符号 ¬ \lnot ¬ ;
  • ④ 对应 : 凡是 1 1 1 赋值的 , 带 ¬ \lnot ¬ 符号 ; 凡是 0 0 0 赋值的 , 对应 正常 命题变项 ;

公式成假赋值名称 p ∨ q ∨ r p \lor q \lor r p∨q∨r 0 0 0 0 \quad 0 \quad 0 000 M 0 M_0 M0​ p ∨ q ∨ ¬ r p \lor q \lor \lnot r p∨q∨¬r 0 0 1 0 \quad 0 \quad 1 001 M 1 M_1 M1​ p ∨ ¬ q ∨ r p \lor \lnot q \lor r p∨¬q∨r 0 1 0 0 \quad 1 \quad 0 010 M 2 M_2 M2​ p ∨ ¬ q ∨ ¬ r p \lor \lnot q \lor \lnot r p∨¬q∨¬r 0 1 1 0 \quad 1 \quad 1 011 M 3 M_3 M3​ ¬ p ∨ q ∨ r \lnot p \lor q \lor r ¬p∨q∨r 1 0 0 1 \quad 0 \quad 0 100 M 4 M_4 M4​ ¬ p ∨ q ∨ ¬ r \lnot p \lor q \lor \lnot r ¬p∨q∨¬r 1 0 1 1 \quad 0 \quad 1 101 M 5 M_5 M5​ ¬ p ∨ ¬ q ∨ r \lnot p \lor \lnot q \lor r ¬p∨¬q∨r 1 1 0 1 \quad 1 \quad 0 110 M 6 M_6 M6​ ¬ p ∨ ¬ q ∨ ¬ r \lnot p \lor \lnot q \lor \lnot r ¬p∨¬q∨¬r 1 1 1 1 \quad 1 \quad 1 111 M 7 M_7 M7​ ( 5 ) 极大项 成假赋值 公式 名称 之间 的 转化 与 推演

极大项 成假赋值 公式 名称 之间 的 转化 与 推演 :

• 1.成假赋值 到 公式 之间的推演 : 公式 的 成假赋值列出 , 就是成假赋值 ; 根据成假赋值 写出 公式 , 1 1 1 对应的 命题变项 带 否定 ¬ \lnot ¬ , 0 0 0 对应 正常的命题变项 ;
• 2.名称 到 成假赋值 之间的 推演 : 这个 最简单 , 直接将 下标 写成 二进制形式 即可 ;
• 3.公式 到 名称 之间的 推演 : 直接推演 比较困难 , 必须通过 成假赋值 过渡一下 , 先写出 成假赋值 , 然后将其当做 二进制数 转为 十进制的下标即可 ;

二. 题目解析 1. 使用等值演算方式求 主析取范式 和 主合取范式

题目 : 使用等值演算方式求 主析取范式 和 主合取范式 ;

• 条件 : A = ( p → ¬ q ) → r A = (p \rightarrow \lnot q) \rightarrow r A=(p→¬q)→r
• 问题 1 : 求 主析取范式 和 主合取 范式 ;

解答 :

① 步骤 一 : 求出一个合取范式 :

( p → ¬ q ) → r (p \rightarrow \lnot q) \rightarrow r (p→¬q)→r

( 使用蕴涵等值式 : A → B    ⟺    ¬ A ∨ B A \rightarrow B \iff \lnot A \lor B A→B⟺¬A∨B , 消除 外层的 蕴涵符号 )    ⟺    ¬ ( p → ¬ q ) ∨ r \iff \lnot (p \rightarrow \lnot q) \lor r ⟺¬(p→¬q)∨r

( 使用蕴涵等值式 : A → B    ⟺    ¬ A ∨ B A \rightarrow B \iff \lnot A \lor B A→B⟺¬A∨B , 消除内层的 蕴涵符号 )    ⟺    ¬ ( ¬ p ∨ ¬ q ) ∨ r \iff \lnot (\lnot p \lor \lnot q) \lor r ⟺¬(¬p∨¬q)∨r

( 使用德摩根律 : ¬ ( A ∨ B )    ⟺    ¬ A ∧ ¬ B \lnot (A \lor B) \iff \lnot A \land \lnot B ¬(A∨B)⟺¬A∧¬B , 处理 ¬ ( ¬ p ∨ ¬ q ) \lnot (\lnot p \lor \lnot q) ¬(¬p∨¬q) 部分 )    ⟺    ( p ∧ q ) ∨ r \iff ( p \land q) \lor r ⟺(p∧q)∨r

( 使用交换率 : A ∨ B    ⟺    B ∨ A A \lor B \iff B \lor A A∨B⟺B∨A )    ⟺    r ∨ ( p ∧ q ) \iff r \lor ( p \land q) ⟺r∨(p∧q)

( 使用分配率 : A ∨ ( B ∧ C )    ⟺    ( A ∨ B ) ∧ ( A ∨ C ) A \lor (B \land C) \iff (A \lor B) \land (A \lor C) A∨(B∧C)⟺(A∨B)∧(A∨C) )    ⟺    ( r ∨ p ) ∧ ( r ∨ q ) \iff (r \lor p) \land (r \lor q) ⟺(r∨p)∧(r∨q)

( 使用交换率 : A ∨ B    ⟺    B ∨ A A \lor B \iff B \lor A A∨B⟺B∨A )    ⟺    ( p ∨ r ) ∧ ( q ∨ r ) \iff (p \lor r) \land (q \lor r) ⟺(p∨r)∧(q∨r)

当前状况分析 :

• 1> 合取范式 : 此时 , ( p ∨ r ) ∧ ( q ∨ r ) (p \lor r) \land (q \lor r) (p∨r)∧(q∨r) 是一个合取范式 , 根据该合取范式 求主合取 范式 ;
• 2> 拆分 : 分别将 ( p ∨ r ) (p \lor r) (p∨r) 和 ( q ∨ r ) (q \lor r) (q∨r) 转为 极大项 ;

② 步骤二 : 将 ( p ∨ r ) (p \lor r) (p∨r) 转为 主合取范式 :

( p ∨ r ) (p \lor r) (p∨r)

( 使用 零律 : A ∨ 0    ⟺    A A \lor 0 \iff A A∨0⟺A , 析取式 , 析取一个 0 0 0 后 , 其值不变 )    ⟺    ( p ∨ 0 ∨ r ) \iff (p \lor 0 \lor r) ⟺(p∨0∨r)

( 使用 矛盾律 : A ∧ A = 0 A \land A = 0 A∧A=0 , 引入 命题变元 q q q , 即使用 A ∧ A A \land A A∧A 替换 式子中的 0 0 0 )    ⟺    ( p ∨ ( q ∧ ¬ q ) ∨ r ) \iff (p \lor ( q \land \lnot q ) \lor r) ⟺(p∨(q∧¬q)∨r)

( 使用交换律 A ∨ B    ⟺    B ∨ A A \lor B \iff B \lor A A∨B⟺B∨A 和 结合律 ( A ∨ B ) ∨ C    ⟺    A ∨ ( B ∨ C ) (A \lor B) \lor C \iff A \lor (B \lor C) (A∨B)∨C⟺A∨(B∨C) )    ⟺    ( ( p ∨ r ) ∨ ( q ∧ ¬ q ) ) \iff ( ( p \lor r ) \lor ( q \land \lnot q ) ) ⟺((p∨r)∨(q∧¬q))

( 使用分配律 : A ∨ ( B ∧ C )    ⟺    ( A ∧ B ) ∨ ( A ∧ C ) A \lor (B \land C) \iff (A \land B) \lor (A \land C) A∨(B∧C)⟺(A∧B)∨(A∧C) , 将 p , q , r p,q,r p,q,r 都集合到一个析取式中 )    ⟺    ( p ∨ r ∨ q ) ∧ ( p ∨ r ∨ ¬ q ) \iff (p \lor r \lor q) \land (p \lor r \lor \lnot q) ⟺(p∨r∨q)∧(p∨r∨¬q)

( 使用交换律 )    ⟺    ( p ∨ q ∨ r ) ∧ ( p ∨ ¬ q ∨ r ) \iff (p \lor q \lor r) \land (p \lor \lnot q \lor r) ⟺(p∨q∨r)∧(p∨¬q∨r)

根据 极大项 公式 写出对应序号 :

• 1> ( p ∨ q ∨ r ) (p \lor q \lor r) (p∨q∨r) : 成假赋值 0 0 0 0 \quad 0 \quad 0 000 , 是极大项 M 0 M_0 M0​ ;
• 2> ( p ∨ ¬ q ∨ r ) (p \lor \lnot q \lor r) (p∨¬q∨r) : 成假赋值 0 1 0 0 \quad 1 \quad 0 010 , 是极大项 M 2 M_2 M2​ ;
• 3> ( p ∨ r ) (p \lor r) (p∨r) 对应的 主合取范式是 : ( p ∨ q ∨ r ) ∧ ( p ∨ ¬ q ∨ r )    ⟺    M 0 ∧ M 2 (p \lor q \lor r) \land (p \lor \lnot q \lor r) \iff M_0 \land M_2 (p∨q∨r)∧(p∨¬q∨r)⟺M0​∧M2​

③ 步骤三 : 将 ( q ∨ r ) (q \lor r) (q∨r) 转为 主合取范式 :

( q ∨ r ) (q \lor r) (q∨r)

( 使用 零律 : A ∨ 0    ⟺    A A \lor 0 \iff A A∨0⟺A , 析取式 , 析取一个 0 0 0 后 , 其值不变 )    ⟺    ( 0 ∨ q ∨ r ) \iff (0 \lor q \lor r) ⟺(0∨q∨r)

( 使用 矛盾律 : A ∧ A = 0 A \land A = 0 A∧A=0 , 引入 命题变元 q q q , 即使用 A ∧ A A \land A A∧A 替换 式子中的 0 0 0 )    ⟺    ( ( p ∧ ¬ p ) ∨ q ∨ r ) \iff (( p \land \lnot p ) \lor q \lor r) ⟺((p∧¬p)∨q∨r)

( 使用分配律 : A ∨ ( B ∧ C )    ⟺    ( A ∧ B ) ∨ ( A ∧ C ) A \lor (B \land C) \iff (A \land B) \lor (A \land C) A∨(B∧C)⟺(A∧B)∨(A∧C) , 将 p , q , r p,q,r p,q,r 都集合到一个析取式中 )    ⟺    ( p ∨ r ∨ q ) ∧ ( ¬ p ∨ r ∨ q ) \iff (p \lor r \lor q) \land (\lnot p \lor r \lor q) ⟺(p∨r∨q)∧(¬p∨r∨q)

根据 极大项 公式 写出对应序号 :

• 1> ( p ∨ q ∨ r ) (p \lor q \lor r) (p∨q∨r) : 成假赋值 0 0 0 0 \quad 0 \quad 0 000 , 是极大项 M 0 M_0 M0​ ;
• 2> ( ¬ p ∨ q ∨ r ) (\lnot p \lor q \lor r) (¬p∨q∨r) : 成假赋值 1 0 0 1 \quad 0 \quad 0 100 , 是极大项 M 4 M_4 M4​ ;
• 3> ( p ∨ r ) (p \lor r) (p∨r) 对应的 主合取范式是 : ( p ∨ q ∨ r ) ∧ ( ¬ p ∨ q ∨ r )    ⟺    M 0 ∧ M 4 (p \lor q \lor r) \land (\lnot p \lor q \lor r) \iff M_0 \land M_4 (p∨q∨r)∧(¬p∨q∨r)⟺M0​∧M4​

该题目最终结果 :

( p → ¬ q ) (p \rightarrow \lnot q) (p→¬q)

( 步骤一 的结论 )    ⟺    ( p ∨ r ) ∧ ( q ∨ r ) \iff (p \lor r) \land (q \lor r) ⟺(p∨r)∧(q∨r)

( 将步骤二 和 步骤三 结果代入到上式中 )    ⟺    ( M 0 ∧ M 2 ) ∧ ( M 0 ∧ M 4 ) \iff (M_0 \land M_2) \land (M_0 \land M_4) ⟺(M0​∧M2​)∧(M0​∧M4​)

( 根据结合律 可以消去括号 将 M 0 ∧ M 0 M_0 \land M_0 M0​∧M0​ 组合起来 )    ⟺    ( M 0 ∧ M 0 ) ∧ M 2 ∧ M 4 \iff ( M_0 \land M_0 ) \land M_2 \land M_4 ⟺(M0​∧M0​)∧M2​∧M4​

( 根据 幂等律 : A ∧ A    ⟺    A A \land A \iff A A∧A⟺A , 可以消去 一个 M 0 M_0 M0​ )    ⟺    M 0 ∧ M 2 ∧ M 4 \iff M_0 \land M_2 \land M_4 ⟺M0​∧M2​∧M4​

2. 使用 真值表法 求 主析取范式 和 主合取范式

题目 : 使用 真值表法 求 主析取范式 和 主合取范式 ;

• 条件 : A = ( p → ¬ q ) → r A = (p \rightarrow \lnot q) \rightarrow r A=(p→¬q)→r
• 问题 1 : 求 主析取范式 和 主合取 范式 ;

解答 :

① 首先列出其真值表 ( 列的真值表越详细越好 , 算错好几次 )

p q r p \quad q \quad r pqr ( ¬ q ) (\lnot q) (¬q) ( p → ¬ q ) (p \rightarrow \lnot q) (p→¬q) A = ( p → ¬ q ) → r A=(p \rightarrow \lnot q) \rightarrow r A=(p→¬q)→r极小项极大项 0 0 0 0 \quad 0 \quad 0 000 1 1 1 1 1 1 0 0 0 m 0 m_0 m0​ M 0 M_0 M0​ 0 0 1 0 \quad 0 \quad 1 001 1 1 1 1 1 1 1 1 1 m 1 m_1 m1​ M 1 M_1 M1​ 0 1 0 0 \quad 1 \quad 0 010 0 0 0 1 1 1 0 0 0 m 2 m_2 m2​ M 2 M_2 M2​ 0 1 1 0 \quad 1 \quad 1 011 0 0 0 1 1 1 1 1 1 m 3 m_3 m3​ M 3 M_3 M3​ 1 0 0 1 \quad 0 \quad 0 100 1 1 1 1 1 1 0 0 0 m 4 m_4 m4​ M 4 M_4 M4​ 1 0 1 1 \quad 0 \quad 1 101 1 1 1 1 1 1 1 1 1 m 5 m_5 m5​ M 5 M_5 M5​ 1 1 0 1 \quad 1 \quad 0 110 0 0 0 0 0 0 1 1 1 m 6 m_6 m6​ M 6 M_6 M6​ 1 1 1 1 \quad 1 \quad 1 111 0 0 0 0 0 0 1 1 1 m 7 m_7 m7​ M 7 M_7 M7​

② 真值表中 取值为 真 的项 对应的 极小项 m i m_i mi​ 构成 主析取范式 ; m 1 ∨ m 3 ∨ m 5 ∨ m 6 ∨ m 7 m_1 \lor m_3 \lor m_5 \lor m_6 \lor m_7 m1​∨m3​∨m5​∨m6​∨m7​

③ 真值表中 取值为 假 的项 对应的 极大项 m i m_i mi​ 构成 主合取范式 ; M 0 ∧ M 2 ∧ M 4 M_0 \land M_2 \land M_4 M0​∧M2​∧M4​

极小项 - 合取式 - 成真赋值 - 对应条件真值表中的 1 1 1 - 主析取范式 ( 多个合取式的析取式 )

极大项 - 析取式 - 成假赋值 - 对应条件真值表中的 0 0 0 - 主合取范式 ( 多个析取式的合取式 )