A counterexample for a universally quantified statement is an element in the domain for which the predicate is false.

existential quantifier

• The symbol ∃ is an existential quantifier and the statement ∃x P(x) is called a existentially quantified statement. 

Now that you have completed this lesson you should be able to evaluate the truth values for universally quantified or existentially quantified statements. Take a moment to think about what you’ve learned in this lesson:

• A predicate is a logical statement whose truth value is a function of one or more variables. The standard notation for the function of one variable is P(x), whose truth value will change based on the value of x.
• The set of all possible x values for P(x) is called the domain of the predicate.
• The universal quantifier, “for all x, is denoted ∀x, P(x).This means that for all values of x in the domain of P(x), the predicate is true.
• The existential quantifier, “there exists an x” such that P(x) is denoted ∃x, P(x). This means there is at least one x in the domain of the predicate that yields a truth value for P(x).
• Use counterexamples to prove a universally quantified or existentially quantified statement is false.
  • To show that ∀x, P(x) is not a true statement, we need only show for one x, P(x) is false.
  • To show that ∃x, P(x) is not a true statement, we need to show for all values of x, P(x) is false.

1.15 – Quantified Statements

• Consider the statements: “The variable x is a prime number.” “All x are prime.” “There exists an x that is prime.” We know these are all examples of predicates.
• The universal and existential quantifiers are generically called quantifiers. 
• A logical statement that includes a universal or existential quantifier is called a quantified statement.

• A variable x in the predicate P(x) is called a free variable because the variable is free to take on any value in the domain.
• The variable x in the statement ∀x P(x) is a bound variable because the variable is bound to a quantifier

Now that you have completed this lesson you should be able to evaluate the truth value of a quantified statement with logical operations and free or bound variables. Take a moment to think about what you’ve learned in this lesson:

• The rule of order to evaluate a compound quantified statement is to apply the quantifiers (∀,∃) before the logical operations (∧, ∨, → and ↔).
• A variable x in the predicate P(x) is called a free variable because it is not quantified. That is, the variable is free to take on any value in the domain.
• The variable x in the statement ∀xP(x) is a bound variable because it is quantified. That is, the variable is bound to a quantifier.
• If the statement has no free variables, then the statement is a proposition because its truth value can be determined.
• When reading quantified formulas in English, read them from left to right. To transcribe a quantified predicate stated in English, first restate the proposition using the predicates, connectives, and quantifiers. Then, replace the English phrases with the corresponding logic symbols.

1.16 Quantified statements and logical equivalence

Now that you have completed this lesson you should be able to analyze a quantified statement for logical equivalence using De Morgan’s law. Take a moment to think about what you’ve learned in this lesson:

• Predicate statements with the same domain are equivalent if they have the same truth values for each x in the domain.
• De Morgan’s laws for quantified statements are the same laws for propositions. Apply the law to create logically equivalent quantified predicates by negating the statement. The table summarizes De Morgan’s laws for predicates. Note the negation sign applies directly to a predicate.
  ¬∀xP(x) ≡ ∃x¬P(x)
• ¬∃xP(x) ≡ ∀x¬P(x)

1.17 Nested Quantifiers

•  A logical expression with more than one quantifier that bind different variables in the same predicate is said to have nested quantifiers.
• n reasoning whether a quantified statement is true or false, it is useful to think of the statement as a two player game in which two players compete to set the statement’s truth value. One of the players is the “existential player” and the other player is the “universal player”. The variables are set from left to right in the expression. 

Now that you have completed this lesson you should be able to deduce the truth value of a statement with nested quantifiers. Take a moment to think about what you’ve learned in this lesson:

• A logical expression with more than one quantifier that binds different variables in the same predicate is said to have nested quantifiers. For example, ∀x∀yM(x,y).
• Read nested quantifiers from left to right.
• The following table summarizes the logical symbolism and English translation:

1.18 De Morgan’s law with nested quantifiers

Now that you have completed this lesson you should be able to analyze nested quantifiers using De Morgan’s law and the laws of propositional logic to find equivalent logical statements. Take a moment to think about what you have learned in this lesson:

• Each time the negation sign moves past a quantifier, the quantifier changes type from universal to existential or from existential to universal.
• The following table summarizes and translates De Morgan’s laws for nested quantifiers:

1.19 Logic of Proof

This page marks the beginning of Module 4. This module contains three lessons and examines the following topics:

• Logical reasoning
• Rules of inference with propositions
• Rules of inference with quantifiers

