习题17

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【习题17】共19组。⊨表示所有赋值上的语义蕴涵;证明步骤中MP指假言推理、MT指拒取式、DS指析取三段论。临时假设最后必须撤销。讨论日历等背景时,若只判断命题形式,须把原子当独立变项,不偷偷添加额外事实。

【17.1】两个附加律实例:(1)若4是偶数,则4是偶数或5是偶数,设p、q表示这两原子,p⇒p∨q。(2)已知今天下雨,所以今天下雨或刮风,设r下雨、s刮风,r⇒r∨s。结论不声称新增的另一分项一定真。

【17.2】两个化简律实例:(1)既去过广州又去过北京,所以去过广州;p∧q⇒p。(2)一个整数同时被3和5整除,所以被5整除;r∧s⇒s。自然语言中的“和”必须连接两个完整命题,而非仅连接关系的两个主语。

【17.3】三个MP实例:(1)4整除a则2整除a;4整除a;所以2整除a。(2)下雨则带伞;下雨;所以带伞。(3)文件通过校验则显示通过;文件通过校验;所以显示通过。每题分别命名前件p、后件q,形式均为{p→q,p}⊨q,对应((p→q)∧p)→q恒真。原书示例若把p→q写成p∧q,所得推理虽也有效,却是在化简合取,不能作为MP模式的正确符号化。

【17.4】拒取式:若停电则灯灭,灯未灭,所以未停电;{p→q,¬q}⊨¬p。析取三段论:去图书馆或操场,没去操场,所以去图书馆;{p∨q,¬q}⊨p。假言三段论:4整除a推出2整除a,2整除a推出a为偶数,所以4整除a推出a为偶数;{p→q,q→r}⊨p→r。

等价三段论:给定a,b,c三个数,a=b当且仅当b=a,b=a当且仅当a−b=0,因此a=b当且仅当a−b=0;令p、q、r为三命题,{p↔q,q↔r}⊨p↔r。构造性二难:若下雨则室内活动,若晴天则户外活动,已知下雨或晴天,所以室内或户外活动;{p→q,r→s,p∨r}⊨q∨s。活动规则作为前提,不冒充没有例外的现实常识。

【17.5】每条等值式拆两个方向。德摩根两式产生四条:¬(A∨B)⇒¬A∧¬B;¬A∧¬B⇒¬(A∨B);¬(A∧B)⇒¬A∨¬B;¬A∨¬B⇒¬(A∧B)。吸收两式也产生四条:A∨(A∧B)⇒A;A⇒A∨(A∧B);A∧(A∨B)⇒A;A⇒A∧(A∨B)。单向推理中的⇒不是对象语言↔。

【17.6】本题首先按纯命题形式判断,不额外把“今天星期一”和“明天星期二”的日历关系加入前提。各小题以p表示今天星期一,q表示该小题主要的明天日期命题;第(5)题q表示明天星期二、r表示明天星期三。六个形式及结论如下。

(1)前提p→q,p,结论q;F₁=((p→q)∧p)→q,MP,有效。(2)前提p→q,q,结论p;F₂=((p→q)∧q)→p,是肯定后件,不有效,pq=01反例。(3)前提p→q,¬q,结论¬p;F₃=((p→q)∧¬q)→¬p,MT,有效。

(4)前提p→q,¬p,结论¬q;F₄=((p→q)∧¬p)→¬q,否定前件错误,pq=01反例。(5)前提p→(q∨r),p,结论q;F₅=((p→(q∨r))∧p)→q,不有效,pqr=101前提全真、结论假。(6)前提p↔q,¬p,结论¬q;F₆=((p↔q)∧¬p)→¬q,由q→p及MT有效。

pqrF1F2F3000111001111010101011101100111101111110111111111
题17.6(1)—(3) 真值表;r为未出现的哑元
pqrF4F5F6000111001111010011011011100111101101110111111111
题17.6(4)—(6) 真值表

第二种判断法由等值演算得F₁、F₃、F₆均⇔1;F₂、F₄均⇔p∨¬q,01时为0;F₅⇔¬p∨q∨¬r,101时为0。表格与演算分别给出要求的两种方法。

若额外加入通常日历公理“今天星期一↔明天星期二”,则某些具体语句的语义推理会改变,例如(2)可由该新增公理成立;这不说明其一般“肯定后件”形式有效。形式有效不等于前提描述真实,(1)虽然拿星期三作后件,MP形式仍有效。

【17.7】每项给有效结论、无效结论及反例。(1)Γ={p→q,q→r},有效p→r,无效p,赋值000使前提真而p假。(2)Γ={(p∧q)→r,¬r,q},有效¬p:由MT得¬(p∧q),与q用DS得¬p;无效p,反例010。(3)Γ={p→(q→r),p,q},有效r,连续两次MP;无效¬r,反例111。

【17.8】p天气热、q游泳、r有时间。(1)Γ={q→p,q}有效结论p;无效结论r,取pqr=110。(2)Γ={p→q,¬q}有效¬p;无效q,取p=q=0。(3)Γ={q→(p∧r),¬p∨¬r}有效¬q,因为第二句等值于¬(p∧r),MT即得;无效¬p,取pqr=100,天气热但无时间、未游泳。原条件不允许把“没时间”误推成“天气不热”。

【17.9】p:a奇,q:a偶,r:2整除a。前提p→¬r、q→r,结论q→¬p。整体F=((p→¬r)∧(q→r))→(q→¬p)。

pqrTBF000111001111010011011111100111101011110001111001
题17.9 八行真值表,F均为1

真值表法:八行全1。等值演算法:F⇔¬((¬p∨¬r)∧(¬q∨r))∨¬q∨¬p⇔(p∧r)∨(q∧¬r)∨¬q∨¬p;由吸收及分配,(p∧r)∨¬p⇔¬p∨r,(q∧¬r)∨¬q⇔¬q∨¬r,合并得1。主DNF法:F含全部m₀到m₇。因此三法均证有效;也可将第一句假言易位为r→¬p,再与q→r串联。

【17.10】p:ab<0,q:a<0,r:b<0。前提p→((q∧¬r)∨(¬q∧r))、¬p,结论¬q∧¬r。整体F为这两前提合取到结论的蕴涵。

pqrTBF000111001100010100011100100011101001110001111001
题17.10 真值表,001、010、011是形式反例

按pqr,F的主DNF为m₀∨m₄∨m₅∨m₆∨m₇,缺m₁,m₂,m₃,不永真,所以形式无效。实际可取a=b=−1,乘积1不为负,两个数却都为负,对应011,前提均真、结论假。不能从否定一个充分条件推出后件的否定。

【17.11】原前提¬p∨q、¬q∨r、r→s、p,结论s。所缺行③q由①p与②¬p∨q用DS(将p写成¬¬p);⑤r由③q与④¬q∨r用DS;⑦s由⑤r与⑥r→s用MP。三处都必须引用先前行,不是凭直觉追加。

【17.12】①p∧q为附加前提;②p、③q由①化简;④p→(q→r)原前提;⑤q→r由②④MP;⑥r由③⑤MP;⑦q→(r→s)原前提;⑧r→s由③⑦MP;⑨s由⑥⑧MP;最后⑩撤销①,得(p∧q)→s。原证明只列至s,这里补上所需结论行。

【17.13】Γ含¬(p→q)∧q、p∨q、r→s。第一句已等值于p∧¬q∧q,为矛盾。因此r、s、r∨s都是Γ的有效结论,并且任意B都可推出。

在P中具体构造:由第一前提化简得q及¬(p→q);后者置换为p∧¬q,再化简得¬q。由q附加得q∨B,与¬q用DS得B。此为经典逻辑爆炸原理,不说明现实中任意B都真,而是说明这组前提不可能同时为真。第一前提中¬作用于整个(p→q),不可删去。

【17.14】在P中构造证明。(1)由p→(q→r)、p得q→r,再与q得r,附加得r∨s。(2)¬(q∧r)置换为¬q∨¬r,与r用DS得¬q;由p→q、¬q用MT得¬p。

(3)临时假设p,由p→q得q,合取p∧q,撤销假设得p→(p∧q)。(4)由t∧r得t,由s↔t得t→s,故s;由q↔s得s→q,故q;由q→p得p,合取p∧q。

(5)由p∧q得p、q,分别与p→r、q→s用MP得r、s,合取r∧s。(6)原前提¬p∨r、¬q∨s、p∧q,先得p、q,再DS得r、s,合取r∧s。临时引入t也仍有此结论,撤销t得t→(r∧s)。前两句中的p、q都带¬,不能错录为正文字。

【17.15】必须使用附加前提法。(1)临时①s;由s→p得p;由p→(q→r)得q→r;与原前提q得r;撤销①得s→r。(2)临时①p;附加p∨q;由(p∨q)→(r∧s)得r∧s,化简s,附加s∨t;由(s∨t)→u得u;撤销①得p→u。

【17.16】必须使用归谬法。(1)前提p→¬q、¬r∨q、r∧¬s,证¬p。临时假设p,MP得¬q;由r∧¬s得r,结合¬r∨q用DS得q,与¬q矛盾;撤销p得¬p。¬s未被用到不影响有效性。

(2)前提p∨q、p→r、q→s,证r∨s。临时假设¬(r∨s),德摩根化简得¬r、¬s,MT分别得¬p、¬q;p∨q与¬p得q,与¬q矛盾。撤销临时假设,由经典反证法得r∨s。

【17.17】p:A到过房间,q:A在11点前离开,r:看门人看见A,s:A是题设中的嫌疑人。前提(p∧¬q)→s、p、q→r、¬r。由q→r与¬r用MT得¬q;与p合取得p∧¬q,再MP得s。结论严格是题设规则下的“嫌疑人”,没有推出犯罪事实或有罪。

【17.18】(1)p今天星期六、q去颐和园、r去圆明园、s颐和园人多。前提p→(q∨r)、s→¬q、p、s。两次MP得q∨r及¬q,DS得r。(2)p小王理科、q数学成绩好、r文科。前提p→q、¬r→p、¬q。先MT得¬p,再与¬r→p用MT得¬¬r,双重否定得r。无需擅自添加“所有学生非文即理”的额外分类前提。

【17.19】每项将结论否定加入原前提CNF,再消解到□。

(1){¬p∨¬q∨r,p,q,¬r,¬s};第一句与p消得¬q∨r,再与q得r,再与¬r得□,故推出r∨s。

(2){¬p∨q,p,¬p∨¬q},其中后两句来自¬(p→(p∧q))。第一句与p得q;第三句与p得¬q;二者得□。

(3)原前提CNF为{¬q∨p,¬q∨s,¬s∨q,¬s∨t,¬t∨s,t,r},再加¬p∨¬q。由t及¬t∨s得s,再得q,再得p;p与¬p∨¬q得¬q,与q得□。

(4){¬p∨r,¬q∨s,p,q,t,¬r∨¬s},后两句来自¬(t→(r∧s))。先得r、s;r与¬r∨¬s得¬s,再与s得□。

(5){p∨q,¬p∨r,¬q∨s,¬r,¬s}。由¬r与¬p∨r得¬p;由¬s与¬q∨s得¬q;p∨q与¬p得q,再与¬q得□。每一步只消一对互补文字,禁止一次同时删去多对。