Logic B-Exam
January 1996
There are 3 questions worth 10 points each for a total of 30 points.
-
The 3-colorability problem is as follows.
You are given a finite undirected graph G = (V,E).
You have to decide whether G has a 3-coloring, i.e.,
an assignment of one of three colors (say, red, green, and blue)
to each node so that no edge connect two nodes of the same color.
Show that this problem can be polynomially reduced to satisfiability
of propositional formulas.
- Fix a finite vocabulary L that consists of
predicate and function symbols. A first-order theory over
L is a set S of first-order sentences over
L that is closed under logical implication, i.e., if
S(logically implies)s, then s(is an element
of)S. The theory S is complete if for
every first-order sentence s over L we have
that either s(is an element of)S or ~s(is an
element of)S. Use the Completeness Theorem to show that if
S is consistent, complete, and recursively enumerable, then
it is recursive.
-
Let a be the first-order sentence
(for All)x(there Exists)yP(x,y).
Find a second-order Skolem normal-form sentence b for a.
That is, b should:
-
have a quantifier prefix consisting of a string of existential
second-order quantifiers, followed by a string of universal
first-order quantifiers, followed by a quantifier-free formula,
-
be logically equivalent to a
Justify why b is logically equivalent to a.