Welcome to our next lesson! In our previous session, you learned how to translate English sentences into the structured language of predicate logic using universal (∀) and existential (∃) quantifiers. You now have the tools to express ideas like "Every cat is fluffy" or "There is a fox faster than all snails" with mathematical precision.
Today, we move from writing these statements to evaluating them. A logical statement isn't just a string of symbols; it's an assertion that is either true or false. Our goal is to determine which it is. This process is similar to running unit tests on a function: you provide a specific context (a set of inputs) and check if the function's output (the statement's truth) is correct. The "context" in logic is called the domain of discourse, and it is the key to everything we will do today.
The Importance of the Domain
A quantified statement is meaningless without a defined domain. Consider ∀x (x > 5).
- If the domain is the set of all integers, this is false. A counterexample is
x=4, since 4 is an integer but 4 is not greater than 5. - If the domain is the set
{6, 7, 8}, this is true. Every element in the set is greater than 5.
This is the central idea of today's lesson: the truth of a quantified statement is not absolute, but relative to its domain.
To evaluate these statements, we need two distinct strategies: one for universal statements and one for existential statements.
-
To prove a universal statement
∀x P(x)is true, you must showP(x)holds for every single element in the domain. -
To prove a universal statement
∀x P(x)is false, you only need to find one element in the domain that makesP(x)false. This is called a counterexample. -
To prove an existential statement
∃x P(x)is true, you only need to find one element in the domain that makesP(x)true. This is called a witness. -
To prove an existential statement
∃x P(x)is false, you must showP(x)is false for every single element in the domain.
The following resource formally defines these concepts. Pay close attention to the role of counterexamples and witnesses in proving or disproving these statements.
2.7: Quantifiers - Mathematics LibreTexts
This text provides the formal rules for evaluating quantified statements.
Please read the sections on the Universal Quantifier and the Existential Quantifier. Focus on the role of the counterexample for universal statements and how to prove an existential statement by finding a single example.
Evaluating Statements: From Simple to Nested
Let's see this in action. Working with a small, concrete domain makes the process very clear. The following video demonstrates how to check statements against a specific set of numbers.
Quantifiers - Logic - Discrete Mathematics
This segment from a lecture by Ekeeda provides a straightforward example of evaluating quantified statements over a small, finite set.
Watch the part of the video from this example, where the presenter determines the truth value of two statements over the domain A = {1, 2, 3, 4}. Notice how for the ∀x statement, every element must be checked.
This process becomes more interesting, and more like programming, when we have nested quantifiers. The order of the quantifiers is critical and can completely change the meaning of a statement. Think of them like nested loops:
∀x ∃y ...is like saying:for every x in domain: ... find a y such that ...∃y ∀x ...is like saying:find one specific y in domain: ... such that for every x ...
In the first case, y can depend on x. In the second, y must be a single value that works for all x. The following video works through several excellent examples that illustrate this.
Proof and Problem Solving - Quantifiers Example 03
This video by Adam Panagos demonstrates a problem-solving approach to evaluating statements with nested quantifiers.
Please watch these three segments: This example shows how to prove a ∀x ∃y... statement is false by finding a single x for which no y works (a counterexample). This segment shows how to prove a ∃x ∃y... statement is true by finding just one pair (x, y) that works (a witness). This part demonstrates a true ∀x ∃y... statement, where for every x, you can find a corresponding y.
For more practice, the following text resource provides a series of solved problems. Working through them will help solidify your understanding.
This article contains a list of solved problems that cover a range of scenarios.
Review the "Solved Questions Predicates and Quantifiers" section. Focus on Question 5, which shows a simple true/false evaluation, and Question 9, which explains why a ∀x ∃y... statement is true. These examples reinforce the thought process for evaluating different kinds of quantified statements.
The Link Between Evaluation and Negation
You might have noticed a connection between proving a statement true or false and the concept of negation. These are two sides of the same coin. The rules for negation directly mirror the strategies for evaluation.
Recall De Morgan's laws for quantifiers:
¬(∀x P(x)) ≡ ∃x ¬P(x)¬(∃x P(x)) ≡ ∀x ¬P(x)
Let's translate these into our evaluation strategy:
- To prove
∀x P(x)is false, you prove its negation,∃x ¬P(x), is true. You do this by finding a witness for∃x ¬P(x), which is the same thing as a counterexample for∀x P(x). - To prove
∃x P(x)is false, you prove its negation,∀x ¬P(x), is true. This means you must show that¬P(x)holds for allxin the domain.
This gives us a powerful and systematic way to think about disproving statements.
Conclusion
In this lesson, we established the methods for verifying the truth of quantified statements. You have learned that this process is not an abstract exercise but a concrete evaluation that depends entirely on a defined domain of discourse. By treating quantified statements as claims to be tested, you can systematically determine their validity.
Key Takeaways:
- The truth of a quantified statement depends on its domain.
- A universal statement (∀) is proven false with a single counterexample. To prove it true, it must hold for all elements.
- An existential statement (∃) is proven true with a single witness. To prove it false, it must fail for all elements.
- The order of nested quantifiers is critical.
∀x ∃yallowsyto depend onx, while∃y ∀xrequires a singleyto work for allx. - Proving a statement false is equivalent to proving its negation true.
We've now completed our foundational tour of logic. You can translate statements into logical form and evaluate their truth. The concept of a "domain" is actually a formal mathematical object called a set. In our next module, we will dive into the world of Set Theory, exploring the properties of these collections and the operations we can perform on them. You'll see that the logical connectives AND, OR, and NOT have direct parallels in the set operations of intersection, union, and complement.