In the previous modules you learned about deducing the truth values of propositional and predicate statements. In this module you will extend your knowledge of logic into the realm of arguments. An argument consists of a sequence of statements, called hypotheses or premises, which are offered as reasons to believe the conclusion is true. For example, Premise 1: If Lincoln was president, then Lincoln was commander-in- chief. Premise 2: Lincoln was president. Conclusion: Lincoln was commander-in- chief.

MODULE OBJECTIVE: By the end of this module, you should be able to use logic and the rules of inference to test the validity of arguments.

1.20 Lesson: Logical reasoning

• An argument is a sequence of propositions or hypotheses, followed by a final proposition, called the conclusion. An argument is valid if the conclusion is true whenever the hypotheses are all true, otherwise the argument is invalid. 
• The form of an argument expressed in English is obtained by replacing each individual proposition with a variable. 

Now that you have completed this lesson you should be able to evaluate the validity of a logical argument using logical reasoning. Take a moment to think about what you’ve learned in this lesson:

• An argument consists of a collection of propositions that include a set of premises called the hypotheses and a concluding one called the conclusion. Symbolically, we use p₁, p₂, … p_n to represent the hypotheses and c for the conclusion.
• Symbolically we can express the argument as (p₁ ∧ p₂∧ … ∧ p_n) → c . The translation of English statements into symbols is called the form of an argument.
• A proposition can be true or false whereas an argument is valid or invalid.
• The argument is valid if all the premises are true AND the conclusion is true. It is invalid otherwise.
• To determine the validity of an argument, use a truth table on the form of an argument. The columns should consist of all the premises and the conclusion. Each row consists of all the possible truth values for each variable in the hypotheses. If there exists a row where all the premises are true and the conclusion is true, the argument is valid.

1.21 Lesson: Rules of inference with propositions

Now that you have completed this lesson you should be able to analyze the validity of a logic argument using the rules of inference. Take a moment to think about what you’ve learned in this lesson:

• The validity of an argument is deduced by identifying common rules of inference that are embedded into the argument.
• A logical proof shows that an argument is valid by providing justification for each step in the argument using the common rules of inference and the laws of propositional logic.
• The following are common rules of inference that are known to be valid expressed symbolically

1.22 Lesson: Rules of inference with quantifiers

• A value that can be plugged in for variable x is called an element of the domain of x.
• An arbitrary element of a domain has no special properties other than those shared by all the elements of the domain.
• A particular element of the domain may have properties that are not shared by all the elements of the domain.
• The rules existential instantiation and universal instantiation replace a quantified variable with an element of the domain. The rules existential generalization and universal generalization replace an element of the domain with a quantified variable.

Now that you have completed this lesson you should be able to analyze the validity of a logical argument with quantified statements using the rules of inference. Take a moment to think about what you’ve learned in this lesson:

• The values of x that make up the domain of the predicate P(x) are called elements.
• An element that refers to any unspecified x in the domain is called an arbitrary element. For example, “Let x be any element in the domain of P(x).”
• An element that refers to an x in the domain with certain properties is called a particular element. For example, “Let x be in the domain of P(x) such that x is also even.”
• For each particular element in an argument, assign a new variable. It is a common error to use the same name for different particular elements.
• Review the following rules of Inference that are known to be valid for quantified statements

1.23 Module 5: Foundations of Proofs

• Introduction to proofs
• Proofs by exhaustion
• Proofs by counterexample
• Direct proofs
• Proofs by contrapositive
• Proofs by contradiction (indirect proof)
• Proofs by cases

MODULE OBJECTIVE: By the end of this module, you should be able to evaluate a given proof for validity and the type of proof (e.g., direct, contrapositive, contradiction, proof by cases).

1.24 Lesson: Introduction to proofs

• A theorem is a statement that can be proven to be true. 
•  proof consists of a series of steps, each of which follows logically from assumptions, or from previously proven statements, whose final step should result in the statement of the theorem being proven.
• The proof of a theorem may make use of axioms, which are statements assumed to be true.

Now that you have completed this lesson you should be able to evaluate the structure and elements of a proof using universal statements. Take a moment to think about what you’ve learned in this lesson:

• In mathematics, a theorem is a claim that can be proved true using logical arguments.
• The process we use to show the theorem is true is called a proof.
• Claims that we accept to be true without proof are called axioms.
• There is not a set algorithm to prove each theorem. Different proofs require different techniques and they are not “one size fits all.” It is an art form that can be learned. Trial and error is often how we begin.

1.25 Lesson: Proofs by exhaustion

• If the domain of a universal statement is small, it may be easiest to prove the statement by checking each element individually. A proof of this kind is called a proof by exhaustion.

