Automated Reasoning – Prerequisites

Stylistically, this is mostly a mathematical lecture (Definition, Definition, Lemma, Proof, Theorem, Proof, ...). If you strongly dislike this kind of lectures, you might consider picking another course.

You should have some basic knowledge of theoretical computer science, e. g., grammars, transition systems, undecidability results, NP-completeness.

You should be familiar with the mathematical way of thinking and with mathematical proof techniques (such as dealing with quantifiers, dealing with equivalences, proof by contradiction, proof by induction, etc.). You should be able to solve simple proof tasks yourself. For instance this one:

Let $A$ and $B$ be two sets. Prove: $B = \emptyset$ if and only if $(A \setminus B) \cup (B \setminus A) = A$.
Or this one:
Let $n \in \mathbb{N}$. Prove that $\sum_{i=1}^n (-1)^i\, i\,$ equals $n/2$ if $n$ is even and $-(n+1)/2$ if $n$ is odd.
Or this one:
Let $A$ be a set. Let $f : A \times A \rightarrow A$ be a binary function on $A$ with the property that for every $x \in A$ and every $y \in A$ there exists a $z \in A$ such that $f(x,z) = y$. Prove that for every $x \in A$ and every $y \in A$ there exists a $z \in A$ such that $f(x,f(y,z)) = x$.


Previous | Up | Next
Uwe Waldmann <uwe@mpi-inf.mpg.de>, 2021-09-13.
Imprint | Data Protection