Unit 1 Flashcards
1
Q
Blank is the study of formal reasoning
A
Logic
2
Q
A blank is a statement that is either true or false.
A
proposition
3
Q
A proposition’s blank is a value indicating whether the proposition is actually true or false.
A
truth value
4
Q
A blank shows the truth value of a proposition.
A
truth table
5
Q
A blank is created by connecting individual propositions with logical operations
A
compound proposition
6
Q
A blank combines propositions using a particular composition rule
A
logical operation
7
Q
the conjunction operation is denoted by blank
A
∧
8
Q
The proposition p ∧ q is read “p and q” and is called the blank of p and q
A
conjunction
9
Q
The disjunction operation is denoted by blank
A
∨
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
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
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
13
Q
The blank operation acts on just one proposition and has the effect of reversing the truth value of the proposition.
A
negation
14
Q
The negation of proposition p is denoted blank and is read as “not p”.
A
¬p
15
Q
The negation operation is a blank, or an operation that acts on only one input.
A
unary operation
16
Q
A logical operation combines blank using a particular composition rule.
A
propositions
17
Q
The logical operator that joins two propositions with blank is called the conjunction and is denoted p ∧ q.
A
AND
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
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
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
21
Q
Blank is usually denoted with the symbol ⊕
A
The exclusive or operation
22
Q
A blank can be created by using more than one operation.
A
compound proposition
23
Q
Order of operations in absence of parentheses.
A
¬ (not)
∧ (and)
∨ (or)
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
25
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.
conditional operation
26
A compound proposition that uses a conditional operation is called a blank
conditional proposition
27
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."
conditional statement
28
In p → q, the proposition p is called the blank, and the proposition q is called the blank.
hypothesis
conclusion
29
The blank of p → q is q → p.
converse
30
The blank of p → q is ¬q → ¬p.
contrapositive
31
The blank of p → q is ¬p → ¬q.
inverse
32
If p and q are propositions, the proposition "p if and only if q" is expressed with the blank and is denoted p ↔ q.
biconditional operation
33
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.
true
false
34
The term blank is an abbreviation of the expression "if and only if", as in "p iff q".
iff
35
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.
tautology
36
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.
contradiction
37
p ∨ ¬p is a simple example of a blank
tautology
38
The proposition p ∧ ¬p is an example of a simple blank
contradiction
39
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.
false
40
Two compound propositions are said to be blank if they have the same truth value regardless of the truth values of their individual propositions.
logically equivalent
41
If s and r are two compound propositions, the notation blank is used to indicate that r and s are logically equivalent.
s ≡ r
42
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
different truth values
43
Blank are logical equivalences that show how to correctly distribute a negation operation inside a parenthesized expression.
De Morgan's laws
44
The first De Morgan's law is:
¬(p ∨ q) ≡ (¬p ∧ ¬q)
45
The second version of De Morgan's law swaps the role of the disjunction and conjunction:
¬(p ∧ q) ≡ (¬p ∨ ¬q)
46
f two propositions are blank, then one can be substituted for the other within a more complex proposition.
logically equivalent
47
p ∨ p ≡ p
Idempotent law
48
p ∧ p ≡ p
Idempotent law
49
( p ∨ q ) ∨ r ≡ p ∨ ( q ∨ r )
Associative laws
50
( p ∧ q ) ∧ r ≡ p ∧ ( q ∧ r )
Associative laws
51
p ∨ q ≡ q ∨ p
Commutative law
52
p ∧ q ≡ q ∧ p
Commutative law
53
p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r )
Distributive law
54
p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )
Distributive law
55
p ∨ F ≡ p
Identity law
56
p ∧ T ≡ p
Identity law
57
p ∧ F ≡ F
Domination law
58
p ∨ T ≡ T
Domination law
59
¬¬p ≡ p
Double negation law
60
p ∧ ¬p ≡ F
¬T ≡ F
Complement law
61
p ∨ ¬p ≡ T
¬F ≡ T
Complement law
62
¬( p ∨ q ) ≡ ¬p ∧ ¬q
De Morgan's law
63
¬( p ∧ q ) ≡ ¬p ∨ ¬q
De Morgan's law
64
p ∨ (p ∧ q) ≡ p
Absorption law
65
p ∧ (p ∨ q) ≡ p
Absorption law
66
p → q ≡ ¬p ∨ q
Conditional identities
67
p ↔ q ≡ ( p → q ) ∧ ( q → p )
Conditional identities
68
Since p ∧ q requires p, p ∨ (p ∧ q) is just p.
Absorption laws
69
Only applies when the operators are all ∧ or ∨. Rearranging the parentheses in an expression will not change its value.
Associative laws
70
Rearranging the propositions within a single disjunction or conjunction will not change its truth value.
Commutative laws
71
It cannot be true that p is true and ¬p is true. Similarly, it always true that either p or ¬p is true.
Complement laws
72
It is convenient sometimes to translate conditional statements into ones that involve the conjunction or disjunction.
Conditional identities
73
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.
De Morgan's laws
74
Reformulate conjunctions and disjunctions within logical proofs.
Distributive laws
75
The conjunction with a proposition that is false is always false. The disjunction with a proposition that is always true is true.
Domination laws
76
A double negative makes a positive.
Double negation law
77
To say p OR p or to say p AND p is redundant. In both cases, we just have p.
Idempotent laws
78
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.
Identity laws
79
A logical statement whose truth value is a function of one or more variables is called a blank.
predicate
80
The blank of a variable in a predicate is the set of all possible values for the variable.
domain
81
The symbol blank is a universal quantifier
∀
82
the statement ∀x P(x) is called a blank.
universally quantified statement
83
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.
every possible value
84
A blank for a universally quantified statement is an element in the domain for which the predicate is false.
counterexample
85
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.
one possible value
86
The symbol blank is an existential quantifier
∃
87
the statement ∃x P(x) is called a blank.
existentially quantified statement
88
∃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.
at least one value
89
The universal and existential quantifiers are generically called blank
quantifiers
90
A logical statement that includes a universal or existential quantifier is called a blank.
quantified statement
91
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.
free variable
92
The variable x in the statement ∀x P(x) is a blank because the variable is bound to a quantifier.
bound variable
93
A statement with no free variables is a blank because the statement's truth value can be determined.
proposition
94
The rule of order to evaluate a compound quantified statement is to apply the blank (∀,∃) before the blank (∧, ∨, → and ↔).
quantifiers
logical operations
95
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.
logical meaning
96
¬∀x F(x) ≡ ∃x ¬F(x).
De Morgan's law for quantified statements
97
¬∃x P(x) ≡ ∀x ¬P(x)
De Morgan's laws for quantified statements
98
A logical expression with more than one quantifier that bind different variables in the same predicate is said to have blank
nested quantifiers
99
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).
more than one quantifier
100
Read nested quantifiers from blank
left to right.
101
∀x∀y M(x,y)
For every pair of x and y, M(x,y) is true
102
∃x∃y M(x,y)
There exists at least one pair of x and y such that M(x,y) is true
103
∃x∀y M(x,y)
There exists at least one x that pairs with ALL y, such that M(x,y) is true
104
∀x∃y M(x,y)
For each x, there is at least one y, such that M(x,y) is true
105
¬∀x ∀y P(x, y) ≡ ?
∃x ∃y ¬P(x, y)
106
¬∀x ∃y P(x, y) ≡ ?
∃x ∀y ¬P(x, y)
107
¬∃x ∀y P(x, y) ≡ ?
∀x ∃y ¬P(x, y)
108
¬∃x ∃y P(x, y) ≡ ?
∀x ∀y ¬P(x, y)
109
¬∀x ∀y P(x, y) ≡ ∃x ∃y ¬P(x, y)
It is not true for all x and for all y, P(x, y).
110
¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y)
It is not true for all x there exists a y, such that P(x, y) is true
111
¬∃x ∀y P(x, y) ≡ ∀x ∃y ¬P(x, y)
It is not true that there exists an x for all y, such P(x, y) is true
112
¬∃x ∃y P(x, y) ≡ ∀x ∀y ¬P(x, y)
It is not true that there exists a pair of x and y, such that P(x, y) is true.
113
An blank is a sequence of propositions or hypotheses, followed by a final proposition, called the conclusion.
argument
114
An argument is valid if the conclusion is blank whenever the hypotheses are all true, otherwise the argument is invalid.
true
115
The blank of an argument expressed in English is obtained by replacing each individual proposition with a variable.
form
116
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.
hypotheses
conclusion
117
Symbolically we can express the argument as blank
(p1 ∧ p2∧ ... ∧ pn) → c
118
A proposition can be blank whereas an argument is blank.
true or false
valid or invalid
119
The argument is valid if all the blank AND the blank. It is invalid otherwise.
premises are true
conclusion is true
120
p
p → q
∴ q
Modus ponens
121
¬q
p → q
∴ ¬p
Modus tollens
122
p
∴ p ∨ q
Addition
123
p ∧ q
∴ p
Simplification
124
p
q
∴ p ∧ q
Conjunction
125
p → q
q → r
∴ p → r
Hypothetical syllogism
126
p ∨ q
¬p
∴ q
Disjunctive syllogism
127
p ∨ q
¬p ∨ r
∴ q ∨ r
Resolution
128
The validity of an argument can be established by applying the rules of inference and laws of propositional logic in a blank
logical proof
129
A logical proof of an argument is a blank, each of which consists of a proposition and a justification.
sequence of steps
130
Given p;
if p then q;
then q can be inferred
Modus ponens
131
Given NOT q;
if p then q;
then NOT p can be inferred
Modus tollens
132
Given p;
p OR q can be inferred
Addition
133
Given p AND q;
p can be inferred
Simplification
134
Given p;
Given q;
p AND q can be inferred
Conjunction
135
If p implies q;
and q implies r;
Then p implies r can be inferred
Hypothetical syllogism
136
Given p OR q;
Given NOT p;
Then q can be inferred
Disjunctive syllogism
137
Given p OR q;
Given NOT p OR r;
Then q OR r can be inferred
Resolution
138
A value that can be plugged in for variable x is called an blank of the domain of x.
element
139
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
quantifier
140
An blank of a domain has no special properties other than those shared by all the elements of the domain.
arbitrary element
141
A blank of the domain may have properties that are not shared by all the elements of the domain
particular element
142
The rules blank and blank replace a quantified variable with an element of the domain.
existential instantiation and universal instantiation
143
The rules blank and blank replace an element of the domain with a quantified variable.
existential generalization and universal generalization
144
c is an element (arbitrary or particular)
∀x P(x)
∴ P(c)
Universal instantiation
145
Sam is a student in the class.
Every student in the class completed the assignment.
Therefore, Sam completed his assignment.
Universal instantiation
146
c is an arbitrary element
P(c)
∴ ∀x P(x)
Universal generalization
147
Let c be an arbitrary integer.
c ≤ c2
Therefore, every integer is less than or equal to its square.
Universal generalization
148
There is an integer that is equal to its square.
Therefore, c2 = c, for some integer c.
Existential instantiation*
149
∃x P(x)
∴ (c is a particular element) ∧ P(c)
Existential instantiation*
150
c is an element (arbitrary or particular)
P(c)
∴ ∃x P(x)
Existential generalization
151
Sam is a particular student in the class.
Sam completed the assignment.
Therefore, there is a student in the class who completed the assignment.
Existential generalization
152
A blank is a statement that can be proven to be true
theorem
153
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.
proof
154
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
axioms
155
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.
exhaustion
156
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.
counterexample
157
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.
direct proof
158
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.
rational number
159
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.
contrapositive
160
An even integer can be expressed as blank for some integer k.
2k
161
An odd integer can be expressed as blank for some integer k.
2k + 1
162
An blank is a real number that is not rational.
irrational number
163
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.
contradiction
164
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.
indirect proof
165
Assume p. Follow a series of steps to conclude q.
direct proof
166
Assume ¬q. Follow a series of steps to conclude ¬p
proof by contrapositive
167
Assume p ∧ ¬q. Follow a series of logical steps to conclude r ∧ ¬r for some proposition.
proof by contradiction
168
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.
proof by cases
169
The blank of a number is whether that number is odd or even.
parity
