第六节 形式推演
一、形式推演
1、 形式推演本质（形式推演仅涉及公式的结构，而与公式的语义无关） 2、 形式推演规则（共有11条规则） 3、 推论：如果A∈∑，则∑├A
二、形式可推演
1、 概念：形式可推演∑├A（∑├A，当且仅当存在有限序列∑1├A1，…∑n├An，其中的每一项∑k├Ak都是由使用某一形式推演规则生成，并且∑n＝∑，An＝A） 2、 概念的剖析：归纳定义
三、基础定理
1、 定理：如果∑├A，则存在有限的EO∈∑，使得∑O├A（对∑├A的结构做归纳） 2、 概念推广：∑├∑’（注意可以推广到无限情形） 3、 推演传递定理：如果∑├∑’，∑’├A，则∑├A
四、定理集群一（每一条都要求严格证明，并且反复记忆，作为后面证明的出发点） 1、 定理：（→定理群；定理2.6.4） ⑴、★★性质：A→B，A├B ⑵、★★性质：A→B，?B├ ?A ⑶、性质：A├B→A
⑷、性质：A→B，B→C ├A→C（蕴涵传递） ⑸、性质：A→（B→C）、A→B├A→C
2、 定理：（?定理群；定理2.6.5） ⑴、★★性质：??A├A；A├ ??A
⑵、★★性质：如果∑，A├B；∑，A├ ?B，则∑├ ?A（归谬律，或称（?＋）） ⑶、性质：A，?A├B
3、 定理：（→?定理群之一；定理2.6.6） ⑴、★★性质：A→B├ ?B→?A（以此为基础衍生的4条性质） ⑵、★★性质：如果A├B，则?B├ ?A（以此为基础衍生的4条性质） ⑶、★★性质：A├B，当且仅当Φ├A→B（严格证明之）
4、 定理（→?定理群之二；定理2.6.7） ⑴、性质：?A→A├A（相似性质：A→?A├ ?A） ⑵、性质：A→B，A→?B├ ?A（相似性质：A→B，?A→B├B） ⑶、性质：?（A→B）├A（相似性质：?（A→B）├ ?B）
五、定理集群二（每一条都要求严格证明，并且反复记忆，作为后面证明的出发点） 1、 概念：语法等值公式A|－|B
2、 定理（∧定理群；定理2.6.8） ⑴、★★性质：A∧B|－|A，B
⑵、性质：A∧B|－| B∧A（∧交换律） ⑶、性质：（A∧B）∧C|－| A∧(B∧C)（∧结合律） ⑷、★★★★性质：?（A∧B）|－| A→?B（相似性质：?（A→B）|－| A∧?B） ⑸、性质：?├ ?（A∧?A）（不矛盾律）
3、 定理（∨定理群；定理2.6.9）
⑴、★★性质：A├A∨B，B∨A（最关键还是规则本身：允许在前面或后面增加∨） ⑵、性质：A∨B |－|B∨A（∨交换律） ⑶、性质：（A∨B）∨C|－| A∨(B∨C)（∨结合律） ⑷、★★★★性质：A∨B |－| ?A→B（相似性质：?A∨B |－| A→B）（分析其证明步骤） ⑸、★★性质：?（A∨B）|－| ?A∧?B（Morgen定律） ⑹、★★性质：?（A∧B）|－| ?A∨?B（Morgen定律） ⑺、性质：?├ A∨?A（排中律）
4、 定理（∨∧定理群；定理2.6.10）
⑴、★★性质：A∨（B∧C）|－| (A∨B)∧（A∨C)（∨∧分配律） ⑵、★★性质：A∧（B∨C）|－| (A∧B)∨（A∧C)（∧∨分配律） ⑶、性质：A→（B∧C）|－| (A→B)∧（A→C) ⑷、性质：A→（B∨C）|－| (A→B)∨（A→C) ⑸、性质：（A→B）∧C|－| (A→C)∨（B→C) ⑹、性质：（A→B）∨C|－| (A→C)∧（B→C)
5、定理（?定理群；定理2.6.11）
⑴、★★★★性质：A?B|－|A→B，B→A（严格证明） ⑵、性质：A?B|－| B?A（?交换律） ⑶、性质：A?B|－|? A??B ⑷、★★性质：?（A?B）|－| A??B ⑸、★★性质：?（A?B）|－| ?A?B ⑹、性质：A?B|－|（A∨?B）∧（?A∨B） ⑺、性质：A?B|－|（A∧B）∨（?A∧?B） ⑻、性质：（A?B）?C|－|A?( B?A)（?结合律） ⑼、性质：A?B；B?C├A?C ⑽、性质：A??A├B
⑾、性质：?├ （A?B）∨?（A??B）
六、定理群 1、 定理：
⑴、A1，…，An├A，当且仅当?├A1∧…∧An→A
⑵、A1，…，An├A，当且仅当?├A1→（…→（An→A）…） 2、★★引理：如果A|－|A’并且B|－|B’，则有?A|－|?A’等5条性质
3、★★★★等值替换定理：如果B|－|C并且在A中把B的某些出现替换为C而得到A’，则A|－|A’
4、★★对偶性定理：A’|－|?A（其中A’是A的对偶）
第七节 析取范式和合取范式
一、基本概念
1、 概念：单式（原子公式或者原子公司的否定式） 2、 概念：子式、析取子式、合取子式 3、 概念：析取范式、合取范式
二、定理
1、 定理：任何A∈Form（LP）逻辑等值于某一析取范式 2、 定理：任何A∈Form（LP）逻辑等值于某一合取范式
三、基本概念
1、 概念：公式A的析取范式（合取范式）
2、 概念：互补公式（一个公式和它的否定式，称为互补公式）
3、 定理：一个析取范式是矛盾式，当且仅当它的每个合取子式含互补的单式 一个合取范式是重言式，当且仅当它的每个析取子式含互补的单式
4、 定理：一个公式是矛盾式，当且仅当它的析取范式的每个合取子式含互补的单式
一个公式是矛盾式，当且仅当它的析取范式的每个合取子式含互补的单式
5、 概念：完全析取范式、完全合取范式
四、由公式导出它的析取范式（合取范式）的方法
1、 利用逻辑等值关系消去→、?等符号（等值替换定理） 2、 利用逻辑等值关系进行化简
第八节 联结符号的完备集
一、基本概念
1、 概念：fA1…An（n元联结符号f，联结公式A1…An所构成的公式） 2、 性质：对于任何的n?1，有2∧（2∧n）个不同的n元联结符号
二、基本概念
1、 概念：完备集（联结符号集称为完备的，当且仅当所有的n元联结符号都能由其中的联结符号定义） 2、 定理：{?，∧，∨}是联结符号的完备集 3、 推论：{?，∧}、{?，∨}、{?，→}是联结符号的完备集 4、 概念：↑称为与非式，即p↑q |=| ?（p∧q） 5、 概念：↓称为或非式，即p↓q |=| ?（p∨q） 6、 定理：{↑}，{↓}是联结符号的完备集
第三章 经典一阶逻辑
第一节 量词
一、基本概念
1、 概念：结构（论域＋个体＋关系＋函数）
2、 ★★概念：变元（以论域为变化范围的变元，用来构成关于个体的一般性命题或条件）
二、基本概念
1、 概念：全称量词和存在量词（对于所有（论域中的）个体：存在（论域中的）个体） 2、 概念：全称命题和存在命题（对于所有x，都有R（x）：存在x，使得R（x））
三、基本概念
1、 概念：命题函数（它不是命题，只有将某一个体指派为x的值时，它才成为命题） 2、 概念：自由变元、约束变元（命题函数中的变元、被量化的变元） 3、 归纳：量词的作用（将n元命题函数逐步转换为命题）
四、基本概念
1、 性质：论域D是有限集，可以将全称量词和存在量词，分别解释为合取和析取的推广 2、 概念：受限制的量词（范围受到限制的量词：范围由原来的论域，限制为论域的某个子集）
3、 性质：将受限制的量词，转换成为不受限制的量词（受限制的全称量词：全称量词＋蕴涵、受限制的存在量词：存在量词＋合取）
4、 概念：一阶逻辑和高阶逻辑（个体变元和个体量词/集的变元和量词）