离散数学第一章习题

第一章习题课第一章学习指南1）掌握和理解命题（简单命题和复合命题）、命题的真值（T和F）、命题联结词（～、∨、∧、→、）、命题符号化；2）掌握命题公式的递归定义、指派、真值表、公式的分类、永真（假）式的概念；3）掌握命题公式等价的概念，基本等价式，掌握等价式的证明法（真值表法和公式推导法即等价取代法）；掌握蕴涵式的概念、蕴涵式的证明法（真值表法、前件真推出后件真法、后件假推出前件假法和公式推导法）；4）了解对偶式的基本概念和对偶定理；5）理解范式的概念、主析（合）取范式和主合取范式，能够熟练求公式的主析（合）取范式（真值表法、公式推导法）；6）了解推理形式的基本结构，熟悉基本的推理定律和基本推理规则（P规则、T规则和CP规则），掌握不同证明方法（直接法、反证法）。重点和难点1）命题符号化。命题符号化的一般处理过程是先分析自然语言描述的语义，然后用正确的命题联结词加以表示。应特别注意用于表示“合取”含义的一些联结词：如“不但(仅)…而且…”、“既…又…以”；用于表示条件联结词的“若…则…”，“p→q”表示q是p的必要条件，p是q的充分条件。在自然语言表达中，要根据前提和结论的语义来判断条件语句的前件和后件，否则会出现将必要条件当成充分条件的情形，以至于将真命题变成假命题，或将假命题变成真命题。在构造命题公式时，应概念清楚，按命题公式的定义准确书写公式。2）永真（假）式的判断、等价式和蕴涵式的证明；3）主析(合)取范式的求取可用：真值表法、公式推导法；或者可从主析(合)取范式直接转换成主合(析)取范式。）；如采用公式推导(等价取代)）法，可先将公式中的条件和双条件联结词转化掉，化为只含∧，∨，～的式子，然后利用德摩根律将“～”放到每个变元的前面，利用结合律、分配律将公式化成析(合)取范式。然后再要求将之化为主析(合)取范式。4）基本等价式、基本蕴涵式、推理规则和推理定律的熟练掌握；进行推理时能合适地选取证明方法：真值表法、用蕴涵式的定义(前件真推后件也真法、后件假推前件也假法)、直接证明法、反证法。一、求下列各公式的主析取范式和主合取范式：1.(p→q)∧r解：(p→q)∧r≡(～p∨q)∧r≡(～p∧r)∨(q∧r)(析取范式)≡(～p∧(q∨～q)∧r)∨((～p∨p)∧q∧r)≡(～p∧q∧r)∨(～p∧～q∧r)∨(～p∧q∧r)∨(p∧q∧r)≡(～p∧q∧r)∨(～p∧～q∧r)∨(p∧q∧r)(主析取范式)～((p→q)∧r)≡(～p∧～q∧～r)∨(～p∧q∧～r)∨(p∧～q∧r)∨(p∧q∧～r)∨(p∧～q∧～r)(原公式否定的主析取范式)(p→q)∧r≡(p∨q∨r)∧(p∨～q∨r)∧(～p∨q∨～r)∧(～p∨～q∨r)∧(～p∨q∨r)(主合取范式)主析取范式为(～p∧q∧r)∨(～p∧～q∧r)∨(p∧q∧r)主合取范式为(p∨q∨r)∧(p∨～q∨r)∧(～p∨q∨r)∧(～p∨q∨～r)∧(～p∨～q∨r)pqr(p→q)∧rTTTTTTFFTFTFTFFFFTTTFTFFFFTTFFFF2.(～p→q)∧(r∨p)解：(～p→q)∧(r∨p)≡(p∨q)∧(r∨p)(合取范式)≡(p∨q∨(r∧～r))∧(p∨(q∧～q))∨r)≡(p∨q∨r)∧(p∨q∨～r)∧(p∨q∨r)∧(p∨～q∨r)≡(p∨q∨r)∧(p∨q∨～r)∧(p∨～q∨r)(主合取范式)～((～p→q)∧(r∨p))≡(p∨～q∨～r)∧(～p∨q∨r)∧(～p∨～q∨r)∧(～p∨q∨～r)∧(～p∨～q∨～r)(原公式否定的主合取范式)(～p→q)∧(r∨p)≡(～p∧q∧r)∨(p∧～q∧～r)∨(p∧q∧～r)∨(p∧～q∧r)∨(p∧q∧r)(主析取范式)主析取范式为(p∧q∧r)∨(p∧q∧～r)∨(p∧～q∧r)∨(p∧～q∧～r)∨(～p∧q∧r)；主合取范式为(p∨q∨r)∧(p∨q∨～r)∧(p∨～q∨r).pqr(～p→q)∧(r∨p)TTTTTTFTTFTTTFFTFTTTFTFFFFTFFFFF3.p∨(～p→(q∨(～q→r)))解：p∨(～p→(q∨(～q→r)))≡p∨(p∨(q∨(q∨r)))≡p∨q∨r(主合取范式)～(p∨(～p→(q∨(～q→r))))≡(p∨～q∨r)∧(p∨～q∨～r)∧(p∨q∨～r)∧(～p∨q∨r)∧(～p∨q∨～r)∧(～p∨～q∨r)∧(～p∨～q∨～r)(原公式否定的主合取范式)p∨(～p→(q∨(～q→r)))≡(～p∧q∧～r)∨(～p∧q∧r)∨(～p∧～q∧r)∨(p∧～q∧～r)∨(p∧～q∧r)∨(p∧q∧～r)∨(p∧q∧r)(主析取范式)主析取范式为(p∧q∧r)∨(p∧q∧～r)∨(p∧～q∧r)∨(p∧～q∧～r)∨(～p∧q∧r)∨(～p∧q∧～r)∨(～p∧～q∧r)主合取范式为(p∨q∨r)pqrp∨(～p→(q∨(～q→r)))TTTTTTFTTFTTTFFTFTTTFTFTFFTTFFFF二、证明：1.p→q，～q∨r，～r，～s∨p～s证明：(1)～r前提引入(2)～q∨r前提引入(3)～q析取三段论，(1)，(2)(4)p→q前提引入(5)～p拒取式，(3)，(4)(6)～s∨p前提引入(7)～s析取三段论，(5)，(6)2.～b∨d，(e→～f)→～d，～e～b证明：(1)b结论的否定引入(2)～b∨d前提引入(3)d析取三段论，(1)，(2)(4)(e→～～f)→～d前提引入(5)～(e→～f)拒取式，(3)，(4)(6)e∧f置换，(5)(7)e化简，(6)(8)～e前提引入(9)e∧～e合取引入，(7)，(8)4、p→(q→r)，r→(q→s)p→(q→s)证明：(1)p附加前提引入(2)q附加前提引入(3)p→(q→r)前提引入(4)q→r假言推理，(1)，(3)(5)r假言推理，(2)，(4)(6)r→(q→s)前提引入(7)q→s假言推理，(5)，(6)(8)s假言推理，(2)，(7)三、设p：明天是晴天，q：我去教室，r：我去图书馆。试用日常语言复述下列各命题：(1)p→(q∨r);(2)q→～p∧～r;(3)(p∧q)r答：(1)如果明天是晴天，那么我去教室，或者我去图书馆。(2)如果我去教室，则晴天不是晴天，而且我也不去图书馆。(3)如果明天是晴天，而且我不去教室，那么我去图书馆；如果我去图书馆，那么明天是晴天，而且我不去教室。四、求下列公式的代入实例：(1)用p→q和q→p分别取代((p→q)→p)中的p和q；(2)用q和p∧～p分别取代(p→q)→(q→p)中的p和q。解：(1)(((p→q)→(q→p))→(p→q))(2)(q→(p∧～p))→((p∧～p)→q)五、下列公式哪些是永真式、永假式或可满足式：(1)(p∨～p)→((p→q)→(～q→～p))(2)(p∧(q∨r))→((p∧q)∨(p∧r))(3)(p∧q)→p(4)((p→q)∧(q→r))→(p→r)答：(1)，(3)，(4)，(2)都是永真式。六、证明下列各式：(1)p→(q→p)≡～p→(p→～q)(2)((p∧q)→p)≡T(3)(p→q)∧(r→q)≡(p∨r)→q证明：(1)p→(q→p)≡～p∨(～q∨p)≡～(～p)∨(～p∨～q)≡～p→(p→～q)(2)((p∧q)→p)≡～(p∧q)∨p≡(～p∨～q)∨p≡(～p∨p)∨～q≡T∨～q≡T(3)(p→q)∧(r→q)≡(～p∨q)∧(～r∨q)≡(～p∧～r)∨q≡～(p∨r)∨q≡(p∨r)→q七、用附加前提法(CP规则)证明：p→qp→(p∧q)证明：(1)p附加前提引入(2)p→q前提引入(3)q假言推理，(1)，(2)(4)p∧q合取引入，(1)，(3)八、用反证法证明：(1)p∨q，p→r，q→sr∨s；(2)p→～q，q∨～r，r∧～s～p证明：(1)(1)～(r∨s)结论的否定引入(2)～r∧～s置换，(1)(3)～r化简，(2)(4)～s化简，(2)(5)p→r前提引入(6)～p拒取式，(3)，(5)(7)q→s前提引入(8)～q拒取式，(4)，(7)(9)p∨q前提引入(10)p析取三段论，(8)，(9)(11)p∧～p合取引入，(6)，(10)(2)(1)p结论的否定引入(2)p→～q前提引入(3)～q假言推理，(1)，(2)(4)q∨～r前提引入(5)～r析取三段论，(3)，(4)(6)r∧～s前提引入(7)r化简，(6)(8)r∧～r合取引入，(5)，(7)