LOGIC

Statement

A declarative sentence that can be classified as either true or false, but not both. Its truth or falsity is called its truth value.

Truth Value

The classification of a proposition as true (T) or false (F).

Proposition

Any meaningful statement that is true or false, but not both. Denoted by lowercase letters p, q, r, …

Compound Proposition

A new proposition formed by combining atomic propositions using logical connectives (NOT, OR, AND, IF-THEN, IF AND ONLY IF). Denoted by uppercase P, Q, R, …

Atomic Proposition

A simple, indivisible proposition that serves as the basic building block for compound propositions.

Negation (NOT, ~p)

The logical opposite of proposition p. When p is true, ~p is false; when p is false, ~p is true.

Disjunction (OR, p v q)

The proposition “p or q.” False only when both p and q are false; true in all other cases. The “or” is inclusive.

Conjunction (AND, p ^ q)

The proposition “p and q.” True only when both p and q are true; false in all other cases.

Conditional / Implication (p => q)

The proposition “if p, then q.” False only when p is true and q is false; true in all other cases.

Biconditional (p

The proposition “p if and only if q.” True when p and q share the same truth value; false when they differ. Also called the equivalence connective.

Antecedent (Hypothesis)

In the conditional p => q, the proposition p — the “if” part that acts as the condition triggering the conclusion.

Consequent (Conclusion)

In the conditional p => q, the proposition q — the outcome asserted to follow when the hypothesis is true.

Sufficient Condition

p is a sufficient condition for q means p => q: the truth of p alone is enough to guarantee the truth of q.

Necessary Condition

q is a necessary condition for p means p => q: p can only be true if q is also true.

Equivalent Forms of the Conditional

“If p then q,” “p implies q,” “p only if q,” “q if p,” “q whenever p,” “q provided that p,” “p is sufficient for q,” and “q is necessary for p” all express the same conditional statement p => q.

Truth Table

A systematic table listing all possible combinations of truth values for propositions and the resulting truth value of the compound proposition formed from them.

Negation Truth Table

p = T gives ~p = F; p = F gives ~p = T. Two rows total.

Disjunction Truth Table

p v q is FALSE only when both p = F and q = F. TRUE in all other three combinations (TT, TF, FT).

Conjunction Truth Table

p ^ q is TRUE only when both p = T and q = T. FALSE in all other three combinations (TF, FT, FF).

Conditional Truth Table

p => q is FALSE only when p = T and q = F. TRUE in the remaining three combinations (TT, FT, FF).

Biconditional Truth Table

p

Propositional Function

Another name for a compound proposition or predicate — a statement whose truth value depends on the values of one or more variables.

Predicate

An expression involving one or more variables defined on a domain of discourse. Substituting a specific value produces a proposition that is either true or false. Example: p(n): n is prime.

Domain of Discourse

The set of all possible values that a variable in a predicate can take.

Free Variable

The variable x in a predicate p(x) whose substitution with specific values changes the truth value of the expression.

Truth Set (Tp)

The collection of all values in the domain for which the predicate p(x) is true.

Universal Quantifier (for all, symbol: inverted A)

Read “for every,” “for all,” or “for each.” The statement [for all] x, p(x) asserts that p(x) holds true for every element x in the domain.

Existential Quantifier (there exists, symbol: backwards E)

Read “there exists” or “there is at least one.” The statement [there exists] x such that p(x) asserts p(x) is true for at least one x in the domain.

“Such That” Symbol

Shorthand notation (symbol: backwards E with vertical bar) meaning “such that,” used alongside the existential quantifier: [there exists] x such that p(x).

Negation of a Universal Statement

The negation of “[for all] x, p(x)” is “[there exists] x such that ~p(x).” Negating “all have property P” yields “at least one does not have property P.”

Negation of an Existential Statement

The negation of “[there exists] x such that p(x)” is “[for all] x, ~p(x).” Negating “some have property P” yields “none have property P.”

Order of Quantifiers

The order in which quantifiers appear changes meaning and truth value. “[for all] x [there exists] y p(x,y)” and “[there exists] y [for all] x p(x,y)” are generally NOT equivalent.

Implicit Universal Quantifier

When a variable appears in the antecedent of an implication without explicit quantification, the universal quantifier is assumed to apply by convention.

Set

A well-defined collection of objects (elements or members) characterized by a defining property, allowing the objects to be thought of as a whole. Example: A = {1, 2, 3, 4}.

Element / Member (in-symbol)

An object belonging to a set. Written x in A. If the object does not belong, written x not-in A. Example: If A = {1,2,3,4}, then 2 in A and 5 not-in A.

Subset (A subset-of B)

A is a subset of B if every element of A is also an element of B. Written A subset-of B (equivalently, B superset-of A).

Proper Subset

A is a proper subset of B if A is a subset of B and A does not equal B — A is strictly contained within B.

Set Equality (A = B)

Two sets are equal if A is a subset of B and B is a subset of A — they contain exactly the same elements.

Empty Set

The unique set containing no elements, denoted by the empty-set symbol. By Theorem 1.1, the empty set is a subset of every set.

Standard Number Set N

The set of all positive integers (natural numbers): {1, 2, 3, …}.

Standard Number Set Z

The set of all integers: {…, -2, -1, 0, 1, 2, …}.

Standard Number Set Q

The set of all rational numbers — numbers expressible as p/q where p, q are integers and q is not zero.

Standard Number Set R

The set of all real numbers, including rationals and irrationals.

Union (A union B)

A union B = {x : x in A or x in B}. The set of all elements belonging to A or B or both. Corresponds to logical disjunction (OR).

Intersection (A intersect B)

A intersect B = {x : x in A and x in B}. The set of elements belonging to both A and B simultaneously. Corresponds to logical conjunction (AND).

Set Difference (A minus B)

A minus B = {x : x in A and x not-in B}. Elements in A that are not in B. Corresponds to (x in A) AND NOT (x in B).

Disjoint Sets

Sets A and B are disjoint if their intersection is the empty set — they share no common elements.

Closed Interval [a, b]

{x in R : a <= x <= b}. All real numbers between a and b, with both endpoints included.

Open Interval (a, b)

{x in R : a < x < b}. All real numbers strictly between a and b; neither endpoint is included.

Half-Open Interval [a, b)

{x in R : a <= x < b}. Includes the left endpoint a but excludes the right endpoint b.

Half-Open Interval (a, b]

{x in R : a < x <= b}. Excludes the left endpoint a but includes the right endpoint b.

Unbounded Interval [a, infinity)

{x in R : x >= a}. All real numbers greater than or equal to a, with no upper bound.

Unbounded Interval (a, infinity)

{x in R : x > a}. All real numbers strictly greater than a, with no upper bound.

Unbounded Interval (-infinity, b]

{x in R : x <= b}. All real numbers less than or equal to b, with no lower bound.

Unbounded Interval (-infinity, b)

{x in R : x < b}. All real numbers strictly less than b, with no lower bound.