Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Discrete Math 1 > Unit 3 > Flashcards

Unit 3 Flashcards

1
Q

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.

A

Boolean algebra

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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.

A

digital logic,

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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.

A

Boolean multiplication

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

0 * 0 = blank

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

0 * 1 = blank

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

1 * 0 = blank

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

1 * 1 = blank

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Boolean addition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

0 + 0 = blank

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

0 + 1 = blank

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

1 + 0 = blank

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

1 + 1 = blank

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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.

A

complement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

exclusive or or XOR operation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

0 ⊕ 0 = blank

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

1 ⊕ 0 = blank

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

0 ⊕ 1 = blank

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

1 ⊕ 1 = blank

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

Boolean variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

Boolean expressions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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.

A

Boolean multiplication
complement operation
Parentheses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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.

A

equivalent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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

A

equal sign (=)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

x + x = x

A

Idempotent laws

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

x * x = x

A

Idempotent law

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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

A

Idempotent laws

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

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

A

Associative laws

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

(xy)z = x(yz)

A

Associative laws

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

xy = yx

A

Commutative laws:

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

x + y = y + x

A

Commutative laws:

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

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

A

Distributive laws:

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

x(y + z) =xy + xz

A

Distributive laws:

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

x + 0 = x

A

Identity laws:

34
Q

x * 1 = x

A

Identity laws:

35
Q

x + 1 = 1

A

Domination laws:

36
Q

x * 0 = 0

A

Domination laws:

37
Q

x + (xy) = x

A

Absorption laws:

38
Q

x(x + y) = x

A

Absorption laws:

39
Q

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.

A

De Morgan’s laws

40
Q

A double negative makes a positive.

A

Double complement law

41
Q

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.

A

Complement laws

42
Q

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.

A

Boolean function

43
Q

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.

A

input/output table

44
Q

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

A

2k

45
Q

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.

A

equivalent Boolean expression

46
Q

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

A

literal

47
Q

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.

A

minterm

48
Q

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

A

disjunctive normal form

49
Q

A blank expression has the form:

c1 + c2 + …. + cm

where each cj for j ∈ {1, …, m} is a product of literals.

A

disjunctive normal form (DNF)

50
Q

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

A

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

51
Q

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

A

conjunctive normal form

52
Q

A blank expression has the form:

d1 * d2 * …. * dm

where each dj for j ∈ {1, …, m} is a sum of literals.

A

conjunctive normal form (CNF)

53
Q

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

A

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

54
Q

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

A

Complements are applied to only single variables:

No addition within a term:

55
Q

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

A

Complements are applied to only single variables:

No multiplication within a factor:

The factors in a CNF expression can be single literals.

56
Q

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

A

functionally complete

57
Q

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.

A

functionally complete

58
Q

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

A

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.

59
Q

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

A

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

60
Q

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

A

NAND operation

61
Q

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

A

NOR operation

62
Q

0 ↑ 0 = blank

A

1

63
Q

1 ↓ 0 = blank

A

0

63
Q

1 ↓ 1 = blank

A

0

64
Q

0 ↓ 1 = blank

A

0

65
Q

0 ↓ 0 = blank

A

1

66
Q

1 ↑ 1 = blank

A

0

67
Q

1 ↑ 0 = blank

A

1

68
Q

0 ↑ 1 = blank

A

1

69
Q

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.

A

Boolean satisfiability problem

70
Q

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.

A

evaluate to 1

71
Q

Circuits are built from electrical devices called blank

A

gates

72
Q

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

A

AND
OR
inverter

73
Q

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

A

x ↑ y

74
Q

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

A

x ↓ y

75
Q

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

A

1

76
Q

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

A

1

77
Q

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.

A

combinatorial circuit

78
Q

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

A

Circuit minimization

79
Q

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

A

Convert to a sum of minterms
Apply the complement law:

80
Q

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

A

idempotent law

Discrete Math 1 (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions