3J 贾利新-01-0415-离散数学命题的若干技巧2015-OK

离散数学一、逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。

联接词：∧、∨、→、↔、¬。

记住“p仅当q”意思是“如果p，则q”，即p→。

记住“q除非p”意思是“¬p→q”。

会考察条件语句翻译成汉语。

系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。

1.3命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。

谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如∀x>0P(x)。

当论域中的元素可以一一列举，那么∀xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。

同理，∃xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。

两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如∀x（P(x)∧Q(x))和(∀xP(x))∧(∀xQ(x))。

量词表达式的否定：¬∀xP(x) ⇔∃x¬P(x)，¬∃xP(x) ⇔∀x¬P(x)。

1.5量词嵌套我们采用循环的思考方法。

量词顺序的不同会影响结果。

语句到嵌套量词语句的翻译，注意论域。

嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。

1.6推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。

但有效论证二、集合、函数、序列、与矩阵2.1集合∈说的是元素与集合的关系，⊆说的是集合与集合的关系。

常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。

A和B相等当仅当∀x(x∈A↔x∈B)；A是B的子集当仅当∀x(x∈A→x∈B)；A是B的真子集当仅当∀x(x∈A→x∈B)∧∃x(x∉A∧x∈B)。

幂集：集合元素的所有可能组合，肯定有∅何它自身。

离散数学复习要点离散数学是数学的一个分支领域，主要研究离散的结构和离散情形下的数学对象及其相关性质。

它与连续数学不同，离散数学的对象是离散的，如集合、图、布尔代数等。

在计算机科学、信息科学、通信工程等领域中，离散数学的理论和方法被广泛应用。

以下是离散数学的一些重要的复习要点：1.集合论：集合是离散数学的基础，集合的基本运算如交、并、差等，以及集合的基本性质如并集和交集的结合律、分配律等，都是需要复习的内容。

此外，还需要了解集合的基数和幂集等概念。

2.命题逻辑：命题是一个可以判断真假的陈述句，命题逻辑是研究命题及其逻辑关系的数学体系。

需要复习的内容包括命题的逻辑运算，如非、与、或、异或等，以及逻辑等价、逻辑推理等。

3.谓词逻辑：谓词逻辑是对自然语言中的谓词进行形式化表示和推理的系统。

复习重点包括一阶谓词逻辑的基本概念，如谓词、量词、域、项等，以及谓词的合取、析取、全称量词和存在量词等逻辑联结词的语义。

4.图论：图论是研究图及其性质的数学分支。

需要复习的内容包括图的基本概念，如顶点、边、路径、圈等，以及图的表示方法、图的遍历算法、连通图、树等。

5. 网络流模型：网络流模型是研究流动网络的数学方法，主要包括最大流、最小割等问题。

需要复习的内容包括网络的基本概念，如容量、割、流等，以及Ford-Fulkerson算法等解决网络流问题的方法。

6.布尔代数：布尔代数是一种关于逻辑运算的代数系统，常用于电路设计和逻辑推理。

需要复习的内容包括布尔代数的基本运算，如与、或、非等，以及布尔函数的最小项与最大项表示、卡诺图等。

7.组合数学：组合数学是研究离散中的计数问题的数学分支。

需要复习的内容包括排列、组合、多元排列组合等的计数方法，如乘法原理、加法原理、排列组合的顺序问题等。

8.代数系统：代数系统是研究代数结构及其性质的数学分支，包括群、环、域等。

需要复习的内容包括群的基本概念和性质，如封闭性、结合律、单位元、逆元等。

离散数学命题符号一、离散数学命题符号的定义在离散数学中，命题是一个陈述句，可以判断为真或为假。

为了准确地表示命题，在离散数学中引入了命题符号。

命题符号主要用于表示命题的逻辑关系，以及对命题的运算。

1. 命题变量和命题符号离散数学中，命题变量被表示为字母，常用的命题变量包括p、q、r等。

命题符号则用来表示对命题变量的操作和运算关系。

常用的命题符号包括逻辑与（∧）、逻辑或（∨）、非（¬）等。

2. 逻辑连接词离散数学中，逻辑连接词用于将多个命题连接起来，形成复合命题。

常见的逻辑连接词有：- 逻辑与（∧）：表示两个命题都为真时，复合命题为真；否则为假。

- 逻辑或（∨）：表示两个命题至少一个为真时，复合命题为真；否则为假。

- 非（¬）：表示对命题的否定。

3. 命题符号的优先级为了保证命题的运算顺序和结果的准确性，在离散数学中，命题符号有一定的优先级。

常见的命题符号优先级从高到低依次为：- ¬（非）- ∧（逻辑与）- ∨（逻辑或）二、离散数学命题符号的应用1. 命题的合取和析取在离散数学中，逻辑与（∧）和逻辑或（∨）的运算被广泛应用于命题的合取和析取。

- 合取：当多个命题同时为真时，可以使用合取运算符（∧）将这些命题合并成为一个复合命题。

例如，当p表示“今天下雨”、q表示“今天天气阴沉”时，合取命题p∧q表示“今天同时下雨并且天气阴沉”。

- 析取：当多个命题至少一个为真时，可以使用析取运算符（∨）将这些命题合并成为一个复合命题。

