Modelling with propositional logic

Propositional formulas can be used to model various circumstances, from mathematical functions to algorithmic problems.

A very simple application of propositional formulas is to use them to describe boolean functions.

Example Consider the statement: I am unhappy if, and only if, it rains and it is cold. So me being happy is a boolean function of it raining and it being cold. Such a boolean function can be expressed by a formula: when we write $X_0$ for it raining, and $X_1$ for it being cold, then $$\neg (X_0 \wedge X_1)$$ is a good and precise way to express whether I am happy.

Under certain circumstances, dependencies between values are not of a functional, but of a relational nature. Then, again, the possible combinations of (boolean) values can be expressed by a formula. This time the formula describes a relation.

Example I might be unhappy not only when it rains and it is cold, but in any case if it rains and it is cold. Then me being happy is no longer a function of it raining and it being cold. Rather, there is a relation between me being happy, it raining and it being cold. This relation can be expressed by a propositional formula. To this end, it is useful to agree that $X_2$ represents me being happy (in addition to what we agreed on in the previous example). Then $$X_0 \wedge X_1 \rightarrow \neg X_2$$ expresses the desired relation: all combinations of assigning truth values under which the formula evaluates to true describe the relation.

The above examples are simple, but very instructive. They show two different ways of using propositional formulas. These two different ways are explained more formally below, and it is explained what it means that specific circumstances are represented in propositional logic.

Concrete examples of modeling with propositional logic are colorability and sudoku.

Expressing functions

In the simplest case, we want to express an $m$-ary boolean function $f \colon \{0,1\}^m \to \{0,1\}$. Then we use a formula $\varphi$ with $\text{vars}(\varphi) \subseteq \{X_0, \dots, X_{n-1}\}$ and which satisfies $$f(a_0, \dots, a_{m-1}) = \llbracket \varphi\rrbracket_{\{X_0 \mapsto a_0, \dots, X_{m-1} \mapsto a_{m-1}\}}$$ for all $a_0, \dots, a_{m-1} \in \{0,1\}$. A good example is given above.

In more complicated cases, we may have a function $f \colon M \to \{0,1\}$ or even a function $f \colon M \to N$, where $M$ is not of the form $\{0,1\}^m$ for any $m$ and $N$ is different from $\{0, 1\}$.

Then values of $M$ have to be encoded as elements of $\{0,1\}^m$ for some appropriate value of $m$. Similarly, several formulas may be needed when $N$ has more than two elements.

Example We want to describe the function $f \colon \{0,1\}^3 \to \{0,1\}^4$ which describes how a bit string of length 3 is incremented. In the worst case, the value of this function has four bits. So we need four formulas altogether:

• The first formula describes the least significant bit, which is simply negated: $\neg X_0$.
• The second formula describes the next significant bit. This is the same as the corresponding input bit, if the least significant bit is 0, and else it is negated: $(\neg X_0 \wedge X_1) \vee (X_0 \wedge \neg X_1)$.
• The third formula is: $((\neg X_0 \vee \neg X_1) \wedge X_2) \vee (X_0 \wedge X_1 \wedge \neg X_2)$.
• The fourth formula is: $X_0 \wedge X_1 \wedge X_2$.

Expressing relations

In the simplest case, we want to express an $m$-ary boolean relation $r \subseteq \{0,1\}^m$. Then we use a formula $\varphi$ with $\text{vars}(\varphi) \subseteq \{X_0, \dots, X_{n-1}\}$ and which satisfies $$\langle a_0, \dots, a_{m-1}\rangle \in r \text{ iff } \{X_0 \mapsto a_0, \dots, X_{m-1} \mapsto a_{m-1}\} \mymodels \varphi$$ for all $a_0, \dots, a_{m-1} \in \{0,1\}$. Again, a good example is given above.

Representations

In many situations, it is important to agree on how objects are represented by partial variable assignments. In fact, this is often the most important step in modelling.

Suppose we wanted to say that if we put four balls into three bins, then there is one bin with at least two balls. Stated in a mathematical fashion, this means that for every function $f \colon \{0,1,2,3\} \to \{0,1,2\}$ it is true that there is a $j < 3$ such that $\lvert f^{-1}(j)\rvert \geq 2$.

We could use variables $X_{i,j}$ with $i<4$ and $j<3$ to represent a mapping $f$ as follows.

