当前位置：文档之家 › 第9讲谓词逻辑公式

第9讲谓词逻辑公式

  • 格式：ppt
  • 大小：485.00 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

谓词逻辑I 谓词、量词与谓词公式共32页

谓词逻辑I 谓词、量词与谓词公式共32页


谓词逻辑I 谓词、量词与谓词 公式
41、实际上，我们想要的不是针对犯 罪的法 律，而 是针对 疯狂的 法律。 ——马 克·吐温 42、法律的力量应当跟随着公民，就 像影子 跟随着 身体一 样。— —贝卡 利亚 43、法律和制度必须跟上人类思想进 步。— —杰弗 逊 44、人类受制于法律，法律受制于情 理。— —托·富 勒
45、法律的制定是为了保证每一个人 自由发 挥自己 的才能 ，而不 是为了 束缚他 的才能 。—— 罗伯斯 庇尔

1、最灵繁的人也看不见自己的背脊。——非洲 2、最困难的事情就是认识自己。——希腊 3、有勇气承担命运这才是英雄好汉。——黑塞 4、与肝胆人共事，无字句处读书。——周恩来 5、阅读使人充实，会谈使人敏捷，写作使人精确。——培根
谓词公式与翻译(精)

谓词公式与翻译(精)


（4）谓词
P（x）为P（a）= 0，P（b）= 1；
Q（x，y）为Q（a，a）= 0，Q（a，b）= Q（b，a）= Q（b，b）
= 1；
L（x，y）为L（a，b）=L（b，a）= 0，L（a，a）= L（b，b）=
1。
求下列公式在解释I下的真值
2）x（ P（f（x））∧Q（x，f（x）））；
在解释I下
5
2.3 谓词公式与翻译
由例可知，对于命题翻译成谓词公式时，机动性很大，由于对个 体描述性质的刻划深度不同，就可翻译成不同形式的谓词公式。

例如：这只大红书柜摆满了那些古书
解法1：
解法2：
设：F(x,y): x摆满了y
设：F(x,y): x摆满了y

R(x): x是大红书柜
x（ P（f（x））∧Q（x，f（x）））
=（ P（f（a））∧Q（a，f（a）））∨（ P（f（b））∧Q（b，f
（b）））
=（ P（b）∧Q（a，b））∨（ P（a）∧Q（b，a））
=（ 1∧1）∨（ 0∧1）
= 1∨0
= 1 2019/6/3
10
【例2.2.1】给定解释I如下
（1）U =｛a，b｝；
人总是要犯错误的。
解：设F(x)：x犯错误，M(x)：x是人。则上句符
号化为：
(a) ┒(x)(M(x)⋀┒F(x)) (b) x(M(x)→F(x)) 【例2】尽管有人聪明但未必一切人都聪明。
解：设P(x)：x聪明，M(x)：x是人。则上句符号 化为：
2019/6/3 x(M(x)⋀P(x))⋀┒(x(M(x)→P(x)))
2019/6/3
7
2.3 谓词公式与翻译
谓词逻辑 基本推理公式

谓词逻辑 基本推理公式

谓词逻辑基本推理公式
谓词逻辑的基本推理公式包括：
1. 全称量词规则：如果个体域中每一个个体具有性质A，则存在一个个体具有性质A。

即，能找出一个就表示存在。

公式为A ( c ) ⇒∃ x A
( x )A(c)\Rightarrow\exists xA(x)A(c)⇒∃xA(x)。

规则成立的条件是c是个体域中某个确定的个体，代替c的x不在A©中出现过。

2. 存在量词规则：如果个体域中存在个体具有性质A，则至少存在一个个体具有性质A。

公式为∃ x A ( x ) ∀ y A ( y )\exists xA(x)\forall yA(y)∃x A(x)∀yA(y)。

3. 归结推理：将公式中的量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变。

4. 代入规则：把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号。

5. 解释（赋值）：谓词公式A的个体域D是非空集合，则每一个常项指定D中一个元素；每一个n元函数指定Dn到D的一个函数；每一个n元谓词指定Dn到{0,1}的一个谓词。

按这个规则做的一组指派，称为A的一个解释或赋值。

以上是谓词逻辑的基本推理公式，通过这些公式可以推导出更复杂的逻辑推理结果。

谓词逻辑I 谓词、量词与谓词公式

谓词逻辑I 谓词、量词与谓词公式

如 F(x)G(x), xF(x)yG(y)是pq的代换实例 定理 重言式的代换实例都是重言式，矛盾式的代 换实例都是矛盾式.
26
实例
例 判断下列公式的类型 (1) ∀xF(x)→∃xF(x)；
设I为任意的解释，若∀xF(x)为假，则 ∀xF(x)→∃xF(x)为真. 若∀xF(x)为真，则∃xF(x)也为 真，所以∀xF(x)→∃xF(x)恒为真. 是逻辑有效式. (2) ∀xF(x)→(∀x∃yG(x,y)→∀xF(x))； 重言式p→(q→p) 的代换实例，是逻辑有效式.

