联结词的完备集

与非联结词 $\uparrow$ NAND 或非联结词 $\downarrow$ NOR 不可兼析取 $\bar{\vee }$ XOR

n 元真值函数

称 $F:\{0,1{\}}^n\to \{0,1\}$ 为 $n$ 元真值函数.

$n$ 个命题变项共有 $2^{2^n}$ 个 $n$ 元真值函数.

任何一个含有 $n$ 个命题变项的命题公式 $A$ 都对应唯一的一个 $n$ 元真值函数 $F$, $F$ 恰好为 $A$ 的真值表.

指向原始笔记的链接

定义 设 $S$ 是一个联结词集合, 如果任何 $n$ 元真值函数都可以由仅含 $S$ 中的联结词构成的公式表示, 则称 $S$ 为联结词完备集.

若 $S$ 是联结词完备集, 则任何命题公式都可以由 $S$ 中的联结词表示.

定理 $S=\{\neg ,\wedge ,\vee \}$ 是联结词完备集.

$\{\wedge ,\vee ,\to ,\leftrightarrow \}$ 不是联结词完备集, 因为 0 不能由其表示. 其子集也不是联结词完备集.

定理 $\{\uparrow \}$ 和 $\{\downarrow \}$ 为联结词完备集.

如果联结词完备集 $S$ 中任何一个联结词去掉后都不完备, 则称 $S$ 为最小联结词完备集.