离散数学(高教)概念整理

《离散数学(高教)概念整理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数理逻辑命题逻辑命题p,q,r,s……非真即假的陈述句命题的真值01命题的陈述句所表达的判断结果原子命题（简单命题）不能被分解成更简单的命题简单命题通过联结词联结而成的命题，称为复合命题命题的符号化p:4是素数用小写英文字母（如p:4是素数）表示命题。用小写英文字母（如p:4是素数）表示原子命题，用联结词联结原子命题表示复合命题。联结词否定连接词￢否p为真当且仅当p为假合取联结词∧p合取q为真当且仅当p，q同时为真（复合命题“p并且q”称为p与q的合取式）析取联结词∨p析取q为假当且仅当p，q同时为假（复合命题“p或q”称为p与q的析取式）39蕴含连接词→p蕴含q为假当且仅当p为

2、真，q为假。（复合命题“如果p,则q”（因为p所以q，除非q才p）称为p与q的蕴含式，p是蕴含式的前件，q是蕴含式的后件）q是p的必要条件。等价联结词↔p等价q当且仅当，同时为真或假。（复合命题“p当且仅当q”称作p与q的等价式）真值表命题公式及其赋值命题常项原子命题（简单命题）的另一称呼，由于其真值确定命题变项真值可以变化的陈述句合式公式（命题公式）A，B……命题变项用联结词和圆括号用一定逻辑关系连接起来的符号串，简称公式赋值（解释）给公式A中的每个命题变项各指定一个真值。这组值使A为1，则称为成真赋值。39含n个命题变项的公式有2的n次方个不同赋值。含n个命题变项的公式有2的2的n次方

3、个不同真值表情况。重言式（永真式）命题公式A在各种赋值下取值均为真矛盾式（永假式）命题公式A在各种赋值下取值均为假可满足式命题公式A至少存在一个成真赋值哑元对公式A和B进行比较讨论，可知A和B共含有n个命题变项，其中A不含有的命题变项称为A的哑元，其取值不影响A的值命题逻辑等值演算等值式⇔ 如果命题A和B有相同的真值表，则有命题A↔B为重言式，这种情况下称A与B是等值的，记作A⇔B（重要）等值式模式常用的16条命题间的等值模式，书p1839析取范式与合取范式文字命题变项及其否定的统称简单析取式，简单合取式由有限个文字构成的析取式，合取式析取范式，合取范式由有限个简单合取式的析取构成的命题公

4、式，称为析取范式。同理为合取范式。命题公式的析取或合取范式一般不唯一极小项，极大项miMi简单合取式中的命题变项及它的否定式恰好出现一次，并按照下标拍好，这样的简单合取式叫做极小项。同理为极大项。n个命题变项可以产生2的n次方个极小项，每个极小项都有且仅有一个成真赋值，这一组成真赋值（01组成）转化为对应的十进制数i，将这个极小项表示为mi类似的，极大项为Mi主析取范式m0∨m1∨m3∨m7主合取范式所有简单合取式都是极小项的析取式，这是唯一的主析取范式。同理。联结词的完备集n元真值函数F函数F的自变量为n个命题变项，值域为{0,1},这样的函数叫n元真值函数。n个命题变项一共可以构成2的

5、2的n次方个不同的真值函数。每个真值函数与唯一的一个主析取范式（主合取范式）等值，同时它们都等值于无穷多个等值的命题公式。39联结词完备集S={￢,∨}s是一个联结词集合，任何n元真值函数都可以仅用s中的联结词构成的公式表示.s就是联结词完备集。命题逻辑的推理理论推理{A1,…Ak}┠B是指从前提触发推出结论的思维过程。前提是已知的命题公式集合，结论是推出的命题公式。有效的结论命题集合Ai的合取式有0和1两种取值，只要不出现某一种赋值情况下命题集合为假，结论B为真。那么就称结论B是有效的结论。称这一种推理是正确的。证明是由一个描述推理过程的命题公式序列形式系统I书p46自然推理系统P数p4

6、7主要是用来在这个系统下构造推理的证明附加前提证明法结论为蕴含式时，可以把前件作为推理前提，使结论为后件归谬法使结论的否命题作为前提能退出矛盾，则证明39一阶逻辑基本概念一阶命题符号化∀x(M(x)→F(x))1个体词a,b,x,y……研究对象中独立存在的客体。取值范围叫做“个体域”。默认个体域为“全总个体域”2谓词F（ａ）　G（ａ，ｂ）　Ｈ……刻画个体词性质或关系的词。比如说“是无理数”。含有ｎ个命题变项的谓词叫做ｎ元谓词。以个体域为定义域，｛０,１｝为值域的ｎ元函数或关系。３量词∀∃　全称量词“任意”∀存在量词“存在”一阶语言（花体Ｉ）由抽象符号构成的用于一阶逻辑的形式语言。项个体常项

7、，个体变项，ｎ元函数（自变量为项）是花体Ｉ的项。指导变元　量词的辖域例如∀ｘＡ，ｘ就叫做指导变元，Ａ是量词的辖域，在辖域中ｘ的所有出现称为约束出现，其他变项叫自由出现合式公式（谓词公式）一阶语言下的合式公式。39闭式（封闭的公式）公式中不含自由出现的个体变项.解释I解释就是对抽象一阶语言的在I的具体含义，包括四个部分：①非空个体域D1②每一个个体常项在D1中的对应③每一个n元函数在D1上的对应④每一个谓词符号在D1上的对