Unit 3

Question 1

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.

Answer 1

Boolean algebra

Question 2

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.

Answer 2

digital logic,

Question 3

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.

Answer 3

Boolean multiplication

Question 4

0 * 0 = blank

Answer 4

0

Question 5

0 * 1 = blank

Answer 5

0

Question 6

1 * 0 = blank

Answer 6

0

Question 7

1 * 1 = blank

Answer 7

1

Question 8

blank, denoted by +, applies to two elements from {0, 1} and obeys the standard rules for addition, except for 1 + 1.

Answer 8

Boolean addition

Question 9

0 + 0 = blank

Answer 9

0

Question 10

0 + 1 = blank

Answer 10

1

Question 11

1 + 0 = blank

Answer 11

1

Question 12

1 + 1 = blank

Answer 12

1

Question 13

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.

Answer 13

complement

Question 14

The blank is a logical operation that outputs 1 only when the inputs are different.

Answer 14

exclusive or or XOR operation

Question 15

0 ⊕ 0 = blank

Answer 15

0

Question 16

1 ⊕ 0 = blank

Answer 16

1

Question 17

0 ⊕ 1 = blank

Answer 17

1

Question 18

1 ⊕ 1 = blank

Answer 18

0

Question 19

Variables that can have a value of 1 or 0 are called blank.

Answer 19

Boolean variables

Question 20

blank can be built up by applying Boolean operations to Boolean variables or the constants 1 or 0.

Answer 20

Boolean expressions

Question 21

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.

Answer 21

Boolean multiplication
complement operation
Parentheses

Question 22

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.

Answer 22

equivalent

Question 23

In predicate logic, a special symbol (≡) is used to denote logical equivalence. In Boolean algebra, the blank is used to denote logical equivalence.

Answer 23

equal sign (=)

Question 24

x + x = x

Answer 24

Idempotent laws

Question 25

x * x = x

Answer 25

Idempotent law

Question 26

To say x OR x—or to say x AND x—is redundant. In both cases, we just have x.

Answer 26

Idempotent laws

Question 27

(x + y) + z = x + (y + z)

Answer 27

Associative laws

Question 28

(xy)z = x(yz)

Answer 28

Associative laws

Question 29

xy = yx

Answer 29

Commutative laws:

Question 30

x + y = y + x

Answer 30

Commutative laws:

Question 31

x + yz =(x + y)(x + z)

Answer 31

Distributive laws:

Question 32

x(y + z) =xy + xz

Answer 32

Distributive laws:

Question 33

x + 0 = x

Answer 33

Identity laws:

Question 34

x * 1 = x

Answer 34

Identity laws:

Question 35

x + 1 = 1

Answer 35

Domination laws:

Question 36

x * 0 = 0

Answer 36

Domination laws:

Question 37

x + (xy) = x

Answer 37

Absorption laws:

Question 38

x(x + y) = x

Answer 38

Absorption laws:

Question 39

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.

Answer 39

De Morgan's laws

Question 40

A double negative makes a positive.

Answer 40

Double complement law

Question 41

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.

Answer 41

Complement laws

Question 42

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.

Answer 42

Boolean function

Question 43

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.

Answer 43

input/output table

Question 44

A Boolean function with k input variables will require an input/output table with blank rows.

Answer 44

2k

Question 45

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.

Answer 45

equivalent Boolean expression

Question 46

A blank is a Boolean variable or the complement of a Boolean variable (for example, x or x).

Answer 46

literal

Question 47

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.

Answer 47

minterm

Question 48

A Boolean expression that is a sum of products of literals is said to be in blank (abbreviated as DNF).

Answer 48

disjunctive normal form

Question 49

A blank expression has the form: c1 + c2 + .... + cm where each cj for j ∈ {1, …, m} is a product of literals.

Answer 49

disjunctive normal form (DNF)

Question 50

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

Answer 50

Complement only applied to a single variable. No addition within a term.

Question 51

A Boolean expression that is a product of sums of literals is said to be in blank (abbreviated as CNF).

Answer 51

conjunctive normal form

Question 52

A blank expression has the form: d1 * d2 * .... * dm where each dj for j ∈ {1, …, m} is a sum of literals.

Answer 52

conjunctive normal form (CNF)

Question 53

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

Answer 53

Complement only applied to single variables. No multiplication within a factor.

Question 54

The two rules for disjunctive normal form DNF (the sum of products of literals) are:

Answer 54

Complements are applied to only single variables: No addition within a term:

Question 55

The rules for conjunctive normal form CNF (the product of sums of literals) are:

Answer 55

Complements are applied to only single variables: No multiplication within a factor: The factors in a CNF expression can be single literals.

Question 56

A set of operations is blank if any Boolean function can be expressed using only operations from the set.

Answer 56

functionally complete

Question 57

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.

Answer 57

functionally complete

Question 58

What is the method to express an arbitrary Boolean function using only multiplication and complement operations:

Answer 58

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.

Question 59

What are the steps to rewrite a Boolean expression into a more efficient form using only addition and complement operations:

Answer 59

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

Question 60

The blank (which stands for "not and") is denoted by the symbol ↑. The expression x ↑ y is equivalent to complement (xy).

Answer 60

NAND operation

Question 61

The blank (which stands for "not or") is denoted by the symbol ↓. The expression x ↓ y is equivalent to complement(x + y).

Answer 61

NOR operation

Question 62

0 ↑ 0 = blank

Answer 62

1

Question 63

1 ↓ 0 = blank

Answer 63

0

Question 63

1 ↓ 1 = blank

Answer 63

0

Question 64

0 ↓ 1 = blank

Answer 64

0

Question 65

0 ↓ 0 = blank

Answer 65

1

Question 66

1 ↑ 1 = blank

Answer 66

0

Question 67

1 ↑ 0 = blank

Answer 67

1

Question 68

0 ↑ 1 = blank

Answer 68

1

Question 69

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.

Answer 69

Boolean satisfiability problem

Question 70

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.

Answer 70

evaluate to 1

Question 71

Circuits are built from electrical devices called blank

Answer 71

gates

Question 72

The blank gate computes Boolean multiplication, the blank gate computes Boolean addition, and the blank computes the complement.

Answer 72

AND OR inverter

Question 73

The NAND gate computes the NAND operation blank . The gate outputs 0 if all inputs are 1 and outputs 1 otherwise.

Answer 73

x ↑ y

Question 74

The NOR gate computes the NOR operation . The gate outputs 1 if all inputs are 0 and outputs 0 otherwise.

Answer 74

x ↓ y

Question 75

A two-input XOR gate (for "exclusive OR") outputs blank if the input values differ.

Answer 75

1

Question 76

A two-input XNOR gate (for "exclusive NOR") outputs blank if the input values are the same.

Answer 76

1

Question 77

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.

Answer 77

combinatorial circuit

Question 78

blank is the simplification of a Boolean expression before converting to a circuit to yield a smaller circuit.

Answer 78

Circuit minimization

Question 79

To make simplification opportunities more obvious, a common algebraic simplification process is to:

Answer 79

Convert to a sum of minterms Apply the complement law:

Question 80

A Boolean expression can sometimes be simplified by applying the blank to replicate a term

Answer 80

idempotent law