文章同步于@c.w.-知乎，个人博客
本文及其系列文章用于离散数学（1）科目的期末考试复习
一些定义和名称
-
个体词就是命题逻辑里面的主词。包括了个体常项和个体变项。将个体变化的范围成为个体域或者论域\(D\)。
-
谓词指的是用来刻画对象性质和关系的符号，一般用大写字母\(P,Q,R\)表示，可以理解为语法上的谓语的作用。把在谓词的定义中涉及到的个体词的个数称为该谓词的元数。如\(P(x,y)\)表示\(x=y\)就是一个二元谓词；命题逻辑中的命题就是一个零元谓词。注意，谓词的值域是\(\{T,F\}\)
-
函数指的是一些从\(D\)到\(D\)的映射。他们与谓词的区别在于值域。例如，\(f(x)\)表示“\(x\)的父亲”是一个函数，而\(P(x)\)表示“\(x\)是父亲”就是一个谓词。
-
项是用于表示论语中对象的符号表达式。个体词和函数都是项。
-
量词是对个体数量加以约束和限制的词。量词分为全称量词和存在量词。全称量词就是\(\forall\)，存在量词就是\(\exist\)，具体内涵就是我们高中就熟知的。量词的辖域指的就是某个量词所约束的范围。一般而言，我们可以认为如果量词后不加括号，那辖域就是后一个谓词符号；如果量词后有括号，那就是括号里的内容。
一些实例
在这里给出一些自然语言形式化变成一阶谓词逻辑的结果，便于理解。注意，这些结果中有些是特别需要注意的。
-
所有的有理数都是实数
取\(P(x)\)表示\(x\)是有理数，\(R(x)\)表示\(x\)是实数。则原句可以形式化为\((\forall x)(P(x)\rightarrow R(x))\)
注意，“所有的……都是……”这样类型的语句只能用\(\rightarrow\)
-
有的实数是有理数
取\(P(x)\)表示\(x\)是有理数，\(R(x)\)表示\(x\)是实数。则原句可以形式化为\((\exist x)(R(x)\land P(x))\)
注意，“有的……是……”这样类型的语句一般用\(\land\)
-
有的实数不是有理数
取\(P(x)\)表示\(x\)是有理数，\(R(x)\)表示\(x\)是实数。则原句可以形式化为\((\exist x)(R(x)\land \neg P(x))\)
-
没有无理数是有理数
取\(P(x)\)表示\(x\)是有理数，\(Q(x)\)表示\(x\)是无理数数。则原句可以形式化为\(\neg(\exist x)(Q(x)\land P(x))\)
-
至少有一个偶数是素数
取\(A(x)\)表示\(x\)为偶数，\(B(x)\)表示\(x\)为素数。则原句可以形式化为\((\exist x)(A(x)\land B(x))\)
-
至少有一个偶数并且至少有一个素数
取\(A(x)\)表示\(x\)为偶数，\(B(x)\)表示\(x\)为素数。则原句可以形式化为\((\exist x)A(x)\land(\exist x) B(x)\)
-
函数\(f(x)\)在\([a,b]\)上的点\(x_0\)处连续
根据微积分的知识，可以形式化为\((\forall \epsilon)(\epsilon >0\rightarrow (\exist \delta)(\delta>0\land (\forall x)(|x-x_0|<\delta\rightarrow|f(x)-f(x_0)|<\epsilon)))\)
-
自然数集合的形式描述
即，论域是自然数集，我们要形式化下列语句（自然数集合建立公理）：\(\\\\(1)\)对于每个数，有且仅有一个相继后元\(\\\\(2)\)没有一个数的相继后元是0 \(\\\\(3)\) 对于除0以外的数，有且仅有一个相继前元。
设谓词\(P(x,y)\)表示\(x=y\)，函数\(f(x)=x+1\)，函数\(g(x)=x-1\)。则原句可以形式化为：\(\\\\(1)(\forall x)(\exist y)(P(y,f(x))\land(\forall z)(P(z,f(x))\rightarrow P(y,z)) )\\\\(2)\neg(\exist x)P(0,f(x))\\\\(3)(\forall x)(\neg P(0,x)\rightarrow (\exist 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)\)
\((\exist 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)\)
\((\exist 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)(\exist x)P(x,y)=(\exist x)P(x,1)\land (\exist x)P(x,2)=(P(1,1)\lor P(2,1))\land(P(1,2)\lor P(2,2))\)
\((\exist x)(\exist y)P(x,y)=(\exist y)P(1,y)\lor(\exist y)P(2,y)=P(1,1)\lor P(1,2)\lor P(2,1)\lor P(2,2)\)