第二节 一阶语言
一、基本概念：一阶语言的八类符号 1、个体符号：a、b、c
2、关系符号：F、G、H（n元关系符号、相等符号（特殊的二元关系符号）） 3、函数符号：f、g、h（m元函数符号）
4、自由变元符号和约束变元符号（u、v、w和x、y、z） 5、联结符号（5类联结符号）
6、量词符号（全称量词符号?、存在量词符号?）（量词、全称量词、存在量词） 7、标点符号（左括号、右括号和标点）
二、基本概念：项
1、 概念： t∈Term（L），当且仅当它能由（有限次使用）以下的⑴、⑵生成： ⑴、a、u∈Term（L）（单独一个个体符号是项、单独一个自由变元符号是项） ⑵、如果t1，…tn∈Term（L），并且f是n元函数符号，则f（t1，…tn）是项 2、 概念：闭项（不含自由变元符号的项）
3、 概念：对项的结构作归纳（如何证明Term（L）中所有的元都具有某个性质）
三、基本概念：原子公式
1、 概念：L的表达式是Atom（L）中的元，当且仅当它有⑴、⑵两种形式之一 ⑴、F（t1，…tn），其中F是n元关系符号，并且t1，…tn∈Term（L） ⑵、≡（t1，t2）（可以更直观的简写为：t1≡t2） 2、 注意：原子公式不是归纳定义
四、基本概念：公式
1、 概念：U（s1，…，sn） 表示符号s1，…，sn出现在表达式U中 2、 概念：A∈Form（L），当且仅当它能由（有限次使用）以下的⑴～⑷生成： ⑴、Atom（L）∈Form（L） ⑵、如果A∈Form（L），则（?A）∈Form（L） ⑶、如果A、B∈Form（L），则（A*B）∈Form（L） ⑷、如果A（u）∈Form（L），x不在A（u）中出现，则?xA（x），?xA（x）∈Form（L） 3、 概念：闭公式（语句）（不含自由变元符号的公式）
4、 概念：拟公式（与公式结构相似的表达式、拟公式不是公式） 5、 概念：对公式的结构作归纳
五、定理群1
1、 定理1：L的任何项恰好具有以下三种形式之一：
2、 定理2：如果t是f（t1，…tn）的段，则t＝f（t1，…tn）或t是ti的段 3、 定理3：L的任何公式恰好具有以下八种形式之一：
六、定理群2
1、 概念：全称公式、存在公式（全称公式：?xA（x），存在公式：?xA（x））
2、 概念：量词的辖域（如果?xA（x）是B的段，则称A（x）是?x在B中的辖域） 3、 性质：量词的辖域是拟公式，联结符号如果出现在量词的辖域中，则可能是拟公式 4、 定理1：L的任何公式中任何全称量词或存在量词有唯一的辖域
5、 定理2：如果A是?xB（x）中的段，则A＝?xB（x）或是?xB（x）的段
第三节 语义
一、基本概念：一阶语言的解释（后面五类符号，在所有一阶语言中都是相同的） 1、一阶语言和某个结构有联系（一阶语言是用来描述这个结构的）
2、一阶语言和任何结构无联系（一阶语言是一个一般的，抽象的一阶语言） 首先需要一个论域（只要求是不空的集合），然后再在该论域中如下解释： ⑴、个体符号解释为论域中的个体
⑵、n元关系符号解释为论域上的n元关系 ⑶、m元函数符号解释为论域上的m元全函数
3、概念：全函数（处处有定义的函数，函数的运算结果不会跑到论域之外）
二、基本概念 1、 基本规定
⑴、项f（t1，…tn）被解释为论域中的个体：?（a1，…an） ⑵、原子公式F（t1，…tn）被解释为命题：a1，…an有R关系 2、 系列结论
⑴、闭项和闭公式的解释（分别解释为论域中的个体，或命题）
⑵、含自由变元的项，经过解释（得到论域上的n元全函数）和指派，得到论域中的个体 ⑶、对于一个含自由变元的公式，经过解释（得到命题函数）和指派，得到命题 3、 说明
⑴、区分：个体符号解释为个体，自由变元符号指派为个体
⑵、一次性指派：同时将所有的可数无限多个自由变元符号，指派为论域中的个体
三、基本概念
1、 概念：一阶语言L的赋值v（包括一个论域D和一个赋值函数v）
2、 概念：项的值（L的项在以D为论域的赋值v之下的值，递归定义如下） 3、 定理：设v是以D为论域的赋值，并且t∈Term（L），则tV∈D（对项的结构做归纳）
四、基本概念
1、 概念：定义一个新的赋值v（u/a）：它与原来的v处处相同，只是作用在自由变元符号u时，可能会不同
2、 概念：公式的真假值（L的公式在以D为论域的赋值v之下的真假值，递归定义如下） ⑴、取u不在A（x）中出现，由A（x）构作A（u）
⑵、?xA（x）是由A（u）生成的，所以?xA（x）V要由A（u）V来决定
⑶、?xA（x）V＝1的涵义：无论v指派u为D中的哪一个个体a，都有A（u）V＝1 ⑷、对于原来在A（x）中，现在仍在A（u）中的自由变元w来说，wV保持不变
★★归纳：如果v是?xA（x）V中的指派，那么v（u/a）表示除此之外，还要给自由变元符号U作指派
3、定理：设v是以D为论域的赋值，A是公式，则AV∈{0，1}
五、基本概念
1、 概念：一致的（有相同论域的两个赋值v和v’，在四类符号上是一致的）
2、 定理：设v和v’是有相同论域的两个赋值，并且它们在项t和公式A所含的四类符号上都是一致的，则tV＝tV’，AV=AV’
六、基本概念
1、 概念：∑V（∑表示Form（L）中的公式集）
2、 概念：∑是可满足的（存在赋值v，使得∑V＝1）
3、 概念：A∈Form（L）是有效的（对于任何赋值v，都有∑V＝1）
4、 性质：可满足是由命题的内容决定的，而有效性是由公式的逻辑形式决定的 5、 性质：不存在一个统一的算法，用来判断L中公式的有效性或者可满足性
第四节 逻辑推论
一、逻辑推论
1、 符号：∑╞A（A是∑的逻辑推论，其中∑?Form（L），A∈Form（L）） 2、 概念：∑╞A，当且仅当对于任何赋值V，如果∑V＝1，则AV＝1 3、 概念：∑|≠A（存在赋值V，使得∑V＝1，AV＝0）
★★前者是指任何论域上的任何赋值V，后者是指存在以D为论域的赋值V 4、 性质：?╞A（则A是有效公式） 5、 概念：逻辑等值公式A|＝|B
二、例题分析：注意找到捷径和方法
1、 如何证明一个逻辑推论是成立的（直接证明或者反证法）
2、 如何证明一个逻辑推论是不成立的（构造出这样的赋值V，使得∑V＝1，AV＝0） ⑴、性质：当确定赋值的论域时，问题在于论域的大小，和论域中有怎样的个体无关 ⑵、D上的n元关系F：FV＝{
三、定理群
1、 引理1：如果A|＝|A’并且B|＝|B’，则有?A|＝|?A’等7条性质
2、 约定：B、C是拟公式，则B|=|C的含义是指B’|=|C’（注意B’、C’的形成）
3、 等值替换定理：设B|＝|C并且在A中把B的某些出现替换为C而得到A’，则A|＝|A’ （注意：B和C可能是拟公式） 4、 对偶性定理：A’|＝|?A（其中A’是A的对偶）
面向计算机科学的数理逻辑复习文档
