## 4.101 Introduction to predicate logic

• Predicate Logic
• Propositional logic has some limitations:
• Cannot precisely express meaning of complex math statements.
• Only studies propositions, which are statements with known truth values.
• Predicate logic overcomes the limitations and can be used to build more complex reasoning.
• Example 1:
• Given statements:
• "All men are mortal."
• "Socrates is a man."
• Naturally, it follows that: "Socrates is mortal"
• Propositional logic can't express this reasoning, but predicate logic can enable us to formalise it.
• Example 2:
• "x squared is equal to 4."
• It's not a proposition, as its truth value is a function depending on x.
• We need predicate logic.

## 4.103 What are Predictates?

• Consider statement $x^2 = 4$
• It's not a proposition as its true value depends on $x$
• Therefore, it can't be expressed using propositional logic.
• Can be expressed using predicate logic.
• Predicate
• Predicates behave as functions whose values $T$ or $F$ depend on their variables.
• Predicates become propositions when their variables are given actual values.
• The statement above has 2 parts:
• The variable x: the subject of the statement.
• The predicate "squared is equal to 4": the property the subject of the statement can have.
• The statement can be formalised as $P(x)$ where P is the predicate "squared is equal to 4" and x is the variable.
• Evaluate for certain values of x:
• P(2) is True
• P(3) is False
• A predictate can depend on multiple values:
• Let $P(x, y)$ denote "$x^2 > y$":
• $P(-2, 3)$ = $(4 > 3) \text{ is } \mathbf{ True}$
• $P(2, 4)$ = $4(2^2 >4) \text{ is } \mathbf{False}$
• Let Q(x, y, z) denote x + y < z
• Q(2, 4, 5) = (6 < 5) is F
• Q(2, 4, z) is not a proposition
• Logical operations from propositional logic carry over to predicate logic
• If $P(x)$ denotes $x^2 < 16$, then:
• $P(1) \lor P(-5) \equiv (1 < 16) \lor (25 < 16) \equiv T \lor F \equiv T$
• $P(1) \land P(-5) \equiv T \land F \equiv F$
• $P(3) \land P(y)$ is not a proposition. It becomes a proposition when y is assigned a value.

## 4.105 Quantification

