2.1, 2.2 & 2.3 Flashcards
Boolean Algebra Boolean Expression Logic gates
What is Boolean Algebra?
Mathematical model for digital logic circuits
Binary, {1, 0}, {true, false}
It’s a mathematical system
Mathematical System definition
a set of elements and one or more binary operations to connect these elements.
Elements: {0,1}
Operations: {・,+ , ‘}
Operations: {and, or, not}
Mathematical system properties:
Closure
______
Inverse
______
Associative
_______
Identity
Commutative
Distributive
property:
Assumed to be _____
Obvious
true
law:
Proven true by ______ and other proven laws
properties
A ∧ (B ∧ C) = (A ∧ B) ∧ C
A ∨ (B ∨ C) = (A ∨ B) ∨ C
Associative property
A ∧ B = B ∧ A
A ∨ B = B ∨ A
A ∨ (B ∧ C) = (A ∨ B) ∧ C
A ∧ (B ∨ C) = A ∧ (B ∨ C)
A ∧ B ∧ C = C ∧ B ∧ A
commutative property
A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
distributive property
A ∧ True = A
B ∨ False = B
identity law
A ∨ A’ = True
B ∧ B’ = False
complement law
A ∨ A = A
B ∧ B = B
idempotent law
(A’)’ = A
((A ∧ B)’)’ = A ∧ B (same for ∨)
(A ∨ B’)’ ≠ A ∨ B
Double negation law
(A ∧ B)’ = A’ ∨ B’
(A ∨ B)’ = A’ ∧ B’
de Morgan’s Law
A ∧ (A ∨ B) = A
A ∨ (A ∧ B) = A
Absorptive law
Boolean Algebra is a way of formally specifying, or describing, a particular situation or procedure. We use variables to represent elements of our situation or procedure. Variables may take one of only two values. Traditionally this would be True and False. So for instance we may have a variable X and state that this represents if it is raining outside or not. The value of X would be :
True if it is raining outside.
False if it is not raining outside.
When _______ are used in an expression this means that we evaluate that part of the expression first before the other parts.
brackets ( )
If g is True and p is False then :
Substituting g and p for those values we get :
(True OR False) AND NOT(True AND False)
The first set of brackets (True OR False) AND NOT(True AND False) evaluates to True so let’s replace that into the expression and we get :
____ ____ ___ (___ __ ____)
The next set of brackets True AND NOT(True AND False) evaluates to _____ so let’s replace that into the expression as well giving us :
True AND NOT(False)
NOT(False) evaluates to True so we can apply that to the expression and we end up with :
True and True
And the final result is True.
True AND NOT(True AND False)
False
NAND is effectively the opposite of what AND is.
r NAND S is equivalent to ___(__ ___ ___)
NOT(r AND s)
NOR or NOT OR
NOR is effectively the opposite of OR.
b NOR k is equivalent to ___(__ ___ __)
NOT(b OR k)
A term AND‘ed with a “0” equals 0 or OR‘ed with a “1” will equal 1
A . 0 = 0 A variable AND’ed with 0 is always equal to 0
A + 1 = 1 A variable OR’ed with 1 is always equal to 1
Annulment Law
A term OR‘ed with a “0” or AND‘ed with a “1” will always equal that term
A + 0 = A A variable OR’ed with 0 is always equal to the variable
A . 1 = A A variable AND’ed with 1 is always equal to the variable
Identity Law
An input that is AND‘ed or OR´ed with itself is equal to that input
A + A = A A variable OR’ed with itself is always equal to the variable
A . A = A A variable AND’ed with itself is always equal to the variable
Idempotent Law
A term AND‘ed with its complement equals “0” and a term OR´ed with its complement equals “1”
A . A = 0 A variable AND’ed with its complement is always equal to 0
A + A = 1 A variable OR’ed with its complement is always equal to 1
Complement Law
The order of application of two separate terms is not important
A . B = B . A The order in which two variables are AND’ed makes no difference
A + B = B + A The order in which two variables are OR’ed makes no difference
Commutative Law
A term that is inverted twice is equal to the original term
A = A A double complement of a variable is always equal to the variable
Double Negation Law
There are two “de Morgan’s” rules or theorems,
(1) Two separate terms NOR‘ed together is the same as the two terms inverted (Complement) and AND‘ed for example: A+B = _____
(2) Two separate terms NAND‘ed together is the same as the two terms ______ (Complement) and OR‘ed for example: A.B = A + B
AB
inverted
While not Boolean Laws in their own right, these are a set of Mathematical Laws which can be used in the simplification of Boolean Expressions.
0 . 0 = 0 A 0 AND’ed with itself is always equal to 0
1 . 1 = 1 A 1 AND’ed with itself is always equal to 1
1 . 0 = 0 A 1 AND’ed with a 0 is equal to 0
0 + 0 = 0 A 0 OR’ed with itself is always equal to 0
1 + 1 = 1 A 1 OR’ed with itself is always equal to 1
1 + 0 = 1 A 1 OR’ed with a 0 is equal to 1
1 = 0 The Inverse (Complement) of a 1 is always equal to 0
0 = 1 The Inverse (Complement) of a 0 is always equal to 1
Boolean Postulates
This law permits the multiplying or factoring out of an expression.
A(B + C) = A.B + A.C (OR _____ _____)
A + (B.C) = (A + B).(A + C) (AND ____ _____)
Distributive Law
This law enables a reduction in a complicated expression to a simpler one by absorbing like terms.
A + (A.B) = (A.1) + (A.B) = A(1 + B) = A (OR Absorption Law)
A(A + B) = (A + 0).(A + B) = A + (0.B) = A (AND Absorption Law)
Absorptive Law
This law allows the removal of brackets from an expression and regrouping of the variables.
A + (B + C) = (A + B) + C = A + B + C (OR Associate Law)
A(B.C) = (A.B)C = A . B . C (AND Associate Law)
Associative Law
In mathematics, an _____ is a statement true for all possible values of its variable or variables.
The algebraic identity of x + 0 = x tells us that anything (x) added to zero equals the original “anything,” no matter what value that “_______” (x) may be.
Like ordinary algebra, Boolean algebra has its own unique identities based on the bivalent states of Boolean variables.
identity
anything
