高级数理逻辑第4讲

4一阶谓词逻辑

4.1 一阶谓词逻辑的基本概念

4.1.1命题逻辑的局限性

命题逻辑中的原子命题是最小的研究单元，不再进行深入研究。因此，命题逻辑对现实世界的描述能力是有限的。

1、例如：

所有自然数都大于它的素数 A ?x(A(x)→y?(P(x,y) ∧Q(y)))

A(2100)→y?(P(2100,y) ∧Q(y))

?x(A(x)→y?(P(y,x) ∧Q(y)))

2100是自然数B A(2100)

2100有大于它的素数C y?(P(y, 2100) ∧Q(y))

对于这个现实中的例子，用命题逻辑无法描述。因为，用命题逻辑来描述，第一个句子是一个原子命题、二三句同样是原子命题。而这些原子命题之间无法建立关联关系。

因此，每一个前题都是单一的命题，没有联结词。所以用命题逻辑描述它不能进行推理。然而上述推理是正确的，是现实中存在的现象。

2、再例如：

所有实数的平方是非负的A

-是实数B

3

-的平方是非负的C

3

4.1.2一阶谓词逻辑

1、概述

一阶谓词逻辑解决了上述问题，能够对原子命题进行分割和更细致的研究工作。

●个体域：任何一门科学都有其研究对象，这些对象的集合称为个体域。个体域

即论域包含所描述问题域中的常元和变元。P(x)

●函词：个体上可以进行运算，能够产生新的个体。这些运算被称为函数，在一

阶谓词里被称为的函词（函数）。F(x,y)=x*y

●谓词：我们在研究个体的时候，主要研究个体的性质。这些有关个体性质的描

述称为谓词。

Q(y), P(x,y) ::x

●量词：关于个体性质，不一定是对全体的个体的都成立。有的对一个范围内成

立，有离散的几个个体成立，有的对全部都成立。为了描述这种范围特征，一

阶谓词引入了量词。

2、谓词和函词

●谓词定义：谓词表示个体性质和关系的语言成分。它附带放置对象的空位，只

有空位被填充对象，谓词才有意义。没有被填充对象的谓词，称为谓词命名式；

相反为谓词填式。谓词后面的空位个数为谓词的元数。谓词是一个体域上的n

元关系。

通常P(x,y,z)=0,1，表示x,y之间具有关系P(1,2)。

●函词定义：函词是表示某种操作的语言成份。用于在给定的个体基础上，产生

新的个体对象。与谓词一样，函词具有空位的概念。函词后面空位的个数为函

词的元数。

通常用F(x,y,z)=x+y+z表示。

3、变元和常元

●常元：常元表示个体域中的一个确定个体。如：5，Zhang San 等。

●变元：变元可以用来表示个体域上的任意个体，是不确定的。

例如：（1）z+y=0 P(f(y,z)) 二元谓词表示方程

P(f(x,z))==;P(f(-3,2))

－3＋2＝0

Z+y=x+y=0

（2）对所有z，x，y?x=x?y Q(x*Z,Z*x) 二元谓词表示乘法交换率

Q(x,z)=1

3*2=2*3

Q (f(x,y),f(y,x))=

Q (f(1,2),f(2,1))=1

从这个例子来看，变元是具有不同的性质的。因此，在一阶谓词逻辑中将变元划分成自由变元和约束变元。f(x)+x+z=0

对于所有的X,Y,P(x,y)<=P(X,Y)

●自由变元：自由变元是真正的变元，可以将个体域中的任意个体代入到自由变

元中。类似于数学中的变元。

●约束变元：约束变元并不是实际意义的变元（数学意义上的变元）。约束变元

是为表达某种想的辅助符号。

●自由变元与约束变元的对比：

自由变元约束变元

可代入不可代入

不可改名可改名

举例说明：采用上例。

4、量词

我们引入了谓词、函词、变元和常元的概念，还不能充分的描述现实中的命题。例如对于下面的命题：

如果P(x)对任意x恒真，则P(x+1)恒真。

我们现在表示，只能用P(x)→P(x+1)，来表示。而这种表示方法没有确定的含义，例如可以认为P(x)是存在一个x 的值是P(x)成立。为了描述这些谓词的成立范围，一阶谓词逻辑引入了量词的概念。

?x Q(X2)=~ x ?~Q(X2)

x ?Q(X,100000)=~?x ~Q(X,100000) ~?x Q(X,100000)= x ?~Q(X,100000)

?z ?y(Q(z*y,y*z))

? x P(x) →?yP(y+1)；P 大于0，x 论域是自然数, ?xP(x)→ ?yP(y+1)

?x ? y(P(x)→P(y+1))

? x (P(x) →P(x+1)); P 大于0，x 论域是实数

