부울 대수

Boolean algebra

수학과 수학 논리학에서 부울 대수는 대수학의 한 분야입니다.초등 대수와는 두 가지 점에서 차이가 있습니다.첫째, 변수의 값은 참값거짓값이며, 일반적으로 1과 0으로 표시되는 반면, 기본 대수에서는 변수의 값이 숫자입니다.둘째, 부울 대수는 접속사(그리고)가 ∧로 표시되고, 접속사(또는)가 ∨로 표시되고, 부정사(아니)가 ¬로 표시되는 논리 연산자를 사용합니다.그러나 초등 대수학은 덧셈, 곱셈, 뺄셈, 나눗셈과 같은 산술 연산자를 사용합니다.따라서 부울 대수는 기본 대수가 수치 연산을 설명하는 것과 같은 방식으로 논리 연산을 설명하는 형식적인 방식입니다.

부울 대수학은 조지 부울에 의해 그의 첫 번째논리학[1] 수학적 분석(1847)에서 소개되었고, 그의 사고법칙의 조사(1854)[2]에서 더 자세히 설명되었습니다.헌팅턴에 따르면, "부울 대수"라는 용어는 헨리 M에 의해 처음 제안되었습니다. 1913년에 비록 찰스 샌더스 피어스가 1880년에 [4]그의 "가장 단순한 수학"의 첫 장에 "상수가 하나인 불리언 대수"라는 제목을 주었지만,[3] 셰퍼는 1913년에 "가장 단순한 수학"이라는 제목을 붙였습니다.부울 대수는 디지털 전자공학의 발전에 있어서 기본적인 역할을 해왔고, 모든 현대 프로그래밍 언어에서 제공됩니다.집합 이론 및 [5]통계학에서도 사용됩니다.

역사

부울 대수의 선구자는 고트프리트 빌헬름 라이프니츠개념 대수였습니다.아이칭과 관련된 이진법의 사용은 라이프니츠의 특징인 보편성의 중심이었습니다.그것은 결국 [6]개념의 대수학의 기초를 만들었습니다.라이프니츠의 개념 대수는 집합의 부울 [7]대수와 연역적으로 동등합니다.

부울의 대수학은 추상 대수학과 수학적 논리학의 현대적 발전보다 앞섰지만, 두 [8]분야의 기원과 관련이 있는 것으로 여겨집니다.추상적인 환경에서 부울 대수는 19세기 후반에 Jevons, Schröder, Huntington 등에 의해 현대적인 수학적 [8]구조 개념에 도달할 때까지 완성되었습니다.예를 들어, 집합의 대수식을 부울 대수식으로 변환함으로써, 집합의 대수식을 조작할 수 있다는 경험적 관찰은, 집합의 대수식은 부울 대수식이라고 함으로써 현대 용어로 설명됩니다.사실, M. H. 스톤은 1936년에 모든 부울 대수가 집합과 동형이라는 것을 증명했습니다.

1930년대에, 클로드 섀넌은 스위칭 회로를 연구하면서 부울의 대수의 법칙을 [9]이 환경에서도 적용할 수 있음을 관찰했고, 는 논리 게이트 측면에서 대수적인 방법으로 회로를 분석하고 설계하는 방법으로 스위칭 대수적 방법으로 회로를 분석하고 설계하는 방법으로 스위칭 대수를 도입했습니다.섀넌은 이미 추상적인 수학적 장치를 마음대로 가지고 있었기 때문에 그는 그의 스위칭 대수를 2요소 부울 대수로 주조했습니다.현대 회로 공학 환경에서는 다른 부울 대수를 고려할 필요가 거의 없기 때문에 종종 "스위칭 대수"와 "부울 대수"가 [10][11][12]혼용됩니다.

부울 함수의 효율적인 구현은 조합 논리 회로 설계의 근본적인 문제입니다.VLSI 회로를 위한 최신 전자 설계 자동화 도구는 논리 합성 및 형식 [13]검증을 위해 BDD(Binary Decision Diagram)로 알려진 부울 함수의 효율적인 표현에 의존하는 경우가 많습니다.

고전 명제 미적분학으로 표현할 수 있는 논리 문장은 부울 대수학에서 동등한 표현을 갖습니다.따라서 이러한 방식으로 수행되는 명제 [14][15][16]연산을 나타내기 위해 부울 논리가 사용되기도 합니다.부울 대수는 1차 논리식과 같은 한정자를 사용하여 논리식을 캡처하기에 충분하지 않습니다.

수학적 논리학의 발전이 불의 프로그램을 따르지는 않았지만, 그의 대수학과 논리학의 연결은 나중에 많은 [8]다른 논리학의 대수적 체계를 연구하는 대수적 논리학의 설정에서 확고한 기반 위에 놓이게 되었습니다.주어진 부울(명제) 공식의 변수들이 그 공식이 참으로 평가되도록 하는 방식으로 할당될 수 있는지를 결정하는 문제는 부울 만족도 문제(SAT)라고 불리며 NP-완전인 것으로 나타난 첫 번째 문제로서 이론 컴퓨터 과학에 중요합니다.부울 회로(Boolean circuit)로 알려진 계산의 밀접한 관련 모델은 (알고리즘의) 시간 복잡도회로 복잡도를 연관시킵니다.

가치

식들은 주로 기초 대수학에서 숫자를 나타내지만, 부울 대수학에서는 진리값거짓과 참임을 나타냅니다.이러한 값은 비트 0과 1로 표시됩니다.이들은 1 + 1 = 2인 정수 0과 1처럼 행동하지 않지만, 2변수 필드 GF(2), 1 + 1 = 0인 정수 산술 모듈로 2의 요소와 동일시될 수 있습니다. 덧셈과 곱셈은 각각 XOR(배타-or)와 AND(연결)의 부울 역할을 분배 x ∨ y(π-o)로 수행합니다.r) x + y - xy로 정의할 수 있고 부정 ¬x 1 - x 정의할 수 있습니다. GF(2)에서 -는 동일한 연산을 나타내기 때문에 +로 대체될 수 있습니다. 그러나 이러한 부울 연산 표기 방식은 정수의 일반적인 산술 연산을 적용할 수 있습니다(이것은 GF(2)가 구현되지 않은 프로그래밍 언어를 사용할 때 유용합니다).

부울 대수는 또한 그 값이 집합 {0, 1}에 있는 함수들을 다룹니다.비트 시퀀스는 이러한 함수에 일반적으로 사용됩니다.또 다른 일반적인 예는 집합 E의 부분 집합입니다. E의 부분 집합 F에 대해 F의 1과 F 외부의 값 0을 취하는 지시 함수를 정의할 수 있습니다.가장 일반적인 예는 부울 대수의 요소이며, 앞서 설명한 모든 요소가 그 예입니다.

기본 대수와 마찬가지로,[17] 이론의 순수 등식 부분은 변수에 대한 명시적인 값을 고려하지 않고 개발될 수 있습니다.

작전

기본작업

부울 대수의 기본 연산은 접속, 접속, 접속, 부정입니다.이러한 부울 연산은 해당하는 이진 연산자(AND OR)와 단항 연산자(NOT)로 표현되며, 이를 통칭하여 부울 [18]연산자라고 합니다.

변수 x와 y에 대한 기본 부울 연산은 다음과 같이 정의됩니다.

또는 x∧y, xy 및 ¬x의 값은 다음과 같이 진리표를 사용하여 값을 표시할 수 있습니다.

참값 0과 1을 정수로 해석할 경우, 이러한 연산은 산술의 일반 연산(x + y는 덧셈을 사용하고 xy는 곱셈을 사용함) 또는 최소/최대 함수로 나타낼 수 있습니다.

부정과 접속의 관점에서 접속을 정의할 수 있는 다음과 같은 동일성 때문에 부정과 다른 두 연산 중 하나만 기본이라고 생각할 수 있습니다(드 모르간의 법칙).

2차 작업

기본 연산으로 구성된 연산에는 다음과 같은 예가 있습니다.

소재 조건:
재질 이중 조건:
배타적 논리합(XOR):

이러한 정의는 가능한 네 가지 입력에 대한 이러한 연산 값을 제공하는 다음과 같은 진리표를 생성합니다.

부차적인 작전.
0 0 1 0 1
1 0 0 1 0
0 1 1 1 0
1 1 1 0 1
재질조건
첫 번째 연산인 xy 또는 Cxy물질적 의미라고 합니다.x가 참이면 x → y의 결과를 y의 결과로 만듭니다(예: x가 이고 y가 거짓이면 x → y거짓입니다).그러나 x가 false이면 y 이 무시될 수 있지만 연산은 일부 부울 값을 반환해야 하며 두 가지 선택 사항만 있습니다.따라서 정의상 x가 거짓일 때 xy입니다.(논리적논리는 잘못된 전제를 가진 암시를 참 또는 거짓이 아닌 다른 것으로 간주함으로써 이 정의를 제시합니다.)
배타적 논리합(XOR)
두 번째 연산인 xy 또는 Jxy는 배타적 또는 (종종 XOR로 약칭됨) 포괄적인 종류로서의 분리와 구별하기 위해 배타적 또는 (exclusive)이라고 불립니다.x와 y모두 참일 가능성을 배제합니다(예: 표 참조). 둘 다 참이면 결과는 거짓입니다.산술적으로 정의하면 mod 2가 1 + 1 = 0일 때 덧셈입니다.
논리적 동치
세 번째 연산인 exclusive or의 보어는 동치 또는 부울 동치입니다. xy 또는 Exyx와 y가 같은 값을 가질 참입니다.따라서 x ⊕ y는 그것의 보어로서 x ≠ y로 이해될 수 있으며, x와 y가 다를 때만 참입니다.따라서 산술 모드 2에서 동치의 상대는 x + y 이고, 산술 모드 2에서 동치의 상대는 x + y + 1 입니다.

법칙들

부울 대수의 법칙은 두 부울 항 사이의 x ∨ (yz) = (xy)z같은 동일성입니다. 여기서 부울 항은 연산 ∧, ∨, ¬를 사용하여 변수와 상수 0과 1로 구성된 식을 정의합니다.이 개념은 ⊕, → 및 ≡와 같은 다른 부울 연산을 포함하는 용어로 확장될 수 있지만, 이러한 확장은 법이 적용되는 목적에는 불필요합니다.이러한 목적에는 부울 법칙의 임의의 모델로서 부울 대수의 정의, 그리고 y ∧ z = zy에서 x § (y ∨ z) = x ∨ (zy)의 유도에서와 같이 구로부터 새로운 법칙을 유도하기 위한 수단으로서(∧ axi Axiomatizing Boolean 대수에서 처리됨).

단조법칙

부울 대수는 ∨를 덧셈과 일치시키고 ∧를 곱셈과 일치시킬 때 일반 대수와 같은 많은 법칙을 만족시킵니다.특히 다음 법칙들은 두 종류의 [19][20]대수에 공통적으로 적용됩니다.

연관성:
}의연관성:
교환성:
}의교환성:
}에 대한의 분포도:
의 ID
}의 ID [NB 1]
}에대한 소멸기:

다음 법칙들은 부울 대수에서는 성립하지만 일반 대수에서는 성립하지 않습니다.

