187 – Selected solutions to problems from Chapter 1

September 19, 2011

Professor Warren Esty, one of the authors of our main textbook, has made available a list of solutions to some of the problems from Chapter 1. They are most of the odd numbered problems. Please let him (or me) know if you find errors or typos, or if you have suggestions for alternative solutions or different approaches.

Solutions (Chapter 1)

3 Comments | 187: Discrete mathematics | Permalink
Posted by andrescaicedo

187 – The resolution method

September 19, 2011

This note is based on lecture notes for the Caltech course Math 6c, prepared with A. Kechris and M. Shulman.

We would like to have a mechanical procedure (algorithm) for checking whether a given set of formulas logically implies another, that is, given {A_1, \dots, A_n, A}, whether

\displaystyle (A_1\land \dots \land A_n)\Rightarrow A

is a tautology (i.e., it is true under all truth-value assignments.)

This happens iff

\displaystyle A_1\wedge\dots\wedge A_n\wedge\neg A\text{ is unsatisfiable.}

So it suffices to have an algorithm to check the (un)satisfiability of a single propositional formula. The method of truth tables gives one such algorithm. We will now develop another method which is often (with various improvements) more efficient in practice.

It will be also an example of a formal calculus. By that we mean a set of rules for generating a sequence of strings in a language. Formal calculi usually start with a certain string or strings as given, and then allow the application of one or more “rules of production” to generate other strings.

A formula {A} is in conjunctive normal form iff it has the form

\displaystyle A_1\land A_2\land\dots\land A_n

where each {A_i} has the form

\displaystyle B_1\lor B_2\lor\dots\lor B_k

and each {B_i} is either a propositional variable, or its negation. So {A} is in conjunctive normal form iff it is a conjunction of disjunctions of variables and negated variables. The common terminology is to call a propositional variable or its negation a literal.

