谓词
个体:命题中所涉及的对象。
谓词: 刻画个体的性质或若干个体间关系的模式。 一般用大写字母P, Q, R, … 表示。
例子:
张明生于背景。
Q(x, y): x生于y; c:张明, d:北京, 则有Q(c, d)
个体变元:讨论对象未确定, 泛指的个体, 如x, y。
个体常元:讨论对象已确定,特定的个体,如c,d。
个体域:n元谓词P(x1, x2, … , xn)中个体变元的取值范围叫做论述域或个体域。可有限也可无限。
Note:
- 一元谓词刻画性质,多元谓词刻画关系。
- 多元谓词中注意个体变元的次序。
- 命题可以认为是0元谓词,所以谓词是命题的扩充,命题是谓词的一种特殊情况。
简单命题函数(简单谓词命名式):由一个谓词,一些个体变元组成的表达式
复合命题函数(复合谓词命名式):由一个或n个简单命题函数以及逻辑联结词组成的表达式
逻辑连接词就是命题联结词
量词
- 全称量词:$\forall$
- 存在量词:$\exists$
在谓词前面加上全称量词或存在量词,说成是变元x被全称量化或存在量化。量化用来约束变元。
使$P(x_1, x_2, …, x_n)$成为命题的两种方法:
- 所有个体变元指定确定的个体
- 将所有个体变元量化
例子: P(x)表示“x是质数”, x是自然数。
$\forall x, P(x)$和$\exists x, P(x)$是命题
P(x): x是质数; a:3, 则有P(a)为命题。
全总个体域:将谓词中各个体变元的所有个体域统一起来,称为全总个体域。
特性谓词:(全总个体域中)限定个体变化范围的谓词。
特性谓词加入断言的规则:
- 全称量词,特性谓词作为蕴含式的前件加入
- 存在量词,特性谓词作为合取项加入
谓词演算公式与翻译
谓词演算公式
谓词演算的原子公式:不出现命题联结词和量词的谓词命名式$P(x_1,x_2,… ,x_n)$
谓词演算的合式公式:
- 谓词演算的原子公式是谓词演算公式;
- 若A,B是谓词演算公式,则$(\lnot A),(A \land B),(A \lor B), (A→B),(A \leftrightarrow B),\forall x \quad A,\exists x \quad A$是谓词演算公式
- 只有有限次应用上述步骤构成的公式才是谓词演算公式
翻译
\[\lnot \forall x (R(x) \rightarrow Q(x))\]并非每个实数都是有理数。 (R, Q)
\[\forall x (M(x) \rightarrow \exists y (G(y) \land F(x, y)))\]每个人都有些缺点。(M, G, F)
思考:怎么理解?
论述域是人和缺点, M(x)表示“x是人”, G(y)表示“y是缺点”, F(x, y)表示“x有y”。
\[\exists x (M(x) \land F(x)) \land \lnot \forall x(M(x) \rightarrow F(x))\]尽管有人聪明, 但未必所有人都聪明。(M, F)
论述域是人, M(x)表示“x是人”, F(x)表示“x聪明”。
自由变元与约束变元
辖域:紧接于量词之后最小的子公式叫量词的辖域
例子:
\[\forall x \underline {P(x)} \rightarrow Q(x)\] \[\exists x \underline {(P(x, y) \land Q(x, y))} \rightarrow F(x)\]注意:辖域若不是原子公式,两边要有括号; 否则, 不应有括号。
约束变元:在量词$\forall x ,\exists x$的辖域内变元x的一切出现称为约束出现
自由变元:在一公式中,变元的非约束出现称为变元的自由出现
谓词演算
谓词演算的基本概念
定义1:两个任意谓词公式A和B,E是它们公有的论述域,若:
- 对公式A和B中的谓词变元(包括命题变元),指派以任一在E上有意义的确定的谓词。
- 对谓词命名式中的个体变元,指派以E中的任一确定的个体。
所得的命题具有同样的真值,则称公式A和B遍及E等价,记为在E上$A \Leftrightarrow B$
思考:谓词变元和命题变元有什么区别?
回答:
首先什么是命题, 具有确定真值的陈述句。什么是命题变元, 一个命题标识符表示任意的命题。
其次什么是谓词,刻画个体的性质或若干个体间关系的模式。什么是谓词变元,谓词变元指的是数理逻辑中表示某一范围内的任意谓词。
定义2:如果两谓词公式A和B,在任意论述域上都等价,则称A和B等价,记为$A \Leftrightarrow B$
定义3:给定任一谓词公式A,如果在论述域E上,对公式A中的谓词和个体变元进行定义1中的两种指派,所得命题:
- 都真,则称A在E上有效或在E上永真。
- 至少有一个是真,则称A在E上可满足。
- 都假,则称A在E上永假或在E上不可满足。
定义4:给定任一谓词公式A,如果在任意论述域上,对公式A中的谓词和个体变元进行定义1中的两种指派,所得命题:
- 都真,则称A有效或永真。
- 至少有一个是真,则称A可满足。
- 都假,则称A永假或不可满足。
定义5:设A、B是谓词公式,E是它们共同的个体域,如果A→B在E上永真,则称在E上A蕴含B,记作在E上$A \Rightarrow B$。
定义6:如果两谓词A和B,在任意论述域上A都蕴含B,则称A蕴含B,记为$A \Rightarrow B$。
思考:谓词和谓词公式有什么区别?
回答:
谓词:刻画个体的性质或若干个体间关系的模式。
谓词公式:
- 单个谓词是谓词公式,称为原子谓词公式
- 若A是谓词公式,则¬A $\lnot$ A¬A也是谓词公式
- 若A,B都是谓词公式,则A∧B,A∨B,A→BA $\land$ B, A $\lor$ B, A $\to$ BA∧B,A∨B,A→B也都是谓词公式
- 若A是谓词公式,则(∀X)A,(∃X)A($\forall$ X)A,($\exists$ X)A(∀X)A,(∃X)A也都是谓词公式
- 有限步应用1~4步所得到的公式也是谓词公式
判断谓词公式永真-真值表方法
例子:
P(x)仅可解释为: a. A(x): x是质数。 b. B(x):x是合数。 论述域是{3, 4}, 判定谓词公式$P(x) \land \exists x P(x)$是否永真。
P(x) | x | $P(x) \land \exists x P(x)$ |
---|---|---|
A(X) | 3 | $1 \land 1 \Leftrightarrow 1$ |
A(X) | 4 | $0 \land 1 \Leftrightarrow 0$ |
B(X) | 3 | $0 \land 1 \Leftrightarrow 0$ |
B(X) | 4 | $1 \land 1 \Leftrightarrow 1$ |
谓词演算的基本永真公式
命题演算的永真公式也是谓词演算的永真公式。
谓词演算是命题演算的扩充
思考:这里的例子不明白。
回答:
利用公式
\[P \rightarrow Q \Leftrightarrow \lnot P \lor Q\]推导
量词的添加与消去
如果A是不含约束变元x的公式,则
\[\forall x A \Leftrightarrow A \quad \exists x A \Leftrightarrow A\]思考:这里的例子也不明白。
量词的否定
否定联结词可以通过量词深入到辖域,反之亦可。
\[\lnot \forall x P(x) \Leftrightarrow \exists \lnot P(x)\] \[\lnot \exists x P(x) \Leftrightarrow \forall \lnot P(x)\]否定的深入:
\[\lnot \forall x \forall y \exists z (x + z = y) \\ \Leftrightarrow \exists x \lnot \forall y \exists z (x + z = y) \\ \Leftrightarrow \exists x \exists y \lnot \exists z (x + z = y) \\ \Leftrightarrow \exists x \exists y \forall z \lnot (x + z = y) \\ \Leftrightarrow \exists x \exists y \forall z (x + z \neq y)\]量词辖域的扩张和收缩
\[\forall x (A(x) \lor B) \Leftrightarrow \forall x A(x) \lor B \\ \forall x (A(x) \land B) \Leftrightarrow \forall x A(x) \land B \\ \exists x (A(x) \lor B) \Leftrightarrow \exists x A(x) \lor B \\ \exists x (A(x) \land B) \Leftrightarrow \exists x A(x) \land B\]这里B是不含约束变元x的谓词(包括命题),所以它属于或不属于量词的辖域均有同等意义。
量词的分配形式
\[\forall x (A(x) \land B(x)) \Leftrightarrow \forall x A(x) \land \forall x B(x) \\ \exists x (A(x) \lor B(x)) \Leftrightarrow \exists x A(x) \lor \exists x B(x) \\ \exists x (A(x) \land B(x)) \Rightarrow \exists x A(x) \land \exists x B(x) \\ \forall x A(x) \lor \forall x B(x) \Rightarrow \forall x (A(x) \lor B(x))\]量词对条件和双条件的处理
利用公式
\[P \rightarrow Q \Leftrightarrow \lnot P \lor Q\]以及CP规则进行推导
思考: 怎么理解这个公式?
回答: 列出真值表:
$P$ | $Q$ | $P \rightarrow Q$ | $\lnot P \lor Q$ |
---|---|---|---|
1 | 1 | 1 | 1 |
0 | 0 | 1 | 1 |
1 | 0 | 0 | 0 |
0 | 1 | 1 | 1 |
思考:什么是CP规则?
回答:
前提是H1,H2,…,Hn,欲证结论R→P(结论是条件式),则将条件式作为附加前提证得P即可,这就是CP规则。
设H=H1∧H2∧…∧Hn,由前提H证明R→P,即证明H→(R→P)永真,而H→(R→P)等价于H∧R→P,因此证明H∧R→P永真即可。
\[\forall x (A(x) \rightarrow B(x)) \Rightarrow \forall A(x) \rightarrow \forall B(x) \\ \exists x (A(x) \rightarrow B(x)) \Leftrightarrow \exists x A(x) \rightarrow x B(x) \\ \exists x A(x) \rightarrow \forall x B(x) \Rightarrow \forall x (A(x) \rightarrow B(x)) \\ \forall x(A(x) \leftrightarrow B(x)) \Rightarrow \forall x A(x) \leftrightarrow \forall x B(x)\]谓词演算的推理规则
命题演算中所有推理规则在谓词演算中都适用
谓词演算中所有永真蕴含式和等价式也可使用
思考:什么是永真蕴含式?
回答:
首先什么是蕴含式。
设p、q为两个命题。复合命题”如果p,则q”称为p与q的蕴含式,记作p→q。并称p为蕴含式的前件,q为后件。并规定p→q为假当且仅当p为真q为假。
所以永真蕴含式就是永真的蕴含式
全称指定规则(Universal Specification,US )
\[\frac{\forall x P(x)}{\therefore P(c)}\]P是谓词, c是论述域中任意个体。 意义是, 全程量词可以删除。
存在指定规则(Existential Specification,ES )
\[\frac{\exists x P(x)}{\therefore P(c)}\]P是谓词, c是论述域中某些个体, 不是任意的。
全称推广规则(Universal Generalization,UG)
\[\frac{P(x)}{\therefore \forall x P(x)}\]如果能够证明对于论述域中每一个个体x使P(x)都成立, 则可以得到上面结论。
存在推广规则(Existential Generalization,EG)
\[\frac{P(c)}{\therefore \exists x P(x)}\]p是谓词, c是论述域中一个个体。意义是, 对论述域中某些个体使P(x)为真, 则可得上面结论。