• Quantification
• Quantification expresses the extent to which a predicate is true over a range of elements
• They express the meaning of the words all and some.
• Two most important ones:
• Universal quantifier
• Existential quantifier
• Example
• "All men are mortal"
• "Some computers are not connected to the network"
• A third quantifier called "uniqueness quantifier".
• Universal Quantifier
• The universal quantifier of predictate P(x) is proposition:
• P(x) is true for all values of x in the universe of discourse.
• We use the notation: $\forall x P(x)$, which is read "for all x"
• If the universe of discourse is finish, say $\{n_1, n_2, \ldots, n_3\}$ then the universal quanifier is simply the conjunction of the propositions over all elements:
• $\forall x P(x) \Leftrightarrow P(n_{1}) \land P(n_{2}) \land \ldots \land P(n_k)$
• Example 1:
• $P(x)$: "x must take a Discrete Mathematics course"
• $Q(x)$: "x is a Computer Science student."
• Where, the university of discourse for both $P(x)$ and $Q(x)$ is all university students.
• Let's express the following statements:
• Every CS student must take a discrete math course
• $\forall \ \ x \ \ Q(x) \rightarrow P(x)$
• Everybody must take a discrete maths course or be a CS student
• $\forall \ \ x \ \ (P(x) \lor Q(x))$
• Everybody must take a discrete maths course and be a CS student
• $\forall \ \ x \ \ (P(x) \land Q(x))$
• Example 2:
• Formalise statement S:
• S: "For every x and every y, x + y > 10"
• Let $P(x, y)$ by the statement x + y > 10, where the universe of discourse for x, y is the set of all integers.
• The statement S is: $\forall x \forall y P(x, y)$
• Can also be written as: $\forall x, y \ \ P(x, y)$
• Existential quantifier
• The existential quantification of a predicate $P(x)$is the proposition:
• "There exists a value x in the universe of discourse such that P(x) is true."
• We use the notation: $\exists \ x \ P(x)$, which reads "there exists x".
• If the universe of discourse is finite, say $\{n_1, n_2, \ldots, n_k\}$ then the existential quantifier is simply the disjunction of propositions over all the elements:
• $\exists \ x \ P(x) \Leftrightarrow P(n_1) \lor P(n_2) \lor \ldots \lor P(n_k)$
• Example 1
• Let $P(x, y)$ denote the statement "x + y = 5".
• The expression E: $\exists \ x \ \exists \ y \ P(x, y)$ means:
• There exists a value x and a value y in the universe of discourse such that $x + y = 5$ is true.
• For instance
• If the universe of discourse is positive integers, E is True.
• If the universe of discourse is negative integers, E is False.
• Example 2
• Let $a, b, c$ denote fixed real numbers.
• And S be the statement: "There exists a real solution to $ax^2 + bx - c = 0$"
• S can be expressed as $\exists \ x \ P(x)$ where:
• $P(x)$ is $ax^2 + bx - c = 0$ and the universe of discourse for x is the set of real numbers.
• Let's evaluate the truth value of S:
• When $b^2 >= 4ac, S \text{ is true , as } P(-b \mp \sqrt(b^2 - 4ac)) / 2a = 0$
• When $b^2 < 4ac, S\text{ is false }$ as there is no real number x that can satisfy the predicate.
• Uniqueness quantifier
• Special case of "existential quantifier".
• The uniqueness quantifier of prediction P of x is the proposition:
• There exists a unique value of x in the universe such that P of x is true.
• We use the notation: $\exists ! x \ P(x)$: read as there exists a unique x.
• Example:
• Let P(x) denote the statement: $x^2 = 4$
• The expression $E$: $\exists ! x \ P(x)$ means:
• There exists a unique value x in the universe of discourse such that $x^2 = 4$ is true.
• For instance
• If the universe of discourse is positive integers, E is True (as x = 2 is the unique solution)
• If the universe of discourse is integers, E is False (as x = 2 and x = -2 are both solutions)

## 4.107 Nested quantifiers

• Nested quantifiers
• To express statements with multiple variables we use nested quantifiers
• $\forall x \forall y P(x, y)$ - P(x, y) is true for every pair x, y
• $\exists x \ \exists y \ P(x, y)$ - There is a pair x, y for which P(x, y) is true.
• $\forall x \ \exists y \ P(x, y)$ - For every x, there is a y for whih P(x, y) i true.
• $\exists x \ \forall y \ P(x, y)$ - there is an x for which P(x, y) is true for every y.
• Binding variables
• A variable is said to be bound if it is within the scope of a quantifier.
• A variable is free if it is not bound by a quantifier or particular values.
• Example
• Let P be a propositional function
• And S the statement: $\exists \ x \ P(x, y)$
• We can say that:
• x is bound
• y is free
• Logical operations
• Logical operations can be applied to quantified statements
• Example
• If P(x) denotes "x > 3" and Q(x) denotes "x squared is even" then
• $\exists \ x \ (P(x) \lor Q(x)) \equiv T (ex. x = 4)$
• $\forall \ x \ (P(x) \rightarrow Q(x) \equiv F (ex. x = 5))$
• Order of operations
• When nested quantifiers are of the same type, the order does not matter.
• With quantifiers of different types, the order does matter.
• Example
• $\forall x \ \forall y P(x, y) \equiv \forall y \ \forall x \ P(x, y)$
• $\exists x \ \exists y \ P(x, y) \equiv \exists y \ \exists x \ P(x, y)$
• $\forall x \ \exists y \ P(x, y)$ is different from $\exists y \ \forall x \ P(x, y)$
• Precendence of quantifiers
• The quantifiers $\forall$ and $\exists$ have a higher precendence than all logical operators
• Example
• P(x) and Q(x) denote two propositional functions.
• $\forall x \ P(x) \lor Q(x)$ is the disjunction of $\forall x \ P(x) \text{ and } Q(x)$ rather than $\forall x \ (P(x) \text{ and } Q(x))$