Week 2

Quick Questions

True or False?

\vDash A \lor \lnot A

Solution

True, because either $A$ or $\lnot A$ will always be true, we obtain that $A \lor \lnot A$ is a tautology. We use the notation $\vDash F$ to express this fact.

If $F$ is a tautology, then $\lnot F$ is unsatisfiable.

Solution

True, see Lemma 2.2 in script.

What is a Universe in predicate logic?

The set of all formulas of predicate logic
A function that assigns 0 or 1 to each element of a set.
A formula that is true in every interpretation
The set of objects we want to reason about

Solution

is correct.

True or false?

((A \to B) \lor B) \land C \vDash ((A \to B) \lor (B \to C)) \lor (A \to C)) \lor C

Solution

True, one can make the observation that in every case where the left-hand side is true, $C$ must be $1$ . Therefore, we obtain that the right-hand side automatically becomes true. Thus, we have indeed a logical consequence.

Correct application of exaclty one rule of Lemma 2.1?

\lnot(\lnot A \land C) \equiv A \lor \lnot C

Solution

No, we used double negation and De-Morgan at once, we should split it up as follows:

\lnot(\lnot A \land C) \equiv \lnot \lnot A \lor \lnot C \equiv A \lor \lnot C

Correct application of exaclty one rule of Lemma 2.1?

A \land (B \lor C) \equiv (A \land B) \lor (A \land C)

Solution

Yes, we have used only the first distributive law.

Which statements are true?

There are infinitely many interpretations in predicate logic, while there are only finitely many in propositional logic.
A formula of predicate logic always has a fixed truth value
Quantifiers only exist in predicate logic
Propositional logic is "stronger" than predicate logic, i.e. we can express more statements.

Solution

True, because there are e.g. infinitely many universes, while there is only a finite amount of propositional symbols in propositional logic, i.e. there are only $2^n$ many interpretations.
False, the truth value may change if we e.g. use another universe.
True
False, predicate logic is "stronger", see 3.

True or False?

\forall x \forall y P(x,y) \equiv \forall y \forall x P(x,y)

Solution

True. See 2.4.7 in script.

Under which interpretation is the following formula true?

\forall x \forall y \exists z \ \left(P\left(x,y\right) \to \left(P\left(x,z\right) \land P\left(z,y\right)\right)\right)

Universe $U = \mathbb{N}$ and $P(x,y) = 1 \iff x < y$
Universe $U = \mathbb{N}$ and $P(x,y) = 1 \iff x \leq y$
Universe $U = \mathbb{R}$ and $P(x,y) = 1 \iff x < y$
Universe $U = \mathbb{N}$ and $P(x,y) = 1 \iff x \text{ is even}$

Solution

False, counterexample: $x = 1, y = 2$ . There exists no number $z$ "between" $x = 1$ and $y = 2$ .
True, if we set $z = x$ , then the formula is true (if we fix any $x, y$ and set $z = x$ , then $x \le y$ implies $x \le z = x$ and $x = z \le y$ )
True, if we set $z = \frac{x + y}{2}$ , then the formula is true (we can always "find" a real number between $x$ and $y$ if $x < y$ )
True, the value of $y$ doesn't matter here and setting $z = x$ trivially satisfies the formula.

Predicate Logic

A short rundown of the main concepts:

💡

Interpretations and Universes Instead of assigning truth values to the propositional symbols to interpret the formula and obtain a mathematical statement, as we did in propositional logic, we now always have to choose a set of mathematical objects (such as $\mathbb{N}, \mathbb{R}$ or similar) we want to reason about. We call this set the Universe denoted by $U$ .

💡

Predicates take elements from the universe and spit out a truth value ( $P : U^k \to \{0,1\}$ ). Example interpretations for predicates: $\text{prime}(x), \text{less}(x,y)$ .

💡

Functions take elements from the universe and spit out an element from the Universe ( $f : U^k \to U$ ). Example interpretations for functions: $x + y$ , $x^2$ (note that we sometimes use the infix notation and not something like $\text{plus}(x,y)$ ). Note that we also allow $k = 0$ , so we would obtain a function taking $0$ arguments, in this way, we can define constants and therefore use expressions like $x + 0$ inside the interpreted formula.

💡

Variables (often denoted by $x,y,z$ ), which are free (more about his in chapter 6), can take any value from the universe. A variable is basically free if there is no quantifier, which is at an outer level of the formula where the variable appears, referring to the same variable. Consider for example the expression $\forall x Q(x,y)$ , here $y$ is a free variable, while $x$ is not.

💡

Quantifiers:

$\forall x$ F is true if for any value $x$ in $U$ , formula $F$ is true.
$\exists x$ F is true if there exists $x$ in $U$ , such that formula $F$ is true.

By combining these elements, predicate logic allows for the creation of more complex and expressive statements than propositional logic.

Exercises

Translation of predicate logicSource: Leon Kolmanic (HS23)

Consider the following interpretation. Let $U = \mathbb{Z}$ be the universe. And

Q(x) = 1 \iff x \text{ is square}

P(x,y) = 1 \iff x = y

\text{sum}(x,y) = x+y

Write down formulas of predicate logic, such that our interpretation is fitting and expresses the following statements (numbers refer to integers):

There is a square number
The sum of two arbitrary numbers is not square
For every number $a$ , there is a number $b$ , such that $a + b$ is square
The sum of two squares is a square

Additionally, translate these formulas into statements under the given interpretation:

$\forall x \forall y ((Q(x) \land Q(y)) \to P(x,y))$
$\forall x (Q(x) \to (\exists a \exists b P(x,\text{sum}(a,b))))$

Propositional Logic Proof Patterns