Unit 1 Flashcards
Blank is the study of formal reasoning
Logic
A blank is a statement that is either true or false.
proposition
A proposition’s blank is a value indicating whether the proposition is actually true or false.
truth value
A blank shows the truth value of a proposition.
truth table
A blank is created by connecting individual propositions with logical operations
compound proposition
A blank combines propositions using a particular composition rule
logical operation
the conjunction operation is denoted by blank
∧
The proposition p ∧ q is read “p and q” and is called the blank of p and q
conjunction
The disjunction operation is denoted by blank
∨
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.
disjunction
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.
exclusive or
The blank operation is the same as the disjunction (∨) operation and evaluates to true when one or both of the propositions are true.
inclusive or
The blank operation acts on just one proposition and has the effect of reversing the truth value of the proposition.
negation
The negation of proposition p is denoted blank and is read as “not p”.
¬p
The negation operation is a blank, or an operation that acts on only one input.
unary operation
A logical operation combines blank using a particular composition rule.
propositions
The logical operator that joins two propositions with blank is called the conjunction and is denoted p ∧ q.
AND
The logical operator that joins two propositions with blank is called the disjunction and is denoted p ∨ q. It is the inclusive “or.”
OR
The logical operator that joins two propositions with blank but not both is called the exclusive “or” and is denoted p ⊕ q.
EITHER OR
The blank of a proposition changes it truth value and is denoted ¬p. For example, if p is true then ¬p is false.
negation
Blank is usually denoted with the symbol ⊕
The exclusive or operation
A blank can be created by using more than one operation.
compound proposition
Order of operations in absence of parentheses.
¬ (not)
∧ (and)
∨ (or)
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.
2^n
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
A compound proposition that uses a conditional operation is called a blank
conditional proposition
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
In p → q, the proposition p is called the blank, and the proposition q is called the blank.
hypothesis
conclusion
The blank of p → q is q → p.
converse
The blank of p → q is ¬q → ¬p.
contrapositive
The blank of p → q is ¬p → ¬q.
inverse
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
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
The term blank is an abbreviation of the expression “if and only if”, as in “p iff q”.
iff
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
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
p ∨ ¬p is a simple example of a blank
tautology
The proposition p ∧ ¬p is an example of a simple blank
contradiction
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
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
If s and r are two compound propositions, the notation blank is used to indicate that r and s are logically equivalent.
s ≡ r
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
Blank are logical equivalences that show how to correctly distribute a negation operation inside a parenthesized expression.
De Morgan’s laws
The first De Morgan’s law is:
¬(p ∨ q) ≡ (¬p ∧ ¬q)
The second version of De Morgan’s law swaps the role of the disjunction and conjunction:
¬(p ∧ q) ≡ (¬p ∨ ¬q)
f two propositions are blank, then one can be substituted for the other within a more complex proposition.
logically equivalent
p ∨ p ≡ p
Idempotent law
p ∧ p ≡ p
Idempotent law
( p ∨ q ) ∨ r ≡ p ∨ ( q ∨ r )
Associative laws
( p ∧ q ) ∧ r ≡ p ∧ ( q ∧ r )
Associative laws
p ∨ q ≡ q ∨ p
Commutative law
p ∧ q ≡ q ∧ p
Commutative law
p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r )
Distributive law
p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )
Distributive law
p ∨ F ≡ p
Identity law
p ∧ T ≡ p
Identity law
p ∧ F ≡ F
Domination law
p ∨ T ≡ T
Domination law
¬¬p ≡ p
Double negation law
p ∧ ¬p ≡ F
¬T ≡ F
Complement law
p ∨ ¬p ≡ T
¬F ≡ T
Complement law
¬( p ∨ q ) ≡ ¬p ∧ ¬q
De Morgan’s law
¬( p ∧ q ) ≡ ¬p ∨ ¬q
De Morgan’s law
p ∨ (p ∧ q) ≡ p
Absorption law
p ∧ (p ∨ q) ≡ p
Absorption law
p → q ≡ ¬p ∨ q
Conditional identities
p ↔ q ≡ ( p → q ) ∧ ( q → p )
Conditional identities
Since p ∧ q requires p, p ∨ (p ∧ q) is just p.
Absorption laws
Only applies when the operators are all ∧ or ∨. Rearranging the parentheses in an expression will not change its value.
Associative laws
Rearranging the propositions within a single disjunction or conjunction will not change its truth value.
Commutative laws
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
It is convenient sometimes to translate conditional statements into ones that involve the conjunction or disjunction.
Conditional identities
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
Reformulate conjunctions and disjunctions within logical proofs.
Distributive laws
The conjunction with a proposition that is false is always false. The disjunction with a proposition that is always true is true.
Domination laws
A double negative makes a positive.
Double negation law
To say p OR p or to say p AND p is redundant. In both cases, we just have p.
Idempotent laws
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
A logical statement whose truth value is a function of one or more variables is called a blank.
predicate
The blank of a variable in a predicate is the set of all possible values for the variable.
domain
The symbol blank is a universal quantifier
∀
the statement ∀x P(x) is called a blank.
universally quantified statement
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
A blank for a universally quantified statement is an element in the domain for which the predicate is false.
counterexample
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
The symbol blank is an existential quantifier
∃
the statement ∃x P(x) is called a blank.
existentially quantified statement
∃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
The universal and existential quantifiers are generically called blank
quantifiers
A logical statement that includes a universal or existential quantifier is called a blank.
quantified statement
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
The variable x in the statement ∀x P(x) is a blank because the variable is bound to a quantifier.
bound variable
A statement with no free variables is a blank because the statement’s truth value can be determined.
proposition
The rule of order to evaluate a compound quantified statement is to apply the blank (∀,∃) before the blank (∧, ∨, → and ↔).
quantifiers
logical operations
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
¬∀x F(x) ≡ ∃x ¬F(x).
De Morgan’s law for quantified statements
¬∃x P(x) ≡ ∀x ¬P(x)
De Morgan’s laws for quantified statements
A logical expression with more than one quantifier that bind different variables in the same predicate is said to have blank
nested quantifiers
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
Read nested quantifiers from blank
left to right.
∀x∀y M(x,y)
For every pair of x and y, M(x,y) is true
∃x∃y M(x,y)
There exists at least one pair of x and y such that M(x,y) is true
∃x∀y M(x,y)
There exists at least one x that pairs with ALL y, such that M(x,y) is true
∀x∃y M(x,y)
For each x, there is at least one y, such that M(x,y) is true
¬∀x ∀y P(x, y) ≡ ?
∃x ∃y ¬P(x, y)
¬∀x ∃y P(x, y) ≡ ?
∃x ∀y ¬P(x, y)
¬∃x ∀y P(x, y) ≡ ?
∀x ∃y ¬P(x, y)
¬∃x ∃y P(x, y) ≡ ?
∀x ∀y ¬P(x, y)
¬∀x ∀y P(x, y) ≡ ∃x ∃y ¬P(x, y)
It is not true for all x and for all y, P(x, y).
¬∀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
¬∃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
¬∃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.
An blank is a sequence of propositions or hypotheses, followed by a final proposition, called the conclusion.
argument
An argument is valid if the conclusion is blank whenever the hypotheses are all true, otherwise the argument is invalid.
true
The blank of an argument expressed in English is obtained by replacing each individual proposition with a variable.
form
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
Symbolically we can express the argument as blank
(p1 ∧ p2∧ … ∧ pn) → c
A proposition can be blank whereas an argument is blank.
true or false
valid or invalid
The argument is valid if all the blank AND the blank. It is invalid otherwise.
premises are true
conclusion is true
p
p → q
∴ q
Modus ponens
¬q
p → q
∴ ¬p
Modus tollens
p
∴ p ∨ q
Addition
p ∧ q
∴ p
Simplification
p
q
∴ p ∧ q
Conjunction
p → q
q → r
∴ p → r
Hypothetical syllogism
p ∨ q
¬p
∴ q
Disjunctive syllogism
p ∨ q
¬p ∨ r
∴ q ∨ r
Resolution
The validity of an argument can be established by applying the rules of inference and laws of propositional logic in a blank
logical proof
A logical proof of an argument is a blank, each of which consists of a proposition and a justification.
sequence of steps
Given p;
if p then q;
then q can be inferred
Modus ponens
Given NOT q;
if p then q;
then NOT p can be inferred
Modus tollens
Given p;
p OR q can be inferred
Addition
Given p AND q;
p can be inferred
Simplification
Given p;
Given q;
p AND q can be inferred
Conjunction
If p implies q;
and q implies r;
Then p implies r can be inferred
Hypothetical syllogism
Given p OR q;
Given NOT p;
Then q can be inferred
Disjunctive syllogism
Given p OR q;
Given NOT p OR r;
Then q OR r can be inferred
Resolution
A value that can be plugged in for variable x is called an blank of the domain of x.
element
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
An blank of a domain has no special properties other than those shared by all the elements of the domain.
arbitrary element
A blank of the domain may have properties that are not shared by all the elements of the domain
particular element
The rules blank and blank replace a quantified variable with an element of the domain.
existential instantiation and universal instantiation
The rules blank and blank replace an element of the domain with a quantified variable.
existential generalization and universal generalization
c is an element (arbitrary or particular)
∀x P(x)
∴ P(c)
Universal instantiation
Sam is a student in the class.
Every student in the class completed the assignment.
Therefore, Sam completed his assignment.
Universal instantiation
c is an arbitrary element
P(c)
∴ ∀x P(x)
Universal generalization
Let c be an arbitrary integer.
c ≤ c2
Therefore, every integer is less than or equal to its square.
Universal generalization
There is an integer that is equal to its square.
Therefore, c2 = c, for some integer c.
Existential instantiation*
∃x P(x)
∴ (c is a particular element) ∧ P(c)
Existential instantiation*
c is an element (arbitrary or particular)
P(c)
∴ ∃x P(x)
Existential generalization
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
A blank is a statement that can be proven to be true
theorem
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
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
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
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
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
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
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
An even integer can be expressed as blank for some integer k.
2k
An odd integer can be expressed as blank for some integer k.
2k + 1
An blank is a real number that is not rational.
irrational number
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
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
Assume p. Follow a series of steps to conclude q.
direct proof
Assume ¬q. Follow a series of steps to conclude ¬p
proof by contrapositive
Assume p ∧ ¬q. Follow a series of logical steps to conclude r ∧ ¬r for some proposition.
proof by contradiction
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
The blank of a number is whether that number is odd or even.
parity
