狭谓词逻辑的形式结构 普遍有效性和可满足性

命题逻辑中,简单命题作为基本单位,不再分析成主词、谓词和量词等
有些推理形式是命题逻辑所不能包括的,如:
凡循环小数都可以化为分数;
0.2是循环小数
所以0.2可以化为小数
就不是命题逻辑中正确的推理形式

狭谓词逻辑(一阶谓词逻辑):将量词只用于个体变项,而不用于谓词变项和命题变项的谓词逻辑

广义谓词逻辑:将量词也用于命题变项和谓词变项的谓词逻辑

谓词 变项和量词

谓词

通常将一命题里表示思维对象的词称为主词,将表示对象性质的词称为谓词

  • 例:2是有理数
    • “2” 是主词
    • “是有理数” 是谓词

数理逻辑中不用主词这个名词,而将代表个体的词称为个体词,将表示一个个体和两个或两个以上个体间的关系的词称为谓词

  • n个个体之间的关系称为n项关系
  • 表示n项关系的谓词称为n项谓词
    • 表示一个事物的性质的谓词则称为一项谓词
    • n项谓词有n个空位,也称n目谓词或n元谓词

变项

变项表示某类特定事物中的任一个;相对于某一变项的这类事物必须是确定的,具体哪个是不确定的

  • 变项的变程(domain):变项表示某类事物,此类事物就是~

  • 变项的值:变项的变程里的任一分子都可以作为变项的值;变项必须从它的变程中取值

变项的作用:

  • 作为同异的标志:相同的变项取相同值,标志相同的对象
  • 表示形式结构:反映一类命题的共同特征

量词

量词是命题里表示数量的词

  • 全称量词:一切、所有、凡 等
  • 存在量词:有的、有、至少有一 等

量词的符号表示

  • 全称量词

    • “凡事物都是变化发展的”
    • 对任一x而言,x是变化发展的
    • 用符号表示:
      • (x), (y), …
      • 所有x,所有y,…
      • (x)(x是变化发展的)
      • (y)(y是变化发展的)
    • “凡有理数都等于一分数”
    • 对任一x而言,如果x是有理数,那么x等于一分数
    • 用符号表示:
      • (x)(x是有理数 $\rightarrow$ x等于一分数)
  • 存在量词

    • “有的事物是新陈代谢的”
    • 至少有一x,x是新陈代谢的
    • 用符号表示:
      • $(exits x)$, $(exits y)$, …
      • 至少有一x,至少有一y,…
      • $(\exits x)$ (x是有新陈代谢的)
      • $(\exits y)$ (y是有新陈代谢的)
    • “有的自然数是素数”
    • 至少有一x,x是自然数并且x是素数
    • 用符号表示:
      • $(\exits x)$ (x是自然数 $\bigwedge$ x是素数)

自由变项和约束变项

自由变项:

  • x是有理数
    • 是一命题形式
    • 变项x的值未定
    • 既不真也不假
  • x > y

    • 是一个命题形式
    • 变项x和y的值未定
    • 既不真也不假

约束变项:被量词所约束化了的变项

  • (x)(x是发展变化的)
    • 是一个命题
    • 变项x不需要再作代入
    • 命题的涵义已经是确定的,是真命题
  • ($\exits x$)(x是偶数 $\bigwedge$ x > 2 $\bigwedge$ x是素数)

    • 假命题

约束变项不需要作代入:变项的变程确定以后,命题的意义是确定的

  • 约束变项是被量词所约束了的变项;量词内的变项也被此量词所约束,是约束变项
    • 例如:
    • (x)(x是发展变化的)
    • 两个x都是约束变项

狭谓词逻辑的命题形式和公式

谓词逻辑:命题 -> 个体词、谓词和量词等命题成分

狭谓词逻辑:全称量词和存在量词只被引用于个体变项而不被引用于命题变项或谓词变项

符号

  • (甲)命题变项: $p, q, r, s, p_1, q_1, r_1, s_1, p_2, q_2, …$
  • (乙)个体变项: $u, v, w, x, y, z, u_1, v_1, w_1, x_1, y_1, z_1, u_2, …$
  • (丙)谓词变项: $F, G, H, P, Q, R, S, F_1, G_1, …$
  • (丁)真值联结词: $¬, \bigvee, \bigwedge, \rightarrow, \leftrightarrow$
  • (戊)量词: $(…), (\exists…)$
  • (己)括号: $(, )$

个体变项的变程:个体域

单称命题形式:谓词逻辑最简单的命题形式

  • 其他命题形式都可以由单称命题形式和命题变项再加上联结词和量词组合而成

  • 不含量词的单称命题可以分析为二类因素

    • 一个或多个个体词
    • 一元谓词或多元谓词
      • x是F : F(x)
      • x和y有关系R : R(x, y)
      • x, y, z有关系S : S(x, y, z)