● 全称量词：)(x xP ?中的?称为全称量词，x ?中的x 称为?的指导变元；

)(x P 称为量词的辖域。 x ?(A(x))-->B(x)

● 存在量词：)(x xP ?中的?称为存在量词，x ?中的x 称为?的指导变元；)(x P 称为量词的辖域。 x ? (A →B)→C ==x=1,A(1)→B(1) A(1)→B(1) x ?A →B

A(1,…)=1

● 指导变元是约束变元。 ● 量词等价公式：

1. ?xA(x)╞│)))(((x A x ???

{1,2,3} === ~(~(A(1)^A(2)^A(3)))=1 P(x,y)

Y=1, x=1,x=2,x=3, P(x,y)=1===P(1,1),P(2,1), P(3,1)=1

X=1, y=1, P(1,1)=1 P(1,2)=0, P(1,3)=0 X=2, y=2 P(2,2)=1, P(2,1)=P(2,3)=0 X=3, y=3, P(3,1)=P(3,2)=0, P(3,3)=1 ; \ ~(~A(1)v~A(2)v~A(3))=~~A(1)&~~A(2)&~~A(3) 2. )(x xP ? ╞│))((A x ??? 3. ))((x xP ??╞│))((x P x ??

4. )(x xP ??╞│))((x P x ??

5. yA x ??╞│ xA y ??

6. yA x ??╞│xA y ??

yA x ??(x,y) f(x) xA y ??(x,y) x ?(A(x)→A(x+z)) x ?A(x)→A(x+z)

?xA(x) V ?xB(x)=?x(A(x)VB(x);

A(1)^A(2)^A(3) B(1)^B(2)^B(3) A(1), B(1); B(2),A(2); A(3), B(3)

==== ?x ?y(A(x) VB(y))= ?x(A(x)VB(x))

5、 用一阶谓词逻辑描述问题：

例如：所有实数的平方是非负的

3-是实数 3-的平方是非负的

一阶谓词的表示： ))()((2x P x R x →?

)3(-R ))3((2-P

4.2 一阶形式系统（FSFC ）

回顾形式系统的构成，主要有语言部分和推理部分构成。语言部分是一阶语言。

4.2.1 一阶语言

一阶语言可以从以下几个方面定义：符号表、项集、公式集等三个部分。 1、符号表

● 个体变元符号：x,y ……

● 个体常元符号：2

1.....

a a ● 函词符号：

,,,)

1(3)1(2)1(1f f f

（一元函词）

,,,)(3)(2)(1n n n f f f

（n 元函词）

● 谓词符号：

,,,)1(3)1(2)1(1P P P

（一元谓词） ,,,)(3)(2)(1n n n P P P

（n 元谓词）

● 联结词：?→, ● 量词：? ● 技术符：)(,

2、项：谓词所讨论的对象。项是递归定义的集合，其定义如下：

（1）变元和常元交项；

（2）对于任意正整数n 和函数)

(n f

，如果n

t t ........1为项

那么).......(1n n t t f 为项；

（3）除有限次使用（1）（2）得到外，没有任何项。 {a, x, f()}={a, x,fn(a), fn(x)}

由定义可知，项集是递归定义的、是可判定的。

3、公式集：公式由以下递归定义：

（1）对于任意正整数n ，如果n

t t ........1为项，那称).......(1n n t t P 为公式，并为原

子公式；

（2）如果A ，B 为公式，那么B A A →?,，xA ?公式；

（3）公式都是有限次使用（1）（2）得到的，除此之外无其他公式。

4.2.2 一阶语言性质

● 闭项：不含自由变元的项),(21a a f ，

● 闭公式：不含自由变元的公式

P(a,b) ?y(P(a,y)→B(y)) = ?x((P(a,x))－>B(x))

?y(P(a,y)－>B(y))= ?x(P(a,x)－>B(x)) ?x(P(a,x)－>B(y))

?x(P(a,x)－>B(x)) A(x)=1,0;;;, ?x A(x);

● 辖域：公式A 称为量词)(x x ??的辖域，如果)(x x ??与A 相邻，且A 的任何真截断不是公式

● 约束出现：在公式A 中，变元x 的某个出现叫做约束出现，如果x 为?(x)的指导

变元或在?x ，?x 的辖域内。否则为自由出现

)()(1211x P x P x ?→?=VyP(y)→~P2(x1)

x 1为约束出现，x 2为自由出现

● 可代入性：称项t 是对A 中自由变元x 可代入的；如果A 中项x 的任何自由出现

都不在)(y y ??的辖域内，这里y 是t 中的任意自由变元。

?y ?x ?zP(x,z) ?yP(x,f+1)

?yA(x,y) t=y+1;

?yP(x+1,z)

P(5,6)

t=y+1 ?yP(y+1,z) t=(x1+z) A=?yP(x1+z,z)

)(),(y q y x xP →? )(),(a x q a x x xP +→+? )(),(a x q a x z zP +→+?

y=x+a=t 不可代入，y=z+a 为可代入的。

● 代入：将公式A 中变元x 的所有自由出现代换为项t 的过程称为代入，代入后所得

公式称A 的实例。

将项x+a 代入到公式)(),(y q y x xP →?中的y 得到：

)(),(a z q a z x xP +→+?

P(x,y,z)→Q(x)

(y+1)/x, P(y+1,y,z)→Q(y+1) P(y+1,z+1,z)→Q(y+1)

(z+1)/y, P(z+2,z+1,z)→Q(z+2) P(x,z+1,z)→Q(x)

P(y+1,z+1,z)→Q(y+!)

?yP(x,z) ?yP(x,f+1)

?yP(z+1,z):::: ?yP(y+x+1,y+x) ?yP(z+1,y+x)

{(z+1)/x, (y+x)/z}

我们用记号n n v

v v t t t A ,,,,,2121 表示对A 中变元n v v v ,,21，同时作代入，1v 代换为项1t …n v 代换为项n t 。这与下面的逐步代入是不同的：

n n v t v t v t A )))(((2211

?xP(x,y,z)====

Y=z+1, z=y1+1

?xP(x,z+1,y1+1)

?xP(x,z+1,z), ?xP(x,y1+2,y1+1)

Y=y1+2; z=y1+1

例：设公式A 为21)

2(v v P 可以写为),(21v v P ，那么 v2→v1, v3→v2

P(v1,v2)==P(v2,v2)==P(v3,v3) P(v2,v3)

),()((3333)2(2

312v v P v v P A v v v v ==

P(V1,V2)-----P(v2,v2)----P(v3,v3)

P(v2,v3)

P(v1,v2);P(v2,v2);P(v3,v3) P(v1,v2);P(v2,v3)

),(3232)2(,,3

122

v v P v v P A v v v v ==

P(v1,v2)=P(v2,v2)=P(v3,v3) P(v1,v2)=(v2,v3)

可代入性保证了代入过程中变项的约束关系不发生改变，即原来约束的代入后仍旧是约束的；原来自由的代入后仍旧是自由的。

● 子公式：称公式B 为A 的子公式，如果A 为形如'

wBw 的符号串，其中B 为公式。

当'

,w w 有一个非空时，称为真子公式。

● 改名：任何约束变元可改名，公式A 中变元x 为约束出现，将x 改为其它变元，

是合理的

)()(21x xP x P ?→ ＝P1(x)→VyP2(y) )()(21y yP x P ?→ ))()((21y yP x P x ?→?

?xA(x)-->A(x)

))()(()))()(((2121y P x P y P x P y x →→→??

两式等价。

● 公式性质和项的性质（递归集合），可以用归纳证明（根据公式和项定义过程来证

明）。 ● 设n v v v ,,21为公式A 中所有的自由变元，那么公式A v v v r i i i ???,,21 称为公式

A 的全称化（generalizations ），其中n i i i r ≤≤ ,,122。公式A v v v n ???,,21 称为公式A 的全称封闭式。当A 中无自由变元时，A 的全称封闭式是A 本身。

4.2.3 推理部分

推理部分包含：公理集合和推理规则集合。 1、公理集合

A 1 ))((A

B A →→

)))()(()((z zP y B x xP ?→→?

A 2 ))()(())((C A

B A

C B A →→→→→→ A 3 )()(A B B A →→?→?

A 4 x t A xA →?（t 对于A 中的变元x 是可代入的，将t 代入A 中的x ） A 5 )()(x

B xA B A x ?→?→→?

A 6 xA A ?→(x 在A 中无自由出现==无出现)

2、推理规则

分离规则

B

B

A A →,

4.2.4 推理性质

● A 1-A 3为FSPC 中的公理，所以为FSFC 中的公理；但意义不同，A,B,C 代表的是

FSFC 中的任意公式。

● A 6：xA A ?→, 变元x 在A 中无自由出现。

? 对约束出现变量不改变意义，例如：对于公式)(x xP ?与))((x xP x ??具有同

样的意义。

? 对自由出现时，改变了原来的意义，例如：对于公式)(x P 与))((x P x ?具有不同的意义。

? 对于没有出现的变量，则不改变原公式的意义。

4.3 一阶谓词演算

利用公理和推理规则进行推理演算，与命题系统类似，但更为复杂。

4.3.1 基本概念

对于演绎结果、证明序列等概念与形式系统和命题形式系统完全相同。在此不在重复。 例：证明对于FSFC 的任何公式A ，变元v ，├A vA →?。 )()()(z yP x P y x ?→??

证：由于项v 对公式A 中自由变元v 总是可代入的，因此v

v A vA →?为公理，而v

v

A 是A ，因此A vA →? ?x A-->A; 证明对于FSFC 的任何公式A ，变元v ，├A v A ???→。 证： )()(A v A A A v ???→??→?→?? （1）公理3 A A v ?→??

（2）公理4

A v A ???→??

（3）mp r （2）（1）

B=A(x)-->A(x)==1 x ?(A(x)-->A(x) ）=0 B=~A(x)-->A(x)==0 , ?x(~A(x)-->A(x))=1

4.3.2 主要的定理

以下列出的定理是在FSFC 的形式演算中经常使用的性质。

1、命题形式系统中的重言式是FSFC 的定理：即存在证明序列，由公理和推理规则得到重言式。

证明：假设A 为FSPC 中的重言式，因此A 为FSPC 中的公理或者定理。

因此，在FSPC 中，存在A 的一个证明序列

A 1……….A n （＝A ）,

其中A i 或者为公理，或者为A i1，A i2由分离规则得到的。 对证明序列长度n 归纳证明： 当n=1时，A 为FSPC 的公理，同时为FSFC 公理。因此，命题成立。 假设n

当n=m 时，由于A 是由A i , A j 通过分离规则得到的。假设A i = A A j →。

由于归纳假设有：A i , A j ，为FSFC 的定理。因此，A 为FSFC 的定理。

2、全称推广规则：对于FSFC 中的任一公式A ，变元x 在A 中无自由出现，如果├A,则├xA ?。

证明：由于├A ，则存在一个A 的证明序列：

)(,,,,321A A A A A l =

xA A ?→ xA ?

对证明序列长度归纳证明。 ● 当1=l 时，A 为公理；

若x 在A 中无自由出现，则

（1）xA A ?→ 公理 （2）A 前题

（3）xA ? rmp(1,2)

● 假设n l <时，定理成立；

● 当n l =时，分成以下集中情况：

? 若A n 为公理，则同Ⅰ;

? 若A n 不为公理，则A n 为A i , A j 分离规则得到的。不妨设A j =A i →A n 。由

假设 ├A i ├i xA ?， ├n i A A →，├)(n i A A x →?

（1）i xA ?

归纳假设 （2）)(n i A A x →?

归纳假设 （3）├)()(n i n i xA xA A A x ?→?→→? 公理

（4）n i xA xA ?→?

（2，3）

（5）n xA ?

（1，4）

所以有：├xA ?。由此定理成立。

3、全称推广规则推广：对于FSFC 中的任意公式集合∑，公式A ，变元x 不在∑中自由出现，如果∑├A ，则∑├xA ?。

4、演绎定理：设∑为FSFC 中的任意集合，A,B 为FSFC 中的任一公式。那么∑，A ├B 当且仅当∑├A →B 。

5、反证规则：如果FSFC 公式集合{}A ??∑是不一致的，那么∑├A 。

证明：由于{}A ??∑是不一致的，因此有公式B ，是A ?∑;├B, A ?∑;├?B 同时成立。根据演绎定理有：

（1）∑├B A →? 归纳假设 （2）∑├B A ?→?

归纳假设 （3）)))(()(A B A B A →?→?→→? 为重言式 （4）A B A →?→?)(

（1，3）

（5）∑├A （2, 4）

6、替换原理：在FSFC 中，如果已知公式A,B 满足A ├│B ，A 是C 的子公式，D 是将C 中A 的若干出现替换于B 所得到的公式，则C ├│D 。

7、改命原理：在FSFC 中，称公式A ′为公式A 的改名式，如果将A 中至少一个量词的指导变元和相应的约束变元（如果有）都改为另一个相同名字的变元后得到的公式A ’。在FSFC 中，如果A ’为公式A 的改命式，且A ’改用的变元在A 中无任何出现，那么A ├│A ’。

?xP(a,x,x,y) =?zP(a,z,z,y) ?xP(x,y)→ E x P(x,z)

8、量词规则

● 全称（?）消去规则：如果∑├)(x xA ?，且项t 对于公式)(x A 为可代入的，

则∑├)(t A 。 证明： （1）)(x xA ?

前提

（2）)()(t A x xA →?

（3）)(t A

● 全称（?）引入规则：如果∑├)(t A ，t 不在∑中出现，则∑├)(x xA ?。

● 存在（?）销去规则：设∑为FSFC 的任意公式集合，A, B 为公式。变元x

在∑和公式B 中无出现。如果∑├)(x xA ?，A ,∑├B 则∑├B 。 A1,A2,….An |-有一些b1,b2论域中的两个元素，使得A(b1，b2)＝1。

A1,A2,….An,A|-B

A1,A2,….An|-B

● 存在（?）引入规则：设∑为FSFC 的任意公式集合，B 为公式。变元x 在∑

和公式B 中无出现。如果∑├B ，则∑├)(x xB ?。

?xP(x)→P(x)→ ?xP(x) A(1)-->?xA(x)

4.3.3 示例

1、例：用演绎定理证明：对FSFC 中对任一公式集∑，公式A,B, A ,∑├B ?当且仅当B ,∑├A ?。

证明：

充分性证明：设A ,∑├B ?，则有：

（1）∑├B A ?→

演绎定理

（2）)()(A B B A ?→→?→ 重言式 （3）∑├A B ?→ (1,2) (4 ) B ,∑├A ?

演绎定理

必要性同理可证。

2、例：利用改名原理证明：对FSFC 中任意公式A ，变元x ，y ，yA x ??├x

y yA ?。

?x ?y P(x,y)→ ?y P(y,y)

?x ?z P(x,z)→ ?z P(x,z)→ ?z P(y,z)→ P(y,z)→P(y,y)→ ?y P(y,y)

证明：由于y 对x 是不代入的，所以不能使用公理4

（1）yA x ??

已知 （2）y

z zA x ?? 将y 改名为z

改名原理

（3）y

z zA x ??→))((x

y y z A z ?

公理4（因为：y 在y

z zA ?对x

可代入）。

（4）x y y z A z )(?

(2,3) （5）x y y z A z )(?→z

y x y y z A ))(( 公理4 （5）x y yA ?

3、例：证明存在（?）销去规则。 如果∑├)(x xA ?，A ,∑├B 则∑├B 。

（1）∑ |-B A →

演绎定理

（2）)()(A B B A ?→?→→ 公理3 （3）∑ |-)(A B ?→?

（1，2）

（4）∑ |-)(A B x ?→??

全称推广 （5）))()(()(A x B x A B x ??→??→?→?? 公理5 （6）∑ |-)()(A x B x ??→??

（4，5）

（7）))()(())()((B x A x A x B x ???→???→??→?? 公理3 （8）))()(())()((xB xA A x B x ?→?→??→?? 量词等价式 （9）∑ |-)()(xB xA ?→?

（4，8）

（10）∑ |-xA ? 已知

（11）∑ |-xB ?

（9，10）

（12）B x B ??→?)(

公理6 （13）)())((B B x B x B →???→??→? 公理3

（14）B xB →? （12，13） （15）∑ |-B

（11，14）

形式逻辑 第四章 复合判断

第四章判断(二) [学习提示]本章介绍各种复合判断。通过本章的学习,要了解什么就是复合判断、复合判断分类的根据;各种复合判断的逻辑形式及逻辑性质。 各种复合判断的逻辑形式与逻辑性质就是复合判断推理的基础,就是本章学习的重点内容,要牢固掌握。其中还要注意把握联言判断与相容选言判断、相容选言判断与不相容选言判断、充分条件假言判断与必要条件假言判断之间的联系与区别;几种主要的负判断及其等值判断的逻辑形式;假言判断的等值转换形式等内容。 第一节复合判断概述 一、什么就是复合判断？ 指本身含有其它判断的判断。如:未来战争或者就是核战争,或者就是常规战争。 二、复合判断的构成及形式 复合判断由联结词将支判断(命题变项)联结起来而构成。 形式:就是由联结词与命题变项组成的表达式。 三、复合判断的种类 以联结词的逻辑性质为标准,分为联言判断、选言判断、假言判断与负判断四种。 第二节联言判断 一、什么就是联言判断 联言判断就是断定若干事物情况共同存在的复合判断。例如: 泰山既雄伟,又壮丽。 联言判断由联言支与联言联结项构成。联言支可以有两个或三个以上,联言支通过联结项“并且”联结起来。一个二支联言判断的逻辑形式就是: P并且q 在现代逻辑中,“并且”也可用“∧”(读作“合取”)表示。这样,联言判断的逻辑形式也可表示为: P∧q 在现代汉语中,联言判断用并列复句、递进复句、连贯复句、转折复句与某些单句表达。 在日常生活中,联言命题常用省略的语言形式表达,如: 虚心使人进步,骄傲使人落后(省略连接词) 二、联言判断的真假值 联言判断的真假决定于联言支的真假。一个联言判断,只有当它的联言支都真时,它才就是真的,只要有一个联言支假,它就就是假的。 两个联言支中如果有一个假或者两个都假时,那么,这个联言判断就就是假的。 联言判断的真假值与联言支的真假值的制约关系可以用下列真值表来表示:

数理逻辑复习题

一、选择题 1、永真式的否定是（2） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 2、设P ：2×2=5，Q ：雪是黑的，R ：2×4=8，S ：太阳从东方升起，则下列真命题为(1) (1)R Q P ∧→ (2)S P R ∧→ (3)R Q S ∧→ (4) )()(S Q R P ∧∨∧。 3、设P ：我听课，Q ：我看小说，则命题R “我不能一边听课，一边看小说”的符号化为⑵ ⑴ P Q → ⑵Q P ?→(3) Q P →? ⑷ P Q ?→?()P Q ?∧ 提示：()R P Q P Q ??∧?→? 4、下列表达式错误的有⑷ ⑴()P P Q P ∨∧? ⑵()P P Q P ∧∨? ⑶()P P Q P Q ∨?∧?∨ ⑷()P P Q P Q ∧?∨?∨ 5、下列表达式正确的有⑷ ⑴ P P Q ?∧ ⑵ P Q P ?∨ ⑶ ()Q P Q ???→⑷Q Q P ??→?)( 6、下列联接词运算不可交换的是(3) ⑴∧ ⑵∨ (3)→ ⑷ ? 6、设D ：全总个体域，F （x ）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢y ，则命题“有的人喜欢所有的花”的逻辑符号化为⑷ ⑴(()(()(,))x M x y F y H x y ?∧?→ ⑵(()(()(,))x M x y F y H x y ?∧?→ (3) (()(()(,))x M x y F y H x y ?∧?→ ⑷(()(()(,))x M x y F y H x y ?∧?→ 7、设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些 老 师”的逻辑符号化为⑵ ⑴)),()((y x A x L x →? ⑵))),()(()((y x A y J y x L x ∧?→? (3) )),()()((y x A y J x L y x ∧∧?? ⑷)),()()((y x A y J x L y x →∧?? 8、谓词公式)())()((x Q y yR x P x →?∨?中的 x 是⑶ ⑴自由变元 ⑵约束变元 ⑶既是自由变元又是约束变元 ⑷既不是自由变元又不是约束变元 9、下列表达式错误的有⑴ ⑴(()())()()x A x B x xA x xB x ?∨??∨? ⑵(()())()()x A x B x xA x xB x ?∧??∧? (3) (()())()()x A x B x xA x xB x ?∧??∧? ⑷(()())()()x A x B x xA x xB x ?∨??∨?

第四章知识推理技术p

第四章知识推理技术 本章主要在知识表达的基础上，讨论“知识的运用”即知识推理的概念和方法。 第一节知识推理的概念和类型 一．知识推理的基本概念 所谓“知识推理”（Knowledge Inference）是指在计算机或智能机器中，在知识表达的基础上，即利用形式化的知识模式——表达与问题有关知识的符号体系，进行及其思维、求解问题、实现知识推理的智能操作过程。一句话，知识推理就是运用知识求解问题。 知识推理的过程就是问题求解的过程，知识推理技术就是使问题从初始状态转移到目标状态的方法和途径。 研究人工智能的知识推理技术，目的是寻求问题、实现状态转移的智能操作序列，以便从初始状态，沿着最优或最经济的途径，有效地转移到所要求的目标状态，实现问题求解过程的智能机械化或计算机化。 例如：利用计算机制定机器人的行动规划，安排机器人从出发地点到目的地点所需的操作序列和行动路线。又如，利用计算机证明数学定理，给出从已知条件开始到定理证明完毕所需的算子序列和演算步骤等等都是知识推理技术的运用。 二．知识推理技术的类型 1.根据知识表达法分类 知识推理是以知识表达技术作为前提条件的，它们之间有着密切的关系，由知识表达的特点，知识推理技术可概括为两种类型： （1）“图搜索”方法 在人工智能的知识表达技术中，许多基本的、常用的表达方式都具有图的形式，或者可以变换为相应的（同种或同态变换）图的形式，并且，往往可用树图表达。例如：状态空间态、与/或树图、语义网络图以及由生产是系统或框架表达方式所变换的树图或网络图。 针对图的知识表达，问题求解的知识推理过程，就是从图中相当于初始状态

的出发结点到相当于目标状态的终结点的路线搜索过程。即搜索从初始状态有效地转移到目标状态，所经历的最优向或最经济的路线，相应的知识推理方法即“图搜索”方法。 广度优先搜索法 基本的图搜索法 深度优先搜索法 （2）“逻辑论证”方法 当知识采用谓词逻辑或其他方法的形式逻辑表达时，知识推理的便成为逻辑论证。在此情况下，求解两个问题相应于证明一个定理或几个定理，问题求解的知识推理过程相应于用数理逻辑方法进行定理证明的过程。 例如：在自动问答系统中，如果用一组谓词逻辑表达式A描述提问的内容，包括有关的事实、情况和条件，而用另一组谓词逻辑表达式B描述问题的答案或结论，那么，只要通过逻辑演算的方法论证定理：A→B成立，也就相应于完成了该问题的知识推理。 基本的逻辑推理方法主要有：命题逻辑中的机器定理证明的王浩算法和一阶谓词逻辑中定理证明的鲁宾逊消解方法。 2.根据问题求解过程的完备性分类 根据问题求解过程是否完备，可将知识推理方法分为： （1）推理算法 若问题求解的知识推理过程是完备的，则对于可解的问题从任意初始状态出发，通过这种推理过程，总可以找到一条求解路线，经过有限的、确定的操作序列，转移所要求的目标状态，保证推理过程的收敛性，求得问题的解答。这种推理过程具有完备性，而完备的推理过程称为“推理算法”。 例如：王浩算法就是一种知识推理算法。又如广度优先搜索推理方法具有完备性，也是一种知识推理的搜索算法。 （2）推理步骤 若问题求解的推理过程是不完备的，则不能保证其推理过程的收敛性，以任意初始状态转移到目标态，不一定能求得问题的解答。这种推理过程是不完备的、非算法的，称为“推理步骤”。

北邮高级数理逻辑课件

形式系统由{∑, TERM, FORMULA, AXIOM, RULE}等5个部分构成，其中 称为符号表，TERM 为项集；FORUMULA 为公式集；AIXIOM 为公理集；RULE 为推理规则集。： 1、 符号表∑为非空集合，其元素称为符号。 2、 设∑* 为∑上全体字的组合构成的集合。项集TERM 为∑* 的子集，其元素称为项； 项集TERM 有子集V ARIABLE 称为变量集合，其元素称为变量。F(X) a, X, 3、 设∑* 为∑上全体字的组合构成的集合。公式结FORMULA 为∑* 的子集，其元素称为公式；公式集有子集ATOM ，其元素称为原子公式。 A(f(a,x1,y)), A →B 4、 公理集AXIOM 是公式集FROMULA 的子集，其元素称为公理。 5、 推理规则集RULE 是公式集FORMULA 上的n 元关系集合，即 RULE=)}2(|{n FORMULA r n n n r ?∧≥∧?是正整数， 其元素称为形式系统的推理规则。 其中公式集和项集之间没有交叉，即TERM ∩FORMULA =φ，公式和项统称为表达式。 由定义可知，符号表∑、项集TERM 、公式集FORMULA 是形式系统的语言部分。而公理集AXIOM 、推理规则集RULE 为推理部分 形式系统特性 1、 符号表∑为非空、可数集合（有穷、无穷都可以）。 2、 项集TERM 、公式集FORMULA 、公理集AXIOM 和推理规则集RULE 是递归集合， 即必须存在一个算法能够判定给定符号串是否属于集合（可判定的）。 3、 形式系统中的项是用来描述研究的对象，或者称为客观世界的。而公式是用来描述 这些研究对象的性质的。这个语言被称为对象语言。定义公式和项产生方法的规则称为词法。 公理： I ))((A B A →→ II ))()(())(((C A B A C B A →→→→→→ III ))())()(((A B B A →→?→? 证明：A →A (1) A →(A →A) ((A →(B →C))→((A →B)→(A →C)) ((A →(B →A))→((A →B)→(A →A)) ((A →((A →A)→A))→((A →(A →A))→(A →A)) A →((A →A)→A)) (A →(A →A))→(A →A) (A →(A →A)) A →A

数理逻辑考试题及答案

“离散数学”数理逻辑部分考核试题答案 ━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━ 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：p∧q，其中，P：小刘怕吃苦；q：小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→p，其中，P：怕敌人；q：战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：r→(p→p)，其中，P：别人有困难；q：老张帮助别人；r：困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P：小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A：((p q)((p q) (p q))) r （1）B：(p(q p)) (r q) （2）C：(p r) (q r) （3）E：p(p q r) （4）F：(q r) r 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。 3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分） （0）设y=2|x|，x为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，x为实数。令P：y在x=0处可导，q：y在x=0处连续。由此，p为假，q为真。本题推理符号化为：(p q) q p。由p、q的真值，计算推理公式真值为假，由此，本题推理不正确。 （1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令p:2是素数，q:3是素数，r:5是奇数，s:6是奇数。由此，p=1，q=1，r=1，s=0。本题推理符号化为： ((p q) →s) p q) →(r s)。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算（5分） 1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。共2分） （0）求公式p→((q∧r) ∧(p∨(q∧r)))的主析取范式。 解：p→((q∧r) ∧(p∨(q∧r)))p∨(q∧r∧p) ∨(q∧r∧q∧r) p∨(q∧r∧p) ∨0 (p∧q∧r) ∨ (p∧1∧1) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨m7 (p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨m7 m0∨m1∨m2∨m3∨m7. （1）求公式((p→q)) ∨(q→p)的主合取范式。 解：((p→q)) (q→p) (p→q) (p→q) (p→q) p q M2.

高级数理逻辑第2讲全解

3命题逻辑形式系统（FSPC） 3.1 命题逻辑与命题演算 Leibniz提出逻辑推理变成符号演算不久，英国数学家BOOL提出了布尔代数。布尔代数把逻辑命题与逻辑推理归结为代数计算。把命题看作是计算对象；把联结词看作算子；讨论计算的性质。 1、命题（Propositions）：可以判断真假的陈述句。不涉及任何联结词的命题称为原 子命题。 2、联结词：?, →, ?, ∨, ∧为联结词，用于联结一个或者多个命题。 ~A=1-A →如果A成立则B成立，<->如果A成立则B成立，并且如果B成立则A成立； A→B A∨B，或者A成立或者B成立；A∧B，A成立并且B成立。 3、真值表：命题的真假称为命题的真值，用0表示假；用1表示真。 A←→B T(~A)=1-T(A) A=1, ~A=0, 1-A True(?A)＝1- True(A)，如果True(A)＝0，True(?A)=1：True(A)=1, True(?A) ＝0 T(A→B)=1 或者A不成立，或者B成立； A=1, B=1, A→B =1 A=0, B=1, A→B=1 A=0, B=0, A→B=1 A=1,B=0 A→B=0 或者A=0, 或者B＝1 ~AvB=A→B A<=B;;;; A<=B A=0,B=1 A=0时，B=?,1;A=1,B=1,1;A=1,B=0,0; A=0,B=0,T(A→B)=1;A=0,B=1,T(A→B)=1;A=1,B=0,T(A→B)=1;A=1,B=1,T(A→B) =1; A=0;T(A→B)=1 B=1;T(A→B)=1 A→B是或者A=0,或者B=1；=～AvB A<=B A∨B=MAX(A,B) A=1, B=0, 1;A=1,B=1, 1, A=0,B=1;1, A=0,B=0, 0 A∧B=MIN(A,B) =~(~A v ~B) DEMORGAN ~A ∨B True(A->B)：True（A）《＝True（B）

高级数理逻辑第11讲全解

总复习 本章对高级数理逻辑所讲述的内容总结，并对已经学习的内容进行回顾。在对所讲述的内容回顾之前，首先对整个数理逻辑学科的组成进行回顾，从而使大家有更深刻的认识。 数理逻辑学科 学科发展 从数理逻辑学中衍生出来的学科有很多，如：递归论、可计算理论、模型论、机器证明、知识工程、布尔代数等。这些理论都是以数理逻辑学为基础的。针对数理逻辑本身，由于这些学科的需求产生了很多不同种类的逻辑系统。 数理逻辑的不同种类，基本上都是从经典的逻辑系统中扩展而来的。这种扩展通常有语法扩展和语义扩展。 ●语法扩展：在经典逻辑系统中，扩充一些符号，从而衍生出新的逻辑系统。如模态 逻辑，二阶谓词逻辑等。 ●语义扩展：对逻辑系统中语义的范围等进行扩展，如模糊逻辑等。 数理逻辑通常划分成以下不同种类的逻辑系统： 1、经典逻辑：传统的命题逻辑、一阶谓词逻辑等。认为世界是黑白的，对于一个命题 非真既假。 2、模态逻辑：认为世界上任何事情的真假是与时间有着密切的关系的。 3、多值逻辑：认为世界上的对与错是没有绝对的，命题的真假是可以是多个甚至连续 值的。 4、非单调逻辑：讨论如何将人类的常识加入到逻辑系统中去。经典逻辑是单调逻辑， 既事实越多，已有的结论不会消失；而单调逻辑中，可能随着事实的增加原有的结论被否定。 体系构成 在高级数理逻辑（计算逻辑）中，每一种逻辑都自成体系。逻辑的体系过程主要包括以下几个方面： 1、形式系统：用符号的方式来描述一个逻辑系统的构成。类似于形式语言系统。 2、语义系统：针对形式进行解释的一套体系，这套体系确定了符号的含义的解释方法 和规则。 3、元理论：对形式系统组成、语义系统特性和形式与语义之间关系进行研究。从而保 证了数理逻辑的初衷（利用数学演算的方法来研究人类思维过程）。 4、自动化推理：在形式系统的基础上，研究利用计算机自动进行推理的理论和方法。 以及自动推理的效率提高方法和自动推理完备性研究。

高级数理逻辑第3讲全解

3命题逻辑形式系统（FSPC）－续3.4 命题逻辑语义 P(X)→Q(F(X－a)) A(X)-->A(X) X是复数，则（x-a）平方大于等于0； X=R Px是复数 Q(x)代表的是大于等于0 F代表的是平方 X复数 T(P(X))=0.5 P(X)→(Q(X)→P(X)) A→B 3.4.1基本概念 1、什么是形式系统的语义 （1）形式系统与具体的系统无关 （2）能够用形式系统来描述现实系统 （3）把从形式系统解释成“→”现实系统的过程成为语义 语义有多种类型：指称语义，克里普克语义，操作语义，公理语义等2．语义构成(指称语义) 语义主要有两部分： （1）结构：（有两个主要部分构成） *确定研究对象集合，论域或个体域 *把形式系统中的变量到论域中的一组规则映射规则（2）域值：指一组给公式赋值的规则 根据这项规则将－Atomic→Value中

3.4.2 命题逻辑语义 1、语义结构 由于没有变量，所以只有第二部分赋值，值域为{0,1} 赋值规则： I. {}1,0∈V P II. ???? ?===?0 ,11 ,0)(V V V A A A T(~A)= 当T （A ）＝0时，T(~A)=1。当T （A ）＝1时，T(~A)=0。 III. ?????=====∧0 0,01,1)(V V V V V B A B A B A 或 当T(A)=T(B)=1时，T(B A ∧)=1，其他情况T(B A ∧)=0。 IV. ?????=====∨0 01 11)(V V V V V B A B A B A ，或， 当T(A)＝1或者T （B ）＝1情况下，T （B A ∨）＝1，其他情况T （B A ∨）＝0。 V. ???===→，否则 或，01 01)(V V B A B A 当T(A)=0时候，T （B A →）=1,当T(B)=1时候，T （B A →）=1。其他情况下T （B A →）=0。 A B VI. ?????≠==?V V V V V B A B A B A ，，01)( 2、 语义的特殊公式 1) 公式A 为永真式，重言式tautologies ，如果对一切赋值v ，1=V A .

数理逻辑2.1

1.4 将自然语言转化为命题公式 *要把自然语言转化为命题公式, 按以下步骤进行. 1.首先判定这个句子是否命题逻辑中所研究的命题, 排除 一些不是陈述句的句子,以及一些不具有真假值的句子. 2.其次,找出这个句子中所包含的原子命题.通常只有一个主 语和一个谓语的句子就是一个原子命题. 3.再次,将句子中的原子命题用命题变量表示,在整个句子中, 若相同的原子命题出现多次,则用相同的命题变量表示同一原子命题. 4.然后,分析句子中连词的逻辑含义,确定句子的整体结构, 以及各支命题之间的逻辑关系. 5.最后,使用合适的命题联结词将各支命题符号化,最后写出 整个句子的命题公式. 例1.12: 1.我们在学好逻辑学的同时,还应学好其它学科. 2.我虽人到中年, 但求知欲并未减弱. 3.液体沸腾的原因是温度增高,或是压力下降. 4.李晓霞是湖南人或江西人. 5.逆水行舟,不进则退. 解: 1.设p: 我们要学好逻辑, q: 我们要学好其它学科. 公式: p∧q .

2.设p: 我人到中年, q: 我求知欲减弱. 公式: p∧┐q . 3.设p: 液体沸腾的原因是温度增高. q: 液体沸腾的原因是压力下降. 公式: p∨q . 4.设p: 李晓霞是江西人. q: 李晓霞是湖南人. 公式: (p∧┐q)∨(┐p∧q) . 5.设p: 逆水行舟会进, q: 逆水行舟会退. 公式: (p∧┐q)∨(┐p∧q) . 例1.13: 1.如果看不到事物的否定方面, 就不能科学地预见事物的 发展方向. 2.只有懂了事物的对立统一规律, 才能懂得事物的发展. 3.只要你努力, 就会取得成果. 4.会休息的人, 才会工作. 5.不会休息的人, 就不会工作. 6.哪里有他, 哪里就有歌声. 7.若要人不知, 除非己莫为. 8.除非他真心悔改, 才能得到群众的谅解. 9.除非整数x是奇数, 否则x会被2整除. 10.整数x能被2整除, 除非x是奇数.

逻辑学第四章 复合判断

第四章复合判断 这一章主要介绍复合判断的内容。后面第七章所讲的复合判断推理就是根据复合判断逻辑联结词的性质进行推演的。 ?复合判断就是自身中包含有其他判断的判断。P126 构成复合判断的其他判断，统称为支判断，用英文小写字母p、q、r…表示。 例：张三作案或者李四作案。（自身中包含有两个判断）P（支判断） q（支判断） 逻辑常项） 逻辑变项）组成的。 ?复合判断的真假由其支判断的真假和逻辑联结词的性质决定！P126③ ?逻辑联结词（逻辑常项）不同，是区分不同类型复合判断的唯一依据！ ?复合判断分为联言判断、选言判断（又分两种）、假言判断（又分三种）、负判断。 一、联言判断 P127 定义：“同时存在” 构成联言判断的支判断，叫联言支。 例⑴：既．要应付考试，又．要学点知识。 p（联言支） q（联言支） 其形式为：既p，又q

例⑵：不但 ．．要注意学习方法。 ．．要勤奋学习，而且 p（联言支） q（联言支） （作事得法，事半功倍；方法不当，事倍功半。）其形式为：不但p，而且q 例⑶：虽然 ．．紧要处常常只有几步。 ．．人生的道路漫长，但是 P(联言支) q（联言支）其形式为：虽然p，但是q 逻辑联结词：“并且” 说明：P127①～P128②所列的，均表示联言判断的联结词。有时为了语言表达的精炼，可省略掉联词。例如： ▲“网络诈骗不难防，不贪不给不上当。” ▲“语言，人们用来抒情达意；文字，人们用来记言记事。” ▲“社会主义核心价值观：富强、民主、文明、和谐；自由、平等、公正、法治；爱国、敬业、诚信、友善。”（12个联言支从国家、社会、个人行为三个层面概述了社会主义核心价值观的内容）命题形式：“p并且q”或“p∧q”（“∧”叫合取符合） 逻辑联结词的性质：联言支同时为真（即定义“同时存在”）真值表：P129 说明：真值表(truth table)是数理逻辑中用以定义判断联结词并确定复合判断真值(即真或假)的一种图表。 复合判断属二值逻辑，其真假组合情况为：2n 公式中的“2”表示二值逻辑的真和假。（真和假均称为真值）。

第一篇 数理逻辑复习题

第一篇 数理逻辑复习题 第1章 命题逻辑 一、单项选择题 1. 下列命题公式等值的是( ) B B A A Q P Q Q P Q B A A B A A Q P Q P ),()D (),() C ()(),()B (,)A (∧∨?∨∨?∨→→→?→→∨?∧? 2. 设命题公式G ：)(R Q P ∧→?,则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 3. 命题公式Q Q P →∨)(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 4 命题公式)(Q P →?的主析取范式是( )． (A) Q P ?∧ (B) Q P ∧? (C) Q P ∨? (D) Q P ?∨ 5. 前提条件P Q P ,?→的有效结论是( )． (A) P (B) ?P (C) Q (D)?Q 6. 设P ：我将去市里，Q ：我有时间．命题“我将去市里，仅当我有时间时”符号化为 ( ) Q P Q P Q P P Q ?∨??→→)D ()C ()B ()A ( 二、填空题 1. 设命题公式G ：P →?(Q →P )，则使公式G 为假的真值指派是 2. 设P ：我们划船，G ：我们跑步，那么命题“我们不能既划船，又跑步”可符号化为 3. 含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 4. 若命题变元P ，Q ，R 赋值为(1,0,1)，则命题公式G ＝)())((Q P R Q P ∨??→∧的 真值是 5. 命题公式P →?(P ∧Q )的类型是 ． 6. 设A ，B 为任意命题公式，C 为重言式，若C B C A ∧?∧，那么B A ?是 式(重言式、矛盾式或可满足式) 三、解答化简计算题 1. 判别下列语句是否命题？如果是命题，指出其真值. (1) 中国是一个人口众多的国家. (2) 存在最大的质数. (3) 这座楼可真高啊！ (4) 请你跟我走! (5) 火星上也有人. 2.作命题公式))(()(P Q P Q P ∨∧→→的真值表，并判断该公式的类型． 3. 试作以下二题：(1) 求命题公式(P ∨?Q )→(P ∧Q )的成真赋值． (2) 设命题变元P ,Q ,R 的真值指派为(0,1,1),求命题公式 ))()(()(Q R Q P R P →?∨→?∧?的真值． 4. 化简下式命题公式))()((P Q P Q P ∧?∧?∨∧ 5. 求命题公式))()((Q P P Q P ∧?∧→→的主合取范式. 6. 求命题公式R P R Q P P R Q ∨?∨→?∧→?∧)())((的真值． 7. 求命题公式)()(Q P Q P ?→∧→?的主析取范式，并求该命题公式的成假赋值．

数理逻辑

数理逻辑 引言 逻辑思想 亚里士多德欧几里德几何 逍遥学派斯多葛学派 麦加拉学派智者派 经院哲学经院逻辑 培根穆勒黑格尔康德 形式逻辑 数理方向 莱布尼茨 布尔 弗雷格 罗素皮亚诺 1903年《数学原则》 两个演算经典逻辑非经典逻辑 ●经典逻辑的一些基本特征： 1.是外延逻辑。 2.是二值逻辑。 3.承认排中律。 反证法：假设非A（即A未假），如果推出了逻辑矛盾，就能得到A。 4.承认矛盾律。 5.不含有模态词。 6.使用实质蕴涵。 7.是确定的、保真的推理。 8.基于离散性的逻辑 ●20世纪初以来新兴的非经典逻辑： 1.内涵逻辑（外延原则：用内涵不同但真值相同的命题去替换复合命题中的支命题，复合命题真值保持不变） 2.多值逻辑（将来可能命题） 3.模态逻辑 4.直觉主义逻辑 5.弗协调逻辑 6.相干逻辑、衍推逻辑 7.条件句逻辑 8.模糊逻辑概率逻辑辩证逻辑…… ●数理逻辑的应用领域： ——服务于哲学研究。 ——服务于数学研究。 ——服务于语言学研究。 ——服务于自然科学研究。 ——服务于计算机科学。 ●第一编命题逻辑的基本内容：

第一章主要介绍命题逻辑的一些比较重要的基本概念。主要包括命题、命题的真值、真值联结词、真值形式、真值函项、真值表、简化真值表、重言式、推理的形式结构、重言等值式等等。 第二章主要介绍公理化的命题演算系统。主要包括公理化的方法、命题演算形式系统、命题演算的定理的推演和证明、求否定运算和求对偶运算。 第三章主要介绍同一真值函项，不同表达式的标准表达形式——范式、优范式，以及命题演算系统的一致性、完全性，还有公理的独立性。 第四章主要是介绍了一些不同符号体系的命题逻辑以及不同于古典命题演算的其它命题演算系统(多值、直觉主义、模糊、模态、相干等)。 第一篇命题逻辑 ●“命题” 的两种理解 这是一本书。 This is a book. 此乃书也。 ●命题逻辑狭谓词逻辑谓词逻辑 命题逻辑，以简单命题作为研究基本单位，而不再对简单命题进行结构上的分析。 谓词逻辑，对简单命题进行了进一步的分解，它把命题分析到了个体变项、谓词和量词。 狭谓词逻辑，仅研究量词作用于个体变项。（广义谓词逻辑进行了进一步的推广，还研究量词作用于命题变项和谓词变项） 一·一简单命题复合命题命题的真值 ●简单命题：不包含其它的命题成分的命题。 ●复合命题：就是包含其它命题成分的。 基本的复合命题有哪些？ ●命题的真假 上海或者是中国最大的城市，或者不是中国最大的城市。 真值表中给出的真假是事实真假还是逻辑真假？ 复合命题的真假是怎样确定的？ 一·二真值联结词 自然语言联结词真值联结词真值联结词的名称 并非?否定 或者∨析取并且∧合取 若，则→蕴涵 当且仅当?等值一·三五个基本真值联结词 ●五个真值联结词的真值特征 1．否定的真值特征：总是取反值。 2．析取的真值特征：同假它为假，否则它为真； 3．合取的真值特征：同真它为真，否则它为假； 4．蕴涵的真值特征：前真后假它为假；否则它为真； 5．等值的真值特征：同真同假它为真，否则它为假。 ▲命题联结词的逻辑含义和自然语言联结词的含义并不完全相同。 1. 否定词与“并非”、“不” 2. 合取词与“并且”

形式逻辑 第四章 复合判断

第四章判断（二） [学习提示]本章介绍各种复合判断。通过本章的学习，要了解什么是复合判断、复合判断分类的根据；各种复合判断的逻辑形式及逻辑性质。 各种复合判断的逻辑形式和逻辑性质是复合判断推理的基础，是本章学习的重点内容，要牢固掌握。其中还要注意把握联言判断与相容选言判断、相容选言判断与不相容选言判断、充分条件假言判断与必要条件假言判断之间的联系和区别；几种主要的负判断及其等值判断的逻辑形式；假言判断的等值转换形式等内容。 第一节复合判断概述 一、什么是复合判断？ 指本身含有其它判断的判断。如：未来战争或者是核战争，或者是常规战争。 二、复合判断的构成及形式 复合判断由联结词将支判断（命题变项）联结起来而构成。 形式：是由联结词与命题变项组成的表达式。 三、复合判断的种类 以联结词的逻辑性质为标准，分为联言判断、选言判断、假言判断和负判断四种。 第二节联言判断 一、什么是联言判断 联言判断是断定若干事物情况共同存在的复合判断。例如： 泰山既雄伟，又壮丽。 联言判断由联言支和联言联结项构成。联言支可以有两个或三个以上，联言支通过联结项“并且”联结起来。一个二支联言判断的逻辑形式是： P并且q 在现代逻辑中，“并且”也可用“∧”（读作“合取”）表示。这样，联言判断的逻辑形式也可表示为： P∧q 在现代汉语中，联言判断用并列复句、递进复句、连贯复句、转折复句与某些单句表达。 在日常生活中，联言命题常用省略的语言形式表达，如： 虚心使人进步，骄傲使人落后（省略连接词） 二、联言判断的真假值 联言判断的真假决定于联言支的真假。一个联言判断，只有当它的联言支都真时，它才是真的，只要有一个联言支假，它就是假的。 两个联言支中如果有一个假或者两个都假时，那么，这个联言判断就是假的。 联言判断的真假值与联言支的真假值的制约关系可以用下列真值表来表示：

数理逻辑2.2

2.2 析取范式与合取范式 1.简单析取式与简单合取式 定义2.2: 命题变项及其否定统称为文字. 仅由有限个文字构成的析取式称作简单析取式. 仅由有限个文字构成的合取式称作简单合取式. *解释: 析取, 合取. 例子: p, ┐q, p∨┐p, ┐p∨q, p∨┐q∨r, p∨┐p∨r 都是简单析取式. ┐p, q, p∧┐p, p∧┐q, p∧q∧┐r, ┐p∧p∧q 都是简单合取式. 定理2.1: (1) 一个简单析取式是重言式当且仅当它同时含某个命题变项及其的否定式; (2) 一个简单合取式是矛盾式当且仅当它同时含某个命题变项及其否定式. *举例说明: p∨┐p∨q∨r, p∨┐q∨r p∧┐p∧┐q∧r, ┐p∧q∧r 2.合取范式与析取范式 定义 2.3: 由有限个简单合取式的析取构成的命题公式称为析取范式. 由有限个简单析取式的合取构成的命题公式称为合取范式. 析取范式与合取范式统称为范式. *析取范式的一般形式为A1∨A2∨…∨A s, 其中, A i为简单合取式, i =1, 2, …,s. 合取范式的一般形式为B1∧B2∧…∧B t, 其中, B j为简单析

取式, j = 1, 2, …, t. 例如: (p∧┐q)∨(┐q∧r)∨p是析取范式. (p∨q∨r)∧(┐p∨┐q)∧r∧(┐p∨┐r∨s)为合取范式. 定理 2.2: (1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式; (2) 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式; 例如: (p∧┐p∧q)∨(q∧┐q∧p∧r)∨(p∧┐p∧┐r)是矛盾式; (p∨r∨q∨┐q)∧(p∨┐q∨r∨┐r)∧(┐p∨p∨q∨┐r)是重言式. 3. 将合式公式转化为析取范式与合取范式 命题公式有5个联结词{∧,∨,┐,→,?}, 如何把包含这5个联结词的公式转化为合取范式或析取范式? (1) 蕴涵式与等值式 A→B?┐A∨B A?B?(A→B)∧(B→A) ?(┐A∨B)∧(┐B∨A) (2) 公式中的否定 ┐┐A?A ┐(A∧B)?┐A∨┐B ┐(A∨B)?┐A∧┐B (3) 析取范式与合取范式互换

高级数理逻辑第4讲分析

4一阶谓词逻辑 4.1 一阶谓词逻辑的基本概念 4.1.1命题逻辑的局限性 命题逻辑中的原子命题是最小的研究单元，不再进行深入研究。因此，命题逻辑对现实世界的描述能力是有限的。 1、例如： 所有自然数都大于它的素数 A ?x(A(x)→y?(P(x,y) ∧Q(y))) A(2100)→y?(P(2100,y) ∧Q(y)) ?x(A(x)→y?(P(y,x) ∧Q(y))) 2100是自然数B A(2100) 2100有大于它的素数C y?(P(y, 2100) ∧Q(y)) 对于这个现实中的例子，用命题逻辑无法描述。因为，用命题逻辑来描述，第一个句子是一个原子命题、二三句同样是原子命题。而这些原子命题之间无法建立关联关系。 因此，每一个前题都是单一的命题，没有联结词。所以用命题逻辑描述它不能进行推理。然而上述推理是正确的，是现实中存在的现象。 2、再例如： 所有实数的平方是非负的A -是实数B 3 -的平方是非负的C 3 4.1.2一阶谓词逻辑 1、概述 一阶谓词逻辑解决了上述问题，能够对原子命题进行分割和更细致的研究工作。 ●个体域：任何一门科学都有其研究对象，这些对象的集合称为个体域。个体域 即论域包含所描述问题域中的常元和变元。P(x) ●函词：个体上可以进行运算，能够产生新的个体。这些运算被称为函数，在一 阶谓词里被称为的函词（函数）。F(x,y)=x*y ●谓词：我们在研究个体的时候，主要研究个体的性质。这些有关个体性质的描 述称为谓词。 Q(y), P(x,y) ::x

●量词：关于个体性质，不一定是对全体的个体的都成立。有的对一个范围内成 立，有离散的几个个体成立，有的对全部都成立。为了描述这种范围特征，一 阶谓词引入了量词。 2、谓词和函词 ●谓词定义：谓词表示个体性质和关系的语言成分。它附带放置对象的空位，只 有空位被填充对象，谓词才有意义。没有被填充对象的谓词，称为谓词命名式； 相反为谓词填式。谓词后面的空位个数为谓词的元数。谓词是一个体域上的n 元关系。 通常P(x,y,z)=0,1，表示x,y之间具有关系P(1,2)。 ●函词定义：函词是表示某种操作的语言成份。用于在给定的个体基础上，产生 新的个体对象。与谓词一样，函词具有空位的概念。函词后面空位的个数为函 词的元数。 通常用F(x,y,z)=x+y+z表示。 3、变元和常元 ●常元：常元表示个体域中的一个确定个体。如：5，Zhang San 等。 ●变元：变元可以用来表示个体域上的任意个体，是不确定的。 例如：（1）z+y=0 P(f(y,z)) 二元谓词表示方程 P(f(x,z))==;P(f(-3,2)) －3＋2＝0 Z+y=x+y=0 （2）对所有z，x，y?x=x?y Q(x*Z,Z*x) 二元谓词表示乘法交换率 Q(x,z)=1 3*2=2*3 Q (f(x,y),f(y,x))= Q (f(1,2),f(2,1))=1 从这个例子来看，变元是具有不同的性质的。因此，在一阶谓词逻辑中将变元划分成自由变元和约束变元。f(x)+x+z=0 对于所有的X,Y,P(x,y)<=P(X,Y) ●自由变元：自由变元是真正的变元，可以将个体域中的任意个体代入到自由变 元中。类似于数学中的变元。 ●约束变元：约束变元并不是实际意义的变元（数学意义上的变元）。约束变元 是为表达某种想的辅助符号。 ●自由变元与约束变元的对比： 自由变元约束变元 可代入不可代入 不可改名可改名 举例说明：采用上例。 4、量词 我们引入了谓词、函词、变元和常元的概念，还不能充分的描述现实中的命题。例如对于下面的命题： 如果P(x)对任意x恒真，则P(x+1)恒真。

数据库第四章练习题答案

第四章练习题 一、选择题 1．设计性能较优的关系模式称为规范化，规范化主要的理论依据是。 A．关系规范化理论 B．关系运算理论 C．关系代数理论 D．数理逻辑 答案：A 2．规范化理论是关系数据库进行逻辑设计的理论依据。根据这个理论，关系数据库中的关系必须满足：其每一属性都是。 A．互不相关的 B．不可分解的 C．长度可变的 D．互相关联的 答案：B 3．关系数据库规范化是为解决关系数据库中问题而引入的。 A．插入、删除和数据冗余 B．提高查询速度 C．减少数据操作的复杂性 D．保证数据的安全性和完整性 答案：A 4．当关系模式R(A，B)已属于3NF，下列说法中是正确的。 A．它一定消除了插入和删除异常B．仍可能存在一定的插入和删除异常 C．一定属于BCNF D．A和C都是 答案：B 5. 关系模式中2NF是指_______。 A.满足1NF且不存在非主属性对关键字的传递依赖现象 B.满足1NF且不存在非主属性对关键字部分依赖现象 C.满足1NF且不存在非主属性 D.满足1NF且不存在组合属性 答案：B 6. 关系模式中3NF是指___________。 A.满足2NF且不存在非主属性对关键字的传递依赖现象 B.满足2NF且不存在非主属性对关键字部分依赖现象 C.满足2NF且不存在非主属性 D.满足2NF且不存在组合属性 答案：A 7．关系模型中的关系模式至少是。 A．1NF B．2NF C．3NF D．BCNF 答案：A 8．在关系模式中，如果属性A和B存在1对1的联系，则说。 A．A→B B．B→A C．A←→B D．以上都不是 答案：C 9．若关系模式R∈1NF，且R中若存在X→Y，则X必含关键字，称该模式_______。 A.满足3NF B.满足BCNF C.满足2NF D.满足1NF 答案：B 10．消除了部分函数依赖的1NF的关系模式，必定是。 A．1NF B．2NF C．3NF D．BCNF 答案：B 11．候选关键字中的属性可以有。 A．0个 B．1个 C．1个或多个 D．多个 答案：C 12．设某关系模式S（SNO，CNO，G，TN，D），其中SNO表示学号，CNO表示课程号，

高级数理逻辑第8讲

模态逻辑 汉语中“模态”是英语词Modal的音译。英语词modality(模态性)源出于拉丁文modalitas，含形态、样式和形式的意思。 现代模态逻辑是现代逻辑的重要分支，它在科学和技术领域的应用越来越广泛，它的许多课题不仅受到逻辑学家的注意，而且也受到计算机科学家和计算机工程技术人员以及其他工程技术人员的关注。因此，深入研究和发展这门科学，已成为逻辑工作者的一项重要任务。 逻辑学中在两种意义上，即在狭义和广义上使用“模态”这个术语。涉及必然性，或然性（偶然性），遗传性和相容性等模态属于狭义模态。从某种观点来看，它们表达的是命题的真假强度。因此，也称为真值模态。例如：“物体间存在着引力是必然的”；“到本世纪末我国国民生产总值翻两翻是可能的”等都属于这类模态命题。我们这章的模态系统主要研究这类狭义模态性。 广义模态性是指命题本身所具有的非真值函项的（或非外延的）种种性质。广义模态词较多，除了必然、可能之外，尚有必须（应该）、允许、禁止；知道、相信、可接受、可疑、可证；曾经、总是、将是、优先、中立等。这些模态词分别是道义逻辑，认识逻辑，时态逻辑，和价值逻辑研究的对象。还有希望、需要等尚未深入研究的模态词。其例子为：“宇宙间存在着黑洞是可信的”；“在商品生产的社会中价值规律起着重要作用是众所周知的”；“子女赡养扶助父母是应该的”；“世界上还存在着野人是可疑的”等。 在这章，我们将讨论一些模态命题逻辑的系统，但首先将给出现代模态系统所要表达的某些模态概念的一般叙述。 6.1 模态逻辑介绍 本章主要来介绍模态逻辑系统基本概念，然后，具体介绍命题模态逻辑和一阶谓词模态逻辑。Modal logic 6.1.1模态逻辑引入 逻辑系统的发展从命题逻辑发展到了一阶谓词逻辑，主要是因为命题逻辑系统的描述能力有限。模态逻辑的出现同样是为了扩充一阶谓词逻辑和命题逻辑的描述能力。 1、命题逻辑的缺陷：命题逻辑的原子命题不能细化，层次太高，而不能完全描述世界； 例：所有实数的平方是非负的； -3是实数； -3的平方是非负的； 一阶谓词逻辑，利用谓词，函词和量词来解决这样的问题；

4,第四章 逻辑学 复合命题及其推理

第四章复合命题及其推理 复合命题的含义与性质 1．定义 所谓复合命题就是在一个命题中还包含有其它命题的一种命题形式，其表现形式相当于语句中的复句。 2.种类 据复合命题中联结项的不同，复合命题可以分为联言命题、选言命题、假言命题和负命 如：今天既刮风又下雨。 今天或刮风或下雨。 如果学习好，就能得奖学金 只有学习好，才能得奖学金 3.复合命题的学习方法 ①必须弄清楚各种复合命题的逻辑联结项（或逻辑联结词）的涵义。 ②充分利用真值表方法。也即充分利用真值表对各种复合命题的逻辑联结项的定义作用和对复合命题真值情况的判定作用。 ③必须弄清楚复合命题的逻辑涵义与自然语言的意义上的联系。 第一节联言命题及其推理 一、联言命题 1.定义 联言命题就是断定若干事物情况同时存在的命题。例如： （1）张三和李四都要受到法律制裁。 （2）王某不但犯有盗窃罪，而且犯有抢劫罪。 2. 逻辑性质（特征） 断定若干事物情况存在的可能性，所有情况必须同时为真（同时存在）。 3.结构： 联言支（两个或两个以上）：一般用符号P、q表示； 联结项：用逻辑符号“∧”（读作“合取”）表示。 联结项的语言形式有：“并且（和）”、“既……又”、“……而且……”、“……而……””“不但……而且”、“虽然……但是”等。 4、逻辑形式 一个二支联言命题的逻辑形式为：语言表达式：p并且q 符号表达式：p∧q（“∧”读做合取；“p∧q”读做p合取q）

5、联言命题的真假值 1．根据联言命题的逻辑性质或特征:只有当全部联言支所断定的情况都存在时，联言命题才是真的。也即：当且仅当联言支全真时，联言命题为真。 2．联言命题的真值表 真假情况共有2的n次方。联言命题P∧q的真假值和支命题P、q的真假值的关系，可以用如下真值表来表示： 注意： （1）、合取式只要求其支命题同真，不考虑其间的意义联系。 （2）、数理逻辑认为，p∧q与q∧p是一样的，其值不变。在普通逻辑中，由于有递进、转折等，位置不能随意换。 如：曾国藩屡战屡败→屡败屡战 情有可原，罪无可恕→罪无可恕，情有可原 【思维训练题】某地有两种人，分别是说谎族和诚实族。诚实族总说真话，说谎族总说假话。一天，有旅行者路过此地，看见此地的甲乙二人。他向甲提出一个问题：“你俩中有诚实族吗？”甲回答说：“没有。”旅行者想了想，就正确地推出了结论。 问：以下哪项是旅行者作出的命题？ A．甲是诚实族，乙是说谎族。 B．甲乙都是诚实族。 C．甲乙都是说谎族。 D．甲是说谎族，乙是诚实族。 E．甲乙所属均不明。 二、联言推理 1.定义 联言推理就是前提或结论为联言命题的推理。它是根据联言命题的逻辑性质进行推演的推理。例如： （1）小胡既是我们班的班长，又是我们班的团支部书记， ——————————————————— 所以，小张是我们班的团支部书记。