离散数学精简讲义

《离散数学精简讲义》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一编数理逻辑命题逻辑1.1命题符号化否定词┑，合取词∧，析取词∨，蕴含词→，等值词↔若一个命题是一个简单陈述句，则称之为简单命题；由简单命题通过┑、∧、∨、→、↔这些联结词组成的命题称为复合命题；P→Q是条件命题；P↔Q是双条件命题。1.2合式公式命题常元T，F命题变元P₁，P₂，...P联结词┑∧∨→↔辅助词（）这个字母表可记为∑（P₁，P₂，…）,如不引起混淆，也可简记为∑。∑（P₁，P₂，…）表示字母表∑（P₁，P₂，…）上的所有字符串，包括空串ɛ；用∑⁺表示∑上的所有非空符号串的集合。●合式公式：（1）命题常元或命题变元是合式公式；（2）若A，B是合式公式，则（

2、┑A），（A∧），（A∨B），（A→B），（A↔B）是合式公式；（3）只有通过有限次使用（1），（2）所得到的符号串才是合式公式。代入和替换：替换只要求对该子公式的某一出现或某几个出现进行替换，而不是对每一处出现都进行替换。1.3永真公式解释：设是含有这n 个命题变元的合式公式，对的一组真值赋值，称为对A的一个解释，记作I=，其中取0或1，I()=。合式公式可分为：永真式，永假式，可满足式。逻辑恒等式：永真蕴含式：1.4范式文字：命题变元或命题变元的否定称为文字，并称命题变元为正文字，命题变元的否定为负文字。基本和的归纳定义是：①文字是基本和；②若A，B是基本和，则A∨B

3、是基本和。合取范式的归纳定义如下：①基本和是合取范式；②若A，B是合取范式，则（A∧B）是合取范式。主合取范式的归纳定义是：①极大项是主合取范式；②若A，B是主合取范式，则（A∧B）是主合取范式。基本积的归纳定义是：①文字是基本积；②若A，B是基本积，则A∧B是基本积。析取范式的归纳定义如下：①基本积是析取范式；②若A，B是析取范式，则（A∨B）是析取范式。主析取范式的归纳定义是：①极小项是主析取范式；②若A，B是主析取范式，则（A∨B）是主析取范式。▲1.5推理理论推理规则：⑴附加规则⑵化简规则⑶MP规则⑷拒取式⑸析取三段论⑹假言三段论⑺合取引入⑻构造二性难▲证明方法：

4、⑴前件假证明法⑵后件真证明法⑶直接证明法⑷间接证明法⑸分情况证明法⑹附加前提证明法⑺反证法▲公理系统一般由下列几部分组成：⑴初始符号：它们是不经定义而直接使用的符号；⑵形成规则：确定定义在初始符号上的哪些符号串是合式公式；⑶公理集：它们是不经证明而被认为是恒真的命题；⑷推理规则：规定如何从公理和前面已经推导出的合式公式经过符号变形而推出其它公式。命题逻辑的公理系统L的定义如下：⑴初始符号：⑵形成规则：①P是合式公式；②若A是合式公式，则（┑A）是合式公式；③若A和B是合式公式，则（A→B）是合式公式；④只有通过有限次使用①~③得到的符号串是合式公式。⑶公理集：（L）（A→

5、（B→A））；（L）（（A→（B→C））→（（A→B）→（A→C）））；（L）（（（┑A）→（┑B））→（B→A））。⑷推理规则：从A和（A→B）可推出B。证明：L中的证明是合式公式的一个有穷序列A，A，…A,其中A或者是公理，或者是序列中其前的某两个合式公式经MP规则得到。并称该证明人是A是在L中的证明，称A是L的定理，记作。演绎：设是合式公式集，L中的从推出A的一个演绎是合式公式的一个有穷序列A，A，…A，其中A或者是公理，或者是中的一个合式公式，或者是序列中其前的某两个合式公式经MP规则得到。中的合式公式称为假设。L的演绎定理：推论：设A，B，C是L的任意合式公式，

6、则{A→B，B→C}A→C。1.6联结词的全功能集设C是联结词的集合，若任何公式均可由仅含C中联结词的公式等价的表示，则称C是联结词的全功能集；若从C中任意去掉一个联结词，则C不是全功能集，则称C是联结词的极小全功能集。2.一阶逻辑2.1命题符号化在一阶逻辑中，我们把所讨论的对象称为个体，用来表示个体的符号称为个体词。若一个个体词表示一个特定个体，则称之为个体常元；若一个个体词泛指任何一个个体，则称之为个体变元；个体变元的取值范围称为个体域或论域。在简单命题中，表示个体的性质或个体之间联系的词称为谓词，表示数量的词称为量词，量词一般有两种：全称量词∀和存在量词∃2.2合式

7、公式一阶谓词逻辑的字母表∑为个体常元a,b,c,…个体变元x,y,z,…函数符号f,g,h,…(n元函数f可记为f)谓词符号P，Q，R，…联结词┑∧∨→↔量词∀∃辅助符号（）项的归纳定义如下：⑴个体常元和个体变元是项；⑵若t,t,t,…是项，则f(t,t,t,…)是项；⑶只有通过有限次使用（1）和（2）所得到的符号串是项。设t,t,t,…t是项，则称P(t,t,t,…t)为原子公式。合式公式的归纳定义如下：⑴原子公式是合式公式；⑵若A，B是合式公式，则（┑A），（A∧B），（A∨B），（A→B），（A↔B），∀xA,∃xA是合