Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: mathematics

Topic: Exercises in Deductive Reasoning and Logical Connectives

Jacob Zelko (Apr 10 2023 at 16:36):

Hi folks!

Working through Velleman's text, How To Prove It, and had a few questions on solutions I developed for some of the practice problems I worked through. Here are some of the questions I worked through; would anyone be willing to comment on my answers if I was on the right track or not? Thank you!

Is the following expression a well-formed formula: $(P \land Q)(P \lor Q)$

I said no because that does not mean anything. You can't multiply these statements!

Let $S$ stand for the statement "Steve is happy" and $G$ for "George is happy". What English sentence is represented by the following expression: $S \lor [G \land (\neg{S} \lor \neg{G})]$?

I had trouble with this but my best shot was saying "Steve is happy or George is happy and Steve nor George are happy." But it doesn't quite make sense to me with the phrase "Steve nor George are happy" as it seems to contradict the $G \land$ term. Any thoughts?

Let $S$ stand for the statement "Steve is happy" and $G$ for "George is happy". What English sentence is represented by the following expression: $[S \lor (G \land \neg{S})] \lor \neg{G}$?

I felt somewhat better about this one but it was still tricky. I said, "Steve is happy or George is happy and Steve is not happy, or George is not happy." What I struggled with is if the grammar is correct here. I think it is due to the commas but am not sure I broke the question.

Identify the premises and conclusions of the following deductive arguments and analyze their logical forms. Do you think the reasoning is valid?

1) Either John or Bill is telling the truth. Either Sam or Bill is lying. Therefore, either John is telling the truth or Sam is lying
2) Either sales go up and the boss will be happy, or expenses will go up and the boss won't be happy. Therefore, sales and expenses will not both go up.

For 1) I said to let $J$ be that John tells the truth, $B$ that Bill tells the truth, and $S$ be that Sam tells the truth. Analyzing each of the statements, I thought it went like:

1) $J\lor B$
2) $\neg{S} \lor \neg{B}$
3) $J \lor \neg{S}$

With the last step being the conclusion. I did not think that it was valid as John telling the truth doesn't imply that Sam has to be a liar

For 2), this was a struggle (Velleman even said he expected students to struggle here). I said to let $S$ be sales go up, $B$ that boss is happy, and $E$ that expenses go up. Analyzing each statement I thought it went like this:

1) $(S \land B) \lor (E \ \land \neg{B})$
2) $B \land (S \land E)$

I was really stuck on how to interpret this as it doesn't feel valid as the conclusion feels paradoxical and logically inconsistent -- therefore, my answer was that it was invalid.

Let me know if I can add clarification anywhere -- thanks folks!

~ jz

John Baez (Apr 10 2023 at 17:15):

Jacob Zelko said:

Let $S$ stand for the statement "Steve is happy" and $G$ for "George is happy". What English sentence is represented by the following expression: $S \lor [G \land (\neg{S} \lor \neg{G})]$?

I had trouble with this but my best shot was saying "Steve is happy or George is happy and Steve nor George are happy." But it doesn't quite make sense to me with the phrase "Steve nor George are happy" as it seems to contradict the $G \land$ term. Any thoughts?

I guess one big question is whether the book is expecting you to use the laws of logic (e.g. classical boolean logic of the sort embodied by truth tables) to simplify these statement, or simply to translate the statements into an English sentence.

If the latter, I'd say "Either Steve is happy or else this: George is happy yet either Steve or George is unhappy." It's not a sentence people would actually say, but it's a fun challenge to translate complex logical formulae into English. "Either" and "neither" often serve as left parentheses.

John Baez (Apr 10 2023 at 17:18):

I don't think your "... and Steve nor George are happy" is good. First, in English I don't think we ever say things of the form "and S nor G". We can say

... and neither S nor G.

... and neither S nor G

but these mean $\ldots \wedge (\neg S \wedge \neg G)$.

John Baez (Apr 10 2023 at 17:20):

But you are trying here to say $\ldots \land (\neg{S} \lor \neg{G})$. I'd say this as "... and either not S or not G"

John Baez (Apr 10 2023 at 17:24):

In real life I might use the laws of Boolean logic to simplify this expression to $... \wedge \neg( S \wedge G)$. Then I could say "... and not both S and G".

John Baez (Apr 10 2023 at 17:26):

Or even better, "... but not both S and G".

John Baez (Apr 10 2023 at 17:27):

Then I get "Either Steve is happy or else this: George is happy but not both Steve and George are happy".

John Baez (Apr 10 2023 at 17:27):

But in real life I'd use the laws of logic to simplify this statement even more!

John Baez (Apr 10 2023 at 17:28):

For example, "Either Steve is happy or only George is happy".

(Here "only George is happy" is how people would say "only George but not Steve is happy".)

Mike Shulman (Apr 10 2023 at 17:39):

I think Velleman wants the reader to just translate in this case, not simplify.

John Baez (Apr 10 2023 at 17:50):

Okay, then we have to accept that we'll get awkward-sounding sentences.

