当前位置：文档之家 › 离散数学第二章一阶逻辑

离散数学第二章一阶逻辑

  • 格式：ppt
  • 大小：275.50 KB
  • 文档页数：25

下载文档原格式

  / 25

合集下载

第二章一阶逻辑

第二章一阶逻辑
本命题符号化为 ┐ x(W(x)→B(x))。
练习2 在一阶逻辑中将下列命题符号化。 ⑴ 兔子比乌龟跑得快。 ⑵ 每个人都有自己喜欢的职业。 ⑶ 不存在同样高的两个人。 ⑷ 存在最小的自然数。 解 ⑴兔子比乌龟跑得快。 令F(x)：x是兔子， G(x)：x是乌龟， H(x,y)：x比y跑得快。 本命题符号化为 x(F(x)→ y(G(y)→H(x,y)))， 或 x y(F(x)∧G(y)→H(x,y))。
⑷ 存在着偶素数。
⑸ 在北京工作的人未必都是北京人。
解 ⑴有的有理数是整数。
令Q(x)：x是有理数。 P(x)：x是整数。 本命题符号化为 x (Q(x)∧P(x))。
⑵每个计算机系的学生都学离散数学。
令P(x)：x是计算机系的学生。
R(x)：x学离散数学。
本命题符号化为x (P(x)→R(x))。
⑶ 每个人都会犯错误。
令 R(x)：x是人。 P(x)：x会犯错误。 本命题符号化为 x (R(x)→P(x))。
⑷ 存在着偶素数。
令E(x)：x是偶数。
P(x)：x是素数。
本命题符号化为 x(E(x)∧P(x))。
⑸在北京工作的人未必都是北京人。
令W(x)：x在北京工作。
B(x)：x是北京人。
母a, b, c, d 等表示常元。
个体变项（也称个体变元，简称变元）：泛指
个体域中个体的符号。一般用小写英文字母x, y,
z 等表示变元。
例
2是有理数。 这是一个简单命题。 “2”是个体词 “…是有理数”是谓词，它表示个体的性 质。 个体词：是表示个体的符号。 谓词：用来刻画个体的性质或个体之间的关 系。一般用大写英文字母表示谓词。 例 张三比李四高。 有两个个体词：张三，李四 “…比…高”是谓词，表示两个体之间的关 系。

《离散数学》-一阶逻辑-基本概念

《离散数学》-一阶逻辑-基本概念

《离散数学》-⼀阶逻辑-基本概念⼀阶逻辑这个⼀块属于离散数学的内容，它的功能就是将⾃然事物给符号化以为体系的确⽴奠定语⾔基础。

回想⽆论学汉语还是英语的语法，我们都是从句⼦的主⼲学起，那么数学作为⼀门语⾔，它的句⼦当然也有所谓的主⼲。

个体词：个体次是所研究对象可以独⽴存在的具体的或者抽象的客体。

具体⽽特定的客体个体成为个体常项，⼀般⽤⼩写字母a、b、c表⽰。

⽽将抽象或泛指的个体词成为个体变项，⼀般⽤英⽂字母x、y、z表⽰，并称个体变项的取值范围为个体域。

举例说明：(1)“5是素数”，5、素数都是个体词语，5是个体常项⽽素数是个体变项.(2)“x>y”，x、y都是个体变项.谓词：这⾥似乎类似于⾃然语⾔中谓语动词，往往是形容“⼀个动作”，但是在这⾥，谓词是形容“⼀种关系”，当然和个体词类似，根据这种描绘个体之间的关系的确定与否(具体或者抽象泛指)，我们也可以把谓词分为常项和变项。

举例说明:（1） X是有理数。

“是有理数”是常项谓词。

（2） X与y有具体关系L。

这⾥及其迷惑⼈的是语句“有具体关系L”，但是本质上关系L还是抽象的不确定的，因此这⾥“有具体关系L”是变项谓词。

下⾯要做的就是将这种描述关系的语句进⾏符号化，这⾥其实有点类似于函数的概念，因为谓词描述的是个体之间的关系，因此它必须依赖于个体。

