【数理逻辑】范式 ( 合取范式

2023-12-26 21:35| 来源: 网络整理| 查看: 265

文章目录一. 相关概念1. 简单析取合取式( 1 ) 简单合取式( 2 ) 简单析取式 2. 极小项( 1 ) 极小项简介( 2 ) 极小项说明( 3 ) 两个命题变项的极小项( 4 ) 三个命题变项的极小项( 5 ) 极小项成真赋值公式名称之间的转化与推演 3. 极大项( 1 ) 极大项简介( 2 ) 极大项说明( 3 ) 两个命题变项的极大项( 4 ) 三个命题变项的极大项( 5 ) 极大项成假赋值公式名称之间的转化与推演二. 题目解析1. 使用等值演算方式求主析取范式和主合取范式2. 使用真值表法求主析取范式和主合取范式

一. 相关概念 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 - 主合取范式 ( 多个析取式的合取式 )

【本文地址】

公司简介

联系我们