离散数学左孝凌课后习题答案

表1-6.1 P 0 0 1 1 Q 0 1 0 1 P ∨Q 0 1 1 0
不可兼析取
不可兼析取有下列的性质： ⑴ P ∨ QQ ∨ P ⑵ (P ∨ Q) ∨ RP ∨ (Q ∨ R) (交换律) (结合律)
⑶ P∧(Q ∨ R)(P∧Q) ∨ (P∧R) (合取对异或的分配律) ⑷ P∨ Q(P∧Q)∨(P∧Q) ⑸ P ∨ Q(PQ) ⑹ P ∨ P0，0 ∨ PP，1 ∨ PP 定理1-6.1 设P，Q，R为命题公式，如果P ∨ QR，则P ∨ R Q，Q ∨ RP，P ∨ Q ∨ R为一矛盾式。 (书中有证明)
不等价的命题公式的个数
两个命题变元可以构成多少个不等价的命题公式？ 由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两个 命题变元构成的命题公式有多少个不同的真值表？
两个命题变元构成的命题公式的真值表的格式如下表所示。真值表中每行 4 公式的真值都有1，0两种可能，所以命题公式的真值有2×2×2×2 = 2 = 22 = 16种可能，既有22 个不同的真值表。故有22 种不等价的公式。
表1-6.3 q 0 1 0 1 p 0 0 1 1 p↓q 1 0 0 0
1.6 全功能联结词集
至此已经学了8个联结词： ,∧,∨,→,, ∨ ,↑,↓。类似于定义命题 公式的方法，可以定义包含上述8个联结词 的命题公式。 定义1-6.4 设S是一个联结词集合，如果任何 n(n≥1)个变元组成的公式，都可以由S中的 联结词来表示，则称S是全功能联结词集。
1.6 全功能联结词集
定义1-6.1 设P和Q是两个命题，复合命题P ∨ Q称作P和Q的 不可兼析取，也叫异或。定义为：P ∨ Q为T当且仅当P 和Q的真值不相同时。联结词“ ∨ ”称为异或联结词。 联结词“ ∨ ”的真值表如表 1-6.1所示。 “ ∨ ”也可以看成逻辑运 算，它是二元逻辑运算。它在程 序设中有广泛的引用。

P125 21.a)N={1,3} Φ(4)=2b)N={1,3,7,9}Φ(10)=4c)N={1,2,3,…,12}Φ(13)=12P149 25b) 5^2003 mod 1001=983P183 4“the sailing race will be held and the lifesaving demonstration will go on”: this sentence should be split into two propositions ,one is the “sailing race will be held “, the other is “the lifesaving demonstration will go on.”P202 64N is odd and not divisible by 3 , so we can express n=6k+1 or 6k+5(k>=1) Basis step: It is easy to prove the correction of the proposition when n=7 and n=11.Inductive step: assume that if n=6k+1, the proposition is true,and if n=6(k+1)+1=(6k+1)+6, as shown in the figure below :the square is split into 4 parts asa)(6k+1)*(6k+1), b) 7*7-1 ( pleaseallow me to write this way), c)6k*6 andd)6*6k . it is clear that a) is fit to theproposition , b) can be filled withL-shaped pieces and c),d) can be filled with a rectangle consist of 2 L-shaped pieces.If n=6(k+1)+5 , the proposition can be also proved as above.So , we can believe that the proposition is true.P259 49a)We need to find something to count so that the left-hand side of theequation counts it in one way and the right-hand side counts it in different way. After much thought , we might try the following. We will count the number of bit strings of length n+r+1containing exactly r 0’s and n+1 1’s . There are C(n+r+1,r) such strings , sincea string is completely specified by deciding which r of the bits areto be the 0’s . To see that the left-hand side of the identity counts the same thing,let l+1 be the position of the last 1 in the string . Since there are n+1 1’s , we know that l cannot be less than n . thus there are disjoint cases for each l from n to n+r . For each such l, we completely determine the string by deciding which of the l positionsI the string before the last 1 are to be 0’s . Since there are n 1’s inthis range, there are l-n 0’s. Thus there are C(l,l-n) .ways to choose the positions of the 0’s . Now by the sum rule , the total number of bit strings will be ∑(l=n to n+r)C(l,l-n) . By making the change of variable k=l-n,this transforms into the left-hand side, and we arefinished.P243 33a)there can clearly be no one-to-one function from {1,2,…n} to {0,1}if n>2. if n=1 ,then there are 2 such functions , the one that sends 1 to 0, and the one that sends 1 to 1. if n=2 , then there are again 2 such functions since once it is determined where 1 is sent , the function must send 2 to the other value in the codomain.b)If the function assigns 0 to both 1 and n , then there are n-2 functionvalues free to be chosen. Each can be chosen in 2 ways. Therefore by product rule, there are 2^n-2 such functions ,as long as n>1. if n=1 ,then clearly there is just one such function.c)If n=1, then there are no such functions.If n>1, we will decide which of the numbers from 1 to n-1 , inclusive,will get sent to 1. there are n-1 ways to make this choice.finally , we are free to specify the value if the function at n,and this may be done in 2ways ,hence by the product rule ,the answer is 2(n-1).P383 25b)for each unordered pair {a.b} of distinct elements of A, we have a3-way choice----either include (a,b) only, include (b,a) only , orinclude neither .For each element of A we have a 2-way choice .Therefore the answer is (3^C(n,2))*(2^n) .c)as in part (b) we have a 3-way choice for a!=b . there is no choiceabout including (a,a) in the relation——the definition prohibits it.Therefore the answer is 3^C(n,2)。

