下载文档原格式
1一阶逻辑的推理演算这一讲我们学习一阶逻辑的自然推理系统。
其功能是由若干前提12,,,n A A A 推导出一条结论B 。
这相当于证明下列蕴含式是永真的： 12n A A A B ∧∧∧→1. 一阶逻辑的代入定理 将永真命题公式中的各命题变元代换为任何一阶公式后，所得的一阶公式是永真的。
例如，()p q p q →∧→是永真命题公式。
进行一阶公式代入p=F (x )，q=G (x )后得如下永真一阶公式：(()())()()F x G x F x G x →∧→定理1.1（代入定理）任何永真命题公式在代入一阶公式后是永真一阶公式。
证明 略。
证毕2. 永真蕴含式和推理定律永真蕴含式：若A →B 是永真式，则记为A B ⇒，称为永真蕴含式。
将永真命题蕴含式中的变元视为取值为任何一阶公式的变元，则该永真命题蕴含式就变成一条推理定律。
根据代入定理，推理定律表示一批形式相似的永真蕴含式。
因此，推理定律是描述永真蕴含式的模式。
由任何永真蕴含式可以得到对应的推理定律。
例如，由永真蕴含式()p q p q →∧⇒可得一阶逻辑的假言推理定律()A B A B →∧⇒，其中变元A ，B 表示任何一阶公式。
这条推理定律的含义是，对于任何一阶公式A 和B ，若(A →B )为真并且A 为真，则B 为真。
因此，由前提(A →B )与A 可得结论B 。
这是我们思维中最常用的一条推理规则，称为假言推理规则或者分离规则。
因此，推理定律可以当作推理规则使用。
2再如，(())p q q p →∧⌝→是永真蕴含式，由此可得推理定律(())A B B A →∧⌝⇒，称为拒取式。
命题逻辑的自然推理系统P 中的所有9条推理定律都可以当作一阶逻辑推理定律来使用。
3. 量词消去与引入规则与命题逻辑的自然推理系统相比，这是一阶逻辑自然推理系统所特有的推理规则。
见课本第75页。
这是课程中的一个难点，我们可以借助于语义来理解其正确性。
1） 全称量词消去规则（简记为∀-）（1）第一个竖式得出的结论是一个句型。
1一阶逻辑语言重点：一阶逻辑语言的构成及其解释。
引入：（1）命题逻辑的局限性举例。
（2）一阶逻辑的特点：指出命题的两个组成部分，即主语（subject ）和谓语（predicate ），并且讨论两种量词“所有”与“存在”。
1. 预备知识为了介绍一阶逻辑语言及其解释，我们需要引入若干预备知识。
1） 集合对象：客观存在的事物与主观存在的观念是我们思考和语言表达的对象，称为认知对象（cognitive object ），简称对象（object ）。
集合：集合是一些对象的全体，其中各对象称为该集合的元素。
例如，所有整数的全体称为整数集合。
若A 是集合，x 是A 的元素，则记为x A ∈。
然而，并非任何对象的全体都能称为集合，例如，所有集合的全体不能再称为集合，否则会导致矛盾。
假如任何集合都不以自己为元素，则所有集合全体不包含自己，所以所有集合全体不是一个集合。
假如存在集合以自己为元素，则所有这样的集合全体不是一个集合。
事实上，若所有不以自己为元素的集合全体T 是集合，则T T T T ∈⇔∉这个矛盾称为罗素悖论（Russell ’s Paradox ）。
因此，并不是任何对象全体都是集合。
论域：一段论述所谈论的对象全体称为论域（universe 或者domain ），其中的对象称为个体（entity ），它们是该论述中语句主语和宾语的所指。
例如，下面论述的论域是所有整数。
所有大于2的偶数都能分解为两个素数之和。
2） 关系设D 是非空集合。
D 上的关系定义如下：一元关系：D 的子集A 称为D 上的一元关系（1-ary relation ）。
其功能是表示D中元素的性质。
若A 表示某性质，则x A ∈表示x 有该性质，而x A ∉表示x 没有该性质。
二元关系：D 2的子集称为D 上的二元关系（2-ary relation ）。
表示D 中个体之间某种关系。
注：2{(,)|,}D x y x y D =∈设R是D上的二元关系。
离散数学一阶逻辑笔记一、一阶逻辑基本概念。
（一）个体词。
1. 定义。
- 个体词是指所研究对象中可以独立存在的具体的或抽象的客体。
- 例如，在“小王是学生”中，“小王”就是个体词；在“3是有理数”中，“3”是个体词。
2. 分类。
- 个体常项：表示具体或特定的客体的个体词，常用a,b,c,·s表示。
“小李”可以用a表示。
- 个体变项：表示抽象或泛指的个体词，常用x,y,z,·s表示。
例如，“某个学生”可以用x表示。
（二）谓词。
1. 定义。
- 谓词是用来刻画个体词性质及个体词之间相互关系的词。
- 例如，在“小王是学生”中，“是学生”就是谓词，它刻画了“小王”的性质；在“3大于2”中，“大于”是谓词，它刻画了“3”和“2”之间的关系。
2. 分类。
- 谓词常项：表示具体性质或关系的谓词。
如“是偶数”是谓词常项。
- 谓词变项：表示抽象的、泛指的性质或关系的谓词。
- 一元谓词：与一个个体词相联系的谓词。
例如P(x)，其中P表示“是学生”，x是个体变项。
- 二元谓词：与两个个体词相联系的谓词。
例如Q(x,y)，其中Q表示“大于”，x,y是个体变项。
- n元谓词：与n个个体词相联系的谓词，一般表示为P(x_1,x_2,·s,x_n)。
（三）量词。
1. 全称量词。
- 符号表示为“∀”，表示“所有的”“任意一个”等。
- 例如，“所有的人都会呼吸”可以表示为∀ x(P(x)to Q(x))，其中P(x)表示“x是人”，Q(x)表示“x会呼吸”。
2. 存在量词。
- 符号表示为“∃”，表示“存在一个”“至少有一个”等。
- 例如，“存在一个数是偶数”可以表示为∃ x(P(x)，其中P(x)表示“x是数且x是偶数”。
二、一阶逻辑公式及其解释。
（一）一阶逻辑合式公式（谓词公式）1. 原子公式。
- 设P(x_1,x_2,·s,x_n)是n元谓词，t_1,t_2,·s,t_n是项，则P(t_1,t_2,·s,t_n)称为原子公式。
