Exercise 1
Let A be a propositional variable. Decide (and prove) whether there is a formula  such that
1.   (  A)  A
2.   (  A)  A
3.   (A  )  A
4.   (A  )  A
Exercise 2
Given a formula   A  B  C  (D  E) , find an equivalent formula  of the system L(|).
(we define | by 1 | 2  (1  2) for all 1, 2)
Exercise 3
Prove that the system L() is not functionally complete (i.e. "plnohodnotný").
Exercise 4
Decide and prove whether the system L() is functionally complete.
Exercise 5
Decide and prove whether the system L(, ) is functionally complete.
Exercise 6
Let A, B be countable family and let R  A × B be a relation such that for all a  A the set
Ba = {b | (a, b)  R} is a finite nonempty family. Find a family of propositional formulae T such that T
is satisfiable if and only if there is an injective function f : A  B such that f  R.
Exercise 7
Give a polynomial time algorithm that to any finite directed graph G = (V, E) (i.e. E  V × V ,
see http://en.wikipedia.org/wiki/Graph_(mathematics)) for detailed information) returns a formula
G such that G is satisfiable if and only if G is strongly connected (see http://en.wikipedia.org/
wiki/Strongly_connected_component). It suffices to describe the formula G and argue why it can be
constructed in time polynomial in the size of G.
(Note: The algorithm itself must not compute whether the graph is strongly connected. In particular,
the solution "decide whether G is strongly connected and return A if yes and A  A otherwise" does not
count)
Exercise 8
Give a polynomial time algorithm that to any finite directed graph G = (V, E) returns a formula G
such that G is satisfiable if and only if G contains a Hamiltonian cycle (http://en.wikipedia.org/
wiki/Hamiltonian_path).
It suffices to describe the formula G and argue why it can be constructed in time polynomial in the
size of G.
1