Predicates and Quantifiers
Contents
Predicates and Quantifiers¶
Boolean Functions¶
As programmers, we frequently write functions and expressions that result in a boolean value. All the following Python commands return Boolean values.
a = 9 < 7
b = 12%9==1
c = 9 in [1,2,3,4,5]
If all these commands return Boolean values, then we can combine then using the logical operators.
q = (j > 0) and (A[j] < A[j-1])
This is similar to using Boolean logic to say
X = the result of
(j > 0)Y = the result of
(A[j] < A[j-1])
\( \begin{align} X \wedge Y \end{align} \)
The problem with using pure Boolean logic is we hide the fact that these statements are controlled by a variable \(j\). Understanding that a variable effect the result is very important, especially when talking about problems that will be implemented as code.
To solve this problem, we introduce the predicate. A predicate is a function that takes \(n \ge 0\) input arguments and returns a Boolean.
Note
If all your predicates takes \(n=0\) inputs, then it is a Boolean logic expression. Nothing is dependent on input arguments.
Since predicates always return Boolean values, we can use them with logic operators and traditional Boolean variables.
There are many predicates build into most programming languages. To be language agnostic, they are given in mathematical notation below. When used in code, we will use language specific symbols.
Predicate |
Meaning |
|---|---|
\(a > b\) |
True when \(a\) is greater than \(b\) |
\(a \ge b\) |
True when \(a\) is greater than or equal to \(b\) |
\(a < b\) |
True when \(a\) is less than \(b\) |
\(a \le b\) |
True when \(a\) is less than or equal to \(b\) |
\(a \equiv b\) |
True when \(a\) is equal to \(b\) |
\(a \neq b\) |
True when \(a\) is not equal to \(b\) |
We can define out own predicates in terms of other predicates. We can define \(G(a,b)\) as greater than. We use the \(:=\) symbol to define a new predicate. This avoids confusion between bi-conditional (\(\iff\)), variable assignment/algebraic equals (a=7), mathematical equivalence (\(\equiv\)), and predicate definition (\(:=\)).
\( \begin{align} G(a,b) := a > b \end{align} \)
We can use logical operators and the \(G(a,b)\) predicate to implement all the other operators in the table.
\( \begin{align} L(a,b) :=& G(b,a) & \text{Less Than} \\ E(a,b) :=& \neg L(a,b) \wedge \neg G(a,b) & \text{Equals} \\ NE(a,b) :=& \neg E(a,b) & \text{Not Equals} \\ LE(a,b) :=& L(a,b) \vee E(a,b) & \text{Less Than or Equal} \\ GE(a,b) :=& G(a,b) \vee E(a,b) & \text{Greater Than or Equal} \\ \end{align} \)
We can use these predicates to implement code.
def G(a,b):
return a > b
def L(a,b):
return G(b,a)
def E(a,b):
return not L(a,b) and not G(a,b)
def NE(a,b):
return not E(a,b)
def LE(a,b):
return L(a,b) or E(a,b)
def GE(a,b):
return G(a,b) or E(a,b)
Reasoning about predicates will allow us to make predications about how code and functions will work.
We can come up with an expression first and verify it makes senses. What if we want to test if the product of two numbers will be positive before we multiply them. If two numbers are both positive, then their product will be positive. Additionally, if two numbers are negative, the negatives will cancel and the product will be positive.
\( \begin{align} \text{positiveProduct}(x,y) := \left( x \ge 0 \wedge y \ge 0 \right) \vee (x < 0 \wedge y < 0) \end{align} \)
We could implement this concept.
def positiveProduct(x,y):
return (x >= 0 and y >= 0) or (x < 0 and y < 0)
What if we wanted to determine the product was negative? We could just define a function using negation.
\( \begin{align} negativeProduct(x,y) := \neg \text{positiveProduct}(x,y) \end{align} \)
We could also try to simply the definition to create a new one.
\( \begin{align} \neg \text{positiveProduct}(x,y) =& \neg \left( ( x \ge 0 \wedge y \ge 0 ) \vee (x < 0 \wedge y < 0) \right) & \text{Definition Applied}\\ =& \neg( x \ge 0 \wedge y \ge 0 ) \wedge \neg (x < 0 \wedge y < 0) & \text{Demorgan's Law} \\ =& ( \neg(x \ge 0) \vee \neg(y \ge 0) ) \wedge (\neg(x < 0) \vee \neg( y < 0) ) & \text{Demorgan's Law} \\ =& ( x < 0 \vee y < 0) \wedge (x \ge 0 \vee y \ge 0) & \text{Based on definitions of inequalities} \\ \end{align} \)
Now, we can implement the simplified version.
def negativeProduct(x,y):
return (x < 0 or y < 0) and ( x >= 0 or y >= 0)
Note
Zero is a special exception not caught by this statement since \(-1*0=0\) instead of \(-0\). We might want to break out this case, but it was ignored here just to keep the example short and readable.
This is a simple example, but it gets the basic point across. We can use reasoning about predicates to improve implementation of code. By reasoning about the predicates we plan to use first, we can find flaws, introduce improvements, or justify our designs.
Sets and Lists¶
Once we have predicates, there are now things in our reasoning that aren’t boolean. All our example predicates were implied to take numbers as inputs, but it was not specified.
The specific rule \(\neg(x < y) = x \ge y\), only applies to some kinds of \(x\) and \(y\) data types. When working with predicates, we often need to specify what data type we are talking about.
A set is a collection of distinct elements. A set never contains any duplicate values.
A list is a collection of values in a specific order. A list may contain duplicates, they will be at different locations in the ordering.
There are a number of classical mathematical sets.
Symbol |
Name |
Examples |
|---|---|---|
\(\mathbb{W}\) |
Whole Numbers |
\(0,1,2,3,4,5,\cdots\) |
\(\mathbb{N}\) |
Natural Numbers |
\(1,2,3,4,5,\cdots\) |
\(\mathbb{Z}\) |
Integers |
\(\cdots,-3,-2,-1,0,1,2,3,\cdots\) |
\(\mathbb{Q}\) |
Rational Numbers |
\(\cdots,0,\frac{1}{4},\frac{1}{2},\frac{9}{11},\cdots\) |
\(\mathbb{I}\) |
Irrationals Numbers |
\(\pi, e, \sqrt{2},\cdots\) |
\(\mathbb{R}\) |
Real Numbers |
\(\cdots,0,1,2,\frac{1}{2},\sqrt{3},\pi,\cdots\) |
\(\mathbb{C}\) |
Complex Numbers |
\(\cdots,2i-7,0,1,2,\frac{1}{2},\sqrt{3},\pi,\cdots\) |
Note
The whole numbers \(\mathbb{W}\) can also be written as \(\mathbb{Z}^{+}\). The positive values of the Integers. We can also specify the natural numbers \(\mathbb{N}\) as positive integers greater than 0, \(\mathbb{Z}^{+>0}\)
We can also define our own sets and lists. A set used curly brackets \(\{,\}\) and may never include duplicates. A list uses square brackets \([,]\).
Below are some examples.
\( \begin{align} S_{1} =& \{ 1,2,3,4\} \\ S_{2} =& \{2,4,6,8\} \\ S_{3} =& \{4,2,3,1\} \\ L_{1} =& [3,5,7,9] \\ L_{2} =& [4,4,4,4,4,4] \\ L_{3} =& [4,2,3,1] \\ \end{align} \)
Since order doesn’t matter \(S_{1}\) and \(S_{3}\) are the same set. Order does matter in \(L_{3}\). This is a list, so it is saying \(4\) must be first.
Once we have a list or a set, we can ask if a value is in the collection.
Note
A collection is any grouping of values. It could be a list, set, dictionary, or any other structure that stores values.
To ask if a value is in a set, we use the symbol \(\in\). We would ask if \(10\) is in \(S_{1}\) by writing \(10 \in S_{1}\). In this case, \(10\) is not in the set. This statement would be false.
We can evaluate multiple examples on \(S_{2} = \{2,4,6,8\}\)
\( \begin{align} 1 \in S_{2} =& \text{False} \\ 2 \in S_{2} =& \text{True} \\ 3 \in S_{2} =& \text{False} \\ 4 \in S_{2} =& \text{True} \\ \end{align} \)
Quantifiers¶
If a predicate takes values from a collection, we might want to ask questions like “Does this function return true for all values in the collection?” or “Does there exists an input that cause an incorrect output?”.
Describing variables over the collection like this is called quantifying it. We are stating that it has some quality we want to be true over the entire collection of possible inputs.
The two quantifiers are For All (\(\forall\)) and Exists (\(\exists\)).
For All¶
We can write a statement that asks if something is true for all possible inputs. We start with a set \(S=\{0,2,4,6,8,10\}\). We could ask if for all elements in the set, is the remainder of division by two equal to zero. We use the For All quantifier symbol \(\forall\).
\( \begin{align} \forall x \in S \left( x\%2==0 \right) \end{align} \)
The For All quantifier tells us that this statement needs to true for every value \(x\) can take in the set \(S\). We could write this out without quantifiers by giving every possible case and making a conjunction.
\( \begin{align} (0\%2==0) \wedge (2\%2==0) \wedge (4\%2==0) \wedge \cdots \end{align} \)
Although this is also correct, the quantifier makes thing much more compact. It is also more flexible, because we can redefine \(S\) without changing the rest of the statement.
To determine if the statement is actually true, we need to set over every value.
\( \begin{align} (0\%2)==0 &= \text{True} \\ (2\%2)==0 &= \text{True} \\ (4\%2)==0 &= \text{True} \\ (6\%2)==0 &= \text{True} \\ (8\%2)==0 &= \text{True} \\ (10\%2)==0 &= \text{True} \\ \end{align} \)
They are all true, which means
\( \begin{align} \forall x \in S \left( x\%2==0 \right) = \text{True} \end{align} \)
The For All needs to be true for every possible value. If even one is false, then the statement is false. What if we asked a different question?
\( \begin{align} \forall x \in S \left( x < 9 \right) \end{align} \)
This is true in all but one case, which means the expression is false. It is not true for all values.
\( \begin{align} 0 < 9 &= \text{True} \\ 2 < 9 &= \text{True} \\ 4 < 9 &= \text{True} \\ 6 < 9 &= \text{True} \\ 8 < 9 &= \text{True} \\ 10 < 9 &= \text{False} \\ \forall x \in S \left( x < 9 \right) &= \text{False} \end{align} \)
Remember, the For All is telling us to make a conjunction or all possible inputs. They all have to be true for the conjunction to be true.
We can implement a For All with a loop. This implementation takes a function and a set to check over. The For All statement is defined as true over the empty set. If there are no elements, then the expression is never false. There are no elements to make it false.
S=set([0,2,4,6,8,10])
def f1(a):
return a%2==0
def f2(a):
return a < 9
def forall(func,Set):
result = True #True for empty set
for x in Set:
result = result and func(x)
return result
print(forall(f1,S))#Returns True
print(forall(f2,S))#Returns False
Exists¶
What if we don’t care about every value? What if we just want to know that at least one values exists that makes a statement true. In this case, we use the Exists quantifier symbol \(\exists\).
We can ask if there Exists any number in the set \(S=\{0,2,4,6,8,10\}\) that is larger than four.
\( \begin{align} \exists x \in S \left( x > 4 \right) \end{align} \)
We still need to test against every input, but we only need one to be true. This is a disjunction. Again, we could write it without the quantifier, but it would be very messy.
\( \begin{align} (0 > 4) \vee (2 > 4) \vee (4 > 4) \vee \cdots \end{align} \)
To evaluate the expression, we need to try all combinations.
\( \begin{align} (0 > 4) =& \text{False} \\ (2 > 4) =& \text{False} \\ (4 > 4) =& \text{False} \\ (6 > 4) =& \text{True} \\ (8 > 4) =& \text{True} \\ (10 > 4) =& \text{True} \\ \exists x \in S \left( x > 4 \right) =& \text{True} \end{align} \)
The Exists statement is only false when it is false for all possible inputs. There does not exist one value that makes it true. There are no odd values in the set at all. Asking \(\exists x \in S \left( x \%2 ==1 \right)\) will give us a false result.
\( \begin{align} (0 \%2==1) =& \text{False} \\ (2 \%2==1) =& \text{False} \\ (4 \%2==1) =& \text{False} \\ (6 \%2==1) =& \text{False} \\ (8 \%2==1) =& \text{False} \\ (10 \%2==1) =& \text{False} \\ \exists x \in S \left( x \%2 ==1 \right) =& \text{False} \end{align} \)
Between the two operators, we have a significant amount of additional power. This operator can also be implemented using a loop and disjunctions. The Exists is false for the empty set. If there are no elements at all, then there does not exist one that makes it true.
S=set([0,2,4,6,8,10])
def g1(a):
return a>4
def g2(a):
return a%2==1
def exists(func,Set):
result = False #True for empty set
for x in Set:
result = result or func(x)
return result
print(exists(g1,S))#Returns True
print(exists(g2,S))#Returns False
Note
Both implementations can have short circuits. If the For All hits a false, we know the answer is false and can stop checking. If Exists hits a true, we know the statement is true and can stop checking.