합니까 연산자를 사용하여 A, B와 C 사이의 모든 조합이 계정?
귀하의 규칙에 따라 다르지만 합당한 규칙이 있다고 생각합니다. 예를 들어 A & (!B & !C)이 표시되지 않습니다.
손으로 직접해야하는 대신이 조합을 계산하는 방법이 있습니까?
양식이 귀하의 양식에 속하는 규칙을 적어 두십시오. 구체적으로 말하십시오. A, B 및 C이 각각 정확히 한 번 표시됩니까? 이 중 0, 1, 2 또는 3은 임의의 표현식에서 무효화 될 수 있습니까? 괄호는 항상 가장 오른쪽에있는 연산 주위에 있고 가장 왼쪽에있는 연산자는 아닌가? 괄호로 둘러싸인 표현식을 무효화 할 수 있습니까? 허용되지 않는 여러 부정을 확인하면 그 가능성을 고려한 것으로 나타납니다.
규칙을 수립하면 표현식에 필요한 구성 요소와 제한 사항을 검토하고 모든 제약 조건이 충족되는 모든 요구 사항을 충족시키기위한 옵션 수를 말할 수 있습니다. 예를 들어, 가정 A, B, C 각 변수가 이항 연산자가 자유롭게 선택할 수 있다는 것을 부정 여부를 될 수 있음을, 정확히 한 번 순서에 표시 독립적으로, 내가 얻을 : 선택하고 준비하는
- 한 방법을 변수
A, B, C
- 1 발현을 부정을 배치
- 2^3 = 8 가지 (3 개 변수 번 괄호 표현식 모두 하나가 무효 여부) 이진 연산자를 선택할
- 3^2 = 9 가지를 괄호로하는 방법 (3 명, 2 명, 자유롭게 각각 선택)
- 총계 : 1 x 1 x 8 x 9 = 72 식
이러한 72 개의 표현식 중 일부는 동일합니다. 특히 !X^!Y = X^Y, !X^Y = X^!Y 및 X^!Y = !X^Y이므로 두 번째 연산자로 ^을 선택하면 1/2 사례에서 두 배로 계산됩니다. 모든 경우의 1/3. 72 x 1/2 x 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 x 1/2 x 1/3 x 1/3 x 1/2 = 72/36 = 2 경우에는 다시 추가해야합니다. 그래서 우리는 62 개의 논리적으로 구별 된 표현식과 10 개의 표현식을 다른 62 개의 표현식과 동일하게하여 총 72 개의 표현식을 만듭니다.
3 개의 변수에 대해 논리적으로 고유 한 256 개의 표현식이있을 것으로 예상됩니다 (3 개의 변수에 대한 2^3 할당과 각 할당에 대한 2 개의 함수 값은 2^(2^3) = 2^8 = 256 함수를 의미 함) . 유사하게, 하나의 변수에 대해 2^(2^1) = 2^2 = 4이고, 하나의 변수에 대해 2^(2^0) = 2^4 = 변수가없는 경우 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이 &, | 또는 ^ 뒤에 :
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
하나를 구성하는 시작이에 대한 표현이없는 볼 수 있습니다. & 인 경우 한쪽에만 T을 사용할 수 있지만 두 가지 모두에 T을 넣을 수는 없습니다. | 인 경우, 절반은 모두 T이어야하며, 반쪽도 모두 T입니다. 그래서 ^이 유일한 옵션입니다.
A은 무효입니다.
입니다
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
, B 및 C에 대한 표현식이 A, 모순에 따라 달라집니다 :이 부정되는 경우, 우리는 B 및 C에 대해 다음과 같은 진리표가 필요합니다. 따라서이 진리표가있는 우리 체계에는 표현이 없습니다. 다음은 진리표가있는 세 변수의 표현입니다. (A & B) | (B & C) | (A & C)