集合论与图论：第2讲 一阶逻辑基础

1、2022-6-3集合论与图论第2讲1第2讲 一阶逻辑基础内容提要 1. 量词、谓词、个体词、命题符号化 2. 合式公式、解释、永真式 3. 一阶逻辑等值式 4. 一阶逻辑推理规则2022-6-3集合论与图论第2讲2一阶逻辑的字母表个体常项: a, b, c, , a1, b1, c1,个体变项: x, y, z, , x1, y1, z1,函数符号: f, g, h, , f1, g1, h1,谓词符号: F, G, H, , F1, G1, H1, 量词符号: , 联结词符号: , , , , 括号与逗号: (, ), ，2022-6-3集合论与图论第2讲3谓词(predicate)谓词：表

2、示性质、关系等；相当于句子中的谓语。用大写英文字母F,G,H,后跟括号与变元来表示。例如：F(x): x是人。G(x,y): x与y是兄弟。 n元谓词：含有n个变元。例如： F(x)是一元谓词， G(x,y)是二元谓词2022-6-3集合论与图论第2讲4量词(quantifier)全称(universal)量词: “所有的”, “全部的”,存在(existential)量词: “有一些的”, “某些的”,唯一(unique)存在量词: ! “恰好存在一个”2022-6-3集合论与图论第2讲5量词(举例)设：F(x)：x是自然数。G(x)：x是偶数。 H(x) ： x是奇数。 I(x,y)：x=

3、y。“有些自然数是偶数”。 x(F(x)G(x)“既有奇数又有偶数” 。xH(x)yG(y)存在既奇又偶的数” 。x(H(x)G(x)“存在唯一的自然数0”。 !x(F(x)I(x,0)2022-6-3集合论与图论第2讲6个体常项(constant)表示具体的特定对象用小写英文字母a,b,c,来表示例如： a:王大明，b:王小明， G(x,y): x与y是兄弟, “王大明与王小明是兄弟”: G(a,b)2022-6-3集合论与图论第2讲7个体变项(varible)表示不确定的泛指对象用小写英文字母x,y,z,来表示例如： F(x): x是人。G(x): x是数。 “存在着人”: xF(x) “

4、仅有一人”: !xF(x) “万物皆数”: xG(x) 2022-6-3集合论与图论第2讲8合式公式（举例） x(F(x)y(G(y)H(x,y) F(f(a,a),b)约定：省略多余括号最外层优先级递减： , ; ; ,; ,2022-6-3集合论与图论第2讲9命题符号化个体域(scope): 个体词的取值范围, 缺省(default)采用全总个体域. 全总个体域: 世界上的万事万物特性谓词: 表示所关注的对象的性质两种模式: x(M(x)G(x) x(M(x)G(x) 其中M(x)是特性谓词。2022-6-3集合论与图论第2讲10命题符号化(举例)例: “有些人是要死的”.解1: 采用全总

5、个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: x(F(x)G(x)解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: xG(x)2022-6-3集合论与图论第2讲11命题符号化(举例、续)例: “凡人都是要死的”.解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: x(F(x)G(x)解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: xG(x)2022-6-3集合论与图论第2讲12命题符号化(举例、续)例: “存在最小的自然数”。 解1: 设: F(x):

6、 x是自然数; G(x,y): xy; 原命题符号化成: x(F(x)y(F(y)G(x,y) 解2: 采用全体自然数作为个体域. 设: G(x,y): xy; 原命题符号化成: xyG(x,y)注意量词顺序: yxG(x,y): “没有最小的自然数”.2022-6-3集合论与图论第2讲13命题符号化(举例、续)例: “不存在最大的自然数”。 解: 设: F(x): x是自然数; G(x,y): xy 原公式解释成: “3-35”。2022-6-3集合论与图论第2讲25一阶逻辑永真式(tautology)永真式:在各种解释下取值均为真(逻辑有效式)命题逻辑永真式: 在各种赋值下取值均为真(重言

7、式)永假式:在各种解释下取值均为假(矛盾式)命题逻辑永假式: 在各种赋值下取值均为真(矛盾式)可满足式：非永假式2022-6-3集合论与图论第2讲26一阶逻辑等值式(定义)等值： AB 读作：A等值于B含义：A与B在各种解释下取值均相等AB 当且仅当 AB是永真式例如： xF(x)xF(x)F F2022-6-3集合论与图论第2讲27一阶逻辑等值式(来源)命题逻辑等值式的代换实例与量词有关的有限个体域量词消去量词否定量词辖域收缩与扩张量词分配与变项命名有关的换名规则代替规则2022-6-3集合论与图论第2讲28代换实例在命题逻辑等值式中, 代入一阶逻辑公式所得到的式子, 称为原来公式的代换实例

8、. 例1：AA, 令A=xF(x), 得到xF(x)xF(x)例2：ABAB, 令A=F(x), B=G(y), 得到F(x)G(y)F(x)G(y)2022-6-3集合论与图论第2讲29有限个体域上消去量词设个体域为有限集D=a1, a2, an, 则xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)例: 个体域D=a,b,c, 则 xyF(x,y) x (F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c) (F(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,c)2022-6-3集合论与图论第2讲30量词否定等值式

9、xA(x)xA(x) xA(x)xA(x)2022-6-3集合论与图论第2讲31量词否定等值式(举例) N n ( nN |an-a|N |an-a|N |an-a|N |an-a|N |an-a|N |an-a|N |an-a|N |an-a| )aannlimaannlim2022-6-3集合论与图论第2讲33量词辖域收缩与扩张()x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x) BxA(x)说明: B中不含x的出现例1: x(F(x)G(y) xF(x)G(y)例2: xy(F(x)G(y) x(F(x)yG(y) xF(x)yG(

10、y)2022-6-3集合论与图论第2讲34量词辖域收缩与扩张(、续) x(A(x)B) xA(x)B 证明: x(A(x)B) x(A(x)B) xA(x)B xA(x)B xA(x)B x(BA(x) BxA(x) 证明: x(BA(x) x(BA(x) BxA(x) BxA(x) BxA(x)2022-6-3集合论与图论第2讲35量词辖域收缩与扩张()x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x) BxA(x)说明: B中不含x的出现例1: x(F(x)G(y) xF(x)G(y)例2: xy(F(x)G(y) x(F(x)yG(y

11、) xF(x)yG(y)2022-6-3集合论与图论第2讲36量词辖域收缩与扩张(、续) x(A(x)B) xA(x)B 证明: x(A(x)B) x(A(x)B) xA(x)B xA(x)B xA(x)B x(BA(x) BxA(x) 证明: x(BA(x) x(BA(x) BxA(x) BxA(x) BxA(x)2022-6-3集合论与图论第2讲37量词分配x(A(x)B(x) xA(x)xB(x)x(A(x)B(x) xA(x)xB(x)2022-6-3集合论与图论第2讲38量词分配(反例)x(A(x)B(x) xA(x)xB(x)x(A(x)B(x) xA(x)xB(x) 个体域为全体

12、自然数; A(x): x是偶数 B(x): x是奇数; 左1, 右0 x(A(x)B(x) xA(x)xB(x)x(A(x)B(x) xA(x)xB(x) 个体域为全体自然数; A(x): x是偶数 B(x): x是奇数; 左0, 右1 2022-6-3集合论与图论第2讲39一阶逻辑推理定律(定义)推出： AB 读作：A推出B含义：A为真时, B也为真AB 当且仅当 AB是永真式例如： xF(x) xF(x)F2022-6-3集合论与图论第2讲40一阶逻辑推理定律(来源)命题逻辑推理定律的代换实例基本等值式生成的推理定律其他的一阶逻辑推理定律 xA(x)xB(x) x(A(x)B(x) x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) 2022-6-3集合论与图论第2讲41一阶逻辑推理定律(举例)命题逻辑推理定律的代换实例 例如: 假言推理规则: (AB )AB 代入 A=F(a), B=G(a), 得到(F(a)G(a)F(a)G(a)2022-6-3集合论与图论第2讲42一阶逻辑推理定律(举例、续)基本等值式生成的推理定律 即由 AB 可得 AB 和 BA 例如: 量词分配等值式: x(A(x)B(x) xA(x)xB(x) 可得 x(A(x)B(x) xA(x)xB(x) xA(x)xB