联结词与命题解释

联结词是一种二元逻辑操作符,根据不同的"T"和“F"组合,可能有$2^4=16$$2^4=16$种不同的联结词。列表如下：

以上将$x_1{O}_n{x}_2$$x_1{O_n}x_2$ ($n=1,2,\cdots ,16$$n=1,2,\cdots,16$)的各种运算结果排成16列,这种表格又称真值表。

其中,较常用的联结词有: $O_2$${O_2}$是$\vee$$\lor$; $O_3$${O_3}$是$\leftarrow$$\leftarrow$; $O_5$${O_5}$是$\to$$\rightarrow$; $O_7$${O_7}$是$\leftrightarrow$$\leftrightarrow$; $O_8$${O_8}$是$\wedge$$\land$; $O_9$${O_9}$是$\uparrow$$\uparrow$; $O_{10}$$O_{10}$是$\oplus$$\oplus$; $O_{15}$$O_{15}$是$\downarrow$$\downarrow$.

在命题逻辑中,命题又有命题常量和命题变量之分。

命题常量表示一个特定的命题;命题变量表示任意命题。

命题常量表示一个特定的命题,所以它有确定的真值。

命题变量没有确定的真值,它不是命题,仅当用一个特定命题取代它时,才能确定真值,这称为对命题变量的赋值(Assignment)或解释(Intepretation),通常用$I$$I$表示。

例: 在解释$I=\{p\leftarrow T,q\leftarrow F\}$$I=\{p{\leftarrow}T,q{\leftarrow}F\}$下公式$A$$A$: $p\to q\leftrightarrow \mathrm{\neg }q\to \mathrm{\neg }p$$p{\rightarrow}q\leftrightarrow\lnot{q}\rightarrow\lnot{p}$的真值如下：

即$v_I=T$$v_I=T$.

对一个公式的理解往往需要分析该公式在不同解释下的真值。

对于公式$A$$A$,

设$S$$S$为包含若干联结词的集合,若由$S$$S$中的联结词构成的命题公式能表示任何命题公式,则称$S$$S$是全功能联结词集。

例：$S$$S$={$\mathrm{\neg }$$\lnot$,$\wedge$$\wedge$,$\vee$$\vee$,$\to$$\rightarrow$,$\leftrightarrow$$\leftrightarrow$,$\oplus$$\oplus$,$\uparrow$$\uparrow$,$\downarrow$$\downarrow$,$\nrightarrow$$\nrightarrow$​}是一个全功能联结词集。

判断一个联结词集是否为全功能联结词集,就看该联结词集中的联结词能否取代一个全功能联结词集中的所有联结词。不难验证,剩下7种联结词均可由以上集合$S$$S$中的9种联结词的组合取代。 求证: {$\mathrm{\neg }$${\lnot}$,$\wedge$${\wedge}$,$\vee$${\vee}$,$\to$${\rightarrow}$,$\leftrightarrow$${\leftrightarrow}$}是全功能联结词集.

证明: 由于{$\mathrm{\neg }$${\lnot}$,$\wedge$${\wedge}$,$\vee$${\vee}$,$\to$${\rightarrow}$,$\leftrightarrow$${\leftrightarrow}$,$\oplus$${\oplus}$,$\uparrow$${\uparrow}$,$\downarrow$${\downarrow}$,$\nrightarrow$${\nrightarrow}$}是全功能联结词集,而: $p\oplus q\iff \mathrm{\neg }(p\leftrightarrow q)$$p{\oplus}q{\Leftrightarrow}{\lnot}(p{\leftrightarrow}q)$ $p\uparrow q\iff \mathrm{\neg }(p\wedge q)$$p{\uparrow}q{\Leftrightarrow}{\lnot}(p{\wedge}q)$ $p\downarrow q\iff \mathrm{\neg }(p\vee q)$$p{\downarrow}q{\Leftrightarrow}{\lnot}(p{\vee}q)$ $p\nrightarrow q\iff \mathrm{\neg }(p\to q)$$p{\nrightarrow}q{\Leftrightarrow}{\lnot}(p{\rightarrow}q)$ 故$\oplus$${\oplus}$, $\uparrow$${\uparrow}$, $\downarrow$${\downarrow}$和$\nrightarrow$${\nrightarrow}$这4个联结词都可以由$\mathrm{\neg },\wedge ,\vee ,\to$${\lnot}, {\wedge}, {\vee}, {\rightarrow}$和$\leftrightarrow$${\leftrightarrow}$这5个联结词来取代。$\iff$${\Leftrightarrow}$表示左右的命题公式在任何解释下真值相同。

可见{$\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$${\lnot},{\wedge},{\vee},{\rightarrow},{\leftrightarrow}$}是全功能联结词集。

{$\mathrm{\neg },\wedge ,\vee$${\lnot},{\wedge},{\vee}$},{$\mathrm{\neg },\wedge$${\lnot},{\wedge}$},{$\mathrm{\neg },\vee$${\lnot},{\vee}$}也是全功能联结词集。

求证: {$\mathrm{\neg },\wedge ,\vee$${\lnot},{\wedge},{\vee}$}是全功能联结词集。