第四章代数结构（作业）作业：P86：4、7、94、（1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。

（2）任选整数集合中的三个元素x,y和z。

则有：(x*y)*z = (x+y+xy)*z= (x+y+xy)+z+(x+y+xy)×z= x+y+z+xy+xz+yz+xyzx*(y*z) = x*(y+z+yz)= x+(y+z+yz)+x×(y+z+yz)= x+y+z+yz+xy+xz+xyz= (x*y)*z因此，*运算满足结合律。

（3）假设e为（Z,*）的幺元，则有：任选整数集中的一个元素x，都有0*x = 0+x+0×x=x且x*0 = x+0+x×0=x故0是(Z,*)的幺元。

7、N+上的所有元素都是（N+ ,*）等幂元；（N+ ,*）无幺元；（N+ ,*）的零元为1。

9、（A,*）中的等幂元：a、b、c、d；（A,*）中的幺元：b；（A,*）中的零元：c；a-1 = d，b-1 = b，c-1 不存在，d-1 = a，作业：P87：12、13、1812、（A，*）到（N4,⊕4）的同构映射f为：f(a)=0, f(b)=1, f(c)=2, f(d)=3;或者：f(a)=0, f(b)=3, f(c)=2, f(d)=1;13、同构映射f为：f(0)=∅, f(1)={a}, f(2)={b}, f(3)={a,b};或者：f(0)=∅, f(1)={b}, f(2)={a}, f(3)={a,b};18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b)由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。

作业：P96：3，P97：73、(1)显然，*运算对Z 是封闭的。

(2) (a*b)*c = (3(a+b+2)+ab)*c= 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abca*(b*c) = a*(3(b+c+2)+bc)= 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc= (a*b)*c故*运算满足结合律。

简单命题（或原子命题）：简单陈述句表示 的命题。用P，Q，R,…,Pi,Qi,Ri,…表示。
例 P:2是偶数。 Q:雪是黑色的。 命题常量（或命题常元）：简单命题。 命题变项（或命题变元）：真值可以变化的
简单陈述句。不是命题。 例：x+y>5
命题变项也用P，Q，R,…, Pi,Qi,Ri,…表示。 复合命题：由简单命题用联结词联结而成的命题。
∧表示自然语言中的“既……又……”， “不仅……而且……”， “虽然……但是”
P Q P ∧Q
TT
T
TF
F
FT
F
FF
F
例3将下列命题符号化。 （1）李平既聪明又用功。 （2）李平虽然聪明，但不用功。 （3）李平不但聪明，而且用功。 （3）李平不是不聪明，而是不用功。
解：设P：李平聪明；Q：李平用功。 （1）P∧Q （2）P∧ᄀQ （3）P∧Q （4）ᄀ（ᄀP）∧ᄀQ
⇔T→( (Q∧ᄀQ) ∧R)
（排中律）
⇔T→(F∧R)
（矛盾律 ）
⇔T→F
（零律）
⇔ᄀT∨F
（蕴涵等值式）
⇔F∨F⇔F
（等幂律）
3. 证明 (P→Q) ∧ᄀP
⇔(ᄀP∨Q) ∧ᄀP
（蕴涵等价值式）
⇔ᄀP
（吸收律）
1-5 重言式与蕴涵式
定义1－ 给定一命题公式 ，若无论对分量作什么样的指 派，其对应的真值永为T，则称该命题公式 为重言式或永真式。
解：（1）－（4）设P：2+2＝4；Q：3是奇数。
（1）P⇄Q 真命题
（2）P⇄ᄀQ 假命题
（3）ᄀP⇄Q 假命题
（4）ᄀP⇄ᄀQ 真命题
（5）设P：两圆的面积相等；Q：两圆的面积相同。