boolean-logic - 将带/括号的条件表达式转换为不带括号的从左到右求值

Question

我们的框架具有用于业务逻辑的简单表达语言。不幸的是，这不支持括号，也不支持运算符优先级。相反，它使用从左到右的评估。

所以下面的表达式:

a & b | c & d

将被评估为

((a & b) | c) & d

任何带括号的条件表达式都可以转换为等效的所有括号从左到右分组的条件表达式吗？

更具体地说:这个公式的正确转换是什么？

(a & b) | (c & d)

Answer 1

我认为一般来说这是不可能的。看看为什么，让我们把

p := a & b

并首先假设存在 q取决于或 a,b,c,d以至于

p | (c & d) = q | c

然后 c意味着 p | (c & d)或 c -> (p | d) .所以 c -> p或 c -> d ，两者都不可能，因为 c不在 p和 c不是 d (一般来说)。

同样的论点也适用于 d而不是 c .

现在为 &而不是 | .让我们假设

p | (c & d) = q & c

一些 q .在这种情况下 c=false意味着 p | (c & d) = false ，这意味着 p = false .换句话说 ~c -> ~p或 p -> c ，这又是不可能的，因为 c不在 p .
d 的相同参数而不是 c .

一些说明

用左到右括号书写的公式，例如 ((a & b) | c) & d括号之间的每个子表达式的格式如下:

(<expr>) & x

或者

(<expr>) | x

哪里 <expr>递归地具有相同的方面和 x一个 bool 变量。在上面的例子中，我们有:

((a & b) | c) & d = (<expr>) & d

在哪里

<expr> = (a & b) | c

又是同类:

(a & b) | c = <expr> | c

与 <expr> = a & b ，再次 a & b = <expr> & b ，这次是 <expr> = a .

换句话说，你要找的那种公式都是这两种: <expr> | x或 <expr> & x .

我的主张是一般 bool 表达式不能总是转换为所需的方式。如果我错了，则给出任何 bool 表达式 p组合 p | (c & d)可以改写。让我们看看这是不可能的。有两种情况:

p | (c & d) = <expr> & x

或者

p | (c & d) = <expr> | x

现在放 q = <expr>并再次阅读我上面的原始解释以了解无法重写 p | (c & d)以上两种方式中的任何一种。特别是该权利要求适用于 (a & b) | (c & d) .