Problem Set 2

Due Friday, October 11 at 1:00 pm Pacific

This second problem set explores mathematical logic and dives deeper into formal mathematical proofs. We've chosen the questions here to help you get a more nuanced understanding for what first-order logic statements mean (and, importantly, what they don't mean) and to give you a chance to practice your proofwriting. By the time you've completed this problem set, we hope that you have a much better grasp of mathematical logic and how it can help improve your proofwriting structure.

Before attempting this problem set, we recommend that you do the following:

• Familiarize yourself with the online Truth Table Tool and play around with it a bit to get a feel for the propositional connectives.
• Read the online Guide to Negations and Guide to First-Order Translations.
• Read the First-Order Translation Checklist to get a better sense for common errors in first-order logic translations and how to avoid them.

Good luck, and have fun!

Starter Files

Here are the starter files for the problems you'll submit electronically:

📦 PS2 Starter Files

Unpack the files somewhere convenient and open up the bundled project.

If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS2 $\LaTeX$ Template

Problem One: Interpersonal Dynamics:

Consider the following diagram:

If there's an arrow from a person $x$ to a person $y$, then person $x$ loves person $y$. We'll denote this by writing $Loves(x, y)$. For example, in this picture, we have $Loves(p_4, p_3)$ and $Loves(p_5, p_5)$, but not $Loves(p_4, p_1)$.

There are no “implied” arrows in this diagram. For example, although $p_1$ loves $p_3$ and $p_3$ loves $p_2$, the statement $Loves(p_1, p_2)$ is false because there's no arrow from $p_1$ to $p_2$. Similarly, even though $p_4$ loves $p_3$, the statement $Loves(p_3, p_4)$ is false because there's no arrow from $p_3$ to $p_4$.

Below is a series of first-order logic statements. Some are true, and some are false. Your task is, for each false statement, to tell us the smallest collection of arrows that need to be added to the diagram in order to make the statement true.

This problem is autograded. Download the starter files for Problem Set Two and extract them somewhere convenient. You’ll enter your answers into the file res/Interpersonal.dynamics. Specifically, do the following:

• For each true statement, answer true.
• For each false statement, tell us who needs to love whom to make the formula true. Your answer needs to use the smallest number of additional loves relations to receive full credit.

You can use the local “Run Tests” button to check your work locally, or submit to Gradescope. As with Problem Set One, you can submit as many times as you’d like; we’ll only grade your last submission.

We’ve included answers to the first three of these questions as a reference; you need to fill in the rest.

1. $Loves(p_1, p_3)$

2. $Loves(p_3, p_4)$

3. $Loves(p_1, p_2) \land Loves(p_2, p_1)$

4. $Loves(p_1, p_2) \lor Loves(p_2, p_1)$

5. $Loves(p_1, p_1) \to Loves(p_5, p_5)$

6. $Loves(p_1, p_2) \to Loves(p_4, p_3)$

7. $Loves(p_1, p_3) \to Loves(p_3, p_6)$

8. $Loves(p_1, p_4) \to Loves(p_4, p_5)$

9. $Loves(p_1, p_4) \leftrightarrow Loves(p_2, p_3)$

10. $Loves(p_1, p_3) \leftrightarrow Loves(p_5, p_5)$

11. $\forall x. \exists y. Loves(x, y)$

12. $\forall x. \exists y. Loves(y, x)$

13. $\forall x. \exists y. (x \ne y \land Loves(x, y))$

14. $\forall x. \exists y. (x \ne y \land Loves(y, x))$

15. $\exists x. \forall y. Loves(x, y)$

16. $\exists x. \forall y. (x \ne y \to Loves(x, y))$

Problem Two: Propositional Completeness

In this problem, you’ll explore some redundancies within the language of propositional logic.

This problem is autograded. Edit res/PropositionalCompleteness.proplogic with your answers. There’s information inside the file with information about how to structure your answer. Briefly, if the online Truth Table Tool can understand your answer, so can our autograder. As usual, feel free to submit as many times as you’d like; we’ll only grade your last submission.

In lecture, we covered the seven propositional connectives, which for convenience we’ve listed below:

