《离散数学》第二章 一阶逻辑 讲稿文档格式.docx
《《离散数学》第二章 一阶逻辑 讲稿文档格式.docx》由会员分享，可在线阅读，更多相关《《离散数学》第二章 一阶逻辑 讲稿文档格式.docx（23页珍藏版）》请在冰点文库上搜索。
考虑L（2,3）和L（3,2）
L（x1,x2,…,xn）是命题：
只有当L是常项，x1,x2,…,xn是个体常项
0元谓词:
不含个体变项的谓词,如L（a,b）
如L的意义明确，则0元谓词都是命题
一阶逻辑中命题符号化
例1用0元谓词将命题符号化
要求：
先将它们在命题逻辑中符号化，再在一阶
逻辑中符号化
（1）墨西哥位于南美洲
在命题逻辑中,设p:
墨西哥位于南美洲
符号化为p,这是真命题
在一阶逻辑中,设a：
墨西哥，F（x）：
x位于南美洲
符号化为F（a）
例1（续）
（2）
是无理数仅当是有理数
在命题逻辑中,设p：
是无理数，q：
是有理数.
符号化为pq,这是假命题
在一阶逻辑中,设F（x）:
x是无理数,G（x）:
x是有理
数符号化为
（3）如果2>
3，则3<
4
2>
3，q：
3<
4.
符号化为pq,这是真命题
在一阶逻辑中,设F（x,y）：
x>
y，G（x,y）：
x<
y,
符号化为F（2,3）G（3,4）
（4）如果张明比李民高，李民比赵亮高，则张明比赵亮高.
在命题逻辑中,设p：
张明比李民高，q：
李民比赵亮高,r:
张明比赵亮高.
符号化为：
pqr
在一阶逻辑中,设F（x,y）：
x比y高
a:
张明，b:
李民，c:
赵亮
F（a,b）F（b,c）F（a,c）
基本概念（续）
量词:
表示数量的词
例如
（1）所有的人都要死的；
（2）有的人活一百岁以上；
全称量词:
表示任意的,所有的,一切的等
x表示对个体域中所有的个体，xF（x）表示个体域中所有的个体都有性质F.
xF（x），其中F（x）：
x是要死的，个体域为人类集合
存在量词:
表示存在着,有的,有一个，至少有一个等
x表示存在个体域中的个体，xF（x）表示存在着个体域中的个体具有有性质F
xG（x），其中G（x）：
x活一百岁以上，个体域为人类集合
如果个体域D为全总个体域，则
xF（x），其中F（x）：
x是要死的，表示宇宙间的一切事物都要死的.
x活一百岁以上，表示宇宙间的一切事物中存在活一百岁以上的.
特性谓词：
M（x）:
x是人
（1）x（M（x）F（x））
（2）x（M（x）G（x））
考虑：
一阶逻辑中命题符号化（续）
例2在一阶逻辑中将下面命题符号化
（1）
人都爱美;
（2）有人用左手写字
分别取（a）D为人类集合,（b）D为全总个体域.
解：
（a）
（1）设G（x）：
x爱美,符号化为xG（x）
（2）设G（x）：
x用左手写字,符号化为xG（x）
（b）设F（x）：
x为人，G（x）：
同（a）中
（1）x（F（x）G（x））
（2）x（F（x）G（x））
这是两个基本公式,注意这两个基本公式的使用.
例3在一阶逻辑中将下面命题符号化
（1）正数都大于负数
（2）有的无理数大于有的有理数
解注意:
题目中没给个体域,一律用全总个体域
（1）令F（x）:
x为正数,G（y）:
y为负数,L（x,y）:
x>
y
x（F（x）y（G（y）L（x,y）））或
xy（F（x）G（y）L（x,y））两者等值
（2）令F（x）:
x是无理数,G（y）:
y是有理数,
L（x,y）：
y
x（F（x）y（G（y）L（x,y）））
或xy（F（x）G（y）L（x,y））两者等值
几点注意：
1元谓词与多元谓词的区分
无特别要求，用全总个体域
量词顺序一般不要随便颠倒
例：
对任意x，存在着y，使得x+y=5.个体域为实数集.
符号化为：
xyH（x,y）,其中H（x,y）:
x+y=5
考虑yxH（x,y）
否定式的使用
例：
在一界逻辑中命题符号化
①没有不呼吸的人
②不是所有的人都喜欢吃糖
③不是所有的火车都比所有的汽车快
①x（F（x）G（x））
其中F（x）：
x是人，G（x）：
x呼吸
或者：
x（F（x）G（x））
②x（F（x）G（x））
x喜欢吃糖
x（F（x）G（x））
③x（F（x）y（G（y）H（x,y）））
x（F（x）y（G（y）H（x,y）））
①一切人都不一样高
②每个自然数都有后继数
③有的自然数无先驱数
①xy（F（x）F（y）G（x,y）H（x,y））
x是人，G（x,y）:
x和y不是同一个人，H（x,y）：
x和y一样高
xy（F（x）F（y）G（x,y）H（x,y））
②x（F（x）y（G（y）H（x,y））
x是自然数，H（x,y）：
y是x的后继数
x（F（x）L（x）），L（x）：
x有后继数
③x（F（x）y（G（y）H（x,y））
x（F（x）L（x）），L（x）：
x有先驱数
2.2一阶逻辑公式及解释
字母表
合式公式（简称公式）
个体变项的自由出现和约束出现
解释
永真式（逻辑有效式）
矛盾式（永假式）
可满足式
字母表
定义字母表包含下述符号：
（1）个体常项：
a,b,c,…,ai,bi,ci,…,i1
（2）个体变项：
x,y,z,…,xi,yi,zi,…,i1
（3）函数符号：
f,g,h,…,fi,gi,hi,…,i1
（4）谓词符号：
F,G,H,…,Fi,Gi,Hi,…,i1
（5）量词符号：
（6）联结词符号：
,,,
（7）括号与逗号：
（,）,，
项
定义项的定义如下：
（1）个体常项和个体变项是项.
（2）若（x1,x2,…,xn）是任意的n元函数，t1,t2,…,tn
是任意的n个项，则（t1,t2,…,tn）是项.
（3）所有的项都是有限次使用
（1）,
（2）得到的.
a，b，x，y，f（x,y）=x+y，g（x,y）=x-y都是项
f（a,g（x,y））=a+（x-y）是项
其实,个体常项、变项是项，由它们构成的n元函数
和复合函数还是项
原子公式
定义设R（x1,x2,…,xn）是任意的n元谓词，t1,t2,…,tn
是任意的n个项，则称R（t1,t2,…,tn）是原子公式.
其实，原子公式是由项组成的n元谓词.
例如，F（x,y）,F（f（x1,x2）,g（x3,x4））等均为原子公式
合式公式
定义合式公式（简称公式）定义如下：
（1）原子公式是合式公式.
（2）若A是合式公式，则（A）也是合式公式
（3）若A,B是合式公式，则（AB）,（AB）,（AB）,
（AB）也是合式公式
（4）若A是合式公式，则xA,xA也是合式公式
（5）只有有限次地应用
（1）~（4）形成的符号串
才是合式公式（谓词公式）.
个体变项的自由出现与约束出现
定义在公式xA和xA中，称x为指导变元，A为相
应量词的辖域.在x和x的辖域中，x的所有出现都
称为约束出现，A中不是约束出现的其他变项均称
为是自由出现的.
例如,在公式x（F（x,y）G（x,z））中,
A=（F（x,y）G（x,z））为x的辖域，
x为指导变项,A中x的两次出现均为约束出现，
y与z均为自由出现.
闭式:
不含自由出现的个体变项的公式.
例1：
x（F（x）yH（x,y））
∃yH（x,y）中，y为指导变项，的辖域为H（x,y），其中y为约束出现的，x为自由出现的.
在整个合式公式中，x为指导变项，的辖域为（F（x）yH（x,y）），其中x与y都是约束出现的，x约束出现2次，y约束出现1次.
例2：
xy（R（x,y）L（y,z））xH（x,y）
xy（R（x,y）L（y,z））中，x,y都是指导变项，辖域为（R（x,y）L（y,z）），x与y都是约束出现的，z为自由出现的.
∃xH（x,y）中，x为指导变项，的辖域为H（x,y），其中x为约束出现的，y为自由出现的
在此公式中，x为约束出现的，y为约束出现的，又为自由出现的.z为自由出现的.
换名规则将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未出现过的个体变项符号，公式中的其余部分不变。
xF（x）G（x,y）
换名规则：
zF（z）G（x,y）
代替规则将某个自由出现的个体变项及对应的指导变项，改成公式中未出现过的个体变项符号，处处代替。
代替规则：
xF（x）G（z,y）
用处：
不存在既是约束出现，又是自由出现的个体变项
公式的解释与分类
给定公式A=x（F（x）G（x））
成真解释:
个体域N,F（x）:
2,G（x）:
1
代入得A=x（x>
2x>
1）真命题
成假解释:
1,G（x）:
2
1x>
2）假命题
问:
xF（x）xF（x）有成真解释吗？
xF（x）xF（x）有成假解释吗？
解释
定义解释I由下面4部分组成：
（a）
非空个体域DI
（b）
DI中一些特定元素
（c）
DI上特定函数集合
（d）
DI上特定谓词的集合
说明：
1将公式的个体常项用I的特定常项代替，函数和谓词用I的特定函数和谓词代替
2被解释的公式不一定全部包含解释中的4部分.
3闭式在任何解释下都是命题，
4不是闭式的公式在某些解释下也可能是命题.
例给定解释I：
DI＝{2,3}
DI中特定元素a=2
DI上特定函数f（x）:
f
（2）=3,f（3）=2
（d）DI上特定谓词F（x）:
F
（2）=0,F（3）=1，
G（x,y）为G（i,j）=1,其中i,j=2,3
1）x（F（x）G（x,a））
（F
（2）G（2,2））（F（3）G（3,2））
（01）（11）0假命题
2）x（F（f（x））G（x,f（x）））
（F（f
（2））G（2,f
（2）））（F（f（3））G（3,f（3）））
（F（3）G（2,3））（F
（2）G（3,2））
（11）（01）1真命题
例给定解释：
个体域为自然数集合DN
DN中特定元素a=0
DN上特定函数f（x,y）=x+y,g（x,y）=x.y
（d）DN上特定谓词F（x,y）为x＝y
1）xF（g（x,a）,x））
xF（x.0,x）x（x.0=x）假命题
2）xy（F（f（x,a）,y）F（f（y,a）,x））
xy（F（0+x,y）F（y+0,x））
xy（（0+x=y）（y+0=x））真命题
3）xyF（f（x,y）,g（x,y））
xyF（x+y,x.y）xy（x+y=x.y）假命题
4）F（f（x,y）,f（y,z））
F（x+y,y+z）x+y=y+z不是命题
例1给定解释I如下:
（a）个体域D=N
（b）
（c）
（d）谓词
说明下列公式在I下的涵义,并讨论真值
公式的分类
永真式（逻辑有效式）：
公式在任何解释下都是真的，即无成假赋值
矛盾式（永假式）：
公式在任何解释下都是假的，即无成真赋值
可满足式：
至少存在一个解释使公式成真
永真式为可满足式，但反之不真
某些代换实例可判公式类型
代换实例
定义设A0是含命题变项p1,p2,…,pn的命题公式，
A1,A2,…,An是n个谓词公式，用Ai处处代替A0中的pi
（1in），所得公式A称为A0的代换实例.
例如:
F（x）G（x）,xF（x）yG（y）等都是pq的换实例，
x（F（x）G（x））等不是pq的代换实例.
定理命题公式中的重言式的代换实例，在谓词公式中都是永真式，
命题公式中的矛盾式的代换实例，在谓词公式中都是矛盾式.
代换实例（续）
例2判断下面公式的类型
（1）xF（x）xF（x）
解：
设任意解释I
a）如果存在a使得F（a）为假，则xF（x）为假，所以xF（x）xF（x）为真
b）如果对任意x使得F（x）为真，则xF（x）为真，而且xF（x）也为真，所以xF（x）xF（x）为真
因此，公式为永真式.
（2）xF（x）（xyG（x,y）xF（x））
（3）xF（x）（xF（x）yG（y））
（4）（F（x,y）R（x,y））R（x,y）
（5）xyF（x,y）xyF（x,y）
解释I1,个体域为自然数集合N，F（x,y）:
x等于y
此时，前件为真，后件为假
解释I2,个体域为自然数集合N，F（x,y）:
x小于等于y
此时，前件为真，后件为真
因此，公式为非永真式的可满足式
2.3一阶逻辑等值式
等值式
基本等值式
量词否定等值式
量词辖域收缩与扩张等值式
量词分配等值式
前束范式
等值式与基本等值式
基本等值式:
命题逻辑中16组基本等值式的代换实例
如，xF（x）xF（x）xF（x）
xF（x）yG（y）xF（x）yG（y）
（xF（x）yG（y））xF（x）yG（y）
消去量词等值式设D={a1,a2,…,an}
（1）xA（x）A（a1）A（a2）…A（an）
（2）xA（x）A（a1）A（a2）…A（an）
（1）xA（x）xA（x）
（2）xA（x）xA（x）
基本等值式（续）
量词辖域收缩与扩张等值式
设A（x）是含x自由出现的公式，B中不含x的出现
关于全称量词的：
x（A（x）B）xA（x）B
x（BA（x））BxA（x）
基本的等值式（续）
量词分配等值式
x（A（x）B（x））xA（x）xB（x）
注意：
对无分配律，对无分配律
量词等值式
xyA（x,y）yxA（x,y）
xyyxA（x,y）
其中A（x,y）是x,y自由出现的谓词公式
例将下面命题用两种形式符号化
（1）没有不犯错误的人
（2）不是所有的人都爱看电影
解
（1）令F（x）：
x是人，G（x）：
x犯错误.
x（F（x）G（x））
请给出演算过程，并说明理由.
（2）令F（x）：
爱看电影.
给出演算过程，并说明理由.
例如，xy（F（x）（G（y）H（x,y）））
是前束范式,而
x（F（x）y（G（y）H（x,y）））
不是前束范式，
公式的前束范式
定理（前束范式存在定理）一阶逻辑中的任何公
式都存在与之等值的前束范式
注意:
公式的前束范式不惟一
求公式的前束范式的方法:
利用重要等值式、
置换规则、换名规则、代替规则进行等值演算.
换名规则与代替规则
换名规则:
将量词辖域中出现的某个约束出现的
个体变项及对应的指导变项，改成另一个辖域中未
曾出现过的个体变项符号，公式中其余部分不变，
则所得公式与原来的公式等值.
代替规则:
对某自由出现的个体变项用与原公式
中所有个体变项符号不同的符号去代替，则所得公
式与原来的公式等值.
公式的前束范式（续）
例求下列公式的前束范式
（1）x（M（x）F（x））
解x（M（x）F（x））
x（M（x）F（x））（量词否定等值式）
x（M（x）F（x））
两步结果都是前束范式，说明前束范式不惟一.
例（续）
（2）xF（x）xG（x）
解xF（x）xG（x）
xF（x）xG（x）（量词否定等值式）
x（F（x）G（x））（量词分配等值式）
另有一种形式
xF（x）xG（x）
xF（x）yG（y）（代替规则）
xy（F（x）G（y））（量词辖域扩张）
两种形式是等值的
（3）xF（x）xG（x）
解xF（x）xG（x）
x（F（x）G（x））（为什么？
）
或xy（F（x）G（y））（为什么？
（4）xF（x）y（G（x,y）H（y））
解xF（x）y（G（x,y）H（y））
zF（z）y（G（x,y）H（y））（换名规则）
zy（F（z）（G（x,y）H（y）））（为什么？
或
xF（x）y（G（z,y）H（y））（代替规则）
xy（F（x）（G（z,y）H（y）））
（5）x（F（x,y）y（G（x,y）H（x,z）））
解用换名规则,也可用代替规则,这里用代替规则
x（F（x,y）y（G（x,y）H（x,z）））
x（F（x,u）y（G（x,y）H（x,z）））
xy（F（x,u）G（x,y）H（x,z）））
x与y不能颠倒
2.4一阶逻辑推理理论
推理的形式结构
判断推理是否正确的方法
重要的推理定律
推理规则
构造证明
附加前提证明法
推理
推理的形式结构有两种：
第一种A1A2…AkB（*）
第二种前提：
A1，A2，…，Ak
结论：
B
其中A1,A2,…,Ak,B为一阶逻辑公式.
若（*）为永真式,则称推理正确,否则称推理不正确.
判断方法:
真值表法,等值演算法,主析取范式法及构造证明法.前3种方法采用第一种形式结构,构造证明法采用第二种形式结构.
重要的推理定律
第一组命题逻辑推理定律代换实例
如xF（x）yG（y）xF（x）为化简律代换实例.
第二组由基本等值式生成
如由xA（x）xA（x）生成
xA（x）xA（x）,xA（x）xA（x）,…
第三组
xA（x）xB（x）x（A（x）B（x））
x（A（x）B（x））xA（x）xB（x）
x（A（x）B（x））xA（x）xB（x））
x（A（x）B（x））xA（x）xB（x））
推理规则
（1）前提引入规则
（2）结论引入规则
（3）置换规则（4）假言推理规则
（5）附加规则（6）化简规则
（7）拒取式规则（8）假言三段论规则
（9）析取三段论规则（10）构造性二难推理规则
（11）合取引入规则
推理规则（续）
（12）全称量词消去规则（简记为UI规则或UI）
两式成立的条件是：
x是A（x）中的自由出现的个体变项
在第一式中，取代x的y应为任意的不在A（x）中
约束出现的个体变项.
在第二式中，c为任意个体常项.
用y或c去取代A（x）中的自由出现的x时，一定要
在x自由出现的一切地方进行取代.
（13）全称量词引入规则（简记为UG规则或UG）
该式成立的条件是：
y是A（y）中自由出现的个体变项；
无论y取何值，A（y）应该均为真；
取代自由出现的y的x，也不能在A（y）中约束出
现.
（14）存在量词引入规则（简记为EG规则或EG）
c是使A为真的特定个体常项.
取代c的x不能在A（c）中出现过.
（15）存在量词消去规则（简记为EI规则或EI）
c是使A为真的特定的个体常项.
c不在A（x）中出现.
若A（x）中除自由出现的x外，还有其他自由出现
的
升级会员 