&& 和 || 的表达方式仅使用 -> 和 neg

Question

如何用"Implies"和"Negation"表达"AND"和"OR"？

我尝试了 10 多个 AND 组合，但没有一个成功：

我试过：(X -> Y) -> ( X -> Y) , !(X -> Y) -> (X -> Y) , !(X -> Y) -> !( X -> Y) (X -> Y) -> !(X -> Y) 等

Answer 1

(a -> b) 等同于 ((!a) || b)

由此得出 ((!a) -> b) 等同于 ((! (!a)) || b)

所以 ((!a) -> b) 给你 (a || b)

对于 && 我建议你查一下德摩根定律：https://en.wikipedia.org/wiki/De_Morgan%27s_laws

Answer 2

我们可以欺骗并使用真相 tables 来弄清楚。 ->、!、&& 和 || 的真相 table 看起来像：

X    Y    X->Y    ~X    ~Y    X && Y    X || Y
T    T    T       F     F     T         T
T    F    F       F     T     F         T
F    T    T       T     F     F         T
F    F    T       T     T     F         F

我们看到 && 有一个 T，|| 有一个 F。 || 实际上非常接近 ->；它只是将 F 从 X 是 F 的地方转移到 X 是 T 的地方。当你看到这样的东西时，你首先想到的应该是否定变量以交换相应部分的真相table；通过在 X -> Y 中取反 X，我们应该交换真实部分 table 并得到与 X && Y 相同的值。的确，

X    Y    ~X    ~X -> Y    X || Y
T    T    F     T          T
T    F    F     T          T
F    T    T     T          T
F    F    F     F          F

倒数第一。对于 &&，我们看到它是相似的，除了我们有一个 T 而不是 F 作为 ->。当你看到这个时，事情否定了整个事情：

X    Y    X && Y    !(X && Y)
T    T    T         F
T    F    F         T
F    T    F         T
F    F    F         T

现在我们看到我们需要取反 Y 来交换第一行和第二行的真值 table 为 ->:

X    Y    !Y    X -> !Y    !(X -> !Y)
T    T    F     F          T
T    F    T     T          F
F    T    F     T          F
F    F    T     T          F

这是按要求出来的。这完全是看你要做什么——你从哪里开始——并了解你需要到达哪里，然后从任一端或两端开始工作以找出联系。在这些情况下，考虑 "number of Ts" 很方便，但您可能会根据情况找到更有用的东西。