We settled on this set of connectives because they’re convenient and expressive. However, it turns out that we could get away with fewer connectives than this.

1. Write expression equivalent to $\bot$ that does not use any connectives besides $\land$, $\lor$, $\lnot$, and $\top$. (You’re welcome to use parentheses, but do not use any variables.)

2. Write an expression equivalent to $p \to q$ that does not use any connectives besides $\land$, $\lor$, $\lnot$, and $\top$. (You’re welcome to use the variables $p$ and $q$, along with parentheses.)

3. Write an expression equivalent to $p \leftrightarrow q$ that does not use any connectives besides $\land$, $\lor$, $\lnot$, and $\top$. (You’re welcome to use the variables $p$ and $q$, along with parentheses.)

Your answers to parts (i), (ii), and (iii) of this problem show that the the four propositional connectives $\land$, $\lor$, $\lnot$, and $\top$ collectively are sufficient – the other three connectives can be rewritten purely in terms of them. However, there’s some redundancy within those four connectives, and we can express all propositional formulas just using three of them.

4. Write an expression equivalent to $p \lor q$ that does not use any connectives besides $\land$, $\lnot$, and $\top$. (You’re welcome to use the variables $p$ and $q$, along with parentheses.)

We can push this further. You can rewrite any propositional formula using just the $\to$ and $\bot$ connectives!

5. Write an expression equivalent to $\top$ that does not use any connectives besides $\to$ and $\bot$. (You’re welcome to use parentheses, but do not use any variables.)

6. Write an expression equivalent to $\lnot p$ that does not use any connectives besides $\to$ and $\bot$. (You’re welcome to use the variable $p$, along with parentheses.)

7. Write an expression equivalent to $p \land q$ that does not use any connectives besides $\to$ and $\bot$. (You’re welcome to use the variables $p$ and $q$, along with parentheses.)

   As a hint, what happens if you negate an implication?

To recap: given the $\to$ and $\bot$ connectives, you can express $\land$, $\lnot$, and $\top$. From $\land$, $\lnot$, and $\top$ you can get $\land$, $\lor$, $\lnot$, and $\top$. And from those four connectives, you can get back the original seven. Overall, any propositional formula can be expressed purely in terms of $\to$ and $\top$. Nifty!

Problem Three: Executable Logic

This problem, and the ones after it, concern worlds populated by cats, robots, and humans. Love is in the air, and it seems appropriate to pin down the group dynamics using first-order logic. Let’s assume we have the predicates

• $Person(p)$, which states that $p$ is a person;
• $Cat(c)$, which states that $c$ is a cat;
• $Robot(r)$, which states that $r$ is a robot; and
• $Loves(x, y)$, which states that $x$ loves $y$.

As a note, the $Person$, $Cat$, and $Robot$ predicates are mutually exclusive. For example, you can’t have a robot cat or a cat person. (I mean, you can have a “cat person” in the sense that you can have a person who likes cats, but not someone who is literally both a cat and a person. 😃) Additionally, you can assume that each entity in the world is either a person, a cat, or a robot. Finally, note that love is not necessarily symmetric. It’s possible for $A$ to love $B$ but not the other way around. (Alas!)

Below is a list of six first-order logic statements. Your task is to implement the six C++ functions defined in the file src/ExecutableLogic.cpp, each of which determines whether one of the first-order logic formulas is true about a set of robots, cats, and people. Each robot, cat, or person is represented using a variable of type Entity, and we’ve provided the following C++ functions to you, which mirror the four predicates given above:

bool Person(Entity p);          
bool Cat   (Entity c);          
bool Robot (Entity r);          
bool Loves (Entity x, Entity y);

Our provided starter files will run the six functions you’ll implement on some sample worlds, which you can use to test out your implementations.

1. Consider the following first-order logic formula:

   $\exists x. Cat(x)$

   Write C++ code for a function

   bool isFormulaTrueFor_partI(std::set<Entity> S)
   

   that takes in a set $S$ and returns whether the above formula is true for the entities in that set.

2. Repeat the above exercise with this first-order logic formula:

   $\forall x. Robot(x)$

