文章/答案/技术大牛

发布

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

韩曙亮

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

2.5K0

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

文章目录

一. 相关概念

1. 简单析取合取式

( 1 ) 简单合取式

简单合取式 :

1.组成 : 命题变元 (

p

$p$

) 或 命题变元否定式 (

\neg p

$\lnot p$

) ;

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

( 2 ) 简单析取式

简单析取式 :

1.组成 : 命题变元 (

p

$p$

) 或 命题变元否定式 (

\neg p

$\lnot p$

) ;

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

2. 极小项

( 1 ) 极小项简介

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

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

n

$n$

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

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

i

$i$

(

1 \leq i \leq n

$1 \leq i \leq n$

) 个文字出现在左起第

i

$i$

个位置 ;

n

$n$

是指命题变项个数 ;

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

m_{i}

$m_i$

与

M_{i}

$M_i$

之间的关系 : ①

\neg m_{i} ⟺ M_{i}

$\lnot m_i \iff M_i$

②

\neg M_{i} ⟺ m_{i}

$\lnot M_i \iff m_i$

( 2 ) 极小项说明

关于极小项的说明 :

1.极小项个数 :

n

$n$

个命题变元会产生

2^{n}

$2^n$

个极小项 ;

2.互不等值 :

2^{n}

$2^n$

个极小项均互不等值 ;

3.极小项 :

m_{i}

$m_i$

表示第

i

$i$

个极小项 , 其中

i

$i$

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

4.极小项名称 : 第

i

$i$

个极小项 , 称为

m_{i}

$m_i$

;

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

两个命题变项

p, q

$p, q$

的极小项 :

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

0

$0$

开始计数 ,

m_{0}, m_{1}, m_{2}, m_{3}

$m_0, m_1, m_2, m_3$

;

2.然后写出成真赋值 :

0, 1, 2, 3

$0,1,2,3$

对应的二进制形式 , 即

00, 01, 10, 11

$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

\neg p \land \neg q

$\lnot p \land \lnot q$

00

$0 \quad 0$

m_{0}

$m_0$

\neg p \land q

$\lnot p \land q$

01

$0 \quad 1$

m_{1}

$m_1$

p \land \neg q

$p \land \lnot q$

10

$1 \quad 0$

m_{2}

$m_2$

p \land q

$p \land q$

11

$1 \quad 1$

m_{3}

$m_3$

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

三个命题变项

p, q, r

$p, q, r$

的极小项 :

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

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$

;

2.然后写出成真赋值 :

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$

;

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

\neg p \land \neg q \land \neg r

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

000

$0 \quad 0 \quad 0$

m_{0}

$m_0$

\neg p \land \neg q \land r

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

001

$0 \quad 0 \quad 1$

m_{1}

$m_1$

\neg p \land q \land \neg r

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

010

$0 \quad 1 \quad 0$

m_{2}

$m_2$

\neg p \land q \land r

$\lnot p \land q \land r$

011

$0 \quad 1 \quad 1$

m_{3}

$m_3$

p \land \neg q \land \neg r

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

100

$1 \quad 0 \quad 0$

m_{4}

$m_4$

p \land \neg q \land r

$p \land \lnot q \land r$

101

$1 \quad 0 \quad 1$

m_{5}

$m_5$

p \land q \land \neg r

$p \land q \land \lnot r$

110

$1 \quad 1 \quad 0$

m_{6}

$m_6$

p \land q \land r

$p \land q \land r$

111

$1 \quad 1 \quad 1$

m_{7}

$m_7$

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

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

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

\neg

$\lnot$

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

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

3. 极大项

( 1 ) 极大项简介

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

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

n

$n$

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

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

i

$i$

(

1 \leq i \leq n

$1 \leq i \leq n$

) 个文字出现在左起第

i

$i$

个位置 ;

n

$n$

是指命题变项个数 ;

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

( 2 ) 极大项说明

关于极大项的说明 :

1.极大项个数 :

n

$n$

个命题变元会产生

2^{n}

$2^n$

个极大项 ;

2.互不等值 :

2^{n}

$2^n$

个极大项均互不等值 ;

3.极大项 :

m_{i}

$m_i$

表示第

i

$i$

个极大项 , 其中

i

$i$

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

4.极大项名称 : 第

i

$i$

个极大项 , 称为

M_{i}

$M_i$

;

$m_i$

与

$M_i$

之间的关系 : ①

$\lnot m_i \iff M_i$

②

$\lnot M_i \iff m_i$

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

两个命题变项

$p, q$

的极大项 :

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

$0$

开始计数 ,

$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.先写出极大项名称 : 从

$0$

开始计数 ,

$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.成假赋值到公式之间的推演 : 公式的成假赋值列出 , 就是成假赋值 ; 根据成假赋值写出公式 ,

$1$

对应的命题变项带否定

$\lnot$

$0$

对应正常的命题变项 ;

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$

, 析取式 , 析取一个

$0$

后 , 其值不变 )

$\iff (p \lor 0 \lor r)$

( 使用矛盾律 :

$A \land A = 0$

, 引入命题变元

$q$

, 即使用

$A \land A$

替换式子中的

$0$

)

$\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$

, 析取式 , 析取一个

$0$

后 , 其值不变 )

$\iff (0 \lor q \lor r)$

( 使用矛盾律 :

$A \land A = 0$

, 引入命题变元

$q$

, 即使用

$A \land A$

替换式子中的

$0$

)

$\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