Brainscape's Knowledge GenomeTM

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


See full index

Discrete Math 1 > Unit 1 > Flashcards

Unit 1 Flashcards

1
Q

Blank is the study of formal reasoning

A

Logic

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

A blank is a statement that is either true or false.

A

proposition

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

A proposition’s blank is a value indicating whether the proposition is actually true or false.

A

truth value

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

A blank shows the truth value of a proposition.

A

truth table

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

A blank is created by connecting individual propositions with logical operations

A

compound proposition

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

A blank combines propositions using a particular composition rule

A

logical operation

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

the conjunction operation is denoted by blank

A

∧

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

The proposition p ∧ q is read “p and q” and is called the blank of p and q

A

conjunction

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

The disjunction operation is denoted by blank

A

∨

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

The proposition p ∨ q is read “p or q”, and is called the blank of p and q. p ∨ q is true if either one of p or q is true, or if both are true.

A

disjunction

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

The blank of p and q evaluates to true when p is true and q is false or when q is true and p is false.

A

exclusive or

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

The blank operation is the same as the disjunction (∨) operation and evaluates to true when one or both of the propositions are true.

A

inclusive or

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

The blank operation acts on just one proposition and has the effect of reversing the truth value of the proposition.

A

negation

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

The negation of proposition p is denoted blank and is read as “not p”.

A

¬p

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

The negation operation is a blank, or an operation that acts on only one input.

A

unary operation

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

A logical operation combines blank using a particular composition rule.

A

propositions

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

The logical operator that joins two propositions with blank is called the conjunction and is denoted p ∧ q.

A

AND

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

The logical operator that joins two propositions with blank is called the disjunction and is denoted p ∨ q. It is the inclusive “or.”

A

OR

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

The logical operator that joins two propositions with blank but not both is called the exclusive “or” and is denoted p ⊕ q.

A

EITHER OR

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

The blank of a proposition changes it truth value and is denoted ¬p. For example, if p is true then ¬p is false.

A

negation

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

Blank is usually denoted with the symbol ⊕

A

The exclusive or operation

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

A blank can be created by using more than one operation.

A

compound proposition

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

Order of operations in absence of parentheses.

A

¬ (not)
∧ (and)
∨ (or)

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

A truth table for a compound statement will have a row for every possible combination of truth assignments for the statement’s variables. If there are n variables, there are blank rows.

A

2^n

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

The blank is denoted with the symbol →. The proposition p → q is read “if p then q”. The proposition p → q is false if p is true and q is false; otherwise, p → q is true.

A

conditional operation

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

A compound proposition that uses a conditional operation is called a blank

A

conditional proposition

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

A conditional proposition expressed in English is sometimes referred to as a blank, as in “If there is a traffic jam today, then I will be late for work.”

A

conditional statement

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

In p → q, the proposition p is called the blank, and the proposition q is called the blank.

A

hypothesis
conclusion

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

The blank of p → q is q → p.

A

converse

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

The blank of p → q is ¬q → ¬p.

A

contrapositive

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

The blank of p → q is ¬p → ¬q.

A

inverse

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

If p and q are propositions, the proposition “p if and only if q” is expressed with the blank and is denoted p ↔ q.

A

biconditional operation

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

The proposition p ↔ q is blank when p and q have the same truth value and is blank when p and q have different truth values.

A

true
false

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

The term blank is an abbreviation of the expression “if and only if”, as in “p iff q”.

A

iff

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

A compound proposition is a blank if the proposition is always true, regardless of the truth value of the individual propositions that occur in it.

A

tautology

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

A compound proposition is a blank if the proposition is always false, regardless of the truth value of the individual propositions that occur in it.

A

contradiction

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

p ∨ ¬p is a simple example of a blank

A

tautology

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

The proposition p ∧ ¬p is an example of a simple blank

A

contradiction

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

Showing that a compound proposition is not a tautology only requires showing a particular set of truth values for its individual propositions that cause the compound proposition to evaluate to blank.

A

false

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

Two compound propositions are said to be blank if they have the same truth value regardless of the truth values of their individual propositions.

A

logically equivalent

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

If s and r are two compound propositions, the notation blank is used to indicate that r and s are logically equivalent.

A

s ≡ r

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

Showing that two propositions are not logically equivalent only requires showing a particular set of truth values for their individual propositions that cause the two compound proposition to have blank

A

different truth values

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

Blank are logical equivalences that show how to correctly distribute a negation operation inside a parenthesized expression.

A

De Morgan’s laws

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

The first De Morgan’s law is:

A

¬(p ∨ q) ≡ (¬p ∧ ¬q)

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

