(1) f(0)?g(0). (2) f(n')?h(f(n)).
定理2（递归原理）对于给定的函数g和h，能唯一定义N上一个函数f满足上述递归条件。 一般集合S的归纳定义：
(1) 指定一个集合M。（基元，生成元）
(2) 指定k个函数g1,g2,.....,gk为生成函数.分别为n1,n2,.....,nk元函数。 归纳生成集合S：S:??M,{g1,g2,.....,gk}?。 归纳定义. 集合S是满足如下条件的最小集合T： （1）M?T 。
（2）对于每个1?i?k，
如果x1,.....xn?T，则gi(x1,.....xn)?T。
ii设h,h1,......,hk为k+1个己知基函数：
h:M?Shi:Sni?S(i?1,2,...,k).
递归原理定义S上的一个函数f:
f(x):?h(x)(x?M)f(gi(x1,.....xn)):?hi(f(x1),.....,f(xn))(i?1,2,...,k)
ii定理3（递归原理）对于给定的函数h,h1,......,hk，能唯一定义S上一个函数f满足上述递归条件。
归纳集生成系统：S:??M,{g1,g2,.....,gk}?。 递归函数生成系统：S:??S,{h,h1,h2,.....,hk}?。
S:??M,{g1,g2,.....,gk};{h,h1,h2,.....,hk}?
例：自然数（算术）系统
N:??{0},{s};{c0,?,*}?.x'?s(x)?x?1,c0(x)?0
5
第二章 经典命题逻辑
命题定义：具有明确真假值的（对象）陈述。
简单命题：最小命题。（最简单，不可分解，原子，……） 复杂命题：借助联结词组合后命题小命题。 组合方式：
（1）一元：否定、不、非。 （2）二元：
或；且；如果…,则…；除非；当…,才有…; 仅当…,才有…。等等。
描述缺陷：自然语言。（非通用标准语言） 形式语言：命题语言LP。（通用） 字母表：0，1，p,q,r,……。 运算符：?,?,?,?,?。
真---1；假---0。
命题公式的生成：（归纳定义命题公式集Form(LP)）
PP（1）（归纳基）：Atom(L)?{p,q,r,......}?Form(L)。
（原子命题公式集）
P（2）（归纳定义）：如果A,B?Form(L)，则
?A,(A*B)?Form(LP)。其中，*?{?,?,?,?}。 （3）Form(LP)只含通过有限次使用（1）（2）得到的符号串。 结构归纳法：将Form(LP)类比自然数集N。 设P为一个性质，P(x)对表示x具有性质P。
类似于数学归纳法，引入关于Form(LP)上的某个性质（结论）P是否成立（真）的结构归纳法。
（1）（归纳基） P关于原子命题公式成立。（归纳基）
（2）（归纳步） 对A,B?Form(LP)，假定P关于命题公式A、B成立。验证：P关于命题公
6
式?A,(A*B)成立。其中，*?{?,?,?,?}。 语义解释：命题公式的解释(赋值)。
对原子命题公式的解释：（形式上是一个映射）
v:Atom(LP)?{0,1}。称为一个赋值。
理解为：p在v下被解释为pv?{0,1}。pv?v(p) 0表示“假”。1表示“真”。
基于这样的解释系统，命题逻辑只研究具有明确真、假区分的对象。这就是命题限制到具有明确真、假意义的陈述语句的根本原因。 对联结词运算符号的解释：
p 0 1 p 0 0 1 1 q 0 1 0 1 ?p 1 0
p?q 0 1 1 1 p?q 0 0 0 1 p?q 1 1 0 1 p?q 1 0 0 1
对命题公式的解释：对于一个公式A，在一个赋值v下总可以计算出它的真值：Av?{0,1}。（归纳计算）
(1)pv?{0,1}.?1ifpv?0(2)(?p)??. v0ifp?1??0ifAv?Bv?0v(3)(A?B)??.o.w.?1v 7
?1ifAv?Bv?1(4)(A?B)??.o.w.?0v?0ifAv?1andBv?0(5)(A?B)??.
o.w.?1v?1ifAv?Bv(6)(A?B)??.o.w.?0v命题公式A的真值表：在所有可能的赋值v下，将取值结果列入表中。 如： (┐p∧q)→┐r的真值表
可满足性：公式A是可满足，如果至少存在一个赋值v使A取真。
如果公式A含有n个变元，验证公式A的可满足性需要对2个赋值逐一验证。直观上需要指数验证时间。
可满足性判定问题（SAT问题）： 实例：一个命题公式A。
询问：是否存在一个赋值v使A取真（满足A）？ 验证算法存在！
重言式：A每一个赋值下取值均为真。 矛盾式：A每一个赋值下取值均为假。
8
n SAT问题的在计算机科学中的地位：
SAT问题是计算机科学中的核心问题。曾被著名美籍华人数理逻辑学家王浩称为“当代数理逻辑和理论计算机的第一问题”。
计算机科学家们一直都在寻求各种快速策略和方法改进求解SAT问题。现已证明：工程技术、军事、人工智能、并发控制、交通运输等领域中的诸多重要问题（如程控电话的自动交换，大型数据库的维护，大规模集成电路的自动布线，软件自动开发，机器人动作规划等）都涉及到SAT问题。
SAT问题是NP完全问题。从理论上说，SAT问题不能在多项式时间内解决，直观上它超出了现代计算机的能力。所以，SAT问题是计算机科学技术发展中的“瓶颈”问题。
从理论上讲，可满足性判定问题是NP完全的，然而在实际应用中，并非每一个CNF公式的可满足性问题的判定都需要指数时间。根据统计分析，对于3-CNF公式而言，出现在公式中的子句数与变元数之比是一个重要的参数，当公式的这个参数在4.25附近时，公式的可满足性的判定的确难。但是，当公式的这个参数远离4.25时，公式的可满足性的判定有可能在多项式时间内就可以完成。
约束满足性问题（CSP问题）：q?CSPW n 个变元：u1,......,un。
m 个q元函数：?i(ui1,......,uiq):Wq?{0,1}。
可满足性：(?v?(a1,......,an)?Wn)(?i)[?iv(ai1,......,aiq)?1]。 （CSP问题）：q?CSPW
实例：一个约束??{?1,......,?m}。
询问：是否存在一个赋值(a1,......,an)?Wn使得(?i)[?iv(ai,......,ai)?1]？
1q（回到命题公式讨论）
重言式一定是可满足式，但反之不真。因而，若公式A是可满足式，且它至少存在一个成假赋值，则称A为非重言式的可满足式。
(1) 若真值表最后一列全为1，则公式为重言式。 (2) 若真值表最后一列全为0，则公式为矛盾式。
(3) 若真值表最后一列中至少有一个1，则公式为可满足式。
9