2017-10-16 127 views
2

我在寻找3个二进制输入A,B和C(使用它们全部)的可能组合的可能组合,将给出它们之间可用的操作符范围。我们有OR,AND,XOR和不可用的,我有这个名单的结论:给定操作员数量的3个二进制输入组合的数量是多少?

A & (B & C), !A & (B & C), !A & (!B & C), !A & (!B & !C) 
A & (B | C), !A & (B | C), !A & (!B | C), !A & (!B | !C) 
A & (B^C), !A & (B^C), !A & (!B^C), !A & (!B^!C) 

A | (B & C), !A | (B & C), !A | (!B & C), !A | (!B & !C) 
A | (B | C), !A | (B | C), !A | (!B | C), !A | (!B | !C) 
A | (B^C), !A | (B^C), !A | (!B^C), !A | (!B^!C) 

A^(B & C), !A^(B & C), !A^(!B & C), !A^(!B & !C) 
A^(B | C), !A^(B | C), !A^(!B | C), !A^(!B | !C) 
A^(B^C), !A^(B^C), !A^(!B^C), !A^(!B^!C) 

是否该帐户使用运营商A,B和C之间的所有组合?有没有办法来计算这个数量的组合,而不是我必须手动做这个?

由于

回答

1

这是否帐户使用运营商A,B和C之间的所有组合?

这取决于你的规则是什么,但给了合理的规则,我不会想。例如,我没有看到A & (!B & !C)

有没有办法计算这个数量的组合,而不是我必须手工做这个?

写下您的表单的规则是什么。请明确点。 ABC每个都只出现一次?任何表达式中的任何数字(0,1,2或3)都可以被否定吗?圆括号总是围绕最右边的操作而不是最左边的操作?加括号的表达能否被否定?确认多重否定被拒绝等事情也会表明你已经考虑过这种可能性。

一旦你有了规则,你可以通过所需的组件和表达式的限制,并说明你有多少选项满足每个约束条件下的每个需求。举例来说,假设A, B, C出现一次,以及按照这个顺序,每个变量可以被否定或没有,而二元运算符可以自由选择独立,我得到:

  • 1的方式来选择和安排变量A, B, C
  • 1方式圆括号表达
  • 2^3 = 8点的方式来放置否定(3个变量,一个括号的子表达式,所有要么否定与否)
  • 3^2 = 9点的方式来选择的二进制运算符(3名操作员,两个放置它们的地方,各自选择)
  • 总计:1×1×8×9 = 72个表达式

有些72个的表达式将相当于;特别是!X^!Y = X^Y,!X^Y = X^!YX^!Y = !X^Y,因此当我们选择^作为第二个操作员时,我们在1/2个案例中重复计数 - 所有案例的1/3。 72×1/2×1/3 = 72/6 = 12应该是6,所以72-6 = 66我们的表情依然存在。

但是等一下,请记住De Morgan:(X & Y) = !(!X | !Y)(X | Y) = !(!X & !Y)。所以我们的表达式!A^(B & C)A^(!B | !C)与上面相同的推理是相同的。也就是说,如果最左边的操作是^而且A被否定(分别是案例的1/3和案例的1/2),我们再次重复计算。72 x 1/3 x 1/2 = 72/6 = 12应该是6.所以66 - 6 = 60表达式仍然存在。

当然,这两种情况可以一起发生。我们需要补充,否则我们会有过度补偿。在72×1/2×1/3×1/3×1/2 = 72/36 = 2的情况下,我们需要加回来。所以我们有62个逻辑上不同的表达式,10个表达式相当于另外62个表达式的总和。我们预计在三个变量(2^3分配给3个变量,每个分配2个函数值,意味着2 ^(2^3)= 2^8 = 256个函数)上有256个逻辑独特表达式。 。同样,对于一个变量,2 ^(2^1)= 2^2 = 4,2 ^(2^2)= 2^4 = 16函数,2 ^(2^0)= 2^1 = 2没有变量。利用这一点,我们可以计算出有多少独特的功能,有超过正好三个变量:

exactly 0: 2 
    0 f = T *** 
    1 f = F *** 

exactly 1: 4 - (1 choose 0) * 2 = 2 
    00 f(X) = F 
    01 f(X) = !X *** 
    10 f(X) = X *** 
    11 f(X) = T 

exactly 2: 16 - (2 choose 1) * 2 - (1 choose 0) * 2 = 10 
    0000 f(X,Y) = T 
    0001 f(X,Y) = !X & !Y *** 
    0010 f(X,Y) = !X & Y *** 
    0011 f(X,Y) = !X 
    0100 f(X,Y) = X & !Y *** 
    0101 f(X,Y) = !Y 
    0110 f(X,Y) = X^Y  *** 
    0111 f(X,Y) = !X | !Y *** 
    1000 f(X,Y) = X & Y  *** 
    1001 f(X,Y) = !(X^Y) *** 
    1010 f(X,Y) = Y 
    1011 f(X,Y) = !X | Y *** 
    1100 f(X,Y) = X 
    1101 f(X,Y) = X | !Y *** 
    1110 f(X,Y) = X | Y  *** 
    1111 f(X,Y) = T 

exactly 3: 256 - (3 choose 2) * 10 - (3 choose 1) * 4 - (3 choose 0) * 2 = 212 
... 

这意味着大约有184三个变量的函数,可以在此表示编码,或约150种功能需要至少有三个变量。一个不能由我们的任何表达式计算的函数是:A,B和C中至少有两个是真的。真值表是:

A B C f(A,B,C) 
T T T T 
T T F T 
T F T T 
T F F F 
F T T T 
F T F F 
F F T F 
F F F F 

要看到有这个毫无表情,开始建立一个:

A其次是&|^。如果&,我们只能在一半中拥有T s,但不能同时拥有两个,但我们在两个中都拥有T s。如果|,一半将不得不全部为Ts,但我们的一半都不是全部Ts。所以^是我们唯一的选择。

A要么是否定的,要么是否定的。如果是否定的,我们需要一个真值表像BC如下:

B C g(B,C) 
T T F 
T F F for A=T, T for A=F 
F T F for A=T, T for A=F 
F F T for A=T, F for A=F 

也就是说,BC子表达式将取决于A,一对矛盾。所以我们的方案中没有表达这个真值表。以下是真值表中三个变量的表达式:(A & B) | (B & C) | (A & C)

相关问题