离散数学第二版王元元课后答案

第十一章 群、环、域

11.1 半群

内容提要

11.1.1 半群及独异点

定义 11.1 称代数结构为半群（semigroups），如果 ? 运算满足结合律．当半群含有关于 ? 运算的么元，则称它为独异点（monoid），或含么半群．

定理11.1 设为一半群,那么

（1）的任一子代数都是半群，称为的子半群．

（2）若独异点的子代数含有么元e,那么它必为一独异点,称为的子独异点．

定理11.2 设,是半群,h为S到S’的同态,这时称h为半群同态．对半群同态有

（1）同态象为一半群．

（2）当为独异点时，则为一独异点.

定理11.3 设为一半群,那麽

SS

（1）为一半群，这里S为S上所有一元函数的集合，○ 为函数的合成运算．

S

（2）存在S到S的半群同态．

11.1.2 自由独异点

定义 11.2 称独异点为自由独异点（free monoid）,如果有A?S使得 （1）e?A．

（2）对任意u?S，x?A,u?x ? e . 自由独异点（free monoid）,如果有A?S使得 （3）对任意u,v?S，x,y?A,若u?x = v?y,那么u = v,x = y．

（4） S由A

第九章 特 殊 图

9.1 二分图

内容提要

9.1.1 二分图的基本概念

定义9.1 无向图G = 称为二分图（bipartite graph），如果有非空集合X，Y使X∪Y = V，X∩Y = ?，且对每一e?E，?(e) = (x, y)，x?X，y?Y。此时常用表示二分图G。若对X中任一x及Y中任一y恰有一边e?E，使?(e) = (x, y), 则称G为完全二分图（complete bipartite graph）。当?X? = m，?Y? = n时，完全二分图G记为Km,n。

定理9.1 无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。

9.1.2 匹配

定义9.2 设G = 为二分图，M?E。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximal matching）。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfect matching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。 定

第四篇 抽象代数

第十章 代数结构通论

10.1 代数结构 内容提要

10.1.1代数结构的意义

定义10.1 称 为集合S上的n元运算（operaters），如果 为Sn到S的一个函数。以下 常用以表示二元运算, ?(x,y)常记为x?y；?常用以表示一元运算。对二元运算，’: 称 运算满足结合律，若 xyz(x,y,z?S→x? (y? z) = (x?y) ?z) 称 运算满足交换律，若 xy(x,y?S→x?y= y?x) 称 运算对 ’ 运算满足分配律，若 xyz(x,y,z?S→x?(y?’z) = (x?y) ?’ (x?z))

定义10.2 代数结构（algebra structures）是由以下三个部分组成的数学结构： （1）非空集合S，称为代数结构的载体。 （2）载体S上的若干运算。

（3）一组刻划载体上各运算所满足性质的公理。 代数结构常用一个多元序组来表示，其中 S是载体，?，，…为各种运算。有时为了强调S有某些元素地位

习题3.7

1. 列出关系{?a，b，c，d?|a，b，c，d?Z且a?b?c?d?6}中所有有序4元解 {?a，b，c，d?|a，b，c，d?Z且a?b?c?d?6}

??组。

?{?1,1,1,6?,?1,1,6,1?,?1,6,1,1?,?6,1,1,1?,?1,1,2,3?,?1,1,3,2?,?1,2,1,3?,?1,3,1,2?,

?1,2,3,1?,?1,3,2,1?,?2,3,1,1?,?3,2,1,1?,?2,1,3,1?,?3,1,2,1?,?2,1,1,3?,?3,1,1,2?

2. 列出二维表3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。

表3.18 航班信息

航空公司 Nadir Acme Acme Acme Nadir Acme Nadir

解 略

3. 当施用投影运算?2,3,5到有序5元组?a，b，c，d?时你能得到什么？

解 略

4. 哪个投影运算用于除去一个6元组的第一、第二和第四个分量？

解 略

5. 给出分别施用投影运算?1,2,4和选择运算?航空公司＝Nadir到二维表3.18以后得到的表。 解 对航班信息二维表进行投影运算?2,3,5

.WORD 完美格式.

离散数学答案 屈婉玲版

第二版 高等教育出版社课后答案 第一章部分课后习题参考答案

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）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1） ? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1

17．判断下面一段论述是否为真：“?是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”

答：p: ?是无理数 1 q: 3是无理数 0 r:

2是无理数 1

s: 6能被2整除 1

t: 6能被4整除 0

命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧

2.1 等值式

一、等值式的概念

两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。

设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。

定义2.1 设A,B式两个命题公式，若A,B构成的等价式A

B是等值的，记作A

B.

B为重言式，则称A与

定义中给出的符号不是联结词符，它是用来说明A与B等值（AB是重言式）的一种记法，因而是元语言符号。此记号在下文中频繁出现，千万不要将它与混为一谈，同时也要注意它与一般等号=的区别。 判断等值式有如下方法： 1.真值表

2.等值演算

3.范式

二、用真值表判断公式的等值

例2.1 判断下面两个公式是否等值：

┐(p∨q)与┐p∧┐q

解 用真值表法判断┐(p∨q)

(┐p∧┐q)是否为重言式。此等价式的真值表如表2.1

(┐p∧┐q)。

所示，从表中可知它是重言式，因而┐(p∨q)与┐p∧┐q等值，即┐(p∨q)

其实，在用真值表法判断AB是否为重言式时，真值表的最后一

离散数学习题解 1

习题一

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

习题一

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

习题一

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时为假.

2.13 设解释I为：个体域DI ={-2,3,6},一元谓词F（X）：X（X）：X>5,R(X):X（1） 解：

x(F(x)x(F(x)(F(-2) ((-2((1 00

(2)

x(R(x)

F(x))

G(5) G(5)

F(3)) (( 3

(R(6)7)

(3

F(6))3))

03)

7。在I下求下列各式的真值。

3，G

G(x)) G(x)) G(-2))

(F(3) ((3((0 G(3)) 3)

(F(6) (3>5)) 0))

G(6)) ((6

3)

(6<5))

(-2>5))

0))

0))((1 0

解：x(R(x)(R(-2)((-2

F(x))

F(-2)) (R(3)7)

(-2

3))

G(5)

7)

(( 6

(63)) (5>5) (1 10

1) 1

(1 0

1) 0

(1

0)

0

(3)解：

x(F(x)x(F(x)

G(x)) G(x))

(F(3)

((3 (0

G(3)) 3) 1)

(F(6) (3>5))

G(6)) ((6

3)

(6>5))

(F(-2) ((-2(1

G(-2)) 3)

(-2>5)) (1

0)

0)

1 1

1 1

2.14 求下列各式的前束范式，要求