古典形式逻辑的A、E、I、O

全称肯定命题 S A P : 一切 S 都是 P

  • 对任一x而言,若x是S,则x是P
  • 符号表示: $(x)(S(x) \rightarrow P(x))$

全称否定命题 S E P : 没有 S 是 P

  • 对任一x而言,若x是S,则x不是P
  • 符号表示: $(x)(S(x) \rightarrow ¬P(x))$

  • 全称肯定和全称否定命题用全称量词和蕴涵表示

    • 形式蕴涵
    • 形式蕴涵对S的存在问题无所表示:既未断定有S也未断定无S
    • 若主词表示的事物是存在的,如 “凡人都能劳动”
      • $(\exists x) S(x) \bigwedge (x) (S(x) \rightarrow P(x))$

特称肯定命题 S I P : 有的 S 是 P

  • 有的x,它既是S又是P
  • 符号表示: $(\exists x)(S(x) \bigwedge P(x))$

特称否定命题 S O P : 有的 S 不是 P

  • 符号表示: $(\exists x)(S(x) \bigwedge ¬P(x))$

量化式的否定

量化式:表示全称或存在命题的公式

全称量化式的否定式

  • “并非一切都是必然的”
  • $¬(x)(x是必然的)$
  • $¬(x)F(x)$

存在量化式的否定式

  • “不存在着孤立的事物”
  • $¬(\exists x)(x是孤立的)$
  • $¬(\exists x)F(x)$

否定式的全称量化式

  • “一切事物都不是静止的”
  • $(x)¬(x是静止的)$
  • $(x)¬F(x)$

否定式的存在量化式

  • “有的事物不是生物”
  • $(\exists x)¬(x是生物)$
  • $(\exists x)¬F(x)$

¬(x)F(x) 和 $(\exists x)¬F(x)$ 的涵义是相等的
$¬(\exists x)F(x)$ 和 (x)¬F(x) 的涵义也是相等的

量化式的联结

  • “至少有一偶数是素数”
    • $(\exists x)(F(x) \bigwedge G(x))$
  • “至少有一偶数,并且至少有一素数”
    • $(\exists x)F(x) \bigwedge (\exists x)G(x)$
  • 量词约束的范围不同,两个命题形式的涵义不同

  • “一切事物,它或者是生物或者是非生物”

    • $(x)(F(x) \bigvee G(x))$
  • “或者一切都是生物,或者一切都是非生物”
    • $(x)F(x) \bigvee (x)G(x)$
  • $(x)(F(x) \rightarrow G(x))$

  • $(x)F(x) \rightarrow (x)G(x)$

重迭量词

  • 一元谓词只能引用一次量词
    • $(x)P(x)$ : 凡x都是P
    • $(\exists x)P(x)$ : 有x是P
  • n元谓词可以n次引用量词,得到2n!种形式

重迭量词:有先后次序的量词序列

辖域

量词的辖域是量词所约束的范围

  • 量词的辖域里一切和量词里的变项相同的变项都被此量词所约束
  • 量词后有括号:括号内为此量词的辖域
  • 量词后无括号:量词后最短的公式为此量词的辖域

例:

  • $(x)R(x, y)$
    • $R(x, y)$ 是 $(x)$ 的辖域
  • $(\exists x)(y)R(x, y)$

    • $(y)R(x, y)$ 是 $(\exists x)$ 的辖域
    • $R(x, y)$ 是 $(y)$ 的辖域
  • $(x)(P(x) \rightarrow (\exists y)(R(x, y) \bigwedge Q(y)))$

    • $P(x) \rightarrow (\exists y)(R(x, y) \bigwedge Q(y))$ 是 $(x)$ 的辖域
    • $R(x, y) \bigwedge Q(y)$ 是 $(\exists y)$ 的辖域

全称式:最前方为一全称量词,且此量词的辖域延伸至公式的末端的公式

存在式:最前方为一存在量词,且此量词的辖域延伸至公式的末端的公式

推理形式

  1. 古典形式逻辑三段论第一格的Barbara
1
2
3
4
所有M都是P,
所有S都是M,
----------
所有S都是P
  • 用谓词逻辑符号表示为

$(x)(M(x) \rightarrow P(x))$

$(x)(S(x) \rightarrow M(x))$

$(x)(S(x) \rightarrow P(x))$

  • 写成蕴涵式为

$(x)(M(x) \rightarrow P(x)) \bigwedge (x)(S(x) \rightarrow M(x)) \rightarrow (x)(S(x) \rightarrow P(x))$

  1. 古典形式逻辑全称否定命题的换位