Now that you have completed this lesson you should be able to solve for a proof using proof by exhaustion. Take a moment to think about what you’ve learned in this lesson:

• For proofs of universal statements, a proof by exhaustion is one technique that shows the claim is true for all x in the domain.
• To prove a claim is true by exhaustion, plug each element in the domain with a value and determine its truth value.
• For infinite domains and large finite domains, this process is not possible and one must show the statement is true for an arbitrary element in the domain.

1.26 Lesson: Proofs by counterexample

• A counterexample is an assignment of values to variables that shows that a universal statement is false. 

Now that you have completed this lesson you should be able to determine counterexamples for a logical statement to show no proof is possible. Take a moment to think about what you’ve learned in this lesson:

• To disprove a universal statement, find one counterexample to the claim. For example, to disprove the statement, “All prime numbers are odd” find one example where this statement is false—the number 2—which is both even and prime.

1.27 Lesson: Direct proof

• In a direct proof of a conditional statement, the hypothesis p is assumed to be true and the conclusion c is proven as a direct result of the assumption.
• A rational number, is defined to be a number that can be expressed as the ratio of two integers in which the denominator is non-zero.

Now that you have completed this lesson you should be able to analyze a direct proof for validity and flaws. Take a moment to think about what you’ve learned in this lesson:

• Use a direct proof to prove a claim implies a conclusion for a conditional statement ().
• In a direct proof, start with the hypothesis of a statement and make one deduction after another until you reach the conclusion.
• Symbolically, to prove with a direct proof, start with the original claim p then justify a sequential order of steps. The following is the structure of a direct proof.
  p and show
  p → p₁ then
  p₁ → p₂ then
  p_n → c for a sequence of steps, p₁, p₂, … ,p_n.
• Justify each step of a direct proof using definitions, logical operators, and previously proven theorems.

1.28 Lesson: Proofs by contrapositive\

• A proof by contrapositive proves a conditional theorem of the form p → c by showing that the contrapositive ¬c → ¬p is true.
•  An even integer can be expressed as 2k for some integer k. An odd integer can be expressed as 2k + 1 for some integer k. 

Now that you have completed this lesson you should be able to analyze a proof by contrapositive for validity and flaws. Take a moment to think about what you’ve learned in this lesson:

• The contrapositive of the logical statement p→c is ¬c→¬p, and they are logically equivalent. That is, if one is true then so is the other.
• To prove a statement by contraposition, start with the contrapositive of the statement. In this example ¬c→¬p is the contrapositive of p→c. Then prove the contrapositive by a direct proof and conclude that the original statement is true. (For a refresher on direct proofs, review the previous lesson.)
• The proof by contrapositive is often used for number theory proofs. It is good to know that the definition of an even number can be expressed as 2n where n is an integer. An odd number can be expressed as 2n + 1 for some integer n.
• The proof by contrapositive is often used with statements with rational numbers. A rational number can be expressed as the quotient of integers. An irrational number is one that cannot.

1.29 Lesson: Proofs by contradiction (indirect proof)

• A proof by contradiction starts by assuming that the theorem is false and then shows that some logical inconsistency arises as a result of this assumption.
• A proof by contradiction is sometimes called an indirect proof.

Now that you have completed this lesson, you should be able to analyze a proof by contradiction for validity and flaws. Take a moment to think about what you’ve learned in this lesson:

• An indirect way to prove a theorem is to assume it is false and then show how, under this assumption, a mathematical contradiction will arise. This is called a proof by contradiction.
• To prove by contradiction, start with the conditional statement p→c and assume the premise (p) is true but that conclusion (c) is false. Then proceed to show there is a contradiction using the same steps as the direct proof.
• Use proofs by contradiction when it is more difficult to prove the theorem directly. For example, to show that the sum of an irrational number and a rational number is irrational, it is easier to prove it indirectly by assuming the sum is rational and showing that a contradiction arises, than to prove it directly.

1.30 Lesson: Proofs by cases

• A proof by cases of a universal statement such as ∀x P(x) breaks the domain for the variable x into different classes and gives a different proof for each class. Every value in the domain must be included in at least one class.
• The parity of a number is whether that number is odd or even.
• To prove a predicate P(x) is true on its domain, sometimes it is easier to show the predicate is true by breaking up the domain into different classes and offering proofs for each class separately. This is called a proof by cases.
• We often use proofs by cases when seeking to prove claims that involve parity of integers. For example, to show a claim is true for all integers, sometimes it is easier to show first for the set of even integers and then for the set of odd integers.