离散复习提纲

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

A为重言式当且仅当,A为矛盾式当且仅当主析取范式与主合取范式求公式A的主析取范式的方法与步骤等值演算法1）求公式的析取范式；（1）消去除，，以外公式中出现的所有逻辑联结词。（2）将否定联结词消去或内移到各命题变元之前。如，；；。（3）利用分配律、结合律将公式转化为合取范式或析取范式。如，；。2）除去中所有永假的析取项；3）若的某个简单合取式中不含有某个命题变元，也不含，则将展成形式4）将重复出现的命题变元、矛盾式及重复出现的极小项都消去。5）将极小项按顺序排列。真值表法由主合取范式求析取范式主析取范式的用途求公式的成真赋值与成假赋值判断公式的类型判断公式A与B是否等值。解实际问题推理的形式结构（）判断推理是否正确的方法真值表法等值演算法主析取范式法推理定律（9条）在自然推理系统P中构造证明直接证明法附加前提证明法归谬法一阶逻辑命题的符号化“D中所有x都有性质F”，符号化为“D中有的x有性质F”，符号化为“对D中所有x而言，如果有性质F，x就有性质G”，符号化为“对D中有的x有性质F且有性质G”，符号化为“对于D中所有x,y而言，若x有性质F，y有性质G，则x与y就有关系H”,符号化为“对于D中所有x而言，若x有性质F，就存在y有性质G，使得x与y有关系H”，符号化为“存在着D中x有性质F，并且对D中所有y而言，如果y有性质G，则x与y就有关系H”，符号化为一阶逻辑公式及解释一阶逻辑等值式与置换规则等值式基本的等值式命题逻辑中基本等值式的代换实例。一阶逻辑中重要的等值式求一阶逻辑前束范式约束变元与自由变元一阶逻辑的推理理论（）一阶逻辑中重要的推理定律自然推理系统F第二部分集合的基本概念集合的基本运算有穷集合元素的计数（文氏图或包含排斥原理）鸽笼原理的应用集合恒等式（基本证明方法）命题演算法利用包含哦传递性反证法命题演算证明法的书写规范(以下的X和Y代表集合公式)（1）证XY任取x，xX…xY（2）证X=Y方法一分别证明XY和YX方法二任取x，xX…xY注意：在使用方法二的格式时，必须保证每步推理都是充分必要的有序对与笛卡尔积二元关系关系的表示（关系矩阵，关系图）关系的性质（自反，反自反，对称，反对称，传递）表格若x(x∈A→<x,x>R),则称R在A上是自反的若x(x∈A→<x,x>R),则称R在A上是反自反的.若xy(x,y∈A<x,y>∈R→<y,x>∈R),则称R为A上对称的关系.若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),则称R为A上的反对称关系.xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上的传递关系.。证明：R在A上自反

任取x，有

x∈A…<x,x>R

前提推理过程结论

R在A上对称

任取<x,y>，有

<x,y>R…<y,x>R

R在A上反对称

任取<x,y>，有

<x,y>R∧<y,x>R…x=y

R在A上传递

任取<x,y>，<y,z>有

<x,y>R∧<y,z>R…<x,z>R

关系运算的定义（定义域，值域，域，逆，复合，限制，像，幂，自反闭包，对称闭包，传递闭包及其构造）关系运算的性质等价关系与划分（等价关系证明，等价类，等价类的性质，商集，集合A的划分，一一对应）偏序关系与偏序集（哈斯图，特殊元素）*函数（满射，单射，双射第三部分（×）代数系统，运算规律，特殊元的概念及计算，半群，群概念及判别格的定义格的偏序集定义格的代数系统定义*格的性质对偶原理格的运算性质偏序与运算的关系保序性质*子格与子格的判别

*子格判别：S非空，且S关于格L中的运算封闭。分配格，有界格，有补格的概念分配格的判别方法：根据定义判别：注意在证明L为分配格时，只须证明其中的一个等式即可设L是格，则L是分配个当且仅当L不含有与钻石格或五角格同构的子格。格L是分配格当且仅当第四部分图的定义（平凡图，零图，基图，完全图与竞赛图，子图，补图）图的矩阵表示（关联矩阵，邻