我们⽤F、G、H来进⾏符号化的表⽰。

F(a)、F(x)分别表⽰个体常项a、个体变项x满⾜的性质F(a)和F(x).更⼀般的情况，P(x1,x2,x3…xn)表⽰个体x1,x2,…xn具有关系P。

对于不含个体变项的谓词，我们成为0元谓词。

Ex1：将下列命题在⼀阶逻辑中⽤0元谓词符号化，并讨论他们的真值(1) 只有2是素数，4才是素数。

G(2)表⽰2是素数，G(4)表⽰4是素数，则我们将这个命题符号化的结果： G(2) —> G(4)，由于命题的条件为假，因此该命题为真。

(2) 如果5⼤于4，则4⼤于6G(5,4)表⽰“5⼤于4”，命题符号化之后的结果： G(5,4) —> G(4,6)，条件为真结论为假，因此命题为假。

离散数学第2章习题解答

离散数学第2章习题解答
当然非闭式也可以是逻辑有效式(如F(x) F(x))，也可能为矛盾式(如
F(x) F(x))，也可能不存在其值不确定的解释。
2．10(1)
xA(x)
(A(a)
A(b)
A(c))
(消去量词等值式)
A(a)
A(b)
A(c)
(德·摩根律)
x A(x)
(消去量词等值式)
2)
xA(x)
(A(a)
A(b)
A(c))
( H (b,a) H (b,b) H (b, c)
(H(c,a) H(c,b) H (c,c)
分析 在有穷个体域内消去量词时， 应将量词的辖域尽量缩小， 例如，在(2) 中，首先将量词辖域缩小了(因为yG(y)中不含x，所以，可以缩小)。否则，演算是相当麻烦的。见下面的演算：
x(F(x) yG(y)
x(F(x) (G(x) H (x))
(2)令F(x):x是人，G(y):y是化，H (x) : x喜欢，命题符号化为x(F(x) y(G(y) H ( x, y)))
(3)令F(x):x是人，G(x) : x犯错误，命题符号化为
x(F(x) G(x)),
或另一种等值的形式为
x(F(x) G(x)
(4)令F(x): x在北京工作，G( x) : x是北京人，命题符号化为
在一阶逻辑中，将命题符号化时，当引入特性谓词(如题中的F(x))之后，
全称量词后往往使用联结词→而不使用，而存在量词 后往往使用 ，而不使用→，如果用错了，会将真命题变成假命题，或者将假命题变成真命题。
2．6在解释R下各式分别化为
(1)x( x 0);
(2)x y(x y x);
(3)x y z(x y) (x z y z));

一阶逻辑推理理论

一阶逻辑推理理论

一阶逻辑推理实例
命题逻辑中的推理规则及在一阶逻辑中
的代换实例，在一阶逻辑推理中仍然使 用 量词消去和引入规则
例1: 证明苏格拉底三段论“凡人都是要死的。 苏格拉底是人.所以苏格拉底是要死的。” 命题符号化：F（x）：x是人（特性谓词）； G（x）：x是要死的； a：苏格拉底 前提：x（F(x)→G(x)），F(a) 结论：G(a) 证明： （1）x（F(x)→G(x)） 前提引入 （2）F(a)→G(a) UI(1) （3）F(a) 前提引入 （4）G(a) (2)(3)假言推理
xA(x) A(y)中， y应为任意的不在A(x)中约束 出现的个体变项。
全称量词引入规则（简称UG规则） A(y) xA(x) ③ 公式成立的条件是 1.y在A(y)中自由出现，且y取任何值时A均为真 2.取代y的x不在A(y)中约束出现。
例:设定义域为实数， 取F(x,y)为x>y，A(y)=xF(x,y)=x(x>y)， A对任意给定的y都是真的。 如下推理是否正确 : ①xF(x,y) 前提引入 ②xxF(x,x) ①UG xx(x>x)是假命题，推理出错。 出错的原因是违背了条件2：取代y的x不在A(y) 中约束出现 ②zxF(x,z) ①UG √
例: 在自然数集中，设F(x)为x是奇数，G(x)是x 是偶数，则xF(x)∧xG(x)是真命题. 以下推理 是否正确： (1) xF(x)∧xG(x) 前提引入 (2) xF(x) (1)化简规则 (3) xG(x) (1)化简规则 (4) F(a) (2)EI (5) G(b) (3)EI (6) F(a)∧G(b) (4)(5)合取规则 (7) x(F(x)∧G(x)) (6)EG
前提: x ( F(x) → G(x)) ，x ( F(x) ∧ H(x) ) 结论: x ( G(x) ∧ H(x) )

离散数学PPT课件

离散数学PPT课件
定义2.1设A,B是两个命题公式，若A，B构成的等价 式AB为重言式，则称A与B等值，记为AB。
20
例2.1判断下面两个公式是否等值： (pq), pq 例2.2判断下面各组公式是否等值： （1）p(qr) 与 (pq)r （2） ( pq)r与 (pq)r
21
置换规则 ： 设（A）是含公式A的命题公式， （B） 是用公式B置换了（A）中所有的A以后得到的命题公式， 若BA，则（B） （A）。
定义1.2 设p，q为两命题，复合命题“p并且q”称为p与 q的合取式，记作“pq”。 pq为真当且仅当 p， q同 时为真。
定义1.3 设p，q为两命题，复合命题“p或q”称为p与q的 析取式，记作“pq”。 p q为假当且仅当 p， q同时为 假。
7
例1.3将下列命题符号化 （1）吴影既用功又聪明。 （2）吴影不仅用功而且聪明。 （3）吴影虽然聪明，但不用功。 （4）张辉与王丽都是三好学生。 （5）张辉与王丽是同学
16
例1.8求下列公式的真值表，并求成真赋值。 (1) (pq)r (2) (pp)(qq) (3) (p q) q r
定义1.10设A为一命题公式 （1）若A在它的各种赋值下取值均为真，则称A是重 言式或永真式。 （2）若A在它的各种赋值下取值均为假，则称A是矛 盾式或永假式。 （3）若A不是矛盾式，则称A是可满足式。
离散数学
1
离散数学课件
离散数学是计算机科学的核心理论课程， 是计算机专业的专业基础课。
第一部分 数理逻辑 第二部分 集合与关系代数 第三部分 图论
2
第一部分数理逻辑
第一章 命题逻辑基本概念 第二章 命题逻辑等值演算 第三章 命题逻辑推理理论 第四章 一阶逻辑基本概念 第五章 一阶逻辑等值演算与推理

离散数学-第2章 习题课

离散数学-第2章 习题课

A(a) B(a) C(a) D(b) E(b) F (a, b)
24
谓词公式与翻译
例12 从数学分析中极限定义为：任给小正数s，则 存在一个正数z，使得当0<|x-a|<z时有|f(x)-b|<s。 此时称 lim f ( x ) b
x
解： P(x,y)表示“x大于y”，Q(x,y)表示“x小于y”， 故 lim f ( x ) b 可以表示为：
16
谓词公式与翻译
例7 用谓词公式写出下式。 若x<y和z>0,则xz>yz
解：设G(x,y):x大于y。则有
(x)(y)(z)(G( y, x)G(0, z) G( xz, yz))
17
谓词公式与翻译
例8 自然数共有三个公理： a)每个数都有唯一的一个数是它的后继数。 b)没有一个数，使数1是它的后继。 c)每个不等于1的数，都有唯一的一个数是它的直接 先行者。 用两个谓词表达上述三条公理
27
变元的约束
例14 对 (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( y, y)) Q( x, y)。因为后两种更改 都将使公式中量词的约束范围有所变动。
( P(a) Q(a)) ( P(b) Q(b)) ( P(c) Q(c)) d) (x)P( x) (x) P( x)
(P(a) P(a) P(a)) ( P(a) P(a) P(a))
29

