Hints, Solutions and Help -- a companion to GIAM

Chapter 2 -- Logic and quantifiers

Section 2.1 -- Predicates and Logical Connectives

  1. Design a digital logic circuit (using and, or & not gates) that implements an exclusive or.
    First, it's essential to know what is meant by the term "exclusive or". This is the interpretation that many people give to the word "or" -- where "X or Y" means either X is true or Y is true, but that it isn't the case that both X and Y are true. This (wrong) understanding of what "or" means is common because it is often the case that X and Y represent complimentary possibilities: old or new, cold or hot, right or wrong... The truth table for exclusive or (often written xor, pronounced "ex-or", symbolically it is usually ⊕) is
    A B A ⊕ B
    T T Ø
    T Ø T
    Ø T T
    Ø Ø Ø

    So it's true when one, or the other, but not both of its inputs are true. The upshot of the last sentence is that we can write A ⊕ B   ≅   (A ∨ B) ∧ ¬(A ∧ B).

    The above reformulation should help...

  2. Consider the sentence "This is a sentence which does not refer to itself." which was given in the beginning of this chapter as an example. Is this sentence a statement? If so, what is its truth value?

     
     

    The only question in your mind, when deciding whether a sentence is a statement, should be "Does this thing have a definite truth value?"

    Well?

    Isn't it just plainly false?

  3. Consider the sentence "This sentence is false." Is this sentence a statement?

     

    Try to justify why this sentence can't be either true or false.

     

  4. Complete truth tables for each of the sentences (A ∧ B) ∨ C and A ∧ (B ∨ C). Does it seem that these sentences have the same logical content?

     
    A tiny hint here: since the sentences involve 3 variables you'll need truth tables with 8 rows. Here's a template.

    ABC(A ∧ B) ∨ CA ∧ (B ∨ C)
    T T T    
    T T Ø    
    T Ø T    
    T Ø Ø    
    Ø T T    
    Ø T Ø    
    Ø Ø T    
    Ø Ø Ø    

  5. There are two other logical connectives that are used somewhat less commonly than ∨ and ∧. These are the Scheffer stroke and the Peirce arrow -- written | and ↓, respectively --- they are also known as NAND and NOR. The truth tables for these connectives are:
    A B A|B
    T T Ø
    T Ø T
    Ø T T
    Ø Ø T
                   
    A B A↓B
    T T Ø
    T Ø Ø
    Ø T Ø
    Ø Ø T
    Find an expression for (A  ∧ ¬ B) ∨ C using only these new connectives (as well as negation and the variable symbols themselves).
    Sorry, I know this is probably the hardest problem, but I'm (mostly) not going to help...

    Just one hint to help you get started: NAND and NOR are the negations of AND and OR (respectively) so, for example, (X ∧ Y)   ≅   ¬(A|B).

