Quantifier Duality: A Journey from ∀ (for all) to ∃ (exists)
Explore the simple relationship between forAll and exists using De Morgan's Laws. Look at practical examples to see how understanding this relationship can help us write better and faster code. This is a step towards making coding more straightforward and more efficient.
In logic and mathematics, quantifiers are the gatekeepers of generality and specificity. They enable us to make assertions about entire collections of objects. Among these quantifiers, ∀ (for all) and ∃ (exists) are the most important. Independent yet bound by an intriguing duality. We will refer to them using their mathematical symbols for brevity's sake.
Relevant Logical Concepts
Before diving into the quantifiers' connection, let's review some relevant discrete logic concepts.
Predicate
A predicate is a statement about a subject. The statement can be over any property or condition of the subject. And it has to be true or false without any ambiguity. In programming, a predicate is a function that evaluates to true or false.
Operations
Predicates can be connected with logical operations; the most primitive operations are NOT, AND, and OR.
The NOT operation, denoted by ¬, inverts the truth value of its operand.
| A | ¬A |
|---|---|
| T | F |
| F | T |
The AND operation, denoted by ∧, outputs true only when both operands are true.
| A | B | A ∧ B |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
The OR operation, denoted by ∨, outputs true if at least one of the operands is true.
| A | B | A ∨ B |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
De Morgan's Laws for Operations
Augustus De Morgan lived in the 19th century in logic and mathematical reasoning. He laid the groundwork for modern symbolic logic and set the stage for many discoveries. His influence extends to our time through the laws named after him.
De Morgan's laws result from the distributive nature of negation over conjunction (AND) and disjunction (OR). And show the relationship between the logical operations NOT, AND, and OR. They are as follows:
- First Law: ¬(A ∧ B) ≡ ¬A ∨ ¬B
- Second Law: ¬(A ∨ B) ≡ ¬A ∧ ¬B
These laws are vital for simplifying and transforming logical expressions.
Quantifiers Definition
For all, written in mathematics as ∀x P(x), it asserts that the predicate P holds for all elements in a particular domain. It is a shorthand notation for applying the predicate to all domain elements and joining the results using the AND operation.
Exists, written as ∃x P(x), declares that at least one element exists in the domain for which P holds. It is equivalent to applying the predicate to all domain elements and joining the results using the OR operation.
De Morgan's Laws for Quantifiers
De Morgan's Laws extend to quantifiers. They express a beautiful duality between universal and existential quantification under negation. Their mathematical definition is:
- First Law: ¬(∀x P(x)) ≡ ∃x ¬P(x)
- Second Law: ¬(∃x P(x)) ≡ ∀x ¬P(x)
In other words, saying not all elements have a property is the same as saying that at least one element does not. The second says that no element existing with a given property equals saying all the elements do not have that property.
Informal Proof for: ¬(∀x P(x)) ≡ ∃x ¬P(x)
The expression ¬(∀x P(x)) translates to "It is not the case that for every x, P(x) holds."
By definition of negation and universal quantification, this statement is true if and only if at least one element in the domain for which P(x) does not hold.
This is precisely the statement "There exists an x such that P(x) does not hold.", which translates to ∃x ¬P(x).
Hence, ¬(∀x P(x)) ≡ ∃x ¬P(x).
Informal Proof for: ¬(∃x P(x)) ≡ ∀x ¬P(x)
Similarly, the expression ¬(∃x P(x)) translates to "It is not the case that there exists an x such that P(x) holds."
By definition of negation and existential quantification, this statement is true if and only if P(x) does not hold for every element in the domain.
This is the statement "For every x, P(x) does not hold.", which translates to ∀x ¬P(x).
Hence, ¬(∃x P(x)) ≡ ∀x ¬P(x).
Utility of Duality in Programming
We can use this duality while programming. We can change our code to be easier to read or faster to execute while ensuring it retains the same meaning. We can use our understanding of De Morgan's Laws to transform complex logical expressions into more readable or efficient forms without altering their meaning.
Let's consider a scenario in a high-level language, We have a condition and want to check if it applies to all collection elements. By using the laws, we can rewrite the code to the dual expression:
object QuantifierDuality extends App:
def allNegative(numbers: List[Int]): Boolean =
numbers.forall(_ < 0)
def existsNonNegative(numbers: List[Int]): Boolean =
!numbers.forall(_ < 0)
// Example list of numbers with both negative and positive values
val numbers = List(-3, -2, -1, 0, 4, 5)
// Universal quantification (forall)
val allNeg = allNegative(numbers)
println(s"All numbers are negative: $allNeg")
// Expressed using existential quantification (exists)
val existsNonNeg = existsNonNegative(numbers)
println(s"Exists a non-negative number (duality): $existsNonNeg")
def all_negative(numbers):
return all(n < 0 for n in numbers)
def exists_non_negative(numbers):
return not all(n < 0 for n in numbers)
# Example list of numbers with both negative and positive values
numbers = [-3, -2, -1, 0, 4, 5]
# Universal quantification (forall)
all_neg = all_negative(numbers)
print(f"All numbers are negative: {all_neg}")
# Expressed using existential quantification (exists)
exists_non_neg = exists_non_negative(numbers)
print(f"Exists a non-negative number (duality): {exists_non_neg}")
In the original expression, we use forall to check if all items are valid and negate the result. In the simplified expression, we use exists to check if there's any item that is not valid. Our rewrite is better because it stops evaluating when finding the first invalid item and avoids unnecessary work.
Conclusion
Harnessing the duality expressed in De Morgan's Laws allows us to write clearer or faster code while ensuring its correctness. This article explored how blending logic in our programming elevates our code. We learned to use these mathematical concepts to craft efficient and reliable software.
Addendum: A Special Note for Our Readers
I decided to delay the introduction of subscriptions, you can read the full story here.
In the meantime, I decided to accept donations.
If you can afford it, please consider donating:
Every donation helps me offset the running costs of the site and an unexpected tax bill. Any amount is greatly appreciated.
Also, if you are looking to buy some Swag, please visit I invite you to visit the TuringTacoTales Store on Redbubble.
Take a look, maybe you can find something you like:
