0%

离散数学笔记

写在前面

离散数学好像只学第1,2,5部分

第1部分 数理逻辑

第1章 命题逻辑的基本概念

1.1 命题与连接词

命题是判断结果唯一的陈述句
判断结果称为命题的真值,真值只取两个值:
真值为真的命题称作真命题,真值为假的命题称作假命题

不能被分解成更简单的命题称作简单命题原子命题
由简单命题通过联结词联结而成的命题称作复合命题

由真能推出假、又由假能推出真,从而既不为真也不能为假的陈述句称作悖论,悖论不是命题

定义1.1 设p为命题,复合命题“非p”(或p的否定)称作p否定式,记作¬p,符号¬否定联结词¬p为真当且仅当p为假
定义1.2 设p,q为两个命题,复合命题“p并且q”(或pq)称为pq合取式,记作pq. 称作合取联结词pq为真,当且仅当pq同时为真
定义1.3 设p,q为两个命题,符合命题pq称作pq析取式,记作pq. 称作析取联结词. 规定pq为假当且仅当pq同时为假

相容或 pq
排斥或 (¬pq)(p¬q)

定义1.4 设p,q为两个命题,复合命题“如果p,则q”称为pq蕴含式,记作pq,并称p是蕴含式的前件q为蕴含式的后件. 称作蕴含联结词,并规定pq为假当且仅当p为真q为假
pq的逻辑关系为qp的必要条件

自然语言里,qp的必要条件的叙述方式

  • 只要p,就q
  • 因为p,所以q
  • p仅当q
  • 只有q,才p
  • 除非qp

定义1.5 设p,q为两个命题,复合命题“p仅当q”称作pq等价式,记作pq称作等价联结词. 规定pq为真,当且仅当pq同时为真或同时为假
pq的逻辑关系为pq互为充分必要条件

优先顺序为(),¬,,,,

1.2 命题公式及其赋值

简单命题是命题逻辑中最基本的研究单位,其真值是确定的,又称作命题常项命题常元.
取值1(真)或0(假)的变元称作命题变项命题变元
可以用命题变项表示真值可以变化的陈述句,命题变项不是命题.
将命题变项用联结词和圆括号按照一定的逻辑关系联结起来的符号串称作合式公式

定义1.6 (1) 单个命题变项是合式公式,并称为原子命题公式
(2) 若A是合式公式,则(¬A)是合式公式
(3) 若A,B是合式公式,则(AB),(AB),(AB),(AB)是合式公式
(4) 有限次地应用(1)-(3)形成的符号串是合式公式

定义1.6采用的是归纳定义或递归定义的方式
其中A,B用它们表示任意的合式公式,称作元语言符号,而某个具体的公式称作对象语言符号

定义1.7 (1) 若公式A是单个的命题变项,则称A为0层公式
(2) 称An+1(n0)层公式是指下面情况之一
(a) A=≠B, Bn层公式
(b) A=BC, 其中BC分别为ij层公式,且n=max{i,j}
(c) A=BC, 其中B,C的层级及n同(b)
(d) A=BC, 其中B,C的层级及n同(b)
(e) A=BC, 其中B,C的层级及n同(b)
(3) 若公式A的层次为k,则称Ak层公式

定义1.8 设p1,p2,,pn是出现在公式A中的全部命题变项,给p1,p2,,pn各指定一个真值,称为对A的一个赋值解释.
若指定的一组真值使A为1,则称这组值为A成真赋值;若使A为0,则称这组值为A成假赋值.

赋值按下标顺序或字母顺序依次赋值

定义1.9 将命题公式A在所有赋值下取值情况列成表,称作A真值表.

定义1.10 设A为任一命题公式
(1) 若A在它的各种赋值下取值均为真,则称A重言式永真式.
(2) 若A在它的各种赋值下取值均为假,则称A矛盾式永假式.
(3) 若A不是矛盾式,则称A可满足式.
重言式一定为可满足式

设公式A,B中共含有命题变项p1,p2,,pn,而AB不全含这些命题变项,则称A中不含的命题变项为A哑元,即A的取值与哑元无关.

第2章 命题逻辑等值演算

2.1 等值式

定义2.1 设A,B是两个命题公式,若A,B构成的等价式AB为重言式,则称AB是等值的,记作AB.

常用的等值式模式

  1. 双重否定律 A¬¬A.
  2. 幂等式 AAA,AAA.
  3. 交换律 ABBA,ABBA.
  4. 结合律 (AB)CA(BC),(AB)CA(BC).
  5. 分配律 A(BC)(AB)(AC),A(BC)(AB)(AC).
  6. 德摩根律 ¬(AB)¬A¬B,¬(AB)¬A¬B.
  7. 吸收律 A(AB)A,A(AB)A.
  8. 零律 A11,A00.
  9. 同一律 A0A,A1A.
  10. 排中律 A¬A1.
  11. 矛盾律 A¬A0.
  12. 蕴涵等值律 AB¬AB.
  13. 等价等值律 AB(AB)(BA).
  14. 假言易位律 ABB¬A.
  15. 等价否定等值式 AB¬A¬B.
  16. 归谬论 (AB)(A¬B)¬A.

代入实例
由一直的等值式推演出另外一些等值式的过程称作等值演算.

置换规则Φ(A)是含公式A的命题公式,Φ(B)是用公式B置换Φ(A)A的所有出现后得到的命题公式. 若BA,则Φ(A)Φ(B).

2.2 析取范式与合取范式

定义2.2 命题变项及其否定统称作文字. 仅由有限个文字构成的析取式称作简单析取式. 仅由有限个文字构成的合取式称作简单合取式.

定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式
(2) 一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式

定义2.3 由有限个简单合取式的析取构成的命题公式称作析取范式. 由有限个简单析取式的合取构成的命题公式称作合取范式. 析取范式与合取范式统称作范式.

定理2.2 (1) 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式
(2) 一个合取范式是重言式当且仅当它的每个简单析取范式都是重言式.

定理2.3(范式存在定理) 任一命题公式都存在与之等值的析取范式与合取范式

定义2.4 在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项和它的存在的否定式恰好出现一个且仅出现一次,而且命题变项或它的否定式按照下标从小到大或按照字典顺序排列,称这样的简单合取式(简单析取式)为极小项(极大项).

每个极小项都有且仅由一个成真赋值,每个极大项只有一个成假赋值.

定理2.4 设miMi是命题变项含p1,p2,,pn的极小项和极大项,则¬miMi,¬Mimi.
定义2.5 所有简单合取式(简单析取式)都是极小项(极大项)的析取范式(合取范式)称为主析取范式(主合取范式).
定理2.5 任何命题公式都存在与之等值的主析取范式和主合取范式,并且是唯一的.

2.3 联结词的完备集

貌似这部分选修…

第3章 命题逻辑的推理理论

3.1 推理的形式结构

数理逻辑的主要任务是用数学的方法研究推理,所谓推理是指从前提除法推出结论的思维过程,而前提是已知的命题公式集合,结论是从前提出发应用推理规则推出的命题公式

定义3.1 设A1,A2,,AkB,若对于A1,A2,,AkB中出现的命题变项的任意一组赋值,或者A1A2Ak为假,或者当A1A2Ak为真时B也为真,则称由前提A1,A2,,Ak推出结论B的推理是有效的正确的,并称B有效的结论. B不一定是正确的.
由推理Γ推出B的推理记为ΓB. 若推理是正确的,则记为ΓB否则记ΓB为推理形式结构.

定理3.1 命题公式A1,A2,,Ak推出B的推理正确当且仅当A1A2AkB为重言式.
判断是否为重言式的方法 1. 真值表法 2. 等值演算法 3. 主析取范式法

有一些重要的重言蕴含式,称作推理定律.

  1. 附加律 A(AB)
  2. 化简律 (AB)A
  3. 假言推理 (AB)AB
  4. 拒取式 (AB)¬B¬A
  5. 析取三段论 (AB)¬BA
  6. 假言三段论 (AB)(BC)(AC)
  7. 等价三段论 (AB)(BC)(AC)
  8. 构造性二难 (AB)(CD)(AC)(BD),(AB)(¬AB)B
  9. 破坏性二难 (AB)(CD)(¬B¬D)(¬A¬C)

3.2 自然推理系统P

定义3.2 一个形式系统I由下面4个部分组成.
(1) 非空的字母表A(I).
(2) A(I)中符号构成的合式公式集E(I).
(3) E(I)中一些特殊的公式组成的公理集AX(I).
(4) 推理规则集R(I).
I记为4元组$.I$的形式语言系统,而$I$的形式演算系统.

形式系统一般分为两类. 一类是自然推理系统,他的特点是从任意给定的前提出发,应用系统中的推理规则进行推理演算,最后得到的命题公式是推理的结论。另一类是公理推理系统,它只能从若干条给定的公理出发,应用系统中的推理规则进行推理演算,得到的结论是系统中的重言式,称为系统中的定理。

定义3.3 自然推理系统P定义如下.

  1. 字母表
    (1) 命题变项符号: p,q,r,,pi,qi,ri,(i1).
    (2) 联结词符号: ¬,,,,.
    (3) 括号与逗号: (,),,.
  2. 合式公式 同定义1.6
  3. 推理规则
    (1) 前提引入规则: 在证明的任何步骤都可以引入前提
    (2) 结论引入规则: 在证明的任何步骤所得到的结论都可以作为后继证明的前提
    (3) 置换规则: 在证明的任何步骤,命题公式中的子公式都可以用等值的公式置换,得到公式序列的又一个公式
    由9条推理定律和结论引入规则可以导出以下各条推理规则
    (4) 假言推理规则(或分离规则): 若证明的公式序列中已出现过ABA,则由假言推理定律(AB)AB可知,BABA的有效结论. 图示ABAB(5) 附加规则:AAB(6) 化简规则ABA(7) 拒取式规则AB¬B¬A(8) 假言三段论规则ABBCAC

…就是符号表示一下,不打了,一共到12

设前提A1,A2,,Ak,结论B和公式序列C1,C2,,Cl. 如果每一个i(i=1,2,,l),Ci是某个Aj或者可由序列中前面的公式应用推理规则得到,并且Cl=B,则称公式序列C1,C2,,Cl是由A1,A2,,Ak推出B证明.

附加前提证明法: 推理形式结构 (A1A2Ak)(AB),可以改写成(A1A2AkA)B.
拆开可得到两式等值,若能证明后式为重言式则前式为重言式,称作附加前提证明法A称作附加前提

将结论的否定式作为前提引入并推出矛盾式的证明方法称作归谬法

3.3 消解证明法

消解证明法是根据归谬法的思想吗,采用消解规则构造证明的方法,它的基本做法是把前提中的公式和结论的否定都化成等值的合取范式,以这些合取范式中的所有简单析取式作为前提,用消解规则构造证明。如果能得到空式,则证明推理是正确的

第4章 一阶逻辑基本概念

量词用来表达出个体与总体之间的内在联系和数量关系,这就是一阶逻辑所研究的内容
一阶逻辑也称作一阶谓词逻辑或谓词逻辑

4.1 一阶逻辑命题符号化

个体词是指所研究对象中可以独立存在的具体的或抽象的客体
将表示具体或特定的客体个体词称作个体常项,一般用小写英文字母a,b,c表示
将表示抽象或泛指的个体词称作个体变项,常用x,y,z表示,并称个体变项的取值范围为个体域(或论域)
个体域可以是有穷集合也可以是无穷集合
有一个特殊的个体域,它是由宇宙间一切事物组成的,称作全总个体域

谓词是用来刻画个体词性质及个体词之间相互关系的词,常用F,G,H表示
表示具体性质或关系的谓词称作谓词常项,表示抽象或泛指的性质或关系的谓词称作谓词变项

一般地,含n(n1)个个体变项x1,x2,,xn的谓词P称作n元谓词,记作P(x1,x2,,xn)
n元谓词是以个体域为定义域,以{0,1}为值域的n元函数或关系
将不带个体变项的谓词称作0元谓词

表示个体常项或变项之间数量关系的词称作量词
“一切的”,“所有的”,“每一个”,“任意的”,“凡”,“都”等词统称作全称量词,用符号表示
“存在”,“有一个”,“有的”,“至少有一个”等词统称作存在量词,用符号表示

特性谓词的作用是将个体变元局限止在满足该谓词代表的性质或关系的范围之内
若个体域为全总个体域,对个体变项的范围用医院特性谓词描述
特性谓词的使用规则
(1) 对于全称量词x,其特性谓词作为蕴含式的前件加入
(2) 对于存在量词x,其特性谓词作为合取式的合取项加入

F是谓词常项时,xF(x)是一个命题. 如果把个体域中的任何一个个体a代入,F(a)都为真,则xF(x)为真;否则xF(x)为假. xF(x)也是一个命题. 如果个体域中存在一个个体a,使得F(a)为真,则xF(x)为真;否则xF(x)为假.

4.2 一阶逻辑公式及其解释

一阶语言是用于一阶逻辑的形式语言,一阶逻辑是建立在一阶语言上的逻辑体系.

个体常项符号、函数符号和谓词符号称作非逻辑符号,个体变项符号、量词符号、联结词符号和括号与逗号称作逻辑符号

定义4.2 L的项定义如下.
(1) 个体常项符号和个体变项符号是项
(2) 若φ(x1,x2,,xn)n元函数符号,t1,t2,,tnn个项,则φ(t1,t2,,tn)是项
(3) 所有的项都是有限次使用(1),(2)得到的
定义4.3 设R(x1,x2,,xn)Ln(n1)元谓词符号,t1,t2,,tnLn个项,称R(t1,t2,,tn)原子公式
定义4.4 合式公式的定义如下
(1) 原子公式是合式公式
(2) 若A是合式公式,则(¬A)也是合式公式
(3) 若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式
(4) 若A是合式公式,则xA,xA也是合式公式
(5) 只有有限次的应用(1)-(4)构成的符号串才是合式公式
L的合式公式也称作谓词公式,简称为公式
定义4.5 在公式xAxA中,称x指导变元A为量词的辖域. xx的辖域中,x的所有出现都称作约束出现A中不是约束出现的其他变项均称作自由出现
定义4.6 设A是任意的公式,若A中不含自由出现的个体变项,则称A封闭的公式,简称作闭式.

个体域及个体常项符号、函数符号、谓词符号的指定称作解释,指定自由出现的个体变项的值称作赋值

定义4.7 设L是由L生成的一阶语言,L的解释I由下面4部分组成
(a) 非空个体域DI.
(b) 对每一个个体常项符号aL,有一个a¯DI,称a¯aI中的解释.
(c) 对每一个n元函数符号fL,有一个DI上的n元函数f¯:DInDI,称f¯fI中的解释.
(d) 对每一个n元谓词符号FL,有一个DI上的n元谓词常项F¯,称F¯FI中的解释.
I下的赋值σ:对每一个个体变项符号x指定DI中的一个值σ(x).
设公式A,规定:在解释I和解释σ

  1. 取个体域DI
  2. A中含个体常项符号a就将它替换成a¯.
  3. A中含函数符号f就将它替换成f¯.
  4. A中含谓词符号F就将它替换成F¯
  5. A中含自由出现的个体变项符号x就将它替换成σ(x)
    把这样所得到的公式记作A. 称AAIσ下的解释,或AIσ下被解释成A
    定义4.8 设A为一公式,若A在任何解释和该解释下的任何赋值下均为真,则称A永真式(或称作逻辑有效式). 若A在任何解释和该解释下的任何赋值均为假,则称A矛盾式(或永假式). 若A在任何解释和该解释下的一个赋值使A为真,则称A可满足式
    定义4.9 设A0是含命题变项p1,p2,,pn的命题公式,A1,A2,,Ann个谓词公式,用Ai(1in)处处代替A0中的pi,所得的公式A称为A0代换实例.
    定理4.1 重言式的代换实例都是永真式,矛盾式的代换实例都是矛盾式

第5章 一阶逻辑等值演算和推理

5.1 一阶逻辑等值式与置换规则

定义5.1 设A,B是一阶逻辑中任意两个公式,若AB是永真式,则称AB等值,记作AB. 称AB等值式.

  1. 量词否定等值式
    (1) ¬xA(x)x¬A(x)
    (2) ¬xA(x)x¬A(x)
  2. 量词辖域收缩与扩张等值式
    (1) x(A(x)B)xA(x)B.
    x(A(x)B)xA(x)B.
    x(A(x)B)xA(x)B.
    x(BA(x))BxA(x).
    (2) x(A(x)B)xA(x)B.
    x(A(x)B)xA(x)B.
    x(A(x)B)xA(x)B.
    (BA(x))BxA(x).
  3. 量词分配等值式
    (1) x(A(x)B(x))xA(x)xB(x).
    (2) x(A(x)B(x))xA(x)xB(x).

规则

  1. 置换规则 设Φ(A)是含公式A的公式,Φ(B)是用公式B取代Φ(A)中所有的A之后所得到的公式. 那么,若AB,则Φ(A)Φ(B).
  2. 换名规则 设A为一公式,将A中某量词辖域中的一个约束变项的所有出现及相应的指导变元全部改成该量词辖域中未曾出现过的某个个体变项符号,公式中其余部分不变,将所得公式记作A,则AA.

5.2 一阶逻辑前束范式

定义5.2 具有如下形式Q1x1Q2x2QkxkB的一阶逻辑公式称作前束范式,其中Qi(1ik)B为不含量词的公式.
定理5.1(前束范式存在定理) 一阶逻辑中的任何公式都存在等值的前束范式.

5.3 一阶逻辑的推理理论

在一阶逻辑中,从前提A1,A2,,Ak出发推出结论B的推理的形式结构,依然采用如下的蕴含式形式A1A2AkB. 若为永真式,则称推理正确,否则称推理不正确.
在一阶逻辑中称永真式的蕴含式为推理定律. 若一个推理的形式结构是推理定律,则这个推理是正确的.

后面关于自然推理系统的定义就不写了

第2部分

第5部分

参考

  • 《离散数学(第2版)》,屈婉玲、耿素云、张立昂,高等教育出版社
Have fun.