Suppose $\beta \colon \{X_{i,j} \colon i<4, j<3\} \to \{0,1\}$ is a partial assignment. Then it represents a mapping as desired if for every $i<4$ there is exactly one $j<3$ such that $\beta(X_{i,j}) = 1$ holds. If this is the case, it represents the mapping $f$ defined by $f(i) = j$ for the unique $j$ such that $\beta(X_{i,j}) = 1$.

That $\beta$ as above represents indeed a function is expressed by $$\bigwedge_{i<4}\dot{\bigvee_{j<3}} X_{i,j} \enspace.$$

The fact that $\beta$ representing a function represents a function with at leat "two balls in one bin" is expressed by $$\bigvee_{j<3}\bigvee_{i_0 < 4}\bigvee_{i_1 < i_0} (X_{i_0, j} \wedge X_{i_1, j})\enspace.$$

Altogether, if the above statement is true, then $$\bigwedge_{i<4}\dot{\bigvee_{j<3}} X_{i,j} \rightarrow \bigvee_{j<3}\bigvee_{i_0 < 4}\bigvee_{i_1 < i_0} (X_{i_0, j} \wedge X_{i_1, j})$$ evaluates to true under every assignment, that is, it is a tautology.

Exercises

Exercise Beantworten Sie die folgenden Fragen:

1. Wieviele Variablen werden bei der Modellierung von Sudoku genutzt?
2. Wieviele Variablen werden bei der Modellierung von Berechnungen verwendet?
3. Bestimmen Sie $\operatorname{depth}(\text{Symbols})$ für die Teilformel $\text{Symbols}$ aus der Modellierung von Berechnungen?
4. Bestimmen Sie $\operatorname{size}(\text{Symbols})$ für die Teilformel $\text{Symbols}$ aus der Modellierung von Berechnungen?
5. Lässt sich 8-Färbbarkeit eines Graphen $G=(V,E)$ mit $3|V|$-Variablen modellieren?

Exercise Modellieren Sie Dreifärbbarkeit von endlichen ungerichteten Graphen in Aussagenlogik, das heißt, geben Sie zu jedem endlichen ungerichteten Graphen $G$ mit Knotenmenge $\{0, \dots, m-1\}$ und $n$-elementiger Kantenmenge $\{\{i_0, j_0\}, \dots, \{i_{n-1}, j_{n-1}\}\}$ an:

1. eine geeignete Variablenmenge,
2. eine Formel $\chi_G$ über diese Variablenmenge,
3. wie 1-Belegungen von $\chi_G$ auf dieser Menge Färbungen mit drei Farben repräsentieren,
4. eine Formel $\varphi_G$ über der Variablenmenge, die zu jeder Färbung mit drei Farben ausdrückt, ob diese eine Dreifärbung ist.

Exercise Modellieren Sie Vierfärbbarkeit von endlichen ungerichteten Graphen in Aussagenlogik, das heißt, geben Sie zu jedem endlichen ungerichteten Graphen $G$ mit Knotenmenge $\{0, \dots, m-1\}$ und $n$-elementiger Kantenmenge $\{\{i_0, j_0\}, \dots, \{i_{n-1}, j_{n-1}\}\}$ an:

1. eine geeignete Variablenmenge,
2. wie partielle Belegungen auf dieser Menge Färbungen mit vier Farben repräsentieren,
3. eine Formel $\varphi_G$ über dieser Variablenmenge, die zu jeder Färbung mit vier Farben ausdrückt, ob diese eine Vierfärbung ist.

Exercise Die Frage nach der Gültigkeit der Gleichung P = NP ist eine schwierige Frage, an der sich immer wieder Wissenschaftler*innen versuchen. Wir haben Daten von vier fiktiven Personen zusammengetragen, die sich nacheinander mit dieser Frage beschäftigt haben, und diese in Form von Bedingungen formuliert:

• Die Vornamen lauten: Karl, Gabi, Emma, Heinz.
• Die Nachnamen lauten: Zunke, Lange, Meier, Kuhn.
• Die Heimatuniversitäten sind: Kiel, Saarbrücken, Aachen, München.

(*) Jeder Vorname, jeder Nachname und jede Universität kommt genau einmal vor.

0. Die erste Person forscht nicht an der Universität Saarbrücken und heißt Meier, aber nicht Heinz.
1. Emma Kuhn arbeite nicht als letzte an der Frage.
2. Für die Person namens Lange und die an der Universität in München gilt: Eine der beiden arbeitete direkt vor Karl und die andere direkt nach Karl an der Frage.
3. Die dritte Person forscht an der Universität Kiel.

