표준적으로 정의된 부울대수

이 기사는 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수 있습니다. 기술적인 내용은 삭제하지 않고 비전문가도 이해할 수 있도록 개선을 도와주시기 바랍니다. (2022년 12월) (본 템플릿 메시지 삭제 방법 및 시기 알아보기)

부울대수는 두 값의 방정식 이론의 모델입니다. 이 정의는 격자 및 링 정의와 동일합니다.

부울 대수는 추상 대수학에서 수학적으로 풍부한 분야입니다.스탠퍼드 철학 백과사전은 부울 대수를 '유감적 연결만을 갖는 2-값 논리의 대수 또는 결합과 상보 하에 있는 집합의 대수의 등가'로 정의합니다.^[1]군론이 군을 다루는 것과 벡터 공간을 갖는 선형 대수를 다루는 것처럼, 부울 대수는 (해석이 숫자일 필요가 없는) 두 값 0과 1의 등식 이론의 모델입니다.부울 대수, 군, 벡터 공간에 공통적인 것은 어떤 방정식을 만족시키는 일부 연산 아래에서 닫힌 집합인 대수적 구조의 개념입니다.^[2]

정수의 군 $Z{\displaystyle \mathbb{}}$ ${\$ n개의 개체의 순열의 대칭군 S와_n 같은 군의 기본적인 예가 있는 것처럼, 다음과 같은 부울 대수의 기본적인 예도 있습니다.

• 논리 연산 아래의 2진 숫자 또는 비트 0과 1의 대수(접속, 접속, 부정 등).응용 분야로는 명제적 미적분학과 디지털 회로 이론이 있습니다.
• 결합, 교집합, 상보를 포함한 집합 연산 아래의 집합 대수.집합론이 수학의 표준적인 기초이기 때문에 응용 분야는 광범위합니다.

따라서 부울 대수학은 수학적 논리학과 디지털 논리학에 추상 대수학의 방법을 적용하는 것을 허용합니다.

복잡성과 다양성을 보이고 1차 이론이 특수한 경우에만 결정 가능한 유한 차수의 그룹과 달리, 모든 유한 부울 대수는 동일한 정리를 공유하고 결정 가능한 1차 이론을 가지고 있습니다.대신, 부울 대수의 복잡성은 무한 대수의 구조와 그 통사 구조의 알고리즘 복잡성 사이에서 나뉩니다.

정의.

부울 대수는 부울 원형이라고 불리는 최대 2요소 유한 대수의 등식 이론과 부울 대수라고 불리는 이론의 모델을 다룹니다.^[3]이 용어들은 다음과 같이 정의됩니다.

대수는 집합에 대한 연산들의 집합으로, 대수의 기본 집합이라고 불립니다.우리는 부울 프로토타입의 기본 세트를 {0,1}로 잡습니다.

대수는 각각의 연산이 유한하게 많은 인수만을 취할 때 유한합니다.프로토타입의 경우 작업의 각 인수는 작업의 결과와 마찬가지로 0 또는 1입니다.이러한 최대 대수는 {0,1}에 대한 모든 유한 연산으로 구성됩니다.

각 연산이 취하는 인수의 수를 연산의 아리티라고 합니다.arity n 또는 n-ary 작업의 {0,1}에 대한 작업을 n개 인수에 대해 가능한 2개의ⁿ 값 중 하나에 적용할 수 있습니다.각 인수 선택에 대해 n-ary 연산이 2개인²ⁿ 경우, 연산이 0 또는 1을 반환할 수 있습니다.

따라서 프로토타입에는 인수를 사용하지 않는 0 연산 또는 null 연산, 즉 0 연산과 1 연산이 있습니다.이것은 4개의 단항 연산을 가지고 있는데, 그 중 2개는 상수 연산이고, 다른 하나는 항등식이고, 가장 일반적으로 사용되는 부정이라고 하는 것은 그 주장의 반대를 반환합니다: 0이면 1, 1이면 0.이 연산은 16개의 이진 연산으로 구성되어 있습니다. 이 중 2개는 상수이고, 다른 하나는 첫 번째 인수를 반환하지만, 다른 하나는 두 번째 인수를 반환하고, 두 개의 인수가 모두 1이고, 아니면 0이면 1을 반환하고, 다른 하나는 연결이라고 하며, 두 개의 인수가 모두 0이고 아니면 1이면 0을 반환합니다.프로토타입의 (n+1)-ary 연산 수는 n-ary 연산 수의 제곱이므로 16개 = 256개의 3차 연산, 256개 = 65,536개의 4차 연산 등이 있습니다.

패밀리는 인덱스 집합으로 인덱싱됩니다.대수를 구성하는 연산군의 경우, 지수는 연산 기호라고 불리며, 해당 대수의 언어를 구성합니다.각 기호에 의해 색인화된 연산을 해당 기호의 표시 또는 해석이라고 합니다.각 작업 기호는 해당 해석의 희귀도를 지정하며, 여기서 기호에 대한 모든 가능한 해석은 동일한 희귀도를 가집니다.일반적으로 대수는 동일한 연산으로 구별되는 기호를 해석하는 것이 가능하지만, 이는 기호가 연산과 일대일로 일치하는 프로토타입에는 해당되지 않습니다.따라서 프로토타입에는 부울 연산 기호라고 불리며 부울 대수의 언어를 형성하는 2개의²ⁿ n-ary 연산 기호가 있습니다.부정을 위한 ¬, 접속을 위한 ∧, 접속을 위한 ∨와 접속을 위한 ∨와 같은 전통적인 기호를 가진 작업은 극히 일부에 불과합니다.i번째 n번째 기호는 진리표에 대한 부분에서 아래와 같이 f로_i 간주하는 것이 편리합니다.

주어진 언어에서의 등식 이론은 그 언어의 기호를 사용하는 변수들로부터 만들어진 항들 사이의 방정식들로 구성됩니다.부울 대수 언어의 대표적인 방정식은 x ∧리 = y ∧x, x ∧x = x, x ∧¬x = y ∧¬리, x ∧리 = x입니다.

대수는 연산 기호가 해당 대수에 의해 지정된 것으로 해석될 때 방정식이 해당 대수에서 변수의 모든 가능한 값에 대해 성립할 때 방정식을 만족시킵니다.부울 대수의 법칙은 프로토타입에 의해 만족되는 부울 대수 언어의 방정식입니다.위의 예제 중 처음 세 개는 부울 법칙이지만 1 ∧0 ≠ 1 이후 네 번째는 아닙니다.

대수의 등식 이론은 대수에 의해 만족되는 모든 방정식의 집합입니다.따라서 부울 대수의 법칙은 부울 원형의 등식 이론을 구성합니다.

이론의 모델은 이론의 언어로 연산 기호를 해석하고 이론의 방정식을 만족시키는 대수입니다.

부울 대수는 부울 대수의 법칙들의 임의의 모델입니다.

즉, 부울 대수는 부울 연산 기호를 해석하고 부울 프로토타입과 동일한 법칙을 만족시키는 집합 및 연산 패밀리입니다.^[5]

만약 우리가 대수의 호몰로그를 그 대수의 방정식 이론의 모델로 정의한다면, 부울 대수는 프로토타입의 임의의 호몰로그로 정의될 수 있습니다.

예 1.부울 원형은 자신의 법칙을 만족시키기 때문에 부울 대수입니다.따라서 전형적인 부울 대수입니다.우리는 처음에 정의에 순환성이 나타나는 것을 피하기 위해 그것을 그렇게 부르지 않았습니다.

근거

작업이 모두 명시적으로 명시될 필요는 없습니다.기본은 나머지 연산을 구성으로 얻을 수 있는 모든 집합입니다."부울 대수"는 여러 가지 다른 기저들 중 어느 하나에서 정의될 수 있습니다.부울 대수의 세 가지 기본은 일반적으로 사용됩니다. 격자 기본, 링 기본, 그리고 셰퍼 스트로크 또는 NAND 기본.이 기초들은 각각 피험자에게 논리적, 산술적, 인색한 성격을 부여합니다.

• 격자 기반은 19세기에 논리적 사고 과정의 대수적 형식화를 추구하는 부울, 피어스와 다른 사람들의 작업으로 시작되었습니다.
• 고리 기저는 20세기에 제갈킨과 스톤의 연구로 생겨났고 추상 대수학의 배경에서 주제로 온 대수학자들에게 선택의 기초가 되었습니다.부울 대수의 대부분의 처리는 격자 기저를 가정하는데, 주목할 만한 예외는 선형 대수 배경이 분명히 그의 고리 기저를 사랑했던 할모스[1963]입니다.^[6]
• {0,1}에 대한 모든 유한 연산은 셰퍼 스트로크 NAND(또는 그 듀얼 NOR)로 정의될 수 있기 때문에, 결과적인 경제적 기반은 디지털 회로, 특히 디지털 전자 장치의 게이트 어레이를 분석하는 데 있어 선택의 기초가 되었습니다.

격자 기저와 고리 기저의 공통 원소는 상수 0과 1이며, 격자 기저에서는 meet x ∧리, 고리 기저에서는 곱셈 xy로 불리는 연관 교환 이진 연산입니다.그 구별은 단지 용어적인 것일 뿐입니다.격자 기저에는 조인, x ∨리 및 보체인 ¬x의 추가 연산이 있습니다.대신 링 베이스에는 산술 연산 x 덧셈의 ⊕리가 있습니다(후자에는 조인의 부울 읽기가 주어지기 때문에 기호 ⊕는 +보다 우선하여 사용됩니다).

기저가 되는 것은 다른 모든 연산을 구성별로 산출하는 것입니다. 이때 두 기저는 상호 변환 가능해야 합니다.격자 기저는 x ∨리를 x ⊕리 ⊕xy로, ¬x를 x ⊕1로 링 기저로 변환합니다.반대로 고리 기저는 x ⊕리를 격자 기저로 (x ∧¬리) ∧리(x ∨리)로 변환합니다.

이 두 기저 모두 부울 연산의 등식 속성의 부분 집합을 통해 부울 대수를 정의할 수 있습니다.격자 기저의 경우, 부울 대수는 x ∧¬x = 0과 x ∨¬x = 1을 만족하는 분포 격자로 정의하면 충분하며, 이를 상보적 분포 격자라고 합니다.링 베이스는 부울 대수를 부울 링, 즉 x = x를 만족시키는 링으로 바꿉니다.

에밀 포스트는 일련의 연산이 0이 아닌 부울 연산의 기초가 될 필요충분조건을 제시했습니다.사소한 속성은 기본을 구성하는 모든 작업이 아닌 일부 작업이 공유하는 속성입니다.포스트는 5개의 포스트의 클래스와 식별할 수 있는 5개의 중요하지 않은 연산의 속성을 나열했으며, 각각의 속성에 대해 집합에 해당 속성이 없는 연산이 포함되어 있으면 연산의 집합이 기초를 형성했음을 보여주었습니다. (포스트의 정리의 반대, "if"를 "if and only if"로 확장하면 쉬운 관찰입니다.후보 기준의 모든 작업을 보유하는 이 다섯 가지 중에서 하나의 자산이 해당 후보의 구성에 의해 형성된 모든 작업도 보유하게 되며, 따라서 해당 자산의 중요성에 의해 후보는 기초가 되지 못합니다.)포스트의 5가지 속성은 다음과 같습니다.

• 모노톤, 0-1 입력 전환이 없으면 1-0 출력 전환이 발생할 수 있습니다.
• 이중선형 또는 그 이상의 항이 결여된 제갈킨 다항식으로 대표되는 아핀(affine), 예를 들어 x ⊕리 ⊕1이지만 xy는 아닙니다.
• 모든 입력을 보완하여 x 또는 중위수 연산자 xy ⊕yz ⊕zx와 같이 출력을 보완하거나 그 부정을 보완하도록 자체 dual.
• 엄격 (0으로 mapping하는 all-zero 입력);
• 비용이 많이 듭니다. (모든 것을 mapping합니다.)

NAND(dual NOR) 연산은 이 모든 것이 부족하기 때문에 스스로 기반을 형성합니다.

진리표

{0,1}의 마지막 연산은 0과 1을 진리값이 거짓이고 참이라고 생각하여 진리표로 나타낼 수 있습니다.^[7]애플리케이션에 구애받지 않고 통일적이고 독립적인 방식으로 배치할 수 있으므로 이름을 지정하거나 최소한 개별적으로 번호를 지정할 수 있습니다.^[8]이러한 이름은 부울 연산에 편리한 축약어를 제공합니다.n-ary 연산의 이름은 2비트의ⁿ 이진수입니다.두 가지 작업이 있는데²ⁿ 더 간결한 명명법을 요구할 수는 없습니다.각 유한 연산을 스위칭 함수라고 부를 수 있습니다.

이 레이아웃 및 관련 작업 이름은 0부터 2까지의 아티스에 대해 전체적으로 여기에 나와 있습니다.

최대 2 arity의 부울 연산에 대한 진리표

상수 ${\displaystyle {}^{0}\!f_{0}}$ ${\displaystyle {}^{0}\!f_{1}}$ 0 1

단항 연산 ${\displaystyle x_{0}}$ ${\displaystyle {}^{1}\!f_{0}}$ ${\displaystyle {}^{1}\!f_{1}}$ ${\displaystyle {}^{1}\!f_{2}}$ ${\displaystyle {}^{1}\!f_{3}}$ 0 0 1 0 1 1 0 0 1 1

이진 연산 ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle {}^{2}\!f_{0}}$ ${\displaystyle {}^{2}\!f_{1}}$ ${\displaystyle {}^{2}\!f_{2}}$ ${\displaystyle {}^{2}\!f_{3}}$ ${\displaystyle {}^{2}\!f_{4}}$ ${\displaystyle {}^{2}\!f_{5}}$ ${\displaystyle {}^{2}\!f_{6}}$ ${\displaystyle {}^{2}\!f_{7}}$ ${\displaystyle {}^{2}\!f_{8}}$ ${\displaystyle {}^{2}\!f_{9}}$ ${\displaystyle {}^{2}\!f_{10}}$ ${\displaystyle {}^{2}\!f_{11}}$ ${\displaystyle {}^{2}\!f_{12}}$ ${\displaystyle {}^{2}\!f_{13}}$ ${\displaystyle {}^{2}\!f_{14}}$ ${\displaystyle {}^{2}\!f_{15}}$ 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

