离散数学期末知识点总结

总结 离散数学知识点

第二章 命题逻辑

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、

下列各选项错误的是

A、? ? ? B、? ? ? C、? ?{ ?} D、? ? {? }

2、命题公式 (p∧q) →p 是 A、矛盾式 B、重言式 C、可满足式 D、等值式

3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是

A、等价关系 B、偏序关系 C、全序关系 D、都不是

4、下列句子中那个是假命题？ A、

是无理数.

B、2 + 5 ＝8.

C、x + 5 ＞ 3 D、请不要讲话！ 5、下列各选项错误的是？ A、? ? ? B、? ? {? } C、? ?{ ?} D、{? } ? ?

6、命题公式 p→（p?q?r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式

7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是

8、设D=,则V={a,b,c,d,e,f},R={ ,,,,},有向图D为 A、强连通 B、单向连通 C、弱连通

D、不连通的

9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1 ?R2 B、R1-1 C、R1 ?R2 D、R1 -R2

10、连通平面图G有4个

离散数学

一、填空20%（每空2分）：

1．若对命题P赋值1，Q赋值0，则命题P?Q的真值为 。 2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为 3．公式?(P?Q)?(P??(Q??S))的对偶公式为

4．图 的对偶图为

5．若关系R是等价关系，则R满足 性质。 6．关系R的传递闭包t (R) = 。 7．代数系统?A,??是群，则它满足 8．设?A,?,??和?B,?,??是两代数系统，f是从?A,?,??到?B,?,??的同态映射，则f具有 性质。

离散数学期末复习各个章节要点纲要（及定理）

离散数学定义定理

1.3.1命题演算的合式公式规定为： （1）单个命题变元本身是一个合式公式。 （2）如果A是合式公式，那么┐A是合式公式。

（3）如果A和B是合式公式，那么（A∨B）、（A∧B）、（A→B）、（A?B）、都是合式公式。 （4）当且仅当有限次地应用（1）（2）（3）所得到的包含命题变元，连接词和圆括号的符号串是合式公式。

1.3.2 设Ai是公式A的一部分，且Ai是一个合式公式，称Ai是A的子公式。

1.3.3 设P为一命题公式，P1,P2,……，Pn为出现在P中的所有命题变元，对P1,P2,……，Pn指定一组真值称为对P的一种指派。若指定的一种指派，使P的值为真，则称这组指派为成真指派。若指定的一种指派，使P的值为假，则称这种指派为成假指派。 含n个命题变元的命题公式，共有2n个指派。

1.3.4 给定两个命题公式A和B，设P1,P2,……，Pn为所有出现于A和B中的原子变元，若给P1,P2,……，Pn任一组真值指派，A和B的真值都相同，称A和B是等价的，记做A <=>B。

1.3.5 设A为一命题公式，若A在它的各种指派情况下，其取值均为真，则称A为重言式或永真式。 1.3.6

《离散数学》期末考试试卷（A卷）

--------------------------------------------------------------------------------------------------------------------------------------------------- 03．A?{?,{a},{b},{a,b}}上的包含关系为?，则子集C?{{a},{b}}的极大元为

＿＿＿＿，极小元为＿＿＿＿，上界为＿＿＿＿，下界为＿＿＿＿，最大元为＿＿＿， 最小元为＿＿＿（若没有填无）。 04．设A?{a,b}，则A上共有＿＿＿个不同的等价关系。

05．有一个函数f:X?Y，若要使f有逆函数，f就必须是＿＿＿。

三、演算题（每小题10分，总30分）

年级 专业 姓名 学号 座位号

大登

一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题干后的括号内。每题3分，共18分） 01．下列语句中，真命题是（ ）

A、我正在说谎； B、若1?2?3，则雪是黑的； C、这句话

离散数学期末复习题

一、选择题

1、永真式的否定是（2） (2) 永假式

2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1) (1)P?Q?R

3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为⑵ ⑵P??Q(3)

提示：R??(P?Q)?P??Q 4、下列表达式错误的有⑷ ⑷P?(?P?Q)?P?Q 5、下列表达式正确的有⑷ ⑷?(P?Q)??Q

6、下列联接词运算不可交换的是(3) (3)?