대한 소멸기: [NB 1]
아이엠포텐셜:
}의동일한 효력:
흡수 1:
흡수 2:
에 대한 ∨ {\의 분포도:

위의 세 번째 법칙에서 x = 2취하면 2 × 2 = 4이므로 일반적인 대수 법칙이 아님을 알 수 있습니다.나머지 5개의 법칙은 모든 변수를 1로 함으로써 일반 대수학에서 위조될 수 있습니다.예를 들어, 흡수법 1에서, 왼손 측은 1(1 + 1) = 2인 반면, 오른손 측은 1(등)인 것입니다.

지금까지 다루어진 모든 법은 접속과 접속을 위한 것이었습니다.이러한 연산은 하나의 인수를 변경하면 출력이 변경되지 않거나 입력과 동일한 방식으로 출력이 변경되는 속성이 있습니다.이와 동일하게 변수를 0에서 1로 변경해도 출력이 1에서 0으로 변경되지 않습니다.이 속성을 가진 작업은 단조로운 작업이라고 합니다.따라서 지금까지의 공리는 모두 단조 부울 논리에 대한 것이었습니다.다음과 같이 보어 ¬를 통해 비단조성이 들어갑니다.

논모노톤 법칙

보완작업은 다음 두 가지 법칙에 의해 정의됩니다.

[NB 1]

아래의 법칙을 포함한 모든 부정의 성질은 위의 두 법칙에서만 [5]따르게 됩니다.

보통 대수와 부울 대수 모두에서, 부정은 원소의 쌍을 교환함으로써 작용하며, 여기서 두 대수 모두에서 이중 부정 법칙을 만족합니다.

하지만 보통의 대수는 두 법칙을 만족시키는 반면에

부울 대수는 드 모르간의 법칙을 만족합니다.

완성도

위에 나열된 법칙들은 주제의 나머지 부분을 수반한다는 의미에서 부울 대수를 정의합니다.보법 1과 2는 단조 법칙과 함께 이러한 목적으로 충분하며, 따라서 가능한 완전한 법칙 집합 또는 부울 대수의 공리화로 간주될 수 있습니다.부울 대수학의 모든 법칙은 이 공리들로부터 논리적으로 따릅니다.또한, 부울대수는 § 부울대수에서 처리된 것처럼 이러한 공리의 모델로 정의될 수 있습니다.

명확하게 설명하자면, 부울 대수의 추가 법칙을 적는 것은 이러한 공리들의 새로운 결과를 낳을 수 없고, 또한 그들의 어떤 모델도 배제할 수 없습니다.이와는 대조적으로, 동일한 법칙들이 아닌 일부 법칙들의 목록에서, 목록의 법칙들로부터 따르지 않는 부울 법칙들이 존재할 수 있었고, 게다가 부울 대수가 아닌 나열된 법칙들의 모델들이 존재했을 것입니다.

이 공리화는 우리가 일부 공리가 다른 공리들로부터 따랐는지에 관심을 기울이지 않았고 단순히 우리가 충분한 법칙을 가지고 있다는 것을 알아차렸을 때 멈추기로 선택했다는 점을 고려할 때 결코 유일한 것은 아니며, 심지어 가장 자연스러운 것이기도 합니다. 부울 대수 공리화에서 더 자세히 다루어집니다.또는 [21][22]0과 1을 넘는 변수의 모든 값에 대해 성립하는 방정식으로 이해되는 부울 법칙을 직접 임의의 토우톨로지로 정의함으로써 공리의 중간 개념을 완전히 회피할 수 있습니다.부울 대수의 이러한 정의들은 모두 동치임을 보여줄 수 있습니다.

이중성 원리

원칙:{X,R}이(가) 부분 순서 집합이면 {X,R(inverse)}도 부분 순서 집합입니다.

부울 대수의 값에 대한 기호 선택에 마법 같은 것은 없습니다.우리는 α와 β를 말하기 위해 0과 1의 이름을 바꿀 수 있으며, 우리가 그렇게 일관성 있게 하는 한, 비록 명백한 외관상의 차이가 있기는 하지만 여전히 부울 대수일 것입니다.

그러나 0과 1을 각각 1과 0으로 이름을 바꾼다고 가정합니다.그러면 여전히 부울 대수이고, 더 나아가 동일한 값에 대해 연산할 수 있습니다.그러나 그것은 우리의 원래 부울 대수와 동일하지 않을 것입니다. 왜냐하면 이제 우리는 ∧가 하던 방식으로 행동하는 것을 발견하고 그 반대도 마찬가지이기 때문입니다.따라서 0과 1을 사용하고 있음에도 불구하고 표기법을 만지작거리고 있다는 것을 보여주는 미용적 차이가 여전히 존재합니다.

그러나 값의 이름을 바꾸는 것 외에 두 이진 연산의 이름도 바꾼다면, 이제 우리가 한 일의 흔적이 없습니다.최종 제품은 우리가 시작한 것과 전혀 구분이 안 됩니다.우리는 진리표의 x ∧ y 열과 x ∨ y 이 바뀐 것을 알아차릴 수 있지만, 그 스위치는 중요하지 않습니다.

값과 연산이 모든 쌍이 동시에 전환될 때 중요한 모든 것을 변하지 않는 방식으로 쌍을 이룰 수 있을 때, 우리는 각 의 구성원을 서로 이중이라고 부릅니다.따라서 0과 1은 이중이고, π와 π는 이중입니다.De Morgan duality라고도 불리는 이중성 원리는 모든 이중 쌍이 서로 바뀔 때 부울 대수는 변하지 않는다고 주장합니다.

이 교환의 일부로서 우리가 할 필요가 없었던 한 가지 변화는 보완하는 것이었습니다.우리는 보완이 자기 이중적인 작업이라고 말합니다.identity 또는 do-nothing 작업 x(입력을 출력에 복사)도 self-dual입니다.자기 이중 연산의 더 복잡한 예는 (x y) ∨ (yz) ∨ (zx)입니다.두 인수 모두에 의존하는 자체 이중 이진 연산은 없습니다.자기 이중 연산의 구성은 자기 이중 연산입니다.예를 들어, f(x, y, z) = (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x)라면, f(f(x, y, z), x, t)는 4개인수 x, y, z, t의 셀프 계산 연산입니다.

이중성의 원리는 자신에게 돌아오는 부울 다항식 집합의 일대일 매핑(자동형성)인 항등식 함수, 상보 함수, 이중 함수, 모순 함수(상보 이중)의 정확히 4개의 함수가 있다는 사실로 집단 이론 관점에서 설명될 수 있습니다.이 4개의 함수는 부울 다항식 집합에 작용하는 클라인 4개의 그룹과 동형인 함수 구성 하그룹을 형성합니다.월터 고트샬크는 결과적으로 현상에 더 적합한 이름은 4차성의 [5]: 21–22 원리(또는 제곱)일 것이라고 말했습니다.

도식 표현

벤 다이어그램

Venn[23] 다이어그램은 음영 처리된 중첩 영역을 사용하는 부울 연산의 표현으로 사용할 수 있습니다.각 변수에 대해 하나의 영역이 있으며, 여기 예제에서는 모두 원형입니다.영역 x의 내부와 외부는 변수 x의 값 1(참)과 0(거짓)에 각각 해당합니다.음영은 영역의 각 조합에 대한 연산 값을 나타내며 어두운 색은 1을 나타내고 빛은 0을 나타냅니다(일부 저자는 반대되는 규칙을 사용함).

아래 그림의 세 개의 벤 다이어그램은 각각 접속 xy, 접속 x∨y, 보 ¬x를 나타냅니다.

그림 2.접속, 접속, 접속 및 보체를 위한 벤 다이어그램

결합의 경우 두 원 내부의 영역에 음영이 발생하여 두 변수가 모두 1일 때 x∧y1임을 나타냅니다.다른 영역은 다른 세 가지 조합에 대해 x∧y가 0임을 나타내기 위해 음영으로 유지됩니다.

두 번째 다이어그램은 원 안에 있는 영역을 음영으로 표시하여 분리 x∨y를 나타냅니다.세 번째 다이어그램은 원 내부가 아닌 영역에 음영을 줌으로써 보 ¬x를 나타냅니다.

상수 0과 1에 대한 벤 다이어그램을 보여주지는 않았지만, 그것들은 각각 흰색 상자와 어두운 상자이며, 둘 다 원을 포함하지 않습니다.그러나 우리는 그 상자들에 x에 대한 원을 넣을 수 있었고, 이 경우 각각은 상수 함수라고 불리는 x와 독립적으로 같은 값을 반환하는 하나의 인수의 함수를 나타낼 것입니다.출력에 관한 한 상수와 상수 함수는 구별할 수 없습니다. 다른 점은 상수는 영항 연산 또는 영항 연산이라 불리는 인수를 취하지 않는 반면 상수 함수는 인수 하나를 취하는데 이는 무시되며 단항 연산입니다.

벤 다이어그램은 법칙을 시각화하는 데 도움이 됩니다.π와 π에 대한 교환성 법칙은 다이어그램의 대칭성에서 알 수 있습니다. x와 y교환하면 다이어그램을 수평으로 반영하는 효과가 있고 교환성의 실패는 대칭성의 실패로 나타날 수 있기 때문에 교환성이 없는 이진 연산은 대칭성을 갖지 않을 것입니다.

발기부전은 두 원을 함께 미끄러뜨리고 음영이 있는 영역이 모두에 대해 전체 원이 된다는 것에 주목하여 시각화할 수 있습니다.

첫 번째 흡수 법칙인 x∧(xy) = x를 보려면 x∨y대한 중간 다이어그램에서 시작하여 음영이 있는 영역에서 x 원과 공통인 부분이 x 원 전체임을 유의하십시오.두 번째 흡수 법칙인 x∨(xy) = x의 경우 x∧y대한 왼쪽 다이어그램에서 시작하여 이전 음영이 x원 안에 있었기 때문에 x원 전체에 음영이 발생한다는 것에 유의하십시오.

이중부정법칙은 x 을 음영화하는 λx에 대한 세 번째 도표의 음영을 보완함으로써 알 수 있습니다.

첫 번째 De Morgan 법칙인 (¬x) ∧(¬y) = ¬(x∨y)를 시각화하려면 x∨y대한 중간 다이어그램에서 시작하여 두 원 밖의 영역만 음영이 발생하도록 음영을 보완합니다. 이것이 법칙의 오른쪽에서 설명하는 것입니다.결과는 마치 우리x원의 바깥쪽과 y원의 바깥쪽에 있는 영역, 즉 그들의 외부와의 연결, 즉 법칙의 왼쪽이 설명하는 것과 같습니다.

두 번째 De Morgan의 법칙인 (¬x) ¬(∧y) = ¬(xy)는 두 도표가 서로 교환된 상태에서 동일한 방식으로 작동합니다.

첫 번째 보법 법칙인 x∧¬x = 0은 x 원의 내부와 외부가 겹치지 않는다고 말합니다.두 번째 보법인 x∨¬x = 1은 모든 것이 x 원 안에 있거나 밖에 있다고 말합니다.

디지털 논리 게이트

디지털 로직은 회로 다이어그램을 형성하기 위해 연결된 로직 게이트로 구성된 전자 하드웨어에 0과 1의 부울 대수를 적용하는 것입니다.각 게이트는 부울(Boolean) 연산을 구현하며, 연산을 나타내는 모양으로 개략적으로 표시됩니다.연결용 게이트(AND-gate), 연결용 게이트(Disunction), 연결용 게이트(OR-gate) 및 보체(Inverter)와 관련된 형상은 [24]다음과 같습니다.

왼쪽에서 오른쪽으로: AND, OR, NOT 게이트.

각 게이트의 왼쪽에 있는 선은 입력 와이어 또는 포트를 나타냅니다.입력 값은 리드의 전압으로 표시됩니다.소위 "active-high" 로직의 경우 0은 0 또는 "ground"에 가까운 전압으로 표시되는 반면, 1은 공급 전압에 가까운 전압으로 표시되며, active-low는 이를 반전시킵니다.각 게이트의 오른쪽에 있는 선은 출력 포트를 나타내며, 출력 포트는 일반적으로 입력 포트와 동일한 전압 규칙을 따릅니다.

인버터 게이트로 보체를 구현합니다.삼각형은 단순히 입력을 출력에 복사하는 연산을 나타내며, 출력의 작은 원은 입력을 보완하는 실제 반전을 나타냅니다.이러한 원을 포트에 배치하는 관례는 입력 포트든 출력 포트든 간에 이 포트를 통과하는 신호가 통과하는 과정에서 보완됨을 의미합니다.

Duality Principle, 즉 De Morgan의 법칙은 아래 그림 4와 같이 AND 게이트의 세 개의 포트를 모두 보완하여 OR 게이트로 변환하고 그 반대의 경우도 마찬가지임을 주장하는 것으로 이해할 수 있습니다.그러나 인버터의 두 포트를 모두 보완하면 동작은 변경되지 않습니다.

일반적으로 하나는 AND 또는 OR 게이트의 세 포트의 8개 부분 집합 중 하나를 보완할 수 있습니다.결과적으로 16개의 가능성은 단지 8개의 부울 연산, 즉 진리표에서 홀수가 1인 연산만을 발생시킵니다."홀수 비트 아웃"이 0 또는 1일 수 있고 진리표의 네 위치 중 어느 하나에 있을 수 있기 때문에 8가지가 있습니다.16개의 이진 부울 연산이 있으므로 8개의 연산과 짝수 개의 1을 진리표에 남겨야 합니다.이 중 두 개는 상수 0과 1입니다(두 개의 입력을 모두 무시하는 이진 연산으로). 네 개는 두 개의 입력(x, y, σx, σy) 정확히 하나에 크게 의존하지 않는 연산이며 나머지 두 는 x⊕y(XOR)와 그 보어 x≡y입니다.

부울대수

"대수"라는 용어는 주어, 즉 대수학의 주제와 대상, 즉 대수적 구조를 모두 의미합니다.앞에서 언급한 것이 부울 대수의 주제를 다룬 반면, 이 절에서는 부울 법칙의 모델로 완전한 일반성으로 정의된 부울 대수라고 불리는 수학적 대상을 다룹니다.우리는 법칙을 참조하지 않고 정의할 수 있는 개념의 특별한 경우, 즉 구체적인 부울 대수로 시작한 다음 일반적인 개념의 공식적인 정의를 제공합니다.

콘크리트 부울대수

구체적인 부울 대수 또는 집합장은 X에 대한 결합,[5] 교집합, 보집합의 집합 연산 아래 닫힌 주어진 집합 X의 비어 있지 않은 부분 집합입니다.

(제외로, 역사적으로 X 자체는 축퇴 또는 1원소 부울 대수를 제외하기 위해 비어 있지 않아야 했는데, 이는 축퇴 대수가 모든 방정식을 만족하므로 모든 부울 대수가 동일한 방정식을 만족한다는 규칙의 유일한 예외입니다.그러나 이 배제는 "부울 대수"의 선호하는 순수 등식 정의와 상충되며, 오직 방정식을 사용하여 1요소 대수를 배제할 방법은 없습니다. 0 ≥ 1은 계산되지 않으며, 부정된 방정식입니다.따라서 현대의 저자들은 축퇴 부울 대수를 허용하고 X를 비워 둡니다.)

예 1.X모든 부분집합으로 구성된, X거듭제곱 집합X 2.여기서 X는 빈 집합, 유한 집합, 무한 집합 또는 셀 수 없는 집합일 수 있습니다.

예 2.세트와 X.이 2요소 대수는 구체적인 부울 대수가 무한 집합의 부분 집합으로 구성된 경우에도 유한할 수 있음을 보여줍니다.X의 모든 부분집합의 필드는 빈 집합과 X를 포함해야 함을 알 수 있습니다.따라서 X를 빈 집합과 X를 일치시키기 위해 빈 집합으로 으로써 얻은 퇴화 대수 이외의 더 작은 예는 불가능합니다.

예 3.유한 집합과 유한 집합의 정수 집합입니다. 유한 집합은 유한 집합을 제외한 정수 집합입니다.이것은 분명히 상보 하에서 닫히고, 임의의 집합을 갖는 유한 집합의 결합은 유한한 반면 두 유한 집합의 결합은 유한하기 때문에 결합 하에서 닫힙니다.교집합은 "무한"과 "무한"이 교환된 결합처럼 행동합니다.

예 4.예제 2에 의해 만들어진 점에 대한 덜 사소한 예를 위해 n개의n 폐곡선으로 구성된 벤 다이어그램을 생각하고 X를 평면의 모든 점들의 (무한한) 집합이라고 합니다.따라서 각 영역의 내부는 X의 무한 부분 집합이며, X의 모든 점은 정확히 하나의 영역에 있습니다.그러면 모든 가능한2n 두 영역의 결합 집합(빈 영역 집합의 결합으로 얻은 빈 집합과 모든n 영역의 결합으로 얻은 X를 포함)은 X에 대한 결합, 교집합 및 상보 하에서 닫혀 있으므로 구체적인 부울 대수를 형성합니다.다시 구체적인 부울 대수를 구성하는 무한 집합의 부분 집합이 유한하게 많이 있으며, 예제 2는 곡선이 없는 경우 n = 0으로 발생합니다.

비트 벡터로 부분 집합

X서브셋 Y는 인덱스 집합 X를 갖는 인덱스된 비트 패밀리로 식별될 수 있으며, x ∈ Y의해 인덱스된 비트는 1 또는 0이 됩니다(이는 서브셋의 소위 특성 함수 개념입니다).예를 들어, 32비트 컴퓨터 단어는 {0,1,2,...,31} 집합으로 색인화된 32비트로 구성되며, 0과 31은 각각 낮은 차수의 비트와 높은 차수의 비트를 색인화합니다.작은 예를 들어, = {, {\ X =\{ a, b, c를 왼쪽에서 오른쪽으로 순서대로 비트 위치로 보면 X의 8개 부분 집합 {}, {c}, {b}, {b,c}, {a}, {a,c}, {a,b}, {a,b} 및 {a,b,c}는 각각의 비트 벡터 000,001, 010, 011, 100, 101, 110 및 111로 식별될 수 있습니다.자연수 집합에 의해 색인화된 비트 벡터들은 비트들의 무한한 시퀀스인 반면, 단위 구간 [0,1]의 실수들에 의해 색인화된 벡터들은 너무 조밀하게 채워져서 관습적으로 쓸 수 없지만 그럼에도 불구하고 잘 정의된 색인화된 패밀리들을 형성합니다 ([0,1] 구간의 모든 포인트들을 블랙 또는 화이트로 독립적으로 색칠하는 것을 상상해보세요; 블랙k개의 점은 [0,1])의 임의의 부분 집합을 형성합니다.

이러한 비트 벡터의 관점에서, 구체적인 부울 대수는 1010 ∧ 0110 = 0010, 1010 ∨ 0110 = 1110 및 ¬ 1010 = 0101과 같이, 동일한 길이(더 일반적으로, 동일한 집합에 의해 색인화됨)의 모든 비트 벡터들의 비어 있지 않은 집합으로 동등하게 정의되고 비트와이즈 ∧, ∨, ¬, ¬의 비트 벡터 연산 하에서 닫힐 수 있습니다.각각 조치, 조합, 보완.

부울 대수의 원형

위에서 다룬 {0,1} 집합과 그 부울 연산은 길이 1의 비트 벡터의 특수한 경우로 이해될 수 있으며, 이는 부분 집합으로 비트 벡터를 식별함으로써 또한 하나의 요소 집합의 두 부분 집합으로 이해될 수 있습니다.우리는 이것을 전형적인 부울 대수라고 부르는데, 다음과 같은 관찰에 의해 정당화됩니다.

모든 퇴화되지 않은 구체적인 부울 대수가 만족하는 법칙은 전형적인 부울 대수가 만족하는 법칙과 일치합니다.

이러한 관측은 다음과 같이 쉽게 증명됩니다.확실히 모든 구체적인 부울대수가 만족하는 법칙은 구체적이기 때문에 원형적인 것으로 만족합니다.반대로 어떤 구체적인 부울 대수에 대해 실패하는 모든 법칙은 특정 비트 위치에서 실패했을 것이며, 이 경우 그 위치는 그 법칙에 대한 1비트 반례를 제공합니다.하나의 빈 비트 벡터만 있기 때문에 비퇴화는 적어도 하나의 비트 위치를 보장합니다.

다음 절의 최종 목표는 위의 관찰에서 "콘크리트"를 제거하는 것으로 이해할 수 있습니다.그러나 우리는 동형화까지 모든 부울 대수가 구체적이라는 놀라운 더 강력한 관찰을 통해 그 목표에 도달할 것입니다.

부울대수: 정의

지금까지 본 부울대수는 모두 구체적이며, 비트 벡터 또는 일부 집합의 하위 집합으로 구성됩니다.이러한 부울 대수는 부울 대수의 법칙을 만족시키는 집합과 그 집합에 대한 연산으로 구성됩니다.

부울 법칙들이 만족된다는 것을 보여주는 대신, 우리는 대신 집합 X, X에 대한 두 개의 이진 연산, 그리고 하나의 단항 연산을 가정할 수 있고, 연산들이 부울 대수의 법칙을 만족하도록 요구할 수 있습니다.X의 요소는 비트 벡터나 부분집합이 될 필요는 없지만 어떤 것도 될 수 있습니다.이는 보다 일반적인 추상적 정의로 이어집니다.

부울 대수는 부울 법칙을 만족시키는 이진 연산 ∧와 ∨ 그리고 단항 연산 ¬를 갖는 임의의 집합입니다.

이 정의의 목적상 작업이 어떻게 법을 만족하게 되었는지는 법적이든 증명이든 상관이 없습니다.모든 구체적인 부울 대수는 (정통적인 것이 아니라 증명에 의해) 법칙을 만족시키므로, 모든 구체적인 부울 대수는 우리의 정의에 따라 부울 대수입니다.이러한 부울 대수의 공리적 정의는 피아트에 의해 특정 법칙 또는 공리를 만족시키는 집합 및 특정 연산으로서 현대 또는 추상 대수의 특징적인 , 링, 필드 의 추상적 정의와 전적으로 유사합니다.

상보적인 분포 격자에 대한 공리와 같은 부울 대수의 완전한 공리화가 주어지면, 이러한 종류의 대수적 구조가 모든 부울 법칙을 만족시킬 수 있는 충분한 조건은 그 공리만을 만족한다는 것입니다.따라서 다음은 동등한 정의입니다.

부울 대수는 상보적인 분포 격자입니다.

공리화에 관한 부분은 동등한 정의의 기초가 될 수 있는 다른 공리화들을 나열합니다.

표현 가능한 부울대수

모든 구체적인 부울 대수는 부울 대수이지만, 모든 부울 대수가 구체적일 필요는 없습니다.n제곱이 없는 양의 정수로, 1은 정수의 제곱으로 나눌 수 없습니다. 예를 들어 30이지만 12는 아닙니다.최대 공약수, 최소 공약수, n으로 나눗셈(즉, σx = n/x)의 연산은 인수가 n의 양의 나눗셈에 걸쳐 있을 때 모든 부울 법칙을 만족하는 것으로 나타날 수 있습니다.따라서 그 나눗셈들은 부울 대수를 형성합니다.이 나눗셈들은 집합의 부분집합이 아니므로 정의에 따라 구체적이지 않은 부울 대수의 나눗셈을 만듭니다.

그러나 n의 나눗셈을 소인수의 집합으로 나타낸다면, 이 비구체적 부울 대수는 최소공배수에 해당하는 결합, 최대공배수에 대한 교집합, n으로 나눗셈에 대한 상보로 구성된 모든 소인수 집합으로 구성된 구체적 부울 대수와 동형임을 알 수 있습니다.따라서 이 예는 엄밀히 말해 구체화되지는 않지만 적어도 이 표현을 통해 "도덕적으로" 구체화된 것이며, 를 동형이라고 합니다.이 예는 다음과 같은 개념의 예입니다.

부울 대수는 구체적인 부울 대수와 동형일 때 표현 가능하다고 불립니다.

명백한 다음 질문은 다음과 같이 긍정적으로 대답합니다.

모든 부울 대수는 표현 가능합니다.

즉, 동형화까지는 추상적인 부울대수와 구체적인 부울대수가 같습니다.이 상당히 사소하지 않은 결과는 선택 공리보다 약간 약한 선택 원리인 부울 소수 이상 정리에 의존하며, 부울 대수에 대한 스톤의 표현 정리에서 더 자세히 다루어집니다.이 강한 관계는 이전 하위 항목의 관측치를 다음과 같은 쉬운 대표성 결과로 강화하는 약한 결과를 의미합니다.

모든 부울 대수가 만족하는 법칙은 전형적인 부울 대수가 만족하는 법칙과 일치합니다.

그것 자체가 대표성을 의미하는 것이 아니라는 점에서 더 약합니다.여기서 부울대수는 특별한데, 예를 들어 관계대수는 부가적인 구조를 가진 부울대수이지만 모든 관계대수가 관계대수에 적합한 의미로 표현될 수 있는 것은 아닙니다.

부울 대수를 공리화

추상적 부울 대수를 집합으로 정의하고 "The" 부울 법칙을 만족시키는 연산을 정의하는 위의 정의는 다음과 같은 의문을 제기합니다.단순한 답은 "모든 부울 법칙"이며, 부울 대수 0과 1을 유지하는 모든 방정식으로 정의할 수 있습니다.이러한 법은 무한히 많기 때문에 실제로는 대단히 만족스러운 답이 아니며, 다음 질문으로 이어집니다. 그것은 오직 유한하게 많은 법을 유지하는 것만으로 충분한가요?

부울대수의 경우, 대답은 yes입니다.특히 우리가 위에 열거한 방정식들은 끝이 없이 많습니다.우리는 부울 대수가 유한 공리화 가능하거나 유한 기반이라고 말합니다.

이 리스트를 좀 더 짧게 할 수 있습니까?역시 대답은 그렇다 입니다.우선 위의 법률 중 일부는 다른 법률에 의하여 내포되어 있습니다.위의 법칙들의 충분한 부분집합은 연관성, 치환성, 흡수성 법칙의 쌍, π에 대한 π의 분배성(또는 다른 분배성 법칙-하나로 충분), 그리고 두 개의 보완 법칙으로 구성됩니다.사실 이것은 보완된 분포 격자로서 부울 대수의 전통적 공리화입니다.

위에 나열되지 않은 추가적인 법칙을 도입함으로써 목록을 더 단축하는 것이 가능해집니다. 예를 들어, Sheer stroke 작업을 나타내는 수직 막대의 경우,단일 공리 ) ∣ ) ∣ (( ) = c (( b (a c)=이면를 완전히 공리화하기에 충분합니다.더 일반적인 연산을 사용하여 더 긴 단일 공리를 찾는 것도 가능합니다. 부울 [26]대수의 최소 공리를 참조하십시오.

명제논리학

명제 논리학은 부울 [5]대수학과 밀접하게 연결된 논리 체계입니다.부울 대수의 많은 통사적 개념은 표기법과 용어의 약간의 변화만으로 명제 논리를 이어가는 반면, 명제 논리의 의미론은 부울 대수의 방정식적 정리에 대응하는 방식으로 부울 대수를 통해 정의됩니다.

통사적으로 모든 부울 용어는 명제 논리의 명제 공식에 해당합니다.부울 대수와 명제 논리 사이의 이 번역에서 부울 변수 x,y...명제 변수(또는 원자) P,Q,..., x∨y같은 부울 항은 명제 공식 P∨Q가 되고, 0은 거짓 또는 ⊥이 되며, 1은 참 또는 T가 됩니다.일반적인 명제를 언급할 때는 그리스 문자 ψ, φ, ...를 메타변수(명제적 미적분학을 말할 때 사용되는 언어 밖의 변수)로 사용하여 명제를 나타내는 것이 편리합니다.

명제 논리의 의미론은 진리 할당에 의존합니다.진리할당의 본질적인 아이디어는 명제 변수가 고정된 부울 대수의 요소에 매핑되고, 이 문자를 사용한 명제 공식의 진리값은 공식에 대응하는 부울 항의 값을 계산하여 얻는 부울 대수의 요소입니다.고전적 의미론에서는 2요소 부울 대수만 사용되는 반면, 부울 값 의미론에서는 임의의 부울 대수가 고려됩니다.타우톨로지는 임의의 부울 대수(또는 동등하게 두 요소 부울 대수에 대한 모든 진리 할당)에 의해 진리값 1이 할당되는 명제 공식입니다.

이러한 의미론은 명제 논리학의 튜톨로지와 부울 대수의 방정식 정리 사이의 번역을 허용합니다.명제 논리의 모든 조음 Ⅰ은 부울 대수의 정리가 될 부울 방정식 Ⅱ = 1로 표현할 수 있습니다.반대로, 부울 대수의 모든 정리 φ = ψ는 φ ∧ ¬ ∨ ¬ φ ψ ∨ φ ψ ∧¬ φ ψ ∧ ψ ∨¬ ( to responds ∨ the ¬ converse ( ∧ ( ly ψ every t theorem cor of ψ에 해당합니다.→가 언어인 경우, 이러한 마지막 튜톨로지는 (φ→ψ) ∧ (ψ→φ) φ 또는 두 개의 개별 정리인 ψ→φ 및 ψ→≡로 쓸 수도 있습니다. ψ를 사용할 수 있는 경우 단일 튜톨로지 ≡ φ를 사용할 수 있습니다.

적용들

명제적 미적분학의 한 가지 동기부여적인 적용은 [27]자연어에서의 명제와 연역적 주장의 분석입니다.명제 "만약 x = 3이라면 x+1 = 4"는 +와 1과 같은 기호의 의미에 의존하는 반면, 명제 "만약 x = 3이라면 x = 3이면 x = 3"은 그렇지 않으며, 단지 그 구조상 사실이고, "x = 3"이 "x " 4"로 대체되었는지, "달은 녹색 치즈로 만들어졌다"로 대체되었는지는 여전히 사실입니다.이 맞춤법의 일반적인 또는 추상적인 형태는 "if P 그러면 P" 또는 부울 대수의 언어로 "P → P"입니다.

P를 x = 3 또는 다른 명제로 대체하는 을 그 명제에 의한 P의 인스턴스화라고 합니다.추상 명제에서 P를 인스턴스화한 결과를 명제의 인스턴스라고 합니다.따라서 "x = 3 → x = 3"은 추상적 동조어 "PP"의 예로서 동조어입니다.P → x = 3 또는 x = 3 → x = 4와 같은 넌센스를 방지하기 위해 인스턴스화된 변수의 모든 발생을 동일한 명제로 인스턴스화해야 합니다.

명제 연산은 부울 연산을 사용하여 명제 변수로 구성된 추상 명제로 주의를 제한합니다.명제 연산에서 인스턴스화는 여전히 가능하지만, P→(QP)에서 Q를 Q→P인스턴스화하여 인스턴스 P→(QP)를 산출하는 것과 같이 추상 명제에 의한 명제 변수의 인스턴스화만 가능합니다.

(제언적분학 기계의 일부로서 인스턴스화의 이용 가능성은 일반적인 명제 변수가 임의의 명제를 나타내기 위해 언어 내에서 고려될 수 있기 때문에 명제적분학 언어 내에서 메타변수의 필요성을 피합니다.메타변수 자체는 명제화의 범위 밖에 있으며, 명제적 미적분학의 언어의 일부가 아니라, 명제화된 변수와 그 인스턴스를 별개의 구문적 실체로 구별할 수 있어야 하는 이 문장에 대해 이야기하기 위한 동일한 언어의 일부입니다.)

명제 논리에 대한 연역 체계

명제적 미적분학의 공리화는 공리라고 불리는 일련의 튜톨로지와 오래된 튜톨로지로부터 새로운 튜톨로지를 생성하기 위한 하나 이상의 추론 규칙입니다.공리계 A의 증명은 각각이 A의 공리의 인스턴스이거나 증명의 앞에 나타난 명제로부터 A의 일부 규칙을 따르는 유한한 비어 있지 않은 명제의 시퀀스입니다(따라서 순환 추론을 허용하지 않음).마지막 명제는 증명에 의해 증명된 정리입니다.증명의 비어 있지 않은 모든 초기 부분은 그 자체이며, 따라서 증명의 모든 명제는 그 자체가 정리입니다.공리화는 모든 정리가 동조론일 때 건전하고, 모든 동조론이 정리일 [28]때 완전합니다.

순차 미적분

명제 미적분학은 일반적으로 힐베르트 체계로 구성되는데, 그 체계는 단지 부울 대수학의 그것들이고, 그 정리들은 부울 상수 1과 같은 부울항들입니다.다른 형태는 연속 미적분학으로, 보통의 명제적 미적분학과 같은 명제와 A∨B, A∧C,... 같은 연속이라고 불리는 명제 목록의 쌍을 가지고 있습니다.⊢ A, BC,...연속체의 두 반은 각각 선행자와 후행자라고 불립니다.선행 또는 그 일부를 나타내는 관습적인 메타변수는 γ이고, 후행 δ에 대해서는 γ이고; 따라서 ⊢, A δ는 후행이 리스트 δ이고, 그 후에 명제 A가 추가된 리스트 γ인 시퀀스를 나타낼 것입니다.선행자는 그 명제들의 결합으로, 후행은 그 명제들의 결합으로, 후행은 그 명제들의 결합으로, 후행 자체는 선행자에 의한 후행의 수반으로 해석됩니다.

수반은 부울 대수에서 값을 반환하는 이진 연산인 반면, 전자는 유지되거나 유지되지 않는 이진 관계라는 점에서 함축과는 다릅니다.이러한 의미에서 수반은 외부적인 함의 형태로서, 부울 대수의 외부를 의미하며, 시퀀스의 독자도 외부적인 것으로 생각하고 일부 부울 대수의 선행과 후속을 해석하고 비교합니다.x∨y = y일 ⊢의 자연스러운 해석은 x ≤ y로 정의된 부울 대수의 부분 순서에서 ≤.하나의 논리에서 외재적 의미 ⊢와 내재적 의미 →를 혼합하는 이 능력은 순차적 미적분학과 명제적 미적분학의 본질적인 차이 중 하나입니다.

적용들

두 값의 미적분으로서 부울 대수는 컴퓨터 회로, 컴퓨터 프로그래밍, 수학적 논리학의 기본이며, 집합론, [5]통계학 등 수학의 다른 분야에서도 사용됩니다.

컴퓨터

20세기 초에 몇몇 전기[who?] 기술자들은 부울 대수가 특정 유형의 전기 회로의 거동과 유사하다는 것을 직관적으로 인식했습니다.클로드 섀넌(Claude Shannon)은 1937년 석사 논문인 릴레이와 스위칭 회로의 상징적 분석(A Symbol Analysis of Relay and Switching Circuits)에서 그러한 행동이 부울 대수와 논리적으로 동등하다는 것을 공식적으로 증명했습니다.

오늘날 모든 현대 범용 컴퓨터는 2값 부울 논리를 사용하여 기능을 수행합니다. 즉, 전기 회로는 2값 부울 논리의 물리적 표현입니다.고속 회로와 용량성 저장 장치에서 와이어의 전압, 강자성 저장 장치에서 자기 영역의 방향, 천공 카드나 종이 테이프의 구멍 등 다양한 방식으로 이를 달성합니다. (일부 초기 컴퓨터는 2-값 논리 회로 대신 10진 회로나 메커니즘을 사용했습니다.)

물론 주어진 매체에서 두 개 이상의 기호를 코드화하는 것은 가능합니다.예를 들어 와이어에 4개의 기호로 된 알파벳을 코드화하는 데 각각 0, 1, 2, 3볼트를 사용하거나 천공된 카드의 크기가 다른 구멍을 사용할 수 있습니다.실제로는 고속, 소형, 저전력이라는 엄격한 제약 조건이 결합되어 소음이 주요 요인이 됩니다.따라서 단일 사이트에서 발생할 수 있는 여러 가지 기호가 있을 경우 기호를 구별하기가 어렵습니다.디지털 설계자들은 하나의 와이어에서 4개의 전압을 구분하기보다는 와이어당 높은 전압과 낮은 전압 두 개를 선택했습니다.

컴퓨터는 위와 같은 이유로 2값 부울 회로를 사용합니다.가장 일반적인 컴퓨터 아키텍처는 32개 또는 64개 값(예: 011010001101010101010011)의 부울 값의 순서대로 배열된 시퀀스를 사용합니다.기계 코드, 어셈블리 언어 및 기타 특정 프로그래밍 언어로 프로그래밍할 때 프로그래머는 데이터 레지스터의 낮은 수준의 디지털 구조로 작업합니다.이러한 레지스터는 전압에서 작동하며, 여기서 0V는 부울 0을 나타내고 기준 전압(종종 +5V, +3.3V, +1.8V)은 부울 1을 나타냅니다.이러한 언어는 숫자 연산과 논리 연산을 모두 지원합니다.이런 맥락에서 "숫자"는 컴퓨터가 비트의 시퀀스를 이진수(기본 2개의 숫자)로 취급하고 덧셈, 뺄셈, 곱셈, 나눗셈과 같은 산술 연산을 수행하는 것을 의미합니다."논리적"은 비트의 두 시퀀스 사이의 분리, 접속, 부정의 부울 논리 연산을 뜻하며, 한 시퀀스의 각 비트는 다른 시퀀스의 각 비트와 단순히 비교됩니다.따라서 프로그래머들은 필요에 따라 숫자 대수나 부울 대수의 규칙을 작업하고 적용하는 선택권을 가집니다.이러한 작동 계열 간의 핵심적인 차별화 기능은 첫 번째 작동에서 캐리 작동이 존재하지만 두 번째 작동에서는 존재하지 않는다는 것입니다.

2-값 논리

두 가지 가치관이 좋은 선택인 다른 분야는 법학과 수학입니다.일상적인 여유로운 대화에서 "아마도" 또는 "주말에만"와 같은 미묘하거나 복잡한 대답은 받아들일 수 있습니다.그러나 법정이나 정리에 기반한 수학과 같은 보다 초점을 맞춘 상황에서는 단순한 예/아니오 답변을 인정하기 위해 질문을 구성하는 것이 유리하다고 생각됩니다. 즉, 피고가 유죄 또는 무죄인지, 명제가 참 또는 거짓인지, 다른 답변을 허용하지 않는 것이 좋습니다.이것이 응답자에게 실제로 증명할 수 있는 많은 제약 조건이지만, 단순한 예-질문 없음의 원칙은 사법 논리와 수학 논리 모두의 핵심적인 특징이 되어 두 가치 논리를 그 자체로 조직화하고 연구할 가치가 있습니다.

집합론의 중심 개념은 멤버쉽입니다.이제 조직은 초보자, 준회원, 정식 회원과 같은 여러 등급의 회원 자격을 허용할 수 있습니다.집합이 있는 경우 요소가 들어가거나 빠집니다.디지털 컴퓨터의 와이어와 동일하게 세트 구성된 회원 자격 후보는 각 와이어가 높거나 낮거나 하는 것처럼 각 후보가 회원이거나 비회원입니다.

대수학은 수학적 처리가 가능한 모든 영역에서 기본적인 도구이며, 이러한 고려 사항은 컴퓨터 하드웨어, 수학적 논리 및 집합 이론에 기본적으로 중요한 두 값의 대수를 만들기 위해 결합됩니다.

논리는 특히 부울 도메인 {0, 1}을(를) 단위 간격 [0, 1]로 대체함으로써 다중 값 논리로 확장될 수 있습니다. 이 경우 값 0 또는 1만 취하는 것이 아니라 0과 1 사이의 값과 0을 포함하는 값을 가정할 수 있습니다.대수학적으로, 부정(NOT)은 1 - x로 대체되고, 접속(AND)은 {\xy})으로 대체되며, 접속(OR)은 De Morgan의 법칙을 통해 정의됩니다.이러한 값을 논리적 진리값으로 해석하면 다중값 논리가 생성되며, 이는 퍼지 논리와 확률 논리의 기초를 형성합니다.이러한 해석에서 값은 진리의 "정도" - 명제가 참인 정도 또는 명제가 참일 확률로 해석됩니다.

부울 연산

부울 연산의 원래 응용은 수학적 논리학으로, 개별 공식의 참이든 거짓이든 진리값을 결합하는 것이었습니다.

자연어

영어와 같은 자연어에는 몇 가지 부울 연산, 특히 접속사(그리고), 접속사(또는), 부정(아니), 함축(의미)에 대한 단어가 있습니다.그러나 not 은 동의어이고 not 은 동의어가 아닙니다."블록이 테이블 위에 있다"와 "고양이는 우유를 마신다"와 같은 상황적 주장을 결합하기 위해 사용될 때, 이러한 논리적 연결의 의미는 종종 그들의 논리적 대응물의 의미를 갖습니다.그러나 "짐이 문을 통해 걸어갔다"와 같은 행위에 대한 묘사와 함께, 사람들은 교환성의 실패와 같은 차이를 알아차리기 시작하는데, 예를 들어 "짐이 문을 열었다"와 "짐이 문을 통해 걸어갔다"의 순서의 접속은 다른 순서의 접속과 동등하지 않습니다,보통은 그런 경우를 의미하기 때문입니다.질문도 비슷할 수 있습니다: "하늘은 파랗고, 왜 하늘은 파랗습니까?"라는 순서가 역순보다 더 말이 됩니다.행동에 대한 연결 명령은 옷을 입고 학교에 가는 것처럼 행동적 주장과 같습니다.나를 사랑하거나, 떠나거나, 물고기를 잡거나, 미끼를 베는 것과 같은 금지 명령은 한 가지 대안이 덜 선호된다는 암시를 통해 비대칭적인 경향이 있습니다.차나 우유와 같은 결합 명사는 일반적으로 집합 결합과 함께 집합을 설명하는 반면 차나 우유는 선택입니다.그러나 문맥은 이러한 감각을 뒤집을 수 있습니다. 여러분의 선택에서 커피와 차가 일반적으로 여러분의 선택이 커피와 차(대안)와 같다는 것을 의미하기 때문입니다."나는 우유를 좋아하지 않는다"와 같은 이중 부정은 문자 그대로 "나는 우유를 좋아한다"는 의미가 거의 없으며 오히려 제3의 가능성이 있다는 것을 암시하는 것처럼 일종의 위험을 전달합니다."Not not P"는 "확실히 P"로 느슨하게 해석될 수 있으며, P는 반드시 "Not P"를 의미하지만 직관적 논리와 마찬가지로 영어에서 의심됩니다.자연어에서 접속사의 매우 특이한 사용을 고려할 때, 부울 대수는 그것들을 해석하기 위한 신뢰할 수 있는 프레임워크로 간주될 수 없습니다.

디지털 로직

부울 연산은 디지털 로직에서 개별 와이어에 전달된 비트를 결합하여 {0,1}을(를) 통해 해석하는 데 사용됩니다.n개의 동일한 이진 게이트의 벡터가 n개의 비트 각각의 비트 벡터를 결합하는 데 사용될 때, 개별 비트 연산은 2개의 요소를n 갖는 부울 대수의 값에 대한 단일 연산으로 집합적으로 이해될 수 있습니다.

순진집합론

나이브 집합 이론은 부울 연산이 주어진 집합 X의 부분 집합에 작용하는 것으로 해석합니다.앞서 본 바와 같이 이 동작은 두 비트 벡터의 분리에 해당하는 두 집합의 결합과 함께 비트 벡터의 좌표 단위 조합과 정확히 일치합니다.

비디오 카드

3개의 생성기에 있는 256원소 자유 부울 대수는 비트 블릿을 사용하여 픽셀로 구성된 전체 영역을 조작하는 래스터 그래픽에 기반한 컴퓨터 디스플레이에 배치되며, 소스 영역이 일반적으로 마스크라고 불리는 제3의 영역의 도움을 받아 대상과 결합되는 방법을 지정하기 위해 부울 연산에 의존합니다.현대의 비디오 카드는 이 목적을 위해 모든 2 = 256 터너리 연산을 제공하며, 연산 선택은 1바이트(8비트) 파라미터입니다.상수들은SRC = 0xaa 또는 0b101010, DST = 0xcc 또는 0b≥1100, MSK = 0≥0 또는 0b1100과 같은 부울 연산을 허용합니다.(SRC^DST)&MSK(XOR 소스와 데스티네이션을 의미하고 마스크를 사용한 결과) 컴파일 시간에 계산된 바이트를 나타내는 상수로 직접 적어야 하며, 0x80의 경우(SRC^DST)&MSK예제, 0x88이면SRC^DST, 실행 시 비디오 카드는 바이트를 매우 적은 하드웨어를 필요로 하고 표현의 복잡성과 완전히 독립적인 시간이 걸리는 통일된 방식으로 원래 표현식이 나타내는 래스터 연산으로 해석합니다.

모델링 및 CAD

컴퓨터 보조 설계를 위한 솔리드 모델링 시스템은 다른 객체로부터 객체를 구축하기 위한 다양한 방법을 제공하며, 그 중 하나는 부울 연산입니다.이 방법에서는 객체가 존재하는 공간을 복셀집합 S(2차원 그래픽에서 픽셀의 3차원 아날로그)로 이해하고 모양을 S의 부분 집합으로 정의하여 결합, 교차 등을 통해 객체를 집합으로 결합할 수 있습니다.한 가지 분명한 용도는 단순히 후자의 결합으로 단순한 모양에서 복잡한 모양을 만드는 것입니다.재료의 제거로 이해되는 조각에 또 다른 용도가 있습니다. 물리적 재료의 물리적 기계로 수행할 수 있는 분쇄, 밀링, 루팅 또는 드릴링 작업은 부울 연산 x ¬y 또는 x - y로 컴퓨터에서 시뮬레이션 할 수 있습니다. 부울 연산 x ∧y 또는 x - y는 설정된 이론에서 y의 요소를 x의 요소에서 제거합니다.따라서, 하나는 가공되어야 하고 다른 하나는 제거되어야 하는 재료가 주어지면, 후자를 제거하기 위해 전자를 가공한 결과는 단순히 그들의 세트 차이로 설명됩니다.

부울 검색

검색 엔진 쿼리는 부울 논리도 사용합니다.이 응용 프로그램의 경우, 인터넷의 각 웹 페이지는 "집합"의 "요소"로 간주될 수 있습니다.다음 예제에서는 [NB 2]Google에서 지원하는 구문을 사용합니다.

  • 큰따옴표는 공백으로 구분된 단어를 하나의 [NB 3]검색어로 결합하는 데 사용됩니다.
  • 공백은 검색어 결합을 위한 기본 연산자이므로 논리 AND를 지정하는 데 사용됩니다.
"검색어 1" "검색어 2"
  • OR 키워드는 논리적 OR에 사용됩니다.
"검색어 1" 또는 "검색어 2"
  • 접두사 빼기 기호는 논리 NOT:에 사용됩니다.
"검색어 1" - "검색어 2"

참고 항목

메모들

  1. ^ a b c 컴퓨터 프로그래밍에서 비트 와이즈 연산을 하려면 1을 0xFFFF로 읽는 것이 도움이 될 수 있습니다.이진수의 모든 비트는 1이어야 합니다.
  2. ^ 모든 검색 엔진이 동일한 쿼리 구문을 지원하는 것은 아닙니다.또한 Google과 같은 일부 조직에서는 대체 구문 또는 확장 구문을 지원하는 "전문화된" 검색 엔진을 제공합니다(예: 구문 치트시트, Google 코드 검색은 정규식을 지원합니다).
  3. ^ 두 개의 따옴표로 구분된 검색어를 Google 문서에서 "정확한 구문" 검색이라고 합니다.

참고문헌

  1. ^ Boole, George (2011-07-28). The Mathematical Analysis of Logic - Being an Essay Towards a Calculus of Deductive Reasoning.
  2. ^ Boole, George (2003) [1854]. An Investigation of the Laws of Thought. Prometheus Books. ISBN 978-1-59102-089-9.
  3. ^ "부울에 의해 유래되고 슈뢰더에 의해 확장되고 화이트헤드에 의해 완성된 미적분에 대한 부울 대수(또는 부울 '대수')의 이름은 1913년 셰퍼에 의해 처음으로 제안된 것으로 보입니다." 에드워드 버밀리예 헌팅턴, "화이트헤드와 러셀의 수학 원리를 특별히 참조하여 논리 대수에 대한 새로운 일련의 독립적인 가설들.atica", 미국 수학 학회 거래 35 (1933), 274-304; 각주, 278페이지.
  4. ^ Peirce, Charles S. (1931). Collected Papers. Vol. 3. Harvard University Press. p. 13. ISBN 978-0-674-13801-8.
  5. ^ a b c d e f g Givant, Steven R.; Halmos, Paul Richard (2009). Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer. pp. 21–22. ISBN 978-0-387-40293-2.
  6. ^ Nelson, Eric S. (2011). "The Yijing and Philosophy: From Leibniz to Derrida". Journal of Chinese Philosophy. 38 (3): 377–396. doi:10.1111/j.1540-6253.2011.01661.x.
  7. ^ Lenzen, Wolfgang. "Leibniz: Logic". Internet Encyclopedia of Philosophy.
  8. ^ a b c Dunn, J. Michael; Hardegree, Gary M. (2001). Algebraic methods in philosophical logic. Oxford University Press. p. 2. ISBN 978-0-19-853192-0.
  9. ^ Weisstein, Eric W. "Boolean Algebra". mathworld.wolfram.com. Retrieved 2020-09-02.
  10. ^ Balabanian, Norman; Carlson, Bradley (2001). Digital logic design principles. John Wiley. pp. 39–40. ISBN 978-0-471-29351-4.Balabanian, Norman; Carlson, Bradley (2001). Digital logic design principles. John Wiley. pp. 39–40. ISBN 978-0-471-29351-4.온라인 견본
  11. ^ Rajaraman; Radhakrishnan (2008-03-01). Introduction To Digital Computer Design. PHI Learning Pvt. Ltd. p. 65. ISBN 978-81-203-3409-0.
  12. ^ Camara, John A. (2010). Electrical and Electronics Reference Manual for the Electrical and Computer PE Exam. www.ppi2pass.com. p. 41. ISBN 978-1-59126-166-7.
  13. ^ Shin-ichi Minato, Saburo Muroga (2007). "Chapter 29: Binary Decision Diagrams". In Chen, Wai-Kai (ed.). The VLSI handbook (2 ed.). CRC Press. ISBN 978-0-8493-4199-1.
  14. ^ Parkes, Alan (2002). Introduction to languages, machines and logic: computable languages, abstract machines and formal logic. Springer. p. 276. ISBN 978-1-85233-464-2.
  15. ^ Barwise, Jon; Etchemendy, John; Allwein, Gerard; Barker-Plummer, Dave; Liu, Albert (1999). Language, proof, and logic. CSLI Publications. ISBN 978-1-889119-08-3.
  16. ^ Goertzel, Ben (1994). Chaotic logic: language, thought, and reality from the perspective of complex systems science. Springer. p. 48. ISBN 978-0-306-44690-0.
  17. ^ 할모스, 리처드 (1963).부울대수 강의.밴 노스트랜드
  18. ^ Bacon, Jason W. (2011). "Computer Science 315 Lecture Notes". Retrieved 2021-10-01.
  19. ^ O'Regan, Gerard (2008). A brief history of computing. Springer. p. 33. ISBN 978-1-84800-083-4.
  20. ^ "Elements of Boolean Algebra". www.ee.surrey.ac.uk. Retrieved 2020-09-02.
  21. ^ McGee, Vann, Sentential Calculus Revisited: Boolean Algebra (PDF)
  22. ^ Goodstein, Reuben Louis (2012), "Chapter 4: Sentence Logic", Boolean Algebra, Courier Dover Publications, ISBN 978-0-48615497-8
  23. ^ Venn, John (July 1880). "I. On the Diagrammatic and Mechanical Representation of Propositions and Reasonings" (PDF). The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. 5. 10 (59): 1–18. doi:10.1080/14786448008626877. Archived (PDF) from the original on 2017-05-16. [1] [2]
  24. ^ Shannon, Claude (1949). "The Synthesis of Two-Terminal Switching Circuits". Bell System Technical Journal. 28: 59–98. doi:10.1002/j.1538-7305.1949.tb03624.x.
  25. ^ Koppelberg, Sabine (1989). "General Theory of Boolean Algebras". Handbook of Boolean Algebras, Vol. 1 (ed. J. Donald Monk with Robert Bonnet). Amsterdam, Netherlands: North Holland. ISBN 978-0-444-70261-6.
  26. ^ McCune, William; Veroff, Robert; Fitelson, Branden; Harris, Kenneth; Feist, Andrew; Wos, Larry (2002), "Short single axioms for Boolean algebra", Journal of Automated Reasoning, 29 (1): 1–16, doi:10.1023/A:1020542009983, MR 1940227, S2CID 207582048
  27. ^ Allwood, Jens; Andersson, Gunnar-Gunnar; Andersson, Lars-Gunnar; Dahl, Osten (1977-09-15). Logic in Linguistics. Cambridge University Press. ISBN 978-0-521-29174-3.
  28. ^ Hausman, Alan; Kahane, Howard; Tidman, Paul (2010) [2007]. Logic and Philosophy: A Modern Introduction. Wadsworth Cengage Learning. ISBN 978-0-495-60158-6.
  29. ^ Girard, Jean-Yves; Taylor, Paul; Lafont, Yves (1990) [1989]. Proofs and Types. Cambridge University Press (Cambridge Tracts in Theoretical Computer Science, 7). ISBN 978-0-521-37181-0.

추가열람

역사적 관점

외부 링크