7
基本概念 —谓词：0元谓词
例 将命题“2是素数且是偶数”用0元谓词 符号化 设F(x)：x是素数； G(x)：x是偶数；a: 2 则F(a)G(a)表示“2是素数且是偶数” F(a)和G(a)都是0元谓词，不仅如此 F(a)G(a)也是0元谓词， F(x)G(x)是一个1 元谓词，表示x既是素数又是偶数这一性质. 以个体常元a代入x，从而消去个体变元，便 得到0元谓词F(a)G(a)
10
例 (续 )
(2) 2 是无理数仅当 3是有理数 在命题逻辑中, 设 p： 2 是无理数，q： 3 是有理数. 符号化为 p q 在谓词逻辑中, 设F(x): x是无理数, G(x): x是有理数 符号化为 F ( 2 ) G( 3 ) (3) 如果2>3，则3<4 在命题逻辑中, 设 p：2>3，q：3<4. 符号化为 pq 在谓词逻辑中, 设 F(x,y)：x>y，G(x,y)：x<y, 符号化为 F(2,3)G(3,4)
基本概念 ——谓词：元数
谓词的元数: 谓词中包含的个体的个数， 例如 F(x,y,z)含有三个个体，其元数为3 一元谓词: 表示事物的性质或状态，如F(苏) 多元谓词 (n元谓词, n2): 表示事物之间的 关系. 例如 L(x,y)表示x与y有L关系， 若L表示…大于…，则L(x,y)表示x>y， 若 L 表示 …是 … 的妻子，则 L( 圆 , 又 ) 表示 高圆圆是赵又廷的妻子. n 元谓词规定了 n个个体的顺序，不可随意颠 倒 . 例如 L(圆,又)不能写L(又,圆)
第9讲谓词逻辑公式

第9讲谓词逻辑公式

最外层 优先级递减： ∃, ∀; ¬; ∧,∨, →,↔
2012-2-22
一阶逻辑
17
合式公式中的变项
量词辖域: 在∃xA, ∀xA中, A是量词的辖 域. 例如: ∃x(F(x)∧∀y(G(y)→H(x,y))) 指导变项: 紧跟在量词后面的个体变项. 例如: ∃ ∃x(F(x)∧∀y(G(y)→H(x,y))) ∧∀ → 约束出现: 在辖域中与指导变项同名的变 项. 例如: ∃x(F(x)∧∀y(G(y)→H(x,y))) 自由出现: 既非指导变项又非约束出现. 例如: ∀y(G(y)→H(x,y))
2012-2-22
一阶逻辑
8
字母表
个体常元: 函数符号: 谓词符号: 个体变元: 量词符号: 联结词符号: 括号与逗号:
2012-2-22
a, b, c, …, a1, b1, c1,… f, g, h, …, f1, g1, h1,… F, G, H, …, F1, G1, H1, … x, y, z, …, x1, y1, z1,… ∃, ∀ ¬, ∧, ∨, →, ↔ (, ), ，
2012-2-22 一阶逻辑 22
赋值
是否存在一种公式在任何赋值下都 取相同的真值呢？
2012-2-22
一阶逻辑
23
一阶逻辑永真式(tautology)
永真式:在各种赋值下取值均为真(逻辑有 效式) 命题逻辑永真式: 在各种赋值下取值均为真
(重言式)
永假式:在各种赋值下取值均为假(矛盾式)
命题逻辑永假式: 在各种赋值下取值均为假 (矛盾式)
2012-2-22 一阶逻辑 18
合式公式中的变项(举例)
H(x,y)∨∃xF(x)∨∀y(G(y)→H(x,y)) x 与 y 是指导变项 x与y是约束出现 x与 y是自由出现 注：同一变元在同一公式中可能既有约 束出现又有自由出现
离散数学 谓词逻辑

离散数学 谓词逻辑


