More Logical Reasoning

Problem 1: Logical Equivalences

In our formulation of mathematical logic, we take negation to be equivalent to an implication with $⊥$ :

$\neg p \equiv p \to ⊥.$

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 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 \to q$ and
$q \to p$ .

We say that proving an equivalence is proof "in both directions."

Use this formal definition of logical equivalence to prove these common properties of propositional logic:

Claim 1 (Idempotence of Conjunction): $\cdot ⊢ p \land p \equiv p$ .

Claim 2 (Absorption of Disjunction): $\cdot ⊢ p \lor (p \land q) \equiv p$ .

Problem 2: Coup De Grâce

Finally, try to prove this more complicated claim that brings together a number of the rules we introduced in the reading.

Claim: $\cdot ⊢ (A \to (B \lor C)) \to (A \land \neg C) \to B$ .

(Hint: make a plan regarding how you will plan the overall goal $B$ in terms of the premises $A \to (B \lor C)$ and $A \land \neg C$ . How will the premises contribute towards proving $B$ ?)

CSC 208: Discrete Structures

More Logical Reasoning

Problem 1: Logical Equivalences

Problem 2: Coup De Grâce