Truth Values and Negations of Quantified Statements

From Open Sentences to Quantified Statements

A statement with a variable, like $P(x):x>5$, is often called a predicate or an open sentence. It's "open" because its truth value is not fixed until we specify the value of x. Quantifiers are the tools that "close" the sentence, turning it into a full-fledged proposition.

There are two fundamental quantifiers:

1. The Universal Quantifier ($\forall$), which means "for all" or "for every." The statement $\forall x,P(x)$ asserts that $P(x)$ is true for every possible value of x in our domain of consideration.
2. The Existential Quantifier ($\exists$), which means "there exists" or "for some." The statement $\exists x,P(x)$ asserts that there is at least one value of x in our domain for which $P(x)$ is true.

This first video provides a clear introduction to open sentences and shows how these two quantifiers transform them into statements with definite truth values.

The Importance of the Domain

When we say "for all x" or "there exists an x," we implicitly assume x comes from a specific collection of possible values. This collection is called the domain or universe of discourse. The truth of a quantified statement can change dramatically depending on its domain.

For instance, consider the statement "There exists an x such that $x^2=2$."

• If the domain is the set of real numbers ($\mathbb{R}$), the statement is true (since $x=\sqrt{2}$ is a solution).
• If the domain is the set of integers ($\mathbb{Z}$), the statement is false (since $\sqrt{2}$ is not an integer).

The following reading explains the role of the domain and how to determine the truth value of quantified statements.

Determining Truth Values: Examples and Counterexamples

Now that we have the concepts of quantifiers and domains, how do we systematically determine if a statement is true or false? The strategy depends on the quantifier.

• To show a universal statement $\forall x,P(x)$ is true, you must show $P(x)$ is true for every single element in the domain. This often requires a formal proof, which we will cover in the next module.
• To show a universal statement $\forall x,P(x)$ is false, you only need to find one single element in the domain for which $P(x)$ is false. This element is called a counterexample.
• To show an existential statement $\exists x,P(x)$ is true, you only need to find one single element in the domain for which $P(x)$ is true. This element is called an example or a witness.
• To show an existential statement $\exists x,P(x)$ is false, you must show $P(x)$ is false for every single element in the domain.

The following screencast walks through this logic with several good examples.

Let's apply this to a cybersecurity context. Imagine D is the set of user accounts on a network server.

• The statement ∀x ∈ D, HasMFA(x) means "All users have multi-factor authentication enabled." To prove this false, a security auditor just needs to find one counterexample: a single account without MFA.
• The statement ∃x ∈ D, IsAdmin(x) ∧ LastLogin(x) > 365 days means "There is an administrator account that hasn't been used in over a year." To prove this is true, an auditor would search for just one such dormant, high-privilege account.

Negating Quantified Statements

Being able to negate a quantified statement is a critical skill. It's essential for a proof technique called "proof by contradiction," and it helps clarify what it means for a security policy or a program specification to fail.

The rules for negation are elegant and can be seen as an extension of De Morgan's laws:

1. The negation of a universal statement is an existential statement.
   ¬($\forall x,P(x)$) is equivalent to $\exists x,\neg P(x)$
   In words: "It is not the case that all x satisfy P" is the same as "There exists an x that does not satisfy P."

2. The negation of an existential statement is a universal statement.
   ¬($\exists x,P(x)$) is equivalent to $\forall x,\neg P(x)$
   In words: "There does not exist an x that satisfies P" is the same as "For all x, they do not satisfy P."

The next video gives a fantastic intuition for why these rules work and provides a simple trick for applying them.

To solidify this, here is a textual summary of the rules.

A Note on Multiple Quantifiers

Statements can involve multiple variables and quantifiers. When quantifiers are of the same type (e.g., all ∀ or all ∃), their order doesn't matter.
$\forall x\forall y,P(x,y)\equiv \forall y\forall x,P(x,y)$

However, when you mix quantifiers, order is critical. The statement ∀x ∃y, P(x,y) is very different from ∃y ∀x, P(x,y).

Let the domain be integers and P(x,y) be the predicate x < y.

• ∀x ∃y, x < y: "For every integer x, there exists an integer y that is greater than x." This is true. (For any x, we can choose y = x + 1).
• ∃y ∀x, x < y: "There exists an integer y that is greater than every integer x." This is false. (There is no "largest integer").

When you read these, it's helpful to "peel the onion" from the outside in, as the next reading suggests.

Conclusion

In this lesson, we have extended our logical vocabulary to include quantified statements. This allows us to reason about properties that apply to entire domains of objects, which is fundamental to both mathematics and computer science.

Here are the main takeaways:

• Quantifiers ($\forall$ for "for all," $\exists$ for "there exists") turn predicates (open sentences) into propositions with definite truth values.
• The domain of discourse is the set of values a variable can take, and it is essential for determining a statement's truth.
• A universal statement ($\forall$) is proven false with a single counterexample. An existential statement ($\exists$) is proven true with a single example.
• Negating quantifiers involves flipping the quantifier and negating the predicate inside: ¬∀ becomes ∃¬, and ¬∃ becomes ∀¬.
• For mixed quantifiers, order matters.

We have spent the first two lessons building the language of logic. In the next lesson, we will turn our attention to the objects these logical statements describe: sets. You have already seen domains like the set of integers $\mathbb{Z}$ or real numbers $\mathbb{R}$. We will now study sets formally, learning how to combine and manipulate them with operations like union, intersection, and difference.