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

2023-03-27 16:20:26 浏览数 (1)

文章目录

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

一. 相关概念

1. 简单 析取 合取 式

( 1 ) 简单合取式

简单合取式 :

  • 1.组成 : 命题变元 (
p

) 或 命题变元否定式 (

lnot p

) ;

  • 2.概念 : 有限个 命题变元 或其 否定式 组成的合取式 , 称为 简单合取式 ;
  • 3.示例 :
    • ① 单个命题变元 :
    p

    ;

    • ② 单个命题变元否定式 :
    lnot p
    • ③ 两个 命题变元 或其否定式 构成的合取式 :
    p land lnot q
    • ④ 三个 命题变元 或其否定式 构成的合取式 :
    p land q land r

( 2 ) 简单析取式

简单析取式 :

  • 1.组成 : 命题变元 (
p

) 或 命题变元否定式 (

lnot p

) ;

  • 2.概念 : 有限个 命题变元 或其 否定式 组成的析取式 , 称为 简单析取式 ;
  • 3.示例 :
    • ① 单个命题变元 :
    p

    ;

    • ② 单个命题变元否定式 :
    lnot p
    • ③ 两个 命题变元 或其否定式 构成的析取式 :
    p lor lnot q
    • ④ 三个 命题变元 或其否定式 构成的析取式 :
    p lor q lor r

2. 极小项

( 1 ) 极小项 简介

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

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

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

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

(

1 leq i leq n

) 个文字出现在 左起 第

i

个位置 ;

n

是指命题变项个数 ;

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

与

M_i

之间的关系 : ①

lnot m_i iff M_i

②

lnot M_i iff m_i

( 2 ) 极小项 说明

关于 极小项 的 说明 :

  • 1.极小项个数 :
n

个 命题变元 会 产生

2^n

个 极小项 ;

  • 2.互不等值 :
2^n

个极小项 均 互不等值 ;

  • 3.极小项 :
m_i

表示 第

i

个极小项 , 其中

i

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

  • 4.极小项名称 : 第
i

个极小项 , 称为

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

    符号 ;

    • ④ 对应 : 凡是
    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.先写出 极小项 名称 : 从
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

    符号 ;

    • ④ 对应 : 凡是
    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.前提 ( 简单析取式 ) : 含有
n

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

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

(

1 leq i leq n

) 个文字出现在 左起 第

i

个位置 ;

n

是指命题变项个数 ;

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

( 2 ) 极大项 说明

关于 极大项 的 说明 :

  • 1.极大项个数 :
n

个 命题变元 会 产生

2^n

个 极大项 ;

  • 2.互不等值 :
2^n

个极大项 均 互不等值 ;

  • 3.极大项 :
m_i

表示 第

i

个极大项 , 其中

i

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

  • 4.极大项名称 : 第
i

个极大项 , 称为

M_i

;

  • 5.
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)

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

  • 1>
(p lor q lor r)

: 成假赋值

0 quad 0 quad 0

, 是极大项

M_0

;

  • 2>
(p lor lnot q lor r)

: 成假赋值

0 quad 1 quad 0

, 是极大项

M_2

;

  • 3>
(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)

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

  • 1>
(p lor q lor r)

: 成假赋值

0 quad 0 quad 0

, 是极大项

M_0

;

  • 2>
(lnot p lor q lor r)

: 成假赋值

1 quad 0 quad 0

, 是极大项

M_4

;

  • 3>
(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​

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

极小项极大项

0 quad 0 quad 0
1
1
0
m_0
M_0
0 quad 0 quad 1
1
1
1
m_1
M_1
0 quad 1 quad 0
0
1
0
m_2
M_2
0 quad 1 quad 1
0
1
1
m_3
M_3
1 quad 0 quad 0
1
1
0
m_4
M_4
1 quad 0 quad 1
1
1
1
m_5
M_5
1 quad 1 quad 0
0
0
1
m_6
M_6
1 quad 1 quad 1
0
0
1
m_7
M_7

② 真值表中 取值为 真 的项 对应的 极小项

m_i

构成 主析取范式 ;

m_1 lor m_3 lor m_5 lor m_6 lor m_7

③ 真值表中 取值为 假 的项 对应的 极大项

m_i

构成 主合取范式 ;

M_0 land M_2 land M_4

极小项 - 合取式 - 成真赋值 - 对应条件真值表中的

1

- 主析取范式 ( 多个合取式的析取式 )

极大项 - 析取式 - 成假赋值 - 对应条件真值表中的

0

- 主合取范式 ( 多个析取式的合取式 )

二进制 集合

0 人点赞