离散数学半群【实用资料】

第1章 命题逻辑

本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.

一、重点内容

1. 命题

命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义.

2. 六个联结词及真值表

“”否定联结词，P是命题，P是P的否命题，是由联结词  和命题P组成的复合命题.P取真值1，P取真值0，P取真值0，P取真值1. 它是一元联结词.

 “”合取联结词，PQ是命题P，Q的合取式，是“”和P，Q组成的复合命题. “”在语句中相当于“不但…而且…”，“既…又…”. PQ取值1，当且仅当P，Q均取1；PQ取值为0，只有P，Q之一取0.

 “”析取联结词，“”不可兼析取(异或)联结词， PQ是命题P，Q的析取式，是“”和P，Q组成的复合命题. PQ是联结词“”和P，Q组成的复合命题. 联结词“”或“”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“PQ”“(PQ)(PQ)”. PQ取值1，只要P，Q之一取值1，PQ取值0，只有P，Q都取值0.

 “”蕴含联结词， PQ是“”和P，Q组成的复合命题，只有P取值为1，Q取值为0时，PQ取值为0；其余各种情况，均有PQ的真值为1，亦即10的真值为0，01，11，00的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“PQ”.

 “” 等价联结词，PQ是P，Q的等价式，是“”和P，Q组成的复合命题. “”在语句中相当于“…当且仅当…”，PQ取值1当且仅当P，Q真值相同.

3. 命题公式、赋值与解释，命题公式的分类与判别

命题公式与赋值，命题P含有n个命题变项P1，P2,…,Pn，给P1，P2,…,Pn各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派.

离散数学复习资料和试题

集合论

1. 集合与集合之间的关系, 元素与集合之间的关系

1．判别下列各题是否正确：

（1）{1，2}{1，2，3，{1，2，3}} 正确

（2）{p，q，r}{ p，q，r ，{ p，q，r }} 正确

2．设有集合Ａ＝｛a,b,c｝，为空集，则｛a｝Ａ

3．设S1=，S2={}，S3=ρ({})，S3=ρ()，则：S2 ∈S4为假命题

2. 幂集：ρ（A）就是集合A中子集所组成的集合

求下列集合的幂集：

（1）{a，{a}}={，{a}，{{a}}，{a，{a}}}

（2）{，a，{a}}={，{}，{a}，{{a}}，{，a}，{，{a}}，{a，{a}}，{，a，{a}}}

3. 集合的运算：10组集合恒等式：

1） 交换率：A∪B=B∪A；A∩B=B∩A

2） 结合律：A∪（B∪C）=（A∪B）∪C；A∩（B∩C）=（A∩B）∩C

3） 分配律：A∪（B∩C）=（A∪B）∩（A∪C）；A∩（B∪C）=（A∩B）∪（A∩C）

4） 同一律：A∪=A；A∩E=A

5） 零一律：A∩=；A∪E=E

6） 互补率：A∪~A=E；A∩~A=；~E=；~=E

7） 双重否定率：~~A=A

8） 幂等率：A∪A=A；A∩A=A

9） 吸收率：A∪（A∩B）=A；A∩（A∪B）=A

10） 德摩根率：~（A∪B）=~A∩~B；~（A∩B）=~A∪~B

交：A∩B；并：A∪B；差运算：A—B（属于A不属于B）；补运算：~A；

对称差运算：AB；笛卡儿乘积：A×B={|a∈A，b∈B}

设A={a，b，c}，B={b，d，e}则A—B={a，c}，AB={a，c，d，e}

4. 集合的计数问题：|A|=2 n (n是集合A的元素的个数)

| A∪B |=|A|+|B|—| A∩B |；|A∪B∪C|=|A|+|B|+|C|—| A∩B |—| A∩C |—|B∩C|+| A∩B∩C |

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除

1 / 10 第六章几个典型的代数系统

本章讨论几类重要的代数结构：半群、群、环、域、格与布尔代数等．我们先讨论最简单的半群．

6.1 半群

6。1。1半群的概念

定义6.1.1设

a,b，c∈S,(a•b）•c=a•（b•c）

则称为半群;

定义6。1。2设.

定义6。1.3若半群是可交换半群.

［例6.1.1]

(1)都是含么半群；〈I,－〉不是半群；

(2）设A为任一集合,则<(A），，〉,<(A)，,A>都是可交换的含么半群；

(2)设∑是个字母表，是∑上的连接运算,则空串就是∑中关于连接运算的单位元且该运算满足结合律,故<∑，，>是一个独异点。

6．1．2子半群

定义6。1。4半群的了代数叫子半群，即设〈S,•>是半群，T为S的非空子集。若T关于资料内容仅供您学习参考，如有不当之处，请联系改正或者删除

2 / 10 运算•封闭，则称

定义6。1。5设〈S，•，e〉是独异点，T为S的非空子集。若T关于运算•封闭，且eT,则称〈T,•>是

［例6.1。2］ 〈Z,+>和都是

定义6。1。6设V1=〈S1，〉,V2=〈S2,>是两个半群，V1与V2的积代数V1V2=

其中S=S1S2，,,,,2211yxyx对于

•21212211,,,yyxxyxyx资料内容仅供您学习参考，如有不当之处，请联系改正或者删除

2 / 10 也是半群，叫,V1与V2的积半群。

6．1．3半群的同态

定义6.1。6设和是半群，函数f：S1S2。若a,b∈S1，有f（ab)=f(a)•h（b），则称f是〈S1，>到〈S2，•〉的半群同态。若f是双射，则称f为半群同构。

［例6。1。2］ •000)00(,,,00abaSVRbabaS

.

. 《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． AB，且AB B．BA，且AB C．AB，且AB D．AB，且AB

2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一

A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的

3．设图G的邻接矩阵为

0101010010000011100100110

则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1

C．G的边数比结点数少1 D．G中没有回路．

5．下列公式 ( C )为重言式．

A．PQPQ B．(Q(PQ)) (Q(PQ))

C．(P(QP))(P(PQ)) D．(P(PQ)) Q

6．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（ B ）不是从A到B的函数．

A．R1和R2 B．R2

C．R3 D．R1和R3

7．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( B )．