논리회로 간소화 / 불대수 / 카르노맵

논리회로란? : 전자공학에서 논리 회로(영어: logic gate)는 불 대수를 물리적 장치에 구현한 것으로, 하나 이상의 논리적 입력값에 대해 논리 연산을 수행하여 하나의 논리적 출력값을 얻는 전자회로를 말한다. AND, OR, NOT의 기본 불 대수를 수행하며, 이 기본 불 대수들의 결합으로 복합적인 논리 기능을 수행한다. (출처 : 위키피디아 - 논리회로)

 

부울대수 : 순서론과 추상대수학, 논리학에서, 불 대수(Boole代數, 영어: Boolean algebra)는 어떤 명제의 참과 거짓을 이진수 1과 0에 대응시켜서 명제와 명제간의 관계를 수학적으로 표현하는 것이다. (출처 : 위키피디아 - 불대수)

 

 

전기,전자, 의공학 필기/실기에서 빠질 수 없는 문제로 논리회로 및 논리회로 간소화 문제입니다.

처음 공부할 때 상당히 힘들었던 기억이 있었습니다. 

익숙해지면 큰 어려움 없이 계산하지만 왜이리 쉽지 않던지..

 

 

논리식은 0과 1을 이용한 계산식이라고 생각하면 쉽습니다.

예를 들면 1+1=1 을 예시로 볼 수 있습니다.

따라서 이 부분을 표로 정리하면 다음과 같이 볼 수 있습니다.

논리 대수 연산 진리표

사실 진리표만 있어도 계산을 할 수 있지만,

간략화를 더 쉽게 해주기 위해 부울 대수의 기본정리표를 외워주면 좋습니다.

 

 

부울대수 기본정리 표

* 흡수 법칙 증명 :
#1 : A+A·B = A·(1+B) = A [1+B = 1 이용]
#2 : A·(A+B)=AA+AB = A+AB = A·(1+B) = A

* 분배 법칙 증명 : 

#1  : A+B·C = (A+B)(A+C)
       [우변 이용] AA+AC+AB+BC = A(1+C+B) + BC = A+BC [bec, 1+C+B = 1]
       -암기하는게 편하긴 하지만, 알아두면 확실히 좋습니다.
#2 : A+A'B = A(1+B) +A'B = A+ AB + A'B = A+B(A+A') = A+B [bec, 보원법칙]
#3 : A·(A'+B)=AA'+A·B=A·B

이 정도만 익숙하게 하면 큰 문제 없이 논리 문제를 풀 수 있습니다.

* 그래서 준비한 작은 문제점들을 해결하기 위한 팁 

 

* 컨센서스법칙

AB + BC + A'C = AB + A'C   
(A+B)(B+C)(A'+C)=(A+B)(A'+C)

임의의 식이 위와 같은 형태를 띄고 있을 때 필요없는 항을 소거 할 수 있다. (진하지 않은 BC, (B+C)가 해당)

즉, 중복된 항을 제거하는 방법으로 식의 값이 바뀌지 않는 항임.

 

증명 :
#1 : AB + BC + A'C = AB + A'C   
     =AB + BC + A'C =AB + A'C + (A+A')BC = (AB+ABC) + (A'C + A'BC) = AB(1+C) + A'C(1+B) 
     =AB + A'C

#2 :  (A+B)(B+C)(A'+C)=(A+B)(A'+C)
       =ABC + AC + A'B + A'BC = AC(1+B) + A'B(1+C) = AC + A'B = AC+A'B+BC [컨센서스법칙]
       = 0+AC+A'B+BC = A'A+AC+A'B+BC = A(A'+C)+B(A'+C) =(A+B)(A'+C)


그 밖의 연산 법칙 

연산 우선 순위  : NOT > AND > OR 순     

 

 

논리회로 입니다.

전기/전자 계통 시험에 항상 나오는 문제이고 틀리면 속이 쓰린 문제중 하나입니다.

 

