证明 {F,→} 功能完备
Prove that {F,→} is functionally complete
How can I prove that {F,→} is functionally complete?
我正在尝试仅使用这些符号来编写 p∧q，但我真的不知道如何解决它。
有什么想法吗？
看看 truth table of implication:
如果将输入 Q 固定为 F (false)，则输出是输入 P 的倒数。
因此，蕴涵和F可以组合成反相器。
P implies Q可以写成Q or not P。两者都有相同的真值表。
这表明，蕴涵等同于具有一个反向输入的析取。使用上面显示的反相器，我们得到一个析取（包含或）。
套用De Morgan's laws可以看出P implies Q也等同于not (P and not Q)。这说明我们可以把一个蕴涵变成一个连词。
析取加否定以及合取加否定在功能上是完整的。因此，与 false 常量相结合的蕴涵在功能上也是完整的。查看 here 以获得正式证明。
How can I prove that {F,→} is functionally complete?
我正在尝试仅使用这些符号来编写 p∧q，但我真的不知道如何解决它。 有什么想法吗？
看看 truth table of implication:
如果将输入 Q 固定为 F (false)，则输出是输入 P 的倒数。
因此，蕴涵和F可以组合成反相器。
P implies Q可以写成Q or not P。两者都有相同的真值表。
这表明，蕴涵等同于具有一个反向输入的析取。使用上面显示的反相器，我们得到一个析取（包含或）。
套用De Morgan's laws可以看出P implies Q也等同于not (P and not Q)。这说明我们可以把一个蕴涵变成一个连词。
析取加否定以及合取加否定在功能上是完整的。因此，与 false 常量相结合的蕴涵在功能上也是完整的。查看 here 以获得正式证明。