Homework Set 1 Solution

Complete each of the following problems to the best of your ability. Remember, you can’t be graded on what you don’t write down so (unless you are just making stu up) something is better than nothing. Discussing problems between each other is ne, but your nal writeup and work must be your own.







Propositional Logic




(1.1.2 in the book) Which of these are propositions? What are the truth values of those that are proposi-tions?



Do not pass go.



What time is it?



There are no black ies in Maine.



4 + x = 5.



The moon is made of green cheese.



2n 100.



(1.1.8 in the book) Let P be the proposition ’I bought a lottery ticket this weekend’ and Q be the proposition ’I won the million dollar jackpot’. Express each of the following propositions in english.



:P



P _ Q



P ! Q



P ^ Q



P()Q



:P !:Q



:P ^:Q



:P _ (P ^ Q) - can this one be simpli ed at all?



(1.1.32 in the book) Construct truth tables for the following propositions.



P !:P



P():P



P xor (P _ Q)



(P ^Q)!(P _Q)



(Q ! :P) () (P () Q)



(P () Q) xor (P () :Q)



For each proposition in (3) above, try to simplify it as much as possible into the smallest proposition you can. Let the truth tables guide you, if you need it.



In class, we discussed that there are 16 possible compound propositions of two variables, by looking at how many ways a truth table of two variables could be lled out. Give expressions for all possible two-variable boolean propositions F (A; B) (for example, F (A; B) = A () B).



For each answer to (5) above, try to express it equivalently using only :; ^; _.









1
Computer Science Department - Rutgers University










7) In class, we discussed one-variable propositions and two-variable propositions. Why not three - possi-ble compound propositions F (A; B; C)? By considering the possible values of C (e.g., True or False), try to write or expand a boolean function F (A; B; C) in terms of combinations of one- or two-variable propositions.




Argue from (6) and (7) above that a computer that can compute :; ^; _ could theoretically compute any boolean function of any number of variables.



(1.3.14, 1.3.15 in the book) For each of the following, show that it is either a tautology, or nd an assignment of P and Q to make the expression false:



(:P ^(P !Q))!:Q




(:Q^(P !Q))!:P First Order Predicate Logic




Let L(x; y) be the statement that x loves y. For each of the following statements, 1) translate the statement into rst order predicate logic, 2) negate this expression and simplify as much as possible (pulling the negation inside), and 3) translate the negation back to English. Some of these may include propositions beyond just using the predicate L.




{ Everybody loves somebody. { Somebody loves everybody. { Socrates loves nobody.




{ Somebody who isn’t Socrates loves Socrates.




{ Everybody loves somebody who isn’t themselves. { There are at least two people who love each other.




{ There are at least two people who love each other and no one else. Inference




1) The Resolution Inference Rule states that if (P _ Q) and (:P _ R), we may conclude (Q _ R). Show that




(P _Q)^(:P _R)!(Q_R) (1)




is a tautology, i.e., always true. The truth table is one approach - are there any others?




Modus Ponens is the rule that if P and P ! Q, we may conclude Q. Show that this is really a simple version of the resolution inference rule. Hint: What can be done or said about implication propositions? What is R?



It can be shown that the resolution inference rule is ‘complete’ in the sense that it is all that is needed in order to conclude or infer everything that can be concluded or inferred. Why might other rules of inference still be interesting or useful?



(1.6.20 in the book) Determine whether these are valid arguments. Abstract the statements as much as possible to be able to analyze the logical structure / errors.



If x is a positive real number, then x2 is a positive real number. Therefore, if a2 is positive, where a is a real number, then a is a positive real number.




If x2 6= 0 where x is a real number, then x 6= 0. Let a be a real number with a2 6= 0; then a 6= 0.







2
Computer Science Department - Rutgers University










(1.6.26) Justify the rule of universal transitivity, which states that if 8x : P (x) ! Q(x) and 8x :



Q(x) ! R(x) are true, then 8x : P (x) ! R(x). Proofs




(1.7.16) Prove that if m and n are integers and nm is even, then m is even or n is even.



What is the best approach here, direct proof, proof by contraposition, or proof by contradiction - why?




Complete the proof.




Prove that for any integer n, n is divisible by 3 i n2 is divisible by 3. Does your proof work for divisibility by 4 - why or why not? Identify the kind of proof steps you used, and why.
p




3) Prove that 3 is irrational. What is the best proof approach to take, and why?




Prove that if you take 101 pigeons, and try to force them into 100 pigeonholes, there is some hole that has two pigeons. What is the best proof approach to take, and why?



Generalize the result of the previous problem: that if you take N pigeons and try to force them into M < N pigeonholes, some hole must have at least N=M many pigeons.

































































































































3