离散数学：第一章1-6 推理理论

1第一章命题逻辑

1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论21.6

命题逻辑的推理理论

推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明法3一、推理的形式结构前提是指已知的命题公式；结论是从前提出发应用推理规则推出的命题公式；推理是从前提推出结论的思维过程。若A1ÙA2Ù…ÙAk®B为重言式，称A1ÙA2Ù…Ù

Ak推出结论B的推理正确。B是A1ÙA2Ù…Ù

Ak的逻辑结论或有效结论。若推理正确，则记作：A1ÙA2Ù…ÙAkÞB.称A1ÙA2Ù…ÙAk®B为由前提A1ÙA2Ù…Ù

Ak推出结论B的推理的形式结构。4一、推理的形式结构注意：推理正确，不能保证结论一定正确！因为前提可能是错误的。当A1,A2,…,Ak中有为假时，A1ÙA2Ù…ÙAk®B恒为真！只有在推理正确，且前提也正确时，才能保证结论正确！5二、判断推理是否正确的方法真值表法等值演算法判断推理是否正确主析取范式法构造证明法证明推理正确

说明：当命题变项比较少时，用前3个方法比较方便,此时采用形式结构“A1ÙA2Ù…ÙAk®B”.而在构造证明时，采用“前提:A1,A2,…,Ak,结论:B”.

例判断下面推理是否正确。如果天气凉快，小王就不去游泳。天气凉快。所以小王没去游泳。如果我上街，我一定去新华书店。我没上街。所以我没去新华书店。提示：先将命题符号化；再写出前提、结论、推理的形式结构；最后进行判断。67推理定律——重言蕴涵式

重要的推理定律

A

Þ(AÚB)附加律

(AÙB)Þ

A

化简律

(A®B)ÙA

Þ

B

假言推理

(A®B)ÙØB

Þ

ØA

拒取式

(AÚB)ÙØB

Þ

A

析取三段论

(A®B)Ù(B®C)Þ(A®C)假言三段论

(A«B)Ù(B«C)Þ(A«C)等价三段论

(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)构造性二难8构造证明——直接证明法构造下列推理的证明。前提：p®r,q®s,pÚq.

结论：rÚs.前提：pÚq,p®Ør,s®t,Øs®r,Øt.

结论：q.提示——常用推理规则还有：前提引入规则：任何步骤都可以引入前提；结论引入规则：已证明的结论均可作为后续证明的前提；置换规则：命题公式中的任何子命题均可用与之等值的命题公式置换；合取引入规则：A,BÞAÙB9直接证明法(续)例构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天没备课.所以，明天不是星期一和星期三.解

设p：明天是星期一，q：明天是星期三，

r：我有课，s：我备课推理的形式结构为

前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

10直接证明法(续)前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

证明①r®s

前提引入②Øs

前提引入③Ør①②拒取式④(pÚq)®r

前提引入⑤Ø(pÚq)③④拒取式⑥ØpÙØq⑤置换11构造证明——附加前提证明法

欲证明前提：A1,A2,…,Ak

结论：C®B等价地证明前提：A1,A2,…,Ak,C

结论：B

理由：(A1ÙA2Ù…ÙAk)®(C®B)

Û

Ø(A1ÙA2Ù…ÙAk)Ú(ØCÚB)

Û

Ø(A1ÙA2Ù…ÙAkÙC)ÚB

Û(A1ÙA2Ù…ÙAkÙC)®B12附加前提证明法(例)证明：①s

附加前提引入②ØsÚp

前提引入③p①②析取三段论④p®(q®r)前提引入⑤q®r③④假言推理⑥q

前提引入⑦r⑤⑥假言推理前提：p®(q®r),ØsÚp,q.

结论：s®r.13附加前提证明法(练习)证明：①s

附加前提引入②r®Øs

前提引入③p®r

前提引入④p®Øs②③假言三段论⑤Øp①④拒取式

⑥pÚq

前提引入⑦q⑤⑥析取三段论前提：pÚq,p®r,

r®Øs

结论：s®q14构造证明——归谬法（反证法）

欲证明前提：A1,A2,…,Ak

结论：B将ØB加入前提，若推出矛盾，则得证推理正确.理由:

A1ÙA2Ù…ÙAk®B

Û

Ø(A1ÙA2Ù…ÙAk)ÚB

Û

Ø(A1ÙA2Ù…ÙAkÙØB)括号内部为矛盾式当且仅当(A1ÙA2Ù…ÙAk®B)为重言式。15归谬法(例)证明：①q

否定结论引入

②p

前提引入

③p®(Ø(rÙs)®Øq)

前提引入

④

Ø(rÙs)®Øq

②③假言推理

⑤rÙs①④拒取式

⑥Øs

前提引入

⑦s

⑤化简

⑧ØsÙs

⑥⑦合取由⑧得出了矛盾，根据归谬法说明推理正确。

前提：p®(Ø(rÙs)®Øq),

Øs,p结论：Øq.16归谬法(练习)证明：①q

否定结论引入

②r®s

前提引入

③Øs

前提引入

④

Ør

②③拒取式

⑤Ø(pÙq)Úr

前提引入

⑥Ø(pÙq)④⑤析取三段论

⑦ØpÚØq⑥置换

⑧Øp①⑦析取三段论

⑨p

前提引入

⑩ØpÙp⑧⑨合取由⑩得出了矛盾，根据归谬法说明推理正确。

前提：Ø(pÙq)Úr,r®s,Øs,p结论：Øq1717谁养鱼?此题源自1981年柏林的德国逻辑思考学院.....98%的测验者无法解题,以下是题目的中译版.前提有五间房屋排成一列所有房屋的外表颜色都不一样所有的屋主来自不同的国家所有的屋主都养不同的宠物;喝不同的饮料;抽不同牌的香烟1818谁养鱼?题示:英国人住在红色房屋瑞典人养狗丹麦人喝茶绿色的房子在白色房子的左边绿色房屋的屋主喝咖啡抽PallMall香烟的屋主养鸟黄色屋主抽Dunhill位於最中间的屋主喝牛奶挪威人住在第一间房屋抽Blend的人住在养猫人家的隔壁养马的屋主隔壁住抽Dunhill的人家抽BlueMaster的屋主他喝啤酒德国人他抽Prince挪威人住在蓝色房子隔壁只喝开水的人家住在抽Blend的隔壁1919

答： 挪威-黄色房屋-猫-水-Dunhill

丹麦-蓝色房屋-马-茶-Blend

英国-红色房屋-鸟-牛奶-Pall

德国-绿色房屋-鱼-咖啡-Prince

瑞典-白色房屋-狗-啤酒-Blue问题:请问谁养鱼?房屋——红色、绿色、白色、黄色、蓝色主人——英国、瑞典、丹麦、挪威、德国饮料——茶、咖啡、牛奶、啤酒、水宠物——狗、鸟、猫、马、鱼香烟——Pall、Dunhill、Blend、Blue、Prince谁养鱼?20艾丽斯与谋杀案艾丽斯、艾丽斯的丈夫、他们的儿子、他们的女儿，还有艾丽斯的哥哥，卷入一桩谋杀案。这五人中的一人杀了其余四人中的一人。这五人的有关情况是：（1）在谋杀发生时，有一男一女两人正在一家酒吧里。（2）在谋杀发生时，凶手和被害者两人正在一个海滩上。（3）在谋杀发生时，两个子女中的一个正一人独处。（4）在谋杀发生时，艾丽斯和她的丈夫