Problem 1: The World is Not/And/Or Enough (25 points)

In class, we discussed logical operations like‘and’,‘implies’, etc - the purpose of these operations is to take propositions and combine them to produce new statements, and we worked to understand the relationship between their truth values. We can think‘and’like a function F (A, B) = (A V B), where F (A, B) is true only when A, B are both true, and false otherwise. Each logical operation can be thought of in this way, a function that takes as input two truth values (or propositions that have truth values) and gives as output a proposition with a corresponding truth value.

Importantly, we could then consider operations on more variables - like F (A, B, C) = (AVB VC), where this function is true when at least one of A, B, C is true, and is false otherwise.

The purpose of this problem is to understand what boolean or logical functions are possible, and how to calculate them.

1) Note that for two variables A1 , A2 , there are 4 possible arrangements of truth values TT, TF, FT, FF . If you had N many variables, how many possible arrangements of truth values could these variables have?

2) A logical operation needs to give an output truth value for each possible arrangement of input truth values. How many logical operations are possible on two variables? How many possible logical operations are there on N variables? (Hint:  How many possible truth tables  could you make with N many variables?  How many rows would it have, how many possible ways to fill the final column? )

3) For each possible logical operation on two variables, show that it can be expressed using some combination of AND (V), OR (V), and NOT (-). How do you know that you got them all?

The result of the previous problem is that any two variable logical operation F (A, B) can be expressed in terms of three operations, AND/NOT/OR. These next problems mean to show that this is true for any logical operation, on any number of variables.

4) Consider a boolean operation on three variables, F (A, B, C).  Show that no matter what, F actually is, the following holds:

F (A, B, C) 三 [F (A, B, True) V C] V [F (A, B, False) V -C]                                   (1)

5) Note that F (A, B, True) and F (A, B, False) are in fact two variable logical operations. Use the previous result to argue that any three variable logical operation can be expressed using only AND/OR/NOT.

6) Argue then that any four variable logical operation can be expressed using only OR/NOT/AND, and in fact, any logical operation on any finite number of variables can be expressed using only OR/AND/NOT.

Problem 2: True Facts about the Justice League (25 Points)

You work for noted villain the Calculator. Based on your research, you know the following things are true:

● Batman can only defeat Superman if Superman is alone and Batman has Kryptonite.

● To get Kryptonite, Batman must partner with Lex Luthor.

● If Batman partners with Lex Luthor, Wonder Woman will help Superman.

● If Wonder Woman helps Superman, then Superman is not alone.

The Calculator asks you whether Batman can defeat Superman, but as you start to explain why or why not, they interrupt you - “words are a coward’s math, someone who is good with words can make anything sound true! Prove your claim to me logically.”

1) Introducing variables for each sub-proposition, (for instance A = Batman can defeat superman), represent the four statements above in terms of these variables in logical notation.

2) Is it possible that Batman can defeat Superman?   i.e., is it possible that the statement A is true?   Show, logically, why or why not. (Hint:  Assume that A is true .  From the facts you know (as expressed in the previous problem), what else can you work out the truth value of ? )

3)  The Calculator, nodding as they listen, concurs with your calculations. And then asks the following question: If Batman fails to defeat Superman, is it because Wonder Woman helped him? Why or why not.

Problem 3:  Calculating the Limits of Calculation (25 Points)

Computers can do a lot! But they can’t do everything.

1)  Argue that there are at most countably infinite computer programs.

Think about the problem of computing real numbers as the output of a program.  A computer might calculate 1/3 for instance, by printing 0.3, then go into an infinite loop repeating 3, forever.  More complicated programs could calculate more complex things, like the square root of 2, or π for instance.

2)  Argue that there are real numbers that cannot be calculated by any computer program.  (Hint:   Think  about pairing every program with its real number output.)

3)  Does it matter if you used a different language? Multiple languages? More powerful computers? Why or why not?

4)  Conclude that there are fundamental limits to what can be computed by any computer.