习题16

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【习题16】共36组。主范式始终先固定变量及顺序。为清楚列下标,记D{I}=下标在I中的全部mᵢ的析取,C{J}=下标在J中的全部Mⱼ的合取;D{}=0,C{}=1。两集合在全部二进制行中互补;每题的下标均指该小题注明的变量集,不跨题混用。

【16.1】A=p→q,B=p∧¬q,验证¬(A∨B)⇔¬A∧¬B。A、B互补,左右均0。

pqABLRL↔R0010001011000110010011110001
题16.1 完整真值表,L=¬(A∨B),R=¬A∧¬B

【16.2】仍取上述A、B,验证A→B⇔¬A∨B。两侧按pq=00、01、10、11均为0、0、1、0。

pqABLRL↔R0010001011000110011111110001
题16.2 真值表,L=A→B,R=¬A∨B

【16.3】(1)¬((p∧q)→q)⇔¬1⇔0,矛盾式。(2)(p→(p∨q))∨(p→r)⇔1∨(p→r)⇔1,重言式。(3)(p∨q)→(p∧r)⇔(¬p∧¬q)∨(p∧r),是偶然式,按pqr成真赋值000、001、101、111,成假010、011、100、110。

【16.4】(1)(p∧q)∨(p∧¬q)⇔p∧(q∨¬q)⇔p。(2)(p→q)∧(p→r)⇔(¬p∨q)∧(¬p∨r)⇔¬p∨(q∧r)⇔p→(q∧r)。(3)¬(p↔q)⇔¬((p∧q)∨(¬p∧¬q))⇔(¬p∨¬q)∧(p∨q)⇔(p∨q)∧¬(p∧q)。(4)(p∧¬q)∨(¬p∧q)⇔(p∨q)∧(¬p∨¬q)⇔(p∨q)∧¬(p∧q)。中间展开中含p∧¬p或q∧¬q的项均为0。

【16.5】求主DNF及成真赋值。(1)(¬p→q)→(¬q∨p),按pq,D{0,2,3},成真00、10、11。(2)(¬p→q)∧(q∧r)⇔q∧r,按pqr,D{3,7},成真011、111。(3)(p∨(q∧r))→(p∨q∨r)恒真,按pqr,D{0,1,2,3,4,5,6,7},全部八行成真。

【16.6】求主CNF及成假赋值。(1)¬(q→¬p)∧¬p⇔p∧q∧¬p⇔0,按pq,C{0,1,2,3},全部四行成假。(2)(p∧q)∨(¬p∨r)⇔¬p∨q∨r,按pqr,C{4},仅100成假。原题第二个括号是¬p∨r,不能错成¬p∧r。(3)(p→(p∨q))∨r恒真,按pqr主CNF为空合取1,无成假赋值。

【16.7】按pqr,先求主DNF再取缺失下标。(1)(p∧q)∨r:D{1,3,5,6,7},故主CNF C{0,2,4}。(2)(p→q)∧(q→r):D{0,1,3,7},故C{2,4,5,6}。

【16.8】先求主CNF再取补集。(1)(p∧q)→q,按pq恒真:C{}=1,D{0,1,2,3}。(2)(p↔q)→r,按pqr:C{0,6},D{1,2,3,4,5,7}。这里内层是↔,不是→。(3)¬(r→p)∧p∧q⇔r∧¬p∧p∧q⇔0,按pqr:C{0,1,2,3,4,5,6,7},D{}=0。

【16.9】真值表中F为题(1)=(p∨q)∨(¬p∧r),G为题(2)=(p→q)→(p↔¬q)。

pqrF00000011010101111001101111011111
题16.9(1) 按pqr的八行真值表
pqG000011101110
题16.9(2) 按pq的四行真值表

(1)主DNF D{1,2,3,4,5,6,7};(2)按pq,D{1,2}。F实际等值于p∨q∨r,G等值于p、q异或,但下标必须按各自变量位数写。

【16.10】按pqr真值表,F₁=(p∧q)∨r,F₂=(p→q)∧(q→r)。

pqrF1F20000100111010000111110000101101101011111
题16.10 两公式的共同真值表

读出成假行:(1)主CNF C{0,2,4};(2)C{2,4,5,6}。主CNF用的是输出0的行,不是1的行。

【16.11】F₁=(p∨q)∧r,F₂=p→(p∨q∨r),G=¬(q→¬p)∧¬p。

pqrF1F20000100101010010111110001101111100111111
题16.11(1)(2) 按pqr的真值表
pqG000010100110
题16.11(3) 按pq的真值表

