命题逻辑与谓词逻辑.ppt

② 若A是合式公式，则～A也是合式公式；
③ 若A和B都是合式公式，则(A∧B)，(A∨B)， (A→B)，(AB)也都是合式公式；
④ 若A是合式公式，x是任意变元，且A中无 (x)或(x)出现，则(x)A或(x)A也都是合式公式；
⑤ 当且仅当有限次使用规则①～④得到的公 式是合式公式。
4．量词的辖域与变元的约束 约束变元, 自由变元 。
则称这些指派为公式P在D上的一个解释I。
例2-1 给定公式B = (x)(y)P(x, y)和个 体域D1 = {1，2}。
求：公式B的解释及在该解释下B的真值。
解：x, y都可以取D1中的任何值，于是可有 以下几种情况：P(1, 1)，P(1, 2)，P(2, 1)， P(2, 2)。
对这4个公式，每一个都可以指派真假（T， F）两个值，则共有24=16个不同的组合，构 成16个不同的解释。
公式
约束变元
(x)P(x, y)
x
(x)Q(y)
无
(x)(P(x)→(y)Q(x, y)) x, y
(y)P(x)∧Q(x)
y
自由变元 y y
x
5．谓词公式的解释 谓词公式中的谓词变元、命题变元和自由 个体变元，个体常量和函数的一种指派就 是一个解释。 在每一种解释下，谓词公式都具有一种真 值（T或F）。
• 谓词是用来刻画个体性质或个体间关系的 词。
如： POET(libai) POET(dufu) GREAT(libai, dufu)
一般用大写字母表示谓词，小写字母表示 个体。
元数: 谓词中包含的个体数目称为谓词的。
一元谓词: 与一个个体相连的谓词，如 POET(x)；
多元谓词: 与多个个体相连的谓词叫，如 GREAT(x, y)(二元谓词)。
定义2-7 设D为谓词公式P的个体域，若对P 中的个体常量、函数和谓词按照如下规定赋值：
（a）为每个个体常量指派D中的一个元素； （b）为每个n元函数指派一个从Dn到D的映射， 其中
Dn = {(x1, x2, …, xn) | x1, x2, …, xn D} （c）为每个n元谓词指派一个从Dn到{F，T}的 映射；
非永假的公式称为可满足的公式。
4．等价和永真蕴涵 定义2-4 等价：设A，B是两个命题公
式，P1，P2，…，Pn是出现在A、B中的 所有命题变元。如果对于这n个变元的任何 一个真值指派的集合，A和B的真值都相等， 则称公式A等价于公式B，记作AB。
“等价”又可定义为：AB当且仅当 AB是一个永真式。
Q”。 连接词优先级：～，∧，∨，→，
3．合式公式
定义2-3 合式公式（Well-Formed Formula，WFF）
① 孤立的命题变元或逻辑常量（T，F） 是合式公式；
② 如果A是一个合式公式，则～A也是一 个合式公式；
③ 如果A、B是合式公式，则A∨B，A∧B， A→B，AB也都是合式公式；
定义2-5 永真蕴涵：命题公式A永真蕴 涵命题公式B，当且仅当A→B是一个永真 式，记作AB，读作“A永真蕴涵B”，简 称“A蕴涵B”。
2.2 谓 词 逻 辑
• 1．谓词与个体 原子命题被分解为谓词和个体两部分。
• 个体是指可以单独存在的事物，它可以是 一个抽象的概念，也可以是一个具体的东 西。
设x的取值范围是{甲，乙，丙}三人，y的取值范围是 {bora, jetta, santana}三种车型。
(x)(y)LIKE(x, y)表示甲、乙、丙三人都喜爱{bora, jetta, santana}中的某一种车型； (x)(y)LIKE(x, y)表示甲、乙、丙三人都喜爱{bora, jetta, santana}三种车型。
第二章 逻辑推理
2.1 命 题 逻 辑
1．命题
定义2-1 命题：具有真假意义的语句。
定义2-2 原子命题：如果一个命题不能被 进一步分解成更为简单的命题，则该命题 就称为原子命题。
2．连接词
• ～：称为“非”或“否定”。 • ∨：称为“析取”，P∨Q读作“P或Q”。 • ∧：称为“合取”，P∧Q读作“P与Q”。 • →：称为“条件” 。P→Q。 • ：称为“双条件”。PQ, “P当且仅当
P(1, 1) P(1, 2) P(2, 1) P(2,2)
I1
T
T
T
T
I2
T
T
T
F
I3
T
T
F
T
I4
T
T
F
F
I5
T
F
T
T
I6
T
F
T
F
I7
T
F
F
T
I8
T
F
F
F
I9
F
T
T
T
I10
F
T
T
F
I11
F
T
F
T
I12
F
T
F
F
I13FFT NhomakorabeaT
I14
F
F
T
F
I15
F
F
F
T
I16
F
F
F
F
如对I6，则有B(I6) = T。因为：对 x = 1时，存在一个y = 1，有P(x, y) = P(1, 1) = T。对x = 2时，存在一 个y = 1，有P(x, y) = P(2, 1) = T。所 以在I6解释下，公式B为真。
④ 当且仅当有限次使用规则①～③后得 到的公式才是合式公式。
永真式（或重言式）：给定一个公式， 如果对于所有的真值指派，它的值都为真 （T），则称该公式为永真式（或重言式） ；
永假式（或称该公式为不可满足的）： 如对于所有的真值指派，它的值都为假（F）， 则称该公式为永假式（或称该公式为不可满 足的）。
3．合式谓词公式
原子公式: 若P为不能再分解的n元谓词变元， x1, x2, …, xn是个体变元，则称P(x1, x2, …, xn)为原子公式或原子谓词公式。当n = 0时， P表示命题变元或原子命题公式。所以命题 逻辑是谓词逻辑的特例
定义2-6 谓词合式公式（简称公式）的定义 如下：
① 原子公式是合式公式；
如 D2 = {1，2，3}
根据上面的分析，在D2上的解释应有29个。
下面是其中的一个解释：
I: P(1, 1) P(1, 2) P(1, 3) P(2, 1) P(2, 2) P(2, 3) P(3, 1) P(3, 2) P(3,3)
个体域: 任何个体的变化都有范围。
谓词变元命名式: 一个n元谓词常被表示成 P(x1, x2, …, xn) 。
2．量词
• 全称量词: “(x)P(x)”表示命题“对个体域中所 有的个体x，谓词P(x)均为T”。
• 存在量词: “(x)Q(x)”表示命题“在个体域中存 在某个个体使谓词Q(x)为T”。其中“”叫存在 量词。