【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 )
【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 )
文章目录
一. 相关概念
1. 简单 析取 合取 式
( 1 ) 简单合取式
简单合取式 :
- 1.组成 : 命题变元 (
) 或 命题变元否定式 (
) ;
- 2.概念 : 有限个 命题变元 或其 否定式 组成的合取式 , 称为 简单合取式 ;
- 3.示例 :
- ① 单个命题变元 :
p ;
- ② 单个命题变元否定式 :
\lnot p - ③ 两个 命题变元 或其否定式 构成的合取式 :
p \land \lnot q - ④ 三个 命题变元 或其否定式 构成的合取式 :
p \land q \land r
( 2 ) 简单析取式
简单析取式 :
- 1.组成 : 命题变元 (
) 或 命题变元否定式 (
) ;
- 2.概念 : 有限个 命题变元 或其 否定式 组成的析取式 , 称为 简单析取式 ;
- 3.示例 :
- ① 单个命题变元 :
p ;
- ② 单个命题变元否定式 :
\lnot p - ③ 两个 命题变元 或其否定式 构成的析取式 :
p \lor \lnot q - ④ 三个 命题变元 或其否定式 构成的析取式 :
p \lor q \lor r
2. 极小项
( 1 ) 极小项 简介
极小项 : 极小项 是 一种 简单合取式 ;
- 1.前提 ( 简单合取式 ) : 含有
个 命题变项 的 简单合取式 ;
- 2.命题变项出现次数 : 每个命题变项 均 以 文字 的 形式 在其中出现 , 且 仅出现 一次 ;
- 3.命题变项出现位置 : 第
(
) 个文字出现在 左起 第
个位置 ;
是指命题变项个数 ;
- 4.极小项总结 : 满足上述三个条件的 简单合取式 , 称为 极小项 ;
- 5.
与
之间的关系 : ①
②
( 2 ) 极小项 说明
关于 极小项 的 说明 :
- 1.极小项个数 :
个 命题变元 会 产生
个 极小项 ;
- 2.互不等值 :
个极小项 均 互不等值 ;
- 3.极小项 :
表示 第
个极小项 , 其中
是该极小项 成真赋值 的 十进制表示 ;
- 4.极小项名称 : 第
个极小项 , 称为
;
( 3 ) 两个命题变项 的 极小项
两个命题变项
的 极小项 :
- 1.先写出 极小项 名称 : 从
开始计数 ,
;
- 2.然后写出成真赋值 :
对应的二进制形式 , 即
;
- 3.最后写公式 ( 简单合取式 ) :
- ① 公式形式 : 公式是简单合取式 ,
p \land q , 其中 每个命题变项
p,q 之前都可能带着 否定符号
\lnot ;
- ② 满足成真赋值 : 该公式需要满足 其 上述
00 , 01, 10, 11 赋值是成真赋值 , 即根据成真赋值 , 反推出其公式 ;
- ③ 分析 : 成真赋值 为
0,0 , 合取符号
\land 两边都要为 真 , 赋值为 0 , 那么 对应命题变项 要带上
\lnot 符号 ;
- ④ 对应 : 凡是
0 赋值的 , 带
\lnot 符号 ; 凡是
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 ) 三个命题变项 的 极小项
三个命题变项
的 极小项 :
- 1.先写出 极小项 名称 : 从
开始计数 ,
;
- 2.然后写出成真赋值 :
对应的二进制形式 , 即
;
- 3.最后写公式 ( 简单合取式 ) :
- ① 公式形式 : 公式是简单合取式 ,
p \land q \land r , 其中 每个命题变项
p,q,r 之前都可能带着 否定符号
\lnot ;
- ② 满足成真赋值 : 该公式需要满足 其 上述
000 , 001, 010, 011,100, 101, 110, 111 赋值是成真赋值 , 即根据成真赋值 , 反推出其公式 ;
- ③ 分析 : 成真赋值 为
0,0,0 , 三个命题变项都要为 真 , 赋值为 0 , 那么对应命题变项要带上
\lnot 符号 ;
- ④ 对应 : 凡是
0 赋值的 , 带
\lnot 符号 ; 凡是
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 对应的 命题变项 带 否定
, 1 对应 正常的命题变项 ;
- 2.名称 到 成真赋值 之间的 推演 : 这个 最简单 , 直接将 下标 写成 二进制形式 即可 ;
- 3.公式 到 名称 之间的 推演 : 直接推演 比较困难 , 必须通过 成真赋值 过渡一下 , 先写出 成真赋值 , 然后将其当做 二进制数 转为 十进制的下标即可 ;
3. 极大项
( 1 ) 极大项 简介
极大项 : 极大项 是 一种 简单析取式 ;
- 1.前提 ( 简单析取式 ) : 含有
个 命题变项 的 简单析取式 ;
- 2.命题变项出现次数 : 每个命题变项 均 以 文字 的 形式 在其中出现 , 且 仅出现 一次 ;
- 3.命题变项出现位置 : 第
(
) 个文字出现在 左起 第
个位置 ;
是指命题变项个数 ;
- 4.极大项总结 : 满足上述三个条件的 简单析取式 , 称为 极大项 ;
( 2 ) 极大项 说明
关于 极大项 的 说明 :
- 1.极大项个数 :
个 命题变元 会 产生
个 极大项 ;
- 2.互不等值 :
个极大项 均 互不等值 ;
- 3.极大项 :
表示 第
个极大项 , 其中
是该极大项 成假赋值 的 十进制表示 ;
- 4.极大项名称 : 第
个极大项 , 称为
;
- 5.
与
之间的关系 : ①
②
( 3 ) 两个命题变项的极大项
两个命题变项
的 极大项 :
- 1.先写出 极大项 名称 : 从
开始计数 ,
;
- 2.然后写出成假赋值 :
对应的二进制形式 , 即
;
- 3.最后写公式 ( 简单析取式 ) :
- ① 公式形式 : 公式是简单析取式 ,
p \land q , 其中 每个命题变项
p,q 之前都可能带着 否定符号
\lnot ;
- ② 满足成假赋值 : 该公式需要满足 其 上述
00 , 01, 10, 11 赋值是成假赋值 , 即根据成假赋值 , 反推出其公式 ;
- ③ 分析 : 成假赋值 为
0,0 , 合取符号
\land 两边都要为 假 , 赋值为 0 , 那么对应的命题变项是 正常的命题变项, 不带否定符号
\lnot ;
- ④ 对应 : 凡是
1 赋值的 , 带
\lnot 符号 ; 凡是
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 ) 三个命题变项的极大项
三个命题变项
的 极大项 :
- 1.先写出 极大项 名称 : 从
开始计数 ,
;
- 2.然后写出成假赋值 :
对应的二进制形式 , 即
;
- 3.最后写公式 ( 简单析取式 ) :
- ① 公式形式 : 公式是简单析取式 ,
p \land q \land r , 其中 每个命题变项
p,q,r 之前 都 可能 带着 否定符号
\lnot ;
- ② 满足成假赋值 : 该公式需要满足 其 上述
000 , 001, 010, 011,100, 101, 110, 111 赋值是成假赋值 , 即根据成真赋值 , 反推出其公式 ;
- ③ 分析 : 成假赋值 为
0,0,0 , 三个命题变项都要为 假 , 赋值为 0 , 那么对应命题变项 是正常的命题变项 , 不带否定符号
\lnot ;
- ④ 对应 : 凡是
1 赋值的 , 带
\lnot 符号 ; 凡是
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.成假赋值 到 公式 之间的推演 : 公式 的 成假赋值列出 , 就是成假赋值 ; 根据成假赋值 写出 公式 ,
对应的 命题变项 带 否定
,
对应 正常的命题变项 ;
- 2.名称 到 成假赋值 之间的 推演 : 这个 最简单 , 直接将 下标 写成 二进制形式 即可 ;
- 3.公式 到 名称 之间的 推演 : 直接推演 比较困难 , 必须通过 成假赋值 过渡一下 , 先写出 成假赋值 , 然后将其当做 二进制数 转为 十进制的下标即可 ;
二. 题目解析
1. 使用等值演算方式求 主析取范式 和 主合取范式
题目 : 使用等值演算方式求 主析取范式 和 主合取范式 ;
- 条件 :
- 问题 1 : 求 主析取范式 和 主合取 范式 ;
解答 :
① 步骤 一 : 求出一个合取范式 :
( 使用蕴涵等值式 :
, 消除 外层的 蕴涵符号 )
( 使用蕴涵等值式 :
, 消除内层的 蕴涵符号 )
( 使用德摩根律 :
, 处理
部分 )
( 使用交换率 :
)
( 使用分配率 :
)
( 使用交换率 :
)
当前状况分析 :
- 1> 合取范式 : 此时 ,
是一个合取范式 , 根据该合取范式 求主合取 范式 ;
- 2> 拆分 : 分别将
和
转为 极大项 ;
② 步骤二 : 将
转为 主合取范式 :
( 使用 零律 :
, 析取式 , 析取一个
后 , 其值不变 )
( 使用 矛盾律 :
, 引入 命题变元
, 即使用
替换 式子中的
)
( 使用交换律
和 结合律
)
( 使用分配律 :
, 将
都集合到一个析取式中 )
( 使用交换律 )
根据 极大项 公式 写出对应序号 :
- 1>
: 成假赋值
, 是极大项
;
- 2>
: 成假赋值
, 是极大项
;
- 3>
对应的 主合取范式是 :
③ 步骤三 : 将
转为 主合取范式 :
( 使用 零律 :
, 析取式 , 析取一个
后 , 其值不变 )
( 使用 矛盾律 :
, 引入 命题变元
, 即使用
替换 式子中的
)
( 使用分配律 :
, 将
都集合到一个析取式中 )
根据 极大项 公式 写出对应序号 :
- 1>
: 成假赋值
, 是极大项
;
- 2>
: 成假赋值
, 是极大项
;
- 3>
对应的 主合取范式是 :
该题目最终结果 :
( 步骤一 的结论 )
( 将步骤二 和 步骤三 结果代入到上式中 )
( 根据结合律 可以消去括号 将
组合起来 )
( 根据 幂等律 :
, 可以消去 一个
)
2. 使用 真值表法 求 主析取范式 和 主合取范式
题目 : 使用 真值表法 求 主析取范式 和 主合取范式 ;
- 条件 :
- 问题 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 |
极小项极大项
② 真值表中 取值为 真 的项 对应的 极小项
构成 主析取范式 ;
③ 真值表中 取值为 假 的项 对应的 极大项
构成 主合取范式 ;
极小项 - 合取式 - 成真赋值 - 对应条件真值表中的
- 主析取范式 ( 多个合取式的析取式 )
极大项 - 析取式 - 成假赋值 - 对应条件真值表中的
- 主合取范式 ( 多个析取式的合取式 )
腾讯云开发者