离散数学 第二章 谓词逻辑 习题课

离 散 数 学
第二章 谓词逻辑 习题课
一. 命题符号化 60页(2)
a) (x)(J(x)→L(x)) b) (x)(L(x)∧S(x)) c) (x)(J(x)∧O(x)∧V(x)) d) J(j)∧O(j)∧V(j) e) (x)(L(x)→J(x)) 或者 (x)(L(x)∧J(x) f) (x)(S(x)∧L(x)∧C(x)) g) (x)(C(x)∧V(x) 或者(x)(C(x)→V(x)) h) (x)((C(x)∧O(x))→L(x)) i) (x)(W(x)∧C(x)∧H(x)) j) (x)(W(x)∧J(x)∧C(x)) k) (x)(L(x)→y(J(y)∧A(x,y))) l) (x)(S(x)∧y(L(y)→A(x,y)))
习题课
5)b)设N(x):x是数，A(x,y):y是x的后继数
(x)(N(x)∧A(x,1))
(6)设A(x):x是戴眼镜的,B(x):x是用功的,C(x):x是大 学生,D(x):x是大的,E(x):x是厚的，F(x):x是巨著, A(x,y):x在看y,a:那位，b:这本 A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(b)∧ A(a,b)
75页
(1)b)(x)(yP(x,y)→(zQ(z)→R(x))) (x)(yP(x,y)∨(zQ(z)∨R(x))) (x)(yP(x,y)∨(zQ(z)∨R(x))) (x)(yP(x,y)∨ z(Q(z)∨R(x))) (x)yz(P(x,y)∨(Q(z)∨R(x))) (2)c)(x)P(x)→(x)(zQ(x,z)∨zR(x,y,z)) (x)P(x)∨(x)(zQ(x,z)∨zR(x,y,z)) (x)P(x)∨(x)(zQ(x,z)∨zR(x,y,z)) (x)P(x)∨u(zQ(u,z)∨tR(u,y,t)) (x)uzt(P(x)∨(Q(u,z)∨R(u,y,t))) (x)uzt(P(x)∨Q(u,z)∨R(u,y,t)) 此式既是前束析取范式，也是前束合取范式。