The second version of De Morgan’s law swaps the role of the disjunction and conjunction:

A

¬(p ∧ q) ≡ (¬p ∨ ¬q)

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

f two propositions are blank, then one can be substituted for the other within a more complex proposition.

A

logically equivalent

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

p ∨ p ≡ p

A

Idempotent law

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

p ∧ p ≡ p

A

Idempotent law

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

( p ∨ q ) ∨ r ≡ p ∨ ( q ∨ r )

A

Associative laws

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

( p ∧ q ) ∧ r ≡ p ∧ ( q ∧ r )

A

Associative laws

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

p ∨ q ≡ q ∨ p

A

Commutative law

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

p ∧ q ≡ q ∧ p

A

Commutative law

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

p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r )

A

Distributive law

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

p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )

A

Distributive law

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

p ∨ F ≡ p

A

Identity law

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

p ∧ T ≡ p

A

Identity law

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

p ∧ F ≡ F

A

Domination law

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

p ∨ T ≡ T

A

Domination law

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

¬¬p ≡ p

A

Double negation law

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

p ∧ ¬p ≡ F
¬T ≡ F

A

Complement law

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

p ∨ ¬p ≡ T
¬F ≡ T

A

Complement law

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

¬( p ∨ q ) ≡ ¬p ∧ ¬q

A

De Morgan’s law

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

¬( p ∧ q ) ≡ ¬p ∨ ¬q

A

De Morgan’s law

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

p ∨ (p ∧ q) ≡ p

A

Absorption law

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

p ∧ (p ∨ q) ≡ p

A

Absorption law

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

p → q ≡ ¬p ∨ q

A

Conditional identities

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

p ↔ q ≡ ( p → q ) ∧ ( q → p )

A

Conditional identities

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

Since p ∧ q requires p, p ∨ (p ∧ q) is just p.

A

Absorption laws

69
Q

Only applies when the operators are all ∧ or ∨. Rearranging the parentheses in an expression will not change its value.

A

Associative laws

70
Q

Rearranging the propositions within a single disjunction or conjunction will not change its truth value.

A

Commutative laws

71
Q

It cannot be true that p is true and ¬p is true. Similarly, it always true that either p or ¬p is true.

A

Complement laws

72
Q

It is convenient sometimes to translate conditional statements into ones that involve the conjunction or disjunction.

A

Conditional identities

73
Q

If the negation operation is distributed in a parenthesized expression with either a conjunction or disjunction operation, change the conjunction operation to a disjunction operation, and vice versa.

A

De Morgan’s laws

74
Q

Reformulate conjunctions and disjunctions within logical proofs.

A

Distributive laws

75
Q

The conjunction with a proposition that is false is always false. The disjunction with a proposition that is always true is true.

A

Domination laws

76
Q

A double negative makes a positive.

A

Double negation law

77
Q

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

A

Idempotent laws

78
Q

The disjunction with a proposition that is false can be reduced to just the proposition. The conjunction with a proposition that is always true can be reduced to just the proposition.

A

Identity laws

79
Q

A logical statement whose truth value is a function of one or more variables is called a blank.

A

predicate

80
Q

The blank of a variable in a predicate is the set of all possible values for the variable.

A

domain

81
Q

The symbol blank is a universal quantifier

A

∀

82
Q

the statement ∀x P(x) is called a blank.

A

universally quantified statement

83
Q

The logical statement ∀x P(x) is read “for all x, P(x)” or “for every x, P(x)”. The statement ∀x P(x) asserts that P(x) is true for blank for x in its domain.

A

every possible value

84
Q

A blank for a universally quantified statement is an element in the domain for which the predicate is false.

A

counterexample

85
Q

The logical statement ∃x P(x) is read “There exists an x, such that P(x)”. The statement ∃x P(x) asserts that P(x) is true for at least blank for x in its domain.

A

one possible value

86
Q

The symbol blank is an existential quantifier

A

∃

87
Q

the statement ∃x P(x) is called a blank.

A

existentially quantified statement

88
Q

∃x P(x) is a proposition because it is either true or false. ∃x P(x) is true if and only if P(n) is true for blank n in the domain of variable x.

A

at least one value

89
Q

The universal and existential quantifiers are generically called blank

A

quantifiers

90
Q

A logical statement that includes a universal or existential quantifier is called a blank.

A

quantified statement

91
Q

A variable x in the predicate P(x) is called a blank because the variable is free to take on any value in the domain.

A

free variable

92
Q

The variable x in the statement ∀x P(x) is a blank because the variable is bound to a quantifier.

A

bound variable

93
Q

