Lab: Modeling with Logic

Problem: Back and Forth

Translate each of the natural language propositions into formal logical propositions. Ensure in your answer that you (1) identify the atomic propositions and assign them to variables and (2) write your formal proposition in terms of these variables. Make sure you maximally translate the proposition using as many of the connectives introduced in the reading. In particular, make sure you use the negation logical operator when appropriate in your answers.

1. It rained this morning and it will be sunny this afternoon.
2. If I am forced to stay in-doors this week, I will play Genshin Impact, have fun, and become poor.
3. If I either eat Taco Bell or McDonalds, I will either become swoll, or I will not survive the night.
4. If Jan and Bob both work at the company, then Jan certainly works more than Bob.

Now, consider the following parameterized atomic propositions:

• $A(x)$ = "I love $x$."
• $B(x)$ = "$x$ barfs."
• $C(x)$ = "I own $x$."
• $D(x)$ = "I'm sending away $x$."

As well as their parameterized versions:

Translate each of the formal logical propositions to natural language propositions. Ensure that your natural language propositions clearly indicate the explicit grouping found in the formal logic propositions.

1. $A(\text{cats})\wedge B(\text{cats})$.
2. $A(\text{cats})\to \neg C(\text{dogs})$.
3. $A(\text{cats})\vee (B(\text{cat})\to C(\text{dog}))$.
4. $B(\text{my cat})\to D(\text{my cat})\wedge \neg A(\text{my cat})$.
5. $A(\text{dogs})\to C(\text{dogs})\wedge D(\text{cats})$.

Note that $(\wedge )$ and $(\vee )$ have higher precedence than $(\to )$. So, for example,

$$B(\text{my cat})\to D(\text{my cat})\wedge \neg A(\text{my cat})$$

is equivalent to

$$B(\text{my cat})\to (D(\text{my cat})\wedge \neg A(\text{my cat})).$$

Problem: Warm-up

In our examples from the reading relied heavily on non-mathematical, intuitive propositions to convey the meaning of quantified propositions. Now we'll consider translating propositions of a more mathematical nature between formal, symbolic statements and English.

First, translate each of the following formal statements regarding integers into English and for each, explain in a sentence or two why they are true.

• $\exists x.\exists y.x-y=0$.
• $\forall x.\exists y.y>x$.
• $\forall x.\forall y.x\ge y\wedge y\ge x\to x=y$.

Now, consider the following theorems taken from Fortnow's paper on his Favorite Ten Complexity Theorems of the Past Decade. Computational complexity theory is a branch of computer science concerning the resource usage (both time and space) of algorithms. While we do not have the background to fully understand what each of Fortnow's theorems (i.e., main propositions) says, we can certainly translate their logical intent. For each of these theorems, identify relevant atomic propositions and predicates and give a formal statement of the theorem maximizing your use of our logical connectives.

• Theorem 1: For any one-way function, there exists a pseudorandom generator constructed from that one-way function.
• Theorem 2: There are no sparse sets hard for $\text{NP}$ via polynominal-time bounded truth-table queries unless $\text{P}=\text{NP}$. (Hint: to deal with "unless," think about what it means and try to rewrite the theorem in terms of a "if...then" rather than "unless.")

Problem: Quantification and Negation

The negation of propositions can be tricky to reason about. De Morgan's laws:

• $\neg (p_1\wedge p_2)\equiv \neg p_1\vee \neg p_2$
• $\neg (p_1\vee p_2)\equiv \neg p_1\wedge \neg p_2$

Remind us that negation doesn't simply "distribute into" connectives like conjunction and disjunction. Instead, De Morgan's laws say we "distribute/factor the negations and flip the signs." Are there similar equivalences for quantifiers? We'll answer this question by using real-world examples and our intuition to gain understanding.

Consider the following variants of propositions involving universal and existential quantification and negation both inside and outside of the quantifier.

• $P_1=\forall x.A(x)$.
• $P_2=\exists x.A(x)$.
• $P_3=\neg \forall x.A(x)$.
• $P_4=\neg \exists x.A(x)$.
• $P_5=\forall x.\neg A(x)$.
• $P_6=\exists x.\neg A(x)$.

1. Come up with a concrete example predicate $A(x)$ to use for this exploration. For each of these propositions above, translate the proposition into English. Try to choose a predicate that is both memorable and simple to reason about.
2. Using your English translations as a guide, decide which pairs of propositions are equivalent.
3. For each pair of propositions you believe are equivalent, write a sentence or two justifying the equivalence, using your concrete example to explain why it holds.

Problem: Thinking About Proof

Thinking ahead, we've used first-order logic to explore the extends of what we can express as far as propositions go. However, we are studying logic in this course to derive a set of rules for proving a proposition. Because our propositions are defined inductively, i.e., as a finite set of cases, our rules for proving a proposition also follow by case analysis on the different cases.

For each possible form of a proposition given in the reading, describe at a high-level how you would go about proving that proposition in a few sentences per form. Use a concrete example of a proposition in English for each case to describe your process. For example, for conjunction $p_1\wedge p_2$, I would instantiate $p_1$ and $p_2$ to concrete propositions, e.g.,

• $p_1$ = "The sky is rainy."
• $p_2$ = "It is dark outside."

And then explain how I would prove $p_1\wedge p_2$. Use your example and your intuition about what each logical connective means to arrive at your process. In tomorrow's reading and lab, we'll firm up your intuition with concrete rules and then look at how we express these rules precisely using mathematical notation.