第一部分:第3章AI编程基础 31.1命题 表3-2公式(P→∧(p→P逻辑真值表 Q→P (P→Q)∧( FF F T T F F T F F T F 给定一个公式,如果对于所有的真值指派,它的真值都是T,则称该公式为 永真式(或重言式);如果对于所有的真值指派,它的真值都是F,则称该 公式为永假式(或不可满足的);除了这两种极端情况外,一般的命题公式 的真值有T有F。称非永假的公式为可满足的公式。 2004.11.3 A|程序设计
2004.11.3 AI程序设计 11 第一部分：第3章 AI编程基础 3.1.1 命题 表3-2 公式（P→Q）∧（Q→P）逻辑真值表 给定一个公式，如果对于所有的真值指派，它的真值都是T，则称该公式为 永真式（或重言式）；如果对于所有的真值指派，它的真值都是F，则称该 公式为永假式（或不可满足的）；除了这两种极端情况外，一般的命题公式 的真值有T有F。称非永假的公式为可满足的公式。 P Q P→Q Q→P （P→Q）∧(Q→P） F F T T T F T T F F T F F T F T T T T T
第一部分:第3章AI编程基础 31.1命题 定义35等价( Equivalence):设A、B都是命题公式, P(i=1,2…,m)是出现在A和B中的所有命题变元。如果对于这n个变 元的任何一个真值指派集合,A和B都相等,则称公式A等价于公式B, 记作:A台B。 等价又可定义为:“A台→B当且仅当A←B是一个永真式”。 定义3.6永真蕴含:命题公式A永真蕴含命题公式B,当且仅当A→B 是一个永真式,记作:A→B,读作“A永真蕴含B",简称“A蕴含 B 2004.11.3 A|程序设计 12
2004.11.3 AI程序设计 12 第一部分：第3章 AI编程基础 3.1.1 命题 定义3.5 等价（Equivalence）：设A、B都是命题公式， Pi (i=1,2,...,n)是出现在A和B中的所有命题变元。如果对于这n个变 元的任何一个真值指派集合，A和B都相等，则称公式A等价于公式B， 记作：A⇔B。 等价又可定义为：“A⇔B当且仅当A↔B是一个永真式”。 定义3.6 永真蕴含：命题公式A永真蕴含命题公式B，当且仅当A→B 是一个永真式，记作：A⇒B，读作“A永真蕴含B ”，简称“A蕴含 B ”
第一部分:第3章AI编程基础 3.1.2命题定律 利用真值表,我们可以证明一批常用的蕴含式和等价 式,统称为命题定律 蕴含式(16条)略 等价式(40条)略 2004.11.3 A|程序设计 13
2004.11.3 AI程序设计 13 第一部分：第3章 AI编程基础 3.1.2 命题定律 利用真值表，我们可以证明一批常用的蕴含式和等价 式，统称为命题定律。 蕴含式 （16条）略 等价式 （40条）略
第一部分:第3章AI编程基础 3.1.3范式 我们知道,具有相同真值表的公式可以有无穷多个,但他们都是等价 的。为了研究的方便,我们需要找到它们的标准形式—范式。首先 看基本概念: 文字:原子公式及其否定叫文字。 基本积:仅由文字构成的合取式叫基本积。 基本和:仅由文字构成的析取式叫基本和。 2004.11.3 A|程序设计 14
2004.11.3 AI程序设计 14 第一部分：第3章 AI编程基础 3.1.3 范式 我们知道，具有相同真值表的公式可以有无穷多个，但他们都是等价 的。为了研究的方便，我们需要找到它们的标准形式——范式。 首先 看基本概念： 文字：原子公式及其否定叫文字。 基本积：仅由文字构成的合取式叫基本积。 基本和：仅由文字构成的析取式叫基本和
第一部分:第3章AI编程基础 3.1.3范式 1)析取范式 由基本积的析取构成的命题公式叫析取范式。例如 PV (PAQ)V(PARv(uPANQ) 其中的每一个基本积叫一个析取项。 任意给定一个命题公式都可以化成与之等价的析取范式。 求公式A的析取范式的步骤 ①利用等价式E38和E39(或E40)消去公式中的→和联结词 ②利用E1和E12将联结词~深入到变元,并用双重否定律E10化简到变 元前最多只有一个~; ③利用分配律E和E将公式最后化为析取范式。 2004.11.3 A|程序设计 15
2004.11.3 AI程序设计 15 第一部分：第3章 AI编程基础 3.1.3 范式 1）析取范式 由基本积的析取构成的命题公式叫析取范式。例如 ～P∨(P∧Q) ∨(P∧~R)∨(~P∧~Q) 其中的每一个基本积叫一个析取项。 任意给定一个命题公式都可以化成与之等价的析取范式。 求公式Ａ的析取范式的步骤 ① 利用等价式E38和E39（或E40）消去公式中的→和联结词； ② 利用E11和E12将联结词~深入到变元，并用双重否定律E10化简到变 元前最多只有一个~； ③ 利用分配律E7和E8将公式最后化为析取范式