A statement with no free variables is a blank because the statement’s truth value can be determined.

A

proposition

94
Q

The rule of order to evaluate a compound quantified statement is to apply the blank (∀,∃) before the blank (∧, ∨, → and ↔).

A

quantifiers
logical operations

95
Q

Two quantified statements (whether they are expressed in English or the language of logic) have the same blank if they have the same truth value regardless of value of the predicates for the elements in the domain.

A

logical meaning

96
Q

¬∀x F(x) ≡ ∃x ¬F(x).

A

De Morgan’s law for quantified statements

97
Q

¬∃x P(x) ≡ ∀x ¬P(x)

A

De Morgan’s laws for quantified statements

98
Q

A logical expression with more than one quantifier that bind different variables in the same predicate is said to have blank

A

nested quantifiers

99
Q

A logical expression with blank that binds different variables in the same predicate is said to have nested quantifiers. For example, ∀x∀yM(x,y).

A

more than one quantifier

100
Q

Read nested quantifiers from blank

A

left to right.

101
Q

∀x∀y M(x,y)

A

For every pair of x and y, M(x,y) is true

102
Q

∃x∃y M(x,y)

A

There exists at least one pair of x and y such that M(x,y) is true

103
Q

∃x∀y M(x,y)

A

There exists at least one x that pairs with ALL y, such that M(x,y) is true

104
Q

∀x∃y M(x,y)

A

For each x, there is at least one y, such that M(x,y) is true

105
Q

¬∀x ∀y P(x, y) ≡ ?

A

∃x ∃y ¬P(x, y)

106
Q

¬∀x ∃y P(x, y) ≡ ?

A

∃x ∀y ¬P(x, y)

107
Q

¬∃x ∀y P(x, y) ≡ ?

A

∀x ∃y ¬P(x, y)

108
Q

¬∃x ∃y P(x, y) ≡ ?

A

∀x ∀y ¬P(x, y)

109
Q

¬∀x ∀y P(x, y) ≡ ∃x ∃y ¬P(x, y)

A

It is not true for all x and for all y, P(x, y).

110
Q

¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y)

A

It is not true for all x there exists a y, such that P(x, y) is true

111
Q

¬∃x ∀y P(x, y) ≡ ∀x ∃y ¬P(x, y)

A

It is not true that there exists an x for all y, such P(x, y) is true

112
Q

¬∃x ∃y P(x, y) ≡ ∀x ∀y ¬P(x, y)

A

It is not true that there exists a pair of x and y, such that P(x, y) is true.

113
Q

An blank is a sequence of propositions or hypotheses, followed by a final proposition, called the conclusion.

A

argument

114
Q

An argument is valid if the conclusion is blank whenever the hypotheses are all true, otherwise the argument is invalid.

A

true

115
Q

The blank of an argument expressed in English is obtained by replacing each individual proposition with a variable.

A

form

116
Q

An argument consists of a collection of propositions that include a set of premises called the blank and a concluding one called the blank. Symbolically, we use p1, p2, … pn to represent the hypotheses and c for the conclusion.

A

hypotheses
conclusion

117
Q

Symbolically we can express the argument as blank

A

(p1 ∧ p2∧ … ∧ pn) → c

118
Q

A proposition can be blank whereas an argument is blank.

A

true or false
valid or invalid

119
Q

The argument is valid if all the blank AND the blank. It is invalid otherwise.

A

premises are true
conclusion is true

120
Q

p
p → q
∴ q

A

Modus ponens

121
Q

¬q
p → q
∴ ¬p

A

Modus tollens

122
Q

p
∴ p ∨ q

A

Addition

123
Q

p ∧ q
∴ p

A

Simplification

124
Q

p
q
∴ p ∧ q

A

Conjunction

125
Q

p → q
q → r
∴ p → r

A

Hypothetical syllogism

126
Q

p ∨ q
¬p
∴ q

A

Disjunctive syllogism

127
Q

p ∨ q
¬p ∨ r
∴ q ∨ r

A

Resolution

128
Q

The validity of an argument can be established by applying the rules of inference and laws of propositional logic in a blank

A

logical proof

129
Q

A logical proof of an argument is a blank, each of which consists of a proposition and a justification.

A

sequence of steps

130
Q

Given p;
if p then q;
then q can be inferred

A

Modus ponens

131
Q

Given NOT q;
if p then q;
then NOT p can be inferred

A

Modus tollens

132
Q

Given p;
p OR q can be inferred

A

Addition

133
Q

Given p AND q;
p can be inferred

A

Simplification

134
Q

Given p;
Given q;
p AND q can be inferred

