Propositional Logic Flashcards
A statement that is either true or false
Proposition
~
not
and
v
or
–>
If-Then
If and only if
IFF
If and only if
Either both are true or both are false
Bent Hyphen Symbol
Not
Alternatively, line over letter
Logical equivalent
The truth values of two statements are the same
Contrapositive
The negative of a statement
If p implies q, not q implies not p.
Converse
The reverse implication of a statement
P implies Q
Converse: Q implies P
An implication & its converse together are equivalent to what?
An IFF statement
The purpose of Truth tables
Assign truth values to propositional symbols & compound statements
De Morgan’s Law
Distributes a negative to a conjunction or disjunction
Tautology
A logical statement that is always true, regardless of the truth values of its variables
Contradiction
A logical statement that is always false, regardless of the truth values of the variables in it.
You can’t check a claim about an infinite set by checking a finite set of its elements
Therefore: propositions that involve all numbers have special set notation
Upside down A
For all
N
For the set of non-negative integers
E
rounded
Is a member of
Belongs to
Is in
Critical rows
The rows of a truth table where all premises are true
Validity
The conclusion is true no matter what truth values are assigned to individual propositional variables
Predicate
A proposition whose truth depends on the value of one or more variables
Predicate notation
Similar to functional notation:
P(n) ::= n is a perfect square
P(n) is either true or false depending on the value of n.
A universally quantified statement
An assertion that a predicate is always true
An existentially quantified statement
An assertion that a predicate is sometimes true
Upside down Ax E D, P(x)
For all x in D, P(x) is true
Reverse Ex D, P(x)
There exists an x in D such that P(x) is true
Modus Ponens
p
p –> q
q
- The cornerstone of deductive reasoning
If the antecedent of a conditional is true, then the consequent must also be true.
Modus Tollens
p –> q
~q
~p
If the consequent of a conditional is false, then the antecedent must also be false.
Satisfiable
A proposition is satisfiable if some setting of the variables makes the proposition true.
Disjunctive addition
A rule of inference pertaining to OR
Add any statement, true or false, to a true statement
p
p v q
Valid because a disjunction is true if at least one of its statements is true
Conjunctive simplification
A rule of inference pertaining to AND
In a given true conjunction, any conjunct can be separated out and is true.
p^q
p, q
Disjunctive Syllogism/ Disjunctive Inference
A rule of inference pertaining to OR
In a disjunction, if one disjunct is false, the other has to be true.
“The process of elimination”
p v q
~q
p
Hypothetical Syllogism
Chain Rule
A rule of inference pertaining to If/Then operator.
Given two conditionals, you can chain the conclusion.
p –> q
q –> r
p –> r
Proof by contradiction
To prove something, assume the converse & arrive at a contradiction.
Division into Cases
- List the Cases
- Give proof a proposition holds for each case
- conclude the overall proposition holds
p v q
p –> r
q –> r
r
Affirming the Consequent
Converse error,
Confusion of necessity and sufficiency
Inferring the converse from the original statement
p –> q
q
p
Denying the Antecedent
Inverse error
Inferring the inverse from the original statement
p –> q
~p
~q
Other Popular Sets: 0 struck through Z Q C
Empty set
Integers (Z)
Rational Numbers (Q)
Complex Numbers (C)
