离散数学(正在施工)

alittlemc

学习:离散数学

发布于：2019年11月14日

温馨提示:请使用电脑浏览器打开,以确保最佳的阅读体验,谢谢.(￣▽￣)”

第一章 命题逻辑

1.1 命题与联结词

命题:

• **命题:**非真即假(唯一)的陈述句(陈述句的悖论除外)

• **简单命题(原子命题):**不能再被分解的更简单的命题.
• **复合命题:**简单命题通过联结词联结而成的命题.

联结词

• ┐:否定
• ∧:合取
• ∨:析取
• →:蕴涵
• ↔:等值

1.2.命题公司及赋值

• **命题常项\命题常元:**常量,不变的.
• **公式\合式公式\命题公式\命题形式:**按规律把联结词合小括号联结起来的符号串.

• **成真赋值\成假赋值:**值为真\假的一组赋值.

  可以用真值表法来求.

• **矛盾式\永假式:**各种赋值都为假.
• **重言式\永真式:**各种赋值都为真.
  • (特殊)**可满足式:**至少有一组赋值为真(包含永真式,,也可以全真)

第二章 命题逻辑等值演算

2.1.等值式(⇔,中间双线,不是联结词)

等值式:

• 如果A↔B为重言式,那么A和B是等值的,记A⇔B.

等值式公式(等值演算):

• 结合律(x=∧或∨):
  • Ax(BxC)⇔(AxB)xC
  • 在作用域中,如果同为∧ or ∨,位置调换不影响.
• 分配律(if x=∧ then y=∨,if x=∨ then y=∧):
  • Ax(ByC)⇔(AxB)y(AxC)
  • 就是开括号.
• 德摩根律(if x=∧ then y=∨,if x=∨ then y=∧):
  • ┐(AxB)⇔┐Ay┐B
  • ┐在外,开括号后∧和∨互变
• 蕴涵等式:
  • A→B┐A∨B
• 等价等值式
  • A↔B⇔(A→B)∧(B→A)
  • 可以互推,就等值.

    求⇎可以直接用等值表法,比用等值演算方便.

2.2.析取范式和合取范式

• **简单合取\析取式:**由于有限个文字(命题变项及其否定)组成的合取\析取式.

  • 其实没必要在乎这个,因为我们学的公式,都是简单合取式和简单析取式.

• **合取\析取范式(简称范式):**由于有限个简单合取\析取组成的.

• 和上面的说明一样,没必要记.

• 任意命题公式都存在合取\析取范式.

求主范式时,可以表示出赋值的对应真假情况

eg:字母p,q,求主析取.

p

⇔p∧(q∨┐q) —主析取在括号内体现,外面反正,取合取

⇔(p∧q)∨(p∧┐q) —然后排列组合好

2.3.联结词完备集

S={┐,∧,∨}
其他的不考.

2.3.可满足性问题与消解法

不考

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

3.1.推理的形式结构

推理正确,但是结论不一定正确(A→B,1?1?0?1,只不过是蕴涵正确而已)

• 文字解释
  • .分割前提
  • 所以后为结论

&一般:
前提:A,B
结论:C

&附加前提:
前提:A,B
结论:C→D
等价为
前提:A,B,C
结论:D

3.2.自然推理系统P

• 推理规则

3.3.消解证明法

不会

第四章 一阶逻辑基本概念

4.1.一阶逻辑命题符号化

弥补命题逻辑(前面的内容)具有的局限性.

• **个体词:**一般是主语.

  • **个体常项:**固定不变的.{a,b,c}
  • **个体变向:**抽象可变的.{x,y,z}

• **个体域:**个体项的取值范围.

  • 比如:人类,有理数等.
  • 默认是全总个体域(宇宙万物).

• **谓词:**描述个体词之间的关系.{F,G,H}

  • 比如
    • F(x):x是人.
    • G(x,y):x>y.
  • n元谓词:传入n个谓词变项(抽象的).
    • F(x,y,z)—>3元/
    • F(a,b)—>0元,因为传入都是谓词常项(具体的).

• **量词:**全称∀和存在∃

• 三要素:个体词,量词,谓词 —(三个词)

题目:所有人都喜欢吃饭.
解:
个体域(全总个体域)
–找谓词F(x):x是人,G(x):x喜欢吃饭.
∀x(F(x)→G(x))

• 一般∀和→,∃和∨是一对

4.2.一阶逻辑公式及其解释

一阶语言:符号组成
(不重要)

• 基本术语

  ∀xF(x,y)

  • x是约束出现,为指导变元.
  • y是自由出现.
  • F(x,y)为辖域(可以控制到的范围).

∀xF(x,y)→∀yG(x,y)

• x约束出现1次,自由出现1次.
• y约束出现1次,自由出现1次.

• **封闭的公式(闭式):**没有任何的变项自由出现.

• 解释I:(以后写)

• 代换实例:(课本P69)
  • 谓词用命题变项代替.

    一般用来求永正/矛盾,要不然就求不了的.

第五章 一阶逻辑等值演算与推理

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

这里说的等值式,命题逻辑的等值式也同样适用

(不想记)

5.2.一阶逻辑前束范式

• **前束范式:**量词全部提前,开头不能有┐
• 用5.1小节的内容来求

5.3.一阶逻辑的推理理论

先不写了

第六章 集合代数

6.1.集合的基本概念

集合元素…

• 元素∈集合

• 集合⊆集合

• **空集:**x∈Ø (必错),空集不含子集.

• **n元集合:**有n个子集,.

6.2.集合运算

• **幂集:**把元素的所有的子集组成的集合.
  • P( { a , b } )={ Ø , { a } , { b } , { a , b } }.

• 广义交∩:**把所有的元素的公共元素**取出来组成,A不能是空集.

  • A={ {a , b} , { a } , { a ,d} }
  • ∩A={ a }

• 广义并∪:**把所有的的元素的全部元素**拆出来组成的集合,元素没有元素就用∪起来.

  • A={ a , { b , c } , { { c } , d } }
  • ∪A={ b , c , { c } , d } ∪ a

• **对称差⊕:**去除了公共部分的其他全部部分.

  • A={ 1 , 2 , 3 } B={ 1 , 4 , 5 }
  • A⊕B={ 2 , 3 , 4 , 5 }

• **绝对补~:**全集去出本集合剩下的.

  • E={ a , b , c } A={ a }
  • ~A={ b , c }

• **相对补-:**A-B,A特有的B没有.

6.3.有穷集的计数

P96

6.4.集合恒等式

P100

第七章 二元关系

7.1.有序对与笛卡尔积

• **有序对<x,y>:**只有两个元素x,y,并且顺序不可交换.

• **笛卡尔积:**按规律排序–A×B={<x,y>|x∈A and y∈B}

  • A={ a , b } B={ 0 , 1 , 2 }
  • A×B={ < a , 0 > , < a , 1 > , < a , 2 > , < b , 0 > , < b , 1 > , < b , 2 > }

7.2.二元关系

• 二元关系R包括:
  • 空集
  • 所有的元素都是<x,y>有序对
• 表示:
  • 1R2表示<1,2>∈R.
  • A×B的子集称之为A到B的二元关系 .
    • A×A同理是A上的二元关系.
    • R集是A×的子集.

• 全域关系:
  • E_A=A×A 自交
• 恒等关系:
  • I_A={<x,x>|x∈A} 对称
• 小于等于关系:
  • L_A={<x,y>|x,y∈A,x≤y} 后面比前面大.
• 整除关系:
  • D_A={<x,y>|x,y∈A,x|y} 后面可除前余数为0.
• 包含关系:
  • R_⊆={<x,y>|x,y∈A,x⊆y} 后是前的爸爸.

7.3.关系的运算

• 定义域:domR

• 值域:ranR

• 域:fldR fldR=domR∪ranR

• 逆关系:R^-1
  • R^-1={<x,y>|<y,x>∈R} 前后调换.
• 右复合:F^oG
  • F={<a,**b**>}
  • G={<**b**,c>}
  • F^oG={<a,c>}
• 限制:R↾A
  • A={1,2,3}
  • R={<1,2>,<1,3>,<3,4>}
  • R↾A={<1,2>,<1,3>} 找出R二元中由A元素组成的.
• 像:R[A]
  • R[A]=ran(R↾A) 限制的值域.
• n次幂:Rⁿ
  • n=0时为 I (前换一样<x,x>)
  • R^n+m=R^{n o} R^m

7.4.关系的性质

• 自反性:
  • 每个顶点都有环
• 反自反性:
  • 每个顶点都没有环
• **对称性:**∀x∀y(x,y∈A∧<x,y>∈R→<y,x>∈R)
  • 所有的元素交换x,y都在R中
  • **无单边性:**两顶点之间一定是双边.
• 反对称性:
  • 无双向边
• 传递性:
  • a到b有边,三角形两同项一异项目.

7.5.关系的闭包

• r自反
  • 全部顶点没有环就加上环.
• s对称
  • 全部单向的边,补上反方向边.
• t传递
  • 两两顶点之间的边都有来有回.

7.6.等价关系与划分

• P131

7.7.偏序关系

ppt7

P136

更新于：2020年1月12日

离散数学