例1 给定解释I1如下：
(1)个体域为自然数集合N； (2)N中的特定元素a=0； （3）F(x,y):x大于或等于y. 在解释I1下,求下列各式的真值： (1)(∀x)F(x,a)；(2)(∀x∃y)F(x,y) 解 在解释I1下,公式分别解释为： (1)任何自然数都大于或等于零, 为真命题.
(2)对任一自然数x,都存在一自然数y使得x≥y, 为真命题.
4
例子
［例2-1.1］ 张明是位大学生。 解：设S(x)：x是大学生,c：张明, 一元谓词：表 则原句的谓词形式为S(c)。 示客体性质 ［例2-1.2］我坐在张三和李四中间。 解：设S(x,y,z)：x坐在y和z之间,i：我,z：张 三,l：李四, 多元谓词：表 示客体间关系 则原句的谓词形式为S(i,z,l)。
★从以上两命题的符号化可以看出,同一命题在不同个体域下 符号化的形式可能不同。
11
这里,M(x)称为特性谓词。应该注意 的是,全称量词和存在量词符号化时,引入 特性谓词时的形式是不同的。 用全称量词 符号化时,特性谓词作为条 件式的前件； 用存在量词符号化时则作为合取式的一 项。
12
对于任一给定的实数x,都存在着一个实数y,使得 x+y=0。 如果取个体域为实数集合 ∀ x ∃ y H(x, y ) 然而 ∃ y ∀ x H(x, y )： 存在着一个少数y,对于任一实数x,使得x+y=0
3
谓词的表示
客体词有两种：客体常元和客体变元。客体常 元表示具体的或特定的客体,一般用小写字母 a、b、c等表示；表示抽象的或泛指的客体的 词称为客体变元,常用小写字母x、y、z等表 示。 谓词,通常用大写的字母A、B、C等表示。
谓词填式：单独一个谓词不是完整的命题, 把谓词字母后填以客体所得的式子。
谓词逻辑的等值和推理演算-PPT精选文档

谓词逻辑的等值和推理演算-PPT精选文档

Lu Chaojun, SJTU11Fra bibliotek何转化成PNF
1.消去和↔ 2.否定词内移
– 应用De Morgan律
3.约束变元易名(如果必要的话) 4.量词左移
– 应用分配等值式
Lu Chaojun, SJTU
12
例:求PNF
((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = ((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (z)Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y) Q(z,b) R(x)) = (x)(z)(y)(P(a,x,y) Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y)Q(z,b)R(x)(pp))
Lu Chaojun, SJTU
5
量词分配等值式
• 量词对及的分配律
(x)((x)) (x)(x) (x)((x)) (x)(x) (x)((x)) (x)(x) (x)((x)) (x)(x) – 其中 不含自由x ! – 这个条件很容易满足:对约束变元改名即可.
Lu Chaojun, SJTU
6
量词分配等值式(续)
• 量词对的分配律
(x)((x)) (x)(x) (x)((x)) (x)(x) (x)((x)) (x)(x) (x)((x)) (x)(x) – 其中 不含自由x !
谓词公式与翻译(精)

谓词公式与翻译(精)


xP(x)→x Q(x)) ┒(x)P(x) ⋁x Q(x)
定义2:
设A为谓词公式，若在任何解释下，A的真值都为真，则 称A为永真式；
若至少存在一种解释，使A的真值为真，则称A为可满足 式；
若在任何解释下，A的真值都为假，则称A为矛盾式，矛 盾式也称不可满足式。
2019/6显/3 然，永真式是可满足式。
2019/6/3
7
2.3 谓词公式与翻译
2．谓词公式的解释 定义 谓词公式的一个解释I，由下面4部分组成 1）非空的论域U； 2）U中的特定的个体常项； 3）U上特定的函数； 4）U上特定的谓词。
若将谓词公式中的个体常项，函数和谓词分别指定 为U中的特定个体常项，U上特定的函数和U上特定的谓 词，即为该公式在解释I下的真值。
彐x(P(z)∧R(x,z)) 但是彐x(P(x)∧R(x,x))与彐x(P(z)∧R(x,y))这两种代入都是与
规则不符的。
2019/6/3
15
2.5谓词公式的等价与蕴涵
1、谓词逻辑中常见的等价与蕴含关系 谓词公式的赋值:
在谓词公式中常包含命题变元和客体变元，当客体 变元由确定的客体所取代，命题变元用确定的命题 所取代时，就称作对谓词公式的赋值。一个谓词公 式经过赋值以后，就成为具有确定真值T或F的命 题。
17
(1)命题逻辑中等价和蕴含的推广
在命题演算中，任一永真公式，其中同一命题变元， 用同一公式取代时，其结果也是永真公式。我们可以 把这个情况推广到谓词公式之中，当谓词演算中的公 式代替命题演算中永真公式的变元时，所得的谓词公 式即为有效公式，故命题演算中的等价公式表和蕴含 式表都可推广到谓词演算中使用。
例题 2 对x(P(x)→R(x,y))∧Q(x,y)换名。 解 可换名为： z(P(z)→R(z,y))∧Q(x,y)， 但不能改名为： y(P(y)→R(y,y))∧Q(x,y) 以及 z(P(z)→R(x,y))∧Q(x,y)。
谓词逻辑永真公式

谓词逻辑永真公式

