Category Archives: logic

Summer projects for students

Three students are in the midst of summer reading projects under my supervision, Acyr Locatelli, Alex Tao, and Nikhil Mehrotra.

Acyr is reading Ideals, Varieties, Algorithms by Cox, Little, and O’Shea, a very nice introduction to computational algebraic geometry.

Alex is reading Rational Points on Elliptic Curves by Silverman and Tate. This book deals with integral and rational solutions to cubic equations like

y^2=x^3+x-1000.

This class of problems, seemingly limited in scope, turns out to have many remarkable attendant structures, making it one of the most important directions of contemporary number theory.

Nikhil is reading Goedel, Escher, Bach by Douglas Hofstadter, a great classic on consciousness, mathematics, and the possibility of artificial intelligence.

I will be posting here their weekly reports, in case someone else wants to follow along. For now, here are

Alex’s report 1

Acyr’s report 1

Hmm

I guess I should then also disavow concern with my image, serious or not….

Logic question

Dear Prof. Kim,

Sorry to disturb your working.I am one of your students. Since we do not have tutorial during this reading week,I have got a problem of understanding one of the question from the homework. Not only me, but also other students have the same problem.The question is followed.
Q: Show that every truth table in 2 variables is the truth table of some formula of Propositonal Calculus.(Hint: 8=16/2)

I will be really appreciated if you can explain it for me.

Thanks,
Austin

Reply:

Call the variables A and B. Then given any assignment of truth values for A and B, you should be able to cook up a formula that’s true for that assignment and none else. This is very simple. For A=F and B=T, for example, you can use

(not A) and B

Make sure you understand this elementary construction. Now start experimenting with some truth tables:

A B P

—————-

T T

T F

F T

F F

That is, start with some sample fill-ins for the third column, and see if you can combine the elementary formulas above to come up with a P that works. If you experiment with a few, you may see a pattern. Alternatively, since there are only sixteen truth tables possible, you could just do them all separately in an ad hoc way 🙂