交大数理逻辑课件2-3命题逻辑的等值和推理演算

《交大数理逻辑课件2-3命题逻辑的等值和推理演算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章命题逻辑的等值和推理演算2.1等值定理2.2等值公式2.3命题公式与真值表的关系2.4联结词的完备集2.5对偶式2.6范式2.7推理形式2.8基本的推理公式2.9推理演算2.10归结推理法讨论等值演算讨论推理演算极大项定义n个命题变项的简单析取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单析取式称为极大项。如：两个命题变元P和Q，其极大项为：PQ，PQ，PQ，PQ说明n个命题变项产生2n个极大项，它们互不等值用Mi表示第i个极大项，每个小项的n个变元排序相同。（按下标或字典顺序），分别记为其中i是该极大项成假赋值的十

2、进制表示的补.（正变项：0，变元的否定：1）M11M10M01M00由P,Q,R三个命题变项形成的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称PQRPQRPQRPQRPQRPQRPQRPQR000001010011100101110111m0m1m2m3m4m5m6m7PQRPQRPQRPQRPQRPQRPQRPQR111110101100001010001000M0M1M2M3M4M5M6M7主合取范式主合取范式由极大项构成的合取范式如n=3,命

3、题变项为P,Q,R时，主合取范式:(PQR)(PQR)=M6M2定理任何命题公式都存在与之等值的主合取范式,并且是惟一的.求主合取范式的方法等值演算法和真值表法1.求A的合取范式A´；2.若A´的某简单析取式B中不含某命题变项或其否定，则将B展成如下形式：B=B0=B(PiPi)=(BPi)(BPi)3.将重复出现的命题变项、重言式及重复出现的极大项都“消去”。4.将极大项按由小到大的顺序排列，并用表示之，如M1M2M6用(1,2,6)表示。用等价演算法求主合取范式的步骤求公式(PQ)R的主合取范式解1:：(PQ)R=

4、(PQ)R=(PQ)R=(PQ)(QR)①PR=(PR)(QQ)=(PRQ)(PQR)=M111M101②QR=(QR)(PP)=(PQR)(PQR)=M111M011③②,③代入①并排序，得主合取范式：=M3M5M7=(3,5,7)解2:(PQ)R=(PQ)R=(PQ)R=(PR)(QR)(合取范式)=M1x1Mx11=M101M111M011M111=M3M5M7=(3,5,7)求公式(PQ)R的主合取范式=(PQ)R（析取范式）=m11xmx

5、x1=(m110m111)(m001m011m101m111)=(1,3,5,6,7)主析取范式与主合取范式的转换——(1,3,5,6,7)=[(0~7)-(1,3,5,6,7)]补=(0,2,4)补=(3,5,7)2.7推理形式推理引例:(1)正项级数收敛当且仅当部分和有上界.(2)若AÈCÍBÈD，则AÍB且CÍD.数理逻辑的主要任务是用逻辑的方法研究数学中的推理。推理——从前提出发，应用推理规则推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.推理的组成——前提——推理所根据的已知命题结论——从前提出发通过推理而得到的新命题证明——

6、描述推理正确或错误的过程.推理形式例：如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。解：令P：我有时间。Q：我去上街。R：我去书店买书。根据题意，前提为：P→Q，Q→R，¬R结论为：¬P推理的形式为：(P→Q)∧(Q→R)∧¬R→¬P反映了一类推理关系重言蕴涵定义若（A1ÙA2Ù…ÙAk）®B为重言式，则称由A1,A2,…,Ak推出结论B的推理正确（有效结论）否则推理不正确（错误）.“A1,A2,…,Ak推出B”的推理正确当且仅当A1ÙA2Ù…ÙAk®B为重言式.推理的形式结构——A1ÙA2Ù…ÙAk®B或前提：A1,A

7、2,…,Ak结论：B若推理正确，则记作：A1ÙA2Ù…ÙAkÞB例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。解题方法——①将命题符号化②写出前提、结论和推理的形式结构③进行判断解：①设P：天气凉快，Q：小王去游泳.②前提：P®ØQ，P结论：ØQ推理的形式结构为：((P®ØQ)ÙP)®ØQ判断上式是否为重言式例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。③判断((P®ØQ)ÙP)®ØQ是否为重言式方法1：真值表法PQP®ØQ(P®ØQ)ÙP((P®