例如，当p表示“今天下雨”、q表示“今天天气阴沉”时，析取命题p∨q表示“今天下雨或者天气阴沉”。

2. 命题的否定在离散数学中，非（¬）运算符常用于对命题的否定。

如果p为真，则¬p为假；如果p为假，则¬p为真。

例如，若p表示“今天下雨”，则¬p表示“今天不下雨”。

3. 命题的复合运算通过组合使用逻辑连接词和命题符号，可以对多个命题进行复合运算。

注意/技巧：析取符号为V，大写字母Vx + y = 3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。

也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。

选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（→）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P→Q只有P，才Q等价于非P→非Q，也就是Q→PP→Q特殊的表达形式：P仅当Q、Q每当P双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式）、矛盾式（永假式）、偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。

如果命题公式A为重言式，那么A⇔T常见的命题等价公式：需要背过被标出的，尽量去理解。

关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。

当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。

蕴含:若A→B是一个重言式，就称作A蕴含B，记作A⇒B常见的蕴含公式的运用方法同上面的命题等价公式证明A⇒B：①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当A⇒B且B⇒A时，A⇔B，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或）、或非（析取的否定）、与非（合取的否定）任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式）。

离散数学证明方法有哪些离散数学中的概念和定理偏多，思维较抽象，证明强调技巧性但改变不多。

下面我给大家整理了关于离散数学证明方法，盼望对你有协助!1离散数学证明方法离散数学是现代数学的一个重要分支，是计算机科学中根底理论的核心课程。

离散数学以探究离散量的构造和相互间的关系为主要目标，其探究对象一般地是有限个或可数个元素，因此他充分描述了计算机科学离散性的特点。

2离散数学证明方法干脆证明法干脆证明法是最常见的一种证明的方法，它通常用作证明某一类东西具有一样的性质，或者符合某一些性质必定是某一类东西。

干脆证明法有两种思路，第一种是从确定的条件来推出结论，即看到条件的时候，并不知道它怎么可以推出结论，那么可以先从确定条件遵照定理推出一些中间的条件(这一步可能是没有目的的，要看看从确定的条件中能够推出些什么)，接着，选择可以推出结论的那个条件接着往下推演;另外一种是从结论反推回条件，即看到结论的时候，首先要反推一下，看看从哪些条件可以得出这个结论(这一步也可能是没有目的的，因为并不知道要用到哪个条件)，以此类推始终到确定的条件。

通常这两种思路是同时进展的。

反证法反证法是证明那些“存在某一个例子或性质”，“不具有某一种的性质”，“仅存在”等的题目。

它的方法是首先假设出所求命题的否命题，接着依据这个否命题和确定条件进展推演，直至推出与确定条件或定理相冲突，那么认为假设是不成立的，因此，命题得证。

构造法证明“存在某一个例子或性质”的题目，我们可以用反证法，假设不存在这样的例子和性质，然后推出冲突，也可以干脆构造出这么一个例子就可以了。

这就是构造法，通常这样的题目在图论中多见。

值得留意的是，有一些题目其实也是本类型的题目，只不过比拟隐藏罢了，像证明两个集合等势，事实上就是证明“两个集合中存在一个双射”，我们即可以假设不存在，用反证法，也可以干脆构造出这个双射。

数学归纳法数学归纳法是证明与自然数有关的题目，而且这一类型的题目可以递推。

离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，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、界说和定理多。

离散数学是建立在很多界说上面的逻辑推理学科。

因而对概念的了解是咱们学习这门学科的中心。

在这些概念的基础上，格外要注意概念之间的联络，而描绘这些联络的实体则是很多的定理和性质。

●证实等价联系：即要证实联系有自反、对称、传递的性质。

●证实偏序联系：即要证实联系有自反、反对称、传递的性质。

(特殊联系的证实就列出来两种，要证实剩余的几种只需要联系界说来进行)。

●证实满射：函数f：XY，即要证实关于恣意的yY，都有x或许关于恣意的f(x1)=f(x2)，则有x1=x2。

●证实调集等势：即证实两个调集中存在双射。

有三种情况：榜首、证实两个详细的调集等势，用结构法，或许直接结构一个双射，或许结构两个调集彼此间的入射;第二、已知某个调集的基数，假如为?，就设它和R之间存在双射f，然后通过f的性质推出别的的双射，因而等势;假如为?0，则设和N之间存在双射;第三、已知两个调集等势，然后再证实别的的两个调集等势，这时，先设已知的两个调集存在双射，然后依据剩余题设条件证实要证的两个调集存在双射。

●证实群：即要证实代数系统关闭、可联系、有幺元和逆元。

(相同，这一有些能够作为证实题的概念更多，要联系界说把它们全部搞透彻)。

●证实子群：尽管子群的证实定理有两个，但假如考证实子群的话，一般是第二个定理，即设是群，S是G的非空子集，假如关于S中的恣意元素a和b有a*b-1是的子群。

关于有限子群，则可考虑榜首个定理。

●证实规范子群：若是一个子群，H是G的一个子集，即要证实关于恣意的aG，有aH=Ha，或许关于恣意的hH，有a-1 *h*aH。

这是最常见的标题中所使用的办法。

●证实格和子格：子格没有条件，因而和证实格相同，证实调集中恣意两个元素的最大元和最小元都在调集中。