离散作业材料

《离散作业材料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.命题及其表示1)判断哪些是命题（悖论，真值不能确定的，非陈述句）a)我正在说假话！b)X=2c)今天天气真好啊！2)分清简单命题与复合命题a)蓝色和黄色可以调配成绿色.b)蓝色和黄色是常用的颜色.3)区别相容或与排斥或a)李和平是山西人或陕西人.b)李冰选学英语或法语.4)蕴涵式的逻辑关系，准确地找出蕴涵式的前件与后件（只有……才，除非……否则非……，除非……才……，……仅当……）矚慫润厲钐瘗睞枥庑赖。a)除非4是奇数，否则5不是奇数.b)只有4是偶数，则5才是偶数.c)5是偶数仅当4是奇数.2.求复合公式的成真赋值，成假赋值，类型以及真值.（真值表法）3.等值式与基本等

2、值式4.等值演算，置换规则5.重言式与矛盾式的判别法A为重言式当且仅当,A为矛盾式当且仅当6.主析取范式与主合取范式1)求公式A的主析取范式的方法与步骤a)等值演算法1）求公式的析取范式；（1）消去除，，以外公式中出现的所有逻辑联结词.（2）将否定联结词消去或内移到各命题变元之前.如，；；.（3）利用分配律、结合律将公式转化为合取范式或析取范式.如，；.2）除去中所有永假的析取项；3）若的某个简单合取式中不含有某个命题变元，也不含，则将展成形式4）将重复出现的命题变元、矛盾式及重复出现的极小项都消去.5）将极小项按顺序排列.a)真值表法b)由主合取范式求析取范式主析取范式的用

3、途1.求公式的成真赋值与成假赋值2.判断公式的类型3.判断公式A与B是否等值.4.解实际问题2.推理的形式结构（）3.判断推理是否正确的方法1)真值表法2)等值演算法3)主析取范式法4.推理定律（9条）5.在自然推理系统P中构造证明直接证明法附加前提证明法归谬法6.一阶逻辑命题的符号化a)“D中所有x都有性质F”，符号化为b)“D中有的x有性质F”，符号化为c)“对D中所有x而言，如果有性质F，x就有性质G”，符号化为d)“对D中有的x有性质F且有性质G”，符号化为e)“对于D中所有x,y而言，若x有性质F，y有性质G，则x与y就有关系H”,符号化为f)“对于D中所有x而言，

4、若x有性质F，就存在y有性质G，使得x与y有关系H”，符号化为g)“存在着D中x有性质F，并且对D中所有y而言，如果y有性质G，则x与y就有关系H”，符号化为7.一阶逻辑公式及解释8.一阶逻辑等值式与置换规则1)等值式1)基本的等值式a)命题逻辑中基本等值式的代换实例.b)一阶逻辑中重要的等值式2.求一阶逻辑前束范式3.约束变元与自由变元4.一阶逻辑的推理理论（）5.一阶逻辑中重要的推理定律6.自然推理系统F第二部分1.集合的基本概念2.集合的基本运算3.有穷集合元素的计数（文氏图或包含排斥原理）4.鸽笼原理的应用5.集合恒等式（基本证明方法）a)命题演算法b)利用包含哦传递

5、性c)反证法命题演算证明法的书写规范(以下的X和Y代表集合公式)（1）证XÍY任取x，xÎXÞ…ÞxÎY（2）证X=Y方法一分别证明XÍY和YÍX方法二任取x，xÎXÛ…ÛxÎY注意：在使用方法二的格式时，必须保证每步推理都是充分必要的6.有序对与笛卡尔积7.二元关系8.关系的表示（关系矩阵，关系图）9.关系的性质（自反，反自反，对称，反对称，传递）表格（1）若"x(x∈A→ÎR),则称R在A上是自反的（2）若"x(x∈A→ÏR),则称R在A上是反自反的.（3）若"x"y(x,y∈A∈R→∈R),则称R为A上对称的关系.（4）若"x"y

6、(x,y∈A∧∈R∧∈R→x=y),则称R为A上的反对称关系.（1）"x"y"z(x,y,z∈A∧∈R∧∈R→∈R),则称R是A上的传递关系..聞創沟燴鐺險爱氇谴净。证明：R在A上自反任取x，有x∈AÞ…………………ÞÎR前提推理过程结论R在A上对称任取，有ÎRÞ…………………ÞÎRR在A上反对称任取，有ÎR∧ÎRÞ…………………Þx=yR在A上传递任取，有ÎR∧ÎRÞ…………………ÞÎR残骛楼諍锩瀨濟溆塹籟

7、。1.关系运算的定义（定义域，值域，域，逆，右复合，限制，像，幂，自反闭包，对称闭包，传递闭包及其构造）2.关系运算的性质3.等价关系与划分（等价关系证明，等价类，等价类的性质，商集，集合A的划分，一一对应）4.偏序关系与偏序集（哈斯图，特殊元素）5.函数（满射，单射，双射第四部分1.图的定义（平凡图，零图，完全图，子图，补图等）2.图的矩阵表示（邻接矩阵，可达矩阵），通路与回路的计数3.欧拉图，哈密顿图，偶图，平面图定义及判别4.结点的度数及其相关性质（握手定理）；5.树、非同构树、生成树、最小生成树