3. Repeat the above exercise with this first-order logic formula:

   $\exists x. (Person(x) \land Loves(x, x))$

4. Repeat the above exercise with this first-order logic formula:

   $\forall x. (Cat(x) \to Loves(x, x))$

5. Repeat the above exercise with this first-order logic formula:

   \[\begin{aligned} &\forall x. (Cat(x) \to \\ &\quad \exists y. (Person(y) \land \lnot Loves(x, y)) \\ &) \end{aligned}\]

   It’s a lot easier to write code for this one if you use a helper function.

6. Repeat the above exercise with this first-order logic formula:

   \[\begin{aligned} & \exists x. (Robot(x) \leftrightarrow \\ & \quad \forall y. Loves(x, y) \\ &) \end{aligned}\]

Problem Four: First-Order Negations

For each of the first-order logic formulas below, find a first-order logic formula that is the negation of the original statement. Your final formula must not have any negations in it except for direct negations of predicates. For example, given the formula

\[\begin{aligned} & \forall c. (Cat(c) \to \\ & \quad \exists p. (Person(p) \land Loves(p, c)) \\ & ), \end{aligned}\]

you could give the formula

\[\begin{aligned} & \exists c. (Cat(c) \ \land \\ & \quad \forall p. (Person(p) \to \lnot Loves(p, c)) \\ & ). \end{aligned}\]

However, you couldn’t give as an answer the formula

\[\begin{aligned} & \exists c. (Cat(c) \ \land \\ & \quad \lnot \exists p. (Person(p) \land Loves(p, c)) \\ & ), \end{aligned}\]

since the inner negation could be pushed deeper into the expression.

To submit your answers, edit the file res/FirstOrderNegations.fol with your final formulas. That file contains information about how to format your answers.

We strongly recommend reading over the Guide to Negations before starting this problem.

1. Fully negate this formula:

   \[\begin{aligned} & \forall p. (Person(p) \to \\ & \quad \exists c. (Cat(c) \land Loves(p, c) \ \land \\ & \quad \quad \forall r. (Robot(r) \to \lnot Loves(c, r)) \\ & \quad ) \\ & ) \end{aligned}\]

2. Fully negate this formula:

   \[\begin{aligned} &\left( \forall x. \left(Person(x) \leftrightarrow \exists r. \left( Robot(r) \land Loves(x, r) \right)\right)\right) \\ & \quad \to \\ & \left(\forall r. \forall c. \left(Robot(r) \land Cat(c) \to Loves(r, c) \right) \right)\end{aligned}\]

   Be careful – make sure you understand how that formula is parenthesized before you try negating it.

3. Fully negate this formula:

   \[\begin{aligned} & \forall c. (Cat(c) \to \\ & \quad \exists r. (Robot(r) \ \land \\ & \quad \quad \forall x. (Loves(c, x) \leftrightarrow r = x) \\ & \quad ) \\ & ) \end{aligned}\]

4. Fully negate this formula:

   \[\begin{aligned} & \exists x. (Cat(x) \ \land \\ & \quad (\forall r. (Loves(r, x) \to Robot(r)) \lor \forall p. (Loves(p, x) \to Person(p))) \\ &) \end{aligned}\]

Problem Five: This, But Not That

Below is a series of pairs of statements about groups of cats, robots, and people. For each pair, find the absolute simplest world in which the first statement is true and the second statement is false. (By “absolute simplest,” we mean using as few entities as possible, and, of solutions with the fewest entities possible, having as few entities love each other as possible.)

To submit your answers, edit the file res/ThisButNotThat.worlds. There’s information in that file about how to specify your worlds.

Problem Six: Translating into Logic

In each of the following, write a statement in first-order logic that expresses the indicated sentence. Your statement may use any first-order construct (equality, connectives, quantifiers, etc.), but you must only use the predicates $Person$, $Robot$, $Cat$, and $Loves$.

To submit your answers, edit the file res/TranslatingIntoLogic.fol with your formulas. There’s information in that file about the expected format for your answers.

Please read the Guide to Logic Translations before starting this problem.