(1)D{3,5,7},C{0,1,2,4,6}。(2)D{0,1,2,3,4,5,6,7},C{}=1。(3)D{}=0,C{0,1,2,3},最后一小题只有pq两变量。

【16.12】按pqr,成真行000、011、110,下标0、3、6,所以主DNF D{0,3,6},主CNF C{1,2,4,5,7}。

【16.13】成假行010、011、110、111,下标2、3、6、7,故主CNF C{2,3,6,7},主DNF D{0,1,4,5},实际等值于¬q。

【16.14】无成假赋值就是重言式,主CNF不含极大项,规定为空合取1。不是把全部极大项都写入,后者反而恒假。

【16.15】用主DNF比较。(1)按pqr,(p→q)→r为D{1,3,4,5,7},q→(p→r)为D{0,1,2,3,4,5,7},不等值,000即反例。(2)按pq,¬(p∧q)为D{0,1,2},¬(p∨q)为D{0},不等值,01或10可区分。

【16.16】用主CNF比较。(1)p→(q→r)与¬(p∧q)∨r,按pqr均为C{6},等值。(2)p→(q→r)为C{6},(p→q)→r为C{0,2,6},不等值;000或010使二者不同。

【16.17】仅用{¬,∧,∨}。(1)¬(p→(q↔(q∧r)))⇔p∧q∧¬r:q为0时内层等价恒真,q为1时等价值为r。(2)(p∧q)∨¬r已符合要求。(3)p↔(q↔r)⇔(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(p∧¬q∧¬r)∨(p∧q∧r),即三元奇校验;不能将两个↔任意遗漏一个否定后重写。

【16.18】仅用{¬,∧}。(1)p∨¬q∨¬r⇔¬(¬p∧q∧r)。(2)(p↔r)∧q⇔¬(p∧¬r)∧¬(¬p∧r)∧q。(3)(p→(q∧r))∨p⇔1,可写¬(p∧¬p)。结果允许不再实质依赖q、r,它们成为哑元。

【16.19】仅用{¬,∨}。(1)(¬p∨¬q)∧r⇔¬(¬(¬p∨¬q)∨¬r)。(2)(p→(q∧¬p))∧q∧r⇔¬p∧q∧r⇔¬(p∨¬q∨¬r)。(3)p∧q∧¬r⇔¬(¬p∨¬q∨r)。最终各式内部也不得再保留∧。

【16.20】仅用{¬,→}。(1)(p∧q)∨r⇔(p→¬q)→r。(2)(p→¬q)∧r⇔¬((p→¬q)→¬r)。(3)(p∧q)↔r⇔¬((¬(p→¬q)→r)→¬(r→¬(p→¬q)))。可先令A=¬(p→¬q),利用A∧B⇔¬(A→¬B)展开(A→r)∧(r→A),最后将A全部代回;上式已无∧、∨、↔。

【16.21】(1)∧、∨交换,所以p↑q⇔q↑p、p↓q⇔q↓p。(2)都不结合,赋值pqr=001时,(p↑q)↑r=0,而p↑(q↑r)=1;(p↓q)↓r=0,而p↓(q↓r)=1。同一个反例可用于两种运算,但不能由交换性误推结合性。

【16.22】按表16.3.2的四行输出编号:(1)与非1110,即F₁₄;(2)或非1000,即F₈;(3)异或0110,即F₆;(4)¬(p→q)为0010,即F₂。编号是输出向量按00、01、10、11由高位到低位解释,不是某个成真行的下标。

【16.23】(1)任意赋值下A与自身相同,故A⇔A。(2)若每行A、B相同,反向仍相同,得对称。(3)若每行A=B且B=C,则每行A=C,得传递。它是公式集合上的等价关系,不代表所有公式都互相等值。

【16.24】对每个赋值,¬A和¬B相同当且仅当A和B相同,因为0、1取反是双射。因此¬A⇔¬B当且仅当A⇔B。也可对已知等值两侧再取一次否定并用双重否定。

【16.25】联结词∨、∧一般不可消去公共分项。(1)取A=p、B=¬p、C=1,两侧A∨C、B∨C都恒真,但A、B不等值。(2)取C=0,两侧A∧C、B∧C都恒假,仍不能推出A⇔B。

【16.26】若只要求一个对任意A、B都保证可消去的简单条件:析取时C恒假,合取时C恒真,即公共项为该运算的单位元。

给定具体A、B、C时可写更一般的充要补充条件:已知A∨C⇔B∨C,它已保证C假时A=B,还需C真时A=B,等价于A∧C⇔B∧C;已知A∧C⇔B∧C,则还需A∨C⇔B∨C。两者合起来可由A=(A∧C)∨(A∧¬C)恢复A⇔B。仅凭某些赋值下C=0或1不能推出全局等值。

【16.27】p,q,r分别表示开关A、B、C向上。灯亮行001、100、011、110,下标1、4、3、6,故(a)F=D{1,3,4,6}。(b)化简后F是p与r异或,q为哑元,仅用{¬,∧}可写F=¬(p∧r)∧¬(¬p∧¬r)。(c)在{¬,→,↔}上可直接写F=¬(p↔r),不要求集合中的每个联结词都必须出现。反复开关B不影响灯,正是该真值要求的结果。

【16.28】优先级A>B>C,=A,=¬A∧B,=¬A∧¬B∧C。000时都0;否则最高优先级的有效输入唯一获准,不能将写成C或仅¬B∧C。它表示当前时刻的组合优先选择,不自动具有保存未处理请求的队列存储功能。

【16.29】假定三个岗位班长、生活委员、学习委员由三人各任一个,且一岗一人。记、、分别表示王小红任三个岗位,其余两人类似。三人预言恰好一半正确的约束分别为异或、异或、异或。

若王任班长,第一条要求李不任生活,第三条因王不任学习要求李任班长,与一岗一人矛盾。若王任生活,乙的半对要求丁不任班长,丙的半对要求李任班长,此时甲两句话都假(王非班长、李非生活),矛盾。故王任学习,丙要求李不任班长;班长只能丁,剩余生活为李。答案:王小红学习委员、李强生活委员、丁金生班长。代回甲、乙、丙分别“假真”“真假”“假真”,各恰对一句。

【16.30】依次用p,q,r,s,t表示赵、钱、孙、李、周去,约束为(p→q)∧(s∨t)∧((q∧¬r)∨(¬q∧r))∧(r↔s)∧(t→(p∧q))。

由r=s且q=¬r分情况:r=s=1时q=0,p→q迫使p=0,t→q迫使t=0,得00110,仅孙、李去;r=s=0时q=1,s∨t迫使t=1,再由t→p得p=1,得11001,即赵、钱、周去。仅这两种方案,不把“至少一人”擅自写成排斥或;本题其他约束恰已排除李、周同去。

【16.31】一次只删一对互补文字,再合并重复。(1)C₁=¬p∨¬q∨r、C₂=¬q∨¬r∨s∨¬t,以r、¬r消解得¬p∨¬q∨s∨¬t。(2)C₁=p∨¬q∨r∨¬s、C₂=s,得p∨¬q∨r。(3)C₁=¬p∨q∨r、C₂=p∨¬r∨¬s,有两种:消p得q∨r∨¬r∨¬s;消r得¬p∨q∨p∨¬s。两者都永真,不是把p和r两对同时删去得到q∨¬s。

【16.32】(1)原子句依次¬p∨q、¬p∨r、¬q∨¬r、p∨¬r、r。由r与¬q∨¬r得¬q;由r与p∨¬r得p;由p与¬p∨q得q;q与¬q得□,不可满足。(2)¬(((p∨q)∧¬p)→q)的CNF为{p∨q,¬p,¬q},前两句消得q,再与¬q消得□,所以原式为矛盾式。

【16.33】(1){p,¬p∨¬q,q},先消得¬q,再与q得□,不可满足。(2){p∨q,p∨¬q,¬p∨r},前两句得p,再得r。闭包无□,可满足,模型p=1,r=1,q任意;例如101。模型也直接验证原式,不能把“未立即导出空子句”当作不做闭包就断言可满足的理由。

【16.34】若两原子句至少有两对可消解互补文字,在任选一对消去后,另一对仍同时留在结果内,所以每个单步消解结果都永真,彼此等值。结论针对“任选一对”的结果,不允许同时删去多对。

【16.35】纯文字l在S中出现而lᶜ不出现,删去含l的全部子句得S′。若S有模型,限制后满足S′。若S′有模型,可把l对应变量改成使l真的值;S′不含该变量的任一极性,故已有子句不受影响,被删子句则都因l真而满足,扩张得S模型。因此S≈S′。这是保可满足性而非原变量上的逐点等值。

【16.36】把属于U的每个变量的所有文字都换成其补,p换¬p、¬p换p,原题不是“统一换常数1”。给任意赋值α,定义在U内逐位取反、其余不变,则(S)在下与S在α下取值相同。该变换是自身的逆,模型一一对应,故(S)≈S;也保持模型数量,但一般不逐点等值。