布尔运算符和归纳

Question

让@表示由下面的右侧定义的二进制布尔运算符：p @ q =（p ^¬q）

（b）操作符集{@，¬}是否完整？详细说明。

（c）通过归纳证明，仅使用布尔运算符@（或完全不使用运算符）的单个命题变量p中的任何命题公式都是等效的真值False或单个命题变量p。解释。

Answer 1

（b）是。

• 〜（p @ q）=〜（p＆〜q）=〜p | q = p-> q。
• p @〜q = p＆~~ q = p＆q。
• 〜（〜p @ q）=〜（〜p＆〜q）= ~~ p | ~~ q = p | q。

（c）归纳证明可能如下所示：

基本情况：p等于p，而p @ p为False，因为p＆〜p是矛盾的。

归纳假设：假设直到k个仅包含p和@的k个运算的所有命题都等于p或False。

归纳步骤：每个仅包含p和@的命题都可以分解为（（x）@（y））形式的公式，其中x和y是长度小于或等于k的公式。根据归纳假设，x和y都等于p或False。有四种情况：

• x = p，y = p;然后x @ y = False，根据需要；
• x = p，y = False;然后根据需要x @ y = p;
• x = False，y = p：然后根据需要x @ y = False；
• x = False，y = False：然后根据需要x @ y = False。

在所有四种情况下，我们都发现（（x）@（y））必须等于p或False。