위 그림의 (a)를 살펴보자. 어떤 logic circuit을 그냥 사각형으로 단순화하여 보여주고 있고, input으로는 A, B, C가 들어가고, output으로 f가 나오고 있다. 우리는 (b)와 같이 A, B, C와 f, f'의 관계를 truth table을 만들어 볼 수 있다. 우리는 이 logic circuit을 AND와 OR gate를 이용하여 나타내고 싶다. 그러기 위해서는 이 logic circuit을 어떤 boolean expression으로 나타낼 수 있어야 한다. 여기에 truth table을 이용하게 되는 것이다. Truth table을 살펴보면 ABC가 각각 011, 100, 101, 110, 111일 경우에만 f = 1의 값을 갖는다. 다시말해서 ABC가 011 이거나 100 이..

Methods for Determining if an Equation is Valid 모든 variable combination에 대해서 어떤 equation이 유효한지를 알아보는 방법은 여러가지가 있다. 여기서 지금까지 배운 내용을 바탕으로 몇 가지를 정리해보면, 1. Truth table을 만들고, 모든 variable combination에 대해서 좌우변이 동일한 값을 갖는지 확인한다. 이 방법은 variable의 개수가 늘어날 수록 검사해야 하는 경우의 수가 기하급수적으로 늘어나게 되므로, 상당히 비효율적인 방법이라고 할 수 있다. 2. 지금까지 배운 여러 theorem을 이용하여 equation의 한 변을 다른 한변과 동일하게 만든다. 3. 양변을 개별적으로 simplify해서 같은지 확인한다...

Exclusive-OR (XOR) Exclusive-OR, 이하 XOR은 위와 같이 정의된다. Operator의 형태는 덧셈기호를 원으로 둘러 싼 모습을 하고 있다. 같은 숫자일 경우에는 0을, 서로 다른 숫자일 경우에는 1을 나타낸다. XOR gate의 모양은 위와 같다. OR gate의 왼쪽에 둥근 호를 더해놓은 형태를 하고 있다. 한편, XOR operator는 아래와 같이 풀어 쓸 수 있다. 위 식에 대한 증명은 생략한다. XOR에 대해서는 다음과 같은 유용한 공식을 사용해 볼 수 있다. Basic Theorems of XOR 대부분의 공식은 truth table을 이용하거나, 혹은 위에서 언급한 관계식을 이용하면 증명 된다. Equivalence Operation (Exclusive NOR; X..

Basic of Basic 이 포스트에서는 boolean algebra의 가장 기초적인 법칙들에 대해서 다루도록 하겠다. 먼저 다음에 소개될 법칙들은, 그 중에서도 가장 기본적인 법칙으로 그 증명은 그냥 X에 0 또는 1을 넣는 것이면 된다. (여기서 부가적인 증명은 하지 않는다.) 또한 X 대신 어떤 expression을 넣는다 하더라도 아래의 법칙들은 모두 true이다. Operations with 0 and 1 X + 0 = X X + 1 = 1 X · 0 = 0 X · 1 = X Idempotent Laws X + X = X X · X = X Involution Law (X')' = X Laws of Complementarity X + X' = 1 X · X' = 0 Commutative Law ..

앞에서 배운 3가지 basic operation들을 조합하면 다양한 expression들을 만들어 낼 수 있다. Expression은 표현식, 즉, 등호가 포함되지 않은 여러개의 항으로 이루어진 식이다. 위의 그림을 보면 AB' + C, (A + C)(B' + C) 등과 같이 여러개의 operator와 operand들을 조합해서 expression을 만들어낼 수 있다. 이러한 expression은 A, B, C... 등의 variable이 어떤 값을 갖느냐에 따라 expression 전체가 나타내는 값이 달라진다. 이를 알아보기 쉽게 표현한 것이 truth table이며 '진리표'라고 풀이한다. 일반적으로 왼편에 수식에 들어있는 변수들의 모든 가능한 경우를 나열한 다음 우측에 expression과 함께 ..