Demonstration Exercise 3

Problem 1: Down By More Than One

Consider the following recursive Python definitions:

def is_even(n):
    if n == 0:
        return True
    elif n == 1:
        return False
    else:
        return is_even(n-2)

def iterate(f, x, n):
    if n == 0:
        return x
    else:
        return iterate(f, f(x), n-1)

For this problem, you may take the shortcut of evaluating any function call directly to the expression that it returns in a single step.

First prove the following auxiliary claim about even:

Then, consider the following claim about iterate:

In a sentence or two, describe at a high-level why this claim is correct.

Finally, formally prove this claim using the auxiliary claim.

Problem 2: Translation

Consider the following parameterized atomic propositions:

• $A(x,y,z)=$ "$x$ knows that $y$ owes $z$ money"
• $B(x,y)=$ "$x$ owes $y$ money"
• $D(x,y)=$ "$x$ will pay $y$"
• $C(x)=$ "$x$ is an honest person"

First, translate each of the following English propositions into a formal propositional statement, using the parameterized atomic propositions above. Make sure to make maximal use of the logical connectives, in particular, negation, in your formal statements.

• Either Sam owes the store money or the store owes Sam money.
• If Henry knows that Io owes Mateo money and Io is honest, then Io will pay Mateo.
• For all people $x$, if $x$ is not honest, then $x$ will not pay Tina.
• There exists people $x$ and $y$ such that for any person $z$, $x$ owes $y$ money but $z$ does not know that $x$ owes $y$ money.

Now consider the following formal propositional statements. Give English propositions that are equivalent to these formal statements.

• $D(\text{"Laura"},\text{"Roberto"})\to C(\text{"Laura"})$.
• $\forall x,y.C(x)\to D(x,y)$.
• $\forall x.\neg C(x)\to \exists y,z.A(y,x,z)\to \neg D(x,z)\wedge D(x,y)$.

Problem 3: Objection!

A logical fallacy is a misconception due to an erroneous step of logical reasoning. In this problem, we'll explore some common logical fallacies, their formal representation in propositional logic, and their refutation.

For each of the propositions below:

• Translate the proposition into a formal propositional statement, representing atomic propositions with fresh propositional variables. Make sure (a) state which variables correspond to which atomic propositions and (b) make maximal use of the logical connectives in your formal statement.
• In a few sentences, argue why the resulting formal proposition is not provable using your intuition of the semantics of the logical connectives of propositional logic.

(Hint: recall that logical implication $(\to )$ captures the idea that we assume that a proposition is true and go on to prove another proposition true using that assumption. Whenever a situation describes a proposition that you are supposed to assume is true, you should use implication to represent this fact.)

1. If I buy you a present, you will like me. I did not buy you a present, therefore you will not like me.
2. We know that this drug will cure cancer or kill the patient. We observe that the drug cures the patient. Therefore, the drug will not kill the patient.
3. Suspect A claims that suspect B was the thief. We showed that suspect A is a liar. Therefore, we know that suspect B is not a thief.
4. It has been proven that if you run, you will get into shape. I got into shape, therefore, I must have run.
5. I claim that there are mole people underground that are plotting to take over the world. There exists no evidence that implies there are not mole people underground. Therefore, my claim about mole people is correct.