Ch 3. Key Terms

Absolute Value: The distance of a real number from zero on the number line; defined piecewise so that [latex]|x| = x[/latex] if [latex]\geq 0[/latex] and [latex]|x| = -x[/latex] if [latex]x < 0[/latex]. Addition (Rule of Inference): A rule of inference that allows a true proposition [latex]p[/latex] to be extended to the disjunction [latex]p \lor q[/latex].

Argument: A sequence of propositions consisting of one or more premises followed by a conclusion, where the conclusion is claimed to follow logically from the premises.

Axiom: A statement assumed to be true without proof and used as a foundational truth from which other results are derived.

Biconditional: A logical statement of the form [latex]p \leftrightarrow q[/latex], meaning “[latex]p[/latex] if and only if [latex]q[/latex],” which is true when both propositions have the same truth value.

Bound Variable: A variable that is quantified by a universal or existential quantifier and forms part of a complete proposition.

Ceiling Function: The function that maps a real number to the smallest integer greater than or equal to that number, denoted [latex]\lceil x \rceil[/latex].

Conjunction: A logical connective represented by [latex]p \land q[/latex], which is true only when both component propositions are true.

Conjunction (Rule of Inference): A rule of inference that allows two true propositions [latex]p[/latex] and [latex]q[/latex] to be combined into [latex]p \lor q[/latex].

Conditional Proposition: A logical statement of the form [latex]p \rightarrow q[/latex], meaning “if [latex]p[/latex], then [latex]q[/latex].”

Contradiction: A situation in which two or more statements cannot all be true at the same time.

Contrapositive: The statement [latex]\neg q \rightarrow \neg p[/latex], which is logically equivalent to the conditional proposition [latex]p \rightarrow q[/latex].

Corollary: A result that follows directly from a theorem or lemma with little or no additional proof.

Counterexample: A specific example that disproves a universally quantified statement by satisfying the hypothesis but violating the conclusion.

Deductive Argument: An argument in which the conclusion necessarily follows from the premises if the argument is valid.

Deductive Reasoning: A form of reasoning that applies general rules to specific cases to reach a necessary conclusion.

De Morgan’s Laws: Logical equivalences that relate conjunctions and disjunctions under negation, such as [latex]\neg (p \land q) \equiv \neg p \lor \neg q[/latex].

Direct Proof: A proof technique in which the hypothesis is assumed to be true and logical reasoning is used to show that the conclusion must also be true.

Disjunctive Syllogism: A rule of inference stating that if [latex]p \lor q[/latex] is true and [latex]p[/latex] is false, then [latex]q[/latex] must be true.

Disjunction: A logical connective represented by [latex]p \lor q[/latex], which is true when at least one of the propositions is true.

Domain of Discourse: The set of all possible values that a variable in a predicate or quantified statement can take.

Existence Proof: A proof that demonstrates that at least one object with a given property exists.

Existential Generalization: A rule of inference that allows one to conclude [latex]\exists x P(x)[/latex] from [latex]P(d)[/latex] for a specific element [latex]d[/latex].

Existential Instantiation: A rule of inference that allows a specific instance to be considered when an existentially quantified statement is given.

Existentially Quantified Statement: A statement of the form [latex]\exists x P(x)[/latex], asserting that there is at least one element in the domain for which the predicate is true.

Exhaustive Proof: A proof by cases in which all possible cases are considered.

Fallacy of Affirming the Conclusion: An invalid form of reasoning that assumes [latex]p[/latex] must be true because [latex]p \rightarrow q[/latex] and [latex]q[/latex] is true.

Floor Function: The function that maps a real number to the greatest integer less than or equal to that number, denoted [latex]\lfloor x \rfloor[/latex].

Free Variable: A variable that is not bound by a quantifier and does not form a complete proposition.

Generalized De Morgan’s Laws: Extensions of De Morgan’s Laws that apply to universally and existentially quantified statements.

Hypothetical Syllogism: A rule of inference that allows the conclusion [latex]p \rightarrow r[/latex] from the premises [latex]p \rightarrow q[/latex] and [latex]q \rightarrow r[/latex].

Inductive Hypothesis: The assumption in mathematical induction that a statement [latex]P(n)[/latex] is true for an arbitrary integer [latex]n[/latex].

Indirect Proof: A proof that establishes a result without proving it directly; proof by contradiction is a common example.

Lemma: A supporting result that helps establish a larger or more important theorem.

Logical Equivalence: A relationship between statements that always have the same truth value, denoted by [latex]\equiv[/latex].

Loop Invariant: A condition that remains true before and after every iteration of a loop and is used to reason about algorithm correctness.

Mathematical Induction: A proof technique used to show that a statement holds for all integers greater than or equal to a given value.

Mathematical System: A structured framework consisting of undefined terms, definitions, axioms, rules of inference, and theorems.

Modus Ponens: A rule of inference stating that from [latex]p \rightarrow q[/latex] and [latex]p[/latex], one may conclude [latex]q[/latex].

Modus Tollens: A rule of inference stating that from [latex]p \rightarrow q[/latex] and [latex]\neq q[/latex], one may conclude [latex]\neq p[/latex].

Negation: A logical operation that reverses the truth value of a proposition, denoted by [latex]\neq p[/latex].

Nested Quantifiers: Statements containing more than one quantifier, where the order of quantifiers affects the meaning.

Predicate (Propositional Function): A statement containing a variable that becomes a proposition when the variable is assigned a value.

Proof: A logical argument that establishes the truth of a mathematical statement using definitions, axioms, and previously proven results.

Proof by Cases: A proof technique that establishes a statement by considering all possible cases.

Proof by Contradiction: A proof technique in which the negation of the desired conclusion is assumed and shown to lead to a contradiction.

Proof of Equivalence: A proof that shows two statements are equivalent by proving each implies the other.

Proposition: A declarative statement that is either true or false, but not both.

Rule of Inference: A logical rule that allows new statements to be derived from existing ones.

Simplification (Rule of Inference): A rule of inference that allows one to infer [latex]p[/latex] from [latex]p \land q[/latex].

Strong Induction: A form of induction in which the inductive step assumes the truth of all previous cases up to [latex]n[/latex], not just the case [latex]n[/latex].

Sufficient Condition: A condition [latex]p[/latex] that guarantees another condition [latex]q[/latex], expressed as [latex]p \rightarrow q[/latex].

Tautology: A compound statement that is always true, no matter what the truth values of its individual components.

Theorem: A mathematical statement that has been proven to be true.

Truth Table: A table that lists all possible truth values of a logical expression based on the truth values of its components.

Universally Quantified Statement: A statement of the form [latex]\forall x P(x)[/latex], asserting that a predicate is true for all elements in the domain.

Universal Generalization: A rule of inference that allows a statement proven for an arbitrary element to be generalized to all elements.

Universal Instantiation: A rule of inference that allows a universally quantified statement to be applied to a specific element.

Valid Argument: An argument in which the conclusion must be true whenever all the premises are true.

Vacuously True: A conditional statement that is true because its hypothesis is false, regardless of the truth of the conclusion.

Well-Ordering Principle: The principle stating that every non-empty set of non-negative integers has a smallest element.