自考离散数学第二章答案

自考离散数学第二章答案-CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN习题2.1答案(从本章起，习题答案由jhju提供，晓津补充。

如有问题或不同意见，欢迎到分课论坛发表)1、用谓词表达式写出下列命题a)小张不是研究生；解：设A(x)：x是研究生；a:小张；|A(a)。

b)他是跳高或篮球运动员；解：设A(x):x是跳高运动员；B(x):x是篮球运动员；a: 他；A(a)∨B(a) 。

c)晓莉非常聪明和能干；解：设 A(x):x非常聪明；B(x):x能干；l: 晓莉；A(l)∧B(l)d)若m是奇数则2m是偶数解：设 A(x): x是奇数B(y):y是偶数m:某数A(m)→ B(2m)2、将下列命题符号化并要分析到个体词及谓词a)长江流经四川省；解：B(x,y):x流经y；a:长江 b:四川省B(a,b)。

个体词：长江、四川省谓词：流经b)这架新式歼击机击沉了那艘老式快艇解：设A(x,y):x击沉了ya:新式歼击机 b:老式快艇A(a,b).个体词：歼击机、快艇谓词：击沉3、用谓词表达式符号化下列命题。

那位戴眼镜穿西服的大学生在看一本英文杂志。

解：设：A(x): x戴眼镜；B(x): x穿西服；C(x): x在看英文杂志；a: 那位大学生A(a)∧B(a)∧C(a)这个表达式的含义就是一个陈述句：那位大学生戴眼镜且那位大学生穿西服且那位大学生在看英文杂志。

个体词是：那位大学生。

谓词有：戴眼镜、穿西服、在看英文杂志。

2.2习题答案(从本章起，习题答案由jhju提供，晓津补充。

如有问题或不同意见，欢迎到分课论坛发表)题号：1234561、对下列公式指出约束变元和自由变元，并指明量词的辖域。

