第3章命 题 逻 辑[*4/5]3.1命题的有关概念习题3.1及参考答案 1. 指出下列语句哪些是命题，对于命题指出其真值. (1) 北京在2008年举办奥运会. (2) 离散数学是计算机专业的必修课. (3) x>y. (4) 西南大学是一所“211工程”建设的学校. (5) 1是素数. (6) 读大学就是要学会思考. (7) 月收入超过3500元要缴纳个人所得税. 解(1) 是命题，真值为1. (2) 是命题，真值为1. (3) 不是命题，因为x和y的取值未定，于是无法确定x>y的真值. (4) 是命题，真值为1. (5) 是命题，真值为0. (6) 是命题，真值为1. (7) 是命题，真值为1. 2. 找出下列各命题的所有原子命题，并分别用小写英文字母表示. (1) 我不去游泳. (2) 张三一边看书，一边用iPhone听音乐. (3) 小李能歌善舞. (4) 这学期我选修人工智能或模式识别课程. (5) 明天去深圳的飞机是上午八点或上午八点半起飞. (6) 如果我有时间，我就回家去看望我的父母. (7) 我今天进城，除非天下雨. (8) 小张既没有外出也没有上网，他在睡觉. (9) 你只有刻苦学习，才能取得好成绩. (10) 仅当你走，我留下值班. 解(1) p: 我去游泳. (2) p: 张三看书，q: 张三用iPhone听音乐. (3) p: 小李能歌，q: 小李善舞. (4) p: 这学期我选修人工智能课程，q: 这学期我选修模式识别课程. (5) p: 明天去深圳的飞机是上午八点起飞，q: 明天去深圳的飞机是上午八点半起飞. (6) p: 我有时间，q: 我回家去看望我的父母. (7) p: 我今天进城，q: 天下雨. (8) p: 小张外出，q: 小张上网，r: 小张睡觉. (9) p: 你刻苦学习，q: 你取得好成绩. (10) p: 你走，q: 我留下值班. 3.2逻辑联结词 习题3.2及参考答案 1. (1) 设p:现在很多人都有车，求瘙綈p. (2) 写出“-2是偶数或3是正数”的否定命题. (3) 设p: 每个自然数都是整数，求p∨瘙綈p. 解(1) 瘙綈p: 现在不是很多人都有车. (2) “-2是偶数或3是正数”的否定命题为“-2不是偶数并且3不是正数”. (3) p∨瘙綈p: 每个自然数都是整数或者不是每个自然数都是整数. 2. 令p: 今天有雨，q: 明天有雨，p∧q，p∨q，p→q，pq，p↑q，p↓q和p→nq分别表示什么复合命题? 解p∧q: 今明两天都有雨. p∨q: 今天或者明天有雨. p→q: 如果今天有雨，那么明天有雨. pq: 今明两天只有一天有雨. p↑q: 不可能今明两天都有雨. p↓q: 不可能今天或明天有雨. p→nq: 不可能今天有雨，则明天有雨. 3. 令p:我们去图书馆，q:我们去上网，瘙綈(p∧q)表示什么复合命题? 解瘙綈(p∧q): 我们不能既去图书馆又去上网. 4. 令p: 我生病，q: 我去上课，则“虽然我没有生病，但我不去上课”该如何用符号表示？ 解瘙綈p∧瘙綈q. 5. “张红和张兰是姐妹”中的“和”与联结词∧有什么不同? 解“张红和张兰是姐妹”中的“和”表示的是两个人之间的关系，而联结词∧表示的是两个命题的合取.特别注意，不能将“张红和张兰是姐妹”分解成“张红是姐妹”且“张兰是姐妹”. 6. 写出一个命题，它可以表示为p(瘙綈q∧r). 解令p: 今天体育课考试，q: 今天下雨，r: 马老师来了，则p(瘙綈q∧r)表示“今天体育课考试当且仅当今天不下雨并且马老师来了”. 3.3命题公式及其真值表 习题3.3及参考答案 1. 将下列命题符号化. (1) 若a和b是奇数，则a+b是偶数. (2) 只有在正整数n≤2时，不定方程xn+yn=zn才有正整数解. (3) 天在下雨，我没有去书店. (4) 两矩阵相等当且仅当其对应的元素分别相等. (5) 这苹果虽然甜，但我不打算买. (6) 除非我接到正式邀请，否则我不去参加圣诞晚会. (7) 我和小王是同学. (8) 因为他要看今晚的NBA篮球比赛，所以他没有来上自习. (9) 尽管她学习成绩不好，但她的动手能力很强. (10) 我的手机没电了，借你的手机用一下. 解(1) 令p: a是奇数，q: b是奇数，r: a+b是偶数. 该命题符号化为p∧q→r. (2) 令p: 正整数n≤2，q: 不定方程xn+yn=zn有正整数解. 该命题符号化为q→p. (3) 令p: 天在下雨，q: 我去书店. 该命题符号化为p∧瘙綈q. (4) 令p: 两矩阵相等，q: 两矩阵对应的元素分别相等. 该命题符号化为pq. (5) 令p: 这苹果甜，q: 我打算买. 该命题符号化为p∧瘙綈q. (6) 令p: 我接到正式邀请，q: 我去参加圣诞晚会. 该命题符号化为瘙綈p→瘙綈q. (7) 令p: 我和小王是同学. 该命题符号化为p. (8) 令p: 他看今晚的NBA篮球比赛，q: 他来上自习. 该命题符号化为p∧瘙綈q. (9) 令p: 她学习成绩好，q: 她的动手能力很强. 该命题符号化为瘙綈p∧q. (10) 令p: 我的手机没电了，q: 借你的手机用一下. 该命题符号化为p∧q. 2. 设p,q和r为命题变元，列出下列命题公式的真值表. (1) (瘙綈p∧(p∨q))→q. (2) (瘙綈p∨瘙綈q)→(p瘙綈q). (3) (p∨q)→r. (4) (p→(q∧r))∧(瘙綈p→(瘙綈q∧瘙綈r)). 解(1) (瘙綈p∧(p∨q))→q的真值表如表31所示.表31pq瘙綈pp∨q瘙綈p∧(p∨q)瘙綈p∧(p∨q)→q110101100101011111001001(2) (瘙綈p∨瘙綈q)→(p瘙綈q)的真值表如表32所示.表32pq瘙綈p瘙綈q瘙綈p∨瘙綈qp瘙綈q(瘙綈p∨瘙綈q)→(p瘙綈q)1100001100111101101110011100(3) (p∨q)→r的真值表如表33所示.表33pqrp∨q(p∨q)→r1111111010101111001001111010100010100001(4) (p→(q∧r))∧(瘙綈p→(瘙綈q∧瘙綈r))（将该命题公式用A表示）的真值表如表34所示.表34pqrp→(q∧r)瘙綈p→(瘙綈q∧瘙綈r)A111111110010续表pqrp→(q∧r)瘙綈p→(瘙綈q∧瘙綈r)A1010101000100111000101000011000001113. 设p,q,r和s为命题变元，判断下列命题公式的类型. (1) (p→(q→r))((p∧q)→r). (2) ((p→r)∨瘙綈r)→(瘙綈(q→p)∧q). (3) ((p∨q)→r)(r→(p∧q)). (4) p→(瘙綈p∧q∧r∧s). 解(1) (p→(q→r))((p∧q)→r)（将该命题公式用A表示）的真值表如表35所示.表35pqrq→rp∧qp→(q→r)(p∧q)→rA1111111111001001101101111001011101110111010001110011011100010111由真值表可知，(p→(q→r))((p∧q)→r)是永真式. (2) 当p=0,q=1,r=1时，((p→r)∨瘙綈r)→(瘙綈(q→p)∧q)为1；当p=0,q=0,r=0时，((p→r)∨瘙綈r)→(瘙綈(q→p)∧p)为0.故((p→r)∨瘙綈r)→(瘙綈(q→p)∧q)是中性式. (3) 根据联结词的定义，对于命题公式((p∨q)→r)(r→(p∧q))，分别考虑(p∨q)→r和r→(p∧q).很显然，当p=0,q=0,r=0时，(p∨q)→r和r→(p∧q)都为1，在这种指派下原命题公式为1.若(p∨q)→r为0，则可取p=1,q=1,r=0，而这时r→(p∧q)为1，于是在这种指派下原命题公式为0. 故((p∨q)→r)(r→(p∧q))是中性式. (4) 当p=1,q=1,r=1,s=1时，p→(瘙綈p∧q∧r∧s)为0；当p=0,q=0,r=0,s=0时，p→(瘙綈p∧q∧r∧s)为1.故p→(瘙綈p∧q∧r∧s)是中性式. 4. 证明: 对于任意命题公式A、B和C，下列命题公式均永真. (1) A→(B→A). (2) (A→(B→C))→((A→B)→(A→C)). (3) (瘙綈A→瘙綈B)→(B→A). 证(1) 假定B→A＝0，则B=1,A=0，因此A→(B→A)永真. (2) 对于命题变元p、q和r，命题公式(p→(q→r))→((p→q)→(p→r))（将该命题公式用D表示）的真值表如表36所示.表36pqrp→(q→r)(p→q)→(p→r)D111111110001101111100111011111010111001111000111由真值表可知，命题公式(p→(q→r))→((p→q)→(p→r))是永真式，故对于任意命题公式A、B和C，(A→(B→C))→((A→B)→(A→C))是永真式. (3) 假定B→A＝0，则B=1,A=0，于是瘙綈A=1,瘙綈B=0，进而瘙綈A→瘙綈B＝0，因此(瘙綈A→瘙綈B)→(B→A)永真. 5. 证明: 对于任意命题公式A和B，有(AB)(A→B)∧(B→A)永真. 证对于任意命题变元p和q，命题公式(pq)(p→q)∧(q→p)的真值表如表37所示.表37pqpq(p→q)∧(q→p)(pq)(p→q)∧(q→p)11111100010100100111由真值表可知，(pq)(p→q)∧(q→p)是永真式.根据永真式的代入定理知，对于任意命题公式A和B，有(AB)(A→B)∧(B→A)永真. 6. 对于任意命题公式A、B和C，证明下列命题公式永真. (1) 瘙綈A→(A→B). (2) (A∨B)∧(A→C)∧(B→C)→C. (3) (A→B)∧(A→瘙綈B)→瘙綈A. (4) A→(瘙綈A→B). 证(1) 假定A→B＝0，则A=1,B=0，于是瘙綈A=0，因此瘙綈A→(A→B)永真. (2) 若(A∨B)∧(A→C)∧(B→C)→C＝0，则 (A∨B)∧(A→C)∧(B→C)=1且C=0 由(A∨B)∧(A→C)∧(B→C)=1，可得A∨B=1，A→C=1，B→C=1.由于C=0，由A→C=1和B→C=1，可推出A=0且B=0，进而A∨B=0，这与A∨B=1矛盾. 故(A∨B)∧(A→C)∧(B→C)→C永真. (3) 假定瘙綈A＝0，则A=1. 若B=0，则A→B=0，进而(A→B)∧(A→瘙綈B)=0. 若B=1，则瘙綈B=0，于是A→瘙綈B=0，进而(A→B)∧(A→瘙綈B)=0. 因此(A→B)∧(A→瘙綈B)→瘙綈A永真. (4) 假定瘙綈A→B＝0，则瘙綈A=1,B=0，进而A=0，所以A→(瘙綈A→B)永真. 3.4逻辑等值的命题公式 习题3.4及参考答案 1. 证明: 命题公式间的等值关系是等价关系. 证(1) 对于任意命题公式A，显然A=A，所以=是自反的. (2) 对于任意命题公式A和B，若A=B，则B=A，于是=是对称的. (3) 对于任意命题公式A、B和C，若A=B且B=C，则A=C，因此=是传递的. 由(1)、(2)和(3)知，=是等价关系. 2. 证明定理35中的分配律和德·摩根律. 证(1) 先证明析取对合取可分配: A∨(B∧C)=(A∨B)∧(A∨C). 对于任意命题变元p,q和r，命题公式p∨(q∧r)及(p∨q)∧(p∨r)的真值表如表38所示.表38pqrq∧rp∨qp∨rp∨(q∧r)(p∨q)∧(p∨r)1111111111001111101011111000111101111111010010000010010000000000由真值表可知，p∨(q∧r)和(p∨q)∧(p∨r)在任何指派下均有相同的真值，所以p∨(q∧r)=(p∨q)∧(p∨r).于是A∨(B∧C)=(A∨B)∧(A∨C)对于任意命题公式A,B和C均成立. 再证明合取对析取可分配: A∧(B∨C)=(A∧B)∨(A∧C). 对于任意命题变元p,q和r，命题公式p∧(q∨r)及(p∧q)∨(p∧r)的真值表如表39所示.表39pqrq∨rp∧qp∧rp∧(q∨r)(p∧q)∨(p∧r)1111111111011011101101111000000001110000010100000011000000000000由真值表可知，p∧(q∨r)和(p∧q)∨(p∧r)在任何指派下均有相同的真值，所以p∧(q∨r)=(p∧q)∨(p∧r).于是A∧(B∨C)=(A∧B)∨(A∧C)对于任意命题公式A,B和C均成立. (2) 先证明瘙綈(A∨B)=瘙綈A∧瘙綈B. 对于任意命题变元p,q，命题公式瘙綈(p∨q)及瘙綈p∧瘙綈q的真值表如表310所示.表310pqp∨q瘙綈p瘙綈q瘙綈(p∨q)瘙綈p∧瘙綈q1110000101010001110000001111由真值表可知，瘙綈(p∨q)和瘙綈p∧瘙綈q在任何指派下均有相同的真值，所以瘙綈(p∨q)=瘙綈p∧瘙綈q.于是瘙綈(A∨B)=瘙綈A∧瘙綈B对于任意命题公式A,B均成立. 再证明瘙綈(A∧B)=瘙綈A∨瘙綈B. 对于任意命题变元p,q，分别列出瘙綈(p∧q)及瘙綈p∨瘙綈q的真值表如表311所示. 由真值表可知，瘙綈(p∧q)和瘙綈p∨瘙綈q在任何指派下有相同的真值，所以瘙綈(p∧q)=瘙綈p∨瘙綈q.于是瘙綈(A∧B)=瘙綈A∨瘙綈B对于任意命题公式A,B均成立.表311pqp∧q瘙綈p瘙綈q瘙綈(p∧q)瘙綈p∨瘙綈q11100001000111010101100011113. 设A,B,C是任意的命题公式，判断下列命题是否成立，阐述理由. (1) 若A∧C=B∧C，则A=B; (2) 若A∨C=B∨C，则A=B; (3) 若瘙綈A=瘙綈B，则A=B. 解(1) 不成立.取A=p，B=p∨q，C=p，则A∧C=p∧p=p且B∧C=(p∨q)∧p吸收律p.于是A∧C=B∧C.而显然p≠p∨q，即A≠B. (2) 不成立.取A=p，B=p∧q，C=p，则A∨C=p∨p=p且B∨C=(p∧q)∨p吸收律p，于是A∨C=B∨C.而显然p≠p∧q，即A≠B. (3) 成立.因为瘙綈A=瘙綈B，所以瘙綈瘙綈A=瘙綈瘙綈B，于是A=B. 4. 设A,B是任意的命题公式，证明下列各式. (1) AB=瘙綈(AB)=(A∧瘙綈B)∨(瘙綈A∧B); (2) A→B=瘙綈A∨B; (3) A↑B=瘙綈(A∧B); (4) A↓B=瘙綈(A∨B). 证这些等值式的证明可以先针对命题变元进行，再根据定理32和永真式的代入定理就能得到要证明的结论.下面都是将A看作命题变元p且B看作命题变元q，利用真值表进行的证明. (1) 命题公式pq、瘙綈(pq)和(p∧瘙綈q)∨(瘙綈p∧q)的真值表如表312所示.表312pqpq瘙綈(pq)(p∧瘙綈q)∨(瘙綈p∧q)11000101110111100000由真值表知，命题公式pq、瘙綈(pq)和(p∧瘙綈q)∨(瘙綈p∧q)在任何指派下的取值都相同，因此pq=瘙綈(pq)=(p∧瘙綈q)∨(瘙綈p∧q).故对于任意命题公式A,B，均有AB=瘙綈(AB)=(A∧瘙綈B)∨(瘙綈A∧B). (2) 命题公式p→q和瘙綈p∨q的真值表如表313所示.表313pq瘙綈pp→q瘙綈p∨q11011100000111101111由真值表知，命题公式p→q和瘙綈p∨q在任何指派下的取值都相同，因此p→q=瘙綈p∨q.故对于任意命题公式A，B，均有A→B=瘙綈A∨B. (3) 命题公式p↑q和瘙綈(p∧q)的真值表如表314所示.表314pqp∧qp↑q瘙綈(p∧q)11100100110101101011由真值表知，命题公式p↑q和瘙綈(p∧q)在任何指派下的取值都相同，因此p↑q=瘙綈(p∧q).故对于任意命题公式A,B，均有A↑B=瘙綈（A∧B）. (4) 命题公式p↓q和瘙綈(p∨q)的真值表如表315所示.表315pqp∨qp↓q瘙綈(p∨q)11100101000110001011由真值表知，命题公式p↓q和瘙綈(p∨q)在任何指派下的取值都相同，因此 p↓q=瘙綈(p∨q).故对于任意命题公式A,B，均有A↓B=瘙綈(A∨B). 5. 设A,B,C是任意的命题公式，证明下列各式. (1) AB=BA； (2) (AB)C=A(BC)； (3) A→B=瘙綈B→瘙綈A； (4) 瘙綈(AB)=A瘙綈B. 证(1) 根据定理36有AB=(A∧瘙綈B)∨(瘙綈A∧B)，于是 BA=(B∧瘙綈A)∨(瘙綈B∧A) 由于∧和∨满足交换律，所以 AB=(A∧瘙綈B)∨(瘙綈A∧B)=(B∧瘙綈A)∨(瘙綈B∧A)=BA (2) 对于任意命题变元p,q和r，命题公式(pq)r及p(qr)的真值表如表316所示.表316pqrpqqr(pq)rp(qr)11100111100100101110010010110111000010111100101110000000由真值表可知，(pq)r和p(qr)在任何指派下均有相同的真值，所以(pq)r=p(qr).于是(AB)C=A(BC)对于任意命题公式A,B和C均成立. (3) 瘙綈B→瘙綈A=瘙綈(瘙綈B)∨瘙綈A=B∨瘙綈A=瘙綈A∨B=A→B. (4) 因为瘙綈(AB)=(A∧瘙綈B)∨(瘙綈A∧B)，而 A瘙綈B=(A→瘙綈B)∧(瘙綈B→A)=(瘙綈A∨瘙綈B)∧(瘙綈瘙綈B∨A) =(瘙綈A∨瘙綈B)∧(A∨B) =(瘙綈A∧A)∨(瘙綈A∧B)∨(瘙綈B∧A)∨(瘙綈B∧B) =0∨(瘙綈A∧B)∨(瘙綈B∧A)∨0=(瘙綈A∧B)∨(A∧瘙綈B) 所以，有瘙綈(AB)=A瘙綈B. 6. 设A和B是命题公式，证明关于逻辑联结词↑的下列结论. (1) 瘙綈A=A↑A； (2) A∧B=(A↑B)↑(A↑B)； (3) A∨B=(A↑A)↑(B↑B). 证(1) 瘙綈A=瘙綈(A∧A)=A↑A. (2) A∧B=瘙綈(瘙綈(A∧B))=瘙綈(A↑B)=(A↑B)↑(A↑B). (3) A∨B=瘙綈(瘙綈A∧瘙綈B)=(瘙綈A)↑(瘙綈B)=(A↑A)↑(B↑B). 7. 设A和B是命题公式，证明关于逻辑联结词↓的下列结论. (1) 瘙綈A=A↓A； (2) A∧B=(A↓A)↓(B↓B)； (3) A∨B=(A↓B)↓(A↓B). 证(1) 瘙綈A=瘙綈(A∨A)=A↓A. (2) A∧B=瘙綈(瘙綈A∨瘙綈B)=(瘙綈A)↓(瘙綈B)=(A↓A)↓(B↓B). (3) A∨B=瘙綈(瘙綈(A∨B))=瘙綈(A↓B)=(A↓B)↓(A↓B). 8. 设A, B和C是命题公式，将等价联结词记为⊙，证明下列等值式. (1) A⊙B=B⊙A； (2) (A⊙B)⊙C=A⊙(B⊙C)； (3) A⊙B=瘙綈(AB)； (4) A⊙B=(A∧B)∨(瘙綈A∧瘙綈B). 证(1) 对于任意命题变元p,q，命题公式p⊙q及q⊙p的真值表如表317所示.表317pqp⊙qq⊙p1111100001000011由真值表可知，p⊙q和q⊙p在任何指派下均有相同的真值，所以p⊙q=q⊙p.于是A⊙B=B⊙A对于任意命题公式A,B均成立. (2) 对于任意命题变元p,q和r，命题公式(p⊙q)⊙r及p⊙(q⊙r)的真值表如表318所示.表318pqrp⊙qq⊙r(p⊙q)⊙rp⊙(q⊙r)11111111101000101000010001110110100010001100110110001100由真值表可知，(p⊙q)⊙r和p⊙(q⊙r)在任何指派下均有相同的真值，所以(p⊙q)⊙r=p⊙(q⊙r).于是(A⊙B)⊙C=A⊙(B⊙C)对于任意命题公式A,B和C均成立. (3) 由于AB=瘙綈(AB)，于是瘙綈(AB)=瘙綈瘙綈(AB)，进而瘙綈(AB)=AB，即A⊙B=瘙綈(AB). (4) A⊙B=(A→B)∧(B→A)=(瘙綈A∨B)∧(瘙綈B∨A) =(瘙綈A∧瘙綈B)∨(瘙綈A∧A)∨(B∧瘙綈B)∨(B∧A) =(瘙綈A∧瘙綈B)∨0∨0∨(B∧A)=(A∧B)∨(瘙綈A∧瘙綈B). 9. 设A,B,C,D是任意的命题公式，化简下列命题公式并将最后的结果仅用↓表示. (1) (A∧B∧C)∨(A∧瘙綈B∧C)； (2) (A∧B)∨(瘙綈A∧B)∨(A∧瘙綈B)； (3) 瘙綈((A∧B)∨(A∧C))； (4) (A∧B)∨(瘙綈A∧B)∨(B∧C∧D). 解(1) (A∧B∧C)∨(A∧瘙綈B∧C) =((A∧C)∧B)∨((A∧C)∧瘙綈B) =(A∧C)∧(B∨瘙綈B)=(A∧C)∧1=A∧C =(A↓A)↓(C↓C). (2) (A∧B)∨(瘙綈A∧B)∨(A∧瘙綈B) =((A∧B)∨(瘙綈A∧B))∨(A∧瘙綈B) =((A∨瘙綈A)∧B)∨(A∧瘙綈B)=(1∧B)∨(A∧瘙綈B)=B∨(A∧瘙綈B) =(B∨A)∧(B∨瘙綈B)=(B∨A)∧1=B∨A=A∨B =(A↓B)↓(A↓B). (3) 瘙綈((A∧B)∨(A∧C)) =瘙綈(A∧(B∨C))=瘙綈瘙綈(瘙綈A∨瘙綈(B∨C))=瘙綈((瘙綈A)↓(瘙綈(B∨C))) =瘙綈((A↓A)↓(B↓C))=((A↓A)↓(B↓C))↓((A↓A)↓(B↓C)). (4) (A∧B)∨(瘙綈A∧B)∨(B∧C∧D) =((A∧B)∨(瘙綈A∧B))∨(B∧C∧D) =((A∨瘙綈A)∧B)∨(B∧C∧D)=(1∧B)∨(B∧C∧D) =B∨(B∧C∧D)=B. 10. 设A,B,C,D是任意的命题公式，判断下列命题公式的类型. (1) ((A→C)∨瘙綈C)→(瘙綈(B→A)∧A)； (2) (A→C)→((B→D)→((A∨B)→C)). 解(1) 由于 ((A→C)∨瘙綈C)→(瘙綈(B→A)∧A) =((瘙綈A∨C)∨瘙綈C)→((B∧瘙綈A)∧A) =(瘙綈A∨(C∨瘙綈C))→(B∧(瘙綈A∧A)) =(瘙綈A∨1)→(B∧0) =1→0=0 所以，((A→C)∨瘙綈C)→(瘙綈(B→A)∧A)是永假式. (2) 因为 (A→C)→((B→D)→((A∨B)→C)) =(A→C)→((B→D)→(瘙綈(A∨B)∨C)) =(A→C)→((瘙綈B∨D)→(瘙綈(A∨B)∨C)) =(A→C)→(瘙綈(瘙綈B∨D)∨(瘙綈(A∨B)∨C)) =(瘙綈A∨C)→((B∧瘙綈D)∨(瘙綈A∧瘙綈B)∨C) =瘙綈(瘙綈A∨C)∨((B∧瘙綈D)∨(瘙綈A∧瘙綈B)∨C) =(A∧瘙綈C)∨(B∧瘙綈D)∨(瘙綈A∧瘙綈B)∨C =((A∧瘙綈C)∨C)∨(B∧瘙綈D)∨(瘙綈A∧瘙綈B) =A∨C∨(B∧瘙綈D)∨(瘙綈A∧瘙綈B) =(A∨(瘙綈A∧瘙綈B))∨C∨(B∧瘙綈D) =A∨瘙綈B∨C∨(B∧瘙綈D) =A∨(瘙綈B∨(B∧瘙綈D))∨C =A∨瘙綈B∨瘙綈D∨C =A∨瘙綈B∨C∨瘙綈D 显然，(A→C)→((B→D)→((A∨B)→C))是中性式. 11. 设A,B,C是任意的命题公式，证明下列等值式. (1) 瘙綈(A→B)=A∧瘙綈B; (2) A→(B→A)=瘙綈A→(A→瘙綈B); (3) (A→C)∧(B→C)=(A∨B)→C; (4) A→(B→C)=(A∧B)→C. 证(1) 瘙綈(A→B)=瘙綈(瘙綈A∨B)=A∧瘙綈B. (2) 由于 A→(B→A)=A→(瘙綈B∨A)=瘙綈A∨(瘙綈B∨A)=瘙綈A∨瘙綈B∨A=1 而 瘙綈A→(A→瘙綈B)=瘙綈A→(瘙綈A∨瘙綈B)=瘙綈瘙綈A∨(瘙綈A∨瘙綈B) =A∨瘙綈A∨瘙綈B=1 所以A→(B→A)=瘙綈A→(A→瘙綈B). (3)(A→C)∧(B→C) =(瘙綈A∨C)∧(瘙綈B∨C) =(瘙綈A∧瘙綈B)∨C=瘙綈(A∨B)∨C=(A∨B)→C. (4)A→(B→C) =A→(瘙綈B∨C)=瘙綈A∨(瘙綈B∨C) =(瘙綈A∨瘙綈B)∨C=瘙綈(A∧B)∨C=(A∧B)→C. 12. 设p和q是命题变元，求出pq的对偶式，它与p⊙q的关系如何? 解由于pq=(p∧瘙綈q)∨(瘙綈p∧q)，所以pq的对偶式为 (pq)*=(p∨瘙綈q)∧(瘙綈p∨q)=(p∧瘙綈p)∨(p∧q)∨(瘙綈q∧瘙綈p)∨(瘙綈q∧q) =(p∧q)∨(瘙綈p∧瘙綈q)=p⊙q 13. 有一个国家只有两种人: 一种人总说真话，另一种人总说假话.一个逻辑学家来到该国，在一个三岔路口处，不知道哪一条路是去首都方向的.这时碰巧来了一个人，逻辑学家只问了他一个问题，就知道去首都的路了.请问他问的是什么问题? 为什么？ 解逻辑学家指着两条路中的一条问：“这条路是去首都方向的吗？其他人(指与所问的人不是同一种人的人)将回答‘是的’，对吗？” 令p:被问的人说真话，q:被问的人回答“是”，r:其他人将回答“是”，s:这条路是去首都方向的，则有表319.表319pqrs1110100101000011由表319可知，r=pq，s=瘙綈q.于是，当被问的人回答“是”时，这条路不是去首都方向的；当被问的人回答“不是”时，这条路是去首都方向的. 3.5命题公式的范式 习题3.5及参考答案 1. 求下列命题公式的析取范式与合取范式. (1) p∧(p→q). (2) 瘙綈(p∧q)∧(p∨q). (3) (瘙綈p∧q)→r. (4) (p→q)→r. 解(1) p∧(p→q)=p∧(瘙綈p∨q)=(p∧瘙綈p)∨(p∧q)=0∨(p∧q) =p∧q(析取范式和合取范式) (2) 瘙綈(p∧q)∧(p∨q)=(瘙綈p∨瘙綈q)∧(p∨q)(合取范式) =(瘙綈p∧p)∨(瘙綈p∧q)∨(瘙綈q∧p)∨(瘙綈q∧q) =(瘙綈p∧q)∨(p∧瘙綈q)(析取范式) (3) (瘙綈p∧q)→r=瘙綈(瘙綈p∧q)∨r=p∨瘙綈q∨r(析取范式和合取范式) (4) (p→q)→r=(瘙綈p∨q)→r=瘙綈(瘙綈p∨q)∨r =(p∧瘙綈q)∨r(析取范式) =(p∨r)∧(瘙綈q∨r)(合取范式) 2. 在一次研讨会上，3名与会者根据王教授的口音分别作出下述判断. 甲说: “王教授不是苏州人，是上海人.” 乙说: “王教授不是上海人，是苏州人.” 丙说: “王教授不是杭州人，也不是上海人.” 王教授听后笑道: “你们3人中有一个人全说对了，有一个人全说错了，有一个人对错各半.” 请问王教授是哪里人? 解令p: 王教授是苏州人，q: 王教授是上海人，r: 王教授是杭州人.分别考虑由p,q,r产生的所有极小项: (1) p∧q∧r表示王教授是苏州人、上海人和杭州人，这时甲和乙对错各一半，而丙全错，不可能. (2) p∧q∧瘙綈r表示王教授是苏州人、上海人，但不是杭州人，这时甲、乙和丙对错各一半，不可能. (3) p∧瘙綈q∧r表示王教授是苏州人、杭州人，但不是上海人，这时甲和丙对错各一半，而乙全对，不可能. (4) p∧瘙綈q∧瘙綈r表示王教授是苏州人，但不是上海人、杭州人，这时甲全错，乙和丙全对，不可能. (5) 瘙綈p∧q∧r表示王教授不是苏州人，是上海人、杭州人，这时甲全对，乙和丙全错，不可能. (6) 瘙綈p∧q∧瘙綈r表示王教授不是苏州人、杭州人，是上海人，这时甲全对，乙全错，而丙对错各半，这是一种正确答案. (7) 瘙綈p∧瘙綈q∧r表示王教授不是苏州人、上海人，是杭州人，这时甲和乙对错各一半，而丙全对，不可能. (8) 瘙綈p∧瘙綈q∧瘙綈r表示王教授不是苏州人、上海人、杭州人，这时甲和乙对错各一半，而丙全对，不可能. 综上所述，王教授是上海人. 说明若利用王教授只能是其中一个城市的人或者不是这三个城市的人这两个可能性，可以将上面的求解过程简化. 3. 当p,q,r,s 4个人考试成绩出来后，有人问4个人中谁的成绩最好.p说“不是我.”q说“是s.”r说“是q.”s说“不是我.”4个人的回答只有一个人符合实际.哪个人的成绩最好？若有两个人成绩并列最好，应是哪两个人？ 解令p: p的成绩最好，q: q的成绩最好，r: r的成绩最好，s: s的成绩最好. 若只有p的回答正确，则有瘙綈p∧瘙綈s∧瘙綈q∧瘙綈瘙綈s. 若只有q的回答正确，则有瘙綈瘙綈p∧s∧瘙綈q∧瘙綈瘙綈s. 若只有r的回答正确，则有瘙綈瘙綈p∧瘙綈s∧q∧瘙綈瘙綈s. 若只有s的回答正确，则有瘙綈瘙綈p∧瘙綈s∧瘙綈q∧瘙綈s. 由于 (瘙綈p∧瘙綈s∧瘙綈q∧瘙綈瘙綈s)∨(瘙綈瘙綈p∧s∧瘙綈q∧瘙綈瘙綈s)∨ (瘙綈瘙綈p∧瘙綈s∧q∧瘙綈瘙綈s)∨(瘙綈瘙綈p∧瘙綈s∧瘙綈q∧瘙綈s) =(p∧s∧瘙綈q∧瘙綈瘙綈s)∨(瘙綈瘙綈p∧瘙綈s∧瘙綈q∧瘙綈s) =(p∧瘙綈q∧s)∨(p∧瘙綈q∧瘙綈s) =(p∧瘙綈q∧r∧s)∨(p∧瘙綈q∧瘙綈r∧s)∨ (p∧瘙綈q∧r∧瘙綈s)∨(p∧瘙綈q∧瘙綈r∧瘙綈s) 在上式中，p∧瘙綈q∧r∧s表示p,r,s成绩最好，p∧瘙綈q∧瘙綈r∧s表示p,s成绩最好，p∧瘙綈q∧r∧瘙綈s表示p,r成绩最好，p∧瘙綈q∧瘙綈r∧瘙綈s表示p成绩最好. 于是，当只有一个人成绩最好时，是p；当有两个人成绩并列最好时，应是p,s或p,r. 4. 已知p,q,r,s这4个人中有且仅有两个人参加围棋比赛, 但必须满足下列4个条件: (1) p和q仅一个人参加. (2) 若r参加，则s也参加. (3) q和s至多参加一个人. (4) 若s不参加，则p也不参加. 应派哪两个人去参加比赛? 解令p: p参加围棋比赛，q: q参加围棋比赛，r: r参加围棋比赛，s: s参加围棋比赛，则4个条件分别符号化为 (1) pq. (2) r→s. (3) 瘙綈(q∧s). (4) 瘙綈s→瘙綈p. 由于4个条件要求同时满足，所以 A(p,q,r,s)=(pq)∧(r→s)∧瘙綈(q∧s)∧(瘙綈s→瘙綈p) 求出A(p,q,r,s)的主析取范式： A(p,q,r,s)=(pq)∧(r→s)∧瘙綈(q∧s)∧(瘙綈s→瘙綈p) =(((瘙綈p∧q)∨(p∧瘙綈q))∧(瘙綈r∨s))∧(瘙綈q∨瘙綈s)∧(s∨瘙綈p) =((瘙綈p∧q∧瘙綈r)∨(瘙綈p∧q∧s)∨(p∧瘙綈q∧瘙綈r)∨ (p∧瘙綈q∧s))∧((瘙綈q∧s)∨(瘙綈p∧瘙綈q)∨(瘙綈p∧瘙綈s)) =(瘙綈p∧q∧瘙綈r∧s)∨(瘙綈p∧q∧r∧s)∨(p∧瘙綈q∧瘙綈r∧瘙綈s)∨ (p∧瘙綈q∧瘙綈r∧s)∨(p∧瘙綈q∧r∧s)∨(瘙綈p∧q∧瘙綈r∧瘙綈s) 根据已知条件，只有p∧瘙綈q∧瘙綈r∧s取真一种情况，于是 p=1,q=0,r=0,s=1 即应派p和s参加围棋比赛. 5. 分别用等值演算法和真值表法求下列命题公式的主析取范式及主合取范式, 并判断其类型. (1) (瘙綈p∨瘙綈q)→(p瘙綈q). (2) (q→p)∧(瘙綈p∧q). (3) (q∨瘙綈p)→r. (4) (p→(q∧r))∧(瘙綈p→(瘙綈q∧瘙綈r)). 解(1) 方法1： 等值演算法. (瘙綈p∨瘙綈q)→(p瘙綈q)=(瘙綈p∨瘙綈q)→((p→瘙綈q)∧(瘙綈q→p)) =瘙綈(瘙綈p∨瘙綈q)∨((瘙綈p∨瘙綈q)∧(p∨q)) =(p∧q)∨((瘙綈p∨瘙綈q)∧(p∨q)) =(p∧q)∨((瘙綈p∧p)∨(瘙綈p∧q)∨(瘙綈q∧p)∨(瘙綈q∧q)) =(p∧q)∨(瘙綈p∧q)∨(p∧瘙綈q)(主析取范式) =m11∨m01∨m10 =M00 =(p∨q)(主合取范式) 方法2： 真值表法. 列出(瘙綈p∨瘙綈q)→(p瘙綈q)的真值表，如表320所示.表320pq瘙綈p瘙綈q瘙綈p∨瘙綈qp瘙綈q(瘙綈p∨瘙綈q)→(p瘙綈q)1100001100111101101110011100由真值表知： (瘙綈p∨瘙綈q)→(p瘙綈q)=(p∧q)∨(瘙綈p∧q)∨(p∧瘙綈q)(主析取范式) (瘙綈p∨瘙綈q)→(p瘙綈q)=(p∨q)(主合取范式) 因此，(瘙綈p∨瘙綈q)→(p瘙綈q)是中性式. (2) 方法1： 等值演算法. (q→p)∧(瘙綈p∧q)=(p∨瘙綈q)∧(瘙綈p∧q)=(((p∨瘙綈q)∧瘙綈p)∧q) =(瘙綈p∧瘙綈q)∧q=瘙綈p∧瘙綈q∧q=0 =(主析取范式不存在) =(p∨q)∧(p∨瘙綈q)∧(瘙綈p∨q)∧(瘙綈p∨瘙綈q)(主合取范式) 方法2： 真值表法. 列出(q→p)∧(瘙綈p∧q)的真值表，如表321所示.表321pq瘙綈pq→p瘙綈p∧q(q→p)∧(瘙綈p∧q)110100100100011010001100由真值表知： (q→p)∧(瘙綈p∧q)的主析取范式不存在. (q→p)∧(瘙綈p∧q)=(p∨q)∧(p∨瘙綈q)∧(瘙綈p∨q)∧(瘙綈p∨瘙綈q)(主合取范式) 因此，(q→p)∧(瘙綈p∧q)是永假式. (3) 方法1： 等值演算法. (q∨瘙綈p)→r=瘙綈(q∨瘙綈p)∨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)(主合取范式) =M000∧M010∧M110 =m111∨m101∨m100∨m011∨m001 =(p∧q∧r)∨(p∧瘙綈q∧r)∨(p∧瘙綈q∧瘙綈r)∨ (瘙綈p∧q∧r)∨(瘙綈p∧瘙綈q∧r)(主析取范式) 方法2： 真值表法. 列出(q∨瘙綈p)→r的真值表，如表322所示.表322pqr瘙綈pq∨瘙綈p(q∨瘙綈p)→r111011110010101001100001011111010110001111000110由真值表知： (q∨瘙綈p)→r=(p∧q∧r)∨(p∧瘙綈q∧r)∨(p∧瘙綈q∧瘙綈r)∨ (瘙綈p∧q∧r)∨(瘙綈p∧瘙綈q∧r)(主析取范式) (q∨瘙綈p)→r=(p∨q∨r)∧(p∨瘙綈q∨r)∧(瘙綈p∨瘙綈q∨r)(主合取范式) 因此，(q∨瘙綈p）→r是中性式. (4) 方法1： 等值演算法. (p→(q∧r))∧(瘙綈p→(瘙綈q∧瘙綈r)) =(瘙綈p∨(q∧r))∧(p∨(瘙綈q∧瘙綈r)) =(瘙綈p∨q)∧(瘙綈p∨r)∧(p∨瘙綈q)∧(p∨瘙綈r) =(瘙綈p∨q∨(r∧瘙綈r))∧(瘙綈p∨(q∧瘙綈q)∨r)∧ (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∨q∨r)∧(瘙綈p∨q∨瘙綈r)∧(瘙綈p∨瘙綈q∨r)∧ (p∨瘙綈q∨r)∧(p∨瘙綈q∨瘙綈r)∧(p∨q∨瘙綈r)(主合取范式) =M100∧M101∧M110∧M010∧M011∧M001 =m111∨m000 =(p∧q∧r)∨(瘙綈p∧瘙綈q∧瘙綈r)(主析取范式) 方法2： 真值表法. 列出(p→(q∧r))∧(瘙綈p→(瘙綈q∧瘙綈r))（将该命题公式用A表示）的真值表，如表323所示.表323pqrp→(q∧r)瘙綈p→(瘙綈q∧瘙綈r)A111111110010101010100010011100010100001100000111由真值表知： (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))是中性式. 6. 利用主范式判断命题公式(p→q)∨(q→r)→((p∨q)→r)的类型. 解因为 (p→q)∨(q→r)→((p∨q)→r) =((瘙綈p∨q)∨(瘙綈q∨r))→(瘙綈(p∨q)∨r) =1→(瘙綈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)∨(q→r)→((p∨q)→r)恰有3种指派使其为0，进而恰有5种指派使其为1，故(p→q)∨(q→r)→((p∨q)→r)是中性式. 7. 利用主范式判断下列两个命题公式是否等值. (1) (p∧q)∨(瘙綈p∧r)∨(q∧r). (2) (p∧q)∨(瘙綈p∧r). 解先分别求出所给两个命题公式的主析取范式. (1) (p∧q)∨(瘙綈p∧r)∨(q∧r) =(p∧q∧(r∨瘙綈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)