1 MATHS 140 AUTUMN 2017 DEPAUL UNIVERSITY DR. ALEXANDER 1. Introduction In this assignment we're going to explore some aspects of boolean algebra, and first order predicates. These problems are a little lengthy, so please don't wait until the final night to begin working on them. Please complete all problems. You may work with others, but each students must hand in his or her own work. This assignment is due on Wednesday 20 September 2017. 2. The Problems (Problem 1) In two-valued logic we see that the three gates (, , ) are sufficient to produce any other gate. For example: p q (p q) (q p) But we know p q p q So we can write \"if, and only if\" as p q ( p q) ( q p) (a) Write the following gates with the three gates , , p xor q (tautology) and c (contradiction) (b) Furthermore we can reduce our universal set to (, ) or (, ). So let's use only (, ) and rewrite the following pq pq pq (c) Repeat part (b) with the set (, ), except the first piece should be pq (d) Good news, everyone! We can reduce further to a single universal gate NAND or NOR. Let's look at NAND: p NAND q (p q) 1 2 HOMEWORK 1 MATHS 140 AUTUMN 2017 DEPAUL UNIVERSITY DR. ALEXANDER Let's give the first, and possibly most important use for NAND. p NAND p p Rewrite the following gates with only NAND. pq pq , c pq HOMEWORK 1 MATHS 140 AUTUMN 2017 DEPAUL UNIVERSITY DR. ALEXANDER 3 (Problem 2) Since we are dealing with \"two-valued\" logic it necessitates all variables being bits. As mentioned in class this means we could just as easily write \"T\" and \"F\" as 1 and 0 (or 0 and 1 depending on circumstances). For this problem we will take false as zero and true as 1. Thus, for example, our table for \"and\" becomes p q p q min(p, q) p q 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 Notice that we've given the table in a somewhat reverse format from that of the class, but it's exactly the same operation. Also notice, that we now have several ways of expressing \"and.\" When we use only 0 and 1, we can multiply or take min/max, or add. By this setup, negation becomes p 1 p. The mod 2 addition is given by the symbol \"\" which has the table p q p q p xor q 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 This is essentially adding \"even\" with \"odd.\" Here, you can think of \"even\" as zero, so the fourth row says \"odd + odd = even.\" One operation that we can't do on True/False is exponentiation. Consider pq All of these make sense except possible 00 which is technically an indeterminate form, but we simply say 00 = 1. This is a fact we can derive from calculus. I don't need you to derive it, simply take that as an axiom for now. (a) Write the truth table for pq . What is the equivalent truth table of the 16 classical ones we showed in class? (b) Using our new found operation of exponentiating bits, show directly r pq 6= pqr What is the classical operation we've shown (in terms of statements in T/F)? Additionally, pick some numbers which are not 0, 1 and plug this in just to show that exponentiation is not associative, but simply right associative. (c) Show that exponentiation distrubtes over multiplication (i.e.) (p q)r pr q r 4 HOMEWORK 1 MATHS 140 AUTUMN 2017 DEPAUL UNIVERSITY DR. ALEXANDER What is the classical version of this? By \"classical version\" I mean the form that we would recognize with the symbols , , , , , ,xor. Hint: Recall that in part (a) you should have gotten pq q p p q HOMEWORK 1 MATHS 140 AUTUMN 2017 DEPAUL UNIVERSITY DR. ALEXANDER 5 (Problem 3) The valid argument forms we have seen generally take the form Hypothesis A, hypothesis B, therefore C This can be rewritten in as a single statement: (A B) C For example the classic modus ponens appears as (p (p q)) q . (a) Establish that the following argument form is valid by any method you choose. pq q (r s) r ( t u) pt u You may use a truth table, deduction with valid argument forms, or a combination thereof. (b) Rewrite this argument form as a single statement. Then reduce it by DeMorgan's laws if possible. (c) Negate the statement you wrote in part (b). Give an example (using actual statements for the variables) to show the negation does not yield a valid argument. 6 HOMEWORK 1 MATHS 140 AUTUMN 2017 DEPAUL UNIVERSITY DR. ALEXANDER (Problem 4) Consider the predicate P (x) on three different domains, integers, rationals, and reals. Integer: x Z, P (x) Rational: x Q, P (x) Real: x R, P (x) In this case, the domain changes the truth of the statement. For example, P (x) = \"x2 x 0\" is true when x is an integer, but otherwise false, since (1/2)2 (1/2) = (1/4). (a) Find a predicate P (x) so that the first two statements are true, but the final statement is false. (b) Find a predicate P (x) so that the final two statements are true, but the first statement is false. (c) Find a predicate P (x) so that the first and third statements are true, but the second statement is false. Hint: Parts (a) and (b) are easy. Part (c) will require a lot more thought. HOMEWORK 1 MATHS 140 AUTUMN 2017 DEPAUL UNIVERSITY DR. ALEXANDER 7 (Problem 5) Consider the following argument form: k N0 , P (k) P (k + 1) P (0) n N0 , P (n) (a) Is this a valid argument form? (b) Use this argument form to check the soundness of the following statement: 1 + 2 + 4 + + 2k = 2k+1 1. 8 HOMEWORK 1 MATHS 140 AUTUMN 2017 DEPAUL UNIVERSITY DR. ALEXANDER 3. Notes The exponential notation xy will be seen in several more contexts this term. Specifically when we get to counting possible numbers of functions f :AB We write the set of all such functions as B A makes sense as there are exactly |B||A| such functions. Additionally when we talk about the power set P(A) of a set A there are 2|A| subsets of A and so the notation 2A is often used in literature from a generation ago. Notice the direction of the arrow f : A B as compared to the notation B A . This works exactly like our boolean algebra pq q p. This suggests that our notation of exponentiating is a good one as it is broad enough to cover vastly different areas of mathematics, but specific enough to calculate a single number 210 = 1024. Once we add a touch of abstraction we see the utility in using the same symbol for \"different\" uses. Problem 5 has an argument which we don't see for the rest of Discrete Math I, but we spend roughly half of Discrete Math II unpacking. This is called mathematical induction (weak induction on one variable). Brodaly speaking there are two main branches of scientific thinking, deductive and inductive. Up until this point in your education you've probably only seen deductive reasoning (scientific method). Inductive reasoning is the other. Again, in the broadest terms, deduction is a general pattern to predict a specific outcome of an experiment. Induction on the other hand is taking a handful of individual items and recognizing a general pattern. Unfortunately, many people who have never worked extensively with induction tend to use it incorrectly. We'll fix that in Discrete Math