명시적 공식

불리언 변수 x1, x2, x3, x4, x5, x6, x7, x8, x9, x10이 있다. 이 열 개의 변수 중에서 서로 다른 변수로 이루어진 모든 쌍(쌍, 2개)과 모든 세쌍(3개)을 생각하자. (쌍은 45가지, 세쌍은 120가지가 있다.) 이 쌍과 세쌍 중에서 값이 1인 변수를 적어도 하나 포함하는 것이 몇 개인지 세자. 그 개수가 홀수면 f(x1, ..., x10) = 1, 짝수면 f(x1, ..., x10) = 0으로 정의한다.

다음은 f(x1, ..., x10)을 올바르게 계산하는 명시적 공식이다:

f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = (x1 ∨ x2) ⊕ (x1 ∨ x3) ⊕ (x1 ∨ x4) ⊕ (x1 ∨ x5) ⊕ (x1 ∨ x6) ⊕ (x1 ∨ x7) ⊕ (x1 ∨ x8) ⊕ (x1 ∨ x9) ⊕ (x1 ∨ x10) ⊕ (x2 ∨ x3) ⊕ (x2 ∨ x4) ⊕ (x2 ∨ x5) ⊕ (x2 ∨ x6) ⊕ (x2 ∨ x7) ⊕ (x2 ∨ x8) ⊕ (x2 ∨ x9) ⊕ (x2 ∨ x10) ⊕ (x3 ∨ x4) ⊕ (x3 ∨ x5) ⊕ (x3 ∨ x6) ⊕ (x3 ∨ x7) ⊕ (x3 ∨ x8) ⊕ (x3 ∨ x9) ⊕ (x3 ∨ x10) ⊕ (x4 ∨ x5) ⊕ (x4 ∨ x6) ⊕ (x4 ∨ x7) ⊕ (x4 ∨ x8) ⊕ (x4 ∨ x9) ⊕ (x4 ∨ x10) ⊕ (x5 ∨ x6) ⊕ (x5 ∨ x7) ⊕ (x5 ∨ x8) ⊕ (x5 ∨ x9) ⊕ (x5 ∨ x10) ⊕ (x6 ∨ x7) ⊕ (x6 ∨ x8) ⊕ (x6 ∨ x9) ⊕ (x6 ∨ x10) ⊕ (x7 ∨ x8) ⊕ (x7 ∨ x9) ⊕ (x7 ∨ x10) ⊕ (x8 ∨ x9) ⊕ (x8 ∨ x10) ⊕ (x9 ∨ x10) ⊕ (x1 ∨ x2 ∨ x3) ⊕ (x1 ∨ x2 ∨ x4) ⊕ (x1 ∨ x2 ∨ x5) ⊕ (x1 ∨ x2 ∨ x6) ⊕ (x1 ∨ x2 ∨ x7) ⊕ (x1 ∨ x2 ∨ x8) ⊕ (x1 ∨ x2 ∨ x9) ⊕ (x1 ∨ x2 ∨ x10) ⊕ (x1 ∨ x3 ∨ x4) ⊕ (x1 ∨ x3 ∨ x5) ⊕ (x1 ∨ x3 ∨ x6) ⊕ (x1 ∨ x3 ∨ x7) ⊕ (x1 ∨ x3 ∨ x8) ⊕ (x1 ∨ x3 ∨ x9) ⊕ (x1 ∨ x3 ∨ x10) ⊕ (x1 ∨ x4 ∨ x5) ⊕ (x1 ∨ x4 ∨ x6) ⊕ (x1 ∨ x4 ∨ x7) ⊕ (x1 ∨ x4 ∨ x8) ⊕ (x1 ∨ x4 ∨ x9) ⊕ (x1 ∨ x4 ∨ x10) ⊕ (x1 ∨ x5 ∨ x6) ⊕ (x1 ∨ x5 ∨ x7) ⊕ (x1 ∨ x5 ∨ x8) ⊕ (x1 ∨ x5 ∨ x9) ⊕ (x1 ∨ x5 ∨ x10) ⊕ (x1 ∨ x6 ∨ x7) ⊕ (x1 ∨ x6 ∨ x8) ⊕ (x1 ∨ x6 ∨ x9) ⊕ (x1 ∨ x6 ∨ x10) ⊕ (x1 ∨ x7 ∨ x8) ⊕ (x1 ∨ x7 ∨ x9) ⊕ (x1 ∨ x7 ∨ x10) ⊕ (x1 ∨ x8 ∨ x9) ⊕ (x1 ∨ x8 ∨ x10) ⊕ (x1 ∨ x9 ∨ x10) ⊕ (x2 ∨ x3 ∨ x4) ⊕ (x2 ∨ x3 ∨ x5) ⊕ (x2 ∨ x3 ∨ x6) ⊕ (x2 ∨ x3 ∨ x7) ⊕ (x2 ∨ x3 ∨ x8) ⊕ (x2 ∨ x3 ∨ x9) ⊕ (x2 ∨ x3 ∨ x10) ⊕ (x2 ∨ x4 ∨ x5) ⊕ (x2 ∨ x4 ∨ x6) ⊕ (x2 ∨ x4 ∨ x7) ⊕ (x2 ∨ x4 ∨ x8) ⊕ (x2 ∨ x4 ∨ x9) ⊕ (x2 ∨ x4 ∨ x10) ⊕ (x2 ∨ x5 ∨ x6) ⊕ (x2 ∨ x5 ∨ x7) ⊕ (x2 ∨ x5 ∨ x8) ⊕ (x2 ∨ x5 ∨ x9) ⊕ (x2 ∨ x5 ∨ x10) ⊕ (x2 ∨ x6 ∨ x7) ⊕ (x2 ∨ x6 ∨ x8) ⊕ (x2 ∨ x6 ∨ x9) ⊕ (x2 ∨ x6 ∨ x10) ⊕ (x2 ∨ x7 ∨ x8) ⊕ (x2 ∨ x7 ∨ x9) ⊕ (x2 ∨ x7 ∨ x10) ⊕ (x2 ∨ x8 ∨ x9) ⊕ (x2 ∨ x8 ∨ x10) ⊕ (x2 ∨ x9 ∨ x10) ⊕ (x3 ∨ x4 ∨ x5) ⊕ (x3 ∨ x4 ∨ x6) ⊕ (x3 ∨ x4 ∨ x7) ⊕ (x3 ∨ x4 ∨ x8) ⊕ (x3 ∨ x4 ∨ x9) ⊕ (x3 ∨ x4 ∨ x10) ⊕ (x3 ∨ x5 ∨ x6) ⊕ (x3 ∨ x5 ∨ x7) ⊕ (x3 ∨ x5 ∨ x8) ⊕ (x3 ∨ x5 ∨ x9) ⊕ (x3 ∨ x5 ∨ x10) ⊕ (x3 ∨ x6 ∨ x7) ⊕ (x3 ∨ x6 ∨ x8) ⊕ (x3 ∨ x6 ∨ x9) ⊕ (x3 ∨ x6 ∨ x10) ⊕ (x3 ∨ x7 ∨ x8) ⊕ (x3 ∨ x7 ∨ x9) ⊕ (x3 ∨ x7 ∨ x10) ⊕ (x3 ∨ x8 ∨ x9) ⊕ (x3 ∨ x8 ∨ x10) ⊕ (x3 ∨ x9 ∨ x10) ⊕ (x4 ∨ x5 ∨ x6) ⊕ (x4 ∨ x5 ∨ x7) ⊕ (x4 ∨ x5 ∨ x8) ⊕ (x4 ∨ x5 ∨ x9) ⊕ (x4 ∨ x5 ∨ x10) ⊕ (x4 ∨ x6 ∨ x7) ⊕ (x4 ∨ x6 ∨ x8) ⊕ (x4 ∨ x6 ∨ x9) ⊕ (x4 ∨ x6 ∨ x10) ⊕ (x4 ∨ x7 ∨ x8) ⊕ (x4 ∨ x7 ∨ x9) ⊕ (x4 ∨ x7 ∨ x10) ⊕ (x4 ∨ x8 ∨ x9) ⊕ (x4 ∨ x8 ∨ x10) ⊕ (x4 ∨ x9 ∨ x10) ⊕ (x5 ∨ x6 ∨ x7) ⊕ (x5 ∨ x6 ∨ x8) ⊕ (x5 ∨ x6 ∨ x9) ⊕ (x5 ∨ x6 ∨ x10) ⊕ (x5 ∨ x7 ∨ x8) ⊕ (x5 ∨ x7 ∨ x9) ⊕ (x5 ∨ x7 ∨ x10) ⊕ (x5 ∨ x8 ∨ x9) ⊕ (x5 ∨ x8 ∨ x10) ⊕ (x5 ∨ x9 ∨ x10) ⊕ (x6 ∨ x7 ∨ x8) ⊕ (x6 ∨ x7 ∨ x9) ⊕ (x6 ∨ x7 ∨ x10) ⊕ (x6 ∨ x8 ∨ x9) ⊕ (x6 ∨ x8 ∨ x10) ⊕ (x6 ∨ x9 ∨ x10) ⊕ (x7 ∨ x8 ∨ x9) ⊕ (x7 ∨ x8 ∨ x10) ⊕ (x7 ∨ x9 ∨ x10) ⊕ (x8 ∨ x9 ∨ x10)

여기서 ∨는 논리합(OR), ⊕는 배타적 논리합(XOR)을 뜻한다.

x1, x2, ..., x10의 값이 주어졌을 때, f(x1, ..., x10)의 값을 구하여라.

10개의 수 x1, x2, x3, x4, x5, x6, x7, x8, x9, x10이 주어진다. 각각은 0 또는 1이다.

f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)의 값 하나를 출력한다.