P(1,1): T； P(1,2): F； P(2,1):F； P(2,2): T – 则xyP(x,y)和yxP(x,y) 在解释I下的真值分
别为?
xyP(x,y) 关于x的一元函数
x y P(x,y) yP(x,y) xyP(x,y)
1
T
1
T
2
F
T
1
F
2
T
2
T
yxP(x,y) 关于y的一元函数
– 例：I(x)：x是整数，论域E为自然数集合
• I(x)在E上是永真式 • I(x) ∨ I(x)是与论域无关的永真式
• 谓词公式的永假式 • 谓词公式的可满足式
例：试说明以下公式的类型
1. xA(x)→A(y)
永真式
2. xA(x)→A(y)
可满足式
3. A(x) (A(x) ：x+6=5) 可满足式
x(A(x)∨B(x)) F
B(1) B(2) F
因此
xA(x) F
所以 xB(x) T
从而 A(1) A(2) B(1) B(2)
F
FT
结论：所给公式不是永真式
例(续前)：试判断xA(x)∨xB(x) → x(A(x)∨B(x)) 是否是永真式，并说明理由。
解：所给公式不是永真式，理由如下。
体函数常量
3. 对A中出现的每一个n元谓词，指定一个D上的n元谓词 常量
4. 对A中出现的每一个个体常量及自由变元，指定D中的 一个个体常量
5. 对A中出现的每一个命题变元P，指派一个真值T或F
由此得到一个命题AI，称AI的真值为公式A在 解释I 下的真值
例
• 取解释I如下：
– D={1,2}, – 定义D上的二元谓词P真值为
谓词逻辑_

谓词逻辑_


2-2.1 命题函数
比如：L(x,y)表示“x小于y”是二元谓词， L(x,3)表示“x小于3”是一元谓词，L(2,3)表示 “2小于3”是0元谓词。
因此可以将命题看成n元谓词的一个特殊 情况。
0元谓词都是命题，命题逻辑中的简单命 题都可以用0元谓词表示。
2-2.1 命题函数
定义2：复合命题函数（compound propositional function）：
举例说明：
例1．“有些人是要死的”. 解1： 采用全体人作为个体域.
设: G(x): x是要死的. 原命题符号化成: (x)G(x)
解2： 采用全总个体域. 设: M(x): x是人; G(x):x是要死
的. 原命题符号化成: (x)(M(x) ∧G(x))
例2． “凡人都是要死的”. 解1: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: (x)G(x)
（x）P(x) is false if P(x) is false for every x in U.
2-2.2 量词
唯一存在量词（unique quantifier）： “恰好存在一个”，用符号“!”表示。
2-2.2 量词
现在对以上两个命题进行符号化，在进行符号 化之前必须确定个体域。
第一种情况．个体域D为人类集合。 设：F(x) ： x是要死的。
解2: 采用全总个体域. 设: M(x): x是人; G(x):x是要死的. 原命题符号化成: (x)(M(x) →G(x))
例3: “存在最小的自然数”。 解1: 采用全体自然数作为个体域. 设: G(x,y): x≤y; 原命题符号化成: (x)(y)G(x,y) 注意量词顺序: (y)(x)G(x,y): “没有最小的自然数”.
谓词公式的解释

谓词公式的解释

