dt001

2. 부울대수

개요

부울 대수 : 변수(a, b, c, ...)들의 조합을 실행시키는 일련의 논리적인 연산
(AND, OR, NOT)으로 정의되는 하나의 수학적 학설.

부울 식(스위칭 식) : 부울 대수를 이용한 표현(변수는 0, 1로 제한)
19세기 George Boole 의 이름에서 유래함 .

Huntington : 1904년에 부울의 연구에 수정을 가하여 일련의 수학적인 표현을 공식화.

디지털 시스템 : 부울과 헌팅턴이 공식화한 함수들을 실행하기 위해 전자공학을 이용
하여 만들어진 시스템.

Claude Shannon : 1930년대 말에 전화 교환에서의 부울대수의 사용에 관한 논문을 발표.
Shannon은 현대 디지털 시스템의 "아버지"로 여겨지고 있다.

2.1 2진 논리함수

2진 변수 : 영(0)과 일(1)의 두 가지 값만을 가질 수 있음. 나머지는 일반 대수에서의
변수와 같다. 이름, 기호, 문자, 숫자, 또는 이들을 조합하여 표현.

            (AND, OR, NOT) : 모든 디지털 시스템의 해석과 설계를 위한 기본함수
                                        함수는 입력과 출력변수들의 관계를 나타내기 위해서 수학과
                                        논리에서사용되는 용어이다. 각각의 변수는 2진 변수(0, 1)로
                                        제한한다.

진리표(truth table) : 2진의 입력과 출력변수사이의 가능한 조합을 표로 표현한 것.

"참(truth)" 1 vs "거짓(false)" 0

정논리(positive logic) : 참은 대부분 1로, 거짓은 0으로 표시될 때.

부논리(negative logic) : 참이 0으로, 거짓이 1로 표시할 때.

논리곱(AND)

                AND는 연산기호 * 로 표시한다. 2진 변수 x와 y의 AND 함수연산은 식 아래와 같다.
                x와 y의 둘 다 참인 경우에 출력은 참이 된다. 즉 입력 중에 어느하나라도 0이면
                출력은 0 가 된다

s = x AND y

                    s = xy
                    s = x*y
                    s = (x)(y)

2-입력 AND의 진리표는 다음과 같다.

                    -------------------------------
                         입력                         출력
                    -------------------------------
                      x           y                       s
                    -------------------------------
                      0           0                       0

0 1 0

1 0 0

1 1 1
-------------------------------

3 입력과 4입력의 표현식을 다음과 같이 쓸 수 있다.

s = xyz

s = wxyz

논리합(OR)

            OR는 연산기호 + 로 표시한다. 2진 변수 x와 y의 OR 함수연산은 식 아래와 같다.
            x와 y의 어느 한쪽이 참이거나, 둘 다 참인 경우에 출력은 참이 된다. 즉 입력 중에
            어느하나라도 1이면 출력은 1이된다

s = x + y

2-입력 OR 진리표는 다음과 같다.

0 1 1

1 0 1

1 1 1
-------------------------------

3 입력과 4입력의 표현식을 다음과 같이 쓸 수 있다.

s = x + y

s = w + x+ y+ z

역논리(부정, NOT)

s = x'

NOT 진리표는 다음과 같다.

                    -------------------
                        입력            출력
                    -------------------
                          x                 s
                    -------------------
                          0                 1

1 0
-------------------

NAND, NOR, EX-OR(배타적 논리합), 그리고 EX-NOR(배타적 NOR)함수들은 모두
AND, OR, NOT 함수의 조합을 기본으로 한다.

역 논리곱(NAND)

                NAND 함수는 NOT과 AND로부터 유도되며, 이것은 NOT AND를 줄여서 표현한
                것이다. 이 함수는 AND 연산 (xy)을 수행한 후 이어서 NOT 연산을 수행하는 것
                으로 정의된다. (xy)' 라고 쓸 수 있다.

s = (xy)'

2-입력 NAND 진리표는 다음과 같다

                    -------------------------------
                         입력                         출력
                    -------------------------------
                      x           y                       s
                    -------------------------------
                      0           0                       1

0 1 1

1 0 1

1 1 0
-------------------------------

