离散数学笔记（特级教师精心整理）
第一章命题逻辑
内容：
命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的：
1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。
2．熟练掌握常用的基本等价式及其应用。
3．熟练掌握（主）析/合取范式的求法及其应用。
4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。
5．熟练掌握形式演绎的方法。
教学重点：
1．命题的概念及判断
2．联结词，命题的翻译
3．主析（合）取范式的求法
4．逻辑推理
教学难点：
1．主析（合）取范式的求法
2．逻辑推理
1.1命题及其表示法
1.1.1 命题的概念
数理逻辑将能够判断真假的陈述句称作命题。
1.1.2 命题的表示
命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。
1.2命题联结词
（1） P↑P?﹁（P∧P）?﹁P；
（2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。
（1）P↓P?﹁（P∨Q）?﹁P；
（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q；
（3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。
1.3 命题公式、翻译与解释
1.3.1 命题公式
定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。
例如，下面的符号串都是公式：
（（（（﹁P）∧Q）→R）∨S）
（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R
以下符号串都不是公式：
（（P∨Q）?（∧Q））（∧Q）
1.3.2 命题的翻译
可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。
命题翻译时应注意下列事项：
（1）确定所给句子是否为命题。
（2）句子中联结词是否为命题联结词。
（3）要正确的选择原子命题和合适的命题联结词。
例：假如上午不下雨，我去看电影，否则就在家里读书或看报。
解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。
本例可表示为：（?P→Q）∧（P→（R∨S））。
1.3.3 命题公式的解释定义
设P1，P2，…，P n是出现在命题公式G中的全部命题变元，指定P1，P2，…，P n的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作T I（G）。
例如，
是G的一个解释，在这个解释下G的真值为1，即T I（G）=1。
1.4 真值表与等价公式
1.4.1 真值表
定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。
构造真值表的方法如下：
（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，P n。
（2）列出G的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序依次写
出各赋值，直到11…1为止（或从11…1开始，按二进制递减顺序写出各赋值，直到00…0为止），然后从低到高的顺序列出G的层次。
（3）根据赋值依次计算各层次的真值并最终计算出G的真值。
定义设G为公式：（1）如果G在所有解释下取值均为真，则称G是永真式或重言式；（2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式；（3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。
1.4.3 等价公式
定义设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为A?B。
性质定理
设A、B、C是公式，则
（1）A?A
（2）若A?B则B?A
（3）若A?B且B?C则A?C
定理设A、B、C是公式，则下述等价公式成立：
（1）双重否定律??A?A
（2）等幂律 A∧A?A ； A∨A?A
（3）交换律 A∧B?B∧A ； A∨B?B∨A
（4）结合律（A∧B）∧C?A∧（B∧C）
（A∨B）∨C?A∨（B∨C）
（5）分配律（A∧B）∨C?（A∨C）∧（B∨C）
（A∨B）∧C?（A∧C）∨（B∧C）
（6）德·摩根律?（A∨B）??A∧?B
?（A∧B）??A∨?B
（7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A
（8）零一律 A∨1?1 ； A∧0?0
（9）同一律 A∨0?A ； A∧1?A
（10）排中律 A∨?A?1
（11）矛盾律 A∧?A?0
（12）蕴涵等值式 A→B??A∨B
（13）假言易位 A→B??B→?A
（14）等价等值式 A?B?（A→B）∧（B→A）
（15）等价否定等值式 A?B??A??B??B??A
（16）归缪式（A→B）∧（A→?B）??A
1.4.4 置换规则
定理（置换规则）设?（A）是一个含有子公式A的命题公式，?（B）是用公式B置换了?（A）中的子公式A后得到的公式，如果A?B，那么?（A）??（B）。
1.5 对偶与范式
1.5.1 对偶
定义在仅含有联结词?、∧、∨的命题公式A中，将联结词∧换成∨，将∨换成∧，如果A中含有特殊变元0或1，就将0换成1，1换成0，所得的命题公式A*称为A的对偶式。
例：公式（?P∨Q）∧（P∨?Q）的对偶式为：（?P∧Q）∨（P∧?Q）定理设A和A*互为对偶式，P1，P2，…，P n是出现在A和A*中的所有原子
变元，若将A和A*写成n元函数形式，则
（1）?A（P1，P2，…，P n）?A*（?P1，?P2，…，?P n）
（2）A（?P1，?P2，…，?P n）??A*（P1，P2，…，P n）
定理（对偶原理）设A、B是两个命题公式，若A?B，则A*?B*，其中A*、B*分别为A、B的对偶式。
1.5.2 范式
定义仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。
定义仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。
定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。
1.5.3 主范式
定义在含有n个命题变元P1，P2，…，P n的简单合取范式中，若每个命
题变元或其否定不同时存在，但二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位置上（若命题变元无脚标，则按字典顺序排列），这样的简单合取式称为极小项。相应的，满足上述条件的简单析取式称为极
大项。n个命题变元P1，P2，…，P n的极小项用公式可表示为 P i* ，极大项可表示为P i*，其中，P i*为P i或?P i（i=1，2，…，n）。
定义设G为公式，P1，P2，…，P n为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，…，P n的一个极小项，则称该析取范式为G的主
析取范式。矛盾式的主析取范式为0。
定理任意的命题公式都存在一个唯一的与之等价的主析取范式。
用等值演算求主析取范式步骤如下：
（1）求G的析取范式G'；
（2）若G中某个简单合取式m中没有出现某个命题变元P i或其否定?P i，则将m作如下等价变换：m?m∧（P i∨?P i）?（ m∧P i）∨（m∧?P i）
（3）将重复出现的命题变元、矛盾式和重复出现的极小项都消去；
（4）重复步骤（2）、（3），直到每一个简单合取式都为极小项；
（5）将极小项按脚标由小到大的顺序排列，并用↖表示。如m0∨m1∨m7可表示为↖（0，1，7）。
定义设G为公式，P1，P2，…，P n为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，…，P n的一个极大项，则称该合取范式为G的主
合取范式。通常，主合取范式用?表示。重言式的主合取范式中不含任何极大项，用1表示。
定理任意的命题公式都存在一个唯一的与之等价的主合取范式。
1.6 公式的蕴涵
1.6.1 蕴涵的概念定义
设G、H是两个公式，若G→H是永真式，则称G蕴涵H，记作G?H。
蕴涵关系有如下性质：
（1）对于任意公式G，有G?G；
（2）对任意公式G、H，若G?H且H?G，则G?H；
（3）若G?H且H?L，则G?L。
广义的蕴涵概念
定义设G1，G2，…，G n，H是公式，如果（G1∧G2∧…∧G n）→H是永真式，则称G1，G2，…，G n蕴涵H，又称H是G1，G2，…，G n的逻辑结果，记作（G1
∧G2∧…∧G n）?H或（G1，G2，…，G n）?H。
1.6.2 基本蕴涵式
（1）P∧Q?P；（2）P∧Q?Q；
（3）P?P∨Q； (4) Q?P∨Q；
（5）?P?（P→Q）；（6）Q?（P→Q）；
（7）?（P→Q）?P；（8）?（P→Q）??Q；
（9）P，P→Q?Q；（10）?Q，P→Q??P；
（11）?P，P∨Q?Q；（12）P→Q，Q→R?P→R；
（13）P∨Q，P→R，Q→R?R；（14）P→Q，R→S?（P∧R）→（Q∧S）；（15）P，Q?P∧Q。
1.7 其它联结词与最小联结词组
1.7.1 其它联结词
定义设P、Q为命题公式，则复合命题P ?Q称为P和Q的不可兼析取，当且仅当P与Q的真值不相同时，P?Q的真值为1，否则P?Q的真值为假。
定义设P、Q是两个命题公式，复合命题P?→
?c Q称为命题P、Q的条件否定，当且仅当P的真值为1，Q的真值为0时，P?→
?c Q
?c Q的真值为1，否则 P?→的真值为0。
1.7.2 最小联结词组
定义设S是一些联结词组成的非空集合，如果任何的命题公式都可以用仅包含S中的联结词的公式表示，则称S是联结词的全功能集。特别的，若S是联结词的全功能集且S的任何真子集都不是全功能集，则称S是最小全功能集，又称最小联结词组。
定理 {?，∧，∨，→，?}是联结词的全功能集。
定理 {?，∧，∨}是联结词的全功能集。
定理 {?，∧}，{?、∨}，{?，→}是最小联结词组。
定理 {↑}，{↓}是最小联结词组。
1.8 命题逻辑推理理论
1.8.1 命题逻辑推理理论
定义如果G1，G2，…，G n蕴涵H，则称H能够由G1，G2，…，G n有效推出，G1，G2，…，G n称为H的前提，H称为G1，G2，…，G n的有效结论。称（G1∧G2∧…∧G n）→H是由前提G1，G2，…，G n推结论H的推理的形式结构。
1.8.2 推理规则下面给出推理中常用的推理规则。
1．前提引入规则：可以在证明的任何时候引入前提；
2．结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提；3．置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。
4．言推理规则：P，P→Q?Q
5．附加规则：P?P∨Q；
6．化简规则：P，Q?P；
7．拒取式规则： ?Q，P→Q??P；
8．假言三段论规则：P→Q，Q→R?P→R；
9．析取三段论规则：?P，P∨Q?Q；
10.构造性二难规则：P∨Q，P→R，Q→R?R；
11.合取引入规则：P，Q?P∧Q
1.8.3 推理常用方法
1.直接证法
直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。
例构造下列推理的证明。
前提：P∨Q，P→R，Q→S 结论：S∨R
证明（1）P∨Q 前提引入规则
（2）P→R 前提引入规则
（3）Q→S 前提引入规则
（4）S∨R （1）（2）（3）构造性二难规则
2．间接证法
间接证法主要有如下两种情况。
（1）附加前提证明法有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：（G1∧G2∧…∧G n）?（R→C）设（G1∧G2∧…∧G n）为S，则上述推理可表示为证明S?（R→C），即证明S→（R→C）为永真式。
用附加前提证明法证明下面推理。
前提：P→（Q→R），?S∨P，Q 结论：S→R
证明：（1）?S∨P 前提引入规则
（2）S 附加前提引入规则
（3）P （1）（2）析取三段论规则
（4）P→（Q→R）前提引入规则
（5）Q→R （3）（4）假言推理规则
（6）Q 前提引入规则
（7）R （5）（6）假言推理规则
2）归缪法定义设G1，G2，…，G n是n个命题公式，如果G1∧G2∧…∧G n 是可满足式，则称G1，G2，…，G n是相容的。否则（即G1∧G2∧…∧G n是矛盾式）称G1，G2，…，G n是不相容的。
例用归缪法证明。
前提：P∨Q，P→R，Q→S 结论：S∨R
证明（1）?（S∨R）附加前提引入规则
（2）?S∧?R （1）置换规则
（3）?S （2）化简规则
（4）?R （2）化简规则
（5）Q→S 前提引入规则
（6）?Q∨S （5）置换规则
（7）?Q （3）（6）析取三段论
（8）P∨Q 前提引入规则
（9）P （7）（8）析取三段论规则
（10）P→R 前提引入规则
（11）?P∨R （10）置换规则
（12）R （9）（11）析取三段论规则
（13）?R∧R （4）（12）合取引入规则
第二章谓词逻辑
本章学习目标
命题逻辑中原子命题是最小的单位，不能够再进行分解，这给推理带来了很大局限性，本章引入谓词逻辑。学习关于谓词逻辑的相关概念和定理，解决实际问题。
内容：
谓词、量词及谓词公式等概念，基本等价式、永真蕴涵式及谓词演算的形式推理方法，谓词范式的概念
教学目的：
1．深刻理解个体、谓词、量词的概念。
2．深刻理解原子、公式、解释的概念。
3．掌握用解释的方法证明等价式和蕴涵式。
4．熟练掌握谓词演算的形式推理方法。
教学重点：
1．个体、谓词、量词的概念
2．用解释的方法证明等价式和蕴涵式
3．谓词演算的形式推理方法
教学难点：
1．解释的方法证明等价式和蕴涵式
2．谓词演算的形式推理方法
2.1 谓词逻辑命题的符号化
1．个体词：个体词是指研究对象中不依赖于人的主观而独立存在的具体的或抽象的客观实体
个体常项或个体常元：
个体变项或个体变元：
个体域或论域：
2．谓词：用来刻画个体词的性质或个体词之间关系的词
一般来说，“x是A”类型的命题可以用A（x）表达。对于“x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表示“…大于…”谓词。我们把A（x）称为一元谓词,B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。
例2.1 将下列命题在谓词逻辑中符号化，并讨论它们的真值：
（1）只有4是素数，8才是素数。
（2）如果2小于3，则8小于7。
解（1）设谓词G（x）：x是素数，a：4，b：8；
（1）中的题符号化为谓词的蕴涵式：G（a）→G（b）
由于此蕴涵式的前件为假，所以（1）中的命题为真。
（2）设谓词H（x，y）：x小于y，a：2，b：3，c：8，d：7
（2）中的命题符号化为谓词的蕴涵式：H（a，b）→H（c，d）
由于此蕴涵式的前件为真，后件为假，所以（2）中的命题为假。
例 2.2 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）所有人都是要死的。
（2）有的人天生就近视。
其中：（a）个体域D1为人类集合。
（b）个体域D2为全总个体域。
解（a）令F（x）：x要死的；G（x）：x天生就近视。
（1）在个体域D1中除人外，没有其他的事物，因而（1）可符号化为：
?x F（x）
（2）在个体域D1中有些人是天生就近视，因而（2）可符号化为谓词的蕴涵式：
? x G（x）
（b）在个体域D2中除人外，还有其他的事物，因而在将（1）、（2）符号化时，必须考虑先将人分离出来，令M（x）：x是人。在D2中，（1）、（2）可分别描
述如下：对于宇宙间的一切事物，如果事物是人，则他是要死的。
（2）在宇宙间存在着天生就近视的人。将（1）、（2）分别符号化为：（1）?x（M（x）→F（x））
（2）?x（M（x）→G（x））
在个体域D1、D2中命题（1）、（2）都是真命题。
例2.3 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6=（x-2）（x-3）
（2）存在x，使得x+1=0。
其中：（a）个体域D1为自然数集合。
（b）个体域D2为实数集合。
解（a）令F（x）：x2-5x+6=（x-2）（x-3）；G（x）：x+1=0。
（1）可符号化为：
?x F(x)
（2）可符号化为：
?x G（x）
在个体域D1中命题（1）为真命题，命题（2）为假命题。
（b）在个体域D2中（1）、（2）符号化分别为
（1）?x F（x）
（2）?x G（x）
在个体域D2中命题（1）、（2）都是真命题。
例2.4 将下列命题符号化，并指出真值情况。
（1）没有人登上过月球。
（2）所有人的头发未必都是黑色的。
解个体域为全总个体域，令M（x）：x是人。
（1）令F（x）：x登上过月球。命题（1）符号化为：
??x（M（x）∧F（x））
设a是1969年登上月球完成阿波罗计划的一名美国人，则M（a）∧F（a）为真，故命题（1）为假。
（2）令H（x）：x的头发是黑色的。命题（2）可符号化为：
??x（M（x）→H（x））
我们知道有的人头发是褐色的，所以?x（M（x）→H（x））为假，故命题（2）为真。
例2.5 将下列命题符号化。
（1）猫比老鼠跑得快。
（2）有的猫比所有老鼠跑得快。
（3）并不是所有的猫比老鼠跑得快。
（4）不存在跑得同样快的两只猫。
解设个体域为全总个体域。令C（x）：x是猫；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同样快。这4个命题分别符号化为：
（1）?x?y（C（x）∧M（y）→Q（x，y））；
（2）?x（C（x）∧?y（M（y）→Q（x，y）））；
（3）??x ?y（C（x）∧M（y）→Q（x，y））；
（4）??x? y（C（x）∧C（y）∧L（x，y））
2.2 谓词逻辑公式与解释
2.2.1 谓词逻辑的合式公式
定义2.1 设P（x1，x2，…，x n）是n元谓词公式，其中，x1x2，…，x n 是个体变项，则称P（x1，x2，…，x n）为谓词演算的原子公式。
定义2.2 谓词演算的合式公式定义如下：
（1）原子公式是合式公式；
（2）若A是合式公式，则（﹁A）也是合式公式；
（3）若A，B是合式公式，则（A∧B）、（A∨B）、（A→B）、（A?B）是合式公式；
（4）若A是合式公式，则?x A、?x A是合式公式；
（5）只有有限次地应用（1）－（4）构成的符号串才是合式公式。
例2.5 在谓词逻辑中将下列命题符号化。
（1）不存在最大的数。
（2）计算机系的学生都要学离散数学。
解取个体域为全总个体域。
（1）令F（x）：x是数，L（x，y）：x大于y；则命题（1）符号化为
﹁?x（F（x）∧?y（F（y）→ L（x，y）））
（2）令C（x）：x是计算机系的学生，G（x）：x要学离散数学;则命题（2）可符号化为：?x（C（x）→ G（x））
例2.6 将下列命题符号化。
（1）尽管有人聪明，但并非所有人都聪明。
（2）这只大红书柜摆满了那些古书。
解（1）令C（x）：x聪明；M（x）：x是人。则命题（1）可符号化为
?x（M（x）∧C（x））∧﹁?x（M（x）→C（x））
（2）令F（x，y）：x摆满了y；R（x）：x是大红书柜；Q（x）:x是古书；a：这只；b：那些。则命题（2）可符号化为
R（a）∧Q（b）∧F（a，b）
2.2.2 约束变元与自由变元
1．约束变元与自由变元的概念
定义 2.3 在公式?x F（x）和?x F（x）中，称x为指导变元，F（x ）为相应量词的辖域或作用域。在?x和?x的辖域中，x的所有出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自由出现。
例2.7 指出下列各式量词的辖域及变元的约束情况：
（1）?x（F（x，y）→ G（x，z））
（2）?x（P（x）→?y R（x，y））
（3）?x（F（x）→ G（y））→?y（H（x）∧M（x，y，z））
解（1）对于?x的辖域是A=（F（x，y）→ G（x，z）），在A中，x是约束出现的，而且约束出现两次，y，z均为自由出现，而且各自由出现一次。
（2）对于?x的辖域是（P（x）→?y R（x，y）），?y的辖域是R（x，y），x，y均是约束出现的。
（3）对于?x的辖域是（F（x）→ G（y）），其中x是约束出现的，而y是自由出现的。对?y的辖域是（H（x）∧M（x，y，z）），其中y是约束出现的，而x，z是自由出现的。在整个公式中，x约束出现一次，自由出现两次，y约束出现一次，自由出现一次，z仅自由出现一次。
2．约束变元的换名与自由变元的代入
例2.8 对公式?x（P（x）→ R（x，y））∧Q（x，y）进行换名。
解对约束变元x换名为t后为
?t（P（t）→ R（t，y））∧Q（x，y）
同理，对公式中的自由变元也可以更改，这种更改称作代入。
自由变元的代入规则是：
（1）对于谓词公式中的自由变元，可以代入，此时需要对公式中出现该自由变元的每一处进行代入。
（2）用以代入的变元与原公式中所有变元的名称都不能相同。
例2.9 对公式?x（F（x）→ G（x，y））∧?y H（y）代入。
解对y实施代入，经过代入后原公式为
?x（F（x）→ G（x，t））∧?y H（y）
另外，量词作用域中的约束变元，当论域的元素是有限时，个体变元的所有可能的取代是可以枚举的。
设论域元素为a1，a2，…，a n，
则?x A（x）? A（a1）∧A（a2）∧…∧A（a n）
?x A（x）? A（a1）∨A（a2）∨…∨A（a n）。
2.2.3 谓词逻辑公式的解释
定义2.4 谓词逻辑公式的一个解释I，是由非空区域D和对G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成：
（1）对每一个常项符号指定D中一个元素。
（2）对每一个n元函数符号，指定一个函数。
（3）对每一个n元谓词符号，指定一个谓词。
显然，对任意公式G，如果给定G的一个解释I，则G在I的解释下有一个真值，
记作T I（G）。
例2.10 指出下面公式在解释I下的真值。
（1）G=?x（P（f（x））∧Q（x，f（a）））；
（2）H=?x（P（x）∧Q（x，a））。
给出如下的解释I：
D={2，3}；
a：2；
f（2）：3、f（3）：2；
P（2）：0、P（3）：1；
Q（2，2）：1、Q（2，3）：1、Q（3，2）：0、Q（3，3）：1；
解（1）T I（G）= T I（（P（f（2））∧Q（2，f（2）））∨（P（f（3））∧Q（3，f（2））））
= T I（（P（3）∧Q（2，3））∨（P（2）∧Q（3，3））
= （1∧1）∨（0∧1）
= 1
（2）T I（H）= T I（P（2）∧Q（2，2）∧P（3）∧Q（3，2））
=0∧1∧1∧0=0
定义2.5 若存在解释I，使得G在解释I下取值为真，则称公式G为可满足的，简称I满足G。
定义2.6若不存在解释I，使得I满足G，则称公式G为永假式（或矛盾式）。若G的所有解释I都满足G，则称公式G为永真式（或重言式）。
2.3 谓词逻辑约束公式的等价与蕴涵
2.3.1 谓词逻辑的等价公式
定义2.7 设A、B是命题逻辑中的任意两个公式，设它们有共同的个体域E，若对任意的解释I都有T I（A）= T I（B），则称公式A、B在E上是等价的，记作A?B。
定理1设A（x）是谓词公式，有关量词否定的两个等价公式：
（1）﹁?x A（x）??x﹁A（x）
（2）﹁?x A（x）??x﹁A（x）
证明（1）设个体域是有限的为：D={ a1，a2，…，a n}，则有
﹁?x A（x）?﹁（A（a1）∧A（a2）∧…∧A（a n））
?﹁A（a1）∨﹁A（a2）∨…∨﹁A（a n））
??x﹁A（x）
（2）设个体域是有限的为：D={ a1，a2，…，a n}，则有﹁?x A（x）?﹁（A（a1）∨ A（a2）∨…∨A（a n））
?﹁A（a1）∧﹁A（a2）∧…∧﹁A（a n）
??x﹁A（x）
定理2 设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有
（1）?x（A（x）∨B）??x A（x）∨B
（2）?x（A（x）∧B）??x A（x）∧B
（3）?x（A（x）→ B）??x A（x）→ B
（4）?x（B→A（x））?B→?x A（x）
（5）?x（A（x）∨B）??x A（x）∨B
（6）?x（A（x）∧B）??x A（x）∧B
（7）?x（A（x）→ B）??x A（x）→ B
（8）?x（B→A（x））?B→?x A（x）
证明（1）设D是个体域，I为任意解释，即用确定的命题及确定的个体代替出现在?x（A（x）∨B）和?x A（x）∨B中的命题变元和个体变元，于是得到两个命题，若对?x（A（x）∨B）代替之后所得命题的真值为真，此时必有A（x）∨B的真值为真；因而A（x）真值为真或B的真值为真，若B的真值为真，则?x A（x）∨B的真值为真；若B的真值为假，则必有对D中任意x都使得A（x）的真值为真，所以?x（A（x）∨B）为真，从而?x A（x）∨B为真。若对?x（A （x）∨B）代替之后所得命题的真值为假，则A（x）和B的真值必为假，因此?x A（x）∨B的真值为假；所以?x（A（x）∨B）为假，有?x A（x）∨B为假。（2）、（5）和（6）证明与（1）类似，证明过程略。
（3）?x（A（x）→ B）??x（?A（x）∨B）
??x?A（x）∨ B
??x? A（x）∨B
??x A（x）→ B
（4）、（7）、（8）证明与（3）类似，证明过程略。
定理3 设A（x）、B（x）是任意包含自由出现个体变元x的公式,则有：（1）?x（A（x）∧B（x））??x A（x）∧?x B（x）
（2）?x（A（x）∨B（x））??x A（x）∨?x B（x）
证明（1）设D是任一个体域，若?x（A（x）∧B（x））的真值为真，则对任意a∈D，有A（a）和B（a）同时为真，即?x A（x）为真、?x B（x）为真，从而?x A（x）∧?x B（x）为真。若?x（A（x）∧B（x））的真值为假，则对任意a∈D，有A（a）和B（a）不能同时为真，即?x A（x）和?x B（x）的真值不能同时为真，从而?x A（x）∧?x B（x）的真值为假。
综上所述?x（A（x）∧B（x））??x A（x）∧?x B（x）
（2）设D是任一个体域，若?x（A（x）∨B（x））的真值为真,则存在a∈D，使得A（a）∨B（a）为真，即A（a）为真或B（a）为真，即?x A（x）为真或?x B （x）为真，从而?x A（x）∨?x B（x）为真。若?x（A（x）∨B（x））的真值为假，则存在a∈D，使得A（a）∨B（a）为假，此时，A（a）为假，B（a）为假，从而?x A（x）∨?x B（x）的真值为假。
综上所述?x（A（x）∨B（x））??x A（x）∨?x B（x）
例2.11 证明下列各等价式
（1）﹁?x（A（x）∧B（x））??x（A（x）→﹁B（x））
（2）﹁?x（A（x）→ B（x））??x（A（x）∧﹁B（x））
证明（1）﹁?x（A（x）∧B（x））
??x ﹁（A（x）∧B（x））
??x（﹁A（x）∨﹁B（x））
??x（A（x）→﹁B（x））
（2）﹁?x（A（x）→ B（x））
??x ﹁（A（x）→ B（x））
??x ﹁（﹁A（x）∨B（x））
??x（A（x）∧﹁B（x））
2.3.2 谓词逻辑的蕴涵公式
定义2.8 设A、B是命题逻辑中的任意两个公式，若A→B是永真式，则称公式A蕴涵公式B，记作A?B。
定理4 下列蕴涵式成立
（1）?x A（x）∨?x B（x）??x（A（x）∨B（x））
（2）?x（A（x）∧B（x））??x A（x）∧?x B（x）
（3）?x（A（x）→ B（x））??x A（x）→?x B（x）
（4）?x（A（x）→ B（x））??x A（x）→?x B（x）
（5）?x A（x）→?x B（x）??x（A（x）→ B（x））
证明：
（1）设?x A（x）∨?x B（x）在任意解释下的真值为真，即对个体域中的每一个x。都能使A（x）的真值为真或者对个体域中的每一个x都能使B（x）的真值为真，无论哪种情况，对于个体域中的每一个x都能使A（x）∨B（x）的真值为真。因此，蕴涵式?x A（x）∨?x B（x）??x（A（x）∨B（x））成立。（2）设个体域为D，在解释I下?x（A（x）∧B（x））的真值为真，即存在a∈D 使得A（a）∧B（a）为真，从而A（a）为真，B（a）为真，故有?x A（x）、?x B
（x）均为真，所以，蕴涵式?x（A（x）∧B（x））??x A（x）∧?x B（x）成立。
（3）设个体域为D，在解释I下?x A（x）→?x B（x）的真值为假,即存在a∈D 使得A（a）→B（a）为假，所以蕴涵式?x（A（x）→B（x））??x A（x）→?x B（x）成立。
（4）?x（A（x）→B（x））→（?x A（x）→?x B（x））
?﹁?x（A（x）→B（x））∨（?x A（x）→?x B（x））
?﹁?x（A（x）→B（x））∨（﹁?x A（x）∨?x B（x））
?﹁?x（A（x）→B（x））∨﹁?x A（x）∨?x B（x）
?﹁（?x（A（x）→B（x））∧?x A（x））∨?x B（x）
?（?x（A（x）→B（x））∧?x A（x））→?x B（x）
（5）?x A（x）→?x B（x）???x A（x）∨?x B（x）
??x ?A（x）∨?x B（x）
??x（?A（x）∨B（x））
??x（A（x）→ B（x））
2.3.3 多个量词的使用
定义2.9 设谓词公式G，不包含联结词→，?。把G中出现的联结词∨，∧互换；命题常量T，F互换；量词?，?互换之后得到的公式称为G的对偶公式，记作G*。
定理5（对偶定理）设A、B是任意两个公式并且不包含联结词→，?。若A?B，则A*?B*。
2.4 前束范式
定义2.10一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾，则该公式称为前束范式。
定理6 对任意一个谓词公式都可以化为与它等价的前束范式。
证明首先利用等价公式将谓词公式中的联结词→，?去掉。其次利用量词的转化律将量词前面的否定深入到谓词前面，在利用改名和代入规则以及量词辖域扩张的公式将量词移到全式的最前面，这样便得到前束范式。
例2.12 求下列谓词公式的前束范式。
（1）?x ?y（?z A（x，z）∧A（x，z））→?t B（x，y，t）
解（1）?x ?y（?z A（x，z）∧A（x，z））→?t B（x，y，t）?﹁?x ?y（?z A（x，z）∧A（x，z））∨?t B（x，y，t）??x ?y（?z﹁A（x，z）∨﹁A（x，z））∨?t B（x，y，t）
（量词转化）
??x ?y（?w﹁A（x，w）∨﹁A（x，z））∨?t B（u，v，t）
（改名及代入规则）??x ?y ?w ?t（﹁A（x，w）∨﹁A（x，z）∨B（u，v，t））
（量词辖域扩张）（2）﹁?x（?y P（x，y）→?x ?y（Q（x，y）∧?y（P（y，x）→Q（x，y））））解（2）﹁?x（?y P（x，y）→?x ?y（Q（x，y）∧?y（P（y，x）→Q（x，y））））
?﹁?x（﹁?y P（x，y）∨?x ?y（Q（x，y）∧?y（P（y，x）→Q（x，y））））??x（?y P（x，y）∧?x?y（﹁Q（x，y）∨?y（P（y，x）∧﹁Q（x，y））））
（量词转化、德·摩根定律）??x（?y P（x，y）∧?x ?y（﹁Q（x，y）∨?z（P（z，x）∧﹁Q（x，z））））
（改名原则）??x（?y P（x，y）∧?x ?y ?z（﹁Q（x，y）∨（P（z，x）∧﹁Q（x，z））））
（量词辖域扩张）??x（?y P（x，y）∧?u ?v ?z（﹁Q（u，v）∨（P（z，u）∧﹁Q（u，z））））
（改名原则）??x ?y ?u ?v ?z （P（x，y）∧（?Q（u，v）∨（P（z，u）∧﹁Q（u，z））））（量词辖域扩张）定义2.11若一个谓词公式，具有如下形式，则称该公式为前束析取范式。
定义2.12 若一个谓词公式，具有如下形式，则称该公式为前束合取范式。
定理7 任意谓词公式都可以化为与其等价的前束析取范式和前束合取范式。
2.5 谓词演算的推理理论
1．全称指定规则（简称US规则）
这条规则有下面两种形式：
(1)?x P（x）?P（y）
(2)?x P（x）?P（c）
其中，P是谓词，（1）中y为任意不在P（x）中约束出现的个体变元；（2）中c 为个体域中的任意一个个体常元。
2．存在指定规则（简称ES规则）
?x P（x）?P（c）
其中，c为个体域中使P成立的特定个体常元。必须注意，应用存在指定规则，其指定的个体c不是任意的。
3．全称推广规则（简称UG规则）
P（y）??x P（x）
4．存在推广规则（简称EG规则）
P（c）??x P（x）
其中，c为个体域中的个体常元，这个规则比较明显，对于某些个体c，若P（c）成立，则个体域中必有?x P（x）。
例2.13 证明?x（M（x）→ D（x））∧M（s）?D（s）这是著名的苏格拉底三段论的论证。
其中 M（x）：x是一个人。
D（x）：x是要死的。
s：苏格拉底。
证明（1）?x（M（x）→ D（x）） P
（2）M（s）→ D（s） US（1）
（3）M（s） P
（4）D（s） T（2）（3）I
例 2.14 判断下列的推理过程是否正确。
（1）?x ?y G（x，y） P
（2）?y G（z，y） US（1）
（3）G（z，c） ES（2）
（4）?x G（x，c） UG（3）
（5）?y ?x G（x，y） EG（4）
解这个推理过程是错误的，因为从它可以得出结论：
?x ?y G（x，y）??y ?x G（x，y）
从前面的学习中我们知道这个式子不成立。它的推导错误出现在第（3）步。?x ?y G（x，y）的含义是：对于任意的一个x，存在着与它对应的y，使得G（x，y）成立。但是，对?y G（z，y）利用ES规则消去存在变量后得到G（z，c）的含义却是：对于任意个体z，有同一个体c，使得G（z，c）成立。显然，G（z，c）不是?y G（z，y）的有效结论。因此，使用ES规则?x P（x）?P（c）消去存在量词的条件是:P（x）中除x外没有其他自由出现的个体变元。
例2.15 证明：?x（C（x）→（W（x）∧R（x）））∧?x C（x）∧Q（x）??x Q（x）∧?x Q（x）
证明（1）?x C（x）P
（2）C（y）ES（1）
（3）?x（C（x）→（W（x）∧R（x）））P
（4）C（y）→（W（y）∧R（y））US（3）
（5）W（y）∧R（y）T（2）（4）I
（6）R（y）T（5）I
（7）?x R（x）EG（6）
（8）Q（x）P
（9）?x Q（x）EG（8）
（10）?x Q（x）∧?x Q（x）T（7）（9）I
例2.16 证明：?x（A（x）∨B（x））??x A（x）∨?x B（x）
证明（1）?x（A（x）∨B（x）） P
（2）A（y）∨B（y） US（1）
（3）?x（A（x）∨B（x）） EG（2）
（4）?x A（x）∨?x B（x） T（3）E
例2.17 给定前提：
?x（P（x）∧?y（Q（y）→ R（x，y）））
?x（P（x）→?y（S（y）→﹁R（x，y）））
证明下列结论：
?x（Q（x）→﹁S（x））
证明：
（1）?x（P（x）∧?y（Q（y）→ R（x，y））） P
（2）P（a）∧?y（Q（y）→ R（a，y）） ES（1）
（3）P（a） T（2）
（4）?x（P（x）→?y（S（y）→﹁R（x，y））） P
（5）P（a）→?y（S（y）→﹁R（a，y）） US（4）
（6）?y（S（y）→﹁R（a，y）） T（3）（5）I
（7）?y（Q（y）→ R（a，y）） T（2）I
（8）S（z）→﹁R（a，z） US（6）
（9）Q（z）→R（a，z） US（7）
（10）R（a，z）→﹁S（z） T（8）E
（11）Q（z）→?S（z） T（9）（10）I
（12）?x（Q（x）→﹁S（x）） UG（11）
例 2.18 符号化下面的命题“所有的有理数都是实数，所有的无理数也是实数，任何虚数都不是实数，所以任何虚数既不是有理数也不是无理数”，并推证其结论。
证明设：P（x）：x是有理数。
Q（x）：x是无理数。
R（x）：x是实数。
S（x）：x是虚数。
本题符号化为：?x（P（x）→ R（x）），?x（Q（x）→ R（x）），?x（S（x）→﹁R（x））??x（S（x）→﹁P（x）∧﹁R（x））
（1）?x（S（x）→﹁R（x）） P
（2）S（y）→﹁R（y） US（1）
（3）?x（P（x）→ R（x）） P
（4）P（y）→ R（y） US（3）
（5）﹁R（y）→﹁P（y） T（4）E
（6）?x（Q（x）→ R（x）） P
（7）Q（y）→ R（y） US（6）
（8）﹁R（y）→﹁Q（y） T（7）E
（9）S（y）→﹁P（y）T（2）（5）I
（10）S（y）→﹁Q（y）T（2）（8）I （11）（S（y）→﹁P（y））∧（S（y）→﹁Q（y）T（9）（10）I （12）（﹁S（y）∨﹁P（y））∧（?S（y）∨﹁Q（y））T（11）E
（13）﹁S（y）∨（﹁P（y）∧﹁Q（y））T（12）E
（14）S（y）→（﹁P（y）∧﹁Q（y））T（13）E
（15）?x（S（x）→﹁P（x）∧﹁R（x））UG（14）
第三章集合
本章学习目标：
集合是一般数学及离散数学中的基本概念，几乎与现代数学的各个分支都有密切联系，并且渗透到很多科技领域。本章主要介绍集合的基本知识，通过本章学习，读者应该掌握以下内容：
1.集合的概念及表示方法
2.子集、空集、全集、补集、幂集等概念
3.集合的基本运算：交、并、补和对称差
4.集合的包含排斥原理
内容：
集合的概念及运算、幂集及笛卡尔积的运算、容斥原理的应用
教学目的：
1．深刻理解子集、空集、全集、集合表示、集合相等、幂集等基本概念。2．熟练掌握集合的并、交、补、运算；能用文氏图表示集合运算。
3．熟练掌握集合运算的基本定律，能熟练地应用这些定律证明集合恒等式。4．深刻理解序偶与笛卡尔积的概念；了解递归定义的概念；理解容斥原理。
教学重点：
1．集合的概念及表示方法
2．子集、空集、全集、补集、幂集等概念
3．集合的基本运算：交、并、补和对称差
4．集合的包含排斥原理
教学难点：
集合的基本运算：交、并、补和对称差集合的包含排斥原理
3.1集合的概念与表示
3.1.1 集合的基本概念
3.1.2 集合的表示
1．列举法
2．描述法
3.文氏图法
3.2 集合之间的关系
定义3.1如果集合A中的每一个元素都是集合B中的元素，则称A是B的
离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；
离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
离散数学自学笔记命题公式及其真值表 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。湖南省自考网：https://www.doczj.com/doc/11820184.html,/整理 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。
第一章，0命题逻辑 素数 = 质数，合数有因子 和或假必真同为真 (p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是单个的命题变项，则称A为0层合式 (┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 【例】求下列公式的真值表，并求成真赋值和成假赋值。 (┐p∧q)→┐r 公式(1)的成假赋值为011，其余7个赋值都是成真赋值 第二章，命题逻辑等值演算 （1）双重否定律??A?A （2）等幂律 A∧A?A ； A∨A?A （3）交换律 A∧B?B∧A ； A∨B?B∨A （4）结合律（A∧B）∧C?A∧（B∧C）；（A∨B）∨C?A∨（B∨C） （5）分配律（A∧B）∨C?（A∨C）∧（B∨C）；（A∨B）∧C?（A∧C）∨（B∧C） （6）德·摩根律?（A∨B）??A∧?B ；?（A∧B）??A∨?B （7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A （8）零一律 A∨1?1 ； A∧0?0 （9）同一律 A∨0?A ； A∧1?A （10）排中律 A∨?A?1 （11）矛盾律 A∧?A?0 （12）蕴涵等值式 A→B??A∨B （13）假言易位 A→B??B→?A （14）等价等值式 A?B?（A→B）∧（B→A） （15）等价否定等值式 A?B??A??B??B??A （16）归缪式（A→B）∧（A→?B）??A
A i(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨A s为析取范式 (p∧┐q)∨(┐q∧┐r)∨p A=A1∧A2∧…∧A s为合取范式 (p∨q∨r)∧(┐p∨┐q)∧r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真，∨大假】 ∧成真小写 【例】(p→q)→(┐q→┐p) = ┐(┐p∨q)∨(q∨┐p) (消去→) = (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) = (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*） = m2∨m0∨m1∨m1∨m3 = m0∨m1∨m2∨m3 (幂等律、排序) (*)由┐p及q派生的极小项的过程如下： ┐p = ┐p∧(┐q∨q) = (┐p∧┐q)∨(┐p∧q) q = (┐p∨p)∧q = (┐p∧q)∨(p∧q) 熟练之后，以上过程可不写在演算过程中。 该公式中含n=2个命题变项，它的主析取范式中含了22=4个极小项，故它为重言式， 00，01，10，11全为成真赋值。 【例】(p→q)∧┐p = (┐p∨q)∧┐p (消去→) = ┐p∨(┐p∧q) (分配律、幂等律) 已为析取范式
教师资格证笔记 中学考试科目：综合素质，教育知识与能力，学科知识与教学能力。 第一课：科目一综合素质指导 一、考点分析 1.题型上： 29 个单选（ 29*2=58）3 个材料分析题（ 3*14=42) 1 个作文题（ 50） 2.内容上： 知识模块知识点 教育观学生观职业理念 教师观 教育法规，学生权教育法律法规利，教师权利和义 务 教师职业道德教师职业道德规范 （三爱两人一终 身） 历史，科学，文学，文化素养 艺术鉴赏素养 分值题型 4 个单选（ 1 个教 育观，2 个学生观，22 分（ 14.7%） 1 个教师观） 1 个 材料分析（学生观 重点） 8 个单选 中华人民共和国 教育法（ 1 个） 中华人民共和国 义务教育法（ 1 个） 中华人民共和国 教师法（ 1 个）16 分（ 10.6%） 中华人民共和国 未成年人保护法 （2 个） 中华人民共和国 预防未成年人犯 罪法（ 1 个） 国家中长期教育 改革和发展规划 纲要（ 2 个） 22 分（ 14.7%） 4 个单选（教师职 业道德 2 个，班主 任工作条例 1 个， 教师职业行为 1 个） 1 个材料分析 9 个单选 中国历史或世界 历史（ 1 个） 传统文化（ 1 个） 地理知识或儿童 18 分（ 12%） 文学（ 1 个） 中国科技史或外 国科技史（ 1 个） 科学常识（ 1 个） 中国古代文学（ 1
个） 中国现当代文学 （1 个） 世界文学（ 1 个）艺术鉴赏与艺术理论（ 1 个） 4 个单选（信息处 逻辑思维，信息，理 2 个，逻辑思维 基本能力72 分（ 48%） 2 个） 1 个阅读理 阅读，写作能力 解（材料分析） 1 个作文 3.内容与题型 题型知识模块题目分布个数分值 单选职业理念1-4 题 4 个8 分 教育法律法规5-12 题8 个16 分 教师职业道德13-16 题 4 个8 分 文化素养17-25 题9 个18 分 基本能力（ 2 26-29 题 4 个8 分 个逻辑推理 2 个信息） 材料分析职业理念30 题 1 个14 分 教师职业道德31 题 1 个14 分 阅读理解（基32 题 1 个14 分 本能力一问 4 分二问 10 分） 写作基本能力33 题 1 个50 分 二、选择题实例分析： 1.职业理念：学生想做科学家，班主任说现在学数学那么吃力，以后学物理化 学肯定学不好，这样的说法忽视了学生的发展性。 2.法律法规：不能给予老师行政处分或者解聘的是（穿戴不整，影响仪表的） 3.职业道德：老师每次布置作业后都只是在下次的课堂上与学生核对答案，他 的做法（不合理，教师应该认真批改作业）爱岗敬业 4.文化素养：下列历史事件与秦始皇有关的（图穷匕见）指鹿为马（赵高）望 梅止渴（曹操）三顾茅庐（刘备诸葛亮） 5.信息能力：在Excel 中，下列方法可以实现快速查找满足条件的数据内容的是 （自动筛选） 6.逻辑推理： 3+4+5=151227 5+3+2=101525 8+2+4=321648则 7+6+5=354277 三、备考方案 1.据历年真题，梳理考点难点（考点分析） 2.学习知识点，形成知识地图（制作目录） 3.学方法，提高备考能力（材料分析和写作） 四、材料分析题实例： 1.职业理念
离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。
谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证
二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。
离散数学笔记（特级教师精心整理） 第一章命题逻辑 内容： 命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的： 1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。 2．熟练掌握常用的基本等价式及其应用。 3．熟练掌握（主）析/合取范式的求法及其应用。 4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。 5．熟练掌握形式演绎的方法。 教学重点： 1．命题的概念及判断 2．联结词，命题的翻译 3．主析（合）取范式的求法 4．逻辑推理 教学难点： 1．主析（合）取范式的求法 2．逻辑推理 1.1命题及其表示法 1.1.1 命题的概念 数理逻辑将能够判断真假的陈述句称作命题。 1.1.2 命题的表示 命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。 1.2命题联结词
（1） P↑P?﹁（P∧P）?﹁P； （2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。 （1）P↓P?﹁（P∨Q）?﹁P；
（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q； （3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。 1.3 命题公式、翻译与解释 1.3.1 命题公式 定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 例如，下面的符号串都是公式： （（（（﹁P）∧Q）→R）∨S） （（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R 以下符号串都不是公式： （（P∨Q）?（∧Q））（∧Q） 1.3.2 命题的翻译 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命题联结词。 例：假如上午不下雨，我去看电影，否则就在家里读书或看报。 解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。 本例可表示为：（?P→Q）∧（P→（R∨S））。 1.3.3 命题公式的解释定义 设P1，P2，…，P n是出现在命题公式G中的全部命题变元，指定P1，P2，…，P n的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作T I（G）。 例如， 是G的一个解释，在这个解释下G的真值为1，即T I（G）=1。 1.4 真值表与等价公式 1.4.1 真值表 定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。 构造真值表的方法如下： （1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，P n。
中公教师资格证考试教育综合知识整理笔记
第一节教育的产生与发展 1、“教育”一词最早出现于《孟子.尽心上》。 2、教育的概念：教育是一种培养人的社会活动，产生于人类的生产劳动，是传承社会文化、传递生产经验和社会生活经验的基本途径。 广义教育：社会教育、学校教育、家庭教育； 狭义教育：学校教育，是教育者根据一定的社会要求，有目的、有计划、有组织地经过学校教育的工作，对受教育者的身心施加影响，促使她们朝着期望方向变化的活动。学校教育由专职人员和专门教育机构承担。 3、教育的构成要素：教育者、受教育者、教育影响。 学校教师是教育者的主体，是最直接的教育者，在教育活动中起主导作用。 教育影响：教育内容、教育措施。 4、教育的本质属性：教育是一种有目的地培养人的社会活动，这是教育区别于其它事物现象的根本特征，是教育的质的规定性。 5、教育的社会属性：1、永恒性、2、历史性、3、相对独立性：教育具有继承性；教育要受其它社会意识形态的影响；教育与社会政治经济发展不平衡。 四、教育的起源与发展 （一）1、神话起源说；2、生物起源说：利托尔诺、桑代克、沛西能；3、心里起源说：代表人物孟禄；4、劳动起源说：米丁斯基、凯洛夫。 (二)教育的发展历程 1、原始社会的教育； 2、古代社会的教育； 3、近现代教育 第二节教育学的产生与发展 1、教育学的研究对象及任务
研究对象：教育现象（教育社会现象和教育认识现象）、教育问题（推动教育学发展的内在动力）。 研究任务：阐明教育的基础知识和基本理论，揭示教育的基本规律，未教育理论工作者和实践者提供理论支撑，为培养符合社会需要的人才服务。 2、教育学的发展 萌芽阶段： 《学记》是中国古代、世界古代最早的一篇专门论述教育、教学问题的论著。 苏格拉底：苏格拉底以其雄辩和与青年智者的问答法著名，这种教学方法又称“产婆术”。1.苏格拉底讽刺；2.定义；3.助产术。 柏拉图：柏拉图的教育思想集中体现在她的代表作《理想国》中。“寓学习于游戏”的最早提倡者。 亚里士多德：《政治学》；首次提出了“教育遵循自然”的原则，注意到了儿童心理发展的自然特点；秉承柏拉图的理性说。 昆体良：古代西方最早的教育学理论著作《雄辩术原理》（《论演说家的教育》《论演说家的培养》） 教育学的创立阶段： 1、培根：英国；首次把教育学作为一门独立学科提了出来。 2、夸美纽斯：“教育学之父”；1632《大教学论》是教育学形成一门独立学科的标志；“泛智教育”；“太阳底下最光辉的职业”。 3、卢梭：自然教育和儿童本位的教育观 4、康德：首次把教育学作为一门课程在大学里讲授。 5、佩斯泰洛奇：最早提出“教育心理学化”的主张。 6、洛克：提出“白板说”。 7、赫尔巴特：《普通教育学》的出版标志着规范教育学的建立。被誉为“现代教育学之父”。 主要观点：
数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明:
数学学科知识与教学 模块二：课程知识 (2) 第一章初中数学课程的性质与基本理念 (2) 第一节：影响初中数学课程的主要因素 (2) 第二节、初中数学课程性质 (2) 第三节：初中数学课程的基本理念 (3) 第四节：数学课程核心概念（10个）（背） (4) 第二章初中数学课程目标 (6) 第三章初中数学课程的内容标准 (8) 第四章：初中数学课程教学建议 (9) 第一节《课标》中的数学教学建议 (9) 第二节教学中应当注意的几个关系 (9) 第五章初中数学课程评价建议 (10) 第一章数学教学方法 (11) 第一节初中数学教学常用的教学方法 (11) 第二节：教学方法的选择 (11) 第二章数学概念的教学 (12) 第一节：重要概念教学的基本要求 (12) 第二节概念教学的一般过程 (12) 第三章数学命题的教学 (12) 第一节重要命题教学的基本要求 (12) 第二节：命题教学的一般过程 (13) 第四章数学教学过程与数学学习方式 (13) 第一节数学教学过程 (13) 第二节：数学学习的概念 (14) 第三节中学数学学习方式 (14) 第一章数学教学设计 (15) 第一节教学目标的阐明 (15) 第二节教学内容的确定 (15) 第三节教学策略的确定 (16) 第四节教学方案的撰写 (17) 第二章数学教学的测量与评价 (17)
模块二：课程知识 第一章初中数学课程的性质与基本理念 第一节：影响初中数学课程的主要因素 1、初中数学课程是一门国家课程，内容主要包括课程目标、教学内容、教学过程和评价手段。它体现了郭嘉从数学教育与教学的角度，对初中阶段学生实现最终培养目标的整体规划。 2、影响初中数学课程的主要因素包括： 一、数学学科内涵：（1）数学科学本身的内涵（数学的知识、方法和意义等） （2）作为教育任务的数学学科的内涵（理解数学的整体性特征，领悟 相关的数学思想，应用数学解决问题的能力等） 二、社会发展现状：（1）当代社会的科学技术、人文精神中蕴含的数学知识与素养等 （2）生活变化对数学的影响等 （3）社会发展对公民基本数学素养的需求。 三、学生心理特征。初中数学课程是针对初中学生年龄特征和知识经验而设置的，因此学生的心理特征必然会影响着具体的课程内容、 （1）适合学生的数学思维特征 （2）学生的知识、经验和环境背景 第二节、初中数学课程性质 一、基础性（1）初中阶段的数学课程中应当有大量的内容是未来公民在日常生活 中必须要用到的。 （2）初中阶段的教育是每一个学生必须经历的基础教育阶段，它将为 其后续生存、发展打下必要的基础。 （3）由于数学学科是其他科学的基础，因此数学课程内容也是学生在 初中阶段学习其他课程的必要基础 因此，义务教育的数学课程能为学生未来生活、工作和学习奠定重要的基础 二、普及性（1）初中阶段的数学课程应当在适龄少年中得到普及，即每一个适龄 的学生都有充分的机会学习它 （2）初中数学课程内容应当能够为所有适龄学生在具备相应学习条件 的前提下，通过自己的努力而掌握 三、发展性
总结离散数学知识点 第二章命题逻辑 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.N ，表示自然数集， 1,2,3 ??，不包括 0； 2.基：集合 A 中不同元素的个数， |A|； 3.集：定集合 A，以集合 A 的所有子集元素成的集合，P(A) ； 4.若集合 A 有 n 个元素，集 P(A) 有2 n个元素， |P(A)|= 2| A| = 2 n； 5.集合的分划： (等价关系 ) ①每一个分划都是由集合 A 的几个子集构成的集合； ② 几个子集相交空，相并全(A)； 6.集合的分划与覆盖的比： 分划：每个元素均出且出一次在子集中； 覆盖：只要求每个元素都出，没有要求只出一次； 第五章关系 1.若集合 A 有 m 个元素，集合 B 有 n 个元素，笛卡 A×B 的基数mn， A 到 B 上可以定2mn种不同的关系； 2.若集合 A 有 n 个元素， |A ×A|= n2，A 上有2n2个不同的关系； 3.全关系的性：自反性，称性，性； 空关系的性：反自反性，反称性，性；
离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式
将一个普通公式转换为范式的基本步骤
1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x)∨WL(x))，即量词的后面为合取式 例题 R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ?x ?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的乌龟跑得快表示为：?x ?y(R(x)∧T(y)→H(x,y)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式
1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={