离散数学-复习和例题讲解.pptVIP

温故而知新!;数理逻辑;数理逻辑研究内容;熟练掌握将简单自然语句形式化的方法。

熟悉根本的等值公式，对于常用的等值公式，能在理解的根底上熟记并能在等值演算中灵活使用；

理解范式的概念深入理解主析取范式和主合取范式的构成，能够将命题公式熟练的化成相应的主析取范式和主合取范式；

理解推理形式的根本结构，掌握重言蕴涵的概念和主要结果；熟悉根本的推理公式，掌握推理公式的不同证明方法；理解根本的推理规那么，掌握使用推理规那么进行推理演算的方法；

重点解决使用谓词逻辑描述自然语句的表达问题，能够熟练的将一些自然语句进行形式化描述；

理解谓词逻辑公式等值的概念，掌握否认型等值式的不同形式及其证明方法；

熟悉谓词逻辑的根本推理公式，能够给出解释性的证明和其它推理公式正确性的判断；

理解谓词逻辑有关量词的四条推理规那么，掌握使用推理规那么进行推理演算的方法；;命题逻辑; 具有确切真值的陈述句称为命题

明年国庆节是晴天。

地球外的星球上也有人

１＋１＝１０。

x+y０。

一般来说，命题可分两种类型：

原子命题(简单命题)：不能再分解为更为简单命题的命题。

复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果...那么...”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。;命题联结词;｛┐，∨｝,｛┐，∧｝可以构成功能联结词集合。使用上述全功能联结词集合表达的命题公式类的系统常称为Boole代数系统

｛┐，→｝也可构成全功能联结词集合。该全功能联结词集合在研究逻辑系统的演绎与推理，以及在程序系统的研究中经常遇到。

｛↑｝,｛↓｝是全功能联结词集合。在大规模集成电路中有广泛的应用。;定义(命题公式)简称公式

单个原子公式本身是一个命题公式；

如P是公式，那么(┐P)也是命题公式；

如P，Q是公式，那么(P∧Q)、(P∨Q)、(P→Q)、(P?Q)也是命题公式；

命题公式仅由有限步使用规那么1-3后产生的结果。该公式常用符号G、H、…等表示。;公式G1称为永真公式(重言式)，如果在它的所有解释之下都为“真”。

设A:A(P1,P2,…,Pn),B:B(P1,P2,…,Pn)是两个命题公式,这里Pi(i=1,2,…,n)不一定在两公式中同时出现。

恒等式如果A?B是重言式,那么A与B对任何指派都有相同的真值。记为A=B,叫做逻辑恒等式,读做“A恒等于B”。;逻辑恒等式;; 首先，双条件词“?”是一种逻辑联结词，公式G?H是命题公式，其中“?”是一种逻辑运算，G?H的结果仍是一个命题公式。而逻辑等价“”那么是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH的结果不是命题公式。

其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式G?H是否是永真公式。;永真蕴含式

如果A→B是一永真式,那么称为永真蕴含式,记为A?B,读做“A永真蕴含B”。;“?”与“→”的区别;表1.2–2永真蕴含式; (代入规那么)(RuleofSubstitution)

一重言式中某个命题变元出现的每一处均代入以同一公式后,所得的仍是重言式。这条规那么之所以正确是由于重言式之值不依赖于变元的值的缘故。;范式;单个的命题变元和一些命题变元的否认是一个根本和、根本积、析取范式、合取范式。

单个的根本和是合取范式、假设省略最外层括号，单个的根本和也是析取范式

单个的根本积是析取范式,假设省略最外层括号，单个的根本积也是合取范式

析取范式、合取范式仅含联结词┐、∧、∨，且┐仅出现在命题变元前。;求一个命题公式的范式步骤如下：;定义1.3-4在n个变元的根本积中,假设每一个变元与其否认不同时存在,而两者之一必出现一次且仅出现一次,那么这种根本积叫极小项。

定义1.3-6在n个变元的根本和中,假设每一个变元与其否认不同时存在,而二者之一必出现一次且仅出现一次,那么这种根本和叫极大项。;对应情况如下:;我们把对应的十进制数当作足标,用mi表示这一项,即;

m0P∧Q∧R m1P∧Q∧R

m2P∧Q∧R m3P∧Q∧R

m4P∧Q∧R m5P∧Q∧R

m6P∧Q∧R m7P∧Q∧R;主析取范式和主合取范式;(1).求主析取范式

从真值表知，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项的析