Unit 3 Flashcards
blank is a set of rules and operations for working with variables whose values are either 0
or 1
. Boolean algebra was defined by George Boole in the mid-19th century.
Boolean algebra
The area of computer science concerned with designing computer circuitry is called blank an indication of the vital role that logic plays in this field.
digital logic,
blank, denoted by *, applies to two elements from {0, 1} and obeys the standard rules for multiplication. The results of the multiplication operation are the same as the logical ∧ (“and”) operation.
Boolean multiplication
0 * 0 = blank
0
0 * 1 = blank
0
1 * 0 = blank
0
1 * 1 = blank
1
blank, denoted by +, applies to two elements from {0, 1} and obeys the standard rules for addition, except for 1 + 1.
Boolean addition
0 + 0 = blank
0
0 + 1 = blank
1
1 + 0 = blank
1
1 + 1 = blank
1
The blank of an element, denoted with a bar symbol, reverses that element’s value. Complementing a Boolean value is analogous to applying the ¬ (“not”) operation in logic.
complement
The blank is a logical operation that outputs 1 only when the inputs are different.
exclusive or or XOR operation
0 ⊕ 0 = blank
0
1 ⊕ 0 = blank
1
0 ⊕ 1 = blank
1
1 ⊕ 1 = blank
0
Variables that can have a value of 1 or 0 are called blank.
Boolean variables
blank can be built up by applying Boolean operations to Boolean variables or the constants 1 or 0.
Boolean expressions
blank takes precedence over Boolean addition.
The blank is applied as soon as the entire expression under the bar is evaluated.
blank can be used to override the precedence rules.
Boolean multiplication
complement operation
Parentheses
Two Boolean expressions are blank if they have the same value for every possible combination of values assigned to the variables contained in the expressions.
equivalent
In predicate logic, a special symbol (≡) is used to denote logical equivalence. In Boolean algebra, the blank is used to denote logical equivalence.
equal sign (=)
x + x = x
Idempotent laws
x * x = x
Idempotent law
To say x OR x—or to say x AND x—is redundant. In both cases, we just have x.
Idempotent laws
(x + y) + z = x + (y + z)
Associative laws
(xy)z = x(yz)
Associative laws
xy = yx
Commutative laws:
x + y = y + x
Commutative laws:
x + yz =(x + y)(x + z)
Distributive laws:
x(y + z) =xy + xz
Distributive laws:
x + 0 = x
Identity laws:
x * 1 = x
Identity laws:
x + 1 = 1
Domination laws:
x * 0 = 0
Domination laws:
x + (xy) = x
Absorption laws:
x(x + y) = x
Absorption laws:
The complement of an OR expression is the same as an AND statement of their individual complements. The complement of an AND statement is the same as an OR statement of their individual complements.
De Morgan’s laws
A double negative makes a positive.
Double complement law
Addition or multiplication by the complement will equal either the multiplicative or additive identity value. Also, the complement of 1 is zero, and the complement of 0 is one.
Complement laws
A blank maps one or more Boolean input values to the set {0, 1}. Let B = {0, 1}. Then Bk is the set of all k-tuples over the set B. A Boolean function with k input variables maps Bk to B.
Boolean function
One way to define a Boolean function is to provide an blank that shows the output value of the function for every possible combination of input values.
input/output table
A Boolean function with k input variables will require an input/output table with blank rows.
2k
To find an blank for function f expressed by a truth table, first find the rows in which the value of f is 1 and add them together.
equivalent Boolean expression
A blank is a Boolean variable or the complement of a Boolean variable (for example, x or x).
literal
In a Boolean function whose input variables are v1, v2,…,vk, a blank is a product of literals u1u2…uk such that each uj is either vj or vj.
minterm
A Boolean expression that is a sum of products of literals is said to be in blank (abbreviated as DNF).
disjunctive normal form
A blank expression has the form:
c1 + c2 + …. + cm
where each cj for j ∈ {1, …, m} is a product of literals.
disjunctive normal form (DNF)
Boolean expression in disjunctive normal form -
This expression is a sum of four terms. Each term is a product of literals and has two rules
Complement only applied to a single variable.
No addition within a term.
A Boolean expression that is a product of sums of literals is said to be in blank (abbreviated as CNF).
conjunctive normal form
A blank expression has the form:
d1 * d2 * …. * dm
where each dj for j ∈ {1, …, m} is a sum of literals.
conjunctive normal form (CNF)
Boolean expression in conjunctive normal form - This expression is a product of four factors. Each factor is a sum of literals with what two rules
Complement only applied to single variables.
No multiplication within a factor.
The two rules for disjunctive normal form DNF (the sum of products of literals) are:
Complements are applied to only single variables:
No addition within a term:
The rules for conjunctive normal form CNF (the product of sums of literals) are:
Complements are applied to only single variables:
No multiplication within a factor:
The factors in a CNF expression can be single literals.
A set of operations is blank if any Boolean function can be expressed using only operations from the set.
functionally complete
The set {addition, multiplication, complement} is blank because any Boolean function can be expressed in disjunctive normal form which only uses addition, multiplication, and complement operations.
functionally complete
What is the method to express an arbitrary Boolean function using only multiplication and complement operations:
Start with the input/output table for the function.
Find a DNF expression that is equivalent to the function.
Repeatedly apply De Morgan’s law to eliminate each addition operation.
What are the steps to rewrite a Boolean expression into a more efficient form using only addition and complement operations:
Create an input-output table for the function
Find a CNF expression that is equivalent to the function
Repeatedly apply De Morgan’s law to eliminate each multiplication operation
The blank (which stands for “not and”) is denoted by the symbol ↑. The expression x ↑ y is equivalent to complement (xy).
NAND operation
The blank (which stands for “not or”) is denoted by the symbol ↓. The expression x ↓ y is equivalent to complement(x + y).
NOR operation
0 ↑ 0 = blank
1
1 ↓ 0 = blank
0
1 ↓ 1 = blank
0
0 ↓ 1 = blank
0
0 ↓ 0 = blank
1
1 ↑ 1 = blank
0
1 ↑ 0 = blank
1
0 ↑ 1 = blank
1
The blank (called SAT for short) takes a Boolean expression as input and asks whether it is possible to set the values of the variables so that the expression evaluates to 1.
Boolean satisfiability problem
If there is a way to set the input variables that causes a Boolean expression to blank, then the expression is said to be satisfiable. Otherwise, the expression is unsatisfiable.
evaluate to 1
Circuits are built from electrical devices called blank
gates
The blank gate computes Boolean multiplication, the blank gate computes Boolean addition, and the blank computes the complement.
AND
OR
inverter
The NAND gate computes the NAND operation blank
. The gate outputs 0
if all inputs are 1
and outputs 1
otherwise.
x ↑ y
The NOR gate computes the NOR operation
. The gate outputs 1
if all inputs are 0
and outputs 0
otherwise.
x ↓ y
A two-input XOR gate (for “exclusive OR”) outputs blank
if the input values differ.
1
A two-input XNOR gate (for “exclusive NOR”) outputs blank
if the input values are the same.
1
In a blank the output of the circuit depends only on the present combination of input values and not on the state of a circuit.
combinatorial circuit
blank is the simplification of a Boolean expression before converting to a circuit to yield a smaller circuit.
Circuit minimization
To make simplification opportunities more obvious, a common algebraic simplification process is to:
Convert to a sum of minterms
Apply the complement law:
A Boolean expression can sometimes be simplified by applying the blank to replicate a term
idempotent law