역 논리합(NOR)

            NOR 함수는 NOT과 OR를 조합한 것이며, 이것은 NOT OR의 축약형이다.
            함수는 OR 함수 (x + y)와 NOT 함수 (x + y)'의 순차적인 실행으로 정의되며
            (x + y)' 로 쓸 수 있다.

s = (x + y)'

2-입력 NOR 진리표는 다음과 같다.

0 1 0

1 0 0

1 1 0
-------------------------------

배타적 논리합(EX-OR)

            배타적 OR는 입력변수 중에서 홀수 개가 참일 경우 그 출력이 참이 되는 함수이다.
            이름중의 배타적이라고 하는 의미는 이 함수가 짝수 개의 입력이 참인 경우를
            "배제(Exclude)"시키기 때문이다.

2-입력 EX-OR 함수는 다음과 같다.

2-입력 EX-OR 진리표는 다음 표와 같다.

0 1 1

1 0 1

1 1 0
-------------------------------

2-입력 EX-OR 함수를 s = xy' + x'y이라고도 쓸 수 있다.

3-입력 EX-OR 진리표는 다음과 같다.

                    -------------------------------
                               입력                     출력
                    -------------------------------
                      x          y          z              s
                    -------------------------------
                      0          0          0              0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1
-------------------------------

            모든 홀수 개의 참인 입력변수를 가지는 조합은 출력을 1로 만든다.
            EX-OR, EX-NOR는 2-입력 게이트로 집적회로로 상용화되어 이용할 수 있다.
            즉 3변수 이상의 입력을 가지는 EX-OR는 2-입력 게이트로부터 조합 하여 사용
            할 수 있다.

배타적 역 논리합(EX-NOR)

            EX-NOR는 등가 게이트(equivalence gate)라고도 한다. 출력은 짝수 개의 입력이
            같을 때 참이 된다. EX-NOR는 EX-OR의 역과 같기 때문에 단순히 EX-OR의 출력에
            NOT 함수를 추가함으로써 EX-NOR 함수를 만들 수 있다. 즉, EX-OR와는 반대로
            홀수 개의 입력이 참이 되는 경우를 "배제(exclude)"하고, 짝수 개의 입력이 참이
            되는 경우를 "포함(include)" 한다.

s = x ⊙ y

2-입력 EX-NOR 진리표는 다음 표와 같다.

0 1 0

1 0 0

1 1 1
-------------------------------

2-입력 EX-NOR 함수는 s = x'y' + xy라고 쓸 수 있다.

3-입력 EX-NOR 진리표는 다음 표와 같다.

                    -------------------------------
                               입력                     출력
                    -------------------------------
                      x          y          z              s
                    -------------------------------
                      0          0          0              1

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0
-------------------------------

            EX-OR와 EX-NOR의 2변수, 3변수 진리표를 비교해 보면 EX-NOR의 출력 행이
            EX-OR의 출력 행의 논리적 역과 같음을 알 수 있다. 2-입력 이상의 입력단을
            가지는 EX-NOR 함수는 EX-OR함수와 유사하게 2-입력 게이트로부터 유도될수 있다.

2.2 논리 대수

AND, OR, NOT연산 : 모든 논리 설계를 가능하게 하는 기본 함수.
논리 대수에서도 3가지의 연산이 존재.

                    1. ( ) 또는 * 또는 · AND
                    2.   OR
                    3.   또는   NOT

2.2.1 등가

{0, 1} ∈ B

            위 식은 B가 원소 0, 1을 포함하는 집합임을 의미한다. 2-변수 x와 y의 값이 같은 경우
            등가(equivalence)라고 한다. 예를 들면, x = 0, y = 0인 경우 x = y이고,
            x = 1, y = 1인 경우도 x = y이다.

2.2.2 닫힘

            어떠한 집합의 원소끼리의 연산의 결과가 그 집합의 원소일 경우 집합은 2진
            연산(·,＋)에 대해서 닫혀 있다고 말한다. 반대로, 연산의 결과가 집합의 원소가 아닐
            경우에는 닫힘(closure)의 성질은 성립하지 않는다.

B는 AND( )에 대해서 닫혀 있다.

            a, b, c가 2진 변수라고 하자. 그러면, 각각의 변수는 2진 문자 집합(0,1)으로 제한된다.
            입력변수 a, b에 AND연산을 적용시켜 보면 출력변수 c는 하나의 2진 값을 가지는
            결과를 만들어, 이 경우 연산이 닫혀 있다고 말한다.