证明: 由于{$\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$${\lnot},{\wedge},{\vee},{\rightarrow},{\leftrightarrow}$}是全功能联结词集,而 $p\to q\iff \mathrm{\neg }p\vee q$$p{\rightarrow}q{\Leftrightarrow}{\lnot}p{\vee}q$ $p\leftrightarrow q\iff (\mathrm{\neg }p\vee q)\wedge (p\vee \mathrm{\neg }q)$$p{\leftrightarrow}q{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}{\lnot}q)$ 故$\to$${\rightarrow}$,$\leftrightarrow$${\leftrightarrow}$这两个联结词可以由$\mathrm{\neg }$${\lnot}$,$\wedge$${\wedge}$和$\vee$${\vee}$这三个联结词来取代。

可见{$\mathrm{\neg }$${\lnot}$,$\wedge$${\wedge}$,$\vee$${\vee}$}是全功能联结词集。

在联结词集中,如果一个联结词可以由该集合中其他联结词定义,则此联结词称为冗余联结词。

例:联结词集{$\mathrm{\neg }$${\lnot}$,$\wedge$${\wedge}$,$\vee$${\vee}$}中,{$\vee$$\vee$}是冗余联结词,因为: $p\vee q\iff \mathrm{\neg }(\mathrm{\neg }p\wedge \mathrm{\neg }q)$$p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q)$

设有一个全功能联结词集$S$$S$,若$S$$S$中不含冗余联结词,则称$S$$S$是极小全功能联结词集。

求证: {$\mathrm{\neg },\vee$${\lnot},{\vee}$}是极小全功能联结词集。

证明:由于{$\mathrm{\neg },\wedge ,\vee$${\lnot},{\wedge},{\vee}$}是全功能联结词集,而: $p\wedge q\iff \mathrm{\neg }(\mathrm{\neg }p\vee \mathrm{\neg }q)$$p{\wedge}q{\Leftrightarrow}{\lnot}({\lnot}p{\vee}{\lnot}q)$ 所以,{$\mathrm{\neg },\vee$${\lnot},{\vee}$}是全功能联结词集。

$\vee$${\vee}$和$\mathrm{\neg }$${\lnot}$相互之间不能取代,所以{$\mathrm{\neg },\vee$${\lnot},{\vee}$}是极小全功能联结词集。

是否存在仅有一个元素的极小全功能联结词集？

求证: {$\uparrow$${\uparrow}$}是极小全功能联结词集。

证明: 由于{$\mathrm{\neg },\vee$${\lnot},{\vee}$}是极小全功能联结词集,而 $\mathrm{\neg }p\iff \mathrm{\neg }(p\wedge p)\iff (p\uparrow p)$${\lnot}p{\Leftrightarrow}{\lnot}(p{\wedge}p){\Leftrightarrow}(p{\uparrow}p)$ $p\vee q\iff \mathrm{\neg }(\mathrm{\neg }p\wedge \mathrm{\neg }q)\iff \mathrm{\neg }p\uparrow \mathrm{\neg }q\iff (p\uparrow p)\uparrow (q\uparrow q)$$p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q){\Leftrightarrow}{\lnot}p{\uparrow}{\lnot}q{\Leftrightarrow}(p{\uparrow}p){\uparrow}(q{\uparrow}q)$ 所以{$\uparrow$${\uparrow}$}也是极小全功能联结词集。

它仅含一个联结词,故是极小全功能联结词集。

下面用$\uparrow$${\uparrow}$表示常用的联结词:

$\mathrm{\neg }p\iff \mathrm{\neg }(p\wedge p)\iff p\uparrow p$${\lnot}p{\Leftrightarrow}{\lnot}(p{\wedge}p){\Leftrightarrow}p{\uparrow}p$ $p\wedge q\iff \mathrm{\neg }(p\uparrow q)\iff (p\uparrow q)\uparrow (p\uparrow q)$$p{\wedge}q{\Leftrightarrow}{\lnot}(p{\uparrow}q){\Leftrightarrow}(p{\uparrow}q){\uparrow}(p{\uparrow}q)$ $p\vee q\iff \mathrm{\neg }(\mathrm{\neg }p\wedge \mathrm{\neg }q)\iff (\mathrm{\neg }p)\uparrow (\mathrm{\neg }q)\iff (p\uparrow p)\uparrow (q\uparrow q)$$p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q){\Leftrightarrow}({\lnot}p){\uparrow}({\lnot}q){\Leftrightarrow}(p{\uparrow}p){\uparrow}(q{\uparrow}q)$ $p\to q\iff ((p\uparrow p)\uparrow (p\uparrow p))\uparrow (q\uparrow q)$$p{\rightarrow}q{\Leftrightarrow}((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q)$ $p\leftrightarrow q\iff ((((p\uparrow p)\uparrow (p\uparrow p))\uparrow (q\uparrow q))$$p{\leftrightarrow}q{\Leftrightarrow}((((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q))$ $\uparrow (((q\uparrow q)\uparrow (q\uparrow q))\uparrow (p\uparrow p)))\uparrow$${\uparrow}(((q{\uparrow}q){\uparrow}(q{\uparrow}q)){\uparrow}(p{\uparrow}p))){\uparrow}$ $((((p\uparrow p)\uparrow (p\uparrow p))\uparrow (q\uparrow q))$$((((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q))$ $\uparrow (((q\uparrow q)\uparrow (q\uparrow q))\uparrow (p\uparrow p)))$${\uparrow}(((q{\uparrow}q){\uparrow}(q{\uparrow}q)){\uparrow}(p{\uparrow}p)))$