Boolean algebra – 불 대수

불 대수(영어: Boolean algebra)는 조지 불이 19세기 중반에 고안한 논리 수학의 대표적 형태이다.
불 격자(Boolean lattice)나 불 속(束)이라고도 한다. 불 대수의 연구는 대수적 구조로서 속의 이론을 발전시키는
하나의 계기가 되었다. 수학적인 엄밀한 정의는 다음에 기술한다.

디지털 회로 설계에서는 필수적인 지식이다. 디지털 회로는 전압의 H(High), L(Low)만으로 정보를 연산하기
때문에, 기본적으로 조합 회로는 불 대수에 있는 논리식을 써서 나타낼 수 있다. (하지만, 플립 플랍 등 순차 회로는
단순하게 하나의 논리식으로 나타낼 수 없다.)

불 대수의 기본 연산(논리 연산)은 논리 부정 ¬(not), 논리합 ∨(or), 논리곱 ∧(and)로 출발된다. 이러한 연산 합성
으로부터 만들어지는 연산 중 대표적인 것으로 배타적 논리합(xor)이 있다.

불 대수를 불 격자(불 속)라고 부르는 이유는, ∨, ∧에 대해서 분배 가능한 격자가 되기 때문이다. 즉, 다음 법칙이
성립한다:

   1. 멱등 법칙(idempotence): x ∧ x = x ∨ x = x,
   2. 교환 법칙(commutativity): x ∧ y = y ∧ x, x ∨ y = y ∨ x,
   3. 결합 법칙(associativity): (x ∧ y)∧ z = x ∧(y ∧ z), (x ∨ y)∨ z = x ∨(y ∨ z),
   4. 흡수 법칙(absorption): (x ∧ y)∨ x = x, (x ∨ y)∧ x = x,
   5. 분배 법칙(distributivity): (x ∨ y)∧ z = (x ∧ z)∨(y ∧ z), (x ∧ y)∨ z = (x ∨ z)∧(y ∨ z).

    또한 불 대수에서는 다음 조건이 성립한다:
    참을 1 거짓을 0으로 하여, 각 x 항과 반대되는 ¬x 항이 존재할 때, (x ∧ ¬x = 0), (x ∨ ¬x = 1)을 만족한다.
    수학에서는 이러한 조건을 공리(公理, axiom)라 하여, 그것을 만족하는 집합을 불 격자(속)나 불 대수라고 한다.

======================================================================

Boolean algebra (or Boolean logic) is a logical calculus of truth values, developed by George Boole. It resembles the algebra of real numbers as taught in high school, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the logical operations of conjunction x∧y, disjunction x∨y, and complement ¬x. The Boolean operations are these and all other operations obtainable from them by composition; equivalently, the finitary operations on the set {0,1}. The laws of Boolean algebra can be defined axiomatically as the equations derivable from a sufficient finite subset of those laws, such as the equations axiomatizing a complemented distributive lattice or a Boolean ring, or semantically as those equations identically true or valid over {0,1}. The axiomatic approach is sound and complete in the sense that it proves respectively neither more nor fewer laws than the validity-based semantic approach.

Applications

Boolean algebra as the calculus of two values is fundamental to digital logic, computer programming, and mathematical logic, and is also used in other areas of mathematics such as set theory and statistics.

Digital logic codes its symbols in various ways: as voltages on wires in high-speed circuits and capacitive storage devices, as orientations of a magnetic domain in ferromagnetic storage devices, as holes in punched cards or paper tape, and so on. Now it is possible to code more than two symbols in any given medium. For example one might use respectively 0, 1, 2, and 3 volts to code a four-symbol alphabet on a wire, or holes of different sizes in a punched card. In practice however the tight constraints of high speed, small size, and low power combine to make noise a major factor. This makes it hard to distinguish between symbols when there are many of them at a single site. Rather than attempting to distinguish between four voltages on one wire, digital designers have settled on two voltages per wire, high and low. To obtain four symbols one uses two wires, and so on.

