命题逻辑与谓词逻辑ppt课件

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