离散数学定义与定理
第一章命题逻辑
表示命题的符号称为命题标识。
一个命题标识符表示确定的命题，称为命题常量。
若命题标识符只表示任意命题的位置标志，称为命题变元或命题变项。
只有当命题变元（例P）被确定的命题取代时(例雪是黑的)，才有确定的真值这时称对P 进行指派。
表示原子命题时的命题变元，称为原子变元。
定义1.1 设p为一命题，复合命题p的否定称为p的否定式，记为?p，读作“非p”。若p 为t ，若?p为f ；若p 为f ，若?p 为t 。联结词“?”表示命题的否定。
否定联结词有时也记为“▔”。
定义1.2 设p和q为两个命题。复合命题“p并且q” (或“p 和q”)称为p和q的合取式，记为p∧q。当且仅当p、q同时为t 时，p∧q 为t。∧为合取联结词。
定义1.3 设p 和q是两个命题，复合命题“p 或q”称为p 与q的析取式。记为p ∨q。“∨”为析取联结词，当且仅当p、q 同时为f 时，p ∨q为f 。
注意：这儿的“或”是可兼或，是与自然语言中的“或”有区别的。
定义1.4 设p 和q是两个命题，复合命题“如果p ，则q”，称为p 和q的蕴涵式，记为p →q 。称p 为蕴涵式的前件，q 为蕴涵式的后件。当且仅当p 的真值为t，q 的真值为f 时，p →q 为f，否则p →q 的真值为t 。
定义1.5 设p 和q是两个命题，复合命题“p 当且仅当q” 称为p 和q的等价式，记为p ?q 。称?为等价联结词。当且仅当p 与q 的真值相同时，p ? q 真值为t 。
不包含任何联结词的命题称为原子命题，至少包含一个联结词的命题称为复合命题。
★命题公式是没有真假值的，仅当在公式中的所有命题变元都用真值代入时，才得到一个命题。该命题的真值依赖于各命题变元的代入真值。
离散数学第二章一阶逻辑知识点总结
数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x
存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中
离散数学课本定义和定理
第1章集合 1.1 集合的基本概念 1. 集合、元（元素）、有限集、无限集、空集 2. 表示集合的方法：列举法、描述法 3. 定义1.1.1（子集）：给定集合A和B，如果集合A的任何一个元都是集合B中的元，则称集合A包含于B或B包含A，记为或，并称A为B的一个子集。 如果集合A和B满足，但B中有元不属于A，则称集合A真包含于B，记为，并且称A为B的一个真子集。 4. 定义1.1.2（幂集）：给定集合A，以A的所有子集为元构成的一个集合，这个集合称为A 的幂集，记为或 1.2 集合的运算 定义1.2.1（并集）：设A和B是两个集合，则包含A和B的所有元，但不包含其他元的集合，称为A和B的并集，记为. 定义1.2.2（交集）：A和B是两个集合，包含A和B的所有公共元，但不包含其他元的集合，称为A和B的交集，记为. 定义1.2.3（不相交）：A和B是两个集合，如果它们满足，则称集合A和B是不相交的。 定义1.2.4（差集）：A和B是两个集合，属于A而不属于B的所有元构成集合，称为A和B 的差集，记为. 定义1.2.5（补集）：若A是空间E的集合，则E中所有不属于A的元构成的集合称为A的补集，记为. 定义1.2.6（对称差）：A和B是两个集合，则定义A和B的对称差为 1.3 包含排斥原理 定理1.3.1设为有限集，其元素个数分别为，则 定理 1.3.2设为有限集，其元素个数分别为，则 定理1.3.3设为有限集，则 重要例题P11 例1.3.1 第2章二元关系 2.1 关系 定义2.1.1（序偶）： 若和是两个元，将它们按前后顺序排列，记为，则成为一个序偶。 ※对于序偶和，当且仅当并且时，才称和相等，记为
考试必备离散数学概念总结
1.1、单个命题变项和命题常项是合式公式, 称作原子命题公式 2.1、若等价式A?B是重言式，则称A与B等值，记作A?B，并称A?B是等值式 2.2、(1) 文字——命题变项及其否定的总称 2.3、设C1=l∨C1', C2=lc∨C2', C1'和C2'不含l和lc, 称C1∨'C2'为C1和C2(以l和lc为消解 文字)的消解式或消解结果, 记作Res(C1,C2) 2.4、设S是一个合取范式, C1,C2,?,Cn是一个简单析取式序列. 如果对每一个i(1≤i≤n), Ci 是S的一个简单析取式或者是Res(Cj,Ck)(1≤j
离散数学的定义精简版
图 1.每个无向图所有结点度总和等于边数的2倍. 2每个无向图中,奇数度的结点必为偶数个. 3G=
离散数学部分概念和公式总结
离散数学部分概念和公式总结 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={
离散数学定义必须背
命题逻辑 ?(论域)定义：论域是一个数学系统，记为D。它由三部分组成： ?(1)一个非空对象集合S，每个对象也称为个体； ?(2) 一个关于D的函数集合F； ?(3)一个关于D的关系集合R。 ?（逻辑连接词）定义 ?设n>0,称为{0,1}n到{0,1}的函数为n元函数，真值函数也称为联结词。 ?若n =0，则称为0元函数。 ?（命题合式公式）定义： R) A n ?结构：论域和解释称为结构。 ?语义：符号指称的对象。公式所指称对象。合式公式的语义是其对应的逻辑真值。 ?（合式公式语义）设S是联结词的集合是{?，∧，∨，⊕，→，?}。由S生成的合式公式Q在真值赋值v下的真值指派v(Q)定义如下： ?⑴v(0)=0, v(1)=1。 ?⑵若Q是命题变元p，则v(A)= pv。 ?⑶若Q1,Q2是合式公式 ?若Q= ?Q1，则v(Q)= ?v(Q1) ?若Q=Q1 ∧ Q2，则v(Q)=v(Q1)∧ v(Q2)
?若Q=Q1∨Q2，则v(Q)=v(Q1)∨v(Q2) ?若Q=Q1→ Q2，则v(Q)=v(Q1)→ v(Q2) ?若Q=Q1 ? Q2，则v(Q)=v(Q1)? v(Q2) ?若Q=Q1⊕ Q2，则v(Q)=v(Q1)⊕ v(Q2) ?（真值赋值）由S生成的公式Q在真值赋值v下的真值v(Q)定义如下：?⑴若Q是S中的0元联结词c，则v(Q)=c。 ?⑵若Q是命题变元p，则v(Q)= pv。 ?⑶若Q是FQ1…,Qn，其中n≥1，F是S中的n元联结词，Qi是公式，则v(Q)=v(FQ1…Qn)=Fv(Q1)…v(Qn)。 ?（可满足与有效）定义1.7 设Q是公式。 ?⑴如果真值赋值v使得v(Q)=1，则称v满足Q。 中 F。 A1 Bn ?（逻辑推论）定义： ?若真值赋值v满足公式集合Γ中的每个公式，则称v满足Γ。若有真值赋值满足Γ，则称Γ是可满足的，否则称Γ是不可满足的。 ?设Γ是公式的集合，A是公式。如果每个满足Γ的真值赋值都满足A，则称A 是Γ的逻辑推论，记为Γ|=A。若Γ|=A不成立，记为Γ|≠A。 谓词逻辑
离散数学课程总结
离散数学课程总结 姓名： 学号： 班级：级计科系软件工程（）班 近年来，计算机科学与技术有了飞速发展，在生产与生活的各个领域都发挥着越来越重要的作用。离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程。 一、课程总结 本书的主要内容有数理逻辑、集合论、代数结构、组合数学、图论以及初等数论六部分，而我们主要学习的有第一部分数理逻辑、第二部分集合论以及第五部分图论，第三部分代数结构也学习了一部分。第一部分：数理逻辑 数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演
算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。 1.在命题逻辑的基本概念中学习了命题的真值及真值表、命题与联 结词、命题及其分类、联结词与复合命题、命题公式及其赋值。2.在命题逻辑的等值演算中主要学习了等值式与基本的等值式模式、 等值演算与置换规则、析取范式与合取范式，极大值和极小值，主析取范式与主合取范式、联结词完备集。 3.在命题逻辑的推理理论中主要学习了推理的正确与错误、推理的 形式结构、判断推理正确的方法、推理定律；自然推理系统P、形式系统的定义与分类、自然推理系统P，在P中构造证明：直接证明法、附加前提证明法、归谬法。 4.在一阶逻辑基本概念中主要学习了一阶逻辑命题符号化、个体词、 谓词、量词、一阶逻辑公式及其解释、一阶语言、合式公式及合式公式的解释、永真式、矛盾式、可满足式。 5.在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本 等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统N及其推理规则。 第二部分：集合论 在集合论中，主要学习了集合代数、二元关系和函数。 1.在集合代数中，学习了集合的基本概念：属于、包含、空集、元 集、幂集、全集；集合的基本运算：并、交、补相对、对称差等； 集合恒等式：集合运算的主要算律、恒等式的证明方法。
离散数学部分概念和公式总结(考试专用)
命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={
(完整word版)离散数学必备知识点总结.docx
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项 (m) 之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为 0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项 时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R 的顺序依次写； 6.真值表中值为 1 的项为极小项，值为0 的项为极大项； 7.n 个变元共有2n个极小项或极大项，这2n为(0~ 2n -1)刚好为化简完 后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法 (=>) ：真值表法；分析法 (假定前键为真推出后键 为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则， T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取 ^;
3.既有存在又有全称量，先消存在量，再消全称量； 第四章集合 1.N ，表示自然数集， 1,2,3 ??，不包括 0； 2.基：集合 A 中不同元素的个数， |A|； 3.集：定集合 A，以集合 A 的所有子集元素成的集合，P(A) ； 4.若集合 A 有 n 个元素，集 P(A) 有2 n个元素， |P(A)|= 2| A| = 2 n； 5.集合的分划： (等价关系 ) ①每一个分划都是由集合 A 的几个子集构成的集合； ② 几个子集相交空，相并全(A)； 6.集合的分划与覆盖的比： 分划：每个元素均出且出一次在子集中； 覆盖：只要求每个元素都出，没有要求只出一次； 第五章关系 1.若集合 A 有 m 个元素，集合 B 有 n 个元素，笛卡 A×B 的基数mn， A 到 B 上可以定2mn种不同的关系； 2.若集合 A 有 n 个元素， |A ×A|= n2，A 上有2n2个不同的关系； 3.全关系的性：自反性，称性，性； 空关系的性：反自反性，反称性，性；
离散数学课本定义和定理
第1章集合 集合的基本概念 1. 集合、元（元素）、有限集、无限集、空集 2. 表示集合的方法：列举法、描述法 3. 定义（子集）：给定集合A和B，如果集合A的任何一个元都是集合B中的元，则称集合A包含于B或B包含A，记为或，并称A为B的一个子集。 如果集合A和B满足，但B中有元不属于A，则称集合A真包含于B，记为，并且称A为B的一个真子集。 4. 定义（幂集）：给定集合A，以A的所有子集为元构成的一个集合，这个集合称为A的幂集，记为或 集合的运算 定义（并集）：设A和B是两个集合，则包含A和B的所有元，但不包含其他元的集合，称为A和B的并集，记为. ! 定义（交集）：A和B是两个集合，包含A和B的所有公共元，但不包含其他元的集合，称为A和B的交集，记为. 定义（不相交）：A和B是两个集合，如果它们满足，则称集合A和B是不相交的。定义（差集）：A和B是两个集合，属于A而不属于B的所有元构成集合，称为A和B的差集，记为. 定义（补集）：若A是空间E的集合，则E中所有不属于A的元构成的集合称为A的补集，记为. 定义（对称差）：A和B是两个集合，则定义A和B的对称差为 包含排斥原理 定理设为有限集，其元素个数分别为，则 。 定理设为有限集，其元素个数分别为，则 定理设为有限集，则 重要例题P11 例第2章二元关系 关系 定义（序偶）： 若和是两个元，将它们按前后顺序排列，记为，则成为一个序偶。
※对于序偶和，当且仅当并且时，才称和相等，记为 定义（有序元组）： 若是个元，将它们按前后顺序排列，记为，则成为一个有序元组（简称元组）。 : 定义（直接积）： 和是两个集合，则所有序偶的集合，称为和的直接积（或笛卡尔积），记为. 定义（直接积）： 设是个集合，，则所有元组的集合，称为的笛卡尔积（或直接积），记为. 定义（二元关系） 若和是两个集合，则的任何子集都定义了一个二元关系，称为上的二元关系。如果，则称为上的二元关系。 定义（恒等关系）： 设是上的二元关系，，则称是上的恒等关系。 定义（定义域、值域）：若是一个二元关系，则称 为的定义域。为的值域。 < 定义（自反）：设是集合上的关系，若对于任何 ．．，都有即则称关系是自反的。 定义（反自反）：设是集合上的关系，若对于任何，都满足,即对任何都不成立，则称关系是反自反的。 定义（对称）：设是集合上的关系，若对于任何，只要,就有,那么称关系是对称的。 定义（反对称）：设是集合上的关系，若对于任何，只要并且时,就有，那么称关系是对称的。 定义（传递）设是集合上的关系，若对于任何，只要并且时，就有，则称关系是传递的。 定理设是集合上的关系，若是反自反的和传递的，则是反对称的。 关系矩阵和关系图 定义无定理无 $ 关系的运算 定义（连接）：设为上的关系，为上的关系，则定义关系 称为关系和的连接或复合，有时也记为.
离散数学总结
离散数学总结 班级：学号：姓名： 临近期末各科课程已经结束，随之而来就是总结各科学习总结和对这门学科的建议。《离散数学》这门课程当然也不会例外了。经过一个学期的学习我发现《离散数学》是一门理论性非常强的课程，而且知识点非常多，定义和定理以及定律是数之不尽。 《离散数学》顾名思义就是一门数学，它是数学众多领域中的一个小分支，即使是一个小小的分支，但是它的内容也非常之多，同时也非常抽象。自认我的数学成绩还是不错的，但是面对《离散数学》我就头痛，书本里面很多知识点我都是似懂非懂地。但鉴于《离散数学》在计算科学中的重要性，这是一门必须牢牢掌握的课程。因此我也很无奈，只好硬着头皮去学好它了。 离散数学是理论性较强的学科，学习离散数学的关键是对离散数学(集合论、数理逻辑和图论)有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 《离散数学》的特点是： 1、知识点集中，概念和定理多。《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法等），同一个题也可能有几种方法。但是《离散数学》证明题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法，再者要善于总结。 在学习《离散数学》的过程中，我明白了理解概念是至关重要的。只有概念明确，才有可能将离散数学学好。但是初学者往往不能够将概念与现实世界中的事物联系起来，这是学好离散数学的基础，因此也是初学者面临的一个困难。只有克服它，你才能有可能学好《离散数学》。 学完这门课后，我总结到了，如果你想学得更好——你可以在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。而且必须及时复习和总结。 《离散数学》是一门数学科，大家都知道学数学就是要大量做数学，因此《离散数学》也不会例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学的思维方法。这一点非常重要。 课程虽然是上完了，但是老师你的教学方法独特而新颖，思想开化而先进，是个容易沟通的老师。有你带着我们学习《离散数学》就是我们不想学好，我想也是很难吧！就我来说每次上课时在我快要与“周公”会面之际，你突然一个笑话和雷人的语录，我和“周公”迫不得已就分开了。当我再次看到周公时，耳边
离散数学(本)主要概念
《离散数学(本)》主要概念、定理与方法 第1章集合及其运算 一、概念 集合（元素）——集合是一些具有确定的、可以区分的若干事件的全体，而集合中的事件称为元素．因此，集合是由若干元素组成的．若a是集合A中的元素，则称a属于A，记作a∈A；若a不是集合A中的元素，则称a不属于A，记作a?A． 定义1.1.1（子集）对任意两个集合A和B，若B中的每个元素都是A中的元素，则称B 为A的子集，记作B?A或A?B． 若B是A的子集，也称A包含B，或B被A包含．若B不是A的子集，即B?A不成立时，记作B?A． 定义1.1.2（集合相等）对任意两个集合A和B，若有A?B且B ?A，则称A与B相等，记作A= B． 定义1.1.3（真子集）对任意两个集合A和B，若B?A且B≠A，则称B为A的真子集，记作B?A或A?B． 定义1.1.4（空集）不含任何元素的集合称为空集，记作?． 空集的定义也可以写成 ≠} （1.1.1） ?={x x x n元集（m元子集）——含有n个元素的集合简称n元集，它的含有m（m≤n）个元素的子集叫做它的m元子集． 定义1.1.5（全集）在一个具体问题中，如果所涉及的集合都是某个集合的子集，则将这个集合称为全集，记作E． 定义1.1.6（幂集）设A是一个集合，由A的所有子集组成的集合，称为A的幂集，记作P(A)或2A． 定义1.2.1（并集、交集、差集、补集、对称差）设E为全集，A和B是E中任意两个子集． （1）所有属于A或属于B的元素组成的集合，称为集合A与B的并集，记作A?B．即 ∈}（1.2.1） {或x B A B x x A ?=∈ ?．即（2）既属于A又属于B的所有元素组成的集合，称为集合A与B的交集，记作A B ∈}（1.2.2） {且x B ?=∈ A B x x A 如果两个集合A和B没有公共元素，即A B ?=?，称为集合A与B不相交． -．即（3）属于A而不属于B的所有元素组成的集合，称为A与B的差集，记作A B -=∈? A B 且（1.2.3） x x A x B {} （4）由E中所有不属于A的元素组成的集合，称为A的补集，记作~A．即 ~A={} 且（1.2.4） x x E x A ∈? 补集~A可以看作全集E与集合A的差集，即~A = E -A． （5）集合(A - B )?(B - A )称为集合A和B的对称差，记作A⊕B．即 A⊕B = (A - B )?(B - A )．（1.2.5）对称差运算的另一种定义是 A⊕B = (A?B ) - (B ?A )．（1.2.5’） 二、定理与性质 集合包含关系的自反性：对于任意集合A，有A?A． 集合包含关系的反对称性：对任意两个集合A和B，若有A?B且B?A，则A=B． 集合包含关系的传递性：对任意三个集合A，B和C，若有A?B，B?C，则A?C．定理1.1.1空集是一切集合的子集． 定理1.1.1的推论空集是唯一的． 集合运算的交换律：A B B A ?=? ?=? A B B A
离散数学的概念总结
图论基本概念 重要定义： 有向图：每条边都是有向边的图。 无向图：每条边都是无向边的图。 混合图：既有有向边又有无向边的图。 自回路：一条边的两端重合。 重数：两顶点间若有几条边，称这些边为平行边，两顶点a,b间平行边的条数成为（a,b）的重数。 多重图：含有平行边的图。 简单图：不含平行边和自回路的图。 注意！一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。 定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D。称为的G定向图. 底图：如果把一个有向图的每一条有向边的方向都去掉，得无向图G称为的D底图。 逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。 赋权图：每条边都赋上了值。 出度：与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。入度：以该定点为终边的边数为入度。 特殊！度数为零的定点称为孤立点。度数为一的点为悬挂点。 无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn 完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。竟赛图：阶图中如果其底图是无向完全图，则程此有向完全图是竟塞图。 注意！n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2。 下面介召图两种操作：①删边：删去图中的某一条边但仍保留边的端点。 ②删点：删去图中某一点以及与这点相连的所有边。 子图：删去一条边或一点剩下的图。 生成子图：只删边不删点。 主子图：图中删去一点所得的子图称的主子图。 补图：设为阶间单无向图，在中添加一些边后，可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图。 重要定理： 定理5.1.1 设图G是具有n个顶点m条边的有向图，其中点集V={v,v, (v) deg+(vi)=deg-(vi)=m 定理5.1.2 设图G是具有n个顶点m条边的无向图，其中点集V={v,v,v, (v) deg(vi)=2m 推论在无向图中，度数为积数的顶点个数为偶数。 通路和富权图的最短通路 1通路和回路 基本概念： 通路的长度：通路中边的条数。 回路：如果通路中始点与终点相同。 简单通路：如果通路中各边都不相同。 基本通路：如果通路中各顶点都不相同。显然（基本通路一定是简单通路，但简单通路不一定是基本通路）
离散数学知识点总结
离散数学知识点总结 一、各章复习要求与重点 第一章 集 合 [复习知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图 3、序偶与迪卡尔积 本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求] 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题] P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析] 1、集合的概念 因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。 2、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析] 例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解 }}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A }}2,1{},2{},1{,{)(φρ=B 于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ
离散数学数理逻辑部分定义与概念
命题逻辑 1.（论域）定义：论域是一个数学系统，记为D。它由三部分组成： (1)一个非空对象集合S，每个对象也称为个体； (2)一个关于D的函数集合F； (3)一个关于D的关系集合R。 2.（逻辑联结词）定义： ?设n > 0，称{0, 1}n到{0, 1}的函数为n元函数，真值函数也称为联结词； ?若n = 0，则称为0元函数。 3.（命题合式公式）定义： (1)常元0和1是合式公式； (2)命题变元是合式公式； (3)若Q是合式公式，则(?Q)是合式公式； (4)若Q, R是合式公式，则(Q∧R)、(Q∨R)、(Q→R)、(Q?R)、(Q⊕R)是合式公式； (5)只有有限次应用(1)-(4)构成的公式是合式公式。 4.（生成公式）定义：设S是联结词的集合。由S生成的公式定义如下： (1)若c是S中的0元联结词，则c是由S生成的公式； (2)原子公式是由S生成的公式； (3)若n≥1，F是S中的n元联结词，A1, …, A n是由S生成的公式，则F A1…A n是由S 生成的公式。 5.（复杂度）公式A的复杂度表示为FC(A)。 ?常元复杂度为0； ?命题变元复杂度为0，如果P是命题变元，则FC(P) = 0； ?如果公式A = ?B，则FC(A) = FC(B) + 1； ?如果公式A = B1∧B2， 或A = B1∨B2， 或A = B1→B2， 或A = B1?B2， 或A = B1⊕B2， 则FC(A) = max{FC(B1), FC(B2)} + 1。 6.命题合式公式语义： ?论域：研究对象的集合。 ?解释：用论域的对象对应变元。 ?结构：论域和解释称为结构。 ?语义：符号指称的对象。公式所指称对象。合式公式的语义是其对应的逻辑真值。
离散数学概念
命题演算 ?命题（真值确定但不一定要知道真假，比如“存在外星人”是一个命题，它的真值确定，即使我们不知道真值） ?原始命题/原子命题 ?复合命题 ?逻辑连接词 ?否定/┐ ?合取/∧ ?析取/∨ ?条件/→（┐P∨Q） ?双条件（不好意思，双向箭头字符未找到，(P∧Q)∨(┐P∧┐Q)） ?真值表 ?命题公式/公式 ?命题变元 ?命题演算 ?等价（自反性、对称性、传递性，等价变换法俗称“少林派”） ?结合律 ?交换律 ?分配律 ?德·摩根律/反演律 ?双重否定率 ?代换 ?蕴含（自反性、反对称性、传递性，蕴含推理法俗称“武当派”，传递法俗称“隔山打牛”） ?对偶法则 ?对偶 ?不可兼析取（析取符上加一横，异或） ?逆条件（条件符上加字母c） ?与非/↑ ?或非/↓
?结合力（⑴┐⑵∧⑶∨、不可兼析取、↑、↓⑷→、逆条件⑸双条件） ?析取范式 ?合取范式 ?主析取范式（∑=m∨…） ?主合取范式（∏=M∧…） ?直接推演 ?P规则 ?T规则 ?CP规则（俗称“北冥神功”） ?间接推演/间接证明/反证法 谓词演算 ?谓词 ?个体 ?量词 ?全称量词（倒A，以下简写为V） ?存在量词（倒E，以下简写为E） ?自由变元 ?约束变元 ?作用域/辖域 ?改名 ?量词分配律（(Ex)[A(x)∨B(x)]<=>(Ex)A(x)∨(Ex)B(x)，(Vx)[A(x)∧B(x)]<=>(Vx)A(x)∧(Vx)B(x)） ?量词转换率（┐(Ex)A(x)<=>(Vx)┐A(x)） ?量词辖域扩张和收缩率 ?前束范式 ?全称指定规则/US ?全称推广规则/UG ?存在指定规则/ES
离散数学(高教)概念整理
数理逻辑 命题逻辑 命题p,q,r,s…… 非真即假的陈述句 命题的真值0 1 命题的陈述句所表达的判断结果 原子命题（简单命题） 不能被分解成更简单的命题 简单命题通过联结词联结而成的命题，称为复合命题 命题的符号化p:4是素数 用小写英文字母（如p:4是素数）表示命题。 用小写英文字母（如p:4是素数）表示原子命题，用联结词联结原子命题表示复合命题。联结词 否定连接词￢ 否p为真当且仅当p为假 合取联结词∧ p合取q为真当且仅当p，q同时为真（复合命题“p并且q”称为p与q的合取式） 析取联结词∨ p析取q为假当且仅当p，q同时为假（复合命题“p或q”称为p与q的析取式）
蕴含连接词→ p蕴含q为假当且仅当p为真，q为假。（复合命题“如果p,则q”（因为p所以q，除非q 才p）称为p与q的蕴含式，p是蕴含式的前件，q是蕴含式的后件）q是p的必要条件。 等价联结词? p等价q当且仅当，同时为真或假。（复合命题“p当且仅当q”称作p与q的等价式） 真值表 命题公式及其赋值 命题常项 原子命题（简单命题）的另一称呼，由于其真值确定 命题变项 真值可以变化的陈述句 合式公式（命题公式）A，B…… 命题变项用联结词和圆括号用一定逻辑关系连接起来的符号串，简称公式 赋值（解释） 给公式A中的每个命题变项各指定一个真值。 这组值使A为1，则称为成真赋值。
含n个命题变项的公式有2的n次方个不同赋值。 含n个命题变项的公式有2的2的n次方个不同真值表情况。 重言式（永真式） 命题公式A在各种赋值下取值均为真 矛盾式（永假式） 命题公式A在各种赋值下取值均为假 可满足式 命题公式A至少存在一个成真赋值 哑元 对公式A和B进行比较讨论，可知A和B共含有n个命题变项，其中A不含有的命题变项称为A的哑元，其取值不影响A的值 命题逻辑等值演算 等值式? 如果命题A和B有相同的真值表，则有命题A?B为重言式，这种情况下称A与B是等值的，记作A?B （重要）等值式模式 常用的16条命题间的等值模式，书p18
离散数学第一章知识点总结
离散数学第一章知识点总结（仅供参考） 1.判断给定的句子是否为命题的基本步骤：首先应是陈述句；其次要有唯一的真值。 例：（1）我正在说谎。 不是命题。因为无法判定其真假值，若假设它为假即我正在说谎，则意味着它的反为真，即我正在说实话，二者相矛盾；若假定它为真即我正在说实话，则意味着它的反为假， 我正在说谎，二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题 （2）x-y?＞2。 不是命题。因为x, y的值不确定，某些x, y使x?y＞2为真，某些x, y使x?y＞2 为假，即x?y＞2的真假随x, y的值的变化而变化。因此x?y＞2的真假无法确定，所以x?y ＞2不是命题。 2.命题可以分为两种类型：原子命题（不能再分解为更简单命题，又可称为简单命题）； 复合命题(通过联结词、标点符号将原子命题联结而成的命题） 3.命题常元：一个命题标识符如果表示确定的简单命题，就称为命题常元 命题变元：如果一个命题标识符只表示任意简单命题的位置标志，就称它为命题变元 注：当命题变元P用一个特定的简单命题取代时，P才能确定真值，这时也称对P进行指派 4.联接词：（1）否定联接词：﹁假为真，真为假；还可以用“非”、“不”、“没有”、“无”、 “并不”等多种方式表示否定 （2）合取联接词：∧一个为假就为假还可用“并且”、“同时”、“以及”、“既…… 又……”、“不但……而且……”、“虽然……但是……”等多种方 式表达合取 （3）析取联接词：∨一个为真就为真；一般用或表示 注：联结词∨是可兼或，因为当命题P和Q的真值都为真时， 其值也为真。但自然语言中的“或”既可以是“排斥或?” 也可以是“可兼或?”。 例晚上我们去教室学习或去电影院看电影。（排斥或） 例他可能数学考了100分或英语考了100分。（可兼或） 例刘静今天跑了200米或300米远。（既不表示“可兼或” 也不表示“排斥或”，它只是表示刘静所跑的大概路程， 因此它不是命题联结词，故例是原子命题。） （4）蕴涵联结词： ? 前真后假才为假；还可以用当……则……、因为……所 以……、仅当、只有……才……、除非……才……、除非……、 否则非……表示 (5)等价联接词：? 同真同假才为真；还可以用当且仅当、充分必要表示 5.命题公式：1）单个命题变元是合式公式，并简称为原子命题公式； 2）如果A是合式公式，那么(﹁A)也是合式公式； 3）如果A, B都是合式公式，那么(A∧B ), (A∨B ), (A?B ), (A B )都是 合式 公式； 4）当且仅当有限次地应用1), 2), 3)所得到的包含命题变元、联结词和括号 的字 符串是合式公式。 根据定义可知，P, (﹁P ), (P ? (P∨Q )), ((﹁P∧Q )∧P ), ((P ? Q ) ?R ) 都是命题公式。而 (∨P ), (P ?Q, (P ∨Q ) ? R )都不是命题公式。 6.n元命题公式：一个命题公式中总共包含有n个不同的命题变元