## 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 taken some course in theoretical computer science before.
You should know what
grammars, transition systems, decidability, recursive enumerability,
and NP-completeness are.

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>,
2023-07-13.

Imprint |

Data Protection