解： 1 永真式 P(QP）的代换实例，故为逻辑有效的。 2 矛盾式 (PQ)Q 的代换实例，故为不可满足的。 3）解释I1: 个体域N, F(x):x>5, G(x): x>4, 公式为真 解释I2: 个体域N, F(x):x<5, G(x):x<4, 公式为假 结论: 为非永真式的可满足式
小结
例2.8
给定解释I如下：
1 个体域为实数集合R； 2 R中的特定元素a=0； 3 R上的特定函数f(x, y) =x+y,
g(x, y)=xy； 4 R上的特定谓词F(x, y)：x=y。
在解释I下，公式分别解释为： 1） xF(f(x, a), g(x, a)) 解释为：
在实数集合R中，x(x+0=x0)
把这样得到的公式记作A*。称A*为A在I下的解释，或A在I下被解释成A*。
例2.8
给定解释I如下：
1 个体域为实数集合R； 2 R中的特定元素a=0； 3 R上的特定函数f(x, y) =x+y,
g(x, y)=xy； 4 R上的特定谓词F(x, y)：x=y。
在解释I下，求下列各式的真值：
1）xF(f(x, a), g(x, a)) 2） xy(F(f(x, y), g(x, y))F(x, y)) 3 ）xF(g(x, y), a)
定理2.2 重言式的代换实例都是逻辑有效的，永假式的代换实例都是不可满足的。
பைடு நூலகம்2.9
判断下列公式中，哪些是逻辑 有效的，哪些是不可满足的？ 1）xF(x)(xyG(x,y)xF(x)) 2）(xF(x)yG(y))yG(y) 3）x(F(x)G(x))
分析——两种思路 1 公式的解释； （2）定理2.2。

谓词逻辑的等值和推理演算-SJTUCS

这是正确的推理形式 在命题逻辑里只能表达成p q → r，显然不是
正确的推理形式
25
推理形式
例2: 人皆有死，孔子是人，所以孔子有死.
(x)(Man(x)→Mortal(x)) Man(Confucius) → Mortal(Confucius)
例3: 若有一个又高又胖的人,则有一个高个 子而且有一个胖子.
(x)Man(x)(x)Woman(x) 要么所有人都是男人，要么所有人都是女人
8
量词分配等值式(续)
回顾：约束变元改名规则
(x)(x) = (y)(y) (x)(x) = (y)(y)
变元易名后的“分配律”
(x)(x)(x)(x)=(x)(y)((x)(y)) (x)(x)(x)(x)=(x)(y)((x)(y))
步骤： 设 是任一公式，通过下述步骤可将其转化
为与之等价的前束范式： （1）消去公式中包含的联结词“”、“”； （2）反复运用摩根定律，直接将“”内移到原子
谓词公式的前端； （3）约束变元易名（如果必要的话）； （4）使用分配等值公式，将所有量词提到公式的最
前端。
14
求((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) 的前束范式。 解 （1）消去联结词“”、“”，得： ((x)(y)P(a, x, y)(x)((y)Q(y,b)R(x)))
引入新个体常项a代入x消去u时引进的个体因为与左边的y和z有关所以不能用个体常项而是用函数两者明显不等值但在不可满足的意义下两者是一致的skolem范式不保持等值24谓词逻辑的推理命题逻辑中有关推理形式重言蕴涵以及基本的推理公式的讨论和所用的术语都可引入到谓词逻辑中并可把命题逻辑的推理作为谓词逻辑的推理的一个部分来看待我们讨论谓词逻辑所特有的推理形式和基本推理公式25推理形式推理形式是指用表达推理的公式例1

谓词逻辑的基本概念和符号

谓词逻辑的基本概念和符号谓词逻辑是数理逻辑中的一种重要分支，用于研究命题中涉及谓词的逻辑关系。

它是对日常语言中命题的形式化描述，通过定义符号和规则，使我们能够准确地分析和推理命题的真假与逻辑关系。

本文将介绍谓词逻辑的基本概念和符号，并解释它们的含义和用法。

一、谓词逻辑的基本概念1. 谓词谓词是指具有真值性质的命题部分，它可以用来描述事物的性质、关系或状态。

例如，"x是红色"和"x大于y"都是谓词表达式，其中"x"和"y"是变量，代表不同的个体或对象。

2. 量词量词用于限定谓词所描述的个体范围，包括普遍量词和存在量词。

普遍量词∀表示命题对所有个体都成立，存在量词∃表示命题至少对某个个体成立。

例如，∀xP(x)表示谓词P适用于所有个体x，∃xP(x)表示谓词P至少适用于一个个体x。

3. 函数函数是指将一个或多个变量映射到一个确定的结果的过程。

在谓词逻辑中，函数常常用来表示物体之间的关系或属性。

例如，f(x)表示把变量x映射为f的结果值。

4. 项项是指变量、常量或函数应用，可以作为谓词中的参数。

例如，"x"和"y"都是变量项，"a"和"b"都是常量项，"f(x)"是函数应用项。

二、谓词逻辑的符号表示1. 逻辑连接词谓词逻辑中常用的逻辑连接词有合取（∧）、析取（∨）和否定（¬）。

合取表示两个命题同时为真，析取表示至少有一个命题为真，否定表示命题的否定。

2. 蕴含和等价蕴含和等价是谓词逻辑中常用的推理运算符。

蕴含（→）表示如果前提成立则结论也成立，等价（↔）表示两个命题的真假相同。

3. 量词符号谓词逻辑中常用的量词符号有普遍量词（∀）和存在量词（∃）。

普遍量词表示全称量化，存在量词表示存在量化。

4. 括号括号用于划定谓词逻辑表达式中的范围，可以改变运算的优先级。

谓词逻辑简介

谓词逻辑简介
谓词逻辑是一种形式逻辑的分支，它用于表示和推理关于状态和关系的命题。

它是由 Gottlob Frege 于1879年提出的。

谓词逻辑的基本元素是谓词（predicate）和变量（variable）。

谓词是用来描述一个命题中的关系或状态的词，如“是大的”，“是蓝色的”等。

变量则是用来表示命题中的实体，如“x”，“y”等。

谓词逻辑中最重要的运算符是量化运算符。

量化运算符有两种：全称量化和存在量化。

全称量化运算符（∀）表示“对于所有”的意思，如“对于所有的x，x 是蓝色的”，而存在量化运算符（∃）则表示“存在”的意思，如“存在一个x，使x是蓝色的”。

谓词逻辑还有其它运算符，如否定运算符（¬），且运算符（∧）和或运算符（∨）等。

这些运算符可以结合起来构成更复杂的命题。

谓词逻辑最重要的应用之一就是在数学中的应用。

谓词逻辑可以用来描述数学定理和命题，并进行推理和证明。

此外，谓词逻辑还广泛应用于人工智能领域，如机器学习和自然语言处理。

在机器学习中，谓词逻辑可以用来描述和表示各种规则和模型。

在自然语言处理中，谓词逻辑可以用来描述语言中各种关系和状态。

总之，谓词逻辑是一种非常重要和有用的逻辑学分支，它在数学、人工智能等领域都有着广泛的应用。

它的基本思想是使用谓词和变量来表示和推理关于状态和关系的命题，并通过量化运算符和其它运算符来构造更复杂的命题。

谓词公式及解释

好比有2个李勇，一个是正坐在家里看电视的“李勇”，
一个是在马路上散步的“李勇”，
为了避免这种“误会”出现，要对“约束变元”改名。
谓词公式及解释-个体变元的身份 例题 分析x(F(x)G(y))y(H(x)L(x,y,z))变
元身份 解：尽管x在公式x(F(x)G(y))出现，又在
y(H(x)L(x,y,z))出现，但两个x不是一回事， 只是恰巧二个名字相同而矣，
x是量词的指导变元。 (F(x,y)G(x,z))是量词的辖域 在 (F(x,y)G(x,z))中x是约束出现，出现2次。 在(F(x,y)G(x,z))自由出现的变元y/z，各一次。
谓词公式及解释-个体变元的身份 量词指导变元：xA和xA中的x 量词辖域：xA和xA中的A为量词/辖域 变元的约束出现：指导变元的每次出现(称约束变元)。 变元的自由出现：不是约束出现的变元(称自由变元) 。 例题 x(F(x,y)G(x,z)) 例题 x(F(x)G(y))y(H(x)L(x,y,z)) 解：
与变元约束情况
解：x、y的作用域是(P(x,y)Q(y,z))， x的作用域是P(x,y)。
将与自由变元同名约束变元yr， 将与前一个同名约束变元xs，则原公式
xr(P(x,r)Q(r,z))sP(s,y)
谓词公式及解释-个体变元的身份 例题 x(P(x)xQ(x,z)yR(x,y))Q(x,y)
(4)同一样公式在不同的论域下真值不同，究竟 如何确定一个公式的真值呢？
谓词公式及解释
非逻辑符号:个体常元、函数符号、谓词符号 逻辑符号:个体变元、量词符号、联结词、逗号、 括号。
项的定义：个体常元与变元及其函数式为项。
(1)个体常元和个体变元是项。 (则2)若(t1,(tx2,1…,x,2,t…n)是, x项n)是。n元函数,t1,t2,…tn是n个项， (3)有限次使用(2)得到的表达式是项。 原子公式：

离散数学之谓词逻辑 ppt课件

▪ 但客体变元在哪些范围内取特定的值，对是 否成为命题及命题的真值极有影响。
例：R(x)表示“x是大学生”，如果x的讨论范 围是某大学里班级中的学生，则R(x)是永真式。 如果x的讨论范围是某中学里班级中的学生， 则R(x)是永假式。如果x的讨论范围为一剧场 中的观众，那么对某些观众，R(x)为真，对另 一些观众，R(x)为假。
2.3 谓词公式与翻译
▪ F 的项： (1)个体常项和个体变项都是项。 (2)若f(x1, x2, …, xn)是任意的n元函数，t1, t2, …, tn是任意的n个项，则f(t1, t2, …, tn)是 项。 (3)所有的项都是有限次使用(1),(2)得到的。
▪ 原子公式 若A(x1, x2, …, xn)是F 的任意n 元谓词，t1, t2, …, tn是F 的任意n个项，则称 A(t1, t2, …, tn)为谓词演算的原子公式。
给定任何两个谓词公式wffa和wff的任一组真值指派所得真值均相同则称谓词公式a和b在e上是等价的并记作给定任意谓词公式wffa其个体域为e对于a的任一组真值指派wffa皆为1则称公式a在e上是有效的永真的
2.1 谓词的概念与表示
下列推理：凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。
众所周知，这是真命题。但在命题逻辑中 ( P ∧ Q ) R ，难证其为重言式。 原因：命题逻辑不考虑命题之间的内在联系 和数量关系。 办法：将命题再次细分。
为相应量词的指导变元。P(x)称为相应量词 的作用域/辖域。在x和x的辖域中，x的
所有出现都称为x在公式A中的约束出现，
所有约束出现的变元，叫做约束变元。A中 不是约束出现的变元均称作自由变元。
2.4 变元的约束
(1)x(F(x) G(x,y)) x是指导变元，量词的辖域为(F(x)G(x,y))， 其中，x是约束出现两次，y是自由出现一次。

2024考研备考资料形式逻辑公式大汇总

引言：2024考研备考是每位考生都面临的重要任务，其中形式逻辑公式是备考过程中不可忽视的一部分。

形式逻辑是考研数学的重点内容，熟练掌握其中的公式对考生来说是必不可少的。

本文将对2024考研备考资料形式逻辑公式进行大汇总，以帮助考生全面了解和掌握这一部分知识。

概述：形式逻辑是数学逻辑的分支，研究命题的形式和逻辑推理。

在考研数学中，形式逻辑是一个重要的方向，备考时需要熟练掌握其中的公式和推理方法。

本文将分析和总结2024考研备考资料中的形式逻辑公式，以帮助考生在备考中更好地理解和运用这些公式。

大点1：命题与关系1.命题的定义与性质2.命题的联结词3.命题的等价与蕴含关系4.命题的否定与充分条件5.命题的简化法则大点2：谓词逻辑1.谓词逻辑的定义与基本概念2.谓词逻辑中的量词3.谓词公式的等价与否定4.谓词逻辑中的常见公式5.谓词逻辑的应用举例大点3：推理与规则1.推理规则的基本原理2.归结推理法3.置换推理法4.形式证明与正确性证明5.推理规则的应用举例大点4：范式与篇式1.范式的定义与分类2.范式的转换和运算3.篇式的定义与性质4.篇式的简化和合取范式5.范式与篇式在命题逻辑中的应用大点5：谓词逻辑的求解方法1.常见谓词公式的求解步骤2.带量词的谓词公式求解方法3.递归算法在谓词逻辑中的应用4.谓词逻辑求解方法的推广与应用5.谓词逻辑的综合应用题解析总结：形式逻辑是2024考研备考中的重要知识点，掌握其中的公式对考生来说是至关重要的。

本文通过分析和总结2024考研备考资料中的形式逻辑公式，帮助考生全面了解和掌握这一部分内容。

希望考生在备考过程中能够重视形式逻辑的学习，通过对公式的掌握提升自己的备考水平，取得优异的成绩。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2012-2-22 一阶逻辑 2
注意：
在论域不同时，命题符号化的形式也不同 若未给出论域，则以全总个体域为论域 论域确定后，使用全称量词与存在量词符 号化形式不同 多个量词同时出现时，不能随意颠倒次序 ∀x∃y(x≤y) ∃x∀y(x≤y)
2012-2-22
一阶逻辑
3
谓词演算的形式系统
字母表 公式 公理 推理规则 形式语言 形式推理
最外层 优先级递减： ∃, ∀; ¬; ∧,∨, →,↔
2012-2-22
一阶逻辑
17
合式公式中的变项
量词辖域: 在∃xA, ∀xA中, A是量词的辖 域. 例如: ∃x(F(x)∧∀y(G(y)→H(x,y))) 指导变项: 紧跟在量词后面的个体变项. 例如: ∃ ∃x(F(x)∧∀y(G(y)→H(x,y))) ∧∀ → 约束出现: 在辖域中与指导变项同名的变 项. 例如: ∃x(F(x)∧∀y(G(y)→H(x,y))) 自由出现: 既非指导变项又非约束出现. 例如: ∀y(G(y)→H(x,y))
一阶逻辑 9
L生成的一阶语言
个体常元: 函数符号: 谓词符号: a, b, c, …, a1, b1, c1,… f, g, h, …, f1, g1, h1,… F, G, H, …, F1, G1, H1, …
非逻辑符号并不一定都出现 一阶语言随着非逻辑符号的不同而不同，称为 由非逻辑符号集合L生成的一阶语言。
2012-2-22
一阶逻辑
8
字母表
个体常元: 函数符号: 谓词符号: 个体变元: 量词符号: 联结词符号: 括号与逗号:
2012-2-22
a, b, c, …, a1, b1, c1,… f, g, h, …, f1, g1, h1,… F, G, H, …, F1, G1, H1, … x, y, z, …, x1, y1, z1,… ∃, ∀ ¬, ∧, ∨, →, ↔ (, ), ，
原子公式是合式公式 若A是合式公式，则(¬A)是合式公式 若A,B是合式公式，则(A∧B), (A∨B), (A→B), (A↔B)也是合式公式 若A是合式公式，则∃xA, ∀xA也是合式 公式 只有有限次地应用上述规则形成的符号 串才是合式公式
2012-2-22 一阶逻辑 16
合式公式（举例）
∃x(F(x)∧∀y(G(y)→H(x,y))) F(f(a,a),b) F(x,y) 约定：省略多余括号
赋值(举例)
F(f(a,a),b) 赋值1： 个体域是全体自然数; a: 2; b: 4; f(x,y)=x+y; F(x,y): x=y 原公式赋值成: “2+2=4”。 赋值2： 个体域是全体实数; a: 3; b: 5; f(x,y)=x-y; F(x,y): x>y 原公式赋值成: “3-3>5”。
2012言是用于一阶逻辑的形式语 言 一阶逻辑是建立在一阶语言上的逻 辑体系
2012-2-22
一阶逻辑
5
一阶语言
谓词演算形式系统语言
•非逻辑符号 •逻辑符号 •项 •（合式）公式
2012-2-22
一阶逻辑
6
非逻辑符号
个体常元: 函数符号: 谓词符号: a, b, c, …, a1, b1, c1,… f, g, h, …, f1, g1, h1,… F, G, H, …, F1, G1, H1, …
可满足式：非永假式
2012-2-22 一阶逻辑 24
代换实例
在含命题变项p1,p2,……,pn的命题公式中, 每个命题变项代换成一阶逻辑公式所得 到的式子, 称为原来公式的代换实例. 例： F(x)→G(y) ¬ ∀xF(x)∨G(y)
2012-2-22
一阶逻辑
25
一阶逻辑公式分类
例： ¬∀xF(x) ↔ ∃x¬F(x) ∀xF(x) →(G(y) → ∀xF(x) ) ∃xF(x) → ∀yG(y) ¬(∀xF(x) →∃yG(y) ) ∧ ∃yG(y)
把函数和谓词中的变元直接写到符号后 的括号中,如F(x,y,x), g(x,y)等 非逻辑符号集合常记为L
2012-2-22 一阶逻辑 7
逻辑符号
个体变元: 量词符号: 联结词符号: 括号与逗号: x, y, z, …, x1, y1, z1,… ∃, ∀ ¬, ∧, ∨, →, ↔ (, ), ，
2012-2-22 一阶逻辑 22
赋值
是否存在一种公式在任何赋值下都 取相同的真值呢？
2012-2-22
一阶逻辑
23
一阶逻辑永真式(tautology)
永真式:在各种赋值下取值均为真(逻辑有 效式) 命题逻辑永真式: 在各种赋值下取值均为真
(重言式)
永假式:在各种赋值下取值均为假(矛盾式)
命题逻辑永假式: 在各种赋值下取值均为假 (矛盾式)
2012-2-22
一阶逻辑
14
原子公式(atomic formula)
若R(x1,x2,…,xn)是n元谓词, t1,t2,…,tn是项, 则R(t1,t2,…,tn)是原子公式 例如: F(a), G(a,y), F(f(a)), G(x,g(a,y))
2012-2-22
一阶逻辑
15
合式公式(well-formed formula)
2012-2-22
一阶逻辑
10
L生成的一阶语言举例
如：非逻辑符号
个体常元: 函数符号: : 0 +
L1={0, +} 如：非逻辑符号
个体常元: 函数符号: 0，1 +,*
L2={0,1, +,*}
2012-2-22 一阶逻辑 11
L生成的一阶语言说明
非逻辑符号与所描述的特定对象有关。 逻辑符号是逻辑系统中的符号。 一阶逻辑研究一阶语言的一般性质，而 不是针对某个特定的一阶语言。对一个 具体的应用而言，L通常是不言自明的， 由使用的全部非逻辑符号组成。
闭式: 无自由出现的变项 一般来说, 闭式表示的是命题, 例如
F(a) ∃xF(x) F(x) ∀y(G(y)→H(x,y))
后两个不是闭式
2012-2-22 一阶逻辑 20
赋值(解释interpret)
对一个合式公式的赋值包括给出
个体域 谓词 函数 个体常项
的具体含义
2012-2-22
一阶逻辑
21
一阶(谓词)逻辑
量词 谓词、函数 个体词 个体域
全总个体域: 世界上的万事万物 特性谓词: 表示所关注的对象的性质
2012-2-22 一阶逻辑 1
苏格拉底三段论
凡人都是要死的。 苏格拉底是人。 所以，苏格拉底是要死的。 重新符号化：∀, ∃, F( ), x, a 设：F(x)：x是人。G(x)：x是要死的。 a：苏格拉底。 前提：∀x(F(x)→G(x))，F(a) 结论：G(a)
2012-2-22 一阶逻辑 12
一阶(first order)逻辑的合式公式
项 原子公式 合式公式
2012-2-22
一阶逻辑
13
项(term)
个体常项和个体变项是项 若ϕ(x1,x2,…,xn)是n元函数, t1,t2,…,tn是项, 则ϕ(t1,t2,…,tn)是项 所有的项都是有限次地应用上述规则形 成的 例如: a, x, f(a), g(a,x), g(x,f(a))
2012-2-22 一阶逻辑 18
合式公式中的变项(举例)
H(x,y)∨∃xF(x)∨∀y(G(y)→H(x,y)) x 与 y 是指导变项 x与y是约束出现 x与 y是自由出现 注：同一变元在同一公式中可能既有约 束出现又有自由出现
2012-2-22 一阶逻辑 19
闭式(closed form)
2012-2-22
一阶逻辑
26
习题
P66 10,11,12,15
2012-2-22
一阶逻辑
27