Mike Shulman (Apr 10 2023 at 18:29):

Yeah. I don't generally assign those exercises for that reason.

Evan Washington (Apr 10 2023 at 19:12):

For the questions about validity, always remember to go back to the definitions. An argument is invalid if there is a way to make the premises true and the conclusion false. For (1), if the conclusion is false, then $J$ must be false and $\neg S$ must be false, as that's the only way a disjunction can be false. But if the premise $J \lor B$ is true and $J$ is false, then $B$ must be true! (This is called disjunctive syllogism). But if $B$ is true, then $\neg B$ is false. So both $\neg B$ and $\neg S$ are false, but that cannot be if $\neg S \lor \neg B$ is true. So what can we say about the argument now? Is it valid?

For (2) check again that you've translated these correctly. Where did the $B$ come from in the second sentence? And (unlike me!) can you think of a way to make the premise true while the conclusion is false?

Jacob Zelko (Apr 11 2023 at 15:06):

@John Baez , ah! This makes way more sense now. I was honestly stumbling over my English grammar and to @Mike Shulman ‘s point, I was more struggling with the awkward sounding grammar that I was mentally trying to munge through. In this situation, starting the phrasing with the “Either…. Or this:” structure was such a useful clarification mechanism for me. I’m about to relearn all the fun laws of logic (De Morgan’s Law, Idempotency, etc.) so going forward, I’ll be looking to simplify/reduce these logical statements

Jacob Zelko (Apr 11 2023 at 15:07):

Also am learning truth tables — now that is incredibly useful!

Jacob Zelko (Apr 11 2023 at 15:12):

Additionally, I remember learning truth tables back in my secondary school several years ago. It’s nice to revisit the concept as I recall having fun with it in the past

Jacob Zelko (Apr 11 2023 at 20:32):

@Evan Washington , just got back to a computer -- couldn't easily answer your thoughts from my phone! For your point about the first validity question, let me rework through this question as you are entirely right. I forgot my basics on the point about "a way to make the premises true and the conclusion false". I just relearned not only truth tables but also some of the fundamental rules. You are entirely right though -- let me see if I can regenerate what you are saying.

For the second question, I thought it made sense to consider $B$ a separate phrase from sales and expenses. Why wouldn't that make sense? Does it make sense just to have an $S$ for sales and an $E$ for expenses? I need to spend a bit more time retrying this problem again.

Jacob Zelko (Apr 11 2023 at 20:32):

That said, thank you so much for your comments! Very much appreciated!

Jason Erbele (Apr 11 2023 at 20:35):

Evan Washington said:

For (2) check again that you've translated these correctly. Where did the $B$ come from in the second sentence?

Agreed. $B$ doesn't belong in $B \land (S \lor E)$

And informally, we might reason like this: Either the boss will be happy, or he won't. On the one hand, suppose the boss is happy. Then either sales go up and the boss is happy, or expenses go up and the boss isn't happy. But the boss is happy! So it can't be that expenses went up. And so it can't be that both expenses went up and sales went up. On the other hand, suppose the boss isn't happy. Then either sales go up and the boss is happy, or expenses go up and the boss isn't happy. But the boss isn't happy, so it can't be that sales went up. And so it certainly can't be that both expenses went up and sales went up. So in either case, it cannot be that both expenses go up and sales go up.

