부울함수의 보수
부울함수 F의 보수는 F바
부울함수 F = X바YZ바 + X바Y바Z 의 보수를 구하시오
F바 = (X바YZ바 + X바Y바Z)바 = (X바YZ바)바 ● (X바Y바Z)바
= (X + Y바 + Z) ● (X + Y + Z바)
● = 도트 라고 읽는다
드모르간 정리를 이용
- AND와 OR를 서로 바꾸고, 각 변수의 보수를 취한다.
1. 부울대수
2. 부울함수의 정규형 및 표준형(정규형을 간략하게 만든것)
1) 정규형 (입력변수 XYZ 인 3변수가 모두 포함되서 표현되는 것)
- 부울함수를 최소항의 합(sum of minterm) 이나 최대항의 곱(product of maxterm) 으로 표현한 것
1-1) 최소항과 최대항
2개의 논리변수 X, Y가 있을 때
최소항: 논리곱(AND)으로 표현되는 4개(XY, XY바, X바Y, X바Y바)의 항 (그 결과가 논리값 1)
최대항: 논리합(OR)으로 표현되는 X + Y, X바 + Y, X + Y바, X바 + Y바 의 네 가지 항 (그 결과가 논리값 0)
최소항과 최대항은 서로 쌍대 관계가 있다.
1-2) 최소항
- n개의 논리변수로 구성된 부울함수에서 최소항이란
* 각 변수의 문자 1개씩 모두 n개의 문자의 논리곱 항으로서
* 그 결과가 논리값 1 인 경우
* Mj로 표시 ex) 2개의 논리변수 X, Y의 경우에는 m0, m1, m2, m3로 4가지라고 표현으로 쓸 수 있다.
(그림 최소항 진리표)
1-3) 최대항
- n개의 논리변수로 구성된 부울함수에서 최대항이란
* 각 변수의 문자 1개씩 모두 n 개의 문자의 논리합 항으로서
* 그 결과가 논리값 0 인 경우
* Mj 로 표시
(그림 최대항 진리표)
1-4) 진리표를 부울함수로 표현 (최소항의 합 형태로)
(그림 진리표를 부울함수로 표현(최소항의 합))
최소항을 각각 모두 구한 뒤 OR 결합 (합) 으로 묶어주면 된다.
1-5) 진리표를 부울함수로 표현 (최대항의 곱 형태로)
(그림 진리표를 부울함수로 표현(최대항의 곱))
논리값이 0 이되는 최대항을 모두 구한 뒤 논리곱 연산자로 모두 결합해주면 된다.
2) 최소항의 합으로 부울함수 표현
- 진리표에서 출력이 1 이 되는 최소항들을 논리합(OR)으로 묶으면 정규형 부울함수가 구해진다.
진리표에서 출력이 1이 되는 항들만 골라서 OR(+로 묶는다)해주면 된다.
진리표에서 출력 F가 1이 되기 위해서는 001, 100, 111 중에 하나이면 된다.
001 = X바Y바Z , 100 = XY바Z바, 111 = XYZ
따라서 F = X바Y바Z + XY바Z바 + XYZ
- 부울함수 F = X + YZ바 를 최소항의 합으로 표현하시오
3) 최대항의 곱으로 부울함수 표현
- 진리표에서 출력이 0 이 되는 최대항들을 논리곱(AND)으로 묶으면 정규형 부울함수가 구해진다.
진리표에서 출력이 0이 되는 항들을 AND로 표현해 준다.
진리표에서 출력 F가 0이 되기 위해서는 000, 010, 011, 101, 110 중에 하나이면 된다.
따라서 F = (X + Y + Z)(X + Y바 + Z)(X + Y바 + Z바)(X바 + Y + Z바)(X바 + Y바 + Z)
- 부울함수 F = XY + X바Z를 최대항의 곱으로 표현하시오.
다른 표현으로 F = M0 · M2 · M4 · M5
F(X,Y,Z) = πM(0,2,4,5)
4) 표준형
- 부울함수를 표현하는 또 다른 형태(간소화된 형태)
- 각 항은 하나 또는 그 이상의 문자로 구성
- 곱의 합(sum of products) 과 합의 곱(product of sums)의 형태
정규형은 진리표에서 바로 얻을 수 있지만, 최소항 또는 최대항에 모든 변수가 포함되어 있어 부울함수의 간소화에는 부적합
따라서 정규형으로부터 간소화된 표준형으로 변환이 필요
4-1) 곱의 합
(표준형을 구하기위해서는 정규형을 먼저 구한 후 정규형을 간소화하면 표준형 부울함수가 도출된다.)
'방송통신대학교12 > 컴퓨터과학과 [3학년 1학기]' 카테고리의 다른 글
[데이터베이스] 6강 정규형의 적용 (0) | 2018.05.17 |
---|---|
[데이터베이스] 5강 정규화 기초 (0) | 2018.05.15 |
[데이터베이스] 4강 데이터베이스 언어 (0) | 2018.03.21 |
[알고리즘] 1강 알고리즘 소개 (0) | 2018.03.19 |
[데이터베이스] 3강 관계형 모델 (0) | 2018.03.19 |
댓글0