符号化与命题公式

通常,命题是具有真假意义或能判断真假的陈述句。

(1)您好?

(2)请勿吸烟!

(3)台湾是中国的一部分。

(4)人能活一千岁。

(5)月球上有生物存在。

(1)和(2)一个是疑问句一个是祈使句，都不是陈述句，所以不是命题。

由简单句构成的命题称原子命题。

可以用命题标识符来实现原子命题符号化：

$p$$p$: 人能活一千岁;

$q$$q$: 月球上有生物存在。

由若干原子命题和联结词联结而成的命题称复合命题。

"如果我有一双翅膀,那么我能在蓝天上飞翔。"

包含两个原子命题,是复合命题。

可先对原子命题进行符号化：

$p$$p$: 我有一双翅膀;

$q$$q$: 我能在蓝天上飞翔。

然后再对复合命题进行符号化；

$p\to q.$$p{\rightarrow}q.$

"$\to$${\rightarrow}$"与"$\wedge$$\wedge$"和"$\vee$$\vee$"类似，都是联结词, 表示"如果$\cdots$$\cdots$,那么$\cdots$$\cdots$."

当$p$$p$为假或$q$$q$为真时，$p\to q$$p{\rightarrow}q$为真。

原子命题和复合命题都是命题公式。

命题公式是表示命题的公式。 常见的形式是带括号的表达式。

$A$$A$: $(p\to q)\leftrightarrow ((\mathrm{\neg }q)\to (\mathrm{\neg }p))$${\quad}(p{\rightarrow}q)\leftrightarrow((\lnot{q})\rightarrow(\lnot{p}))$

$B$$B$: $(p\to (q\leftrightarrow (\mathrm{\neg }(p\to (\mathrm{\neg }q))))$${\quad}(p\rightarrow(q\leftrightarrow(\lnot(p\rightarrow(\lnot q))))$

在$A$$A$和$B$$B$中,各命题标识符和联结词顺序都相同。但是,由于使用了不同位置的括号,所表达的语义不同。

采用优先级可以去掉某些括号。以下是通常关于优先级的约定：

1.$\mathrm{\neg }$${\,\,}\lnot\,\,\,\,\,\,$ 2.$\wedge ,\uparrow$${\,\,}\land,\uparrow\,\,\,\,\,\,$ 3.$\vee ,\downarrow$${\,\,}\lor,\downarrow\,\,\,\,\,\,$ 4.$\to$${\,\,}\rightarrow\,\,\,\,\,\,$ 5.$\leftrightarrow ,\oplus$${\,\,}\leftrightarrow,\oplus$

其中: 1的优先级最高,5的优先级最低。

联结词中: $\mathrm{\neg }$$\lnot$表示否定; $\wedge$$\land$表示与/合取;

$\uparrow$$\uparrow$表示与非; $\vee$$\lor$表示或/析取; $\downarrow$$\downarrow$表示或非;

$\leftrightarrow$$\leftrightarrow$表示左右蕴含; $\oplus$$\oplus$表示异或。

有了约定的优先级,可对前面的公式进行化简：

$A$$A$: $p\to q\leftrightarrow \mathrm{\neg }q\to \mathrm{\neg }p$${\quad}p{\rightarrow}q\leftrightarrow\lnot{q}\rightarrow\lnot{p}$

$B$$B$: $(p\to (q\leftrightarrow \mathrm{\neg }(p\to \mathrm{\neg }q))$${\quad}(p\rightarrow(q\leftrightarrow\lnot(p\rightarrow\lnot q))$

对于$A$$A$, 在没有括号的情况下, 先进行优先级为1的$\mathrm{\neg }q$${\lnot}q$和$\mathrm{\neg }p$${\lnot}p$运算; 然后进行 优先级为4的$p\to q$$p{\rightarrow}q$运算和$\mathrm{\neg }q\to \mathrm{\neg }p$$\lnot{q}\rightarrow\lnot{p}$运算; 最后进行优先级为5的$\leftrightarrow$$\leftrightarrow$运算。

优先级可以减少括号的使用,但$B$$B$仍需必要的括号。

采用波兰表达式（Polish Notation）或逆波兰表达式的方法可以完全去掉括号。

$A$$A$的波兰表达式:

$A:\leftrightarrow \to pq\to \mathrm{\neg }p\mathrm{\neg }q$$A:{\,\,}\leftrightarrow\rightarrow{p}{q}\rightarrow\lnot{p}\lnot{q}$

$A$$A$的逆波兰表达式:

$A:q\mathrm{\neg }p\mathrm{\neg }\to qp\to \leftrightarrow$$A:{\,\,}q\lnot{p}\lnot\rightarrow{q}{p}\rightarrow\leftrightarrow$

$B$$B$的波兰表达式:

$B:\to p\leftrightarrow q\mathrm{\neg }\to p\mathrm{\neg }q$$B:{\,\,}{\rightarrow}p{\leftrightarrow}q{\lnot}{\rightarrow}p{\lnot}q$

$B$$B$的逆波兰表达式:

$B:q\mathrm{\neg }p\to \mathrm{\neg }q\leftrightarrow p\to$$B:{\,\,}q{\lnot}p{\rightarrow}{\lnot}q{\leftrightarrow}p{\rightarrow}$

命题公式也可以用树表达。树的先序、后序和中序遍历分别对应波兰表达式、逆波兰表达式和带括号的普通形式。

命题公式可以用形式化公式(Well Formed Formulas, $wff$$wff$)来定义:

1.$wff::=p,\mathrm{\forall }p\in P$$\,\,wff ::= p,\,\,\forall p \in P$

2.$wff::=\mathrm{\neg }wff$$\,\,wff ::= \lnot wff$

3.$wff::=wffopwff$$\,\,wff ::= wff\,\,op\,\,wff$

4.$op::=\vee |\wedge |\to |\leftrightarrow |\oplus |\uparrow |\to$$\,\,op ::= \lor | \land | \rightarrow | \leftrightarrow | \oplus | \uparrow | \rightarrow$

其中$P$$P$是原子命题集合,$op$$op$是联结词。

1.$p$$p$和$q$$q$都是公式;

2.$\mathrm{\neg }p$${\lnot}p$和$\mathrm{\neg }q$${\lnot}q$是公式;

3.$p\to q$$p{\rightarrow}q$和$\mathrm{\neg }q\to \mathrm{\neg }p$$\lnot{q}\rightarrow\lnot{p}$是公式;

4.$A$$A$: $p\to q\leftrightarrow \mathrm{\neg }q\to \mathrm{\neg }p$${\quad}p{\rightarrow}q\leftrightarrow\lnot{q}\rightarrow\lnot{p}$是公式。

同理：

5.$p\to \mathrm{\neg }q$$p\rightarrow\lnot q$是公式;

6.$\mathrm{\neg }(p\to \mathrm{\neg }q)$$\lnot(p\rightarrow\lnot q)$是公式;

7.$q\leftrightarrow (\mathrm{\neg }(p\to \mathrm{\neg }q))$$q\leftrightarrow(\lnot(p\rightarrow\lnot q))$是公式;

8.$B$$B$: $(p\to (q\leftrightarrow (\mathrm{\neg }(p\to \mathrm{\neg }q)))$${\quad}(p\rightarrow(q\leftrightarrow(\lnot(p\rightarrow\lnot q)))$是公式。