Math 235 - Logic.
Some beautiful equations (and some ugly ones):
Justin Mullins.
EXAM 2
Down load it here.
Turing Machine
Here's a Turing machine 'simulator' (I guess real ones have infinite tapes) to do HW 5.
Homework 1:
1. Prove that the following are wffs. Use the rules given in class. The html for the connectives cannot be read by some browsers so I'll use the words AND, NOT, OR and IMPLIES instead. In the homework you hand in, replace them with the usual symbols.
a. ((NOT(A OR B)) IMPLIES C)
b. (C AND NOT(A)) IMPLIES (B AND NOT(C))
2. Translate into logical symbols, by giving constant names (A, B, C etc) to the atomic formulas and using connective symbols for the logical words.
a. If it is raining I take my umbrella but if it isn't raining and I remember, then I take my parasol.
b. It's difficult to make up random sentences but if you take the trouble it is always rewarding.
c. The fact that today is Wednesday does not imply that tomorrow is Thursday.
3. Prove that every wff has the same number of left parentheses as right parentheses.
4. The length of a wff is the number of symbols in it. For example, the length of ((NOT(A OR B)) IMPLIES C) is 12. Prove that for any positive number n, there exists at least one wff of length n.
5. Send me an email about you math/CS background, your exposure to logic and a photo. If you have a website I can link it to my homepage.
Homework 2:
1. Show that the set {AND, OR, IMPLIES, NOT} is 2-sufficient
2. Show that the same set is 3-sufficient
3. Show that the same set is sufficient (i.e. n-sufficient for any n).
4. Show that AND and OR can be defined in terms of IMPLIES and NOT, and conclude that {NOT, IMPLIES} is sufficient.
5. There is another connective NAND. A NAND B (written A|B) is logically equivalent to NOT(A AND B). Show that {NAND} is sufficient. Is {AND} sufficient (why, why not)?
Homework 3: Due Feb 10
Problems 3.9 (1) - (9)
Recall A OR B is an abbreviation for (NOT A) IMPLIES B, and (A AND B) means NOT(A IMPLIES (NOT B) ). Hints can be found HERE, but try them without the hints first.
Homework 4: Due Feb 17
1. Finish the proof of the completeness theorem for the propositional calculus. That is:
Let Σ be a maximally consistent set of sentences. Suppose v is a valuation function that gives the valuation of T for all atomic sentences in Σ. Assume that ψ is the shortest sentence in Σ that has the valuation F. Show that ψ cannot be of the form ¬α for any sentence α.
If your browser cannot read these symbols, the translation is:
Σ =SIGMA, ψ= psi, α=alpha and ¬=NOT
2. Problem 5.8 page 28
Homework 5: Due Friday Mar 24
Compactness theorem problems.
1. Prove that there is no sentence in any language extending the language of graphs that is true if and only if the graph has no cycles. A cycle is a finite path whose two endpoints are equal
2. Prove that there is no finite set of axioms that is satisfied only by the real numbers.
3. Prove that there is a structure that satisfies all the normal arithmetic of the real numbers but contains "infinitesimals" - that is numbers that are smaller (in absolute value) than every normal real number.
4. Write a Turing machine program to calculate the following functions:
1. f(n,m)= n+m
2. f(n)=3n
3. f(n,m)=nm
Use the simulator at the top of the page to check the program on a few inputs. Cut and paste the program to an email and send it to me so I can check them. A prize for the shortest.
Homework 6: Due Friday Apr 28
Well Orders
1. Let P be the set of polynomials in x with natural number coefficients. We define a well-order on P as follows (<= means "less than or equal to"):
If p and q are polynomials, then p<=q iff
0. p=q OR
1. deg(p) < deg(q) OR
2. deg(p)=deg(q) and the polynomial q-p (q minus p)
has positive leading coefficient.
(The leading coefficient of a polynomial is the coefficient of the highest power of x).
a) Show that <= is a well-order on P (this includes showing it is a partial order, a linear order and satisfies the well-ordering property).
b) Which well-order that we have studied in class (in terms of omega) is it isomorphic to?
2. Suppose that any finite sequence of letters a, b, c, ... is a word, and that all words are listed in alphabetical order.
a. Write down the first few words
b. Is this ordering a partial order? Linear order? Well order?
(Hint: Put these words into alphabetical order: a, aa, aab, aaab)
3. Suppose that X, Y and Z are well-orders, and that Y< Z. Show (using diagrams if necessary) that X+Y< X+Z. Also show that Y+X<= Z+X. But give an example to show that it is not necessarily true that Y+X< Z+X. (Here < and <= are curly).
4. Repeat Q.3 with multiplication replacing addition (assume also that X>0)
| 
