一、命题演算的自然推理形式系统N 二、怎么在计算机上实现如下有效推理:

为什么只考虑五个联结词?即 这五个联结词能否表示所有联结词? 这五个联结词是否有多余的? 要回答这两个问题,必须回答:

1.什么是命题? 命题是陈述客观外界发生事情的陈述句。 命题是或为真或为假的陈述句

什么是数理逻辑 字面含义:数学理论的逻辑。逻辑是研 究演绎(推理)规律的学科。 广义理解:用数学方法研究演绎规律的 学科。 狭义理解:用数学方法研究数学中演绎 规律和数学基础的学科。 研究对象:推理过程的正确性标准。 是数学的一个分支。又称符号逻辑等

一、KC是一个较Nc简洁的谓词演算形式系统 二、Kc是在P的基础上建立的 三、Kc的各组成部分如下:

复习 一阶谓词演算的符号化: 个体变元:x,Y,z,… 个体常元:a,b,c ·谓词:Fn,Gn,Hn, 函数:fn,gn,hn, 量词:全称量词V,存在量词3

1. Peano系统 2.后继,归纳集,自然数,自然数集 3.数学归纳法原理 4.传递集 5.自然数的运算 6.自然数上的序关系

1.k-(点,面,边)着色,k-(点,面,边)色图,点色数x(G),面色数x*(G),边色数x(G) 2.x(G)上界, Brooks定理 3.五色定理 4. Vizing定理 5.色多项式f(G,k)

一、四色问题 二、平面图,面,极大平面图 三、欧拉公式 四、Kuratowski定理 五、对偶图,自对偶图 六、外平面图 七、平面哈密顿图

1.周游世界,哈密顿通(回)路,哈密顿图 2.判定哈密顿图的必要条件 3.判定哈密顿图的充分条件 4.边不重的哈密顿回路 5.货郎问题,计算复杂性