| English | 의미 |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | 부울 대수 |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | 데 모르강의 법칙 |
| Karnaugh map/ˈkɑːnɔː mæp/ | 카노 도표 |
| truth table/truːθ ˈteɪbl/ | 진표 |
| absorption/əbˈsɔːpʃn/ | 흡수법칙 |
| Gray code/ɡreɪ kəʊd/ | 그레이 코드 |
디지털 시대를 구축한 석사 학위 논문
- 1937년 21세의 학생 클로드 섀은 자신이 연구하던 전화 릴레이가 80년 전 조지 불이 참과 거짓에 대한 추론을 위해 발명한 대수학의 결과와 동일한 عمل을 한다는 것을 발견했습니다.
- 스위치가 부울 변수라면 회로는 수식이며, 이 수식을 간소화하면 회로에서 게이트를 제거할 수 있습니다. 게이트가 적으면 비용이 낮고 속도가 빠르며 전력 소모도 줄어듭니다.
- 그의 학위 논문을 세기의 가장 중요한 논문으로 불립니다. 이 페이지의 모든 내용은 그 하나의 아이디어를 도구로 사용한 것입니다.
- 이 수업에서는 부울 대수, 데摩根 법칙, 그리고 눈으로 같은 작업을 수행하는 카르나우 지도를 다룹니다.
표기법과 법칙
+는 OR(OR)을 의미하고,·는 AND(AND)를 의미하며 보통 생략됩니다. 또한 유편(bar)은 NOT(NOT)을 의미합니다. 진리표는 이를 포괄적으로 설명합니다.- 식별자(Identity): $A + 0 = A$ 및 $A \cdot 1 = A$. 영(Null): $A + 1 = 1$ 및 $A \cdot 0 = 0$.
- 동일 법칙: $A + A = A$. 역 법칙: $A + \overline{A} = 1$ 및 $A \cdot \overline{A} = 0$.
- 흡수 법칙: $A + A\cdot B = A$. 왜냐하면 $A$가 참이면 $B$와 상관없이 전체 식이 참이기 때문입니다.
각 부울 법칙과 그것이 말하는内容进行 짝매우십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
이 법칙들은 회로를 설계하기 전에 부호식(부동자 식)을 대수적으로 단순화할 수 있게 해줍니다.
흡수법칙에 따라, A + A·B는 ____로 단순화됩니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
A가 참이면 B의 값과 관계없이 전체 식은 참이고, A가 거짓이면 두 항 모두 거짓입니다. B는 결과에 영향을 미칠 수 없습니다.
드모르간의 법칙(De Morgan's laws)
- 데摩根 법칙은 시험에서 이름으로 사용하도록 요구되는 두 가지 법칙입니다:
- 말로 된 요령은 다음과 같습니다: 전체를 negation(반전)하고, AND와 OR를交换(교체)하며, 각 피연산자를 반전합니다.
- 이들은 실용적으로 중요하여 어떤 식도 NAND 게이트 또는 NOR 게이트만으로 다시 쓸 수 있게 하며, 단일 게이트를 반복적으로 사용하여 제조한 칩은 생산 비용이 더 저렴합니다.
두 가지 식, 하나의 진리표
부울 대수
A·B, A+B, Ā …
부울 대수는 단순히 진리표를 비교하여 식으로 표현된 게이트들입니다.
데摩根 법칙에 의해, $\overline{A \cdot B}$는 다음과 같습니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
전체 부정, operator를 AND→OR로 교체, 각 피연산자 부정: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
부호식에 데 Morgan 법칙을 적용할 때 다음 단계들이 포함됩니다? 모두 선택하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
전체 부정, operator 교체, 각 부분 부정. AND와 OR는 교환법칙이 성립하므로 순서는 무관합니다.
worked example: 간소화하고 게이트 수 세기
- $Z = A\cdot B + A\cdot\overline{B}$를 간소화하고 saving(절감 효과)을 말하세요.
- $A$를 인수로 빼내면: $Z = A\cdot(B + \overline{B})$. 역 법칙에 의해 $B + \overline{B} = 1$이므로,结果是 $Z = A \cdot 1 = A$입니다.
- 원래 식은 두 개의 AND 게이트, 하나의 NOT 게이트, 하나의 OR 게이트가 필요하여 총 네 개의 게이트가 필요합니다. 간소화된 식은 게이트가 하나도 필요 없으며, 단순히 입력 $A$만 있으면 됩니다.
- 항상 간소화가 가져오는 이점을 명시해야 합니다: 게이트 수가 줄어들므로 비용이 낮고 속도가 빠르며 전력 소모가 적은 회로가 됩니다.
$A\cdot B + A\cdot\overline{B}$를 간소화하십시오.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
A를 공통인수로因数提取: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B에는 AND 2개, NOT 1개, OR 1개가 필요합니다. 이 식의 단순화된 형태에는 몇 개의 게이트가 필요합니까?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
simplement하게 A만 남으므로 출력은 입력과 동일하며 게이트가 전혀 필요 없습니다. 총 4개의 게이트가 절약되었습니다.
카르나우 지도
- 카르나우 지도는 진리표에서 인접한 1들을 그룹화하여 식을 간소화합니다.
- 행과 열은 Gray code(그레 코드) 순서인
00, 01, 11, 10로 표시되어 있어 인접한 셀은 정확히 하나의 변수만 다릅니다. 이것이 핵심 비결입니다: 대수를 인접성으로 시각화하게 해줍니다. - 출력이 1인 각 셀에 1을 배치한 후, 변의 길이가 2의 거듭제곱인 1들의 사각형 그룹을 찾으십시오: 1, 2, 4, 8. 그룹은 가장자리에서 감싸질 수 있습니다(wrap around).
직사각형이 클수록 식이 단순해집니다
카르나우 도표는 다음을 통해 부등식을 단순화합니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
인접한 1(그레이 코드 순서로)을 2의 제곱 크기의 사각형으로 그룹화하며, 각 그룹은 단순화된 항이 됩니다.
왜 카르나우 도표의 행과 열은 00, 01, 11, 10으로 표시하고, 00, 01, 10, 11으로 표시되지 않는가?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
그레이 코드 순서는 대수적 인접성을 물리적 인접성으로 만듭니다. 계산 순서대로라면 그룹화 규칙이 작동하지 않습니다.
그룹 읽기
- 그룹 내부에서 변하지 않는 변수는 식에 남고, 변하는 변수는 사라집니다.
- 따라서 2개의 그룹은 변수 하나를, 4개의 그룹은 변수 두 개를, 8개의 그룹은 변수 세 개를 제거합니다. 그룹이 클수록 식이 단순해집니다.
- 가능한 적은 수의 큰 그룹으로 모든 1을 cover(덮음)한 뒤, 그룹 식들을 OR로 합칩니다. 그룹이 overlap(중복)될 수 있으며, 중복往往是 더 큰 그룹을 형성하는 데 필수적입니다.
카르노 도표에서 더 큰 크기의 인접한 1 그룹은 더 많은 변수를 소거하여 더 간단한 항을 생성합니다(2 그룹은 변수 하나를, 4 그룹은 변수 두 개를 소거합니다).
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
인접한 1을 그레이 코드 순서에 따라 2의 제곱 크기의 사각형으로 그룹화하면, 그룹이 클수록得到一个 더 간단한 항이 됩니다.
카르나우 도표를 사용하여 단순화하는 단계를 순서대로 나열하십시오.
난이도 3/5 · 200 코인 + 오늘 첫 완료 시 소액 보너스
Gray code, ones, 가장 큰 그룹, 변화하는 요소 제거, 또는 항(terms)을 OR합니다. 모든 1를 덮을 수 있는 최소且最大の 그룹을 사용하십시오.
worked example: 두 변수 지도 읽기
- $A$과 $B$에 대한 카르나우 지도에는 cell(셀) $\overline{A}B$과 $AB$에 1이 있습니다. 간소화하십시오.
- 두 1은 인접해 있습니다: $B = 1$ 열을 공유하므로 2개의 직사각형 그룹으로 묶일 수 있습니다.
- 그 그룹 내에서 $B$는 내내 1로 유지되지만, $A$는 0에서 1로 바뀝니다. 변하는 변수는 사라집니다.
- 따라서 전체 식은 단순히 $Z = B$입니다. 이는 간소화되지 않은 sum of products(합의 곱), 즉 $\overline{A}B + AB$와 비교해 볼 때 NOT 게이트 하나, AND 게이트 두 개, OR 게이트 하나가 필요하다는 것과 대비됩니다.
어떤 방법을 사용할 것인가
- 부울 대수는 정확하며 변수 수에 상관없이 작동하지만, 어떤 법칙이 적용되는지를 찾아야 합니다.
- 카르나우 지도는 기계적인 방법이며 두 개부터 네 개의 변수까지 틀리기 어렵습니다. 이는 시험 문제 설정 범위이며, 가장 큰 그룹을 직접 보여줍니다.
- 둘 다 같은 답을 줍니다. K-map의 장점은 간소화가 법칙을 search(검색)하는 것이 아니라 look(보기)가 된다는 점입니다.
놓칠 수 있는 점
- 데摩根 법칙은 전체를 반전하고, 연산자를 exchange(교환)하고, 각 부분을 반전하는 것입니다. 연산자만 바꾸는 것은 고전적인 반쪽 정답입니다.
- K-map의 행은 Gray code 순서인
00, 01, 11, 10여야 합니다. 이진 세는 순서라면 인접성이 틀려서 그룹화가 실패합니다. - 그룹 크기는 2의 거듭제곱이어야 하며 가장자리를 wrap around(둘러 감)할 수 있습니다. 3개의 그룹은 유효한 그룹이 아닙니다.
- 간소화의 목적이 무엇인지 말하세요: 게이트 수가 줄어들므로 비용이 낮고 속도가 빠르며 전력 소모가 적습니다.
이해했습니다
- 부울 대수는 식을 더 적은 항으로 rewrites(재작성)하므로, 회로에서 더 적은 게이트가 필요합니다.
- 데摩根: $\overline{A + B} = \overline{A} \cdot \overline{B}$ 및 $\overline{A \cdot B} = \overline{A} + \overline{B}$; 흡수: $A + AB = A$; $A\cdot B + A\cdot\overline{B} = A$
- 카르나우 지도는 진리표에서 인접한 1들을 그룹화하며, 행과 열이 Gray code 순서로 되어 있어 이웃들이 하나의 변수만 다릅니다.
- 그룹 내에서 변하는 변수는 사라지므로 큰 그룹일수록 식이 단순해집니다: 가능한 적은 수의 큰 그룹으로 모든 1을 cover(덮음)하십시오.