부울 식 및 함수

부울 대수는 논리 대수입니다. 두 개의 개별 값, 0 (False) 및 1 (True)을 가질 수있는 변수를 다룹니다. 논리적으로 중요한 작업. 상징 논리를 조작하는 가장 초기의 방법은 George Boole에 의해 발명되었으며 이후에 Boolean Algebra로 알려지게되었습니다.

부울 대수는 이제 스위칭 이론, 기본 전자 회로 구축 및 디지털 컴퓨터 설계에 폭넓게 적용 할 수있어 컴퓨터 과학에서 없어서는 안될 도구가되었습니다.

부울 함수

A Boolean function는 특수한 종류의 수학 함수 $ f : X ^ n \ rightarrow X $ n 차, 여기서 $ X = \ lbrace {0, 1} \ rbrace $는 부울 도메인이고 n은 음이 아닌 정수입니다. 부울 입력에서 부울 출력을 파생하는 방법을 설명합니다.

Example−하자, $ F (A, B) = A'B '$. 이것은 순서가 지정된 부울 변수 쌍에서 $ \ lbrace {0, 1} \ rbrace $ 세트까지의 차수 2 함수입니다. 여기서 $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ 및 $ F (1, 1) = 0 $

부울 식

A Boolean expression항상 부울 값을 생성합니다. 부울 표현식은 부울 상수 (True 또는 False), 부울 변수 및 논리 연결의 조합으로 구성됩니다. 각 부울 표현식은 부울 함수를 나타냅니다.

Example − $ AB'C $는 부울 표현식입니다.

부울 ID

이중 보완 법

$ \ sim (\ sim A) = A $

보완 법

$ A + \ sim A = 1 $ (OR 양식)

$ A. \ sim A = 0 $ (AND 형식)

멱등 법

$ A + A = A $ (OR 양식)

$ A. A = A $ (AND 양식)

신분법

$ A + 0 = A $ (OR 양식)

$ A. 1 = A $ (AND 양식)

지배 법

$ A + 1 = 1 $ (OR 양식)

$ A. 0 = 0 $ (AND 형식)

교환법

$ A + B = B + A $ (OR 양식)

$ A. B = B. A $ (및 양식)

연합 법

$ A + (B + C) = (A + B) + C $ (OR 양식)

$ A. (B. C) = (A. B). C $ (AND 양식)

흡수 법

$ A. (A + B) = A $

$ A + (A. B) = A $

단순 화법

$ A. (\ sim A + B) = A. B $

$ A + (\ sim A. B) = A + B $

배급 법

$ A + (B. C) = (A + B). (A + C) $

$ A. (B + C) = (A. B) + (A. C) $

드 모건의 법칙

$ \ sim (A. B) = \ sim A + \ sim B $

$ \ sim (A + B) = \ sim A. \ sim B $

정식 형식

부울 표현식에는 두 종류의 표준 형식이 있습니다.

  • minterms 합계 (SOM) 형식
  • maxterms (POM) 양식의 제품

SOM (Sum of Minterms) 또는 SOP (Sum of Products) 양식

minterm은 직접 또는 보완 된 형태로 취해진 모든 변수의 산물입니다. 모든 부울 함수는 1 분 항의 합으로 표현할 수 있으며, 역함수는 0 분 항의 합계로 표현할 수 있습니다. 그 후,

F (변수 목록) = ∑ (1 분 지수 목록)

F '(변수 목록) = ∑ (0 분 인덱스 목록)

기간 Minterm
0 0 0 x'y'z ' m 0
0 0 1 x'y'z m 1
0 1 0 x'yz ' m 2
0 1 1 x'yz m 3
1 0 0 xy'z ' m 4
1 0 1 xy'z m 5
1 1 0 xyz ' m 6
1 1 1 xyz m 7

Example

하자 $ F (X, Y, Z) = X 'Y'Z '+ XY'Z + XYZ '+ XYZ $

