谓词的概念与表示
分析： x 大于 3； 其中包含两部分：
主语： x
谓语: 大于3
个体词：是指研究对象中可以独立存在的具体或抽象的客体， 可以使用变量、也可以代入特定的值
个体常项：当个体词表示具体或特定的客体；多用小写字母 a,b,c ... 来表示
个体变项：当个体词表示抽象或泛指的个体；多用小写字母 x,y,z ... 来表示
论域：个体变项的取值范围称个体域或论域；有穷集合、无穷集合
全总个体域：包含全宇宙中所有事物的论域；没有特别指明某个论域，则隐含所指是在全总个体域中讨论
谓词：用来指明个体的性质或个体之间的关系等， 常用大写字母 P，Q，R...来表示
谓词常项：表示具体性质或关系的谓词
谓词变项：表示抽象或泛指的性质或关系的谓词
命题函数：由一个谓词、一些个体变量组成的表达式称为谓词变项或命题函数
B（x,c,y）表示：c 位于x和y之间；
jn 表示济南； bj表示北京， sh表示上海
B(bj,jn,sh) 表示语句：济南位于北京和上海之间
谓词变项中，个体变项的数目称为谓词变项的元数， 如\(A(x)\)为一元谓词；\(L(x,y)\)为二元谓词；\(P(X_1，X_2,...,X_n)\)为n元谓词；
当n元谓词中，某一个个体变项取作常量时， 如\(X_1=a\),此时为\(n-1\)元谓词
不带个体变项的谓词称为0元谓词（都是个体常项）
符号化
小张年龄超过18岁，身体健康，具有大学本科学历， 则他可以参见飞行员招录考试
解：小张表示为a， A(x)：x超过18岁，B(x):x身体健康， C(x):x大学毕业，E(x):x参见飞行员考试
\(A(a) \and B(x) \and C(x) \rarr E(x)\)
如果3小于4，且4小于5 则3小于5
\(设 L(x,y):x 小于y；L(3,4) \and L(4,5)\rarr L(3,5)\)
如果某数是有理数,则该数可以写成分数
\(设：P(x):x 是有理数； Q(x):x 是分数； a:某数； G(a)\rarr Q(a)\)
只有2是素数，4才是素数
\(设：P(x):x 是素数； P(4)\rarr P(2)\) 2是素数是必要条件
量词与合式公式
量词表示数量关系；有全称量词与存在量词两种；
全称量词
某一行性质对变量在某一特定领域内的所有值均为真 \(\forall\)
\(\forall_xP(x): P(x)对x在其论域的所有真为真\)
存在量词
表示某一性质对变量在论域内的若干值为真 \(\exists\)
\(\exists_xP(x):论域中存在一个元素使得P(x)为真\)
特性谓词
有的命题中需要指明论域，这些也是谓词， 称为特性谓词。
在全称量词中， 特性谓词是条件式的前件
在存在量词中，特性谓词后跟一个合取项
一般，在全总个体域中才产生特性谓词。如果没有实现明确提出个体域， 则认为个体域是全总个体域。
全班同学都已学过微积分课程
\(设: P(x): x学过微积分课程，S(x): x 是本班学生； \forall_x(S(x)\rarr P(x))\)
每个自然数都是实数
\(设：N(x):x 是自然数， R(x):x 是实数； \forall_x(N(x)\rarr R(x))\)
每人恰有一个朋友
恰有一个：有且仅有一个
\(设：B(x,y): y 是 x的朋友；\forall_x\exists_y\forall_z(B(x,y) \and (z \ne y) \rarr \neg B(x,z))\)
有些水生动物是肺呼吸的
\(设：P(x): x 是水生动物；Q(x)：x 是肺呼吸的； \exists_x(P(x)\and Q(x))\)
所有狮子都是凶猛的
有些狮子不喝咖啡
有些凶猛的动物不喝咖啡
\[\begin{align}
设：&P(x):x是狮子；Q(x):x是凶猛的动物；R(x): x喝咖啡 \\
(1)& \forall_x(P(x) \rarr Q(x)) \\
(2)& \exists_x(P(x)\and \neg R(x)) \\
(3)& \exists_x(Q(x) \and \neg R(x)) \\
\end{align}
\]
没有最大的实数
\[\begin{align}
设\;\;\; & R(x):x是实数 ， L(x,y):x 小于 y；\\
& \forall_x(R(x)\rarr \exists_x(R(y) \and L(x,y)))
\end{align}
\]
每个实数的平方都不小于0
\[\begin{align}
设\;\;\; & R(x):x 是实数，f(x):x的平方， L(x,y): x 小于y； \\
& \forall_x(R(x) \rarr \neg L(f(x),0)) \\
\end{align}
\]
指导变元&辖域
给定谓词合式公式A， 其中一部分公式形式为 \(\forall_xB(x) \text{或} \exists_xB(x)\), 称量词\(\forall,\exists\)后的\(x\)为指导变元或作用变元；\(B(x)\) 为对应量词的辖域（作用域）；
在辖域中，x的一切出现都是约束出现；在\(B(x)\) 中除去约束出现的其他变元的出现都是自由出现
项
项由以下规则形成（函数）
个体常用和个体变元是项
若f是n元函数， 且\(t_1, t_2, ...,t_n\)是项， 则 \(f(t_1, t_2, ..., t_n)\) 是项
所有项都由1和2生成
张强的父亲是教授
设：\(c: 表示张强， f(x): x 的父亲； Q(y): y 是教授；\) 有：
\(Q(f(c))\) 表示： c的父亲是教授， 即张强的父亲是教授
对任意整数x， \(x^2-1=(x+1)(x-1)\) 是恒等式
设 \(I(x): x是整数， f(x)=x^2-1, g(x)=(x+1)(x-1), E(x,y):x=y\)
命题可表示为 \(\forall_x(I(x)\rarr E(f(x), g(x)))\)
⭐ 没有最大的自然数
意味着对于任何一个自然数，都存在一个比它更大的自然数
设：N(x): x 是自然数； L(x,y): x 小于y
\[\begin{align}
\forall_x(N(x)\rarr (\exists_y)(N(y)\and L(x,y)))
\end{align}
\]
谓词演算的等价式与蕴涵式
消去量词
当确定论域后， \(\forall_xP(x)\;\;和\;\; \exists_xP(x)\) 都是一个特定的命题；
设论域元素为 \(a_1, a_2, ..., a_n\) 这下列关系成立
\(\forall_xA(x) \Lrarr A(a_1)\and A(a_2) \and ... \and A(a_n)\) 全称量词对应 合取
\(\exists_yA(x) \Lrarr A(a_1)\or A(a_2)\or ... \or A(a_n)\) 存在量词对应 析取
计算：论域为D={2, 3}; L(x, y) 定义如下， 求： \(\forall_x\exists_yL(x,y)\)
消去量词
\[\begin{align}
&\forall_x\exists_yL(x,y) \\
\Lrarr& (\exists_yL(2, y) \and (\exists_yL(3,y)) \\
\Lrarr& ((L(2,2))\or(L2,3))\and ((L(3,2)) \or (L(3,3))) \\
\Lrarr&(T \or T)\and( F \or F) \Lrarr F
\end{align}
\]
等价式
量词否定等价式
\[\begin{align}
\neg \exists_xA(x) \Lrarr \forall_x\neg A(x) \\
\neg \forall_xA(x) \Lrarr \exists_x \neg A(x)
\end{align}
\]
量词辖域缩小或扩大等价式
\[\begin{align}
(\forall_x)(A(x) \and B) \Lrarr \forall_xA(x) \and B \\
(\exists_x)(A(x) \and B) \Lrarr \exists_xA(x) \and B \\
(\forall_x)(A(x) \or B ) \Lrarr \forall_xA(x) \or B \\
(\exists_x)(A(x) \or B) \Lrarr \exists_xA(x) \or B \\
\\
\color{red}(\forall_x)\color{black}(A(x) \rarr B) \Lrarr \color{red}(\exists_x)\color{black}A(x) \rarr B \tag{量词反转} \\
\color{red}(\exists_x)\color{black}(A(x) \rarr B) \Lrarr \color{red}(\forall_x)\color{black}A(x) \rarr B \tag{量词反转} \\
(\forall_x)(B\rarr A(x)) \Lrarr B \rarr (\forall_x)A(x) \tag{保持顺序} \\
(\exists_x)(B\rarr A(x)) \Lrarr B \rarr (\exists_x)A(x) \tag{保持顺序} \\
\end{align}
\]
量词分配律等价式
\[\begin{align}
(\forall_x)(A(x) \and B(x)) \Lrarr (\forall_x)(Ax) \and (\forall_x)B(x) \tag{全称量词只能搭配合取}\\
(\exists_x)(A(x) \or B(x)) \Lrarr (\exists_x)A(x) \or (\exists_x)B(x) \tag{存在量词只能搭配析取}
\end{align}
\]
蕴涵
\[(\forall_x)A(x) \or (\forall_x)B(x) \color{red}\Rarr\color{black} (\forall_x)(A(x) \or B(x)) \\
(\exists_x)A(x) \and (\exists_x)B(x) \color{red}\Rarr \color{black}(\exists_x)(A(x) \and B(x)) \\
(\forall_x)(A(x) \rarr B(x)) \color{red}\Rarr \color{black}(\forall_x)A(x) \rarr (\forall_x)B(x) \\
(\exists_x)(A(x) \rarr B(x)) \color{red}\Rarr \color{black}(\exists_x)A(x) \rarr (\exists_x)B(x) \\
\]
前束范式
定义如果一个公式的量词均在全式的开头，它们的作用域延申到整个公式的末尾，则称它为前束范式
\((Q_1V_1)(Q_2V_2)...(Q_nV_n)A\) 其中\(Q_i\)是量词（\(\forall/\exist\)）\(V_i\)是指导变元。A为不含有量词的谓词公式
转换步骤
对不同辖域的同名变元进行换名
利用量词否定等价式，将否定联结词深入到命题变元和谓词公式之前
利用等值式将量词提取到最前面 \(\forall_x(A\or B(x))\Lrarr A\or \forall_xB(x)\) 和 \(\exists_x(A \and B(x)) \Lrarr A \and \exist_xB(x)\)
前束范式
非前束范式
\(\forall_x\forall_y\exists_x(Q(x,y)\rarr R(z))\)
\(\forall_xR(x) \and \exist_yS(y)\)
\(\forall_x\forall_y(\neg P(x,y) \rarr Q(y))\)
\(\forall_x(P(x) \rarr (\color{red}\exist_x\color{black})Q(x,y))\)
\(\forall_xP(x)\rarr Q(x)\)
求下列公式的前束范式
\[\begin{align}
&\neg \exist_x(M(x) \and F(x)) \\
\Lrarr& \forall_x\neg(M(x) \and F(x))) \\
\end{align}
\]
\[\begin{align}
& \forall_xF(x) \and \neg \exist_xG(x)\\
\Lrarr& \forall_xF(x) \and \forall_x\neg G(x) \\
\Lrarr& \forall_x(F(x) \and \neg G(x))
\end{align}
\]
\[\begin{align}
&\forall_xF(x) \rarr \exist_y(G(x,y) \and \neg H(y)) \\
\Lrarr&\forall_zF(z) \rarr \exist_y(G(x,y) \and \neg H(y)) \\
\Lrarr&\exist_z\exist_y(F(z)\rarr (G(x,y) \and \neg H(y)))
\end{align}
\]
\[\begin{align}
&\forall_x(F(x,y) \rarr \exist_y(G(x,y) \and H(x,z)))\\
\Lrarr& \forall_x(F(x,u) \rarr \exist_y(G(x,y) \and H(x,z))) \\
\Lrarr& \forall_x\exist_y(F(x,u) \rarr G(x,y) \and H(x,z))
\end{align}
\]
谓词演算推理理论
全称量词消去规则\(\forall-\)
⭐\(\forall_xA(x)\Rarr A(c)\) c 是论域中的任意个体常元
\(\forall_xA(x) \Rarr A(y)\) y 在A(x)中是自由出现的, 即y在公式中没有出现过
全称量词引入规则\(\forall+\)
避免使用
如果论域中的任意个体c使得P(x)， 则有 \(\forall_xP(x)\)
存在量词消去规则\(\exist-\)
⭐\((\exist_x)A(x) \Rarr A(c)\) c 是论域中特定的个体常元
\((\exist_x)A(x)\Rarr A(y)\) 成立的充分条件是：
c或y不得在前提中或则居先推导公式中出现或自由出现
若A(x)中由其他任何自由变元时，不能使用本规则
存在量词引入规则\(\exist+\)
如果已知论域中存在某个个体c使得P(c)为真，则 \(\exist_xP(x)\)
\(A(c) \Rarr (\exist_y)A(y)\) c 为特定个体常元
注意量词消去规则中存在消去时顺序问题:
综合应用
证明下面苏格拉底论证
所有人都是要死的
苏格拉底是人
因此，苏格拉底是要死的
符号化 （个体变元、论域、量词、特性谓词、谓词、 项）
P(x): x是人， D(x):x是要死的， c：苏格拉底
前提： \(\forall_x(P(x)\rarr D(x))、P(c)\)
结论： D(c)
证明：
\[\begin{align}
(1) & \forall_x(P(x)\rarr D(x)) \tag{P规则} \\
(2) & P(c) \rarr D(c) \tag{全称量词消去规则}\\
(3) & P(c) \tag{P规则} \\
(4) & D(c) \tag{T(2)(3) 假言推理}\\
\end{align}
\]
假言推理：$ (A\rarr B)\and A \Rarr B$
\(\forall_x(P(x)\or Q(x)) \Rarr \forall_xP(x) \or \exist_xQ(x)\)
任何人若他喜欢步行，他就不喜欢乘汽车。每个人或喜欢乘汽车，或喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行
P(x):x 喜欢步行；Q(x):x喜欢乘汽车；R(x):x喜欢骑自行车；论域：人
\[(\forall_x)((P(x)\rarr \neg Q(x))) \and (\forall_x)(Q(x)\or R(x)) \and (\exist_x)\neg R(x) \Rarr (\exist_x)\neg P(x)
\]
\[\begin{align}
前提：\\
& \forall_x(P(x) \rarr \neg Q(x)) \\
& \forall_x(Q(x) \or R(x)) \\
& \exist_x\neg R(x) \\
结论:\\
& \exist_x\neg P(x)
\end{align}
\]
证明：