이러한 표는 n개의 행에서ⁿ 2개의 행으로 계속되며, 각 행은 n개의₀ 변수 x,...x의_n−1 값 또는 바인딩을 제공하고, 각 열 제목 f는_i 해당 값에서 i번째 n차 연산의 값 f_i(x₀,...,x_n−1)를 제공합니다.이 연산에는 변수가 포함됩니다. 예를 들어₂ f는₀ x이고₁₀ f는₀ x(단일 대응 변수의 두 복사본)이며 f는₁₂ x₁(단일 대응 변수 없음)입니다.음수 또는 보어 ¬x는 f로 나타나고 다시 f로 표시되며, f(1 arity에서 나타나지 않은 ¬x), 분리 또는 결합 x ∨x는 f, 접속 또는 교집합 x ∧x는 f, 의미 x→x는 f, 배타적 또는 대칭적 차이 x ⊕x는 f, 설정 차이 x-x는 f로 표시됩니다.

내용보다 형식에 더 중요한 사소한 세부 사항으로서 대수의 연산은 전통적으로 목록으로 구성됩니다.비록 우리가 여기서 부울 대수의 연산을 {0,1}에 대한 유한 연산으로 색인화하고 있지만, 위의 진리표 표현은 연산을 반복적으로 순서화하고 각 반복에 대한 표의 레이아웃으로 두 번째 순서를 정합니다.이를 통해 모든 부울 연산 집합을 기존 목록 형식으로 구성할 수 있습니다.특정 아리티의 작업에 대한 목록 순서는 다음 두 가지 규칙에 의해 결정됩니다.