Section 2.2 -- Implication

  1. The transitive property of equality says that if a=b and b=c then a=c. Does the implication arrow satisfy a transitive property? If so, state it.
    I sometimes like to rephrase the implication X ⇒ Y as "X's truth forces Y to be true."
  2. Complete a truth table for the compound sentences A ⇒ B and ¬A ∨ B.
    You should definitely be able to do this one on your own, but anyway, here's an outline of the table:
    A B A ⇒ B ¬A ∨ B
    T T   
    T Ø   
    Ø T   
    Ø Ø   
  3. Complete a truth table for the compound sentence A ⇒ (B ⇒ C) and for the sentence (A ⇒ B) ⇒ C. What can you conclude about conditionals and the associative property?
    No help on this one other than to say that the associative property does not hold for implications.
  4. Determine a sentence using the and connector (∧) that gives the negation of A ⇒ B.
    Hmmm... This will seem like a strange hint, but if you were to hear a kid at the playground say "Oh yeah? Well, I did call your mom a fatty and you still haven't clobbered me! Owww! OWWW!!! Stop hitting me!!"

    What conditional sentence was he attempting to negate?

  5. Rewrite the sentence "Fix the toilet or I won't pay the rent!" as a conditional.
    The way I see it there are eight possible ways to arrange "You fix the toilet" and "I'll pay the rent" (or their respective negations) around an implication arrow.

    Here they all are. You decide which one sounds best.

    1. If you fix the toilet, then I'll pay the rent.
    2. If you fix the toilet, then I won't pay the rent.
    3. If you don't fix the toilet, I'll pay the rent.
    4. If you don't fix the toilet, then I won't pay the rent.
    5. If I payed the rent, then you must have fixed the toilet.
    6. If I payed the rent, then you must not have fixed the toilet.
    7. If I didn't pay the rent, then you must have fixed the toilet.
    8. If I didn't pay the rent, then you must not have fixed the toilet.

    Some of those are truly strange...

  6. Why is it that the sentence "If pigs can fly, I am the king of Mesopotamia." is true?
    Unless we're talking about some celebrity bringing their pet Vietnamese pot-bellied pig into first class with them, or possibly a catapult of some type... The antecedant (the if part) is false, so Yay! I AM the king of Mesopotamia!! Whoo-hooh! What? I'm not? Oh. But the if-then sentence is true. Bummer.
  7. Express the statement A ⇒ B using the Peirce arrow and/or the Scheffer stroke. (See Exercise 5 in the section 2.1.)
    You'll want to use |, the Scheffer stroke, aka NAND, because it's truth table contains three T's and one Ø -- you'll just need to figure out which of its inputs to negate so as to make that one Ø occur in the second row of the table instead of the first.
  8. Find the contrapositives of the following sentences.
    1. If you can't do the time, don't do the crime.
    2. If you do well in school, you'll get a good job.
    3. If you wish others to treat you in a certain way, you must treat others in that fashion.
    4. If it's raining, there must be clouds.
    5. If an ≤ bn, for all n and ∑n=0∞ bn is a convergent series, then ∑n=0∞ an is a convergent series.
    1. If you do the crime, you must do the time.
    2. If you don't have a good job, you must've done poorly in school.
    3. If you don't treat others in a certain way, you can't hope for others to treat you in that fashion,
    4. If there are no clouds, it can't be raining.
    5. If ∑n=0∞ an is not a convergent series, then either an > bn, for some n or ∑n=0∞ bn is not a convergent series.
  9. What are the converse and inverse of "If you watch my back, I'll watch your back."?
    The converse is "If I watch your back, then you'll watch my back." (Sounds a little dopey doesn't it -- likes its sort of a wishful thinking...)

    The inverse is "If you don't watch my back, then I won't watch your back." (Sounds less vapid, but it means the same thing...)

  10. The integral test in Calculus is used to determine whether an infinite series converges or diverges: Suppose that f(x) is a positive, decreasing, real-valued function with limx → ∞ f(x) = 0, if the improper integral ∫0∞ f(x) has a finite value, then the infinite series ∑n=1∞ f(n) converges. The integral test should be envisioned by letting the series correspond to a right-hand Riemann sum for the integral, since the function is decreasing, a right-hand Riemann sum is an underestimate for the falue of the integral, thus

    ∑n=1∞ f(n) < ∫0∞ f(x).

    Discuss the meanings of and (where possible) provide justifications for the inverse, converse and contrapositive of the conditional statement in the integral test.
    The inverse says -- if the integral isn't finite, then the series doesn't converge. You can cook-up a function that shows this to be false by (for example) creating one with vertical asymptotes that occur in between the integer x-values. Even one such pole can be enough to make the integral go infinite.

    The converse says that if the series converges, the integral must be finite. The counter-example we just discussed would work here too.

    The contrapositive says that if the series doesn't converge, then the integral must not be finite. If we were allowed to use discontinuous functions, it isn't too hard to come up with an f that actually has zero area under it -- just make f be identically zero except at the integer x-values where it will take the same values as the terms of the series. But wait, the function we just described isn't "decreasing" -- which is probably why that hypothesis was put in there!

Section 2.3 -- Logical equivalences

  1. There are 3 operations used in basic algebra (addition, multiplication and exponentiation) and thus there are potentially 6 different distributive laws. State all 6 "laws" and determine which 2 are actually valid. (As an example, the distributive law of addition over multiplication would look like x + (y ⋅ z) = (x + y) ⋅ (x + z), this isn't one of the true ones.)
    These "laws" should probably be layed-out in a big 3 by 3 table. Such a table would of course have 9 cells, but we won't be using the cells on the diagonal because they would involve an operation distributing over itself. (That can't happen, can it?)

    I'm going to put a few of the entries in, and you do the rest.
    + * ^
    + Ø x + (y * z)
    = (x + y) * (x + z)     		x + (yz)
    = (x+y)(x+z)
    * x*(y+z)
    = (x*y)+(x*z)     		Ø  
    ^  
         		  Ø

  2. Use truth tables to verify or disprove the following logical equivalences.
    1. (A ∧ B) ∨ B    ≅    (A ∨ B) ∧ B
    2. A ∧ (B ∨ ¬A)    ≅    A ∧ B
    3. (A ∧ ¬B) ∨ (¬A ∧ ¬B) ≅ ((A ∨ ¬B) ∧ (¬A ∨ ¬B)
    4. The absorption laws.
    You should be able to do these on your own.
  3. Draw pairs of related digital logic circuits that illustrate DeMorgan's laws.
    Here's the pair that shows the negation of an AND is the same as the OR of the same inputs negated.
  4. Because a conditional sentence is equivalent to a certain disjunction, and because DeMorgan's law tells us that the negation of a disjunction is a conjunction, it follows that the negation of a conditional is a conjunction. Find denials (the negation of a sentence is often called its "denial") for each of the following conditionals.
    1. "If you smoke, you'll get lung cancer."
    2. "If a substance glitters, it is not necessarily gold."
    3. "If there is smoke, their must also be fire."
    4. "If a number is squared, the result is positive."
    5. "If a matrix is square, it is invertible."

     

    1. "You smoke and you won't get lung cancer."
    2. "A substance glitters and it is necessarily gold."
    3. "There is smoke,and there isn't fire."
    4. "A number is squared, and the result is not positive."
    5. "A matrix is square and it is not invertible."
  5. The so-called "ethic of reciprocity" is an idea that has come up in many of the world's religions and philosophies. Below are statements of the ethic from several sources. Discuss their logical meanings and determine which (if any) are logically equivalent.
    1. "One should not behave towards others in a way which is disagreeable to oneself." Mencius Vii.A.4 (Hinduism)
    2. "None of you [truly] believes until he wishes for his brother what he wishes for himself." Number 13 of Imam "Al-Nawawi's Forty Hadiths." (Islam)
    3. "And as ye would that men should do to you, do ye also to them likewise." Luke 6:31, King James Version. (Christianity)
    4. "What is hateful to you, do not to your fellow man. This is the law: all the rest is commentary." Talmud, Shabbat 31a. (Judaism)
    5. "An it harm no one, do what thou wilt" (Wicca)
    6. "What you would avoid suffering yourself, seek not to impose on others." (the Greek philosopher Epictetus -- first century A.D.)
    7. "Do not do unto others as you expect they should do unto you. Their tastes may not be the same." (the Irish playwright George Bernard Shaw -- 20th century A.D.)

     

    The one's from Wicca and George Bernard Shaw are just there for laughs.

    For the remainder, you may want to contrast how restrictive they seem. For example the Christian version is (in my opinion) a lot stronger than the one from the Talmud -- "treat others as you would want to be treated" restricts your actions both in terms of what you would like done to you and in terms of what you wouldn't like done to you; "Don't treat your fellows in a way that would be hateful to you." is leaving you a lot more freedom of action, since it only prohibits you from doing those things you wouldn't want done to yourself to others. The Hindus, Epictetus and the Jews (and the Wiccans for that matter) seem to be expressing roughly the same sentiment -- and promoting an ethic that is rather more easy for humans to conform to!

    From a logical perspective it might be nice to define open sentences

    W(x,y) = "x would want y done to him."

    N(x,y) = "x would not want y done to him."

    D(x,y) = "do y to x."

    DD(x,y) = "don;t do y to x."

    In which case, the aphorism from Luke would be

    (W(you, y) ⇒ D(others, y)) ∧ (N(you, y) ⇒ DD(others, y))

Section 2.4 -- Two-column proofs

  1. Write two-column proofs that verify each of the following logical equivalences.
    1. A ∨ (A ∧ B)    ≅    A ∧ (A ∨ B)
    2. A ∨ B    ≅    A ∨ (¬ A ∧ B)
    3. A    ≅    A ∧ ((A ∨ ¬ B) ∨ (A ∨ B))
    4. A    ≅    A ∧ (A ∨ (A ∧ (B ∨ C)))
    5. ¬ (A ∧ B) ∧ ¬ (A ∧ C)    ≅    ¬ A ∨ (¬ B ∧ ¬ C)

 

Here's the last one:

¬ (A ∧ B) ∧ ¬ (A ∧ C)  
  DeMorgan's law (times 2)
≅     (¬A ∨ ¬B) ∧ (¬A ∨ ¬C)  
  Distributive law
≅     ¬A ∨ (¬B ∧ ¬C)  

Section 2.5 -- Quantified statements

  1. There is a common variant of the existential quantifier, ∃!, if you write "∃! x,   P(x)" you are asserting that there is a unique element in the universe that makes P(x) true. Determine how to negate the sentence ∃! x,   P(x).

     

    Unique existance is essentially saying that there is exactly 1 element of the universe of discourse that makes P(x) true. The negation of "there is exactly 1" is "there's either none, or at least 2".

    Is that enough of a hint?

  2. The order in which quantifiers appear is important. Let L(x,y) be the open sentence "x is in love with y." Discuss the meanings of the following quantified statements and find their negations.
    1. ∀ x   ∃ y    L(x,y).
    2. ∃ x   ∀ y    L(x, y).
    3. ∀ x   ∀ y    L(x, y).
    4. ∃ x   ∃ y    L(x, y).

     

    1. ∀ x   ∃ y    L(x,y).
      This is a fairly optimistic statement " For everyone out there, there's somebody that they'll fall in love with."
    2. ∃ x   ∀ y    L(x,y). This one, on the other hand, says something fairly strange: " There's someone who has fallen in love with every other human being." I don't know, maybe the Dalai Lama? Mother Theresa?...

      Anyway, do the last two for yourself.

    3. ∀ x   ∀ y    L(x,y).
    4. ∃ x   ∃ y    L(x,y).

      Here's a couple of bonus questions. Two of the statments above have different meanings if you just interchange the order that the quantifiers appear in. What do the following mean (in contrast to the ones above)?

    5. ∃ y   ∀ x    L(x,y).
    6. ∀ y   ∃ x    L(x,y).
  3. Determine a useful denial of: ∀ ε>0   ∃ δ>0   ∀ x   (|x-c| < δ) ⇒ (|f(x)-l| < ε) . The denial above gives a criterion for saying limx → c f(x) ≠ l.

     

    This is asking you to put a couple of things together. The first thing is that in negating a quantified statement, we get a new statement with all the quantified variables occuring in the same order but with ∀'s and ∃'s interchanged. The second issue is that the logical statement that appears after all the quantifiers needs to be negated. Since, in this statement we have a conditional, you must remember to negate that properly (its negation is a conjunction).

    ∃ ε>0,   ∀ δ>0,   ∃ x,     (|x-c| < δ)  ∧   (|f(x)-l| ≥ ε) .

  4. A Sophie Germain prime is a prime number p such that the corresponding odd number 2p+1 is also a prime. For example 11 is a Sophie Germain prime since 23 = 2⋅ 11 + 1 is also prime. Almost all Sophie Germain primes are congruent to 5 (mod 6), nevertheless, there are exceptions -- so the statement "There are Sophie Germain primes that are not 5 (mod 6)." is true. Verify this.

     

    The exceptions are very small prime numbers. You should be able to find them easily.

Section 2.6 -- Deductive reasoning and Argument forms

  1. In the movie "Monty Python and the Holy Grail" we encounter a medieval villager who (with a bit of prompting) makes the following argument.
    If she weighs the same as a duck, then she's made of wood.
    If she's made of wood then she's a witch.
    Therefore, if she weighs the same as a duck, she's a witch.

    Which rule of inference is he using?

     

    This is what many people refer to as the transitive rule of implication. As an argument form it's known as "hypothetical syllogism."
  2. In constructive dilemma, the antecedants of the conditional sentences are usually chosen to represent opposite alternatives. This allows us to introduce their disjunction as a tautology. Consider the following proof that there is never any reason to worry (found on the walls of an Irish pub).
    Either you are sick or you are well.
    If you are well there's nothing to worry about.
    If you are sick there are just two possibilities:
    Either you will get better or you will die.
    If you are going to get better there's nothing to worry about.
    If you are going to die there are just two posibilities:
    Either you will go to Heaven or to Hell.
    If you go to Heaven there is nothing to worry about. If you go to Hell, you'll be so busy shaking hands with all your friends there won't be time to worry ...
    Identify the three tautologies that are introduced in this "proof."

     

    Look at the lines that start with the word "Either."
  3. For each of the following arguments, write it in symbolic form and determine which rules of inference are used.
    1. You are either with us, or you're against us. And you don't appear to be with us. So, that means you're against us!

       

      W ∨ A
      ¬ W
      -------------------------
      ∴ A

      This is "disjunctive syllogism."

    2. All those who had cars escaped the flooding. Sandra had a car -- therefore, Sandra escaped the flooding.

       

      Let C(x) be the open sentence "x has a car" and let E(x) be the open sentence "x escaped the flooding."

      This argument is actually the particular form of universal modus ponens: (See the final question in the next set of exercises.)

      ∀ x,   C(x) ⇒ E(x)
      C(Sandra)
      -------------------------
      ∴ E(Sandra)

      At this stage in the game it would be perfectly fine to just identify this as modus ponens and not worry about the quantifiers that appear.

    3. When Johnny goes to the casino, he always gambles 'til he goes broke. Today, Johnny has money, so Johnny hasn't been to the casino recently.
    4. (A non-constructive proof that there are irrational numbers a and b such that ab is rational.) Either √2√2 is rational or it is irrational. If √2√2 is rational, we let a=b=√2. Otherwise, we let a=√2√2 and b=√2. (Since √2√2√2 = 2, which is rational.) It follows that in either case, there are irrational numbers a and b such that ab is rational.

     

    I'm leaving the last two for you to do. One small hint: both are valid forms.

Section 2.7 -- Validity of arguments and common errors

  1. Determine the logical form of the following arguments. Use symbols to express that form and determine whether the form is valid or invalid. If the form is invalid, determine the type of error made. Comment on the soundness of the argument as well, in particular, determine whether any of the premises are questionable.
    1. All who are guilty are in prison.
      George is not in prison.
      Therefore, George is not guilty.

       

      This looks like modus tollens. Let G refer to "guilt" and P refer to "in prison"

      G ⇒ P
      ¬P
      -------------------------
      ∴ ¬G
      You should note that while the form is valid, there is something terribly wrong with this argument. Is it really true that everyone who is guilty of a crime is in prison?

    2. If one eats oranges one will have high levels of vitamin C.
      You do have high levels of vitamin C.
      Therefore, you must eat oranges.
    3. All fish live in water.
      The mackeral is a fish.
      Therefore, the mackeral lives in water.
    4. If you're lazy, don't take math courses.
      Everyone is lazy.
      Therefore, no one should take math courses.
    5. All fish live in water.
      The octopus lives in water.
      Therefore, the octopus is a fish.
    6. If a person goes into politics, they are a scoundrel.
      Harold has gone into politics.
      Therefore, Harold is a scoundrel.
  2. If we allow quantifiers and open sentences in an argument form we get arguments that are termed "universal" and "particular."

    For example

    ∀ x, A(x) ⇒ B(x)
    A(p)
    -------------------------
    ∴ B(p)

    is the particular form of modus ponens (here, p is not a variable -- it stands for some particular element of the universe of discourse).

    And,

    ∀ x, A(x) ⇒ B(x)
    ∀ x, ¬ B(x)
    -------------------------
    ∴ , ∀ x, ¬ A(x)

    is the universal form of modus tollens. Re-examine the arguments from problem (1), determine their forms (including quantifiers) and whether they are universal or particular.

     

    Hint: Only one of the arguments is a univeral form (number 4).

    Here's an analysis of number 5:

    All fish live in water.
    The octopus lives in water.
    Therefore, the octopus is a fish.

    Let F(x) be the open sentence "x is a fish" and let W(x) be the open sentence "x lives in water"

    Our argument has the form

    ∀ x,   F(x) ⇒ W(x)
    W(the octopus)
    -------------------------
    ∴ F(the octopus)

    Clearly something is wrong -- a converse error has been made -- if everything that lived in water was necessarily a fish the argument would be OK (in fact it would then be modus ponens). But that is the converse of our major premise.