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 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: