Logic Study Guide: Chapters 2.2 - 3.4

Conditional Statement

An assertion of the form 'If p then q', expressed as p → q.

Truth Table

A table showing all possible truths of a statement and its components.

Vacuously True

A statement that is considered true because its hypothesis is false.

Contrapositive

The statement ~q → ~p, which is logically equivalent to the original conditional.

Modus Ponens

A valid argument form: If p → q and p are true, then q is true.

Predicates

Statements containing variables, represented as P(x), where the truth depends on the variable.

Universal Quantifier (∀)

Indicates that a statement is true for all elements in a domain.

Existential Quantifier (∃)

Indicates that there exists at least one element in a domain for which a statement is true.

Negation of Universal Statement

~(∀x, P(x)) ≡ ∃x such that ~P(x), meaning 'not all P are true'.

Biconditional Statement

A statement of the form p ↔ q, meaning 'p if and only if q'.

Valid Argument

An argument where it is impossible for all premises to be true and the conclusion false.

Order of Quantifiers

The sequence of quantifiers matters when different types are used; order doesn't matter with the same type.

Universal Instantiation

If ∀x, P(x) is true, then for any particular element a, P(a) is also true.

Inverse Error

An invalid conclusion resulting from asserting that if p → q and ~p, then ~q is true.

Biconditional Truth Table

A table showing the truth values of the biconditional statement p ↔ q.

Element of (∈)

Symbol indicating that an element belongs to a set.

Subset (⊆)

Symbol indicating that one set is contained within another.

Converse

The statement q → p, which is NOT logically equivalent to the original conditional p → q.

Inverse

The statement ~p → ~q, which is NOT logically equivalent to the original conditional p → q but is equivalent to the converse.

Modus Tollens

A valid argument form: If p → q and ~q are true, then ~p must be true.

Universal Modus Ponens

A valid argument form combining universal instantiation with modus ponens: ∀x, if P(x) then Q(x); P(a) for a particular a; therefore Q(a).

Universal Modus Tollens

A valid argument form combining universal instantiation with modus tollens: ∀x, if P(x) then Q(x); ~Q(a) for a particular a; therefore ~P(a).

Converse Error

An invalid conclusion resulting from asserting that if p → q and q, then p is true.

Transitivity

A valid argument form: If p → q and q → r, then p → r.

Necessary Condition

"q is a necessary condition for p" means p → q (p cannot be true without q also being true).

Sufficient Condition

"q is a sufficient condition for p" means q → p (if q is true, then p must be true).

Only If

"p only if q" means p → q.

Truth Set

The set of all values that make a predicate true.

Negation of Existential Statement

~(∃x such that P(x)) ≡ ∀x, ~P(x), meaning "there does not exist any x such that P(x)" is equivalent to "for all x, P(x) is false."

Negation of Universal Conditional

~(∀x, if P(x) then Q(x)) ≡ ∃x such that P(x) ∧ ~Q(x)

Conditional Equivalence

p → q ≡ ~p ∨ q (a conditional statement is equivalent to the disjunction of the negation of its hypothesis and its conclusion)

Multiple Quantifier Negation

The negation of ∀x, ∃y such that P(x,y) is ∃x, ∀y such that ~P(x,y)

Proof by Division into Cases

A valid argument form: p ∨ q, p → r, q → r; therefore r.

Contradiction Rule

If ~p leads to a contradiction, then p must be true.

Explicit vs. Implicit Quantification

Explicit quantification uses quantifier symbols; implicit quantification is understood from context (e.g., "If a number is even, then it is divisible by 2" implicitly means "For all numbers, if a number is even, then it is divisible by 2").

Vacuous Truth of Universal Statements

A universal statement ∀x ∈ D, if P(x) then Q(x) is vacuously true if P(x) is false for every x in D.

Order of Operations in Logic

1. Negation (~), 2) Conjunction (∧) and Disjunction (∨), 3) Conditional (→) and Biconditional (↔)