B는 ＋에 대해서 닫혀 있다.

            a, b, c가 2진 변수라고 하자. 그러면, 각각의 변수는 2진 문자 집합(0, 1)으로 제한된다.
            입력변수 a, b에 OR연산을 적용시켜 보면 출력변수 c는 2진수로 그 결과를 생성하는데
            이때 우리는 연산이 닫혀 있다고 한다.

2.2.3 동일성

            2진 연산(·, ＋)은 Ie라고 부르는 동일성(identity) 원소를 가지고 있다.
            Ie는 반드시 2진수 집합{0, 1}에 포함되어 있어야 한다. Ie가 변수 x와 AND연산된
            결과는 x이고, Ie가 변수 x와 OR 연산된 결과도 역시 x이다.

xIe = x

x + xIe = x

동일성 원소는 원소 x의 값을 변화시키지 않는다.

                    ------------------------------------
                            AND                     OR
                    ----------------   ------------------
                     x        Ie          xIe              x        Ie          x + Ie
                    ------------------------------------
                     0        1        0          0        0         0

1 1 1 1 0 1
------------------------------------

            Ie를 1이라고 하면, xIe = x1 = x이다. 그러므로, 2진 상수 1은 AND연산에 대해서는
            동일성 원소이다.
            Ie를 0이라고 하면, x + Ie = x + 0 = x 이다. 그러므로, 2진 상수 0은 OR연산에
            대해서는 동일성 원소이다.

2.2.4 결합성

집합 B에서 수행되는 2진 연산(·, ＋)이 식 (2.12)의 조건을 만족시키면 집합 B는
결합적(associative)이라고 한다.

(xy)z = x(yz)

(x + y) + z = x + (y + z)

괄호의 위치는 중요하지 않다. 변수들의 그룹들은 AND와 OR연산에 대해서는 재정렬
되거나 재결합 될 수 있다.

2.2.5 분배성

집합 B에서 수행되는 2진 연산(·, ＋)이 식 (2.13)의 조건을 만족시키면 집합 B는
분배적(distributive)이라고 말한다.

x(y + z) = xy + xz : OR연산에 대한 AND의 분배성

x + (yz) = (x + y)(x + z) : AND연산에 대한 OR의 분배성

2.2.6 교환성

집합 B에서 수행되는 2진 연산(·, ＋)이 식 (2.14)의 조건을 만족시키면 집합 B는
교환적(commutative)이라고 한다.

xy = yx

x + y = y + x

            교환성은 단순하게 보면 논리연산에서의 변수들의 순서를 재정렬하는 것이다.
            논리 회로는 하나의 게이트만을 가져야 한다. 게이트로의 입력변수의 연결 순서는
            중요하지 않다.

2.2.7 상보성

2진 변수에 대하여 상보(complement) 보수 또는 부정이라고 하는 2진 연산자가
다음 식과 같이 2진 변수들에서도 존재한다.

xx' = 0

x + x' = 1

위 식에서 x'은 x의 보수를 의미한다.
0의 보수는 1이며, 1의 보수는 0이다. 임의의 변수 x의 보수는 x'이라고 쓴다.

2.2.8 쌍대성

            쌍대성(duality)은 원래의 연산자들이나 상수들의 반대 또는 미러(mirror) 영상이다.
            2진 연산자를 이용한 논리는 AND와 OR 연산자들간에 쌍대성이 존재한다. AND의
            쌍대는 OR이고, OR의 쌍대는 AND이다. 그리고 0 의 쌍대는 1 이고 1 의 쌍대는
            0 가 된다.

2.2.9 흡수성

            흡수성(absorption property)은 스위칭 대수식을 간단히 하는데 유용한 도구를
            제공해 준다. 가끔 논리식이 문제로부터 바로 유도되는 경우가 많은데 이렇게 될
            경우에 불필요한 부분이 식에 포함되게 된다. 흡수성에 의해서 이 불필요한 부분을
            제거한다는 것은 최종적으로 구현되는 전자회로의 가격을 낮추게 된다. 예를 들어,

x + xy = x

x(x + y) = x

추후 논리간소화과정에서 상세 설명할것이며 이렇게 간략화 함으로서
두개의 GATE가 소요되던것을 한개의 GATE로 구현 가능하다.

