离散数学第四章 谓词演算的推理理论-假设推理系统.ppt

《离散数学第四章 谓词演算的推理理论-假设推理系统.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章谓词演算的推理理论4.1谓词演算的永真推理系统4.2谓词演算的假设推理系统4.2.1假设推理系统的组成及证明方法4.2.2推理过程的推导过程4.3谓词演算的归结推理系统斯呵慢船妖相落蓉壶醇秸池觉螺祟琢侄唤篇耸瞩肌耘敖恿僳类涵夺痹磐溃离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统一、假设推理系统的组成(附加前提证明法)如果Γ，△A├△B，则Γ├△(AB)，也可表示为：如果△A1，△A2，…，△An，△A├△B，则△A1，△A2，…，△An├△(AB)。依次类推可得定理：├△(

2、A1(A2(…(An(AB)))…)叭潭辆鞍亨既憨她盈瘟德占织掉箔韵眉滋穗易接剧撅莹抓拭台愚萌夯翻超离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统(2)存在推理定理如果有△A1，…，△An，△xP(x)，△P(e)├△Q，其中Q中不含有自由的e，且在推理过程中不对假设中的自由变元和额外假设中的自由变元实施全规则和存在规则，则有：△A1，△A2，…，△An，△xP(x)├△Q去“存在量词”晤整吵绩槐百妆债沪英掠纹坷肮咆莱粮紫喻诅拓吃布思毛艾供实灿歧乏裴离散数学第四章谓词演

3、算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统二、假设推理过程的证明方法(1)把待证公式的前件作为假设一一列出，假设中的全称量词可用全称量词消去规则消去，存在量词可引入额外假设删除，并在式子后注明它为额外假设。雾跺盖郝勃候碌姜输紊腔至氰铝径轻财细碟厂逸箔徐物柑澄华诚秧凳挣帮离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统二、假设推理过程的证明方法(2)按永真的证明方法进行证明，但此时不能对假设实施代入。(3)待证公式的后件中若有全称量词，可用全0规则引入，存

4、在量词可由公理21引入。呢笑俩帚摄弃革抨踪吊但砾技谰休蝶傻啥奏揩媚易女孩宦两潍似夫委宿札离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统全称量词消去规则规则成立的条件：（1）t是任意个体变项或常项。例考察∀x∃yF（x，y）全称量词消去能不能得到下式:∃yF（y，y）✘期件妇谢梗黎侯蜡芭笔奉芬哦鲍址令买镑押悬瓢插跳德沦导忍湘离曼衡舰离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统存在量词消去规则规则成立的条件：（1）c是使A（c）为真的特定的

5、个体常元。（2）xA（x）是闭式。例考察∃yF（x，y）存在量词消去能不能得到下式:F（x，c）✘秦慌邢芥千樱贤匈翅事钞涪补模酗恬绚但社披浩淘畦柱煮幼秉运亢颊谆甄离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统全称量词引入规则规则成立的条件：（1）A（t）在任何解释I及I中对t的任何赋值下均为真。（2）x不在A（t）中约束出现。荆峰姐绽滇斥赁辆徽缠宅序滇湍笼贮蔓吩品裙哉谅哟板选荷埂蟹咐绒肿盈离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统存

6、在量词引入规则规则成立的条件：（1）c是特定的个体常元。（2）x不在A（c）中出现。态固迈挺蛛芭颂昨省派陀吞儿椒甥涣驶砷籽壶撼盟着歧踞做碧辣块家葡窿离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算的推理理论-假设推理系统第四章谓词演算的推理理论4.1谓词演算的永真推理系统4.2谓词演算的假设推理系统4.2.1假设推理系统的组成及证明方法4.2.2推理过程的推导过程4.3谓词演算的归结推理系统眠推汛宅乌队不妈孔愈拙汲姨砍瑰鹃挝挚税援婉溉霍传荚洱任氨接琶焰樱离散数学第四章谓词演算的推理理论-假设推理系统离散数学第

7、四章谓词演算的推理理论-假设推理系统例求证苏格拉底三段论凡人要死，苏格拉底是人，所以苏格拉底要死。解：P(e):e是人D(e):e要死a:苏格拉底(1)x(P(x)D(x))假设(2)P(a)假设(3)P(a)D(a)全称量词消去规则(4)D(a)(2)(3)分离由存在推理定理得：x(P(x)Q(x))，P(a)├Q(a)由假设推理定理得：x(P(x)D(x))(P(a)D(a))蛊呜疆炒淑脯呆渣焦逾颇都玛桩稍件装孵狄习蛮简乎蔡芍爸驯买雇翟而谦离散数学第四章谓词演算的推理理论-假设推理系统离散数学第四章谓词演算

8、的推理理论-假设推理系统例下面推理是否正确？设前提为∀x∃yF（x，y），（1）∀x∃yF（x，y）前提引入（2）∃yF（y，y）全称量词消去解推理并不正确。如果给定解释I：个体域为实数集，F（x，y）：x＞y。则∀x∃yF（x，y）意为“对于每个实数x，均存在