布尔算子与归纳

Question

让@表示由右方定义的二进制布尔运算符:p@q= (p ^q)

(b)操作符集{@，}是否完整？详细解释。

(c)通过归纳证明，仅使用布尔运算符@(或根本不使用运算符)的单个命题变量p中的任何命题公式都等价于真值False或单一命题变量p.解释性。

Answer 1

(b)是。

• ~(p &p@ q) = ~(p &p& ~q) = ~p -> q.
• p @q=p& ~q =p& q.
• ~(~p @ q) =~(p&p&q)=~(p~p&q)=~(p~p ~q) =p_q=p_p_ q.

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

基例:p等价于p，p@p是假的，因为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=False；x@y= p，根据需要；
• x = False，y= p:然后x@y= False，根据需要；
• x = False，y= False：
• @y=False。

f 217

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