logic - 布尔运算符和归纳

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 | 问。

(c) 归纳证明可能如下所示：

基本情况：p 等价于 p，而 p @ p 为 False，因为 p & ~p 是矛盾的。

归纳假设：假设长度为 k 的所有命题仅包含 p 和 @ 操作等价于 p 或 False。

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

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

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