(i) 표의 왼쪽 절반에 있는 i번째 행은 i의 이진법 표현으로, 왼쪽에 최하위 비트 또는 0번째 비트("little-endian" order", 원래 앨런 튜링이 제안한 것이므로 튜링 순서라고 하는 것이 무리는 아닐 것입니다.

(ii) 표의 오른쪽 절반에 있는 j번째 열은 j를 다시 리틀 엔디언 순서로 나타내는 이진법입니다.사실상 연산의 첨자는 해당 연산의 진리표입니다.계산 가능한 함수의 괴델 번호 부여와 유사하게 부울 연산의 이 번호 부여를 부울 번호 부여라고 부를 수 있습니다.

C나 자바로 프로그래밍할 때, 비트 와이즈 디스커넥션(bitwise disunction), 컨졍션(conjection), 네거티브(negation)로 표시됩니다. 따라서 프로그램은 연산 x ∧(y ∨z)를 이전에 설정한 , 그리고 (""는 16진수 또는 16진수로 다음 상수를 읽어야 함을 나타냅니다),변수에 할당되거나 매크로로 정의됩니다.이러한 1바이트(8비트) 상수는 위의 표를 3개의 변수로 확장한 입력 변수의 열에 해당합니다.이 기법은 래스터 그래픽스 하드웨어에서 거의 보편적으로 사용되어 이미지를 조합하고 마스킹하는 유연한 다양한 방법을 제공합니다. 일반적인 작업은 3원 작업이며 소스, 데스티네이션 및 마스크 비트에서 동시에 작동합니다.

예

비트 벡터

예 2.주어진 길이의 모든 비트 벡터는 부울 대수 "포인트와이즈"를 형성하며, 이는 n개의 부울 연산이 한 번에 하나의 비트 위치에 적용될 수 있음을 의미합니다.예를 들어, 각각의 길이 4의 비트 벡터 3개의 3진 OR은 각각의 4개의 비트 위치에서 3개의 비트를 오링함으로써 형성된 길이 4의 비트 벡터이므로, 0100 ∨1000 ∨1001 = 1101.또 다른 예는 n진 연산에 대한 위의 진리표인데, 열은 길이 2의ⁿ 모든 비트 벡터이므로 n진 연산이 부울 대수를 형성할 때 점별로 결합할 수 있습니다.^[9]이것은 유한한 길이와 무한한 길이의 비트 벡터에 대해서도 동일하게 잘 작동하며, 유일한 규칙은 "해당 위치"가 잘 정의되도록 비트 위치가 모두 동일한 집합으로 색인화된다는 것입니다.

그러한 대수의 원자는 정확히 하나의 1을 포함하는 비트 벡터입니다.일반적으로 부울 대수의 원자는 x ∧리가 x 또는 0의 두 가지 가능한 값만을 가지는 원소 x입니다.

멱집합 대수

예 3.멱집합 대수,^[10] 주어진 집합 W의 모든 부분집합의 집합^W 2.이것은 단지 W가 비트 위치들을 인덱싱하는 역할을 하는 위장된 예제 2일 뿐입니다.W의 임의의 부분 집합 X는 X의 요소에 의해 색인화된 비트 위치에서만 1을 갖는 비트 벡터로 볼 수 있습니다.따라서 올-제로 벡터는 W의 빈 부분 집합인 반면 올-원 벡터는 W 자체이며, 이는 각각 멱집합 대수의 상수 0과 1입니다.디스커넥션 x ∨리의 상대는 유니언 X ∪Y인 반면, 컨커넥션 x ∧리의 상대는 교차로 X ∩Y입니다.음의 ¬x는 ~X가 되며, W에 대하여 상보입니다.집합 차이 X\Y = X ∩~Y, 대칭 차이 (X\Y) ∪(Y\X), 3원 결합 X ∪Y ∪Z 등도 있습니다.여기 있는 원자들은 단 하나의 원소를 가진 부분집합입니다.

예제 2와 3은 직접곱이라 불리는 대수의 일반적인 구성의 특수한 경우로, 부울 대수뿐만 아니라 군, 고리 등을 포함한 모든 종류의 대수에도 적용할 수 있습니다.i가 일부 지수 집합 I(꼭 유한하거나 심지어 셀 수 있는 것은 아님)에_i 걸쳐 있는 부울 대수의 임의의 가군 B의 직접 곱은 i번째 원소가 B에서_i 가져온 모든 I-튜플(...x_i,...)로 구성된 부울 대수입니다.직접 곱의 연산은 각각의 좌표 내에서 작용하는 구성 대수의 대응 연산입니다. 특히 곱의 연산 f는_j n개의 튜플의 i번째 좌표에 있는 n개의 요소에 B의_i 연산 f를_j 적용하여 n개의 튜플에 대해 연산합니다.

이런 식으로 곱해지는 모든 대수들이 같은 대수 A일 때 우리는 직접 곱을 A의 직접 거듭제곱이라고 부릅니다.모든 32비트 비트 벡터의 부울 대수는 2로³² 표시된 32번째 거듭제곱으로 증가된 2요소 부울 대수 또는 32요소 집합의 거듭제곱 집합 대수입니다.모든 정수 집합의 부울 대수는 2입니다^Z.우리가 지금까지 보여준 모든 부울 대수는 2요소 부울 대수의 직접 거듭제곱으로, "전력 집합 대수"라는 이름을 정당화합니다.

표현정리

모든 유한 부울 대수는 어떤 멱집합 대수와 동형임을 알 수 있습니다.^[11]따라서 유한 부울 대수의 카디널리티(요소의 수)는 2의 거듭제곱, 즉 1,2,4,8,...,2ⁿ,...이는 유한 부울 대수를 멱집합 대수로 표현함으로써 유한 부울 대수의 본질에 대한 통찰력을 제공하기 때문에 표현 정리라고 불립니다.

이 표현 정리는 무한 부울 대수로 확장되지 않습니다. 모든 거듭제곱 집합 대수는 부울 대수이지만 모든 부울 대수가 거듭제곱 집합 대수와 동형일 필요는 없습니다.특히, 셀 수 없을 정도로 무한한 거듭제곱 집합 대수는 존재할 수 없지만(가장 작은 무한 거듭제곱 집합 대수는 자연수 집합들의 거듭제곱 집합 대수^N 2이며, 셀 수 없을 정도로 많은 무한 부울 대수들이 존재합니다).

멱집합 대수를 넘어서려면 다른 구성이 필요합니다.대수 A의 하위 대수는 A의 연산 하에서 닫힌 A의 모든 하위 집합입니다.부울 대수 A의 모든 하위 대수는 A 자체에 대한 위반을 구성하기 때문에 여전히 A의 방정식을 만족시켜야 합니다.따라서 부울 대수의 모든 하위 대수는 부울 대수입니다.^[12]

멱집합 대수의 부분대수는 집합의 장이라고 합니다. 이와 동등하게 집합의 장은 빈 집합과 W를 포함한 일부 집합 W의 부분 집합의 집합이며 W에 대해 유한 결합과 보 하에서 닫혀 있습니다(따라서 유한 교집합 아래에서도 마찬가지입니다).Birkhoff의 부울 대수에 대한 표현 정리[1935]는 모든 부울 대수는 집합의 장과 동형이라고 말합니다.이제 Birkhoff의 HSP 정리는 다음과 같이 말할 수 있습니다. 대수의 클래스 C의 방정식 이론의 모든 모델 클래스는 C의 대수의 직접 곱의 소대수의 동형 이미지입니다.일반적으로 H, S, P의 세 가지가 모두 필요합니다. 이 두 버크호프 정리 중 첫 번째 정리가 보여주는 것은 다양한 부울 대수의 특별한 경우에 동형으로 대체될 수 있다는 것입니다.따라서 Birkhoff의 일반적인 품종에 대한 HSP 정리는 Birkhoff의 다양한 부울대수에 대한 ISP 정리가 됩니다.

기타 예시

자연수 집합 X를 이야기할 때는 i가 X를 ∈하는 경우에만 x = 1인 비트의 수열로 보는 것이 편리합니다.이 관점은 모든 비트 시퀀스의 부울^N 대수를 만드는 멱집합 대수 2의 하위 대수를 더 쉽게 말할 수 있습니다.^[13]또한 열을 위에서 아래로 읽으면 비트 시퀀스가 되지만 동시에 해당 열로 표시되는 함수가 1로 평가되는 평가(표의 왼쪽 절반에 있는 변수에 대한 할당)의 집합으로 볼 수 있습니다.

예 4.궁극적으로 일정한 순서.궁극적으로 일정한 수열의 부울 조합은 궁극적으로 일정하므로 부울 대수를 형성합니다.우리는 궁극적으로 0인 수열을 음수가 아닌 이진수(순서의 비트 0이 하위 비트)로 보고 궁극적으로 1인 수열을 음수가 아닌 이진수(모두 1인 수열로 2의 보산 연산을 생각)로 봄으로써 정수와 이들을 식별할 수 있습니다.이것은 정수를 부울 대수로 만들고, 결합은 비트 단위 OR이고 보는 -x-1입니다.정수는 셀 수 있을 정도로 많으므로 이 무한 부울 대수는 셀 수 있습니다.원자는 두 개의 힘, 즉 1,2,4,...이 대수를 설명하는 또 다른 방법은 유한한 자연수 집합과 유한한 자연수 집합의 집합이며, 최종적으로 모든 것이 유한한 집합에 해당하며, 이 집합들은 유한한 자연수를 제외한 것입니다.

예 5.주기적인 순서.수열은 모든 i ≥ 0에 대하여 x = x가 되는 주기성의 증인이라고 불리는 어떤 수 n > 0이 존재할 때 주기성이라고 불립니다.주기적인 배열의 주기는 가장 적은 증거입니다.부정은 주기를 변경하지 않고 두 주기 수열의 분리는 주기적이며, 주기는 두 인수의 주기의 최소 공통 배수입니다(주기는 임의의 수열과 그 상보의 결합에서 발생하는 것처럼 1만큼 작을 수 있습니다).따라서 주기적인 수열은 부울 대수를 형성합니다.

예제 5는 셀 수 있다는 점에서는 예제 4와 비슷하지만 원자가 없다는 점에서는 다릅니다.후자는 공비 주기(1보다 큰) 수열과 0이 아닌 주기 수열 x의 결합이 0도 x도 아니기 때문입니다.셀 수 없이 무한한 원자가 없는 부울 대수는 모두 동형이며, 즉 동형이 될 때까지 그러한 대수는 하나뿐이라는 것을 알 수 있습니다.

예 6.주기가 2의 거듭제곱을 갖는 주기적인 수열.이것은 예제 5의 적절한 하위대수입니다(적절한 하위대수는 그 자체와 그 대수의 교집합입니다).이러한 작업은 최종 작업으로 이해될 수 있으며, 그러한 시퀀스의 첫 번째 주기는 작업의 진실 테이블을 제공합니다.예를 들어, 이진 연산의 표에서 x의₀ 진리표, 즉 f는₁₀ 기간 2를 갖지만(따라서 첫 번째 변수만 사용하는 것으로 인식될 수 있습니다), 이진 연산 중 12개는 기간 4를 갖습니다.기간이 2인ⁿ 경우 연산은 처음 n개의 변수, 즉 연산이 유한하다는 의미에만 의존합니다.이 예는 셀 수 없이 무한한 원자가 없는 부울 대수이기도 합니다.따라서 예제 5는 그 자체의 적절한 아대수와 동형입니다!예제 6과 이에 따라 예제 5는 셀 수 있을 정도로 많은 생성기에서 자유 부울 대수를 구성하며, 이는 셀 수 없을 정도로 무한한 생성기 또는 변수의 집합에 대한 모든 유한 연산의 부울 대수를 의미합니다.

예 7.궁극적으로 주기적인 시퀀스, 초기의 유한한 무법 상태 이후에 주기적으로 되는 시퀀스.상수 시퀀스는 주기 1과 함께 주기적이기 때문에 이들은 예제 5의 적절한 확장(예 5가 예제 7의 적절한 하위 대수임을 의미함)과 예제 4의 적절한 확장을 구성합니다.시퀀스는 언제 정착하는지에 따라 달라질 수 있지만 유한 집합의 시퀀스는 결국 모든 주기적 시퀀스가 모든 부울 연산에서 닫혀 부울 대수를 형성합니다.이 예는 예 4와 원자와 덮개가 동일하며, 원자가 없기 때문에 예 5/6과 동형이 아닙니다.그러나 무한 원자가 없는 하위 대수, 즉 예제 5를 포함하고 있으므로 예제 4와 동형이 아니며, 예제 4의 모든 하위 대수는 유한 집합과 그 상보로 이루어진 부울 대수여야 하며 따라서 원자입니다.이 예는 실시예 4 및 5의 직접 제품과 동형이며, 그에 대한 다른 설명을 제공합니다.

예 8.유한하지만 사소하지 않은 임의의 부울 대수를 갖는 주기 수열(예 5)의 직접적인 곱. (사소한 1요소 부울 대수는 유일한 유한 원자가 없는 부울 대수입니다.)이것은 원자와 원자가 없는 아대수를 모두 가지고 있다는 점에서 실시예 7과 유사하지만, 유한하게 많은 원자만을 가지고 있다는 점에서 차이가 있습니다.예제 8은 가능한 각 유한 개의 원자에 대해 하나의 예제의 무한 패밀리입니다.

이러한 예들은 결코 가능한 부울 대수들, 심지어 셀 수 있는 대수들을 다 소모하지 않습니다.실제로, Jussi Ketonen [1978]이 유전적으로 계산 가능한 집합으로 표현할 수 있는 불변량의 관점에서 완전히 분류한 비동형 계산 가능한 부울 대수는 셀 수 없이 많습니다.

부울 연산의 부울대수

n진 부울 연산 자체가 멱집합 대수 2를^W 구성하는데, 즉 W를 n개 입력의 2개의ⁿ 값의 집합으로 할 때입니다.이진법의 i가 진리표의 열인 연산 f의_i 명명 시스템의 관점에서, 이 열들은 임의의 배열의 부울 연산과 결합되어 표에 존재하는 다른 열들을 생성할 수 있습니다.즉, arity m의 부울 연산을 arity m의 부울 연산에 적용하여 임의의 m과 n에 대해 arity n의 부울 연산을 산출할 수 있습니다.

소프트웨어와 하드웨어 모두에 대한 이 규약의 실질적인 의미는 n진 부울 연산을 적절한 길이의 단어로 표현할 수 있다는 것입니다.예를 들어 256개의 3진 부울 연산 각각을 부호 없는 바이트로 나타낼 수 있습니다.그런 다음 AND 및 OR과 같은 사용 가능한 논리 연산을 사용하여 새로운 연산을 구성할 수 있습니다.x, y, z (지금은 첨자가 붙은 변수로 dispens링)를 각각 101010, 1100, 11110000 (십진수로 170, 204, 240, 0xaa, 0xcc, 0 xf0)으로 하면 쌍방향 접속은 x ∧리 = 10001000, y ∧z = 110000, z ∧x = 10100000이고 쌍방향 접속은 x ∨리 = 11101110, y ∨z = 111100,z ∨x = 11111010.세 접속사의 접속사는 11101000인데, 마침 세 접속사의 접속사이기도 합니다.따라서 바이트에 대한 십여 개의 논리 연산을 사용하여 두 개의 3차 연산을 계산했습니다.

${\displaystyle (x\landy)\lor (y\land z)\lor (z\land x)}$

그리고.

${\displaystyle (x\lory)\land (y\lor z)\land (z\lor x)}$

사실 같은 작업입니다즉, 우리는 등식적 정체성을 증명했습니다.

${\displaystyle (}$ ${\displaystyle x}$ ${\displaystyle \wedge }$ ${\displaystyle y}$ )${\displaystyle \vee (}$ ${\displaystyle y}$ ${\displaystyle \wedge }$ ${\displaystyle z}$ )${\displaystyle \vee (}$ ${\displaystyle z}$ ${\displaystyle \wedge }$ ${\displaystyle x}$) $=$ ${\displaystyle x}$ ${\displaystyle \vee }$ ${\displaystyle y}$ )${\displaystyle \wedge }$ ${\displaystyle (}$ ${\displaystyle y}$ ∨ ${\displaystyle z}$ )${\displaystyle \wedge (}$ ${\displaystyle z}$ ∨ ${\displaystyle x}$) ${\displaystyle (x\land$ y$)\lor (y\land z)\lor (z\lan$x)= ($x\lor z)\lor (z\lor x$

부울 대수 2개의 원소에 대하여.따라서 "부울 대수"의 정의에 따라 이 항등식은 모든 부울 대수에 성립해야 합니다.

이 3차 연산은 우연히 그라우의 [1947] 3차 부울 대수의 기초를 형성했고, 그는 이 연산과 부정의 관점에서 공리화했습니다.연산은 대칭이며, 이는 그 값이 인수의 3! = 6개의 순열과 독립적임을 의미합니다.진리표 11101000의 두 반은 ∨, 1110, ∧, 1000의 진리표이므로 연산은 z, x ∨y, 그 외 x ∧y와 같이 표현할 수 있습니다.대칭이므로 if x y ∨z else y ∧z 또는 y y이면 z ∨x else z 중 하나로 표현할 수 있습니다.8 꼭짓점 3-큐브의 레이블로 볼 때, 위쪽 반은 1, 아래쪽 반은 0으로 표시됩니다. 이러한 이유로 인해 홀수 변수에 대한 명백한 일반화와 함께 중위수 연산자라고 불립니다(정확히 반수 변수가 0일 때 동점을 피하기 위해 홀수).

부울대수 공리화

우리가 방금 부울 대수의 동일성을 증명하기 위해 사용한 기술은 부울 논리의 방정식 법칙에 대한 완전한 공리화 또는 완전한 공리화로 받아들여질 수 있는 체계적인 방식으로 모든 항등식에 일반화될 수 있습니다.공리계의 관습적 공식화는 일부 초기 항등식을 가진 "펌프"를 "프라임"하는 일련의 공리들과 공리들 및 이전에 증명된 항등식들로부터 나머지 항등식들을 추론하기 위한 일련의 추론 규칙들로 구성됩니다.원칙적으로 유한개의 공리를 가지는 것이 바람직하지만, 실제적인 문제로서 무한개의 인스턴스를 가지는 유한개의 공리 스키마를 가지는 것이 필요한 것은 아니며, 이는 증명에 사용될 때 각각이 법적 인스턴스임을 쉽게 증명할 수 있기 때문에 여기서 따르는 접근 방식입니다.

부울 항은 형태 = t의 주장이며, 여기서 변수가 x부터 x로 제한되는 항을 의미합니다. 부울 항은 원자 또는 응용 중 하나입니다.응용 프로그램 f_i(t₀,...,t_m-1)는 m-ary 연산 f와_i 피연산자라고 불리는 m-ary 항의 목록 또는 m-tuple(t₀,...,t_m-1)로 구성된 쌍입니다.

모든 항과 연관되는 것은 높이라고 불리는 자연수입니다.원자의 높이는 0인 반면 응용 프로그램의 높이는 1에 피연산자의 높이가 가장 높습니다.

원자란 무엇일까요?일반적으로 원자는 상수(0 또는 1)이거나 변수 x_i(0 ≤ i < n)입니다.여기서 증명 기법의 경우 n-ary 연산 f 대신_i 원자를 정의하는 것이 편리합니다. 비록 여기서 원자로 취급되지만, (반복_0n-1 또는 생략 없이 변수가 표시된 순서대로 나열되어야 한다는 점에서 정확합니다.) f의_i 일반적인 용어와 동일합니다.이 형태의 원자들은 일반적인 모든 원자들, 즉 상수 0과 1을 포함하기 때문에 이것은 제한이 아닙니다. 여기서 각각의 n(약칭 2-1²ⁿ~-1)에 대한 n-ary 연산₀ f와 f로₋₁ 발생합니다. 그리고 변수 x₀,...,x는_n-1 진리표에서 알 수 있듯이, x는₀ 단항 연산 f와₂ 이진 연산 f로₁₀ 나타나는 반면 x는₁ f로₁₂ 나타나는 것입니다.

다음 공리 스키마와 세 가지 추론 규칙은 n-ary 항의 부울 대수를 공리화합니다.

A1. f(f,...,f) = f 여기서 (io ĵ) = i이며, ĵ는 j 전치이며, (ĵ) = (j)로 정의됩니다.

R1. 전제가 없는 경우 추론 = t.

R2. s = u와 t = u에서 s, t, u가 n-항인 = t를 추론합니다.

R3. 모든 항이 n-ary인 s = t, ..., s = t 추론 f(s,...,s) = f(t,...,t)에서 시작합니다.

A1에서 측위 조건의 의미는 v-th 비트가 i의 ĵ 번째 비트인 2비트 수이며, 여기서 각 양의 범위는 u: m, v: 2, j: 2, ĵ: 2입니다. (따라서 j는 2비트 수의 m-튜플이고, j의 전치환이 m-비트 수의 2-튜플이기 때문에 ĵ는 2비트 수의 m-튜플입니다.따라서 j와 ĵ 모두 m2 비트를 포함합니다.)

a1은 m, i, n, j에서₀ j까지의_m-1 메타변수를 포함하는 덕택에 공리가 아닌 공리 스키마입니다.공리화의 실제 공리는 메타 변수를 특정 값으로 설정함으로써 얻어집니다.예를 들어, m = n = i = j = 1을 취하면 i = 0과 i = 1에서 두 비트의 io ĵ를 계산할 수 있으므로 io ĵ = 2(또는 2비트 숫자로 표기할 경우 10)를 계산할 수 있습니다.결과적인 예, 즉 f(f) = f는 이중 부정의 친숙한 공리 ¬¬x = x를 표현합니다.그러면 규칙 R3을 사용하면 s는 f(f) 또는 ¬x, t는 x, f는 ¬¬¬에 대한 것으로 ¬x = ¬¬x를 추론할 수 있습니다.

각 m과 n에 대해 A1을 인스턴스화하는 공리(2^2m × 2)가²ⁿ 유한하게 많습니다.^m각 인스턴스는 2^m+m2ⁿ 비트로 지정됩니다.

우리는 R1이 집단, 고리 또는 다른 종류의 모든 등식 공리화에 공통적인 R2 및 R3와 함께 도메인 독립 규칙이기 때문에 전제가 없는 공리와 같음에도 불구하고 추론 규칙으로 취급합니다.부울 대수에 특정한 유일한 개체는 공리 스키마 A1입니다.이러한 방법으로 다른 등식 이론에 대해 이야기할 때 우리는 규칙을 특정 이론과 독립적인 것으로 한쪽으로 밀어낼 수 있으며, 현재 당면한 특정 등식 이론을 특징짓는 공리계의 유일한 부분으로서 공리에 주의를 기울일 수 있습니다.

이 공리화는 완전하며, 이 체계에서 모든 부울 법칙 = t가 증명 가능하다는 것을 의미합니다.하나는 먼저 s의 높이에 대한 유도를 통해 원자가 되는 모든 부울 법칙이 증명 가능하다는 것을 보여줍니다. 기본 경우에 R1을 사용하고 유도 단계에 A1과 R3을 사용합니다.이 증명 전략은 원자를 산출하기 위해 s를 평가하는 재귀적 절차에 해당합니다.그런 다음 일반적인 경우에서 t가 응용 프로그램일 수 있을 때 = t를 증명하려면 s = t가 항등식이면 s와 t가 동일한 원자로 평가해야 한다는 사실을 이용하여 u라고 합니다.따라서 먼저 위와 같이 = u와 t = u를 증명하고, 즉 A1, R1, R3을 이용하여 평가하고, R2를 호출하여 = t를 추론합니다.

A1에서, n을 함수형 m→n으로, m을 응용 m(n)으로 본다면, i, j, ĵ, io ĵ를 i형의 함수로 재해석할 수 있습니다: (m→2)→2, j: m→((n→2)→2), ĵ: (n→2)→(m→2), io ĵ: (n→2)→2.그러면 A1의 정의 (io ĵ) = i는 (io ĵ)(v) = i(ĵ(v))로 번역되며, 즉 io ĵ은 i와 함수로 이해되는 ĵ의 구성으로 정의됩니다.따라서 A1의 내용은 기본적으로 구성되어야 할 용어 적용을 정의하는 것에 해당합니다. 모듈로는 유형이 구성에 적합하게 일치하도록 m-tuplej를 전환할 필요가 있습니다.이 구성은 앞서 언급한 Lawvere의 파워 세트 범주 및 그 기능 중 하나입니다.이런 식으로 우리는 부울 대수의 등식 이론으로서 해당 범주의 통근 다이어그램을 특정 구성 법칙의 논리적 표현으로서 A1의 등식 결과로 변환했습니다.

기저 격자구조

모든 부울 대수 B의 기본은 부분 순서 집합 또는 포셋(B,≤)입니다.부분 순서 관계는 x = x ∧리일 때 x ≤ y로 정의되거나 y = x ∨리일 때 동등하게 정의됩니다.부울 대수의 원소들의 집합 X가 주어졌을 때, X의 상한은 X의 모든 원소 x에 대하여 x ≤ y인 원소이고, X의 하한은 X의 모든 원소 x에 대하여 y ≤ x인 원소입니다.

X의 sup은 X의 최소 상한, 즉 X의 모든 상한보다 작거나 같은 X의 상한입니다.X의 (inf)는 X에 대한 가장 큰 하한입니다.x와 y의 sup은 항상 x ∨리인 부울 대수의 기본 포셋에 존재하며, 마찬가지로 그들의 inf도 존재합니다, 즉 x ∧리.빈 sup은 0(아래 요소)이고 빈 inf는 1(위)입니다.모든 유한 집합은 sup과 inf를 모두 갖는다는 것이 뒤따릅니다.부울 대수의 무한 부분 집합은 sup 및/또는 inf를 가질 수도 있고 그렇지 않을 수도 있습니다. 거듭제곱 집합 대수에서는 항상 그렇습니다.

원소의 모든 쌍 x,y가 sup과 inf 둘 다를 가지는 임의의 포셋(B,≤)을 격자라고 합니다.sup에는 x ∨리, inf에는 x ∧리라고 적습니다.부울 대수의 기본 포셋은 항상 격자를 형성합니다.격자는 x ∨(y ∨z) = (x ∧y) ∧(x ∧z)일 때 또는 x ∨(y ∧z) = (x ∨y) ∨(x ∧z)일 때 동등하게 분포한다고 합니다.부울 대수의 기본 포셋이 분포 격자를 형성하는 부울 대수의 법칙입니다.

바닥 원소가 0이고 꼭대기 원소가 1인 격자가 주어졌을 때, 원소들의 쌍 x,y는 x ∧리 = 0이고 x ∨리 = 1일 때 상보적이라고 불리고, 그리고 나서 우리는 y가 x의 상보적이라고 말하고 그 반대도 마찬가지입니다.위와 아래가 있는 분포 격자의 임의의 원소 x는 기껏해야 하나의 보어를 가질 수 있습니다.격자의 모든 원소가 상보체를 가질 때 그 격자는 상보체라고 불립니다.보형 분포 격자에서는 원소의 보형물이 항상 존재하고 유일하여 보형물이 단항 연산이 된다는 것을 알 수 있습니다.또한, 모든 상보적 분포 격자는 부울 대수를 형성하고, 반대로 모든 부울 대수는 상보적 분포 격자를 형성합니다.이것은 부울 대수의 대안적인 정의, 즉 보완된 분포 격자를 제공합니다.이 세 가지 성질은 각각 유한한 많은 방정식으로 공리화될 수 있으며, 여기서 이 방정식들은 부울 대수의 방정식 이론의 유한한 공리화를 구성합니다.

방정식 집합의 모든 모델로 정의된 대수의 클래스에서는 보통 클래스의 일부 대수가 클래스에 적합한 것보다 더 많은 방정식을 만족하는 경우가 있습니다.부울 대수의 클래스는 단일 예외를 제외하고 모든 부울 대수가 부울 항등식을 정확히 만족하고 더 이상 만족하지 않는다는 점에서 특이합니다.예외는 모든 방정식, 심지어 x = y도 반드시 만족시키는 1 element 부울 대수이며, 따라서 때때로 일관성 없는 부울 대수라고 불립니다.

부울 동형 사상

부울 동형 사상(Boolean homorphism)은 부울 대수 A,B 사이의 함수 h: A → B로, 모든 부울 연산 f:

$${\displaystyle h(^{m}\!f_{i}(x_{0},...,x_{m-1})={}^{m}\!f_{i}(h(x_{0},...,x_{m-1})}$$

부울 대수의 범주 부울은 모든 부울 대수와 그들 사이의 부울 동형 사상을 객체로 갖습니다.

2요소 부울 대수 2부터 모든 부울 대수까지 고유한 동형 사상이 존재하는데, 동형 사상은 두 상수를 보존해야 하며 2의 유일한 요소이기 때문입니다.이 성질을 가진 부울 대수를 초기 부울 대수라고 합니다.임의의 두 개의 초기 부울대수는 동형이므로 동형 2까지는 초기 부울대수임을 알 수 있습니다.

다른 방향에서는 부울 대수 B부터 2까지 많은 동형이 존재할 수 있습니다.이러한 동형화는 B를 1에 매핑된 요소와 0에 매핑된 요소로 분할합니다.전자로 구성된 B의 부분 집합을 B의 초필터라고 합니다.B가 유한할 때 그것의 울트라 필터는 원자와 짝을 짓습니다; 하나의 원자는 1에 매핑되고 나머지는 0에 매핑됩니다.따라서 B의 각 극초필터는 B의 원자와 그 위에 있는 모든 원소들로 구성되어 있습니다. 따라서 정확히 B의 원소의 절반이 극초필터에 있고, 원자만큼 많은 극초필터가 있습니다.

무한한 부울 대수의 경우 초필터의 개념이 상당히 더 섬세해집니다.원자보다 크거나 같은 원소들은 항상 울트라 필터를 형성하지만, 다른 많은 집합들도 마찬가지입니다. 예를 들어, 정수의 유한 집합과 유한 집합의 부울 대수에서, 유한 집합은 원자가 아님에도 불구하고 울트라 필터를 형성합니다.마찬가지로, 정수의 거듭제곱집합은 주어진 정수를 포함하는 모든 부분집합의 집합을 가진다; 정수 자체와 동일시될 수 있는 이러한 "표준" 울트라필터들이 셀 수 없이 많지만, 셀 수 없이 더 많은 "비표준" 울트라필터들이 있습니다.이들은 비표준 분석의 기초를 형성하며, 무한소 및 델타 함수와 같은 고전적으로 일관되지 않은 객체에 대한 표현을 제공합니다.

무한 확장

부울 대수의 기본적인 부분 순서에 대한 위의 절에서 sup과 inf의 정의를 떠올리십시오.완전한 부울 대수는 무한 부분 집합을 포함하여 sup과 inf를 모두 갖는 모든 부분 집합 중 하나입니다.Gaifman [1964]과 Hales [1964]는 무한한 자유 완전 부울 대수가 존재하지 않음을 독립적으로 보여주었습니다.이는 유한 연산이 있는 논리가 무한히 많은 항을 가질 수 있는 것처럼, 집합 크기의 유한 연산이 있는 논리도 클래스-다수 항을 가질 수 있음을 의미합니다.

그러나 무한 부울 연산을 도입하기 위한 또 다른 접근법이 있습니다: 단순히 부울 대수의 정의에서 "finitary"를 삭제하는 것입니다.{0,1}의 아리티에 대한 모든 연산에 대한 대수의 방정식 이론의 모델을 완전 원자 부울 대수, 또는 CABA라고 합니다. (아리티에 대한 이러한 어색한 제약을 대신하여 우리는 어떤 아리티도 허용할 수 있고, 이는 다른 어색함으로 이어질 수 있으며, 이는 기호가 어떤 집합보다 클 것이라는 것, 즉,제대로 된 수업후자의 접근 방식의 한 가지 이점은 서로 다른 카디널리티의 CABA 간의 동형화의 정의를 단순화한다는 것입니다.)이러한 대수는 원자인 완전한 부울 대수로 동등하게 정의될 수 있으며, 이는 모든 원소가 원자 집합의 합이라는 것을 의미합니다.자유 CABA는 생성기 집합 V의 모든 기수, 즉 멱집합 대수 2에^2V 대해 존재하며, 이는 유한 자유 부울 대수의 명백한 일반화입니다.이것은 가이프만의 운명으로부터 무한한 부울 논리를 깔끔하게 구출합니다.Hales 결과는 그것을 위탁한 것 같습니다.

자유 완전 부울 대수가 존재하지 않는 것은 부울 논리의 방정식을 무한의 접속과 접속을 유지해야 하는 모든 법칙, 특히 완전 부울 대수의 정의에서 분배성을 무시하는 것으로 적절하게 확장하지 못한 것으로 추적될 수 있습니다.완전한 부울 대수는 임의의 접속부가 임의의 접속부를 통해 분포하고 그 반대의 경우에는 완전한 분배라고 불립니다.부울 대수는 CABA의 세 번째 정의를 제공하는 완전하고 완전한 분포인 경우에만 CABA입니다.네 번째 정의는 멱집합 대수와 동형인 부울 대수와 같습니다.

완전한 동형 사상은 유한한 합뿐만 아니라 존재하는 모든 합을 보존하는 것입니다. 마찬가지로 inf.모든 CABA와 그들의 완전한 동형 사상의 범주 CABA는 집합과 그 함수의 범주에 이중이며, 이는 그것이 그 범주의 반대(모든 형태 사상을 뒤집는 결과의 범주)와 동일하다는 것을 의미합니다.마셜 스톤이 효과적으로 보여준 부울 대수의 범주 불과 그들의 동형 사상이 완전히 단절된 콤팩트 하우스도르프 공간, 이후 스톤 공간이라고 불리는 범주에 이중적인 것은 그렇게 간단하지 않습니다.

부울 대수와 완전 부울 대수 사이의 또 다른 무한 클래스는 시그마-대수의 개념입니다.이는 부울 대수를 완성하기 위해 유사하게 정의되지만 합과 정보는 가산성으로 제한됩니다.즉, 시그마 대수는 모든 계산 가능한 합과 inf를 갖는 부울 대수입니다.완전한 부울대수가 있는 상황과는 달리, 합과 inf는 유계 카디널리티이기 때문에, Gaifman-Hales 결과는 적용되지 않고 자유 시그마-대수가 존재합니다.그러나 CABA의 상황과는 달리, 자유롭게 계산 가능하게 생성된 시그마 대수는 멱집합 대수가 아닙니다.

부울 대수의 다른 정의

우리는 이미 부울 대수의 몇 가지 정의를 접했는데, 이 요소 대수의 방정식 이론의 모델로서, 보완된 분포 격자로서, 부울 링으로서, 그리고 특정 범주(Lawvere)의 곱 보존 함수로서입니다.언급할 가치가 있는 두 가지 정의는 다음과 같습니다.

스톤 (1936)

부울 대수는 위상 공간의 모든 닫힌집합의 집합입니다.공간을 완전히 단절된 콤팩트 하우스도르프 공간, 즉 스톤 공간, 즉 모든 부울 대수가 이러한 방식으로 동형화까지 발생하도록 요구하는 것은 제한이 없습니다.또한 두 개의 스톤 공간의 열린 집합으로 형성된 두 부울 대수가 동형인 경우 스톤 공간 자체도 마찬가지이며, 임의의 위상 공간의 경우에는 그렇지 않습니다.이것은 앞에서 언급한 부울 대수에서 스톤 공간까지의 이중성의 역방향일 뿐입니다.이 정의는 다음 정의에 의해 구체화됩니다.

존스톤 (1982)

부울 대수는 유한 부울 대수의 필터링된 콜로밋입니다.

(이 정의의 원형성은 "무한 부울 대수"를 멱집합에 대해 표준적으로 해석되는 부울 연산이 장착된 "무한 멱집합"으로 대체하여 제거할 수 있습니다.)

이를 관점에서 설명하자면, 무한 집합은 유한 집합의 필터링된 콜리밋으로, 무한 CABA는 유한 멱집합 대수의 필터링된 한계로, 무한 스톤 공간은 유한 집합의 필터링된 한계로 발생합니다.따라서 유한 집합에서 시작하여 무한 객체로 일반화하는 방법을 묻는다면 두 가지 방법이 있습니다. "더하기"는 일반 집합 또는 귀납 집합을 제공하는 반면 "더하기"는 스톤 공간 또는 귀납 집합을 제공합니다.유한 집합 대수에 대해서는 유한 집합의 이중과 동일한 선택이 존재합니다. 덧셈은 유도 객체로 부울 대수를 산출하고 곱셈은 CABA 또는 멱집합 대수를 비유의 객체로 산출합니다.

특징적인 특징은 하우스도르프(Hausdorff)로 정의될 때 구성된 객체의 기본 토폴로지가 귀납적 객체에 대해서는 이산적이고 유익한 객체에 대해서는 콤팩트하다는 것입니다.유한 하우스도르프 공간의 위상은 항상 이산적이고 콤팩트한 반면, 무한 공간의 경우 "이산적"과 "콤팩트"는 상호 배타적입니다.따라서 유한 대수(부울 뿐만 아니라 어떤 종류의 것이든)를 무한 대수로 일반화할 때 "이산" 및 "콤팩트" 부분 회사를 선택해야 합니다.유한대수와 무한대수 모두에 대한 일반적인 규칙은 유한대수는 이산인 반면 이중은 콤팩트하고 무한 연산이 특징이라는 것입니다.이 두 극단 사이에는 위상이 이산적이지도 않고 콤팩트하지도 않은 중간 무한 부울 대수가 많이 있습니다.

참고 항목

참고문헌

• Birkhoff, Garrett (1935). "On the structure of abstract algebras". Proc. Camb. Phil. Soc. 31 (4): 433–454. Bibcode:1935PCPS...31..433B. doi:10.1017/s0305004100013463. ISSN 0008-1981. S2CID 121173630.
• Boole, George (2003) [1854]. An Investigation of the Laws of Thought. Prometheus Books. ISBN 978-1-59102-089-9.
• Dwinger, Philip (1971). Introduction to Boolean algebras. Würzburg: Physica Verlag.
• Gaifman, Haim (1964). "Infinite Boolean Polynomials, I". Fundamenta Mathematicae. 54 (3): 229–250. doi:10.4064/fm-54-3-229-250. ISSN 0016-2736.
• Givant, Steven; Halmos, Paul (2009). Introduction to Boolean Algebras. Undergraduate Texts in Mathematics. Springer. ISBN 978-0-387-40293-2.
• Grau, A.A. (1947). "Ternary Boolean algebra". Bull. Am. Math. Soc. 33 (6): 567–572. doi:10.1090/S0002-9904-1947-08834-0.
• Hales, Alfred W. (1964). "On the Non-Existence of Free Complete Boolean Algebras". Fundamenta Mathematicae. 54: 45–66. doi:10.4064/fm-54-1-45-66. ISSN 0016-2736.
• Halmos, Paul (1963). Lectures on Boolean Algebras. van Nostrand. ISBN 0-387-90094-2.
• Givant, Steven; Halmos, Paul (1998). Logic as Algebra. Dolciani Mathematical Exposition. Mathematical Association of America. ISBN 978-0-883-85327-6.
• Johnstone, Peter T. (1982). Stone Spaces. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-33779-3.
• Ketonen, Jussi (1978). "The structure of countable Boolean algebras". Annals of Mathematics. 108 (1): 41–89. doi:10.2307/1970929. JSTOR 1970929.
• Koppelberg, Sabine (1989) "부울대수의 일반이론" Monk, J. Donald, 그리고 Bonna, Robert, eds., Boolean Algebars 핸드북, Vol. 1. North Holland.ISBN 978-0-444-70261-6.
• Peirce, C. S. (1989) Charles S.의 글 피어스: 연대기 편: 1879-1884. 클로젤, C.J.W., ed.인디애나폴리스:인디애나 대학 출판부.ISBN 978-0-253-37204-8.
• Lawvere, F. William (1963). "Functorial semantics of algebraic theories". Proceedings of the National Academy of Sciences. 50 (5): 869–873. Bibcode:1963PNAS...50..869L. doi:10.1073/pnas.50.5.869. PMC 221940. PMID 16591125.
• Schröder, Ernst (1890–1910). Vorlesungen über die Algebra der Logik (exakte Logik), I–III. Leipzig: B.G. Teubner.
• Sikorski, Roman (1969). Boolean Algebras (3rd. ed.). Berlin: Springer-Verlag. ISBN 978-0-387-04469-9.
• Stone, M. H. (1936). "The Theory of Representation for Boolean Algebras". Transactions of the American Mathematical Society. 40 (1): 37–111. doi:10.2307/1989664. ISSN 0002-9947. JSTOR 1989664.
• 타르스키, 알프레드 (1983).논리학, 의미론, 메타수학, 코코란, J., ed.해켓. 1956년 초판 편집, J. H. 우저 옮김, 옥스포드 대학누르다.다음 두 기사의 영어 번역 포함:
  • Tarski, Alfred (1929). "Sur les classes closes par rapport à certaines opérations élémentaires". Fundamenta Mathematicae. 16: 195–97. ISSN 0016-2736.
  • Tarski, Alfred (1935). "Zur Grundlegung der Booleschen Algebra, I". Fundamenta Mathematicae. 24: 177–98. doi:10.4064/fm-24-1-177-198. ISSN 0016-2736.
• Vladimirov, D.A. (1969). булевы алгебры (Boolean algebras, in Russian, German translation Boolesche Algebren 1974). Nauka (German translation Akademie-Verlag).

참고문헌