Suppose {A} is a propositional statement which we want to test for satisfiability. First we note (without proof) that although there is no known efficient algorithm for finding {A'} in cnf (conjunctive normal form) equivalent to {A}, it is not hard to show that there is an efficient algorithm for finding {A^*} in cnf such that:

{A} is satisfiable iff {A^*} is satisfiable.

(But, in general, {A^*} has more variables than {A}.)

So from now on we will only consider {A}s in cnf, and the Resolution Method applies to such formulas only. Say

{A=(\ell_{1,1}\vee\dots\vee\ell_{1,n_1})\wedge\dots \wedge (\ell_{k,1}\vee\dots\vee\ell_{k,n_k})}

with {\ell_{i,j}} literals. Since order and repetition in each conjunct (1):

\displaystyle \ell_{i,1}\vee\dots\vee\ell_{i,n_i}

are irrelevant, we can replace (1) by the set of literals

\displaystyle c_i=\{\ell_{i,1},\ell_{i,2},\dots ,\ell_{i,n_i}\}.

Such a set of literals is called a clause. It corresponds to the formula (1). So the formula {A} above can be simply written as a set of clauses (again since the order of the conjunctions is irrelevant): {C=\{c_1,\dots ,c_k\}}

=\{\{\ell_{i,1},\dots \ell_{i,n_1}\},\dots ,\{\ell_{k,1},\dots , \ell_{k,n_k}\}\}

Satisfiability of {A} means then simultaneous satisfiability of all of its clauses {c_1,\dots ,c_k}, i.e., finding a valuation {\nu} which makes {c_i} true for each {i}, i.e., which for each {i} makes some {\ell_{i,j}} true.

Example 1 A=(p_1\vee\neg p_2)\wedge (p_3\vee p_3)

c_1=\{p_1,\neg p_2\}

c_2=\{p_3\}

C=\{\{p_1,\neg p_2\},\{p_3\}\}.

From now on we will deal only with a set of clauses {C=\{c_1, c_2,\dots,c_n \}}. It is possible to consider also infinite sets {C}, but we will not do that here.

Satisfying {C} means (again) that there is a valuation which satisfies all {c_1,c_2,\dots}, i.e. if {c_i=\ell_{i,1}\vee\dots \vee\ell_{i,n_i}}, then for all {i} there is {j} so that it makes {\ell_{i,j}} true.

Notice that if the set of clauses {C_A} is associated as above to {A} (in cnf) and {C_B} to {B}, then

\displaystyle A\wedge B\text{ is satisfiable iff }C_A\cup C_B\text{ is satisfiable.}

By convention we also have the empty clause {\Box}, which contains no literals. The empty clause is (by definition) unsatisfiable, since for a clause to be satisfied by a valuation, there has to be some literal in the clause which it makes true, but this is impossible for the empty clause, which has no literals. For a literal {u}, let {\bar u} denote its “conjugate”, i.e. \bar u=\neg p, if u=p, and \bar u=p if u=\neg p.

Definition 1 Suppose now {c_1,c_2,c} are three clauses. We say that {c} is a resolvent of {c_1,c_2} if there is a {u} such that {u\in c_1}, {\bar u\in c_2} and

\displaystyle c=(c_1\setminus\{u\})\cup (c_2\setminus\{\bar u\}).

We allow here the case {c=\Box}, i.e. {c_1=\{u\},\ c_2= \{\bar u\}}.

Read the rest of this entry »

Leave a Comment » | 187: Discrete mathematics | Tagged: , | Permalink
Posted by andrescaicedo

187 – The P vs NP problem

September 19, 2011

This note is based on lecture notes for the Caltech course Math 6c, prepared with A. Kechris and M. Shulman.

1. Decision problems

Consider a finite alphabet {A}, and “words” on that alphabet (the “alphabet” may consist of digits, of abstract symbols, of actual letters, etc).

We use the notation {A^*} to indicate the set of all “words” from the alphabet {A}. Here, a word is simply a finite sequence of symbols from {A}. For example, if {A} is the usual alphabet, then

\displaystyle awwweeeedddfDDkH

would be a word.

We are also given a set {V} of words, and we say that the words in {V} are valid. ({V} may be infinite.)

In the decision problem associated to {V}, we are given as input a word in this alphabet. As output we say yes or no, depending on whether the word is in {V} or not (i.e., whether it is “valid”).

We are interested in whether there is an algorithm that allows us to decide the right answer.

Read the rest of this entry »

Leave a Comment » | 187: Discrete mathematics | Tagged: , , | Permalink
Posted by andrescaicedo

414/514 – Metric spaces

September 19, 2011

This is homework 2, due Monday September 26 at the beginning of lecture.

Let (X,d) be a metric space.

  • Show that if d_1:X\times X\to{\mathbb R} is defined by \displaystyle d_1(x,y)=\frac{d(x,y)}{1+d(x,y)}, then d_1 is also a metric on X.
  • Show that if U is open in (X,d) then it is open in (X,d_1), and viceversa.

Recall that U is open iff it is a union of open balls. Use this to explain why it suffices to show that if U is open in (X,d) then for any x\in U there is an \epsilon>0 such that

B_\epsilon^{d_1}(x):=\{y\mid d_1(x,y)<\epsilon\}\subseteq U,

and similarly, if V is open in (X,d_1) then for any z\in V there is a \delta>0 such that

B_\delta^d(z):=\{w\mid d(z,w)<\delta\}\subseteq V.

In turn, explain why to show this it suffices to prove that for any x\in X and any \eta>0 there is a \rho>0 such that

B^{d_1}_\eta(x)\supseteq B^d_\rho(x)

and, similarly, for any \tau>0 there is a \mu>0 such that

B_\tau^d(x)\supseteq B^{d_1}_\mu(x).

Finally, prove this by showing that we can take \rho=\epsilon (no matter what x is) and similarly, find an appropriate \mu that works for \tau (again, independently of x).

  • Illustrate the above in {\mathbb R}^2 as accurately as possible.
  • Suppose that a sequence (x_n)_{n\in{\mathbb N}} converges to x in (X,d) and to x' in (X,d_1). Show that x=x'.
  • Is it true that a sequence (x_n)_{n\in{\mathbb N}} is Cauchy in (X,d) iff it is Cauchy in (X,d_1)? (Give a proof or else exhibit a counterexample, with a proof that it is indeed a counterexample.)
  • (*) Show that any dense G_\delta subset of {\mathbb R} has the same size as {\mathbb R}.

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo

414/514 – Cauchy sequences

September 2, 2011

This is homework 1, due Friday September 9 at the beginning of lecture.

We define absolute value as usual: Given a real x, we say that {}|x| is x if x\ge0 and is -x otherwise.

Absolute values have useful properties: {}|x|=|-x|\ge0 for any x. Also, {}|x|=0 iff x=0. The key property is the triangle inequality: {}|a+b|\le|a|+|b|.

Formally, a sequence is a function s:{\mathbb N}\to{\mathbb R}. As usual, we write the sequence as s_1,s_2,\dots rather than s(0),s(1),\dots

A sequence s is a Cauchy sequence iff for all \epsilon>0 there is an N\in{\mathbb N} such that whenever n,m\in{\mathbb N} and n,m>N, we have |s_n-s_m|<\epsilon.

A sequence s converges iff there is a real r such that for all \epsilon>0 there is an N\in{\mathbb N} such that whenever n\in{\mathbb N} and n>N, we have |r-s_n|<\epsilon.

Note that these concepts also make sense in {\mathbb Q}. Now we require all the s_n to be rational, and we require \epsilon and r to be rational as well.

  • Show that if a sequence converges, then it is Cauchy.
  • Give an example of a Cauchy sequence in {\mathbb Q} that does not converge.
  • Show that any Cauchy sequence in {\mathbb R} converges.

Cauchy’s way of defining the reals was to use Cauchy sequences as the basic building blocks rather than cuts. Again, the idea is that we want to have all the limits, and in {\mathbb Q} some of these limits are missing. In the case of cuts, the way of solving the presence of gaps in {\mathbb Q} was by giving names to all the gaps (the cuts), and adding the names.  The easiest repair to the lack of limits here will be the same: We give a name to the limits (the sequences themselves) and the reals will be just the sequences.

There is a problem here that does not occur with the construction using cuts, namely different sequences may have the same limit. We should identify all of them.

Recall that an equivalence relation on a set X is a binary relation \sim that is:

  1. Reflexive: For any x\in X, x\sim x.
  2. Symmetric: For any x,y\in X, if x\sim y then also y\sim x.
  3. Transitive: For any x,y,z\in X, if x\sim y and y\sim z, then x\sim z.

If \sim is an equivalence relation, the equivalence classes determined by \sim are the sets {}[x]=\{y\in X\mid x\sim y\}. An intuitive way of thinking about this is that we are looking at X from a distance, and so we cannot distinguish points that are close to one another, we just see them smashed together as a single point. Here, two points x,y are close iff x\sim y.

Let s and t be two Cauchy sequences of rationals. Say that s\sim t iff s-t converges to 0. Here, of course,  s-t is the sequence r_1,r_2,\dots with r_n=s_n-t_n.

  • Show that \sim is an equivalence relation. Check that any Cauchy sequence s is equivalent to infinitely many other sequences.
  • Define {\mathbb R} as the set of equivalence classes of the relation \sim. The elements of {\mathbb R} are then Cauchy sequences or, more precisely, collections of Cauchy sequences. A typical element of {\mathbb R} is a class {}[s], and we think of {}[s] as the limit of s. Of course, we have a copy of {\mathbb Q} inside {\mathbb R}: We can identify the rational q with the class q^*=[s] of all sequences s that converge to q.
  • Define +,\times,< in {\mathbb R} and verify that with these definitions we have an ordered field.
  • Verify that {\mathbb R} is complete, meaning that the least upper bound property holds.

This gives a second sense in which {\mathbb R} is complete: It contains the limits of all Cauchy sequences. A small but important point not mentioned above is the following: Given a sequence s of rationals, let s' be its “copy” inside {\mathbb R}, i.e., (s')_n=s_n^*. Then s' is Cauchy iff s is Cauchy, and s converges to a rational q iff s' converges to q^*.

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo