CSE2500 Chapter 3: THE LOGIC OF QUANTIFIED STATEMENTS

Universal Quantifier (∀)

Symbol meaning "for all," "for every," "for each," or "for any." Used to express that a predicate is true for all elements in a domain.

Existential Quantifier (∃)

Symbol meaning "there exists," "for some," or "there is at least one." Used to express that a predicate is true for at least one element in a domain.

Predicate

A statement that contains one or more variables and becomes a proposition when specific values are assigned to the variables.

Domain

The set of all possible values that may be assigned to the variables in a predicate.

Truth Set

The set of all values from the domain that make a predicate true.

Conditional (⇒)

Symbol meaning "if...then" or "implies." Used to express that one statement implies another.

Biconditional (⇔)

Symbol meaning "if and only if." Used to express that two statements imply each other.

Negation (¬)

Symbol meaning "not." Used to express the opposite truth value of a statement.

Conjunction (∧)

Symbol meaning "and." Used to express that both statements are true.

Disjunction (∨)

Symbol meaning "or." Used to express that at least one of the statements is true.

Universal Statement

A statement of the form "∀x, P(x)" which asserts that the predicate P is true for all values of x in the domain.

Existential Statement

A statement of the form "∃x, P(x)" which asserts that the predicate P is true for at least one value of x in the domain.

Universal Conditional Statement

A statement of the form "∀x, if P(x) then Q(x)" which asserts that for all x, whenever P(x) is true, Q(x) is also true.

Implicit Quantification

The use of language that implies universal or existential quantification without explicitly using "all," "every," or "there exists" (e.g., using "a" or "the").

Negation of Universal Statement

¬(∀x, P(x)) ≡ ∃x, ¬P(x). The negation of "all are" is "some are not."

Negation of Existential Statement

¬(∃x, P(x)) ≡ ∀x, ¬P(x). The negation of "some are" is "none are" or "all are not."

Negation of Universal Conditional

¬(∀x, if P(x) then Q(x)) ≡ ∃x, P(x) ∧ ¬Q(x). The negation of "all X with property P have property Q" is "some X with property P do not have property Q."

Negation of Multiple Quantifiers

When negating statements with multiple quantifiers, change each quantifier type (∀ becomes ∃, ∃ becomes ∀) and negate the predicate.

Contrapositive

For a conditional statement "if P then Q," the contrapositive is "if not Q then not P." A conditional and its contrapositive are logically equivalent.

Converse

For a conditional statement "if P then Q," the converse is "if Q then P." A conditional and its converse are not necessarily logically equivalent.

Inverse

For a conditional statement "if P then Q," the inverse is "if not P then not Q." A conditional and its inverse are not necessarily logically equivalent.

Sufficient Condition

P is a sufficient condition for Q means "if P then Q." When P is true, Q must be true.

Necessary Condition

P is a necessary condition for Q means "if Q then P" or "only if P, Q." Q cannot be true unless P is true.

Vacuous Truth

A universal statement that is true because the condition in the "if" part is never satisfied (the domain is empty or the condition is false for all elements).

∀x ∃y P(x,y)

"For every x, there exists a y such that P(x,y)" - means that for each x, you can find a (possibly different) y that satisfies property P.

∃y ∀x P(x,y)

"There exists a y such that for every x, P(x,y)" - means there is one specific y that works for all x.

Quantifier Order

The order of different quantifiers (∀ and ∃) matters and changing their order typically changes the meaning of the statement.

Same Quantifier Order

The order of same-type quantifiers (∀∀ or ∃∃) doesn't affect the meaning: ∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y) and ∃x ∃y P(x,y) ≡ ∃y ∃x P(x,y).

Universal Instantiation

A rule of inference that allows us to derive a specific instance from a universal statement. From "∀x, P(x)" and "a is in the domain," we can conclude "P(a)."

Universal Modus Ponens

A valid argument form combining universal instantiation with modus ponens: From "∀x, if P(x) then Q(x)" and "P(a)," we can conclude "Q(a)."

Universal Modus Tollens

A valid argument form combining universal instantiation with modus tollens: From "∀x, if P(x) then Q(x)" and "¬Q(a)," we can conclude "¬P(a)."

Converse Error

The logical fallacy of incorrectly assuming that the converse of a conditional statement is true when the original statement is true.

Inverse Error

The logical fallacy of incorrectly assuming that the inverse of a conditional statement is true when the original statement is true.

Relation Between ∀ and ∧

For a finite domain {a,b,c}, the statement "∀x ∈ {a,b,c}, P(x)" is equivalent to "P(a) ∧ P(b) ∧ P(c)."

Relation Between ∃ and ∨

For a finite domain {a,b,c}, the statement "∃x ∈ {a,b,c}, P(x)" is equivalent to "P(a) ∨ P(b) ∨ P(c)."

De Morgan's Laws for Quantifiers

¬(∀x, P(x)) ≡ ∃x, ¬P(x) and ¬(∃x, P(x)) ≡ ∀x, ¬P(x). These are analogous to De Morgan's laws for AND and OR.

Formal Logical Notation

A precise symbolic representation where "∀x in D, P(x)" is written as "∀x (x in D → P(x))" and "∃x in D such that P(x)" is written as "∃x (x in D ∧ P(x))."

Tarski's World

A computer program developed to teach logic principles by providing visual representations of logical statements using blocks of various shapes, sizes, and colors.

Counterexample

A specific instance that disproves a universal statement. Finding just one counterexample proves that a universal statement is false.

Proof by Contradiction

A proof technique that assumes the opposite of what you want to prove, then shows this assumption leads to a contradiction, thereby proving the original statement.

Universal Transitivity

A rule of inference that allows us to conclude "∀x, if P(x) then R(x)" from "∀x, if P(x) then Q(x)" and "∀x, if Q(x) then R(x)."