In this lab, we’ll work on developing our proficiency in developing formal proofs in propositional logic using the rules of natural deduction.
Problem 1: Starting Off
Prove the following claims using the rules of natural deduction for propositional logic:
Claim 1: \(\cdot \vdash (A \rightarrow B) \rightarrow A \rightarrow B\).
Claim 2: \(A \vdash (A \rightarrow B) \rightarrow (B \rightarrow C) \rightarrow C\).
Problem 2: Logical Equivalences
In our formulation of mathematical logic, we take negation to be equivalent to an implication with \(\bot\):
\[ \neg p \equiv p \rightarrow \bot. \]
It turns out equivalence itself is also a logical proposition! We say that \(p \equiv q\) if whenever \(p\) is provable, then \(q\) is provable as well and vice versa. This leads to the following definition of logical equivalence:
Definition (Logical Equivalence): we say that proposition \(p\) is (logically) equivalent to \(q\), written \(p \equiv q\), whenever \(p\) is provable, then \(q\) is provable and whenever \(q\) is provable, then \(p\) is provable. In other words, \(p \equiv q\) exactly when the two propositions are provable:
- \(p \rightarrow q\) and
- \(q \rightarrow p\).
We say that proving an equivalence is proof “in both directions.”
Use this formal definition of logical equivalence to prove some of the equivalences in the previous reading are true:
Claim 1 (Idempotence of Conjunction): \(\cdot \vdash p \wedge p \equiv p\).
Claim 2 (Absorption of Disjunction): \(\cdot \vdash p \vee (p \wedge q) \equiv p\).