I disagree with this informal reasoning – you appear to be using the exclusive or. I would be surprised if exclusive or were introduced this early (before De Morgan's Laws, for instance).

Jason Erbele (Apr 11 2023 at 20:40):

And just for clarity, using $B$ to represent "The boss is happy" is perfectly fine. Otherwise you have the sentence "The boss is happy" in your formulas instead of the symbol $B$.

Evan Washington (Apr 11 2023 at 21:10):

Jacob Zelko said:

For the second question, I thought it made sense to consider $B$ a separate phrase from sales and expenses. Why wouldn't that make sense? Does it make sense just to have an $S$ for sales and an $E$ for expenses? I need to spend a bit more time retrying this problem again.

It does make sense to do that. What I'm saying is $(s \land b) \lor (e \land \neg b)$ is a correct rendering of the first sentence but $b \land (s \land e)$ is not a correct rendering of the second. To help you along, if I were to translate the formula you wrote back into English, I would write it as: "The boss is happy, and sales go up, and expenses go up." That seems different from "The sales and expenses will not both go up," doesn't it?

Evan Washington (Apr 11 2023 at 21:22):

Jason Erbele said:

I disagree with this informal reasoning – you appear to be using the exclusive or. I would be surprised if exclusive or were introduced this early (before De Morgan's Laws, for instance).

I don't think I was using exclusive or. Rather, I was trying to mimic the argument patterns we have for reasoning with inclusive disjunctions.

The first was disjunction elimination. For non-logicians, this is just a proof by cases! If I have $p \lor q$ and I want to conclude $r$, then it suffices to show that I can conclude $r$ from just $p$ and that I can conclude $r$ from just $q$. This argument pattern is valid even if both $p$ and $q$ are in fact true. (I was applying this argument to $B \lor \neg B$.)

The second was disjunctive syllogism: if $p \lor q$ is true but $p$ is false, then it must be that $q$ is true. (I was applying this argument to $(S \land B) \lor (E \land \neg B)$. This is not the same as reasoning that if we have $p \lor q$ and $p$ is true then $q$ must be false, which is what happens with exclusive disjunction.

Jason Erbele (Apr 11 2023 at 21:42):

The exclusive or usage is, for example, in the bolded portion below. "The boss is happy" means the first part of the disjunction is automatically true, making the entire disjunction true, regardless of whether expenses go up.

On the one hand, suppose the boss is happy. Then either sales go up and the boss is happy, or expenses go up and the boss isn't happy. But the boss is happy! So it can't be that expenses went up.

Jason Erbele (Apr 11 2023 at 21:43):

It might not exactly be using XOR, but the outcome is similar.

Jason Erbele (Apr 11 2023 at 21:53):

I'm sorry. I'm being a bit sloppy here. The first part of the disjunction in this first case is not true unless sales go up. Regardless, concluding $\lnot E$ does not follow.

Evan Washington (Apr 11 2023 at 22:20):

Jason Erbele said:

I'm sorry. I'm being a bit sloppy here. The first part of the disjunction in this first case is not true unless sales go up. Regardless, concluding $\lnot E$ does not follow.

No, I'm sorry, I'm the one being sloppy here! I'll edit my first comment to correct the mistake. And for perspicuity: I should have taken my own advice, and considered the very definition of validity. There is a way for the premise to be true while the conclusion is false. (Well, there are two ways!)

John Baez (Apr 12 2023 at 18:36):

Jacob Zelko said:

I’m about to relearn all the fun laws of logic (De Morgan’s Law, Idempotency, etc.) ...

Only the fun laws, not the boring laws like $P \implies P$. :upside_down:

By the way, if you want to see a really fun law of logic, check out Peirce's law. It's only true classically, not intuitionistically. (So, you can verify it using truth tables if you want.)

John Baez (Apr 12 2023 at 18:37):

Here's an example. Suppose your friend says "If working hard implies I'll get the job done, then I'll be working hard". According to Peirce's law, this implies he'll be working hard!

John Baez (Apr 12 2023 at 18:38):

:crazy:

Mike Shulman (Apr 12 2023 at 18:43):

I think that example is a bit misleading. If your friend is named X, then the conclusion depends on "X will be working hard" and "X will get the job done" being fixed statements with definite truth values, so in particular in all their occurrences they must refer to a specific time or interval and a specific job. So for instance if they are "X will be working hard tomorrow" and "X will get the report done", then in particular the hypothesis of X's statement is "if I will be working hard tomorrow, then I will get the report done". I think that isn't really how our mind usually interprets a statement like "working hard implies I'll get the job done" -- we usually think of that as implicitly universally quantified, more like "for any job, working hard on that job implies I'll get that job done" -- and that mismatch is what makes the example sound counterintuitive.

John Baez (Apr 12 2023 at 18:54):

Hmm, I think Peirce's law sounds counterintuitive no matter what. Say your friend says "If this particular sandwich being a turkey sandwich implies that I will eat it, then I will eat it." We can conclude (classically) that he will definitely eat it.

John Baez (Apr 12 2023 at 18:55):

We can work through this by thinking a bit, but I don't think it's a conclusion most folks would instantly make, even devoutly classical folks.

John Baez (Apr 12 2023 at 18:56):

(I suspect a lot of folks aren't as classical in real life as they are when doing math.)

Mike Shulman (Apr 12 2023 at 19:10):

I'm not necessarily saying I disagree, but to play devil's advocate a little, I doubt anyone could instantly make any kind of conclusion from a statement like "If this particular sandwich being a turkey sandwich implies that I will eat it, then I will eat it", just because its logical structure is much more complicated than anything we say in ordinary life, kind of like "Either Steve is happy or else this: George is happy yet either Steve or George is unhappy."

Mike Shulman (Apr 12 2023 at 19:12):

So it's natural to expect that presented with a sentence like that, we would have to think a bit to work out its meaning. And if someone believes that either he'll eat the sandwich or he won't, and that a false statement implies anything, then when they work it out they'll reach Pierce's conclusion.

Mike Shulman (Apr 12 2023 at 19:14):

I also think another part of it is that in everyday life we very rarely use a truth-functional implication. Most often when we say "if X then Y" there is an implicit universal quantifier. So if-then statements without such a universal quantifier almost always seem counterintuitive. This is true in constructive mathematics too, e.g. $A \to (B\to A)$.

John Baez (Apr 12 2023 at 19:27):

Agreed. Nonetheless, speaking strictly for myself, I found Peirce's law shocking until I wrote about it, because of its "something from nothing" flavor.

John Baez (Apr 12 2023 at 19:29):

Another reason to care about Peirce's law is that it's part of a convenient set of axioms for the purely implicational fragment of classical propositional logic.