부울 대수 최소 공리

수학 논리학에서 부울대수에 대한 최소 공리는 가능한 짧게 선택되는 부울대수학(또는 명제 미적분학)의 공리와 동등한 가정이다.예를 들어, 만약 어떤 사람이 동일성을 당연시하기로 선택한다면,^[1] 6개의 NAND 연산 및 3개의 변수를 갖는 공리는 부울대수와 같다.

$[\displaystyle (a\mid b)\mid c)\mid (a\mid (a\mid c)\mid a)=c}$

여기서 세로 막대는 NAND 논리 연산(쉐퍼 스트로크라고도 함)을 나타낸다.

그것은 스테판 울프람이 식별한 이 재산에 대한 25개의 후보 공리 중 하나로, 4개 이하의 변수를 가진 비전속 모델이 없는 15개 원소(거울 이미지 제외) 이하의 셰퍼 정체성을 열거하여, 윌리엄 매큐네, 브랜든 피텔슨, 래리 워스에 의해 처음으로 동등하게 입증되었다.^[2][3]울프램과 관련된 사이트인 매트릭월드는 이 공리를 "울프램 공리"라고 명명했다.^[4]McCune 외 연구진도 분리와 부정에 기초하여 부울 대수에 대한 더 긴 단일 공리를 발견했다.^[3]

1933년 에드워드 버밀리 헌팅턴은 그 공리를 확인했다.

${\displaystyle {\neg({\neg x}\lor {y})}\lor {neg({\neg x}\lor y}}=x}$

는 OR연산의 교환, x ∨ y= y∨ x{\displaystyle x\lor y=y\lor)}과 결합됨에 따라 부울 논리 연산 대수에 연대의 가정,∨ z()∨ y)해당하는 것)x ∨(∨ zy){\displaystyle(x\lor y)\lor z=x\lor(zy\lor)}.[5]허버트는 헌팅턴의 공리를 교체 할 수 있추측했다. 에 의해

$\displaystyle \neg(x\lor y)\lor \neg(x\lor {\neg y})=x,}$

논리 부정 연산자 $¬{\displaystyle \neg }$의 사용을 한 번 줄여야 한다$.$ 로빈스나 헌팅턴도 이 추측을 증명할 수 없었고, 나중에 상당한 관심을 갖게 된 알프레드 타르스키도 그럴 수 없었다.그 추측은 결국 1996년에 정리하는 소프트웨어의 도움으로 증명되었다.^[6][7][8]이 증거는 로빈스 공리가 연관성 및 공통성과 함께 부울대수의 3 베이스를 형성한다는 것을 입증했다.2 베이시스의 존재는 1967년 Carew Arthur Meredithes에 의해 설립되었다.^[9]

$\displaystyle \neg({\neg x}\lor y)\lor x=x,}$

$\displaystyle \neg ({\neg x}\lor y}\lor (z\lor y)=ylor (z\lor x).}$

이듬해 메러디스는 셰퍼 스트로크 측면에서 2바지를 발견했다.^[10]

$(x\displaystyle)(x\mid x)\mid(y\mid x)=x,}$

${\displaystyle x (y\mid (x\mid z)=(z\mid y)\mid y)\mid x.}$

1973년, 파드마나반과 콰켄부시는 원칙적으로 부울대수에 대해 1 베이스를 산출하는 방법을 시연했다.^[11]이 방법을 직설적으로 적용하면 "엄청난 길이의 축"^[3]이 발생하여 공리가 어떻게 더 짧아질 수 있는지에 대한 의문이 제기되었다.이 탐색은 위에 주어진 셰퍼 스트로크 측면에서 1 베이시스뿐만 아니라 1 베이시스도 산출했다.

$\displaystyle \neg (\neg (x\lor y)\lor z)\lor \neg (\neg z\lor \neg (z\lor u))=z,}$

OR과 NOT의 용어로 쓰여진 것.^[3]

참조