1. Write a statement in first-order logic that says “robots do not love.” (How sad!)

   As a reminder, love is considered directional. Even if robots do not love, it’s possible that people or cats might love robots. For example, I could love my Roomba even if it feels nothing toward me. 😃

2. Write a statement in first-order logic that says “each robot loves every cat, but no cat loves any person.”

3. Write a statement in first-order logic that says “each cat only loves itself.” (Okay, I’m not that cynical about cats. But it’s still a good exercise to translate this statement!)

4. Write a statement in first-order logic that says “if you pick a person, you’ll find that they love a cat if and only if they also love a robot.”

   Watch your operator precedence.

5. Write a statement in first-order logic that says “each person loves exactly two cats and nothing else.” To clarify, each person is allowed to love a different pair of cats.

6. Write a statement in first-order logic that says “no two robots love exactly the same set of cats.”

   As a reminder, you're restricted to just using the predicates we provided you, so you can't use the $\in$ predicate or the $Set$ predicate like we did in lecture. You'll need to find another way to express this idea. Check the Guide to Logic Translations' section on set theory.

Looking for a good read on the theme of people, robots, pets, and love? Check out Ted Chiang’s novella The Lifecycle of Software Objects, which explores these ideas in depth. 😃

Problem Seven: All the Everys and Alls

Many programming languages provide a function that takes as input a group of items and some predicate, then returns whether the predicate is true for all items in the group. For example, JavaScript has Array.prototype.every, which can be used like this:

function isOdd(n) {
    return n % 2 == 1;
}

[1, 3, 5].every(isOdd)  // true, all these numbers are odd
[1, 2, 3].every(isOdd)  // false, 2 is not odd
[1      ].every(isOdd)  // true, this one number is odd
[2      ].every(isOdd)  // false, this one number is not odd
[       ].every(isOdd)  // true, see below.

The last line of the above code sample highlights an interesting detail: if you use every on an empty list of values, then every returns true regardless of what predicate is provided.

You might think this is just a quirk of JavaScript, but this same behavior can be found in dozens of other languages. For example, C++'s ranges::all_of, C♯'s Enumerable.All, Haskell's all, Ruby's all?, Python's all, Kotlin's all, Swift's allSatisfy(_:), and Common Lisp's every all have the same behavior.

There is a concept we covered in lecture that explains why this behavior is the correct way for this function to handle the empty list (and why so many different languages define their functions similarly). What concept is this? Briefly explain your answer; we're looking for something one or two sentences long.

Problem Eight: Yablo's Paradox

A logical paradox is a statement that isn’t true and isn’t false. One of the simplest paradoxes is the Liar's paradox, which is the following:

$(P)$: Statement $(P)$ is false.

If statement $(P)$ is true, then by its own admission statement $(P)$ is false – a contradiction! That means that statement $(P)$ isn't true.

On the other hand, suppose that statement $(P)$ is false. Then we know that “statement $(P)$ is false” is false, meaning that statement $(P)$ is true – a contradiction! This means that statement $(P)$ isn't false either.

Since statement $(P)$ isn't true and isn't false, it's a paradox.

Paradoxes often arise as a result of self-reference. In the Liar's Paradox, the paradox arises because the statement directly refers to itself. However, it's not the only paradox that can arise from self-reference. This problem explores a beautiful, subtle paradox called Yablo's paradox.

Consider the following collection of infinitely many statements numbered $S_0, S_1, S_2, \dots$, where there is a statement $S_n$ for each natural number $n$. These statements are ordered in a list as follows:

More generally, for each $n \in \mathbb{N}$, the statement $(S_n)$ is

$(S_n)$: All statements in this list after this one are false.

Surprisingly, the interplay between these statements makes every statement in the list a paradox.

1. Prove, by contradiction, that there does not exist a natural number $n$ where statement $(S_n)$ is true.

   Something to ponder: how do you negate a universally-quantified statement?

2. Prove, by contradiction, that there does not exist a natural number $n$ where statement $(S_n)$ is false.

Your results from parts (i) and (ii) collectively establish that every statement in the list above is paradox, since none of them are true and none of them are false.

Now, consider the following modification to this list. Instead of infinitely many statements, suppose that there are “only” $10,000,000,000$ statements. Specifically, suppose we have these statements:

There's still a lot of statements here, but not infinitely many of them. Interestingly, these statements are all perfectly consistent with one another and do not result in any paradoxes.

3. For each statement in the above list, determine whether it's true or false and explain why your choices are consistent with one another.

Going forward, don't worry about paradoxes in CS103. We won't talk about any more statements like these. 😃

Problem Nine: Square and Triangular Numbers

A natural number $n$ is called a square number when there exists a natural number $k$ where $n = k^2\text.$ The first few square numbers are $0, 1, 4, 9, 16, 25, \ldots \text.$ Intuitively, the square numbers count the number of squares in a square grid:

A natural number $n$ is called a triangular number when there exists a natural number $k$ where $n = \frac{k(k+1)}{2}\text.$ The first few triangular numbers are $0, 1, 3, 6, 10, 15, \ldots \text.$ Intuitively, the triangular numbers count the number of squares in these figures:

Prove for all natural numbers $n$ that $n$ is a triangular number if and only if $8n + 1$ is a square number. There's a lovely geometric intuition for this shown here:

Problem Ten: Tournament Champions

A tournament is a contest among $n \ge 0$ players. Each player plays exactly one game against each other player, and either wins or loses the game (let's assume that there are no draws). We can visually represent a tournament by drawing a circle for each player and adding arrows between pairs of players to indicate who won each game. For example, consider this tournament:

In this tournament, player $A$ beat player $E$, but lost to players $B$, $C$, and $D$.

Now, a new definition. A tournament champion is a player $c$ where, for each player $p$ that $c$ lost to, there is a player $q$ where $c$ won against $q$ and $q$ won against $p$.

In the tournament shown above, player $B$ is a champion: she won against $A$, $C$, and $D$, and although she lost to $E$, she won against $D$, who in turn won against $E$. Player $C$ is also a champion: she won against $A$, $D$, and $E$, and the one player she lost to ($B$) is covered because $C$ won against $E$, who in turn won against $B$. Player $A$, however, is not a tournament champion. To see this, $A$ didn’t win against $C$, nor is there any player who $A$ won against who in turn won against $C$.

1. Is player $D$ a tournament champion? How about player $E$? No justification is required.

   You might have an intuition for what a tournament champion is, but to determine the answers to these questions, you’ll have to look back at the definition.

Here’s an amazing fact about tournaments.

2. Let $T$ be an arbitrary tournament and $c$ be a player in that tournament. Prove the following statement: if $c$ won more games than anyone else in $T$ or is tied for winning the greatest number of games, then $c$ is a tournament champion in $T$.

   Remember that proofwriting heavily involves leveraging definitions. Intuitively, it makes sense that someone who won the most games did the best in a tournament, but that’s not what’s being asked here. Instead, you’re asked to show that if someone won the most games (or tied for winning the most games), then they specifically meet the criteria described above that characterize a tournament champion.

   A great question to ponder – what has to happen for someone to not be a tournament champion? Don’t guess based on your intuition; negate the definition of a tournament champion and see what happens. You might want to draw a picture of what happens in this case.

A corollary of the result from (ii) is that every tournament with at least one player has at least one tournament champion – pick someone who won the most games or is tied for winning the most games.

The result you proved in part (ii) of this problem is noteworthy for several reasons. First, this is a fundamental result about tournaments – many aspects of tournaments can be better understood by looking at its champions. Second, it’s an example of a style of proof called a proof by extreme case. In a proof of that sort, you pick some “extreme” object, usually the biggest or smallest object of some type, then prove that it has some property. Here, you proved that the “winningest” player must be a tournament champion. Keep this idea in mind for the future – you’ll likely get some more mileage out of it!

Tournaments have many applications in computational complexity theory and in the emerging field of computational social choice theory. A former CS103 TA, Michael Kim, studied them extensively when doing his PhD here in computer science!

Optional Fun Problem: Insufficient Connectives

As you saw earlier on this problem set, every propositional logic formula could be written in terms of just $\to$ and $\bot$. However, you cannot express every possible propositional logic formula using just the $\leftrightarrow$ and $\bot$ connectives.

Prove why not.