Ziel ist es, durch eine geeignete Modellierung in Aussagenlogik die folgende Tabelle auszufüllen:

	Vorname	Nachname	Universität
1.
2.
3.
4.

Geben Sie für die Modellierung Folgendes an:

1. eine geeignete Variablenmenge (Sie dürfen eine eigene Indizierung verwenden!),
2. eine Formel $\chi$ über der Variablenmenge, die sicherstellt, dass (*) erfüllt ist,
3. wie die 1-Belegungen von $\chi$ auf der Variablenmenge die möglichen Lösungen repräsentieren,
4. zu jeder der Bedingungen $i < 4$ eine Formel $\varphi_i$, die diese ausdrückt, so dass $\chi \wedge \bigwedge_{i<4} \varphi_i$ alle Lösungen des Rätsels repräsentiert.

Exercise Ein hamiltonischer Kreis in einem endlichen, ungerichteten Graphen $G=(V,E)$ ist eine Folge von $n$ Knoten $P=\langle v_0, v_1, \dots, v_{n-1}\rangle$ mit $v_1,\dots, v_{n-1}\in V$, sodass gilt, dass erstens $\{v_n, v_0\}\in E$ und $\{v_i, v_{i+1}\}\in E$ für alle $i\in\{0, 1,\dots, n-2\}$, d. h. der erste und letzte und alle paarweise aufeinander folgenden Knoten sind im Graphen durch eine Kante verbunden, und, dass zweitens jeder Knoten in $V$ genau einmal in der Folge enthalten ist. Modellieren Sie das Problem Graphen auf hamiltonische Kreise zu überprüfen in Aussagenlogik. Das heißt, geben Sie zu jedem endlichen, ungerichteten Graphen $G=(V,E)$ mit Knotenmenge $V=\{0, \dots, n-1\}$ und $m$-elementiger Kantenmenge $\{\{i_0, j_0\}, \dots, \{i_{m-1}, j_{m-1}\}\}$ Folgendes an:

1. Eine geeignete Variablenmenge $\text{Var}_G$.
2. Wie eine Folge  $P_\beta$ von $n$ Knoten durch eine beliebige partielle Belegung $\beta\colon\text{Var}\to\{0,1\}$ repräsentiert wird.
3. Eine Formel $\chi_G$, deren 1-Belegungen genau die Belegungen sind, welche Folgen der Länge $n$ repräsentieren, bei denen alle aufeinanderfolgenden Knoten paarweise durch eine Kante verbunden sind. Das heißt, genau die repräsentierten Folgen, die zusammenhänge Pfade sind.
4. Eine Formel $\varphi_G$, deren 1-Belegungen genau die Folgen repräsentieren, die hamiltonische Kreise sind.

Lösung

---

1. $\text{Vars}_G = \{ X_i^v \mid v\in V(G), 0\leq i \leq |V(G)| - 1 \}$
2. Ein Knoten $v\in V(G)$ sei der $i$te Knoten des Pfades $P_{\beta}$ genau dann, wenn $\beta(X_i^v)=1$ gilt.
3. $\chi_G = \underbrace{\bigl(\bigwedge\limits_{i<|V(G)|} \dot{\bigvee_{v\in V(G)}} X_i^v\bigr)}_{\text{je Position im Pfad nur ein Knoten}} \wedge \underbrace{\left(\bigwedge\limits_{1<i<|V(G)|}\bigwedge\limits_{v\in V(G)}\left(X_i^v \rightarrow\bigvee\limits_{\{v,v'\}\in E(G)} X_{i-1}^{v'}\right)\right)}_{\text{Jeder Knoten (außer der 1.) im Pfad hat einen verbundenen Vorgänger.}}$
4. $\varphi_G=\chi_G \wedge \underbrace{\bigl(\bigwedge\limits_{v \in V(G)} \dot{\bigvee_{i< |V(G)|}} X_i^v\bigr)}_{\text{Jeder Knoten ist genau einmal enthalten.}} \wedge \underbrace{\left(\bigvee\limits_{\{v,v'\}\in E(G)} \left(X_{|V(G)| - 1}^v \wedge X_{0}^{v'}\right)\right)}_{\text{Der erste und letzte Knoten sind verbunden.}}$

Exercise Ordinary sudoku is, in some sense, 3-sudoku. (Why is this so?)

1. Give a definition of $n$-soduku for $n > 0$.
2. Model $n$-soduku in propositional logic.