文章/答案/技术大牛

发布

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

韩曙亮

发布于 2023-03-27 08:20:26

2.5K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一. 相关概念

1. 简单析取合取式

( 1 ) 简单合取式

简单合取式 :

1.组成 : 命题变元 (

) 或 命题变元否定式 (

\lnot p

) ;

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

( 2 ) 简单析取式

简单析取式 :

1.组成 : 命题变元 (

) 或 命题变元否定式 (

\lnot p

) ;

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

2. 极小项

( 1 ) 极小项简介

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

1.前提 ( 简单合取式 ) : 含有

个命题变项 的 简单合取式 ;

2.命题变项出现次数 : 每个命题变项均 以文字的形式在其中出现 , 且 仅出现一次 ;
3.命题变项出现位置 : 第

(

1 \leq i \leq n

) 个文字出现在左起第

个位置 ;

是指命题变项个数 ;

4.极小项总结 : 满足上述三个条件的简单合取式 , 称为极小项 ;
5.

m_i

与

M_i

之间的关系 : ①

\lnot m_i \iff M_i

②

\lnot M_i \iff m_i

( 2 ) 极小项说明

关于极小项的说明 :

1.极小项个数 :

个命题变元会产生

2^n

个极小项 ;

2.互不等值 :

2^n

个极小项均互不等值 ;

3.极小项 :

m_i

表示第

个极小项 , 其中

是该极小项成真赋值的十进制表示 ;

4.极小项名称 : 第

个极小项 , 称为

m_i

;

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

两个命题变项

p, q

的极小项 :

1.先写出极小项名称 : 从

开始计数 ,

m_0, m_1, m_2, m_3

;

2.然后写出成真赋值 :

0,1,2,3

对应的二进制形式 , 即

00 , 01, 10, 11

;

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

\lnot p \land \lnot q

0 \quad 0

m_0

\lnot p \land q

0 \quad 1

m_1

p \land \lnot q

1 \quad 0

m_2

p \land q

1 \quad 1

m_3

( 4 ) 三个命题变项的极小项

三个命题变项

p, q, r

的极小项 :

1.先写出极小项名称 : 从

开始计数 ,

m_0, m_1, m_2, m_3, m_4, m_5, m_6, m_7

;

2.然后写出成真赋值 :

0,1,2,3,4,5,6,7

对应的二进制形式 , 即

000 , 001, 010, 011,100, 101, 110, 111

;

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

\lnot p \land \lnot q \land \lnot r

0 \quad 0 \quad 0

m_0

\lnot p \land \lnot q \land r

0 \quad 0 \quad 1

m_1

\lnot p \land q \land \lnot r

0 \quad 1 \quad 0

m_2

\lnot p \land q \land r

0 \quad 1 \quad 1

m_3

p \land \lnot q \land \lnot r

1 \quad 0 \quad 0

m_4

p \land \lnot q \land r

1 \quad 0 \quad 1

m_5

p \land q \land \lnot r

1 \quad 1 \quad 0

m_6

p \land q \land r

1 \quad 1 \quad 1

m_7

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

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

1.成真赋值到公式之间的推演 : 公式的成真赋值列出 , 就是成真赋值 ; 根据成真赋值写出公式 , 0 对应的命题变项带否定

\lnot

, 1 对应正常的命题变项 ;

2.名称到成真赋值之间的推演 : 这个最简单 , 直接将下标写成二进制形式即可 ;
3.公式到名称之间的推演 : 直接推演比较困难 , 必须通过成真赋值过渡一下 , 先写出成真赋值 , 然后将其当做二进制数转为十进制的下标即可 ;

3. 极大项

( 1 ) 极大项简介

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

1.前提 ( 简单析取式 ) : 含有

个命题变项 的 简单析取式 ;

2.命题变项出现次数 : 每个命题变项均 以文字的形式在其中出现 , 且 仅出现一次 ;
3.命题变项出现位置 : 第

(

1 \leq i \leq n

) 个文字出现在左起第

个位置 ;

是指命题变项个数 ;

4.极大项总结 : 满足上述三个条件的简单析取式 , 称为极大项 ;

( 2 ) 极大项说明

关于极大项的说明 :

1.极大项个数 :

个命题变元会产生

2^n

个极大项 ;

2.互不等值 :

2^n

个极大项均互不等值 ;

3.极大项 :

m_i

表示第

个极大项 , 其中

是该极大项成假赋值的十进制表示 ;

4.极大项名称 : 第

个极大项 , 称为

M_i

;

m_i

与

M_i

之间的关系 : ①

\lnot m_i \iff M_i

②

\lnot M_i \iff m_i

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

两个命题变项

p, q

的极大项 :

1.先写出极大项名称 : 从

开始计数 ,

M_0, M_1, M_2, M_3

;

2.然后写出成假赋值 :

0,1,2,3

对应的二进制形式 , 即

00 , 01, 10, 11

;

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

p \lor q

0 \quad 0

M_0

p \lor \lnot q

0 \quad 1

M_1

\lnot p \lor q

1 \quad 0

M_2

\lnot p \lor \lnot q

1 \quad 1

M_3

( 4 ) 三个命题变项的极大项

三个命题变项

p, q, r

的极大项 :

1.先写出极大项名称 : 从

开始计数 ,

M_0, M_1, M_2, M_3, M_4, M_5, M_6, M_7

;

2.然后写出成假赋值 :

0,1,2,3,4,5,6,7

对应的二进制形式 , 即

000 , 001, 010, 011,100, 101, 110, 111

;

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

p \lor q \lor r

0 \quad 0 \quad 0

M_0

p \lor q \lor \lnot r

0 \quad 0 \quad 1

M_1

p \lor \lnot q \lor r

0 \quad 1 \quad 0

M_2

p \lor \lnot q \lor \lnot r

0 \quad 1 \quad 1

M_3

\lnot p \lor q \lor r

1 \quad 0 \quad 0

M_4

\lnot p \lor q \lor \lnot r

1 \quad 0 \quad 1

M_5

\lnot p \lor \lnot q \lor r

1 \quad 1 \quad 0

M_6

\lnot p \lor \lnot q \lor \lnot r

1 \quad 1 \quad 1

M_7

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

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

1.成假赋值到公式之间的推演 : 公式的成假赋值列出 , 就是成假赋值 ; 根据成假赋值写出公式 ,

对应的命题变项带否定

\lnot

对应正常的命题变项 ;

2.名称到成假赋值之间的推演 : 这个最简单 , 直接将下标写成二进制形式即可 ;
3.公式到名称之间的推演 : 直接推演比较困难 , 必须通过成假赋值过渡一下 , 先写出成假赋值 , 然后将其当做二进制数转为十进制的下标即可 ;

二. 题目解析

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

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

条件 :

A = (p \rightarrow \lnot q) \rightarrow r

问题 1 : 求 主析取范式 和 主合取范式 ;

解答 :

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

(p \rightarrow \lnot q) \rightarrow r

( 使用蕴涵等值式 :

A \rightarrow B \iff \lnot A \lor B

, 消除外层的蕴涵符号 )

\iff \lnot (p \rightarrow \lnot q) \lor r

( 使用蕴涵等值式 :

A \rightarrow B \iff \lnot A \lor B

, 消除内层的蕴涵符号 )

\iff \lnot (\lnot p \lor \lnot q) \lor r

( 使用德摩根律 :

\lnot (A \lor B) \iff \lnot A \land \lnot B

, 处理

\lnot (\lnot p \lor \lnot q)

部分 )

\iff ( p \land q) \lor r

( 使用交换率 :

A \lor B \iff B \lor A

)

\iff r \lor ( p \land q)

( 使用分配率 :

A \lor (B \land C) \iff (A \lor B) \land (A \lor C)

)

\iff (r \lor p) \land (r \lor q)

( 使用交换率 :

A \lor B \iff B \lor A

)

\iff (p \lor r) \land (q \lor r)

当前状况分析 :

1> 合取范式 : 此时 ,

(p \lor r) \land (q \lor r)

是一个合取范式 , 根据该合取范式求主合取范式 ;

2> 拆分 : 分别将

(p \lor r)

和

(q \lor r)

转为极大项 ;

② 步骤二 : 将

(p \lor r)

转为主合取范式 :

(p \lor r)

( 使用零律 :

A \lor 0 \iff A

, 析取式 , 析取一个

后 , 其值不变 )

\iff (p \lor 0 \lor r)

( 使用矛盾律 :

A \land A = 0

, 引入命题变元

, 即使用

A \land A

替换式子中的

)

\iff (p \lor ( q \land \lnot q ) \lor r)

( 使用交换律

A \lor B \iff B \lor A

和结合律

(A \lor B) \lor C \iff A \lor (B \lor C)

)

\iff ( ( p \lor r ) \lor ( q \land \lnot q ) )

( 使用分配律 :

A \lor (B \land C) \iff (A \land B) \lor (A \land C)

, 将

p,q,r

都集合到一个析取式中 )

\iff (p \lor r \lor q) \land (p \lor r \lor \lnot q)

( 使用交换律 )

\iff (p \lor q \lor r) \land (p \lor \lnot q \lor r)

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

(p \lor q \lor r)

: 成假赋值

0 \quad 0 \quad 0

, 是极大项

M_0

;

(p \lor \lnot q \lor r)

: 成假赋值

0 \quad 1 \quad 0

, 是极大项

M_2

;

(p \lor r)

对应的主合取范式是 :

(p \lor q \lor r) \land (p \lor \lnot q \lor r) \iff M_0 \land M_2

③ 步骤三 : 将

(q \lor r)

转为主合取范式 :

(q \lor r)

( 使用零律 :

A \lor 0 \iff A

, 析取式 , 析取一个

后 , 其值不变 )

\iff (0 \lor q \lor r)

( 使用矛盾律 :

A \land A = 0

, 引入命题变元

, 即使用

A \land A

替换式子中的

)

\iff (( p \land \lnot p ) \lor q \lor r)

( 使用分配律 :

A \lor (B \land C) \iff (A \land B) \lor (A \land C)

, 将

p,q,r

都集合到一个析取式中 )

\iff (p \lor r \lor q) \land (\lnot p \lor r \lor q)

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

(p \lor q \lor r)

: 成假赋值

0 \quad 0 \quad 0

, 是极大项

M_0

;

(\lnot p \lor q \lor r)

: 成假赋值

1 \quad 0 \quad 0

, 是极大项

M_4

;

(p \lor r)

对应的主合取范式是 :

(p \lor q \lor r) \land (\lnot p \lor q \lor r) \iff M_0 \land M_4

该题目最终结果 :

(p \rightarrow \lnot q)

( 步骤一的结论 )

\iff (p \lor r) \land (q \lor r)

( 将步骤二和步骤三结果代入到上式中 )

\iff (M_0 \land M_2) \land (M_0 \land M_4)

( 根据结合律可以消去括号将

M_0 \land M_0

组合起来 )

\iff ( M_0 \land M_0 ) \land M_2 \land M_4

( 根据幂等律 :

A \land A \iff A

, 可以消去一个

M_0

)

\iff M_0 \land M_2 \land M_4

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

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

条件 :

A = (p \rightarrow \lnot q) \rightarrow 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