离散证明题集锦

使用时可以删除2例：给出┐(P∧Q)↔(┐P∨┐Q)的真值表PPQ┐(P∧Q)↔(┐P∨┐Q)00101111011011101010101111011000T∧T和T∨T。换，所得命题公式仍为一个重言式。(即代入规则)指派无关，故对同一分量以。3一个重言式。(前面已证)A一B.(替换规则)。A同，所以A一B。证明下列命题公式(可以利用基本等价式)42.原式一((P∧Q)∨P)∧((P∧Q)∨┐Q)一(P∨P)∧(P∨Q)∧(P3.原式一┐(┐P∨Q)∨(Q∨R)一(P∧┐Q)∨(Q∨R)一(P∨Q∨R)∧(Q∨┐Q∨R)一P∨Q∨R(零率)4.原式一(P∧┐Q)∨Q一(P∨Q)∧(┐Q∨Q)一P∨Q(运算次解：原式一(┐P∨Q)∨(P∧┐Q)一(┐P∨Q∨P)∧(┐P∨Q∨┐Q)一T式5CBD定理：如果A一B，则A*一B*。有：┐A*一┐B*，即A*一B*例判断下面各推理是否正确.6的推理问题,应先将命题符号化,然后写出前提、结论,最后进行判断.理的形式结构为判断(*)是否为重言式.值表法全为1,因而(*)是重言式.所以推理正确.等价演算法③主析取范式法一m0∨m1∨m2∨m3理的形式结构为7可见(**)不是重言式,所以推理不正确.还可用其他方法判断之.证明符号化题目:P:因病缺了许多课,Q:中学考试失败,R:有知识, (即后面讲的“构造证明”的格式)：P据P8(3)S(1);I2(4)PQPQ(2),(4);I8(6)SRP(7)R(3),(6);I8(8)QRP(9)R(5),(8);I9(10)R∧R(7),(9)解设A:张三说真话;B:李四说真话;C:王五说真话依题意有A一B,B一C,C一A∧B。ABBC(C一A∧B)一A∧B∧C9证明：{1}{2}{3}{4}PPPP (这部分的T，I8等是另外一本书的内容，所以不用管，只要会推则母鸡就会是飞鸟;如果母鸡是飞鸟,羊不吃草。RS(1)SP(2)RSP(3)R(1),(2),I9P∨QRPE“凌晨一点”理解为阳光不好。前提为:公式依据PQPR∧SP证明(1)SCPRSP(4)R(1),(3),I(5)PRP(6)RP(5),EP(4),(6),I(8)P∨QP(9)PQ(8),E P{1}(1)┐R∨PP{2}(2)RP(附加前提){3}{4}(6)QPST)I8{1}(1)PP(附加前提){1,2}(3)QT,(1)(2)I8{3}(4)┐(Q∨R)P(5)┐Q∧┐RT,(4)E5{1,2,3}(7)Q∧┐QT,(3)(6)例“如果春暖花开,燕子就会飞回北方。如果燕子飞回北方,则冰雪雪融化。则上述问题转化成证明:据P(2)RP(附加前提)(5)P(3),(4);I9课堂练习：派“不是我”，B说“是D”，是谁不喜欢熊例试用量词、谓词表示下列命题：①所有大学生都热爱祖国；②每个自然数都是实数；③一些大学生有远大理想；所有大学生都热爱祖国(Vx)(S(x)→L(x))每个自然数都是实数(Vx)(N(x)→R(x))全称量词(Vx)后跟条件式。一些大学生有远大理想(3x)(S(x)∧I(x))有的自然数是素数(3x)(N(x)∧P(x))正确？(注意到此公式中，约束变元只有x), 现。)我们以y为例，试判断下面哪个正确？现解用约束变元的改名规则得:或用自由变元得代入规则得: 例试证明下面苏格拉底论证：化为：推证如下：{1}(1)(Vx)(M(x)→D(x))P{1}(2)M(s)→D(s)UI,(1){3}(3)M(s)P{1,3}(4)D(s)T,(2),(3),I例证明(3x)A(x)(Vx)B(x)(Vx)(A(x)B(x))(1)(Vx)(A(x)B(x))P(附加前提)(2)(3x)(A(x)B(x))T,(1),EAaBaT,(2),ESAaBaT,(3),I(5)A(a)T,(4),IBaT,(4),I(7)(3x)A(x)T,(5),EG(8)(3x)A(x)(Vx)B(x)P前提VxBxT,I10)B(a)T,US例令A={{1,2},{3},4},B={4,{5},{5,6}},则B{5}例设A={1,3,5},B={2,4,6,8},定义A到B的二元关系R:‹a,d则R课程b，但课程b不是a的必修课，或者课程b是a的必修课，但aba的必修课，但a没有选它。例设A={a,b,c,d},A上的关系R={‹a,a›,‹a,b›,‹b,d›},显然R*S≠S*R复合是——叔侄关系例设A={a,b,c,d,e,f},求Rn(n=1,2,3,4,…)。…Rn=(n＞5)。R={‹a,2›,‹b,2›,‹b,3›,‹d,4›},则23456210101MR=301001400100Sabc},S上的关系R1={‹a,a›,‹b,b›,‹c,c›,‹b,c›}R2={‹a,b›,‹b,a›}R3={‹b,b›,‹c,c›}事实上，关系R＝{‹2,2›,‹3,3›,‹5,5›,‹7,7›,‹3,5›,‹5,3›,‹3,7›,‹7,3›,‹5,7›,‹7,5›}例在集合S={a,b,c,d}上的关系R反