[이산수학] 부울 대수

부울식의 기본 연산과 부울식의 법칙 및 표현 방법을 설명하고 부울 대수에 관련된 전반적인 논제를 확인

부울식

부울 대수

영국의 수학자 부울이 수학적 논리 형태로 소개 → 샤넌이 부울 대수의 기본 개념을 이용하여 회로 함수에 대한 설계로 발전

전기 장치나 컴퓨터 회로는 켜짐과 꺼짐의 두 가지 상태로 나타냄

스위치나 회로는 닫힘과 열림의 두 가지 상태 중 하나인 참 또는 거짓, 1 또는 0으로 표현

0과 1의 조합으로 연산되는 것을 부울 대수

부울식

부울 식은 두 원소를 가지는 집합 A = {0,1}와 이항 연산자 OR, AND /단항 연산자 NOT으로 표현되는 식

‘ (NOT) > · (AND) > + (OR) 의 연산 우선 순위를 가짐

부울식의 법칙

p,q,r을 부울 변수라고 할 때

1. 멱등 법칙 p · p = p p + p = p
2. 항등 법칙 p + 0 = p p · 1 = p
3. 교환 법칙 p + q = q + p p · q = q · p
4. 결합 법칙 p + ( q + r ) = ( p + q ) + r p · ( q**· r** ) = ( p · q ) · r
5. 분배 법칙 p + ( q · r ) = ( p + q ) · ( p + r ) p · ( q + r ) = ( p · q ) + ( p · r )
6. 흡수 법칙 p + ( p · q ) = p p · ( p + q ) = p
7. 역 법칙 p + p = 1 p **·** p =0
8. 보 법칙 (p) = p
9. 우등 법칙 p + 1 = 1 p · 0 = 0
10. 드 모르간의 법칙 ( p + q ) = p · q ( p **·** q ) = p + q

부울식의 표현

부울 함수

부울 변수와 부울 연산자로 구성된 부울식으로 표현

n개의 부울 변수가 있을 때 그 변수들로부터 얻을수 있는 조합은 2^n개

→ n개의 부울 변수로 만들어지는 진리표에서 변수의 각 항을 최소항이라고 함

곱의 합 / 논리합 표준형

부울 함수를 나타나는 데 있어서 최소항들의 합으로 표현하는 것

최소항들은 부울 변수의 곱으로 표현

부울 함수는 부울 변수의 곱의 합으로 표현

부울 함수의 간소화

부울 변수의 최소항들로부터 얻어진 부울 함수는 좀 더 간단하게 만들 수 있음

부울 함수식을 간소하게 표현하는 방법

부울식의 기본 법칙 사용

**카노우맵(카르노 맵)**을 사용

카르노 맵은 진리표를 그래픽으로 나타내는 것으로, 부울 대수식을 간소화하는 데 사용 그리드 형태의 셀로 구성되어 있으며, 각 셀은 입력 조합을 나타냄 셀은 인접한 입력 조합만이 하나의 변수만 다르도록 배열 비슷한 입력을 가진 셀을 그룹화하여 부울식을 간소화

논리 회로 설계

부울 함수로 표현된 식은 컴퓨터에서 사용되는 기본적인 논리 회로를 설계하는 데 활용

컴퓨터 회로를 설계하는 데 있어서 입력과 출력은 논리 회로의 게이트들을 상호 연결함으로써 구성

입력은 부울 변수, 출력은 부울 함수, 부울 연산자는 게이트로 표현

논리 회로

부울 대수의 기본 연산인 논리합, 논리곱, 논리부정 등의 연산을 실행하기 위한 회로로서 논리 게이트라고도 함

논리 회로는 2진 정보를 취급하여 통상 2개 이상의 입력 단자와 하난의 출력 단자로 구성

논리곱 회로

논리곱 회로는 논리곱 조건을 만족시키는 회로로서 2개의 입력 A와 B가 모두 1인 경우에만 출력

논리곱 연산자 AND는 ‘·’ ****로 표현

논리합 회로

논리합 회로는 논리합 조건을 만족시키는 회로로서 입력 A와 B 중 적어도 하나가 1인 경우에 출력이 1이 되는 논리 회로

논리합 연산자는 ‘+’로 표현

논리부정 회로

논리부정 회로는 논리부정 조건을 만족시키는 회로로서 입력 A가 1일 경우 출력이 0이 됨

논리부정 연산자는 ‘’’로 표현

논리회로의 응용

가산기

컴퓨터 중앙처리장치에 있는 산술논리장치 내에는 숫자들을 더하는 기능을 가진 가산기가 내장

이곳에서는 논리 회로를 이용하여 숫자들을 더함

다른 여러 가지 상황에서 사용이 가능하며 부울 대수를 통해 공학적 문제를 해결하거나 컴퓨터의 구조를 이루는 등 많이 사용됨