1
2
3
没有S是P
--------
没有P是S
  • 谓词逻辑中表达为

$(x)(S(x) \rightarrow ¬P(x))$

$(x)(P(x) \rightarrow ¬S(x))$

  • 写成蕴涵式

$(x)(S(x) \rightarrow ¬P(x)) \rightarrow (x)(P(x) \rightarrow ¬S(x))$

  1. 关于重叠量词的推理形式
  • “有的液体可以溶解一切固体”
    • 用符号表示
    • $(\exists y)(液体(y) \bigwedge (x)(固体(x) \rightarrow y溶解x))$
    • 形式
    • $(\exists y)(Q(y) \bigwedge (x)(P(x) \rightarrow R(x, y)))$
  • 可以推论
  • “一切固体都可以被某些液体所溶解”
    • 符号表示
    • $(x)(固体(x) \rightarrow (\exists y)(液体(y) \bigwedge y溶解x))$
    • 形式
    • $(x)(P(x) \rightarrow (\exists y)(Q(y) \bigwedge R(x, y)))$
  • 但后者不能推论前者

推理形式相当于蕴含式

$(\exists y)(Q(y) \bigwedge (x)(P(x) \rightarrow R(x, y))) \rightarrow (x)(P(x) \rightarrow (\exists y)(Q(y) \bigwedge R(x, y)))$

  1. 有关量词分配的推理形式
  • 至少有一x,x既是F又是G
  • 可以推论
  • 至少有一x是F,并且至少有一x是G
  • 但从后者不能推论前者

推理形式相当于蕴涵式

$(\exists x)(F(x) \bigwedge G(x)) \rightarrow (\exists x)F(x) \bigwedge (\exists x)G(x)$

  • 一切x,或者x是F,或者x是G
  • 不能推论得
  • 或者一切x是F,或者一切x是G
  • 但从后者可以推论前者

推理形式相当于蕴涵式

$(x)F(x) \bigvee (x)G(x) \rightarrow (x)(F(x) \bigvee G(x))$

普遍有效性和可满足性

  • 狭谓词逻辑里的公式分为三类

    • 普遍有效的
    • 可满足的但不普遍有效
    • 不可满足的

普遍有效:狭谓词逻辑的一个公式是普遍有效的,当且仅当用任一特定的命题代入其中的命题变项,用任一特定的个体变项代入其中的个体变项,用任一特定的谓词代入其中的谓词变项,其结果总是真的

可满足:狭谓词逻辑的一个公式是可满足的,当且仅当至少有一特定命题,一特定个体词和一特定谓词,代入公式的相应变项以后结果是真的

普遍有效性的判定

  • 命题逻辑的公理和定理都是重言式,是常真的

  • 狭谓词逻辑的公理和定理是常真的,是普遍有效的公式

  • 命题逻辑是狭谓词逻辑的一部分,重言式都是普遍有效的

  • 重言式

    • 有一能行的真值表方法判定一公式是不是重言式
    • 能行的方法:每一步按事先给出的规则明确规定了的并且在有穷步内能完成的方法
  • 普遍有效式

    • 除了重言式和某些情况外一般没有一个能行的方法判定一公式是不是普遍有效

有穷个体域内的判定问题

  • 宇宙间的个体数无穷

  • 有穷个体域的情况下狭谓词逻辑的公式可以转换成命题逻辑的公式,普遍有效性的问题可以归约为重言式的判定问题

  • 数理逻辑中,

    • 用自然数1, 2, 3 …等 代表个体
    • 用 {1, 2, 3, …} 表示一无穷个体域
    • 用 {1, 2, 3, …, k} 表示一有k个个体的有穷个体域

转换方法

  • 全称式 $(x)F(x)$ 表示 一切x都是F
    • 在个体域中,1是F,2是F,…,k是F
    • $(x)F(x) = F(1) \bigwedge F(2) \bigwedge … \bigwedge F(k)$
    • 全称式是一个合取
  • 存在式 $(\exists x)F(x)$ 表示 至少有一x是F

    • 在个体域里,或者1是F,或者2是F,…,或者k是F
    • $(\exists x)F(x) = F(1) \bigvee F(2) \bigvee … \bigvee F(k)$
    • 存在式是一个析取
  • 以上转换只有在个体域有穷时才能进行

    • 无穷合取和无穷析取都不是命题逻辑的合式公式
  • 含有自由个体变项的公式 F(x)

    • x 可以取 {1, 2, …, k} 中任一个体为值,F(x)可以转换为F(1),也可以转换为F(2),…,也可以转换为F(k)
    • 谓词逻辑的公式就转换为一个或一系列命题逻辑的公式

引用

  1. 《数理逻辑引论》,王宪钧,北京大学出版社