2017-10-16 102 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)

相關問題