下载文档原格式
离散数学是一门研究离散结构和离散对象的数学学科，它在计算机科学等领域扮演着重要的角色。
布尔函数和布尔代数是离散数学中的重要概念之一，它们在逻辑电路设计、计算机编程等方面具有广泛的应用。
布尔函数是一种将布尔域上的值映射为布尔域上的值的函数。
布尔域上的值只有两个：真和假。
布尔函数的输入和输出都是布尔值。
布尔函数可以通过真值表、函数表达式或者逻辑电路图表示。
常见的布尔运算有与运算、或运算、非运算等。
布尔函数可以定义在不同的布尔变量上，而布尔变量可以取真或假两个值。
通过组合不同的布尔运算，可以构造出复杂的布尔函数。
布尔代数是研究布尔函数性质和运算规则的代数系统。
布尔代数的基本操作有与运算、或运算、非运算等。
与运算、或运算和非运算是布尔函数的基本运算，在布尔代数中具有特殊的性质。
例如，与运算满足交换律、结合律和分配律；或运算满足交换律、结合律和分配律；非运算满足德摩根定律。
布尔代数还有很多其他的运算规则，如吸收律、零元律、幂等律等。
这些运算规则可以用来简化布尔函数，使其更加简洁明了。
布尔函数和布尔代数在逻辑电路设计中起着重要的作用。
逻辑电路是一种基础的电子电路，用来完成逻辑运算。
布尔函数可以用来描述逻辑电路的功能，布尔代数可以用来简化逻辑电路。
通过布尔函数和布尔代数可以设计出各种复杂的逻辑电路，如逻辑门、多路选择器、时序电路等。
逻辑电路在计算机硬件中广泛应用，是计算机工作的基础。
因此，研究布尔函数和布尔代数不仅有助于理解离散数学的基本概念，也对计算机科学和工程领域有着重要的实际意义。
此外，布尔函数和布尔代数在计算机编程中也具有重要的应用。
计算机程序是一系列指令的集合，通过执行这些指令实现特定的功能。
布尔函数可以用来描述程序中的条件和逻辑关系，判断某个条件是否成立，从而确定程序的执行路径。
布尔代数可以用来简化程序的逻辑表达式，使程序更加高效和可读。
在编程语言中，布尔变量和布尔运算是基础数据类型和基本运算符之一，它们与布尔函数和布尔代数密切相关。
离散数学课后习题及答案离散数学是计算机科学与数学的重要基础课程之一，它涵盖了很多重要的概念和理论。
为了更好地掌握离散数学的知识，课后习题是必不可少的一部分。
本文将介绍一些常见的离散数学课后习题，并提供相应的答案，希望对读者有所帮助。
一、集合论1. 设A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。
答案：A∪B={1,2,3,4}，A∩B={2,3}2. 设A={1,2,3}，B={2,3,4}，C={3,4,5}，求(A∪B)∩C的结果。
答案：(A∪B)∩C={3,4}二、逻辑与命题1. 判断下列命题的真假：a) 若2+2=5，则地球是平的。
b) 若今天下雨，则我会带伞。
c) 若x>0，则x^2>0。
答案：a)假，b)真，c)真。
2. 用真值表验证下列命题的等价性：a) p∧(q∨r) ≡ (p∧q)∨(p∧r)b) p→q ≡ ¬p∨q答案：a)等价，b)等价。
三、关系与函数1. 给定关系R={(1,2),(2,3),(3,4)}，求R的逆关系R^-1。
答案：R^-1={(2,1),(3,2),(4,3)}2. 设函数f(x)=x^2，g(x)=2x+1，求复合函数f(g(x))的表达式。
答案：f(g(x))=(2x+1)^2=4x^2+4x+1四、图论1. 给定图G，其邻接矩阵为：0 1 11 0 11 1 0求图G的度数序列。
答案：度数序列为(2,2,2)2. 判断下列图是否为连通图：a) G1的邻接矩阵为：0 1 11 0 01 0 0b) G2的邻接矩阵为：0 1 01 0 10 1 0答案：a)不是连通图，b)是连通图。
五、组合数学1. 从10个不同的球中，任选3个，求共有多少种选法。
答案：C(10,3)=120种选法。
2. 求下列排列的循环节：a) (123)(45)(67)b) (12)(34)(56)(78)答案：a)循环节为(123)(45)(67)，b)循环节为(12)(34)(56)(78)。
离散数学课后答案(第1-2-4章)武汉大学出版社习题1.11、（1）否（2）否（3）是，真值为0（4）否（5）是，真值为12、（1）P：天下雨Q：我去教室┐P →Q（2）P：你去教室Q：我去图书馆P →Q （3）P，Q同（2）Q →P（4）P：2是质数Q：2是偶数P∧Q3、（1）0（2）0（3）14、（1）如果明天是晴天，那么我去教室或图书馆。
（2）如果我去教室，那么明天不是晴天，我也不去图书馆。
（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。
习题1.21、（1）是（2）是（3）否（4）是（5）是（6）否2、（1）(P →Q) →R，P →Q，R，P，Q （2）(┐P∨Q) ∨（R∧P），┐P ∨Q，R∧P，┐P，Q，R，P（3）((P →Q) ∧(Q →P)) ∨┐(P →Q))，(P →Q) ∧(Q →P)，┐(P →Q)，P →Q，(Q →P)，P →Q，P，Q，Q，P，P，Q3、（1）((P →Q) →(Q →P)) →(P →Q) （2）((P →Q) ∨((P →Q) →R))→((P →Q) ∧((P →Q) →R))（3）(Q →P∧┐P) →(P∧┐P →Q)4、(P →Q) ∨((P∧Q) ∨(┐P∧┐Q)) ∧(┐P∨Q)习题1.31、（1）I(P∨(Q∧R)) = I(P)∨(I(Q)∧I(R)) = 1∨(1∧0) = 1（2）I((P∧Q∧R)∨(┐(P∨Q)∧┐(R∨S))) = (1∧1∧0)∨(┐(1∨1)∧┐(0∨1)) = 0∨(0∧0) = 0 （3）I((P←→R)∧(┐Q→S)) = (1←→0)∧(┐1→1) = 0∧1 = 0（4）I((P∨(Q→R∧┐P))←→(Q∨┐S)) = (1∨(1→(0∧┐1)))←→(1∨┐1) = 1←→1 = 1（5）I(┐(P∧Q)∨┐R∨((Q←→┐P)→R∨┐S)) = ┐(1∧1)∨┐0∨((1←→┐1)→(0∨┐1)) = 0∨1∨1 = 12、（1）P Q P→Q Q∧(P→Q) Q∧(P→Q)→P0 0 1 0 10 1 1 1 01 0 0 0 11 1 1 1 1（2）P Q R Q∧R ┐(P∨(Q∧R)) P∨Q P∨R（2）原式<=> ┐T∨(┐(┐P∨Q)∨(┐┐Q∨┐P)) <=> (P∧┐Q)∨(Q∨┐P)<=> (P∧┐Q)∨┐(P∧┐Q) <=> T 原式为永真式（3）原式<=> ┐(P∧Q) ←→┐(P∧Q) <=> T 原式为永真式（4）原式<=> P∧(Q∨R) ←→P∧(Q∨R) <=> T 原式为永真式（5）原式<=> ┐(P∨┐Q)∨Q <=> (┐P∧Q)∨Q <=> Q 原式为可满足式（6）原式<=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> T 原式为永真式（7）原式<=> (┐P∨P∨Q)∧┐P <=> (T∨Q)∧┐P<=> T∧┐P <=> ┐P 原式为可满足式（8）原式<=> ┐((P∨Q) ∧(┐Q∨R))∨(┐P ∨R) <=> (P∧┐Q)∨(Q∧┐R)∨(┐P∨R)<=> ((P∧┐Q)∨┐P)∨((Q∧┐R)∨R)<=>(( P∨┐P)∧(┐Q∨┐P))∨(( Q∨R)∧(┐R ∨R))<=> (┐Q∧┐P)∨( Q∨R) <=> T 原式为永真式4、（1）左<=> ┐P∨┐Q∨P <=> ┐┐P∨(┐P ∨┐Q) <=> 右（2）左<=> ┐(┐P∨Q) <=> 右（3）左<=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> 右（4）左<=> ┐(P→Q)∨┐(Q→P) <=> (P∧┐Q)∨(Q∧┐P) <=> 中<=> ((P∧┐Q)∨Q)∧((P∧┐Q)∨┐P)<=> (P∨Q)∧(┐Q∨Q)∧(P∨┐P)∧(┐Q∨┐P)<=> (P∨Q)∧┐(P∧Q) <=> 右(5)左( P Q) ( R Q) (P Q) Q 右5.(1)左Q P Q 右(2)(P (Q R)) ((P Q) (P R))( P Q R) ( P Q) ( P R)(P Q R) (P Q) P R(P Q R) ((P P) ( Q P)) R(P Q R) ( Q P R)(P Q R) (P Q R)T故P (Q R) (P Q) (P R)(3).(P Q) (P P Q)( P Q) P (P Q)( P Q) ( P P) ( P Q)( P Q) ( P Q)T故P Q P P Q(4).((P Q) Q) P Q( ( P Q) Q) P Q(( P Q) Q) P Q( P Q) (Q Q) P Q(P Q) (P Q)T故(P Q) Q P Q(5).((P P) Q) ((P P) R) (Q R) (( T Q) ( T R)) Q R(Q R) Q RQ R Q RQ TT故((P P) Q) ((P P) R) Q R(6)左(Q F) (R F)( Q F) ( R F)Q RRR Q 右6.(1)原式( P Q R)(2)原式P Q P (P Q P)(3)原式P (Q R P) P Q R ( P Q R)7.(1)原式( P Q P)(2)原式( P Q R) P Q ( ( P Q R) P Q)(3)原式P Q (R P) (P Q (R P))8. (1) (P Q) (( P ( P Q)) R) P(2)(P Q R) ( P R)(3)(P F) (Q T)习题1.41.(1)原式( P Q) (( P Q) (Q P))( P Q) (Q P)(P Q) Q PQ P,既是析取范式又是合取范式(2)原式(( P Q) ( P Q)) ( ( P Q) ( P Q))(P Q) (P Q) 析取范式P (Q Q)合取范式(3)原式P Q S ( P Q)析取范式( P ( P Q)) Q SP Q S合取范式(4)原式P P Q Q R既是析取范式又是合取范式2.(1)原式P Q R为真的解释是：000，001，011，100，101，110，111故原式的主析取范式为:( P Q R) ( P Q R) ( P Q R) (P Q R) (P QR) (P Q R) (P Q R)(2)原式(P Q) R(P Q (R R)) ((P P) R)(P Q R) (P Q R) (P Q) ( P R)(P Q R) (P Q R) (P (Q Q) 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)为真的解释是101，100，111，011，001(3)原式( P (Q R)) (P ( Q R))(( P (Q R)) P) (( P (Q R)) ( Q R))( P P) (Q P R) ( P Q R) (Q R Q R)(P Q R) ( P Q R)为真的解释是：000,111(4)原式P P Q Q R P Q R为真的解释是：001，010，011，100，101，110，111故原式的主析取范式为：( P Q R) ( P Q R) ( P Q R) (P Q R) (P QR) (P Q R) (P Q R)3.(1)原式P Q P Q T主合取范式，无为假的解释。
离散数学是数学的一个重要分支，研究的是离散结构和离散对象的性质。
代数系统和布尔代数是离散数学中的两个重要概念。
代数系统是研究集合上的运算的一种数学结构。
它由集合和一组运算所组成，其中运算可以是两个对象相互运算得到一个新的对象，也可以是一个对象自身经过某种运算得到一个新的对象。
代数系统包括了很多种类，例如群、环、域等等。
其中，布尔代数是代数系统的一种重要类型。
布尔代数是一种二元代数系统，它研究的是关于真值和逻辑运算的代数。
在布尔代数中，我们考虑的对象是命题，而运算包括了与、或、非等等。
布尔代数主要用于逻辑运算和电路设计中。
布尔代数中的命题可以用真和假来表示，它们分别对应于数学中的1和0。
与、或、非等运算在布尔代数中也有对应的符号，分别是∧、∨、¬。
这些符号在逻辑运算中扮演重要角色。
布尔代数的运算有很多有趣的性质。
比如，与运算满足交换律、结合律、分配律等等；或运算满足交换律、结合律、分配律等等；非运算满足逆运算和恒等律。
这些性质使得布尔代数具有很强的推理和运算能力。
布尔代数在逻辑运算中有着广泛的应用。
在计算机科学中，布尔代数被用于电路设计和逻辑推理；在人工智能领域，布尔代数被用于知识表示和推理；在运筹学中，布尔代数被用于约束求解和优化问题。
布尔代数的应用广泛而深入，是离散数学中的重要工具之一。
总结起来，离散数学中的代数系统和布尔代数是两个重要的概念。
代数系统研究的是集合上的运算，而布尔代数研究的是关于真值和逻辑运算的代数。
布尔代数具有许多有趣的性质和广泛的应用，是离散数学中的一个重要工具。
离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科，它研究离散对象及其关系、结构和运算方法。
离散数学的应用非常广泛，包括计算机科学、信息科学、密码学、人工智能等领域。
而离散数学第2版是一本经典的教材，它系统地介绍了离散数学的基本概念、原理和方法。
本文将为读者提供离散数学第2版课后习题的答案，帮助读者更好地理解和掌握离散数学的知识。
第一章：基本概念和原理1.1 命题逻辑习题1：命题逻辑的基本符号有哪些？它们的含义是什么？答：命题逻辑的基本符号包括命题变量、命题联结词和括号。
命题变量用字母表示，代表一个命题。
命题联结词包括否定、合取、析取、条件和双条件等，分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。
括号用于改变命题联结词的优先级。
习题2：列举命题逻辑的基本定律。
答：命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。
1.2 集合论习题1：什么是集合？集合的基本运算有哪些？答：集合是由一些确定的对象组成的整体，这些对象称为集合的元素。
集合的基本运算包括并、交、差和补等。
习题2：列举集合的基本定律。
答：集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。
第二章：数理逻辑2.1 命题逻辑的推理习题1：什么是命题逻辑的推理规则？列举几个常用的推理规则。
答：命题逻辑的推理规则是用来推导命题的逻辑规则。
常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。
习题2：使用推理规则证明以下命题：如果A成立，则B成立；B不成立，则A不成立。
答：假言推理规则可以用来证明该命题。
根据假言推理规则，如果A成立，则B成立。
又根据假言推理规则，如果B不成立，则A不成立。
2.2 谓词逻辑习题1：什么是谓词逻辑？它与命题逻辑有何区别？答：谓词逻辑是一种扩展了命题逻辑的逻辑系统，它引入了谓词和量词。
与命题逻辑不同，谓词逻辑可以对个体进行量化和描述。
离散数学第3版习题答案离散数学是一门重要的数学学科，它研究的是离散对象和离散结构的数学理论。
离散数学的应用广泛，涉及到计算机科学、信息技术、通信工程等领域。
在学习离散数学的过程中，习题是不可或缺的一部分，通过解答习题可以加深对知识的理解和掌握。
本文将为大家提供《离散数学第3版》习题的答案，希望能对学习者有所帮助。
第一章：命题逻辑1.1 习题答案：1. (a) 真值表如下：p | q | p ∧ qT | T | TT | F | FF | T | FF | F | F(b) 命题“p ∧ q”的真值表如下：p | q | p ∧ qT | T | TT | F | FF | T | FF | F | F(c) 命题“p ∨ q”的真值表如下：p | q | p ∨ qT | T | TT | F | TF | T | TF | F | F(d) 命题“p → q”的真值表如下：p | q | p → qT | T | TT | F | FF | T | TF | F | T1.2 习题答案：1. (a) 命题“¬(p ∧ q)”等价于“¬p ∨ ¬q”。
(b) 命题“¬(p ∨ q)”等价于“¬p ∧ ¬q”。
(c) 命题“¬(p → q)”等价于“p ∧ ¬q”。
(d) 命题“¬(p ↔ q)”等价于“(p ∧ ¬q) ∨ (¬p ∧ q)”。
1.3 习题答案：1. (a) 命题“p → q”的否定是“p ∧ ¬q”。
(b) 命题“p ∧ q”的否定是“¬p ∨ ¬q”。
(c) 命题“p ↔ q”的否定是“(p ∧ ¬q) ∨ (¬p ∧ q)”。
(d) 命题“p ∨ q”的否定是“¬p ∧ ¬q”。
1.4 习题答案：1. (a) 命题“p → q”与命题“¬p ∨ q”等价。
离散数学第二版最全课后习题答案详解离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、电气工程等领域都有着广泛的应用。
对于学习离散数学的同学们来说，课后习题的解答是巩固知识、加深理解的重要环节。
本文将为您提供离散数学第二版的最全课后习题答案详解，希望能对您的学习有所帮助。
在开始讲解具体的习题答案之前，让我们先简要回顾一下离散数学的主要内容。
离散数学包括集合论、数理逻辑、图论、代数结构等几个部分。
集合论是离散数学的基础，它研究集合的性质、运算和关系。
在集合论的习题中，常见的问题包括集合的表示、集合的运算（并集、交集、补集等）、集合的包含关系以及集合的基数等。
例如，有这样一道习题：设集合 A ＝｛1, 2, 3}，B ＝｛2, 3, 4}，求 A ∪ B 和A ∩ B。
答案是：A ∪ B ＝｛1, 2, 3, 4}，A ∩ B ＝｛2, 3}。
这是因为并集是包含两个集合中所有元素的集合，而交集是同时属于两个集合的元素组成的集合。
数理逻辑是研究推理和证明的工具，它包括命题逻辑和谓词逻辑。
在数理逻辑的习题中，需要掌握命题的符号化、逻辑公式的等价变换、推理规则的应用等。
比如，给出这样一个命题：“如果今天下雨，那么我就不去公园”，将其符号化。
我们可以设“今天下雨”为 P，“我去公园”为 Q，那么这个命题可以符号化为P → ¬Q。
图论是研究图的性质和应用的分支。
图的概念在计算机网络、交通运输等领域有着重要的应用。
图论的习题常常涉及图的表示、顶点的度、路径、连通性、图的着色等问题。
假设有这样一道题：一个无向图有 10 个顶点，每个顶点的度都为 6，求这个图的边数。
根据顶点度数之和等于边数的两倍这个定理，我们可以计算出边数为 30。
代数结构则包括群、环、域等概念，在这部分的习题中，需要理解和运用代数结构的定义和性质来解决问题。
接下来，我们具体来看一些习题的详细解答。
例 1：设集合 A ＝｛x ｜ x 是小于 10 的正奇数}，B ＝｛x ｜ x 是小于 10 的正偶数}，求 A B。
《离散数学》题库及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答：（1），（4）2、下列公式中哪些是永真式？()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P答：（2），（3），（4），（5），（6）4、公式某((A(某)B(y，某))zC(y，z))D(某)中，自由变元是(变元是()。
答：某,y,某,z5、判断下列语句是不是命题。
若是，给出命题的真值。
((1)北京是中华人民共和国的首都。
(2)陕西师大是一座工厂。
)，约束)(3)你喜欢唱歌吗？(4)若7+8＞18，则三角形有4条边。
(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()。
答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为()。
(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：（1）QP（2）PQ（3）PQ（4）PQ8、设个体域为整数集，则下列公式的意义是()。
(1)某y(某+y=0)(2)y某(某+y=0)答：（1）对任一整数某存在整数y满足某+y=0（2）存在整数y对任一整数某满足某+y=09、设全体域D是正整数集合，确定下列命题的真值：(1)某y(某y=y)()(2)某y(某+y=y)()(3)某y(某+y=某)()(4)某y(y=2某)()答：（1）F（2）F（3）F（4）T10、设谓词P(某)：某是奇数，Q(某)：某是偶数，谓词公式某(P(某)Q(某))在哪个个体域中为真()2(1)自然数(2)实数(3)复数(4)(1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。
离散数学课后习题答案离散数学课后习题答案离散数学是计算机科学中的一门重要课程，它涵盖了诸多数学概念与技巧，为计算机科学的理论基础打下了坚实的基础。
在学习离散数学的过程中，课后习题是巩固知识、提高能力的重要途径。
然而，有时候我们会遇到一些难以解答的问题，需要参考一些答案来进行思考与学习。
本文将为大家提供一些离散数学课后习题的答案，希望能对大家的学习有所帮助。
一、集合论1. 设A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。
答案：A∪B={1,2,3,4}，A∩B={2,3}。
2. 证明：任意集合A和B，有(A-B)∪(B-A)=(A∪B)-(A∩B)。
答案：首先，对于任意元素x，如果x属于(A-B)∪(B-A)，那么x属于A-B或者x属于B-A。
如果x属于A-B，那么x属于A∪B，但x不属于A∩B；如果x属于B-A，同样有x属于A∪B，但x不属于A∩B。
所以(A-B)∪(B-A)属于(A∪B)-(A∩B)。
另一方面，对于任意元素x，如果x属于(A∪B)-(A∩B)，那么x属于A∪B，但x不属于A∩B。
所以x属于A或者x属于B。
如果x属于A，但x不属于B，那么x属于A-B；如果x属于B，但x不属于A，那么x属于B-A。
所以x属于(A-B)∪(B-A)。
所以(A∪B)-(A∩B)属于(A-B)∪(B-A)。
综上所述，(A-B)∪(B-A)=(A∪B)-(A∩B)。
证毕。
二、逻辑与证明1. 证明：如果p为真命题，那么¬p为假命题。
答案：根据命题的定义，命题要么为真，要么为假，不存在其他情况。
所以如果p为真命题，那么¬p为假命题。
2. 证明：对于任意整数n，如果n^2为偶数，则n为偶数。
答案：假设n为奇数，即n=2k+1（k为整数）。
那么n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1。
根据偶数的定义，2(2k^2+2k)为偶数，所以n^2为奇数。
离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨(q∧r)⇔0∨(0∧1)⇔0（2）（p?r）∧(﹁q∨s)⇔（0?1）∧(1∨1)⇔0∧1⇔0.（3）（⌝(4)（176能被2q:3r:2s:619（4）(p（5）(p（6）((p答：（pqp→q⌝0011111011011110010011110011所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1)⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)⇔(⌝p∨(p∨q))∨(⌝p∨r)⇔⌝p∨p∨q∨r⇔1所以公式类型为永真式(3)P qrp∨qp∧r（p∨q）→(p∧r)0000010010014.(2)(p→(4)(p∧证明（2（45.(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(⌝p→q)→(⌝q∨p)⇔⌝(p∨q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∧p)∨(⌝q∧⌝p)∨(p∧q)∨(p∧⌝q)⇔(⌝p∧⌝q)∨(p∧⌝q)∨(p∧q)⇔∑(0,2,3)主合取范式：(⌝p→q)→(⌝q∨p)⇔⌝(p∨q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∨p)⇔(⌝p⇔1∧(p⇔(p∨⇔∏(2)⌝(p→q)⇔(p∧(3)⇔⌝⇔1∧1⇔1所以该式为永真式.永真式的主合取范式为1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14.在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：（2）①⌝(q∧r)前提引入②⌝q∨⌝r①置换③q→⌝r②蕴含等值式④r⑤⌝q⑥p→q⑦￢p（3证明（4①t②t③q④s⑤q⑥（⑦（⑧q⑨q⑩p15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明①s附加前提引入②s→p前提引入③p①②假言推理④p→(q→r)前提引入⑤q→r③④假言推理⑥q前提引入⑦r⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p证明：①p②p③﹁④￢⑤￢⑥r⑦r⑧r3.:(1)均有2=(x+)(x).(2)其中(a)(b)解：F(x):2=(x+)(x).G(x):x+5=9.(1)在两个个体域中都解释为)(x∀，在（a）中为假命题，在(b)中为真命题。
1.1．略1.2．略1.3．略1.4．略1.5．略1.6．略1.7．略1.8．略1.9．略1.10．略1.11．略1.12．将下列命题符号化,并给出各命题的真值:<1>2+2＝4当且仅当3+3＝6.<2>2+2＝4的充要条件是3+3≠6.<3>2+2≠4与3+3＝6互为充要条件.<4>若2+2≠4, 则3+3≠6,反之亦然.<1>p↔q,其中,p: 2+2＝4,q: 3+3＝6, 真值为1.<2>p↔⌝q,其中,p:2+2＝4,q:3+3＝6,真值为0.<3>⌝p↔q,其中,p:2+2＝4,q:3+3＝6,真值为0.<4>⌝p↔⌝q,其中,p:2+2＝4,q:3+3＝6,真值为1.1.13．将下列命题符号化, 并给出各命题的真值:<1>若今天是星期一,则明天是星期二.<2>只有今天是星期一,明天才是星期二.<3>今天是星期一当且仅当明天是星期二. <4>若今天是星期一,则明天是星期三.令p: 今天是星期一;q:明天是星期二;r:明天是星期三.<1>p→q ⇔ 1.<2> q→p ⇔ 1.<3> p↔q⇔ 1.<4>p→r当p ⇔ 0时为真; p ⇔ 1时为假.1.14．将下列命题符号化. <1>刘晓月跑得快,跳得高.<2>老王是XX人或XX人.<3>因为天气冷, 所以我穿了羽绒服. <4>王欢与李乐组成一个小组.<5>李辛与李末是兄弟.<6>王强与刘威都学过法语. <7>他一面吃饭, 一面听音乐. <8>如果天下大雨,他就乘班车上班.<9>只有天下大雨,他才乘班车上班.<10>除非天下大雨,他才乘班车上班.<11>下雪路滑, 他迟到了.<12>2与4都是素数,这是不对的.<13>"2或4是素数,这是不对的"是不对的.<1>p∧q,其中, p:刘晓月跑得快, q: 刘晓月跳得高.<2>p∨q,其中, p:老王是XX人, q: 老王是XX 人.<3>p→q, 其中,p:天气冷, q:我穿了羽绒服.<4>p, 其中,p:王欢与李乐组成一个小组,是简单命题.<5>p, 其中,p:李辛与李末是兄弟.<6>p∧q,其中, p:王强学过法语, q: 刘威学过法语.<7>p∧q,其中, p:他吃饭,q:他听音乐.<8>p→q, 其中,p:天下大雨, q:他乘班车上班.<9>p→q, 其中,p:他乘班车上班, q: 天下大雨.<10>p→q, 其中,p: 他乘班车上班,q:天下大雨.<11>p→q, 其中,p: 下雪路滑, q:他迟到了.12>⌝ <p∧q>或⌝p∨⌝q,其中,p:2是素数,q:4是素数.<13>⌝⌝ <p∨q>或p∨q,其中,p:2 是素数,q:4是素数.1.15．设p:2+3=5.q: 大熊猫产在中国.r: 复旦大学在XX.求下列复合命题的真值:<1><p↔q>→r<2><r→ <p∧q>>↔ ⌝p<3>⌝r→ <⌝p∨⌝q∨r><4><p∧q∧⌝r>↔ <<⌝p∨⌝q>→r><1>真值为0.<2>真值为0.<3>真值为0.<4>真值为1.注意:p, q是真命题,r是假命题.1.16．略1.17．略1.18．略1.19．用真值表判断下列公式的类型:<1>p→ <p∨q∨r><2><p→⌝q>→⌝q<3>⌝ <q→r>∧r<4><p→q>→ <⌝q→⌝p><5><p∧r>↔ <⌝p∧⌝q><6><<p→q>∧ <q→r>>→ <p→r><7><p→q> ↔ <r↔s><1>, <4>,<6>为重言式.<3>为矛盾式.<2>, <5>,<7>为可满足式.1.20．略1.21．略1.22．略1.23．略1.24．略1.25．略1.26．略1.27．略1.28．略1.29．略1.30．略1.31．将下列命题符号化,并给出各命题的真值:<1>若3+＝4,则地球是静止不动的.<2>若3+2＝4,则地球是运动不止的. <3>若地球上没有树木,则人类不能生存.<4>若地球上没有水,则3是无理数.<1>p→q,其中, p: 2+2＝4,q:地球静止不动,真值为0.<2>p→q,其中, p: 2+2＝4,q:地球运动不止,真值为1.<3>⌝p→⌝q,其中,p:地球上有树木,q:人类能生存,真值为1.<4>⌝p→q,其中,p:地球上有水,q: 3 是无理数,真值为1.习题二2.1.设公式A=p→q,B=p⌝∧q,用真值表验证公式A和B适合德摩根律:⌝<A∨B>⇔ ⌝A⌝∧B.p q A =p→q B=p⌝∧q⌝<A∨B>⌝A⌝∧B0 0 1 0 0 00 1 1 0 0 01 0 0 1 0 01 1 1 0 0 0因为⌝<A∨B>和⌝A⌝∧B的真值表相同,所以它们等值.2.2. 略2.3. 用等值演算法判断下列公式的类型, 对不是重言式的可满足式,再用真值表法求出成真赋值.<1>⌝ <p∧q→q><2><p→ <p∨q>>∨ <p→r><3><p∨q>→ <p∧r><1>⌝ <p∧q→q>⇔ ⌝ <⌝<p∧q>∨ q>⇔ ⌝ <⌝p∨ ⌝q∨ q>⇔ p∧q∧⌝q⇔ p∧0⇔ 0⇔ 0.矛盾式.<2>重言式.<3> <p∨q>→ <p∧r>⇔ ⌝<p∨q>∨ <p∧r>⇔ ⌝p⌝∧q∨ p∧r易见,是可满足式,但不是重言式.成真赋值为:000,001, 101, 111p q r←p∍ ←q(p∍r0 0 0 1 1 1 1 00 0 1 1 1 1 1 00 1 0 1 0 0 0 00 1 1 1 0 0 0 01 0 0 0 0 1 0 01 0 1 0 0 1 1 11 1 0 0 0 0 0 01 1 1 0 0 0 1 12.4.用等值演算法证明下面等值式:<1>p⇔ <p∧q>∨ <p∧⌝q><3>⌝ <p↔q>⇔ <p∨q>∧⌝ <p∧q><4><p∧⌝q>∨ <⌝p∧q>⇔ <p∨q>∧⌝ <p∧q><1><p∧q>∨ <p∧⌝q>⇔ p∧ <q⌝∨q>⇔ p∧ 1⇔ p.<3>⌝<p↔q>⇔⌝ <<p→q>∧ <q→p>>⇔⌝ <<⌝p∨q>∧ <⌝q∨p>>⇔ <p∧⌝q>∨ <q∧⌝p>⇔ <p∨q>∧ <p∨⌝p>∧ <⌝q∨q>∧ <⌝p∨⌝q>⇔ <p∨q> ∧⌝ <p∧q><4><p∧⌝q>∨ <⌝p∧q>⇔ <p∨⌝p>∧ <p∨q>∧ <⌝q∨⌝p>∧ <⌝q∨q>⇔ <p∨q> ∧⌝ <p∧q>2.5.求下列公式的主析取范式,并求成真赋值:<1><⌝p→q>→ <⌝q∨p><2>⌝ <p→q>∧q∧r<3><p∨ <q∧r>> → <p∨q∨r><1><⌝p→q>→ <⌝q∨p>⇔ ⌝<p∨q> ∨ <⌝q∨p>⇔ ⌝p∧⌝q∨ ⌝q∨ p⇔ ⌝p∧⌝q∨ ⌝q∨ p<吸收律>⇔ <p⌝∨p>⌝∧q∨ p∧<q⌝∨q>⇔ p⌝∧q⌝∨p⌝∧q∨ p∧q∨ p⌝∧q⇔ m10∨ m00∨ m11∨ m10⇔ m0∨ m2∨ m3⇔ ∑<0, 2,3>.成真赋值为00,10, 11.<2>主析取范式为0, 无成真赋值,为矛盾式.<3>m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7,为重言式.2.6. 求下列公式的主合取范式, 并求成假赋值:<1>⌝ <q→⌝p>∧⌝p<2><p∧q>∨ <⌝p∨r><3><p→ <p∨q>>∨r<1> ⌝ <q⌝→p>∧ ⌝p⇔ ⌝<⌝q⌝∨p>∧ ⌝p⇔ q∧p∧ ⌝p⇔ q∧0⇔ 0⇔ M0∧M1∧M2∧M3这是矛盾式.成假赋值为00, 01,10,11.<2>M4,成假赋值为100.<3>主合取范式为1, 为重言式.2.7.求下列公式的主析取范式,再用主析取范式求合取范式:<1><p∧q> ∨r<2><p→q> ∧ <q→r><1>m1∨m3∨m5∨m6∨m7⇔M0∧M2∧M4<2>m0∨m1∨m3∨m7⇔M2∧M4∧M5∧M62.8. 略2.9. 用真值表求下面公式的主析取范式.<2><p→q>→ <p⌝↔q>p q<p q> <p← q>0 0 1 0 0 10 1 1 1 1 01 0 0 1 1 11 1 1 0 0 0<2>从真值表可见成真赋值为01,10.于是<p→ q>→ <p⌝ ↔ q>⇔ m1∨ m2.2.10.略2.11.略2.12.略2.13.略2.14.略2.15. 用主析取范式判断下列公式是否等值:<1> <p→q> →r与q→ <p→r><2><p→q> →r⇔ ⌝<⌝p∨q>∨ r⇔ ⌝<⌝p∨q>∨ r⇔ p⌝∧q∨ r⇔ p⌝∧q∧<r⌝∨r>∨ <p⌝∨p>∧ <q⌝∨q>∧r⇔ p⌝∧q∧r∨ p⌝∧q∧⌝r∨p∧q∧r∨ p∧⌝q∧r∨ ⌝p∧q∧r∨ ⌝p∧⌝q∧r= m101∨ m100∨ m111∨ m101∨ m011∨ m001⇔ m1∨ m3∨ m4∨ m5∨ m7= ∑<1,3,4,5,7>.而q→<p→r>⇔ ⌝q∨ <⌝p∨r>⇔ ⌝q∨ ⌝p∨r⇔ <⌝p∨p>⌝∧q∧<⌝r∨r>∨ ⌝p∧<⌝q∨q>∧<⌝r∨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>= m0∨ m1∨ m4∨ m5∨ m0∨ m1∨ m2∨ m3∨ m1∨ m3∨ m5∨ m7⇔ m0∨ m1∨ m2∨ m3∨ m4∨ m5∨ m7⇔ ∑<0,1,2,3,4,5,7>.两个公式的主吸取范式不同,所以<p→q>→rœq→ <p→r>.2.16.用主析取范式判断下列公式是否等值:<1><p→q>→r与q→ <p→r><2>⌝ <p∧q>与⌝ <p∨q><1><p→q>→r> ⇔m1∨m3∨m4∨m5∨m7q→ <p→r>⇔m0∨m1∨m2∨m3∨m4∨m5∨m7所以<p→q>→r>œq→ <p→r><2>⌝ <p∧q>⇔m0∨m1∨m2⌝ <p∨q>⇔m0所以⌝ <p∧q>œ⌝ <p∨q>2.17.用主合取范式判断下列公式是否等值:<1>p→ <q→r>与⌝ <p∧q>∨r<2>p→ <q→r>与<p→q>→r<1>p→ <q→r>⇔M6⌝ <p∧q>∨r⇔M6所以p→ <q→r>⇔ ⌝ <p∧q>∨r<2>p→ <q→r>⇔M6<p→q>→r⇔M0∧M1∧M2∧M6所以p→ <q→r>œ<p→q>→r2.18.略2.19.略2.20.将下列公式化成与之等值且仅含{⌝,→}中联结词的公式.<3> <p∧q>↔r.注意到A↔B⇔ <A→B>∧<B→A>和A∧B⇔ ⌝<⌝A⌝∨B>⇔ ⌝<A⌝→B>以及A∨B⇔ ⌝A→B.<p∧q>↔r⇔ <p∧q → r> ∧ <r → p∧q>⇔ <⌝<p⌝→q>→ r>∧ <r→ ⌝<p⌝→q>>⇔ ⌝<<⌝<p⌝→q>→ r>→ ⌝<r→ ⌝<p⌝→q>>>注 联结词越少,公式越长.2.21.证明:<1> <p↑q>⇔ <q↑p>,<p↓q>⇔ <q↓p>.<p↑q>⇔ ⌝<p∧q>⇔ ⌝<q∧p>⇔ <q↑p>.<p↓q>⇔ ⌝<p∨q>⇔ ⌝<q∨p>⇔ <q↓p>.2.22.略2.23.略2.24.略2.25.设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=q,C = 1 <重言式>, 有A∨C⇔ B∨C,但AœB.<2>取A=p,B=q,C = 0 <矛盾式>, 有A∧C⇔ B∧C,但AœB.好的例子是简单,具体,而又说明问题的.<3>一定.2.26.略2.27.某电路中有一个灯泡和三个开关A,B,C.已知在且仅在下述四种情况下灯亮:<1>C的扳键向上, A,B的扳键向下.<2>A的扳键向上, B,C的扳键向下.<3>B,C的扳键向上,A的扳键向下.<4>A,B的扳键向上,C的扳键向下.设F为1表示灯亮,p,q,r分别表示A,B,C的扳键向上.<a>求F的主析取范式.<b>在联结词完备集{⌝,∧}上构造F.<c>在联结词完备集{⌝,→,↔}上构造F.<a>由条件<1>-<4>可知, F的主析取范式为F⇔ <⌝p∧⌝q∧r>∨ <p∧⌝q∧⌝r>∨ <⌝p∧q∧r>∨ <p∧q∧⌝r>⇔m1∨m4∨m3∨m6⇔m1∨m3∨m4∨m6<b>先化简公式F⇔ <⌝p∧⌝q∧r>∨ <p∧⌝q∧⌝r>∨ <⌝p∧q∧r>∨ <p∧q∧⌝r>⇔⌝q∧ <<⌝p∧r>∨ <p∧⌝r>>∨q∧ <<⌝p∧r>∨ <p∧⌝r>>⇔ <⌝q∨q>∧ <<⌝p∧r>∨ <p∧⌝r>>⇔ <⌝p∧r>∨ <p∧⌝r>⇔⌝ <⌝ <⌝p∧r>∧⌝ <p∧⌝r>><已为{⌝,∧}中公式><c>F⇔ <⌝p∧r>∨ <p∧⌝r>⇔⌝⌝ <⌝p∧r>∨ <p∧⌝r>⇔⌝ <⌝p∧r>→ <p∧⌝r>⇔ <p∨⌝r>→⌝ <⌝p∨r>⇔ <r→p>→⌝ <p→r> <已为{⌝,→,↔}中公式>2.28.一个排队线路, 输入为A,B,C,其输出分别为F A,F B,F C.本线路中,在同一时间内只能有一个信号通过,若同时有两个和两个以上信号申请输出时,则按A,B,C的顺序输出.写出F A,F B,F C在联结词完备集{⌝,∨}中的表达式.根据题目中的要求,先写出F A,F B,F C的真值表<自己写>由真值表可先求出他们的主析取范式,然后化成{⌝,∧}中的公式F A⇔m4∨m5∨m6∨m7⇔p <已为{⌝,∧}中公式>F B⇔m2∨m3⇔⌝p∧q <已为{⌝,∧}中公式>F C⇔m1⇔⌝p∧⌝q∧r <已为{⌝,∧}中公式>2.29.略2.30.略习题三3.1.略3.2.略3.3.略3.4.略3.5.略3.6.判断下面推理是否正确.先将简单命题符号化,再写出前提,结论, 推理的形式结构<以蕴涵式的形式给出>和判断过程<至少给出两种判断方法>:<1>若今天是星期一,则明天是星期三；今天是星期一.所以明天是星期三.<2>若今天是星期一,则明天是星期二；明天是星期二.所以今天是星期一.<3>若今天是星期一,则明天是星期三；明天不是星期三.所以今天不是星期一.<4>若今天是星期一,则明天是星期二；今天不是星期一.所以明天不是星期二.<5>若今天是星期一,则明天是星期二或星期三.<6>今天是星期一当且仅当明天是星期三；今天不是星期一.所以明天不是星期三.设p: 今天是星期一,q:明天是星期二,r:明天是星期三.<1>推理的形式结构为<p→r>∧p→r此形式结构为重言式,即<p→r>∧p⇒r所以推理正确. <2>推理的形式结构为<p→q>∧q→p 此形式结构不是重言式,故推理不正确.<3>推理形式结构为<p→r>∧⌝r→⌝p此形式结构为重言式,即<p→r>∧⌝r⇒⌝p故推理正确. <4>推理形式结构为<p→q>∧⌝p→⌝q此形式结构不是重言式, 故推理不正确.<5>推理形式结构为p→ <q∨r>它不是重言式, 故推理不正确. <6>推理形式结构为<p⇒r>∧⌝p→⌝r.此形式结构为重言式,即<p⇒r>∧⌝p⇒⌝r故推理正确.推理是否正确, 可用多种方法证明.证明的方法有真值表法,等式演算法.证明推理正确还可用构造证明法.下面用构造证明法证明<6>推理正确.前提:p⇒r,⌝p结论:⌝r证明:①p⇒r 前提引入②<p→r>∧ <r→p> ①置换③r→p ②化简律④⌝p 前提引入⑤⌝r ③④拒取式所以,推理正确.3.7.略3.8.略3.9.用三种方法<真值表法,等值演算法,主析取范式法>证明下面推理是正确的:若a 是奇数,则a 不能被2 整除.若a 是偶数,则a 能被2 整除.因此,如果a是偶数, 则a不是奇数.令p: a是奇数;q:a 能被2 整除; r:a是偶数.前提:p→ ⌝q,r→ q.结论:r→ ⌝p.形式结构:<p→ ⌝q>∧ <r→ q>→ <r→ ⌝p>.……3.10.略3.11.略3.12.略3.13.略3.14.在自然推理系统P中构造下面推理的证明:<1>前提: p→ <q→r>,p, q结论: r∨s<2>前提:p→q,⌝ <q∧r>,r结论:⌝p<3>前提: p→q结论: p→ <p∧q><4>前提: q→p, q⇒s,s⇒t,t∧r结论: p∧q<5>前提: p→r,q→s,p∧q.结论: r∧s<6>前提:⌝p∨r,⌝q∨s,p∧q结论:t→ <r∨s><1>证明:①②p→<q→r>p前提引入前提引入③④q→rq①②假言推理前提引入⑤r③④假言推理⑥r∨s⑤附加律<2>证明:①②③⌝ <q∧r>⌝q∨⌝rr前提引入①置换前提引入④⑤⑥⌝qp→q⌝p②③析取三段论前提引入④⑤拒取式<3>证明:①p→q前提引入②⌝p∨q①置换③<⌝p∨q>∧ <⌝p∨p>②置换④⌝p∨ <p∧q>③置换⑤p→ <p∧q> ④置换也可以用附加前提证明法,更简单些.<4>证明:①②③④⑤s⇒t<s→t> ∧ <t→s>t→st∧rt前提引入①置换②化简前提引入④化简⑥s③⑤假言推理⑦⑧⑨⑩q⇒s<s→q>∧ <q→s>s→qq前提引入⑦置换⑧化简⑥⑥假言推理○11 q →p前提引入○12 ○13 pp∧q⑩○11 假言推理⑩○12 合取<5>证明:①②p→rq→s前提引入前提引入③④p∧qp前提引入③化简⑤q③化简⑥r①④假言推理⑦s②⑤假言推理⑧r∧s⑥⑦合取<6>证明:①②t⌝p∨r附加前提引入前提引入③④p∧qp前提引入③化简⑤r②④析取三段论⑥r∨s⑤附加说明:证明中,附加提前t,前提⌝q∨s没用上.这仍是正确的推理.3.15.在自然推理系统P中用附加前提法证明下面各推理:<1>前提: p→ <q→r>,s→p,q结论: s→r<2>前提: <p∨q> → <r∧s>,<s∨t>→u结论: p→u<1>证明:①②ss→p附加前提引入前提引入③p①②假言推理④⑤⑥p→ <q→r>q→rq前提引入③④假言推理前提引入⑦r⑤⑥假言推理<2>证明:①②Pp∨q附加前提引入①附加③<p∨q> → <r∧s> 前提引入④⑤r∧sS②③假言推理④化简⑥⑦⑧s∨t<s∨t>→uu⑤附加前提引入⑥⑦假言推理3.16.在自然推理系统P中用归谬法证明下面推理:<1>前提:p→⌝q,⌝r∨q,r∧⌝s结论:⌝p<2>前提: p∨q,p→r,q→s结论: r∨s<1>证明:①②Pp→⌝q结论否定引入前提引入③④⑤⑥⑦⌝q⌝r∨q⌝rr∧⌝sr①②假言推理前提引入③④析取三段论前提引入⑥化简⑧⌝r∧r⑤⑦合取⑧为矛盾式,由归谬法可知, 推理正确.<2>证明:①⌝ <r∨s>结论否定引入②p∨q前提引入③p→r前提引入④q→s前提引入⑤r∨s②③④构造性二难⑥⌝ <r∨s>∧ <r∨s>①⑤合取① ② ③ ④ ⑤ ⑥ ⑦ pp q (rq (rss ←q←qr ①②假言推理 前提引入 前提引入⑥为矛盾式,所以推理正确.3.17.P53 17. 在自然推理系统P 中构造下面推理的证明:只要A 曾到过受害者房间并且11点以前没用离开,A 就犯了谋杀罪.A 曾到过受害者房间.如果A 在 11点以前离开, 看门人会看到他.看门人没有看到他.所以A 犯了谋杀罪.令p :A 曾到过受害者房间;q :A 在11点以前离开了; r : A 就犯了谋杀罪;s :看门人看到A.前提:p ⌝∧q → r ,p ,q → s ,⌝s.结论:r .前提:p ⌝∧q → r ,p ,q → s ,⌝s;结论:r . 证明:①⌝s前提引入 ②q → s前提引入 ③⌝q①②拒取 ④p前提引入 ⑤p ⌝∧q③④合取 ⑥p ⌝∧q → r前提引入 ⑦r ⑤⑥假言推理3.18.在自然推理系统P 中构造下面推理的证明. <1>如果今天是星期六,我们就要到颐和园或圆明园去玩.如果颐和园游人太多,我们就不去颐和园玩.今天是星期六. 颐和园游人太多.所以我们去圆明园玩.<2>如果小王是理科学生,他的数学成绩一定很好.如果小王不是文科生,他必是理科生.小王的数学成绩不好.所以小王是文科学生.<3>明天是晴天, 或是雨天；若明天是晴天,我就去看电影；若我看电影,我就不看书.所以,如果我看书,则明天是雨天.<1>令p : 今天是星期六;q :我们要到颐和园玩;r :我们要到圆明园玩;s :颐和园游人太多.前提:p → <q ∨r >,s → ⌝q ,p ,s.结论:r .前提引入前提引入 p p →q ∨rq ∨r s s → ⌝q ⌝q r ④⑤假言推理 <1>的证明树③⑥析取三段论① p →r前提引入 ② ⌝r前提引入 ③ ⌝p ①②拒取式 ④ ⌝q →p 前提引入 ⑤ q③④拒取式 <2>令p : 小王是理科生,q :小王是文科生,r :小王的数学成绩很好.前提:p →r ,⌝q →p ,⌝r结论:q证明:⌝q p →q ⌝p ⌝r →p <2> 的证明树 r <3>令p : 明天是晴天,q :明天是雨天,r :我看电影,s :我看书. 前提: p ∨q ,p →r ,r →⌝s 结论: s →q证明:① ② sr →⌝s附加前提引入 前提引入 ③ ⌝r①②拒取式 ④ p →r前提引入 ⑤ ⌝p③④拒取式 ⑥ p ∨q前提引入 ⑦ q ⑤⑥析取三段论习题四4.1.将下面命题用0元谓词符号化:<1>小王学过英语和法语. <2>除非李建是东北人,否则他一定怕冷.<1>令F<x>: x学过英语;F<x>: x学过法语; a:小王.符号化为F<a>∧F<b>.或进一步细分,令L<x,y>: x学过y;a:小王; b1: 英语;b2:法语.则符号化为L<a,b1>∧L<a,b2>.<2>令F<x>: x是东北人;G<x>: x怕冷; a:李建.符号化为⌝F<a>→G<a>或⌝G<a>→F<a>.或进一步细分,令H<x,y>: x是y 地方人;G<x>:x 怕冷;a:小王;b: 东北. 则符号化为⌝H<a,b>→G<a>或⌝G<a>→ H<a,b>.4.2.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为<a>,<b>时命题的真值:<1>凡有理数都能被2整除.<2>有的有理数能被2整除. 其中<a>个体域为有理数集合,<b>个体域为实数集合.<1><a>中, ∀xF<x>,其中,F<x>: x能被2整除, 真值为0.<b>中, ∀x<G<x> ∧F<x>>,其中, G<x>:x为有理数,F<x>同<a>中,真值为0.<2><a>中, ∃xF<x>,其中,F<x>: x能被2整除, 真值为1.<b>中, ∃x<G<x> ∧F<x>>, 其中,F<x>同<a>中,G<x>:x为有理数,真值为1.4.3.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为<a>,<b>时命题的真值:<1>对于任意的x,均有x2-2=<x+2><x- 2>.<2>存在x, 使得x+5=9.其中<a>个体域为自然数集合,<b>个体域为实数集合.<1><a>中,∀x<x2-2=<x+2><x- 2>>,真值为1.<b>中, ∀x<F<x>→ <x2-2=<x+2><x- 2>>>>, 其中,F<x>:x为实数,真值为1.<2><a>中,∃x<x+5=9>,真值为1.<b>中, ∃x<F<x> ∧ <x+5=9>>,其中,F<x>: x为实数,真值为1.4.4.在一阶逻辑中将下列命题符号化:<1>没有不能表示成分数的有理数. <2>在北京卖菜的人不全是外地人.<3>乌鸦都是黑色的. <4>有的人天天锻炼身体.没指定个体域, 因而使用全总个体域.<1>⌝∃x<F<x>∧⌝G<x>>或∀x<F<x>→G<x>>,其中,F<x>:x为有理数,G<x>:x能表示成分数.<2>⌝∀x<F<x>→G<x>>或∃x<F<x>∧⌝G<x>>,其中,F<x>:x在北京卖菜,G<x>:x是外地人.<3>∀x<F<x> →G<x>>,其中,F<x>: x是乌鸦,G<x>: x是黑色的.<4>∃x<F<x> ∧G<x>>,其中,F<x>:x是人,G<x>:x天天锻炼身体.4.5.在一阶逻辑中将下列命题符号化:<1>火车都比轮船快. <2>有的火车比有的汽车快. <3>不存在比所有火车都快的汽车. <4>"凡是汽车就比火车慢"是不对的.因为没指明个体域,因而使用全总个体域<1>∀x∀y<F<x> ∧G<y>→H<x,y>>,其中,F<x>: x是火车,G<y>:y是轮船,H<x,y>:x比y快.<2>∃x∃y<F<x> ∧G<y>∧H<x,y>>, 其中, F<x>:x是火车,G<y>:y是汽车,H<x,y>:x比y快.<3>⌝∃x<F<x>∧∀y<G<y>→H<x,y>>>或∀x<F<x>→∃y<G<y>∧⌝H<x,y>>>,其中,F<x>:x是汽车,G<y>:y是火车,H<x,y>:x比y快.<4>⌝∀x∀y<F<x>∧G<y>→H<x,y>>或∃x∃y<F<x>∧G<y>∧⌝H<x,y>>,其中,F<x>:x是汽车,G<y>:y是火车,H<x,y>:x比y慢. 4.6.略4.7.将下列各公式翻译成自然语言,个体域为整数集®,并判断各命题的真假.<1>∀x∀y∃z<x- y=z>;<2>∀x∃y<x⋅y =1>.<1>可选的翻译:①"任意两个整数的差是整数."②"对于任意两个整数,都存在第三个整数,它等于这两个整数相减."③"对于任意整数x和y,都存在整数z,使得x- y=z."选③,直接翻译,无需数理逻辑以外的知识.以下翻译意思相同, 都是错的:"有个整数,它是任意两个整数的差.""存在一个整数,对于任意两个整数,第一个整数都等于这两个整数相减."❶ "存在整数z,使得对于任意整数x 和y,都有x- y= z."这3个句子都可以符号化为∃z∀x∀y<x- y=z>.0量词顺序不可随意调换.<2>可选的翻译:①"每个整数都有一个倒数."②"对于每个整数,都能找到另一个整数,它们相乘结果是零."③"对于任意整数x,都存在整数y, 使得x⋅y =z."选③,是直接翻译,无需数理逻辑以外的知识.4.8.指出下列公式中的指导变元, 量词的辖域,各个体变项的自由出现和约束出现:<3>∀x∃y<F<x,y>∧ G<y,z>> ∨ ∃xH<x,y, z>∀x∃y<F<x,y>∧ G<y,z>>∨ ∃x H<x,y,z>前件∀x∃y<F<x,y>∧G<y,z>>中,∀ 的指导变元是x, ∀ 的辖域是∃y<F<x,y>∧G<y,z>>;∃ 的指导变元是y, ∃ 的辖域是<F<x,y>∧G<y,z>>.后件∃xH<x,y,z>中, ∃ 的指导变元是x, ∃ 的辖域是H<x,y,z>.整个公式中, x约束出现两次, y约束出现两次,自由出现一次;z 自由出现两次.4.9.给定解释I如下:<a>个体域D I为实数集合\.<b>D I中特定元素↓a=0.<c>特定函数↓f<x,y>=x-y,x,y∈D I.<d>特定谓词↓F<x,y>:x=y,↓G<x,y>:x<y,x,y∈D I.说明下列公式在I下的含义,并指出各公式的真值:<1>∀x∀y<G<x,y>→⌝F<x,y>><2> ∀x∀y<F<f<x,y>,a>→G<x,y>><3>∀x∀y<G<x,y>→⌝F<f<x,y>,a>><4> ∀x∀y<G<f<x,y>,a> →F<x,y>><1>∀x∀y<x<y→x≠y>,真值为1.<2>∀x∀y<<x-y=0> →x<y>, 真值为0.<3>∀x∀y<<x<y>→ <x-y≠0>>,真值为1.<4>∀x∀y<<x-y<0> → <x=y>>,真值为0.4.10.给定解释I如下:<a>个体域D=Æ<Æ为自然数>.<b>D中特定元素↓a=2.<c>D上函数↓f<x,y>=x+y,↓g<x,y>=x·y.<d>D上谓词↓F<x,y>:x=y.说明下列公式在I下的含义,并指出各公式的真值:<1> ∀xF<g<x,a>,x><2> ∀x∀y<F<f<x,a>,y> →F<f<y,a>,x>><3> ∀x∀y∃z<F<f<x,y>,z><4> ∃xF<f<x,x>,g<x,x>><1>∀x<x·2=x>,真值为0.<2>∀x∀y<<x+2=y> → <y+2=x>>,真值为0.<3>∀x∀y∃z<x+y=z>,真值为1.<4>∃x<x+x=x·x>,真值为1.4.11.判断下列各式的类型:<1> F<x,y> → <G<x,y>→ F<x,y>>.<3> ∀x∃yF<x,y>→ ∃x∀yF<x,y>.<5> ∀x∀y<F<x,y>→ F<y,x>>.<1> 是命题重言式p → <q → p>的代换实例,所以是永真式.<3> 在某些解释下为假<举例>, 在某些解释下为真<举例>, 所以是非永真式的可满足式.<5> 同<3>.4.12.P69 12. 设I 为一个任意的解释,在解释I 下,下面哪些公式一定是命题?<1> ∀xF<x,y>→ ∃yG<x,y>.<2> ∀x<F<x> → G<x>>∧ ∃y<F< y>∧ H< y>>.<3> ∀x<∀yF<x,y>→ ∃yG<x,y>>.<4> ∀x<F<x> ∧ G<x>> ∧ H< y>.<2>, <3>一定是命题,因为它们是闭式.4.13.略4.14.证明下面公式既不是永真式也不是矛盾式:<1> ∀x<F<x> →∃y<G<y> ∧H<x,y>>><2> ∀x∀y<F<x> ∧G<y>→H<x,y>><1> 取个体域为全总个体域.解释I1: F<x>:x为有理数,G<y>: y为整数,H<x,y>: x<y在I1下: ∀x<F<x>→∃y<G<y> ∧H<x,y>>>为真命题,所以该公式不是矛盾式.解释I2:F<x>,G<y>同I1,H<x,y>: y整除x.在I2下: ∀x<F<x>→∃y<G<y> ∧H<x,y>>>为假命题,所以该公式不是永真式.<2> 请读者给出不同解释,使其分别为成真和成假的命题即可.4.15.<1>给出一个非闭式的永真式.<2> 给出一个非闭式的永假式.<3> 给出一个非闭式的可满足式,但不是永真式.<1>F<x>∨ ⌝F<x>.<2>F<x>∧ ⌝F<x>.<3> ∀x<F<x,y>→ F<y,x>>.习题五5.1.略5.2.设个体域D={a,b,c}, 消去下列各式的量词:<1> ∀x∃y<F<x> ∧G<y>><2> ∀x∀y<F<x> ∨G<y>><3> ∀xF<x> →∀yG<y><4> ∀x<F<x,y>→∃yG<y>><1> ∀x∃y<F<x> ∧G<y>>⇔∀xF<x> ∧∃yG<y>⇔ <F<a>∧F<b>> ∧F<c>> ∧ <G<a>∨G<b>∨G<c>><2> ∀x∀y<F<x> ∨G<y>>⇔∀xF<x> ∨∀yG<y>⇔ <F<a>∧F<b> ∧F<c>>∨ <G<a> ∧G<b>∧G<c>><3> ∀xF<x> →∀yG<y>⇔ <F<a>∧F<b> ∧F<c>>→ <G<a>∧G<b>∧G<c>><4> ∀x<F<x,y>→∃yG<y>>⇔∃xF<x,y> →∃yG<y>⇔ <F<a,y> ∨F<b,y> ∨F<c,y>>→ <G<a>∨G<b> ∨G<c>>5.3.设个体域D={1,2},请给出两种不同的解释I1和I2,使得下面公式在I1下都是真命题,而在I2下都是假命题.<1> ∀x<F<x> →G<x>><2> ∃x<F<x> ∧G<x>><1>I1:F<x>:x≤2,G<x>:x≤3F<1>,F<2>,G<1>,G<2>均为真,所以∀x<F<x>→G<x>>⇔ <F<1> →G<1>∧ <F<2>→G<2>>为真.I2: F<x>同I1,G<x>:x≤0则F<1>,F<2>均为真,而G<1>,G<2>均为假,∀x<F<x>→G<x>>为假.<2>留给读者自己做.5.4.略5.5.给定解释I如下:<a>个体域D={3,4}.<b>↓f<x>为↓f<3>=4,↓f<4>=3.<c>↓F<x,y>为↓F<3,3>=↓F<4,4>=0,↓F<3,4>=↓F<4,3>=1.试求下列公式在I下的真值:(1)∀x∃yF<x,y>(2)∃x∀yF<x,y><3> ∀x∀y<F<x,y>→F<f<x>,f<y>>>(1)∀x∃yF<x,y>⇔ <F<3,3> ∨F<3,4>> ∧ <F<4,3> ∨F<4,4>>⇔ <0∨1> ∧ <1∨0>⇔1(2)∃x∀yF<x,y>⇔ <F<3,3> ∧F<3,4>> ∨ <F<4,3> ∧F<4,4>>⇔ <0∧1> ∨ <1∧0>⇔0<3> ∀x∀y<F<x,y>→F<f<x>,f<y>>>⇔ <F<3,3>→F<f<3>,f<3>>>∧ <F<4,3> →F<f<4>,f<3>>>∧ <F<3,4> →F<f<3>,f<4>>>∧ <F<4,4> →F<f<4>,f<4>>>⇔ <0→0> ∧ <1→1>∧ <1→1> ∧ <0→0>⇔15.6.略5.7.略5.8.在一阶逻辑中将下列命题符号化,要求用两种不同的等值形式.<1> 没有小于负数的正数.<2> 相等的两个角未必都是对顶角.<1>令F<x>:x小于负数,G<x>:x是正数.符合化为:∃⌝x<<F<x>∧ G<x>>⇔ ∀x<G<x>→ ⌝G<x>>.<2>令F<x>:x是角,H<x,y>:x和y 是相等的, L<x,y>:x与y是对顶角.符合化为:⌝∀x∀y<F<x>∧ F<y>∧ H<x,y>→ L<x,y>>⇔ ∃x∃y<F<x>∧ F<y>∧ H<x,y>∧ ⌝L<x,y>>⇔ ∃x<F<x>∧ <∃y<F<y>∧ H<x,y>∧ ⌝L<x,y>>>.5.9.略5.10.略5.11.略5.12.求下列各式的前束范式.<1>∀xF<x> → ∀yG<x,y>;<3>∀xF<x,y>↔ ∃xG<x, y>;<5>∃x1F<x1,x2>→ <F<x1>→ ∃⌝x2G<x1,x2>>.前束范式不是唯一的.<1> ∀xF<x> → ∀yG<x,y>⇔ ∃x<F<x> → ∀yG<x,y>>⇔ ∃x∀y<F<x>→ G<x,y>>.<3> ∀xF<x,y>↔ ∃xG<x,y>⇔ <∀xF<x,y>→ ∃xG<x,y>>∧ <∃xG<x,y> → ∀xF<x,y>>⇔ <∀x1F<x1,y>→ ∃x2G<x2,y>>∧ <∃x3G<x3,y>→ ∀x4F<x4,y>>⇔ ∃x1∃x2<F<x1,y> → G<x2,y>>∧ ∀x3∀x4<G<x3,y>→ F<x4,y>>⇔ ∃x1∃x2∀x3∀x4<<F<x1,y>→ G<x2,y>>∧ <G<x3,y>→ F<x4,y>>>.5.13.将下列命题符号化,要求符号化的公式全为前束范式:<1> 有的汽车比有的火车跑得快.<2> 有的火车比所有的汽车跑得快.<3> 说所有的火车比所有的汽车跑得快是不对的.<4> 说有的飞机比有的汽车慢是不对的.<1>令F<x>:x是汽车,G< y>:y是火车,H<x,y>:x 比y跑得快.∃x<F<x> ∧ ∃y<G< y>∧ H<x,y>>⇔ ∃x∃y<F<x> ∧ G<y>∧ H<x,y>>.<2>令F<x>: x是火车,G<y>:y是汽车,H<x,y>:x 比y跑得快.∃x<F<x> ∧ ∀y<G< y> → H<x,y>>>⇔ ∃x∀y<F<x> ∧ <G<y> → H<x,y>>>.0错误的答案:∃x∀y<F<x>∧ G<y>→ H<x,y>>.<3>令F<x>: x是火车,G<y>:y是汽车,H<x,y>:x 比y跑得快.⌝∀x<F<x>→ ∀y<G<y>→ H<x,y>>>⇔ ⌝∀x∀y<F<x>→ <G<y>→ H<x,y>>>⇔ ⌝∀x∀y<F<x>∧ G<y>→ H<x,y>> <不是前束范式>⇔ ∃x∃y<F<x> ∧ G<y>∧ H<x,y>>.<4>令F<x>: x是飞机,G<y>:y是汽车,H<x,y>:x 比y跑得慢.⌝ ∃x<F<x>∧ ∃y<G<y>∧ H<x,y>>>⇔ ⌝ ∃x∃y<F<x>∧ G<y>∧ H<x,y>><不是前束范式>⇔ ∀x∀y⌝ <F<x>∧ G<y>∧ H<x,y>>⇔ ∀x∀y<F<x>∧ G<y>→ ⌝H<x,y>>.5.14.略5.15.在自然推理系统F中构造下面推理的证明:<1>前提: ∃xF<x> → ∀y<<F<y>∨ G<y>>→ R<y>>,∃xF<x>结论:∃xR<x>.<2>前提:∀x<F<x>→ <G<a> ∧R<x>>>,∃xF<x>结论:∃x<F<x> ∧R<x>><3>前提:∀x<F<x>∨G<x>>,⌝∃xG<x>结论:∃xF<x><4>前提:∀x<F<x>∨G<x>>,∀x<⌝G<x>∨⌝R<x>>,∀xR<x>结论:∀xF<x>①∃xF<x> → ∀y<<F<y> ∨ G<y>>→ R<y>> 前提引入②∃xF<x> 前提引入③∀y<<F<y> ∨ G<y>> → R<y>> ①②假言推理④<F<c>∨ G<c>>→ R<c> ③UI⑤F<c> ①EI⑥F<c>∨ G<c> ⑤附加⑦⑧R<c>∃xR<x>④⑥假言推理⑦EG<2>证明:①∃xF<x> 前提引入②F<c >①EI③∀x<F<x>→ <G<a>∧ <R<x>>> 前提引入④F<c> → <G<a>∧R<c>>④UI⑤G<a>∧R<c> ②④假言推理⑥R<c> ⑤化简⑦F<c>∧R<c> ②⑥合取⑧∃x<F<x>∧R<x>>⑥E G<3>证明:①⌝∃xG<x> 前提引入②∀x⌝G<x> ①置换③⌝G<c>②UI④∀x<F<x>∨G<x> 前提引入⑤F<c>∨G<c>④UI⑥F<c> ③⑤析取三段论⑦∃xF<x>⑥E G<4>证明:①∀x<F<x>∨G<x>> 前提引入②F<y>∨G<y>①UI③∀x<⌝G<x>∨⌝R<x>> 前提引入④⌝G<y>∨⌝R<y>③UI⑤∀xR<x> 前提引入⑥R<y >⑤UI⑦⌝G<y> ④⑥析取三段论⑧F<y> ②⑦析取三段论⑥∀xF<x> U G5.16.略。
离散数学中的布尔代数知识点介绍离散数学是计算机科学和数学中的一个重要分支，而布尔代数则是离散数学中的一个基础概念。
布尔代数是一种逻辑推理和计算的数学体系，其基本概念和运算规则直接应用于计算机计算和逻辑设计中。
一、布尔代数的基本概念布尔代数有两个基本元素：命题和逻辑操作符。
命题是关于真（True）和假（False）的陈述，可以用字母或其他符号表示。
逻辑操作符包括与（AND）、或（OR）、非（NOT）三种基本运算符，用于对命题进行逻辑运算。
二、布尔代数的基本运算规则1. 与运算（AND）：只有当两个命题都为真时，与运算的结果才为真。
用符号“∧”表示，例如命题A∧B表示“命题A和命题B都为真”。
2. 或运算（OR）：只要两个命题中有一个为真，或运算的结果就为真。
用符号“∨”表示，例如命题A∨B表示“命题A或命题B为真”。
3. 非运算（NOT）：将命题的真值取反，即将真变为假，将假变为真。
用符号“¬”表示，例如¬A表示“命题A的取反”。
三、布尔代数的重要性布尔代数在计算机科学和逻辑设计中具有重要的应用。
布尔代数提供了一种形式化的工具，可以对逻辑关系和计算过程进行精确的描述和处理。
利用布尔代数的运算规则，可以进行逻辑推理、逻辑运算和逻辑设计。
布尔代数为计算机的基本运算提供了理论基础，是计算机科学不可或缺的一部分。
四、布尔代数的应用领域1. 逻辑电路设计：布尔代数的基本运算规则可以用于逻辑门电路的设计与分析。
逻辑门电路由与门、或门、非门等基本门电路组成，通过布尔代数的运算规则可以进行电路的优化和逻辑设计。
2. 程序设计与算法分析：布尔代数在程序设计和算法分析中具有重要地位。
利用布尔代数的运算规则，可以对程序的逻辑关系进行抽象和分析，确保程序的正确性和可靠性。
3. 数据库查询与管理：布尔代数可用于数据库查询和管理中的条件表达式构建。
通过布尔代数的运算规则，可以对数据库数据进行选择、过滤和计算，实现对数据的高效管理与查询。
第十章格和布尔代数习题10.1 1．解 ⑴不是，因为L 中的元素对{2,3}没有最小上界；⑵是，因为L=｛1,2,3,4,6,9,12,18,36｝任何一对元素a ,b ，都有最小上界和最大下界；⑶是，与⑵同理；⑷不是，因为L 中的元素对{6,7}没有最小上界不存在最小上界。
2．证明 ⑴因为，a ≤b,所以，a ∨b=b ；又因为，b ≤c,所以，b ∧c=b 。
故a ∨b=b ∧c ；⑵因为，a ≤b ≤c,所以，a ∧b=a,b ∧c=b,而a ∨b=b ，因此，(a ∧b )∨(b ∧c )=b ；又a ∨b=b,b ∨c=c,而b ∧c=b, 因此，(a ∨b )∧(b ∨c )=b 。
即(a ∧b)∨(b ∧c)=(a ∨b)∧(b ∨c)。
习题10.21．解 由图1知：＜S 1,≤＞不是＜L,≤＞的子格，这是因为，e ∨f=g ∉S 1;＜S 2,≤＞不是＜L,≤＞的子格， ∵e ∧f=c ∉S 2;＜S 3,≤＞是＜L,≤＞的子格.2．解 S 24的包含5个元素的子格有如下的8个：S 1={1,3,6,12,24}, S 2={1,2,6,12,24}, S 3={1,2,4,12,24}, S 4={1,2,4,8,24},S 5={1,2,3,6,12}, S 6={1,2,4,6,12}, S 7={2,4,6,12,24}, S 7={2,4,8,12,24}.3．证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是<L ，∨,∧>的子集，即是<L ，∨,∧>的子代数，故是子格。
4．证明 由(10-4)有，a ∧b ≤a ,由已知a ≤c ,由偏序关系的传递性有，a ∧b ≤c ；同理 a ∧b ≤d 。
由(10-5)和以上两式有，a ∧b ≤c ∧d .5．证明 因为由(10-4)有，a ∧b ≤a ，因此，(a ∧b )∨(c ∧d )≤a ∨(c ∧d ) ①由分配不等式有，a ∨(c ∧d )≤(a ∨c )∧(a ∨d ) ②再由由(10-4)有，(a ∨c )∧(a ∨d ) ≤a ∨c ③由偏序关系的传递性和①②③则有，(a ∧b )∨(c ∧d )≤a ∨c同理 (a ∧b )∨(c ∧d )≤b ∨d因此有， (a ∧b )∨(c ∧d )≤(a ∨c ) ∧(b ∨d )。
习题10.31．解 ⑴ 是，全上界是24，全下界是1；⑵1的补元是24；3的补元是8；8的补元是3，4、6没有补元。
图1图22．解 图3是两个格的哈斯图，其中图⑴是有补格但不是分配格的例子；图⑵是分配格但不是有补格的例子。
3．证明 先证充分性。
由已知条件知，对于任何的a ,b ,c ∈L ,有(a ∨b )∧c ≤a ∨(b ∧c )，因此和等幂律、交换律可得，(a ∨b )∧c=((b ∨a )∧c)∧c≤(b ∨(a ∧c))∧c=((a ∧c)∨b)∧c≤(a ∧c)∨(b ∧c) ①又因为，(a ∧c)≤(a ∨b)∧c 且(b ∧c)≤(a ∨b)∧c ，所以， (a ∧c)∨(b ∧c)≤(a ∨b)∧c ②由①②可得， (a ∧c)∨(b ∧c)=(a ∨b)∧c再由交换律得到， c ∧(a ∨b)=(c ∧a)∨(c ∧b) ③由此式容易证明c ∨(a ∧b)=(c ∨a)∧(c ∨b) ④由③④可知它是分配格。
再证必要性。
因为<L ,≤>是分配格，则(a ∨b )∧c =(a ∧c )∨(b ∧c )≤a ∨(b ∧c )。
4．证明 因为，∧∧=∨∧∧b a b a b a ()()(000)()=∨=∧∧∨b b a a ；同理有，)()()(b a a b a b a ∨∨=∨∨∧111)(=∨=∨∧∧b a b ；又因为补元素是唯一的，故b a b a ∨=∧)(成立。
习题10.41．解 是布尔代数，因为<A ，≤>是有补分配格。
2．证明 因为，<B ，-,∨,∧>是布尔代数，所以，运算-，∨,∧在B 上都是封闭的，因此，由运算 的定义可知，运算 在B 上也是封闭的。
又运算∨,∧都满足交换律。
因此，对于任意的a,b B,)()(b a b a b a ∧∨∧=⊕=))(())((b b a a b a ∨∧∧∨∧=)()()()(b a b a b a a b ∨∧∨=∨∧∨由其对称性可知 满足交换律。
下面证明运算 满足结合律，对于任意的a,b,c B 由上式则有c b a b a c b a ⊕∨∧∨=⊕⊕)]()[()())()(())]()([(c b a b a c b a b a ∨∨∧∨∧∨∨∧∨=])()[()()(c b a b a c b a c b a ∨∧∨∧∧∨∨∧∨∨=)()()()(c b a c b a c b a c b a ∨∨∧∨∨∧∨∨∧∨∨=同理可得)(c b a ⊕⊕)()()()(c b a c b a c b a c b a ∨∨∧∨∨∧∨∨∧∨∨=即，=⊕⊕c b a )()(c b a ⊕⊕，亦即 满足结合律。
下面再证0是关于 的单位元。
事实上对于任意的a B ，a a a a a =∨∧=∧∨∧=⊕0)1()0()0(0。
最后证明任意的a B 关于运算 都可逆，且其逆元就是a 自身，事实上000)()(=∨=∧∨∧=⊕a a a a a a综上所述，>⊕<,B 是交换群。
复习题十1．证明 显然，a ,b ∈B ，所以，B 非空。
对于任意的x , y ∈B ，则a ≤x ≤b , a ≤ y ≤b ，由格的保序性和等幂律则有，a ≤x ∨y ≤b , a ≤x ∧y ≤b即集合B 对于运算∨和∧是封闭的。
因此，<B ，≤>是<L ,≤>的子格。
而子格也是格，故<B ，≤>也是一个格。
2．证明 因为，<L ,∨,∧>是一个格，由格的分配不等式则得（(a ∧b ）∨(a ∧c)）∧((a ∧b)∨(b ∧c))≥(a ∧b)∨(a ∧b ∧c)=a ∧b ①（a ∧b ）∨(a ∧c)≤a ∧(b ∨c) ②（a ∧b ）∨(b ∧c)≤b ∧(a ∨c) ③由②③和格的保序性可得，((a ∧b)∨(a ∧c))∧((a ∧b)∨(b ∧c))≤(a ∧(b ∨c))∧(b ∧(a ∨c)=a ∧b ∧(b ∨c)∧(a ∨c)=a ∧b ④由①④和反对称性则有，((a ∧b )∨(a ∧c ))∧((a ∧b )∨(b ∧c ))= a ∧b 。
3．证明 因为<L ,≤>是格，对任意a ,b ,c ∈L ,(a ∧b )∨(b ∧c )∨(c ∧a ) ≤ [((a ∧b )∨b )∧((a ∧b )∨c )]∨(c ∧a )=[b ∧((a ∧b )∨c )]∨(c ∧a ) ≤[b ∧(a ∨c )∧(b ∨c )]∨(c ∧a )=[b ∧(a ∨c )]∨(c ∧a ) ≤(b ∨(c ∧a ))∧((a ∨c )∨(c ∧a ))=(b ∨(c ∧a ))∧(a ∨c ) ≤ (b ∨c )∧(b ∨a )∧(a ∨c )= (a ∨b )∧(b ∨c )∧(c ∨a )。
4．证明 因为有限格都是有界格，而有界格必存在最大元素和最小元素，故有限格一定有最大元素和最小元素。
5．证明 因为，a ≤b,所以，a ∨b=b ；因此有，a ∨(b ∧c)≤(a ∨b)∧(a ∨c)=b ∧(a ∨c)。
6．证明 因为，h 将运算∨传送到运算∪，将运算“-”传送到运算“＇”，所以，对于任意的x ,x 1,x 2∈B 1有：h (x 1∨x 2)=h (x 1)∪h (x 2) ①))(()('=x h x h ②所以，对于任意的a ,b ∈B 1,而)(b b a ∨=∧，因此有：))()(())(())(()('⋃='∨=∨=∧b h a h b a h b a h b a h)()()))(())(((b h a h b h a h ⋂=''⋃'=。
即h 将运算∧传送到运算∩。
7．证明 由习题10.4第2题可知<B ,⊕>是一个交换群。
由于，在布尔代数<B ，-,∨,∧>中∧是可结合的且是可交换的，由*运算的定义可知，*是可结合的且是可交换的。
由*运算的定义可知可进一步看出，关于*运算的单位元是布尔代数<B ，-,∨,∧>的全上界1。
事实上，对于任意的a B,有a a a =∧=*11因此，要证明<B ,⊕, *>是一个含幺交换环，只需证明*对⊕满足分配律。
事实上，对于任意的a,b,c B,)()()]()[()(c b a c b a c b c b a c b a ∧∧∨∧∧=∧∨∧∧=⊕*)()()()(c a b a c a b a ∧⊕∧=*⊕*))()(())()((c a b a c a b a ∧∧∧∨∧∧∧=))()(())()((c a b a c a b a ∧∧∨∨∨∧∧=)()()()(c b a c a a c b a a b a ∧∧∨∧∧∨∧∧∨∧∧=)()(c b a c b a ∧∧∨∧∧=即 =⊕*)(c b a )()(c a b a *⊕*综上所述，<B ,⊕, *>是一个含幺交换环。