Programmers programming in machine code, assembly language, and other programming languages that expose the low-level digital structure of the data registers operate on whatever symbols were chosen for the hardware, invariably bit vectors in modern computers for the above reasons. Such languages support both the numeric operations of addition, multiplication, etc. performed on words interpreted as integers, as well as the logical operations of disjunction, conjunction, etc. performed bit-wise on words interpreted as bit vectors. Programmers therefore have the option of working in and applying the laws of either numeric algebra or Boolean algebra as needed. A core differentiating feature is carry propagation with the former but not the latter.

Other areas where two values is a good choice are the law and mathematics. In everyday relaxed conversation, nuanced or complex answers such as “maybe” or “only on the weekend” are acceptable. In more focused situations such as a court of law or theorem-based mathematics however it is deemed advantageous to frame questions so as to admit a simple yes-or-no answer—is the defendant guilty or not guilty, is the proposition true or false—and to disallow any other answer. However much of a straitjacket this might prove in practice for the respondent, the principle of the simple yes-no question has become a central feature of both judicial and mathematical logic, making two-valued logic deserving of organization and study in its own right.

A central concept of set theory is membership. Now an organization may permit multiple degrees of membership, such as novice, associate, and full. With sets however an element is either in or out. The candidates for membership in a set work just like the wires in a digital computer: each candidate is either a member or a nonmember, just as each wire is either high or low.

Algebra being a fundamental tool in any area amenable to mathematical treatment, these considerations combine to make the algebra of two values of fundamental importance to computer hardware, mathematical logic, and set theory. It has not featured so prominently in law however, perhaps because mathematical methods in general have not been applied as vigorously there as in these other application areas.

Basic operations사용자 삽입 이미지

After values, the next ingredient of any algebraic system is its operations. Whereas elementary algebra is based on numeric operations multiplication xy, addition x + y, and negation −x, Boolean algebra is customarily based on logical counterparts to those operations, namely conjunction x∧y (AND), disjunction x∨y (OR), and complement or negation ¬x (NOT).

Conjunction is the closest of these three to its numerical counterpart, in fact on 0 and 1 it is multiplication. As a logical operation the conjunction of two propositions is true when both propositions are true, and otherwise is false. The first column of Figure 1 below tabulates the values of x∧y for the four possible valuations for x and y; such a tabulation is traditionally called a truth table.

Disjunction, in the second column of the figures, works almost like addition, with one exception: the disjunction of 1 and 1 is neither 2 nor 0 but 1. Thus the disjunction of two propositions is false when both propositions are false, and otherwise is true. This is just the definition of conjunction with true and false interchanged everywhere; because of this we say that disjunction is the dual of conjunction.

Logical negation however does not work like numerical negation at all. Instead it corresponds to incrementation: ¬x = x+1 mod 2. Yet it shares in common with numerical negation the property that applying it twice returns the original value: ¬¬x = x, just as −(−x) = x. An operation with this property is called an involution. The set {0,1} has two permutations, both involutary, namely the identity, no movement, corresponding to numerical negation mod 2 (since +1 = −1 mod 2), and SWAP, corresponding to logical negation. Using negation we can formalize the notion that conjunction is dual to disjunction via De Morgan’s laws, ¬(x∧y) = ¬x ∨ ¬y and ¬(x∨y) = ¬x ∧ ¬y. These can also be construed as definitions of conjunction in terms of disjunction and vice versa: x∧y = ¬(¬x ∨ ¬y) and x∨y = ¬(¬x ∧ ¬y).

Various representations of Boolean operationsFigure 2 shows the symbols used in digital electronics for conjunction and disjunction; the input ports are on the left and the signals flow through to the output port on the right. Inverters negating the input signals on the way in, or the output signals on the way out, are represented as circles on the port to be inverted.

출처: 위키사전(Boolean algebra), 위키사전(불대수)

You may also like...

댓글 남기기