程序代写代做代考 Review: Boolean Algebra, Truth Tables, Gates

Review: Boolean Algebra, Truth Tables, Gates

Boolean Algebra Axioms

1. Binary field: 𝐵 = 0 𝑖𝑓 𝐵 ≠ 1 𝑎𝑛𝑑 𝐵 = 1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

2. NOT (denoted by ¬/ −): �̅� = 0 𝑖𝑓 𝑋 = 1 𝑎𝑛𝑑 �̅� = 1 𝑖𝑓 𝑋 = 1

3. AND (𝐝𝐞𝐧𝐨𝐭𝐞𝐝 𝐛𝐲 ∙/∗) : 𝑋 ∙ 𝑌 = 1 𝑖𝑓 𝑋 = 𝑌 = 1 𝑎𝑛𝑑 𝑋 ∙ 𝑌 = 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

4. OR (denoted by +): 𝑋 + 𝑌 = 0 𝑖𝑓 𝑋 = 𝑌 = 0 𝑎𝑛𝑑 𝑋 + 𝑌 = 1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Notes:

 The operators AND, OR, NOT are universal or functionally complete in that they can be used to

express all Boolean functions

 Order of precedence is NOT, AND, OR.

 The symbols used to denote these operations (e.g. + for OR) are not universally standard. You

may see some different notations such as ∨ for OR and ^ for AND

Principle of Duality

If 0 and 1 and the operators ∙ (AND) and +(OR) are interchanged, the resulting statement is correct and

equivalent to the original.

Theorems

Name OR (+) Version AND (∙) Version

Idempotent 𝐴 + 𝐴 = 𝐴 𝐴 ∙ 𝐴 = 𝐴
Commutative 𝐴 + 𝐵 = 𝐵 + 𝐴 𝐴 ∙ 𝐵 = 𝐵 ∙ 𝐴

Associative (𝐴 + 𝐵) + 𝐶 = 𝐴 + (𝐵 + 𝐶) (𝐴 ∙ 𝐵) ∙ 𝐶 = 𝐴 ∙ (𝐵 ∙ 𝐶)

Distributive 𝐴 + (𝐵 ∙ 𝐶) = (𝐴 + 𝐵) ∙ (𝐴 + 𝐶) 𝐴 ∙ (𝐵 + 𝐶) = (𝐴 ∙ 𝐵) + (𝐴 ∙ 𝐶)

Identity 𝐴 + 0 = 𝐴 𝐴 ∙ 1 = 𝐴

Null 𝐴 + 1 = 1 𝐴 ∙ 0 = 0
Complement 𝐴 + �̅� = 1 𝐴 ∙ �̅� = 0
Double
Negation/Involution

(�̅�)̅̅ ̅̅̅ = 𝐴

Covering 𝐴 + (𝐴 ∙ 𝐵) = 𝐴 𝐴 ∙ (𝐴 + 𝐵) = 𝐴

Combining (𝐴 + 𝐵) ∙ (𝐴 + �̅�) = 𝐴 (𝐴 ∙ 𝐵) + (𝐴 ∙ �̅�) = 𝐴
Consensus (𝐴 + 𝐵) ∙ (�̅� + 𝐶) ∙ (𝐵 + 𝐶)

= (𝐴 + 𝐵) ∙ (�̅� + 𝐶)
(𝐴 ∙ 𝐵) + (�̅� ∙ 𝐶) + (𝐵 ∙ 𝐶)

= (𝐴 ∙ 𝐵) + (�̅� ∙ 𝐶)
DeMorgan’s (𝐴 + 𝐵̅̅ ̅̅ ̅̅ ̅̅ ̅) = �̅� ∙ �̅� (𝐴 ∙ 𝐵̅̅ ̅̅ ̅̅ ̅) = �̅� + �̅�

Truth Tables and Gates

Boolean functions can be evaluated with a truth table. Given a truth table, we can translate a Boolean

function to gates.

AND

A
B

OR

A
B

NOT

A

NAND

A
B

NOR

A
B

XOR

A
B

Notes:

 By convention, a true state is also called on or 1 and a false state is also called off or 0 .

To Prove a Boolean Function:

1. Directly through theorems of Boolean algebra

2. Exhaustively by a truth table

X

X

X

X

X

X