Enderton 1.5

Are the 5 sentential connectives enough to express everything?  Are
they overkill?  We can ask these questions from the perspective of
efficiency and possibility.

Here are some specific problems to think about.  We probably will not
get to all of these by Friday.

Consider the Majority-of-three connective, #.  So #(A,B,C) is supposed
to be true under exactly the truth assignments that make a majority of
A, B, C true.

0.  First, finish the graph 3-colorability problem.  From a given
graph G, form a wff phi such that phi is satisfiable iff G is
3-colorable.  You should argue that, given a satisfying assignment to
phi, we can read off a valid coloring (a coloring FUNCTION, with no
monochromatic edges), and, given a valid coloring, we can read off a
satisfying assignment.  How big is phi, if G has n vertices and m
edges?  How hard is it to construct phi?
1.  Make a truth table to illustrate the definition of #.
2.  Write a wff phi, using only AND and OR, so that the toplevel of
phi has the same truth table as #.
3.  A monotonic wff phi is a wff with the property that setting any of the
sentence symbols from FALSE to TRUE can not change the value of phi
from TRUE to FALSE.  Show that any monotonic wff is tautologically
equivalent to a wff that uses just AND and OR.  What about
non-monotonic wffs?
4.  Implement AND and OR using bike locks.  (That is, give a
configuration of 2 bike locks, A and B, so that the bike is free if A
AND B are opened.  Give a different configuration for A OR B.)
Implement # using bike locks.  Implement any monotonic wff using bike
locks.
5.  Can we express everything using just AND, OR, and NOT?  (That is, given
any wff, can we find a tautologically equivalent wff that uses just
AND, OR and NOT connectives?)  Can we express everything using just
IFF and NOT?
6.  Show how, given any wff phi, to form a wff psi that is
tautologically equivalent and in Conjunctive Normal Form, CNF:  An AND
of ORs of literals, where a literal is a sentence symbol or the
negation of a sentence symbol.
7.  Show how, given a wff phi in CNF, to make a tangle t of bike locks
and a number k such that phi is satifiable iff we can free the bike by
cutting at most k locks.
8.  Show how, given a collection of course requirements, we can make a
tangle t of bike locks and a number k, such that you can graduate iff
we can free the bike by cutting at most k locks.