离散数学1

#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAX_STACK_SIZE 100 typedef int ElemType; typedef struct{ElemType data[MAX_STACK_SIZE];int top;} Stack;void lnitStack(Stack *S){S->top=-1;}int Push(Stack *S,ElemType x){if(S->top==MAX_STACK_SIZE-1){printf("\n Stack is full!");return 0;}S->top++;S->data[S->top]=x;return 1;}int Empty(Stack *S){return (S->top==-1);}int Pop(Stack *S,ElemType *x){if(Empty(S)){printf("\n Stack is free!");return 0;}*x=S->data[S->top];S_>top__;return 1;}void conversion(int N){int e;Stack *S=(Stack*)malloc(sizeof(Stack));InitStack(S); while(N){Push(S,N%2);"}while(!Empty(S)){Pop(S, &e);printf("%d ",e);}}void main(){ int n;printf(" 请输入待转换的值n: \n");scanf ("%d",&n);conversion(n);1. 判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？(1) 离散数学是计算机专业的一门必修课。

《 离散数学 》同步测试1、命题逻辑一．填空：1．公式)()(s r q p ∨→∧的真值表中共有 16 种真值指派。

2．命题公式（⌝P →Q ）→（⌝ Q ∨ P ）的主析取范式为001011m m m ∨∨或（P ∧Q ）∨（P ∧⌝ Q ）∨（⌝P ∧⌝Q ） ，主合取范式为：01M 或P ∨⌝ Q 。

3．设A 、B 、C 和D 四个人中派两个人出差，需要满足下列条件：（1）若A 去，则C 和D 中要去一人；（2）B 和C 不能都去；（3）C 去则D 要留下。

则有3 种派法，分别为 AC,AD,BD 。

4．给定命题公式：P ∨（⌝P →（Q ∨(⌝ Q →R )）则它的成真指派为001，010，011，100，101，110，111，成假指派为000。

二．判断下列命题的对错。

正确的在括号内填√,错误的在括号内填×。

1、设A 、B 、C 为任意命题公式，若A ∨B ⇔ B ∨ C ，则A ⇔ B 。

（ × ）2、设A 、B 为任意命题公式，若⌝ A ⇔⌝ B ，则A ⇔ B 。

（ √ ）3、公式)()(q p q p ∨→∧是重言式。

（ √ ）4、公式P ∧Q 是合取范式，不是析取范式。

（ × ）5、所有极大项的析取为永真式。

（√ ）6、一个命题公式可以有多个与之等价的析取范式。

（√ ）7、任一命题的主合取范式是唯一的。

（√）8、下面推理是正确的： （ × ）（1）P →Q P（2）⌝P P（3）⌝Q T(1)(2)9、公式（P ∧Q ）→（R ∨ ⌝S ）的对偶式为（P ∨Q ）→（R ∧ ⌝S ）。

（ × ）10、公式（⌝P ∨Q ）∧（P →R ）与P →（Q ∧ R ）。

（ √ ）三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内(多选不给分)。

1、给定命题公式如下：A ．（P ↔Q ）↔（P →Q ）∧（Q → P ）B ．（P ∧⌝P ）↔ QC ．（P ∨⌝P ）→（（Q ∧⌝ Q ）∧R ）则重言式为：( A ) ，矛盾式为：( C )，可满足式为：( B )2．给定命题公式如下：（⌝P →Q ）→（⌝ P ∧Q ）该命题公式的成真赋值个数是（D），成假赋值个数是（B），与它等价的主析取范式中极小项个数为（D），主合取范式中极大项个数为（B）A．0 B．1 C．2 D．3 E. 43．给定命题公式：P∨（Q∧R）则它的成真赋值为（A），成假赋值为（C）A．111，011，100，101，110 B．111，011C．000，010，001 D．0004．给定真值表：则F等价于（ D ）A．P ∧Q B．P∨Q C．P→Q D．⌝P∨⌝Q5．给定命题公式：（⌝P∨Q）∧（P→ R），与之等价的是(C )A．P→（⌝ Q∧R）B．P→（Q∨R）C．P→（Q∧R）D．⌝P→（Q∧R）6．前提条件：P→（Q →S），Q, P∨⌝R,则它的有效推论为(B )A．S B．R→S C．P D．R→Q同步测试2、谓词逻辑一．填空：1．对谓词公式（（∀x）P（x）∨（∃y）Q（y））→（∀x）R（x）中约束变元应用变换规则所得到的前束范式是（∃x）（∀ y）（∀z）（P（x）∨Q（y））→R（z））2．谓词公式（∀x）（P（x）→Q（x））∧（∃z）（R（x）∧S（z））中，量词（∀x）的辖域为（P（x）→Q（x））。

离散数学知识点
离散数学是数学中的一种分支，主要研究离散的数学结构和离散的数学对象，
例如集合、图论和组合数学等内容。

以下是一些离散数学的知识点：
1. 集合和函数：集合是离散数学的基础，函数是一种映射关系。

2. 逻辑和证明：逻辑用于建立数学理论的形式化方法，证明是验证数学结论的
方法。

3. 数论：研究整数和整数间的关系，包括质数、素数、最大公约数、最小公倍
数等。

4. 图论：研究图和网络的数学理论，包括图的表示、遍历、最短路径和树等。

5. 组合数学：研究离散结构的组合和计数问题，包括排列、组合、二项式系数等。

6. 计算理论：研究计算算法和计算机科学的理论基础，包括自动机、形式语言
和复杂性理论等。

7. 数值方法：研究数值计算的方法和理论，包括数值逼近、数值微积分和矩阵
计算等。

8. 离散优化：研究离散问题的最优解，包括线性规划、整数规划和组合优化等。

9. 随机模型：研究随机事件和概率论，包括随机过程、马尔可夫链和随机算法等。

10. 图形理论：研究图形的美学、结构和性质，包括图像处理、计算机视觉和
图形学等。

离散数学常考题型梳理第1章 集合及其运算一、题型分析本章主要介绍集合论的基本概念和结论，集合的运算及其性质，以及利用运算性质进行集合表达式的化简和集合恒等式的证明等内容．经常涉及到的题型有：1-1集合与集合之间的包含、元素与集合之间的属于关系1-2幂集的计算1-3集合之间的运算1-4利用集合运算性质证明集合恒等式因此，在本章学习过程中希望大家要清楚地知道：1．集合与集合之间存在一种包含关系，当两个集合A 和B 存在关系A 包含B ，用A ⊇B 表示，或存在关系B 被A 包含，用B ⊆A 表示，这时称B 为A 的子集．注意空集∅是任意一个集合的子集，集合A 也是自己的子集．当B ⊆A 且B ≠A ，也就是说，只有B ⊂A 或A ⊃B 成立，则称B 为A 的真子集．若B 不是A 的子集，即B ⊆A 不成立时，则称A 不包含B ，记作B ⊆A ．然而，元素与集合之间存在一种从属关系，当a 是集合A 中的元素，则称a 属于A ，记作a∈A ；若a 不是集合A 中的元素，则称a 不属于A ，记作a ∉A ．因此，这两种关系一定不要混淆．2．由集合A 的所有子集组成的集合，称为A 的幂集，记作P (A )或2A ．若集合A 是由n 个元素所组成的集合，则A 的幂集由2n 元素组成．当n =3时，A 的幂集由23=8个元素组成．例如，设集合A = {0, 1, 2 }，则A 的全部子集由以下子集组成：0元子集（即空集）：∅；1元子集：{0}，{1}，{2}；2元子集：{0, 1}，{0, 2}，{1, 2}；3元子集（即集合A ）：{0, 1, 2}．因此，计算集合A 的幂集时，首先要按照上述方法写出集合A 的全部子集，然后检验写出的子集个数是否等于2n 个，其中n 是集合A 的元素个数．3．集合之间的运算有并（⋃）、交（⋂）、差（-）、补（~）和对称差（⊕）等五种运算，在做集合运算的题目时，一定要按照它们的定义进行计算．(1) 集合A 和B 的并集A B x x A ⋃=∈{或 x B ∈} 特点：由集合A 和B 的所有元素组成的集合．见图1 图1 图2(2) 集合A 和B 的交集A B x x A ⋂=∈{ 且 x B ∈}特点：由集合A 和B 的公共元素组成的集合．见图2(3) 集合A 与B 的差集A B -=∈∉{}x x A x B 且 特点：由属于A ，而不属于B 的所有元素组成的集合．见图3(4) 集合A 的补集~A ={}x x E x A ∈∉且特点：由属于全集E 但不属于集合A 的元素组成的集合．见图4补集总相对于一个全集而言，可以看作是全集E 与集合A 的差集．(5) 集合A 与B 的对称差A ⊕B ＝(A －B )⋃(B －A )或 A ⊕B ＝(A ⋃B )－(A ⋂B )特点：由分别属于集合A 与B 的元素但不属于它们公共元素组成的集合．见图5(6) 把集合A ，B 合成集合A ×B 叫做笛卡儿积，规定A ×B ＝{<x , y >∣x ∈A 且y ∈B }注意：由于有序对<x , y >中x ，y 的位置是确定的，因此A ×B 的记法也是确定的，不能写成B ×A.．笛卡儿积的运算一般不能交换.．虽然，笛卡儿积的内容是第2章2.1.1目的内容，是二元关系的预备知识，但我们认为把它作为集合的一种运算考虑更好些。

离散数学课后习题答案离散数学课后习题答案离散数学是计算机科学中的一门重要课程，它涵盖了诸多数学概念与技巧，为计算机科学的理论基础打下了坚实的基础。

在学习离散数学的过程中，课后习题是巩固知识、提高能力的重要途径。

然而，有时候我们会遇到一些难以解答的问题，需要参考一些答案来进行思考与学习。

本文将为大家提供一些离散数学课后习题的答案，希望能对大家的学习有所帮助。

一、集合论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为奇数。

离散数学名词解释
离散数学是一门研究离散结构及其相应的逻辑和算法的数学分支。

以下是几个离散数学中常用的名词解释：
1. 集合论：研究集合及其运算规则的理论，包括集合的并、交、差等操作。

2. 图论：研究图及其应用的理论，图由顶点和边组成，研究图中的路径、连通性和图的着色等问题。

3. 逻辑：研究推理和论证的规则和原则，包括命题逻辑、谓词逻辑和模态逻辑等。

4. 组合数学：研究离散对象的组合方式和计数方法的数学分支，常用于解决排列、组合、图的计数等问题。

5. 代数系统：研究具有特定运算规则的数学结构，如群、环、域等代数结构。

6. 排列组合：研究对象的排列和选择方式的数学方法，包括排列、组合、二项式系数等。

7. 图论中的树：一种无环连通图，其任意两个顶点间只存在唯一路径。

8. 关系：集合之间的对应关系，研究元素之间的相互关系、等价关系和偏序关系等。

9. 图的着色：为图的顶点或边分配标记，使相邻顶点或边不具有相同的标记。

10. 递归：通过将问题分解为一个或多个类似的子问题，并根据基本情况进行解决的数学和计算方法。

这些名词在离散数学中具有重要意义，被广泛应用于计算机科学、信息科学和工程等领域。

离散数学知识点全归纳离散数学是数学的一个分支，研究的是离散对象和离散结构。

在计算机科学、信息技术以及其他领域中，离散数学具有重要的应用价值。

以下是离散数学的一些重要知识点的全面总结。

1. 集合论和逻辑- 集合：基本概念、运算、包含关系、并集、交集、差集、幂集等。

- 命题逻辑：命题、命题的连接词、真值表、逻辑等价、析取范式、合取范式等。

- 谓词逻辑：谓词、量词、逻辑推理、存在量词和全称量词等。

2. 证明方法- 直接证明：利用已知事实和逻辑推理，直接得出结论。

- 对证法：从假设的反面出发，利用矛盾推理得出结论。

- 数学归纳法：证明基础情况成立，再证明递推步骤成立。

3. 图论- 图的基本概念：顶点、边、路径、回路、度、连通性等。

- 图的表示：邻接矩阵、邻接表等。

- 最短路径：Dijkstra算法、Floyd-Warshall算法等。

- 最小生成树：Prim算法、Kruskal算法等。

4. 关系与函数- 关系及其性质：自反性、对称性、传递性、等价关系等。

- 函数及其性质：定义域、值域、单射、满射、双射等。

- 逆函数和复合函数：求逆函数、复合函数的定义和性质。

5. 组合数学- 排列和组合：排列、组合的计算公式和性质。

- 递归关系：递推公式、递归算法等。

- 图的着色：色数、四色定理等。

6. 代数系统- 半群、幺半群、群、环、整环和域的定义和性质。

- 同态：同态映射、同构等。

- 应用：编码理论、密码学等。

以上是离散数学的一些重要知识点的概括。

深入理解和掌握这些知识，对于解决实际问题和在相关领域中取得成功非常重要。

在学习过程中，建议结合实际例子和习题进行练习，加深对知识的理解和应用能力。