출처 : 위키피디아 - 논리회로 (https://url.kr/yjg95a)

다행히, 논리회로 기호를 논리식으로 대응해서 정리하면 쉽게 정리 할 수 있습니다.

 

논리회로는 설명도 중요하지만 예시 문제를 풀어보면서 익히는게 가장 빠릅니다.

 

의공기사 15년도 3월 필기 https://krakens.tistory.com/55

가장 좌측에는 AND게이트이므로 AㆍB , CㆍD, E 로 식을 나타낼 수 있고, 그 다음으로는 OR게이트로 모이므로
F=( AㆍB + CㆍD+ E)로 나타낼 수 있습니다.

의공기사 17년도 9월 논리회로 필기

가장 좌측부터 순서대로 가겠습니다.
AND 게이트 이고, 각각  AㆍB  / BㆍC 로 나타낼 수 있습니다.
OR 게이트에서 두 변수가 만나기에 Y=(AㆍB)+(BㆍC) 로 나타낼 수 있습니다.

 

카르노맵 (카노맵)

 

논리식이 전개되어있고, 논리식을 축약하라는 문제들도 자주 출제가 됩니다.

물론, 위에 방법으로 해결을 해도 문제는 없겠지만 카르노맵을 이용하는것이 더 효율적이라 생각됩니다.

 

카르노 맵(영어: Karnaugh map, 간단히 K-map)은 논리 회로 용어로, 불 대수 위의 함수를 단순화 하는 방법이다. 불 대수에서 확장된 논리 표현을 사람의 패턴인식에 의해 연관된 상호관계를 이용하여 줄이는 방법이다.

(출처 : 위키피디아,카노맵)

 

작성 방법

 

에를들어 F=A'B'C' + A'B'C+A'BC'+AB'C+ABC'+ABC 를 축약해보면

 

= A'B' + BC' + AC 로 축약이 가능하지만, 간략화하는데 많은 노력이 들어갑니다. 

 

하지만 카르노맵을 이용하면 조금 더 직관적이고 간단하게 간략화가 가능하기에 반드시 알아둘 필요가 있습니다.

카르노맵을 설명하기 위해서 예시를 들어서 설명하도록 하겠습니다.

 

• 2변수 카르노맵
  

  

  (좌) 진리표 (우) 카르노맵

  
  간단히 설명하면, F라는 함수의 진리표(좌측)를 카르노맵(우측)으로 표현하였습니다.
  (카르노맵을 표현시 0과 1의 순서에 유의해주세요)
  
  카르노맵 표현을 보신다면 a b c d 가 표안으로 들어온것을 알 수 있습니다.
  
  따라서 
  

  

  0과 1의 진리값을 넣어 표현하면 이런 방식으로 표현이 가능하게 됩니다.
  
  진리표를 카르노맵으로 옮기는 방안은 간단하죠?
  
  다음은 간소화 하는 방법입니다.
  
  카르노맵에서는 F가 1인 인접한 그룹을 묶어낼 수 있으며, 이때는 직사각형태로 2ⁿ개씩 묶어야 됩니다.
  

  

  빨간색 부분을 나타내면 A'B+AB = B(A'+A) = B
  파란색 부분을 나타내면 AB'+AB =A(B'+B) = A  로 표현할 수 있고 
  
  따라서 F= A+B 로 간소화 할 수 있습니다.
  
  
• 3변수 카르노맵
  

  

  

  3변수 카르노맵도 크게 달라진 점은 없지만, 카르노맵으로 표현시 변수의 순서에 주의해주세요
  물론 3변수에서도 마찬가지로  2ⁿ개씩 인접한 1의 그룹을 묶어줘야 합니다.
  
  

  

  출처 : https://www.electricaltechnology.org/wp-content/uploads/2018/04/3-Variable-K-map-groups-of-2-4-8-cells-having-1s-or-0s.png

  예시로 위와 같이 묶는 방법들이 존재합니다.

 

 

• 4변수 카르노맵
  
  물론 4변수 카르노맵도 마찬가지이며
  

  

  출처 : https://www.allaboutcircuits.com/uploads/articles/KMap_Figure3.jpg

  

  출처 : https://flylib.com/books/1/448/1/html/2/chapter02.doc.anc142.gif

  조금 특이하게 묶는 방식으로는 (a)에서 보이는 네귀퉁이를 한번에 묶는 방식,
  아래 사진처럼 4개씩 묶는 방법이 있겠습니다.
  
  

카르노맵을 풀어주는 프로그램을 소개하겠습니다.

Karnaugh Map Minimizer

프로그램이 심플하고 나름 이용하기 쉽습니다.
위 사진으로 예시를 들면 A와 BC로 표현한 카르노맵입니다.
좌측 F에 원하는 값을 넣어주도록 하겠습니다.

이제 solve 버튼을 눌러주면

간소화식을 풀어줍니다.

카르노맵을 검증해보면 맞는지 확인이 가능하겠죠?

A'B'C'와 A'BC'를 묶어 주고, A'B'C와 AB'C를 묶어주도록 하겠습니다.
A'B'C'+A'BC' = A'C'(B'+B) = A'C'
A'B'C+AB'C = B'C(A+A') = B'C  이므로
F=A'C' + B'C 의 값이 나옵니다.

나름 정확하게 풀리는 프로그램입니다.
모르는 문제가 나온다면 도움이 되었으면 좋겠습니다.