2011-11-28 101 views
4

我正在使用一些工具,并且它可以确定特定事务是否成功的唯一方法是它是否通过了各种检查。但是,它一次只能进行一次检查的方式受到限制,并且必须是连续的。一切都必须从左到右计算。所有布尔表达式都可以顺序写入吗?

例如,

A || C && D 

它将与A || C来计算第一,然后其结果将是AND“编带D

括号越来越难处理。由于B ||,我无法计算这样的表达式C需要先被计算出来。我无法执行任何操作顺序;

A && (B || C) 

我想我的工作下来,以这个顺序布尔表达式,

C || B && A 

C || B首先计算,那么结果是AND“随着A

灿都布尔ð表达式被成功处理成顺序布尔表达式? (像比如我)

+0

定义“顺序”。为什么'A &&(B || C)'不是“连续的”? –

+0

B || C首先被计算。我无法使用任何操作顺序 – user906153

+0

您所需要的只是'C || B && A'不是'A && C || B && A'。 – Paulpro

回答

5

答案是否定的:

考虑A || B && C || D它具有真值表:

A | B | C | D | 
0 | 0 | 0 | 0 | 0 
0 | 0 | 0 | 1 | 0 
0 | 0 | 1 | 0 | 0 
0 | 0 | 1 | 1 | 0 
0 | 1 | 0 | 0 | 0 
0 | 1 | 0 | 1 | 1 
0 | 1 | 1 | 0 | 1 
0 | 1 | 1 | 1 | 1 
1 | 0 | 0 | 0 | 0 
1 | 0 | 0 | 1 | 1 
1 | 0 | 1 | 0 | 1 
1 | 0 | 1 | 1 | 1 
1 | 1 | 0 | 0 | 0 
1 | 1 | 0 | 1 | 1 
1 | 1 | 1 | 0 | 1 
1 | 1 | 1 | 1 | 1 

如果有可能依次评价也必须是最后的表达这将是两种情况之一:

案例1:

X || Y苏ch YA,B,C,D之一,X是任何顺序布尔表达式。

现在,由于在A,B,C,D没有变量,其中每当该变量为真整个表达式为真,没有:

X || A 
X || B 
X || C 
X || D 

都不可能在表达式中最后操作(任何X)。

情况2:

X && Y:使得YA,B,C,D一个,X是任何顺序的布尔表达式。

现在,由于在A,B,C,D没有可变其中整个表达式为假每当该变量为假,没有:

X && A 
X && B 
X && C 
X && D 

都不可能在表达式中最后操作(任何X)。

因此你不能写这样(A || B) && (C || D)


的原因,你能为一些表达式做到这一点,如:A && (B || C)成为C || B && A是因为表达可以递归构建出具有上述两种属性之一的表达式:

IE。

真值表A && (B || C)是:

A | B | C | 
0 | 0 | 0 | 0 
0 | 0 | 1 | 0 
0 | 1 | 0 | 0 
0 | 1 | 1 | 0 
1 | 0 | 0 | 0 
1 | 0 | 1 | 1 
1 | 1 | 0 | 1 
1 | 1 | 1 | 1 

,我们可以很快看到有一个是假的,只要A是0,所以我们的表达可能是X && A财产。

接下来我们就来了真值表,看看只,其中A是1行是原始:

B | C 
0 | 0 | 0 
0 | 1 | 1 
1 | 0 | 1 
1 | 1 | 1 

其中有这是真的,每当B为1的属性(或C,我们可以在这里选择)。所以,我们可以写出表达

X || B,整个表达式为X || B && A

然后我们再减少表,其中B为0的部分,我们得到:

C 
0 | 0 
1 | 1 

X是不仅仅是C所以最终的表达是C || B && A

+0

+1一个美丽的证明! –

0

你就不能做到这一点:

((A || C) && D) 

,并为您的第二个例子:

(((A && C) || B) && A) 

会为你工作?

希望帮助...

0

,如果你需要做这样的东西(A || B) && (C || D)除非你可以存储供以后使用的中间值,你会打的问题。

如果允许构建多个链并尝试所有这些链,直到其中一个通过或者它们全部失败(因此每个链实际上都是OR),那么我认为您可以处理任何组合。上面的例子将成为(每一行是一个单独的查询):

(A && C) || 
(A && D) || 
(B && C) || 
(B && D) 

然而,对于一个非常复杂的检查,这可能很容易失控!

1

这是重写,这样在右侧出现没有括号的表达式的问题。逻辑AND(∧)和OR(∨)都是可交换:

  • 甲∧ B = ∧甲
  • 甲∨ B =乙∨甲

因此可以重写任何表达“(Y)a X”的形式“X a(Y)”:

  • A ∧(B ∧ C)=(A ∧ B)∧Ç
  • 甲∧(B ∨ C)=(B ∨ C)∧甲
  • 甲∨(B ∧ C)=(B ∧ C)∨甲
  • 甲∨(B ∨ C)=(B ∨ C)∨甲

它们也分配,由下列法律:

  • (A ∧ B)∨(A ∧ C)
    = A ∧(B ∨ C)
    =(B ∨ C)∧甲
  • (A ∨ B)∧(A ∨ C)
    = A ∨(B ∧ C)
    =(B ∧ C)∨甲

因此很多布尔表达式可以在右侧没有括号的情况下重写。但是,作为计数器­的例子,由于缺乏共同的因素,因此没有办法重写如(A ∧ B)∨(C ∧ D)的表达式如果A ≠ C.