Propositional Logic Flashcards
A proposition is a
declaration of fact that is either true or false, but not both
¬
Negation
not
∧
Conjunction
and
∨
Disjunction
(inclusive) or
⨁
Exclusive Disjunction
exclusive or, xor
→
Conditional
If .. then, ..implies..
↔
Biconditional
if and only if, iff
negation is defined by the following truth table:
Objects cannot be negated, only statements
Incorrect negation:
¬JackistallerthanJoe ≡(¬Jackistallerthan¬Joe)
The correct negation is:
¬JackistallerthanJoe ≡JackisatmostastallasJoe.
Negation Rules for Inequalities
the negation of a strict inequality is non-strict inequality and vice versa.
¬𝑥>𝑦 ≡(𝑥≤𝑦)
¬𝑥≥𝑦 ≡(𝑥<𝑦)
You must exercise special care when negating a double inequality.
The correct negation of 1 ≤ 𝑥 ≤ 2 is
𝑥<1∨𝑥>2
Conjunction
Disjunction
Exclusive Disjunction (aka Exclusive Or)
Conditional
Biconditional
𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞) ∧ (𝑞 → 𝑝)
Observe that 𝑝 ↔ 𝑞 is the negation of
𝑝⨁𝑞.
Also observe that the biconditional is true exactly when p and q have the same truth value, whether that is true or false.
It is not a very good idea to attempt to reduce the understanding of “necessary” and “sufficient” typestatements to the mindlessly symbolical level.
Just like “sufficient” type phrases in English defy simplistic word order analysis, so do “necessary” type statements.
It is helpful to change “necessary” to
“precondition”.For example, we rephrase
“A cloudless sky is necessary to see the stars” as
“A cloudless sky is a precondition for seeing the stars.”
The word precondition makes it clear that the cloudless sky does not guarantee that we can see the stars
“p only if q” means
𝑝 → 𝑞
If you find this hard to remember, just translate the conditional as if the word only was not there, and then switch premise and conclusion.
“p unless q” means
¬𝑞 → 𝑝
This rule shows that unless means if not. “You will get sick unless you take the medicine” means “You will get sick if you don’t take the medicine.”
𝑞 → 𝑝 is called the converse of
𝑝 → 𝑞
¬𝑝 → ¬𝑞 is called the inverse of
𝑝 → 𝑞
¬𝑞 → ¬𝑝 is called the contrapositive of
𝑝 → 𝑞
Order of Operations
- negation
- conjunction
- disjunction
- conditional
- biconditional
Logical Operators on Bitstrings
tautology
A compound proposition that is always true, regardless of the truth values of the individual propositions involved
contradiction
A compound proposition that is always false, regardless of the truth values of the individual propositions involved
contingency
A compound statement that is neither a tautology nor a contradiction
Logical equivalence
two compound statements 𝑝 and 𝑞 “equal” ifthey always share the same truth value
use the symbol ≡ to represent logical equivalence
Using the biconditional and the concept of a tautology that we just introduced, we can formally define logical equivalence as follows:
𝑝 ≡ 𝑞 means that 𝑝 ↔ 𝑞 is a tautology.
An alternative definition is that 𝑝 ≡ 𝑞 means that 𝑝 and 𝑞 share the same truth table.
“Equivalent” vs “Equal”
Do not use the words “equivalent” and “equal” interchangeably . Equivalenceapplies to statements. Two quantities that are the same are equal. If you fail to keep this distinction in mind when dealing with statements that are about quantities, you are in danger of making wholly nonsensical statements.
An important logical equivalence
𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞
Unlike other important logical equivalences, 𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞 does not have a commonly agreed upon name. Technically, we could consider this law the definition of the conditional, so we will refer to it by that name
The Laws of De Morgan
The negation of a conjunction must be the disjunction of the negations. There is also a symmetric law of De Morgan which is obtained by switching the roles of conjunction and disjunction.
Both laws can be formally proved by truth table.
¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞
¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞
Negation of Conditionals
To negate a conditional, we must rewrite it using disjunction and negation, and then carefully apply De Morgan.
¬𝑝→𝑞 ≡¬¬𝑝∨𝑞 ≡ 𝑝∧¬𝑞
De Morgan and Double Inequalities
The correct negation of 1 ≤ 𝑥 ≤ 2 is
𝑥<1∨𝑥>2
To understand this, consider that the original double inequality is a conjunction of two inequalities:
1 ≤ 𝑥 ≤ 2 ≡ 1 ≤ 𝑥 ∧ 𝑥 ≤ 2.
Thereby, by De Morgan, the negation is the disjunction of the individual inequalities, which leads to 𝑥 < 1 ∨ 𝑥 > 2.
Commutative laws
𝑝∨𝑞≡𝑞∨𝑝
𝑝∧𝑞≡𝑞∧𝑝
Associate laws
𝑝 ∨ (𝑞 ∨ 𝑟) ≡ (𝑝 ∨ 𝑞) ∨ 𝑟
𝑝 ∧ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ 𝑞) ∧ 𝑟
Distributive Laws
𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)
𝑝∧ (𝑞∨𝑟) ≡(𝑝∧𝑞)∨(𝑝∧𝑟)
Identity Laws
𝑝∨𝐹≡𝑝
𝑝∧𝑇≡𝑝
Domination Laws
𝑝∨𝑇≡𝑇
𝑝∧𝐹≡𝐹
Idempotent Laws
𝑝∨𝑝≡𝑝
𝑝∧𝑝≡𝑝
Double Negation Law
¬(¬𝑝) ≡ 𝑝
Absorption Laws
𝑝∨ (𝑝∧𝑞) ≡𝑝
𝑝 ∧ (𝑝 ∨ 𝑞) ≡ 𝑝
Logical Equivalence of Conditionals
It is an important fact that a conditional is logically equivalent to its contrapositive, but not to its inverse or converse.
𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝
Since the inverse is the contrapositive of the converse, inverse and converse are logically equivalent to each other:
𝑞 → 𝑝 ≡ ¬𝑝 → ¬𝑞
Logical Equivalence of Conditionals Diagram