6、设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为⑷ ⑷?x(M(x)??y(F(y)?H(x,y))

7、设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些

老

师”的逻辑符号化为⑵

⑵?x(L(x)??y(J(y)?A(x,y)))

8、谓词公式?x(P(x)??yR(y))?Q(x)中的 x是⑶ ⑶既是自由变元又是约束变元 9、下列表达式错误的有⑴

⑴?x(A(x)?B(x))??xA(x)??xB(x)

离散数学期末复习题

一、选择题

1、永真式的否定是（2） (2) 永假式

2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1) (1)P?Q?R

3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为⑵ ⑵P??Q(3)

提示：R??(P?Q)?P??Q 4、下列表达式错误的有⑷ ⑷P?(?P?Q)?P?Q 5、下列表达式正确的有⑷ ⑷?(P?Q)??Q

6、下列联接词运算不可交换的是(3) (3)?

6、设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为⑷ ⑷?x(M(x)??y(F(y)?H(x,y))

7、设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些

老

师”的逻辑符号化为⑵

⑵?x(L(x)??y(J(y)?A(x,y)))

8、谓词公式?x(P(x)??yR(y))?Q(x)中的 x是⑶ ⑶既是自由变元又是约束变元 9、下列表达式错误的有⑴

⑴?x(A(x)?B(x))??xA(x)??xB(x)

1 / 6

一、 命题逻辑部分

1．计算真值表、并由此写出主析取与主合取范式(一个命题公式的主范式具有唯一的表示形式，这样可以精减一个推理系统，去掉多余的等价的前提。其唯一性借助于小项或大项的设计，一个公式中所用到的小项或大项个数与其真值表中所对应的1或0的个数相对应，不能多也不能少)。注意：真值表与公式有什么区别？

2．设 A 、B 是两个命题公式，证明：

a) A B 当且仅当A B 是永真式。b) A B 的充要条件是A B 且B A 。

等价与蕴涵是对两个公式进行比较的概念，性质b)说明两者之间的关系，相对而言蕴涵比等价更重要。与上面两个性质相关联的一个等价公式是：A B A →B ∧B →A.3．证明 P →(Q →R )?Q →(P →R )? ┐R →(Q → ┐P ) 4．证明从前提P →Q ，┐(Q ∨R)可演绎出┐P .

5．证明R →S 可从前提P →(Q →S)，┐R ∨P 和Q 推出。 ├ 6、使用推理规则或归结推理，论证推理形式 1) P →Q, R →?Q ,R ∨S, S →?Q ├?P

2)?P ?Q, S →?Q, ?R, R ∨S ├ P

二、 谓词逻辑

1、 写出谓词的含义、一个谓词公式的解释应包含什么

离散数学第一章知识点总结（仅供参考）

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）否定联

高二数学期末复习知识点总结

一、直线与圆：

、直线的倾斜角?的范围是[0,?）

在平面直角坐标系中，对于一条与x轴相交的直线l，如果把x轴绕着交点按逆时针方向转到和直线l重合时所转的最小正角记为?，?就叫做直线的倾斜角。当直线l与x轴重合或平行时，规定倾斜角为；

、斜率：已知直线的倾斜角为α，且α≠°，则斜率α.

过两点（）,()的直线的斜率( )()，另外切线的斜率用求导的方法。 、直线方程：⑴点斜式：直线过点(x0,y0)斜率为k，则直线方程为

y?y0?k(x?x0), ⑵斜截式：直线在y轴上的截距为b和斜率k，则直线方程为y?kx?b

、l1:y?k1x?b1，l2:y?k2x?b2,①l1∥l2?k1?k2,b1?b2； ②l1?l2?k1k2??1.

直线l1:A1x?B1y?C1、点P(x0,y0)到直线两条平行线

?0与直线l2:A2x?B2y?C2?0的位置关系： （）平行? 注意检验 （）垂直? 1A

Ax?By?C?0的距离公式d?Ax0?By0?CA?B22；

A?B22222、圆的标准方程：(x?a)?(y?b)?r.⑵圆的一般方程：x?y?Dx?Ey?F?0

注意能将标准方程化为一般方程

、过圆外一点作圆的切线