a,(x)(P(x)—→Q(x))∧(x)R(x,y)；(x)的指导变元是x,其辖域是(P(x)—→Q(x))(x)的指导变元是x,其辖域是R(x,y)对于(x)来说，x是约束出现，y则是自由出现。

一阶逻辑推理--离散数学


(5) (P(a)) (6) P(a)
(3); (4); 假言三段论 (5); 双重否定律
15
例6
符号化下述命题,并推证其结论。
“所有有理数是实数，某些有理数是整 数，因此某些实数是整数。” 解 先将命题符号化 令Q(x):x是有理数；R(x):x是实数;I(x);x是整数. x(Q( x) R( x)), x(Q( x) I ( x)) x( R( x) I ( x)) 证明 (1) x(Q( x) I ( x)) 前提 (2) x(Q( x) R( x)) 前提 (3 ) Q(c) I (c) (1); ES (4) Q(c) R(c) (2);US (5) Q(c) (3); 化简 (6) R(c) (4), (5); 假言推理 (7) I (c) (3); 化简 (8) R(c) I (c) (6), (7); 合取引入 (9) x( R( x) I ( x)) (8); EG 16
13
（3） （4） （5） （6） （7） （8） （9）
x( P( x) Q( x)) P(c) P (c ) Q (c ) Q (c) xQ(x)
xP( x) xQ( x)
xP( x) xQ( x)
例5 用构造推理过程的方法证明
(1) x( P( x) Q( a)) xP( x) Q( a)
因为 xP( x) xQ( x) xP( x) xQ( x) 所以 原题可转化为证明
x( P( x) Q( x)) xP( x) xQ( x)
证法二 （1）xP(x)
（2）
xP(x)
附加前提 （1）；量词否定等值式 前提 （2）；ES （3）；US （4）（5）；析取三段论 （6）；EG （1）（7）；CP （8）；蕴含等值式，德摩根

离散数学(屈婉玲版)第二章习题答案

2.13 设解释I为：个体域D I ={-2,3,6},一元谓词F（X）：X≤3，G（X）：X>5,R(X):X≤7。

在I下求下列各式的真值。

（1）∀x(F(x)∧G(x))解：∀x(F(x)∧G(x))⇔(F(-2) ∧G(-2)) ∧(F(3) ∧G(3)) ∧(F(6) ∧G(6))⇔((-2≤3) ∧(-2>5)) ∧((3≤3) ∧(3>5)) ∧((6≤3) ∧(6<5))⇔((1 ∧0))∧((1 ∧0)) ∧((0 ∧0))⇔0∧0∧0⇔0(2) ∀x(R(x)→F(x))∨G(5)解：∀x(R(x)→F(x))∨G(5)⇔(R(-2)→F(-2))∧ (R(3)→F(3))∧ (R(6)→F(6))∨ G(5)⇔((-2≤7) →(-2≤3))∧ (( 3≤7) →(3≤3))∧ (( 6≤7) →(6≤3)) ∨ (5>5)⇔(1 →1)∧ (1 →1)∧ (1→0) ∨ 0⇔1∧ 1∧ 0 ∨ 0⇔0(3)∃x(F(x)∨G(x))解：∃x(F(x)∨G(x))⇔(F(-2) ∨ G(-2)) ∨ (F(3) ∨G(3)) ∨ (F(6) ∨G(6))⇔((-2≤3) ∨ (-2>5)) ∨ ((3≤3) ∨ (3>5)) ∨ ((6≤3) ∨ (6>5))⇔(1 ∨ 0) ∨ (1 ∨ 0) ∨ (0 ∨ 1)⇔1 ∨ 1 ∨ 1⇔12.14 求下列各式的前束范式，要求使用约束变项换名规则。

