本文及其系列文章用于离散数学（1）科目的期末考试复习

一些定义和名称

  • 个体词就是命题逻辑里面的主词。包括了个体常项和个体变项。将个体变化的范围成为个体域或者论域$D$。

  • 谓词指的是用来刻画对象性质和关系的符号，一般用大写字母$P,Q,R$表示，可以理解为语法上的谓语的作用。把在谓词的定义中涉及到的个体词的个数称为该谓词的元数。如$P(x,y)$表示$x=y$就是一个二元谓词；命题逻辑中的命题就是一个零元谓词。注意，谓词的值域是$\{T,F\}$

  • 函数指的是一些从$D$到$D$的映射。他们与谓词的区别在于值域。例如，$f(x)$表示“$x$的父亲”是一个函数，而$P(x)$表示“$x$是父亲”就是一个谓词。

  • 项是用于表示论语中对象的符号表达式。个体词和函数都是项。

  • 量词是对个体数量加以约束和限制的词。量词分为全称量词和存在量词。全称量词就是$\forall$，存在量词就是$\exists$，具体内涵就是我们高中就熟知的。量词的辖域指的就是某个量词所约束的范围。一般而言，我们可以认为如果量词后不加括号，那辖域就是后一个谓词符号；如果量词后有括号，那就是括号里的内容。

一些实例

在这里给出一些自然语言形式化变成一阶谓词逻辑的结果，便于理解。注意，这些结果中有些是特别需要注意的。

  1. 所有的有理数都是实数

    取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\forall x)(P(x)\rightarrow R(x))$

    注意，“所有的……都是……”这样类型的语句只能用$\rightarrow$

  2. 有的实数是有理数

    取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\exists x)(R(x)\land P(x))$

    注意，“有的……是……”这样类型的语句一般用$\land$

  3. 有的实数不是有理数

    取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\exists x)(R(x)\land \neg P(x))$

  4. 没有无理数是有理数

    取$P(x)$表示$x$是有理数，$Q(x)$表示$x$是无理数数。则原句可以形式化为$\neg(\exists x)(Q(x)\land P(x))$

  5. 至少有一个偶数是素数

    取$A(x)$表示$x$为偶数，$B(x)$表示$x$为素数。则原句可以形式化为$(\exists x)(A(x)\land B(x))$

  6. 至少有一个偶数并且至少有一个素数

    取$A(x)$表示$x$为偶数，$B(x)$表示$x$为素数。则原句可以形式化为$(\exists x)A(x)\land(\exists x) B(x)$

  7. 函数$f(x)$在$[a,b]$上的点$x_0$处连续

    根据微积分的知识，可以形式化为$(\forall \epsilon)(\epsilon >0\rightarrow (\exists \delta)(\delta>0\land (\forall x)(|x-x_0|<\delta\rightarrow|f(x)-f(x_0)|<\epsilon)))$

  8. 自然数集合的形式描述

    即，论域是自然数集，我们要形式化下列语句（自然数集合建立公理）：$\\(1)$对于每个数，有且仅有一个相继后元$\\(2)$没有一个数的相继后元是0 $\\(3)$ 对于除0以外的数，有且仅有一个相继前元。

    设谓词$P(x,y)$表示$x=y$，函数$f(x)=x+1$，函数$g(x)=x-1$。则原句可以形式化为：$\\(1)(\forall x)(\exists y)(P(y,f(x))\land(\forall z)(P(z,f(x))\rightarrow P(y,z)) )\\(2)\neg(\exists x)P(0,f(x))\\(3)(\forall x)(\neg P(0,x)\rightarrow (\exists y)(P(y,g(x))\land(\forall z)(P(z,g(x))\rightarrow P(y,z))))$

公式的分类

设$\varphi$是一个谓词公式

  • 如果$\varphi$在任何解释和任何赋值下均为真，那么称其为有效式

  • 如果至少存在一个解释个一个赋值使得$\varphi$为真，那么称其为可满足式

  • 如果$\varphi$在任何解释和任何赋值下均为假，那么称其为不可满足式(永假式)

有限域上的公式表示法

如果论域为有限域，那么这个时候谓词公式可以转化为我们熟悉的命题逻辑。

例如，如果论域为$D=\{1,2,3,……,k\}$,那么我们有：

$(\forall x)P(x)=P(1)\land P(2)\land……\land P(k)$

$(\exists x)P(x)=P(1)\lor P(2)\lor……\lor P(k)$

有时候，为了快速判断某些式子的性质，我们常常把这些式子放到有限域上，特别是$\{1,2\}$域上来做判断。以下是一些例子。

$(\forall x)(\forall y)P(x,y)=(\forall y)P(1,y)\land(\forall y)P(2,y)=P(1,1)\land P(1,2)\land P(2,1)\land P(2,2)$

$(\exists x)(\forall y)P(x,y)=(\forall y)P(1,y)\lor (\forall y)P(2,y)=(P(1,1)\land P(1,2))\lor(P(2,1)\land P(2,2))$

$(\forall y)(\exists x)P(x,y)=(\exists x)P(x,1)\land (\exists x)P(x,2)=(P(1,1)\lor P(2,1))\land(P(1,2)\lor P(2,2))$

$(\exists x)(\exists y)P(x,y)=(\exists y)P(1,y)\lor(\exists y)P(2,y)=P(1,1)\lor P(1,2)\lor P(2,1)\lor P(2,2)$