Extra 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.

"Given that I know ($P$ OR $Q$) and I know ($P$ OR $R$), I can deduce $P$ OR ($Q$ AND $R$)."

$P=$ "The sun is shining."
$Q=$ "It is nighttime."
$R=$ "It is dark outside."
"I know that the sun is shining or it is nighttime, and I know that the sun is shining or it is dark outside. So I know that the sun is shining or it is nighttime and dark outside."

Strategy for proof:

• We have 2 ORs on the left-hand-side that will need to be eliminated.
• There is an OR and an AND that may need to be introduced.
• Idea: eliminate the first of the LHS ORs $(P\vee Q$). We get $P$ on one side, which will let us OR-intro the full RHS expression. For the $Q$ on the other side of that OR, we can use the other LHS OR $(P\vee R)$ to help!

"Given that $P$ implies $Q$ implies $R$, we can prove that $P$ and $Q$ together imply $R$."

$P=$ "I am not paying attention."
$Q=$ "The ice is slippery."
$R=$ "I will fall down."
"I know that if I am not paying attention, it means that if the ice is slippery then I will fall down. So I can deduce that if I am not paying attention when the ice is slippery, then I will fall down."
"I know that if I am not paying attention, then I will fall down if the ice is slippery. So I can deduce I will fall down if I am not paying attention when the ice is slippery."

Strategy for proof:

• There are 2 arrows on the LHS, but they can't be eliminated yet.
• But there is an arrow on the RHS out the outer level that can be introduced. So introduce that arrow by assuming $(P\wedge Q)$.
• Now using $\wedge$-elim will give us $P$ and $Q$, which will let us eliminate the LHS arrows to get $R$.
• We assumed $(P\wedge Q)$ and got $R$, so we can finally introduce that RHS arrow!

"Given that $P$ implies $Q$ or $R$, I can deduce that either $P$ implies $Q$, or $P$ implies $R$."

$P=$ "It is nighttime."
$Q=$ "The sun has set."
$R=$ "Pigs can fly."
"I know that if it is nighttime, then either the sun has set or pigs can fly. Then I can deduce that either (i) if it is nighttime, then the sun has set; or (ii) if it is nighttime, then pigs can fly."

Strategy for proof:

• We can't do any eliminations at the start because we can't use the arrow on the LHS yet.
• The outermost operation on the RHS is an OR, so we will be using OR intro somewhere. How? We need to show the left or right side of that OR.
• Those both have arrows, so let's target an arrow intro. Oh look: they both require assuming $P$!
• That will let us elim the LHS arrow, giving us $(Q\vee R)$. An OR elim will be next.
• In one case, we'll get $P\to Q$. In the other case, we'll get $P\to R$. Those aren't the same...
• But wait! Our goal is to OR these together. So in each case, we can use an OR-intro to get to the goal at the end!