# 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.