2.2.10 멱등성

멱등성(idempotency property)은 동일성과 관계된다.

x + x = x

xx = x

임의의 변수는 자기 자신과 AND 연산되거나 OR 연산되면 출력은 자기자신이 된다.

2.2.11 2진 변수와 상수

{0, 1}의 값을 가질 수 있는 2진 변수 x는 2진 상수 {0, 1}과 결합할 수 있다.

x + 0 = x

x + 1 = 1

x 0 = 0

x 1 = x

2.2.12 드모르간 정리

            영국의 수학자였던 드모르간(DeMorgan)은 부울과 같은 시대의 사람이었다.
            그는 논리식을 변환할 수 있는 매우 유용한 도구를 제공해 주는 한 쌍의 논리적 정리를
            개발했다. 드모르간건에 의해 만들어진 정리는 쌍대성의 원리를 사용한다.

1. AND 함수의 보수는 각각의 입력변수에 보수가 취해진 OR이다.

s = (x·y)' <=> s = x' + y'

s = (x·y·z)' <=> s = x' + y' + z'

2. OR 함수의 보수는 각각의 입력변수에 보수가 취해진 AND 함수이다.

s = (x + y)' <=> s = x'·y'

s = (x + y + z)' <=> s = x'·y'·z'

(x1x2x3 . . . xn)' = x1 + x2 + x3 + . . . + xn

(x1 + x2 + x3 +. . . + xn)' = x1'x2'x3'. . . xn'

                    임의의 논리 함수의 보수는 각각의 변수에 보수를 취해(x는 x'으로) 대치하고,
                    AND는 OR로, OR는 AND로, 그리고 상수도 그들의 보수를 취해
                    (0은 1로, 1은 0으로) 대치시켜 구할 수 있다.

[부울 대수의 동일성과 부울 정리]

                 ------------------------------------------
                                표 현                         가정/정리
                    ------------------------------------------------
                            x + 1 = 1

x0 = 0

x1 = x 동일성

x + 0 = x 동일성

xx' = 0 상보성

x + x'= 1 상보성

xⁿ = x 제곱 또는 더블 상보성

x + x = x 멱등성

xx = x 멱등성

xy = yx 교환성

x + y = y + x 교환성

x(y + z) = xy + xz 분배성

x + (yz) = (x + y)(x + z) 분배성

x(yz) = (xy)z 결합성

x + (y + z) = (x + y) + z 결합성

x + xy = x 흡수성

x(x + y) = x 흡수성

x(x' + y) = xy 흡수성

x'y' = (x + y)' 드모르간

(xy)' = x' + y' 드모르간

xy + xy' = x Adjacency
-----------------------------------------------

[예제 2.1] s = (x·y)' 함수를 드모르간 정리를 이용하여 등가식을 구하라.

[예제 2.2] s = x + y 함수를 드모르간 정리를 이용하여 등가식을 구하라.

[예제 2.3] s = xy + xz 의 등가식을 구하라.

[예제 2.4] s = x(y + z')' 의 드모르간 등가회로를 구하라.

[예제 2.5] s = x + yz' + x(y' + z')의 등가식을 구하라.

2.3 부울 대수를 사용한 스위칭 식의 간략화

논리식 내의 불필요한 변수나 항은 최종회로 구현에서의 손실을 줄이기 위해서 반드시
제거 되어야 한다.

카노맵(Karnaugh map)을 이용해서 스위칭 식을 간략히 할 때 알 수 있겠지만, 보수성은
논리식을 간략히 하는데 중요한 역할을 한다.

[예제 2.6] s = x'y + xy' 논리식에 대해

                1) AND, OR, NOT로 구성되는 설계를 하라.
                2) NOR로 구성되는 설계 설계를 하라.
                3) NAND로 구성되는 설계 설계를 하라.

[예제 2.7] s = xy'z + xyz 논리식을 간략화 하라.

[예제 2.8] s = x'yz' + x'yz + xyz' + xyz 논리식을 간략화 하라.

[예제 2.9] s = x(y' + z)'(yz)' 논리식을 간략화 하라.

[예제 2.10] s = x'y'z' + xy'z + x'yz' + xyz 논리식을 간략화 하라.

[ HOME | TOP | PREVIOUS | NEXT ]