證明{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的正式證明。