또는 $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $

그 후,

$ F (x, y, z) = \ sum (0, 5, 6, 7) $

이제 우리는 $ F (x, y, z) $의 보수를 찾을 것입니다.

$ F '(x, y, z) = x'yz + x 'y'z + x 'yz'+ xy 'z'$

또는 $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $

그 후,

$ F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4) $

Maxterms의 곱 (POM) 또는 합계의 곱 (POS) 양식

maxterm은 직접 또는 보완 형식으로 취해진 모든 변수의 추가입니다. 모든 부울 함수는 0- 최대 항의 곱으로 표현 될 수 있으며 함수의 역함수는 1- 최대 항의 곱으로 표현 될 수 있습니다. 그 후,

F (변수 목록) = $ \ pi $ (0-maxterm 인덱스 목록).

F '(변수 목록) = $ \ pi $ (1- 최대 항 인덱스 목록).

기간 Maxterm
0 0 0 x + y + z 0
0 0 1 x + y + z ' 1
0 1 0 x + y '+ z 2
0 1 1 x + y '+ z' 3
1 0 0 x '+ y + z 4
1 0 1 x '+ y + z' 5
1 1 0 x '+ y'+ z 6
1 1 1 x '+ y'+ z ' 7

하자 $ F (X, Y, Z) = (X + Y + Z에서). (x + y + z '). (x + y '+ z). (x '+ y + z) $

또는 $ F (x, y, z) = M_0. M_1. M_2. M_4 $

그 후,

$ F (x, y, z) = \ pi (0, 1, 2, 4) $

$ F ''(x, y, z) = (x + y '+ z'). (x '+ y + z'). (x '+ y'+ z). (x '+ y'+ z ') $

또는 $ F (x, y, z) = M_3. M_5. M_6. M_7 $

그 후,

$ F '(x, y, z) = \ pi (3, 5, 6, 7) $

논리 게이트

부울 함수는 논리 게이트를 사용하여 구현됩니다. 다음은 논리 게이트입니다-

NOT 게이트

NOT 게이트는 단일 비트 입력을 단일 비트 출력으로 반전합니다.

~ A
0 1
1 0

AND 게이트

AND 게이트는 모든 입력이 높을 때만 높은 출력을 제공하고 그렇지 않으면 낮은 출력을 제공하는 논리 게이트입니다. 점 (.)은 AND 연산을 표시하는 데 사용됩니다.

AB
0 0 0
0 1 0
1 0 0
1 1 1

OR 게이트

OR 게이트는 입력 중 하나 이상이 높으면 높은 출력을 제공하는 논리 게이트입니다. 더하기 (+)는 OR 연산을 표시하는 데 사용됩니다.

A + B
0 0 0
0 1 1
1 0 1
1 1 1

NAND 게이트

NAND 게이트는 모든 입력이 높을 때만 낮은 출력을 제공하고 그렇지 않으면 높은 출력을 제공하는 논리 게이트입니다.

~ (AB)
0 0 1
0 1 1
1 0 1
1 1 0

NOR 게이트

NOR 게이트는 두 입력이 모두 낮 으면 높은 출력을 제공하고 그렇지 않으면 낮은 출력을 제공하는 논리 게이트입니다.

~ (A + B)
0 0 1
0 1 0
1 0 0
1 1 0

XOR (독점 OR) 게이트

XOR 게이트는 입력이 다르면 높은 출력을 제공하고 그렇지 않으면 낮은 출력을 제공하는 논리 게이트입니다.

A⊕B
0 0 0
0 1 1
1 0 1
1 1 0

X-NOR (독점 NOR) 게이트

EX-NOR 게이트는 입력이 동일하면 높은 출력을 제공하고 그렇지 않으면 낮은 출력을 제공하는 논리 게이트입니다.

A X-NOR B
0 0 1
0 1 0
1 0 0
1 1 1