A

Conjunction

135
Q

If p implies q;
and q implies r;
Then p implies r can be inferred

A

Hypothetical syllogism

136
Q

Given p OR q;
Given NOT p;
Then q can be inferred

A

Disjunctive syllogism

137
Q

Given p OR q;
Given NOT p OR r;
Then q OR r can be inferred

A

Resolution

138
Q

A value that can be plugged in for variable x is called an blank of the domain of x.

A

element

139
Q

In order to apply the rules of inference to quantified expressions, such as ∀x ¬(P(x) ∧ Q(x)), we need to remove the blank by plugging in a value from the domain to replace the variable x

A

quantifier

140
Q

An blank of a domain has no special properties other than those shared by all the elements of the domain.

A

arbitrary element

141
Q

A blank of the domain may have properties that are not shared by all the elements of the domain

A

particular element

142
Q

The rules blank and blank replace a quantified variable with an element of the domain.

A

existential instantiation and universal instantiation

143
Q

The rules blank and blank replace an element of the domain with a quantified variable.

A

existential generalization and universal generalization

144
Q

c is an element (arbitrary or particular)
∀x P(x)
∴ P(c)

A

Universal instantiation

145
Q

Sam is a student in the class.
Every student in the class completed the assignment.
Therefore, Sam completed his assignment.

A

Universal instantiation

146
Q

c is an arbitrary element
P(c)
∴ ∀x P(x)

A

Universal generalization

147
Q

Let c be an arbitrary integer.
c ≤ c2
Therefore, every integer is less than or equal to its square.

A

Universal generalization

148
Q

There is an integer that is equal to its square.
Therefore, c2 = c, for some integer c.

A

Existential instantiation*

149
Q

∃x P(x)
∴ (c is a particular element) ∧ P(c)

A

Existential instantiation*

150
Q

c is an element (arbitrary or particular)
P(c)
∴ ∃x P(x)

A

Existential generalization

151
Q

Sam is a particular student in the class.
Sam completed the assignment.
Therefore, there is a student in the class who completed the assignment.

A

Existential generalization

152
Q

A blank is a statement that can be proven to be true

A

theorem

153
Q

A blank consists of a series of steps, each of which follows logically from assumptions, or from previously proven statements, whose final step should result in the statement of the theorem being proven.

A

proof

154
Q

The proof of a theorem may make use of blank, which are statements assumed to be true. A proof may also make use of previously proven theorems

A

axioms

155
Q

If the domain of a universal statement is small, it may be easiest to prove the statement by checking each element individually. A proof of this kind is called a proof by blank.

A

exhaustion

156
Q

A blank is an assignment of values to variables that shows that a universal statement is false. The example illustrates the danger in generalizing from examples because there can always be a counterexample that was not tried.

A

counterexample

157
Q

In a blank of a conditional statement, the hypothesis p is assumed to be true and the conclusion c is proven as a direct result of the assumption.

A

direct proof

158
Q

A blank, is defined to be a number that can be expressed as the ratio of two integers in which the denominator is non-zero.

A

rational number

159
Q

A proof by blank proves a conditional theorem of the form p → c by showing that the contrapositive ¬c → ¬p is true. In other words, ¬c is assumed to be true and ¬p is proven as a result of ¬c.

A

contrapositive

160
Q

An even integer can be expressed as blank for some integer k.

A

2k

161
Q

An odd integer can be expressed as blank for some integer k.

A

2k + 1

162
Q

An blank is a real number that is not rational.

A

irrational number

163
Q

A proof by blank starts by assuming that the theorem is false and then shows that some logical inconsistency arises as a result of this assumption. If t is the statement of the theorem, the proof begins with the assumption ¬t and leads to a conclusion r ∧ ¬r, for some proposition r.

A

contradiction

164
Q

Unlike direct proofs and proofs by contrapositive, a proof by contradiction can be used to prove theorems that are not conditional statements. A proof by contradiction is sometimes called an blank.

A

indirect proof

165
Q

Assume p. Follow a series of steps to conclude q.

A

direct proof

166
Q

Assume ¬q. Follow a series of steps to conclude ¬p

A

proof by contrapositive

167
Q

Assume p ∧ ¬q. Follow a series of logical steps to conclude r ∧ ¬r for some proposition.

A

proof by contradiction

168
Q

A blank of a universal statement such as ∀x P(x) breaks the domain for the variable x into different classes and gives a different proof for each class. Every value in the domain must be included in at least one class.

A

proof by cases

169
Q

The blank of a number is whether that number is odd or even.

A

parity

Discrete Math 1 (7 decks)

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