chap6一阶逻辑.ppt

* 离散数学 * 习题：符号化下列命题，并论证其结论： 每个大学生，不是文科学生就是理科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科生。 命题符号化：设G(x):x是大学生。L(x):x是文科学生。P(x):x是理工科学生。S(x):x是优秀生。c:小张。 * 离散数学 * 附加前提 前提 (2)，US 假言推理，(1)，(3) 前提 析取三段论,据(4),(5) 证明：推理如下： * 离散数学 * 3 量词作用域的收缩与扩张等值式 定理: 设G(x)是恰含一个自由变元x的谓词公式, H是不含变量x的谓词公式. 于是有: 证明 * 离散数学 * 证明：设D是论域，I是G(x)和H的一个解释. * 离散数学 * 4 量词分配等值式 定理: 设G(x),H(x)是恰含一个自由变元x的谓词公式,则有: 对不对？ 证明 （×） （×） 原因 * 离散数学 * 原因 取解释I如下： D：=自然数集； G(x)：=“x是奇数”； H(x)：=“x是偶数”. 同理可证B. * 离散数学 * 证明 （改名规则） （定理6.3.2） (析取词交换律) （定理6.3.2） (析取词交换律) * 离散数学 * 前束范式 定义： 设G为一个谓词公式，如果G具有如下形式： Q1x1…QnxnM 则称G为前束范式， 例： F(x,y)，?x?y?zP(x,y,z) 是前束范式 ?x?y(P(x,y)→Q(x,y)) 是前束范式 Q1x1…Qnxn称为首标,M称为母式。 * 离散数学 * 定理6.3.4： 对任意谓词公式G，都存在一个与其等值的前束范式。 证明： 对于公式G，可通过如下步骤得到等值于G的前束范式。 （1）使用基本等值式： (3)必要的话，将约束变量改名。 （4）使用定理6.3.1～定理6.3.3将所有量词都提到 公式的最左边。 注意: 一个公式的前束范式是不唯一的. 例子 * 离散数学 * 例子: 对公式 推导如下: y * 离散数学 * 习 题：将下式化成前束范式 解（1）： * 离散数学 * 解（2）： 前束范式对首标中量词的次序没有要求， 对母式中公式的形式也没作何种规定。 下面对前束范式作进一步规范，即保留 前束范式中的全称量词而消去存在量 词。 * 离散数学 * 一种特殊的前束范式: Skolem范式 定义：设G是一个谓词公式，Q1x1,…,QnxnM是与G等值的前束范式。其中M为合取范式。 （1）若Qr是存在量词（1≤r≤n），并且它左边没有全称量词，则取异于出现在M中所有常量符号的常量符号c，并用c代替M中所有的xr，然后在首标中消除Qrxr。 （2）若Qr1,…,Qrm是所有出现在Qrxr左边的全称量词，m≥1, 则取异于出现在M中所有函数符号的m元函数符号 f(xr1,…,xrm)，用f(xr1,…,xrm)代替出现在M中的所有xr， 然后在首标中删除Qrxr。 （3）重复以上过程，直到该前束范式的首标中无存在量词。 由此得到的前束范式称为Skolem范式，其中用来代替xr的那 些常数符号和函数符号称为公式G的Skolem函数。 例子 * 离散数学 * 例子： 1）用a代替x；2）用f(y,z)代替u；3）用g(y,z,v)代替w。 于是，得Skolem范式： 注意：公式与其Skolem范式两者不一定等值。 例子： 令解释I为： D={1,2};P(1,1):=0;P(1,2):=1;P(2,1):=0;P(2,2):=1f(1):=1;f(2):=2 * 离散数学 * 定理6.3.5： 设S是谓词公式G的Skolem范式。于是，G是恒假的当且仅当S是恒假的。 证明：由定理6.3.4，不妨设G是前束范式：G=Q1x1…QnxnM(x1,…,xn)，并且首标中至少有一个存在量词。 设Qr是首标中下标最小的存在量词，1≦r ≦n，令 G1=?x1…?xr-1Qr+1xr+1…QnxnM(x1,…xr-1, f(x1,…,xr-1),xr+1,…,xn) 其中f(x1,…,xr-1)是代替xr的Skolem函数。 * 离散数学 * 下面证明，G恒假当且仅当G1恒假。 设G恒假。若G1可满足，则存在一个解释I满足G1，于是，对任意值组(x01,…,x0r-1)∈Dr-1，都有f(x01,…,x0r-1)∈D，使得 Qr+1xr+1…QnxnM(x01,…,x0r-1,f(x01,…,x0r-1),xr+1…xn) 在I下为真。但此时满足G1的解释I也是满足G的解