Even More Logic Practice!

In today's brief lab, we'll continue practicing the skill of applying the rules of natural deduction to write rigorous, low-level proofs.

Note: this "lab" is not due, but will be good practice as you prep for the exam on Friday.

Problem: Logic Practice

For each claim:

• In a sentence, describe what the claim is saying. Your description should be in the rough form "under assumptions ... we must show that ... ." You can reference the atomic propositions in the claims directly in your description, i.e., you don't need to instantiate the proof state into a real-world context.

• Now instantiate the claim using real-world statements like "the sun is shining" or "it is cold outside" or "pigs can fly". Try to pick statements that make sense in the context of the claim itself, what is being assumed, and what you are trying to prove.

• Finally, give a rigorous, natural deduction-style proof of the claim.

Strategy for proof:

• We have 2 ORs to eliminate and 1 arrow to introduce.
• We can actually do these in pretty much any order and the proof will work.
• Let's start with the arrow and assume $P$.
• When we go to elim the $\neg P\vee Q$, we see that the $P$ and $\neg P$ will lead to absurdity and give us $R$.
• In the $Q$ branch of the OR, we will go to elim the other OR, $\neg Q\vee R$.
• In the $\neg Q$ branch of that OR, the $Q$ and $\neg Q$ will lead to absurdity to give us $R$. And the $R$ branch gives us $R$.
• We then just need to close everything out, finishing the two OR eliminations, and finally finishing the arrow introduction.

Strategy for proof:

• We have an arrow to eliminate and nothing to introduce.
• But we can't eliminate the arrow yet because that requires $\neg P$.
• We are stuck! We will need to pull something out of thin air... But what?
• The Law of the Excluded Middle is always Provable!
• We need either $P$ (our goal) or $\neg P$ (to use for the arrow elimination). Use the Law of the Excluded Middle to give us $P\vee \neg P$.
• Now OR elimination will give us $P$ in one branch. The other branch gives us $\neg P$, which leads to $\neg Q$, which leads to absurdity, giving us $P$ anyway.

There are actually a couple ways to approach this problem. Two proofs are shown below!

Strategy for proof 1:

• We have an AND to introduce on the RHS, so we need to show both parts of the AND, $R$ and $S$.
• To get $R$, we can use the $P$ from $P\wedge Q$ with the $\neg P\vee R$ to do OR elimination. $R$ will come from either branch (since the first will be absurdity).
• To get $S$, we can use the $Q$ from $P\wedge Q$ with the $\neg Q\vee S$ to do OR elimination. $S$ will come from either branch (since the first will be absurdity).
• This gives us both the $R$ and $S$ to introduce the final AND.

Strategy for proof 2:

• We can use the $P$ with the first branch of $\neg P\vee R$ to get absurdity, and conclude our goal of $R\wedge S$.
• But, the other branch just gives us $R$. So how to get the $S$ as well?
• Within this branch, we can go to eliminate the other OR, $\neg Q\vee S$.
• The $\neg Q$ branch will give absurdity and again let us conclude our goal $R\wedge S$.
• The $S$ branch gives us our $S$. Since we are already in an $R$ branch from the first OR, we now have $R$ and $S$, so we can introduce the AND in this context to get $R\wedge S$.
• Then we just close off the OR eliminations to get our goal!