（1）⌝∃xF(x)→∀yG(x,y)(2) ⌝（∀xF(x,y) ∨∃yG(x,y) ）解：（1）⌝∃xF(x)→∀yG(x,y)⇔⌝∃xF(x)→∀yG(z,y) 代替规则⇔∀x⌝F(x)→∀yG(z,y) 定理2.1（2 ）⇔∃x(⌝F(x)→∀yG(z,y) 定理2.2（2）③⇔∃x∀y(⌝F(x)→G(z,y)) 定理2.2（1）④（2）⌝（∀xF(x,y) ∨∃yG(x,y) ）⇔⌝(∀zF(z,y) ∨∃tG(x,t)) 换名规则⇔⌝(∀zF(z,y) )∧⌝(∃tG(x,t) )⇔∃z⌝F(z,y) ∧∀t⌝G(x,z)⇔∃z (⌝F(z,y) ∧∀t⌝G(x,z))⇔∃z ∀t(⌝F(z,y) ∧⌝G(x,t))2.15 求下列各式的前束范式，要求使用自由变项换名规则。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(2) ∀x∀y(x+0=y →y+0=x) 真命题 (3) ∀x∀y∃z(x+y=z) 真命题 (4) ∀x∀y(x+y=x*y) 假命题 (5)x+y=y+z,它的真值不确定,因而不是命题. 注)非闭式,在有的解释中不是命题.
定义:设A为一公式(谓词公式),如果A在任何解释下都是 真的,则称A为逻辑有效式(永真式);如果A在任何解释下 都是假的,则称A是矛盾式(永假式);若至少存在一个解 释使A为真,则称A是可满足式. 2.代换实例 设A0是含命题变项p1,p2,…,pn的命题公式,A1,A2,…,An 是n个谓词公式,用Ai(1≤i≤n)处处代换pi,所得公式A 称为A0的代换实例. 例如:F(x)→G(x),∀xF(x)→∃xG(x)等都是p→q的代换实例; 命题公式中的重言式的代换实例在谓词公式中可仍称为重言式 ,这样的重言式都是逻辑有效式. 命题公式中的矛盾式的代换实例仍为矛盾式.
例2.7 给定解释I如下: 1)DI={2,3} 2)DI中特定元素a=2 3)函数f(x)为f(2)=3,f(3)=2 4)谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(i,j)=1,i,j=2,3 L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0 在解释I下,求下列各式的真值 (1) ∀ ∀x(F(x)∧G(x,a)) (2)∃x(F(f(x))∧G(x,f(x))) ∃ (3)∀x∃yL(x,y) ∀ ∃
例2.2 在一阶逻辑中将下面命题符号化 (1)凡有理数均可表成分数; (2)有的有理数是整数; 要求:1)个体域为有理数集合, 2)个体域为实数集合, 3)个体域为全总个体域. 解: 1)个体域为有理数集合(不用引入特性谓词): (1) 设 F(x):x可表成分数; 则命题符号化为∀xF(x). ∀ (2) 设 G(x):x是整数;则命题符号化为∃xG(x). 2)个体域为实数集合(引入特性谓词):令 R(x):x是有理数; (1) 设F(x):x可表成分数;则命题符号化为∀x(R(x)→F(x)) (2) 设G(x):x是整数;则命题符号化为∃x(R(x)∧G(x))。
(2)由于p→(q→p)⇔￢p∨(￢q∨p) ⇔1为重言式, 而原公式∀xF(x)→(∀x∃yG(x,y)→∀xF(x))是该重言式的 代换实例,因而是逻辑有效的. (3)由于p→(p∨q)⇔￢p∨(p∨q) ⇔1为重言式 而原公式∀xF(x)→(∀xF(x)∨∃yG(y))是该重言式的代换 实例,所以是逻辑有效的. (4)由于￢(p→q)∧q⇔(p∧￢q)∧q⇔0是矛盾式, ⇔ ⇔ 而原公式￢(F(x,y)→R(x,y))∧R(x,y)是该矛盾式的代 换实例,故是矛盾式. (5)取解释I如下:1)个体域为自然数集合N;2)F(x,y)为x=y 为此∀x∃yF(x,y)→∃x∀yF(x,y),有前件∀x∃yF(x,y)为真, 后件∃x∀yF(x,y)为假;故原公式为矛盾式; 又取解释I如下:2)F(x,y)为x≤y; 前件∀x∃yF(x,y)为真,后 件∃x∀yF(x,y)为真;公式为重言式;故原公式为可满足式
2.2 一阶逻辑合式公式及解释
一.合式公式(谓词公式) 1.原子公式:设R(x1,x2,…,xn)是任意的n元谓词,t1,t2,…,tn是 项, R(t1,t2,…,tn)为原子公式. 2.合式公式定义如下: (1)原子公式是合式公式; (2)若A是合式公式,则(￢A)也是合式公式; (3)若A,B是合式公式,则(A∧B),(A∨B),(A→B),(A↔B)也 是合式公式. (4)若A是合式公式,则∀xA,∃xA也是合式公式; (5)只有有限次地应用(1)-(4)构成的字符串才是合式公式, 也称为谓词公式,并简称为公式.
解: 设(1),(2),(3)中公式分别为A,B,C,在解释I下: (1)A⇔(F(2)∧G(2,2))∧(F(3)∧G(3,2))⇔(0∧1)∧(1∧1)⇔0 (2)B⇔(F(f(2))∧G(2,f(2)))∨(F(f(3)∧G(3,f(3))) ⇔(F(3)∧G(2,3))∨(F(2)∧G(3,2))⇔(1∧1)∨(0∧1)⇔1 (3)C⇔(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))⇔1∧1⇔1
2.1一阶逻辑的基本概念 2.1一阶逻辑的基本概念
个体常项:表示具体的或特定的个体的词(用a,b,c,…表示). 个体变项:表示抽象的或泛指的个体的词(用x,y,z,…表示). 个体域(论域):个体变项的取值范围. 全总个体域:宇宙间的一切事物组成的个体域. 谓词常项:表示具体性质或关系的谓词(用F,G,H,…表示). 谓词变项:表示抽象的或泛指的谓词(用F,G,H,…表示). 在谓词中所包含的个体词数,含n(n≥1)个个体词的谓词称为n元 谓词.一元谓词是表示个体词性质的,n(n≥2)元谓词是表示个体 词之间关系的.有时将不带个体变项的谓词称为0元谓词. 个体变项x具有性质F,记作F(x),个体变项x,y具有关系L,记作 L( ∀x∀y(R(x,y)∨L(y,z))∧∃xH(x,y)改为 ∀x∀y(R(x,y)∨L(y,z))∧∃tH(t,w); 可知x,y为指导变项,量词的辖域为(R(x,y)∨L(y,z)),x,y 为约束出现,z为自由出现;t为指导变项,∃的量词辖域为 H(t,w),t为约束出现,w为自由出现,此公式为非闭式.
第2章一阶逻辑
2.1 一阶逻辑基本概念
2.2 一阶逻辑合式公式及解释
2.3 一阶逻辑等值式
名词与术语
一阶逻辑(谓词逻辑):对简单命题分析出其中的个体词,谓词, 量词等,研究他们的形式结构及逻辑关系,总结出正确的推理 形式和规则. 简单命题被分解成个体词和谓词两部分. 个体词:是指可以独立存在的客体,它可以是一个具体的事物, 也可以是一个抽象的概念.(名词或代词). 谓词:是用来刻画个体词的性质或个体词之间关系的词. 量词:表示数量的词,表示存在性的量词称为存在量词,用“∃” 表示,表示全局性的量词称为全程量词,用“∀”表示.
例2.6指出下列各合式公式中的指导变项,量词的辖域, 个体变项的自由出现和约束出现. (1) ∀x(F(x)→∃yH(x,y)); (2) ∃xF(x)∧G(x,y); (3) ∀x∀y(R(x,y)∨L(y,z))∧∃xH(x,y) 解: (1) ∃yH(x,y)中, y为指导变项, ∃的辖域为H(x,y),其 ∃ ∃ 中y是约束出现的,x是自由出现.整个合式公式中,x是指导变 项, ∀的辖域(F(x)→∃yH(x,y)),x,y都是约束出现的,x约束 出现2次,y约束出现1次. ∀ ∀x(F(x)→∃yH(x,y))为闭式. ∃ (2)利用换名规则,将∃xF(x)∧G(x,y)改为 ∃zF(z)∧G(x,y); 可知:z为指导变项, ∃的辖域F(z),z为约束出现,x,y为自 由出现,此公式为非闭式. 或利用代替规则将∃xF(x)∧G(x,y)改为 ∃xF(x)∧G(z,y).
例2.1 将下列命题用0元谓词符号化 (1)2是素数且是偶数. (2)如果2大于3,则2大于4. (3)如果张明比李民高,李民比赵亮高,则张明比赵亮高. 解: (1)设F(x):x是素数; G(x):x是偶数; a:2; 则命题符号化为F(a)∧G(a). (2)设L(x,y):x大于y; a:2; b:3; c:4; 则命题符号化为L(a,b) →L(a,c). (3)设H(x,y):x比y高; a:张明; b:李民; c:赵亮; 则命题符号化为H(a,b)∧H(b,c) →H(a,c).
二.公式的解释 1.特定解释:一个解释I由下面4部分组成: (1)非空个体域D; (2)D中一部分特定元素; (3)D上一些特定的函数; (4)D上一些特定的谓词; 注)若D={a1,a2,…,an},对于任意的谓词A(x)都有 (1) ∀xA(x)⇔A(a1)∧A(a2)∧… ∧A(an) (2) ∃xA(x)⇔A(a1)∨A(a2)∨ … ∨A(an)
3.指导变项,辖域,约束出现和自由出现 在合式公式∀xA和∃xA中,称x为指导变项,称A为相应量 词的辖域,在辖域中,x的所有出现称为约束出现;A中不是 约束出现的其他变项的出现称为自由出现. 4.封闭的合式公式(闭式) 设A为任一公式,若A中无自由出现的个体变项,则称A是封闭 的合式公式,简称闭式. 注)闭式在任何解释下都是命题. 5.换名规则和代替规则 换名规则:将量词辖域中出现的某个约束出现的个体变项及 对应的指导变项,改成另一个辖域中未曾出现过的个体变项符 号,公式中其余部分不变. 代替规则:对自由出现的个体变项用与原公式中所有个体变 项符号不同的变项符号去代替,且处处代替.
例2.8 给定解释N如下: 1)个体域为自然数集合DN, 2)DN中特定元素a=0,
3)DN上特定函数f(x,y)=x+y,g(x,y)=x*y 4)DN上特定谓词F(x,y)为x=y 在解释N下,下面哪些公式为真,哪些公式为假? (1) ∀xF(g(x,a),x) (2) ∀x∀y(F(f(x,a),y)→F(f(y,a),x) ∀ ∀ ∃ (3) ∀x∀y∃zF(f(x,y),z) (4) ∀x∀yF(f(x,y),g(x,y)) ∀ ∀ (5)F(f(x,y),f(y,z)) 解: 在解释N下,公式分别化为 (1) ∀x(x*0=x) 假命题
例2.4 在一阶逻辑中将下面命题符号化 (1)凡偶数均能被2整除; (2)存在着偶素数; (3)没有不犯错误的人; (4)在北京工作的人未必都是北京人. 解: 在本题中,没指定个体域,因而取个体域为全总个体域. (1) 设F(x):x是偶数,G(x):x被2整除; 则∀x(F(x)→G(x)); (2) 设F(x):x是偶数,G(x):x是素数; 则∃x(F(x)∧G(x)); ∃ (3) 设M(x):x是人,G(x):x犯错误，则￢∃x(M(x)∧￢G(x)); 或∀x(M(x)→G(x)); (4) 设F(x):x在北京工作的人, G(x):x是北京人; 则命题符号化为∃x(F(x)∧￢G(x))或￢∀x(F(x)→G(x));