证明{F，→}在功能上是完整的

Question

如何证明{F，→}在功能上是完整的？

我想写p∧q只使用这些符号，但我真的不知道如何解决它。 任何想法？

Answer 1

看那truth table of implication：

如果您修复输入Q到F（假），输出输入P的倒数。 因此，含义和F可以组合成一个逆变器。可以写成Q or not P。两者都有相同的真值表。 这表明，暗示等价于一个反转输入的析取。使用上面显示的逆变器，我们得到一个析取（包括或）。

应用De Morgan's laws看到P implies Q也等于not (P and not Q)。这表明我们可以将含义转化为连词。

分离加否定以及与否定相结合在功能上是完整的。因此，含义与false常数在功能上也是完整的。看看here的正式证明。