Comp520MLCourse-6.3-FirstOrderEquivalence

一阶等价式与蕴含式

$A$ $B$ $A{\leftrightarrow}B$ $A$ $B$ 等价 $A{\Leftrightarrow}B$ .

$A{\Leftrightarrow}B$ $A$ $B$ 都具有相同的值。

例如:

${\forall}x{\lnot}{\lnot}P(x){\Leftrightarrow}{\forall}xP(x)$

${\forall}x{\forall}yA(x,y){\Leftrightarrow}{\forall}y{\forall}xA(x,y)$ ${\lnot}{\exists}xA(x){\Leftrightarrow}{\forall}x{\lnot}A(x)$ ${\exists}x(A(x){\vee}B(x)){\Leftrightarrow}{\exists}xA(x){\vee}{\exists}xB(x)$

$A$ $B$ $A{\rightarrow}B$ $A$ 永真蕴含 $B$ $A{\Rightarrow}B.$

$A{\Rightarrow}B$ $A$ $B$ 为真。

例如:

${\forall}xP(x){\Rightarrow}{\exists}xP(x)$ ${\forall}xA(x){\vee}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\vee}B(x))$ ${\forall}x(A(x){\rightarrow}B(x)){\Rightarrow}{\forall}xA(x){\rightarrow}{\forall}xB(x)$ ${\lnot}{\exists}xA(x){\Rightarrow}{\forall}x{\lnot}A(x)$

置换规则

$A$ $A_{1}$ $B_{1}$ $A$ $A_{1}$ $B$ $A_{1}{\Leftrightarrow}B_{1}$ $A{\Leftrightarrow}B$ .

例如:

${\forall}x{\lnot}{\lnot}P(x){\Leftrightarrow}{\forall}xP(x)$

${\forall}x({\lnot}P(x){\rightarrow}Q(x)){\Leftrightarrow}{\forall}x(P(x)\vee{Q(x)})$ ${\forall}x{\forall}y(P(x){\rightarrow}Q(y)){\Leftrightarrow}{\forall}x{\forall}y({\lnot}Q(y){\rightarrow}{\lnot}P(x))$

换名规则

$x$ $y$ ${\forall}xA(x){\Leftrightarrow}{\forall}yA(y),$ ${\exists}xA(x){\Leftrightarrow}{\exists}yA(y).$

例如:

${\forall}x({\lnot}P(x){\rightarrow}Q(x)){\Leftrightarrow}{\forall}y({\lnot}P(y){\rightarrow}Q(y)).$

注意：换名规则针对的是约束变量。

代入规则

$A$ $A$ $A$ $A$ $B$ $A{\Leftrightarrow}B.$

例如:

${\exists}x{\lnot}P(x,y){\Leftrightarrow}{\exists}x{\lnot}P(x,z).$

注意: 代入规则针对的是自由变量。

量词的转换律

${\lnot}{\forall}x{\lnot}A(x){\Leftrightarrow}{\exists}xA(x)$ ${\lnot}{\exists}x{\lnot}A(x){\Leftrightarrow}{\forall}xA(x)$ ${\lnot}{\forall}xA(x){\Leftrightarrow}{\exists}x{\lnot}A(x)$ ${\lnot}{\exists}xA(x){\Leftrightarrow}{\forall}x{\lnot}A(x)$

量词的分配律

${\forall}x(A(x){\wedge}B(x)){\Leftrightarrow}{\forall}xA(x){\wedge}{\forall}xB(x)$ ${\exists}x(A(x){\vee}B(x)){\Leftrightarrow}{\exists}xA(x){\vee}{\exists}xB(x)$

量词辖域的扩张与收缩律

$B$ $x$ 的谓词公式,则:

${\forall}x(A(x){\vee}B){\Leftrightarrow}{\forall}xA(x){\vee}B$ ${\forall}x(A(x){\wedge}B){\Leftrightarrow}{\forall}xA(x){\wedge}B$

${\forall}x(A(x){\rightarrow}B){\Leftrightarrow}{\forall}xA(x){\rightarrow}B$ ${\forall}x(A(x){\leftarrow}B){\Leftrightarrow}{\forall}xA(x){\leftarrow}B$

${\exists}x(A(x){\vee}B){\Leftrightarrow}{\exists}xA(x){\vee}B$ ${\exists}x(A(x){\wedge}B){\Leftrightarrow}{\exists}xA(x){\wedge}B$

${\exists}x(A(x){\rightarrow}B){\Leftrightarrow}{\exists}xA(x){\rightarrow}B$ ${\exists}x(A(x){\leftarrow}B){\Leftrightarrow}{\exists}xA(x){\leftarrow}B$

量词的消去

$I$ $D=\{a_{1},a_{2},{\cdots},a_{n}\}$ ${\forall}xA(x){\Leftrightarrow}A(a_{1}){\wedge}A(a_{2}){\wedge}{\cdots}{\wedge}A(a_{n})$ ${\exists}xA(x){\Leftrightarrow}A(a_{1}){\vee}A(a_{2}){\vee}{\cdots}{\vee}A(a_{n})$ $A(a_{i})(i=1,2,{\cdots},n)$ $a_{i}$ $A(x)$ $x$ 得到的公式。

含有量词的永真蕴含式

${\forall}xA(x){\vee}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\vee}B(x))$ ${\exists}x(A(x){\wedge}B(x)){\Rightarrow}{\exists}xA(x){\wedge}{\exists}xB(x)$ ${\forall}x(A(x){\rightarrow}B(x)){\Rightarrow}{\forall}xA(x){\rightarrow}{\forall}xB(x)$ ${\exists}xA(x){\rightarrow}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\rightarrow}B(x))$

注意：这些永真蕴含式的逆均不成立。

多个量词的使用

${\forall}x{\forall}yA(x,y){\Leftrightarrow}{\forall}y{\forall}xA(x,y)$ ${\exists}x{\exists}yA(x,y){\Leftrightarrow}{\exists}y{\exists}xA(x,y)$ ${\forall}x{\forall}yA(x,y){\Rightarrow}{\exists}y{\forall}xA(x,y)$ ${\forall}y{\forall}xA(x,y){\Rightarrow}{\exists}x{\forall}yA(x,y)$ ${\exists}y{\forall}xA(x,y){\Rightarrow}{\forall}x{\exists}yA(x,y)$ ${\exists}x{\forall}yA(x,y){\Rightarrow}{\forall}y{\exists}xA(x,y)$ ${\forall}x{\exists}yA(x,y){\Rightarrow}{\exists}y{\exists}xA(x,y)$ ${\forall}y{\exists}xA(x,y){\Rightarrow}{\exists}x{\exists}yA(x,y)$