MATH381H Flashcards

¬p

Negation of p, “not p”, 1 truth

p∧q

Conjunction of p and q, “p and q”, 1 truth

p∨q

Disjunction of p and q, “p or q”, 3 truths

p⊕q

Exclusive or of p and q, “p XOR q”, 2 truths

p→q

Conditional statement, “p implies q”, “q whenever p”, 3 truths

p↔q

Biconditional statement, “p if and only if q”, 2 truths

Converse of p→q

q→p

Contrapositive of p→q

¬q→¬p

Inverse of p→q

¬p→¬q

Precedence of Logical Operations

¬, ∧, ∨, →, ↔

Tautology

A compound proposition that is always true

Contradiction

A compound proposition that is always false

Contingency

A compound proposition that is neither a tautology or a contradiction

p≡q

Logical equivalence, “p and q are logically equivalent”

Conditional Disjunction Equivalence

p→q≡¬p∧q

Identity laws

p∧T≡p
p∨F≡p

Domination Laws

p∨T≡T
p∧F≡F

Idempotent Laws

p∨p≡p
p∧p≡p

Double Negation Law

¬(¬p)≡p

Commutative Laws

p∨q≡q∨p
p∧q≡q∧p

Associative Laws

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

Distributive Laws

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

De Morgan’s Laws

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

Absorption Laws

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

Negation Laws

p∨¬p≡T
p∧¬p≡F

Material Implication (or Implication Law)

p→q≡¬p∨q

Contrapositive Law

p→q≡¬q→¬p

Disjunction as Implication

p∨q≡¬p→q

Conjunction as Implication

p∧q≡¬(p→¬q)

Negation of Implication

¬(p→q)≡p∧¬q

Distributing the Premise over Conjunction

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

Distributing the Conclusion over Disjunction

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

Distributing the Premise over Disjunction

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

Distributing the Conclusion over Conjunction

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

Definition of the Biconditional Statement

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

The Negation Equivalence

p↔q≡¬p↔¬q

The Matching Rule

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

The Negation of a Biconditional

¬(p↔q)≡p↔¬q

Modus Ponens Argument

p→q
p
———
∴ q

Modus Tollens Argument

p→q
¬q

———

∴ ¬p

Hypothetical Syllogism

p→q
q→r
———

∴ p→r

Simplification

p∧q
———
∴ p

Disjunctive Syllogism

p∨q
¬p
———
∴ q

Conjunction

p

q

———

∴ p∧q

Addition

p

———

∴ p∨q

Resolution

p∨q
¬p∨r

———

∴ q∨r

Universal Quantification

∀xP(x), “For all x, P(x)”

Existential Quantification

∃xP(x), “There exists x such that P(x)”

Belongs to

∈

Negation of the Universal Quantifier

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

Negation of the Existential Quantifier

¬(∃xQ(X))≡∀x¬Q(x)

Nested Quantifier ∀x∀yP(x,y)

Set x to be some value and then check the validity for ∀yP(x,y). So long as this is true for every choice of x, ∀x∀yP(x,y) is true.

Nested Quantifier ∀x∃yP(x,y)

Set x to be some value and ensure that there is some y such that P(x,y) is true.

Nested Quantifier ∃x∀yP(x,y)

Loop through all x in the domain and check if at least 1 satisfies ∀yP(x,y).

Nested Quantifier ∃x∃yP(x,y)

Loop through all x and check if at least 1 y satisfies P(x,y)

Universal Instantiation

∀xP(x)

———

∴ P(c)

Universal generalization

P(c) (for some c)

———

∴ ∀xP(x)

Existential Instantiation

∃xP(x)

———

∴ P(c)

Existential Generalization

P(c)

———

∴ ∃xP(x)