Show that $A \lor B ⊢ B \lor A$

Question

Prove the following derivability claim using only our primitive rules: $A \lor B ⊢ B \lor A$

I know this can be attributed to the commutative property, but I'm not exactly sure how to prove this using only the primitive rules of sentential logic.

Edit: Sorry about that guys - I am working with the formal system from Teller's Primer. Also using contradiction is fine. However, primitives rules only means no derived rules so De Morgan's is out of the question.

Answer 1

I am using rules I think are the ones assumed in most treatments of Sentence logic. How about:

$A ∨ B ⊢ B ∨ A $

Start by assuming: 1) $ A ∨ B $

2)Assume -$(B∨ A) $

Conclude $-B \land -A$

Conclude $- A$

From $ -A $ conclude $ -A \lor -B $

From $ -A \land -B $ conclude

-$( A ∨ B)$ , a contradiction , conclude

$(B ∨ A) $

Discharging assumptions :

---

$( A ∨ B) ⊢ (B∨A) $

Answer 2

I assume the natural deduction rules for disjunction here.

Unlike conjunction, that has only one introduction and elimination rule, the disjunction has two different intros and one elim - which is why it needs some further clarification here:

• Elim: $ \qquad \dfrac{\Gamma, p \vdash r \qquad \Gamma, q \vdash r \qquad \Gamma \vdash p \lor q}{\Gamma \vdash r}$

• Intro 0: $\qquad \dfrac{ \Gamma \vdash p}{ \Gamma \vdash p \lor q}$

• Intro 1: $\qquad \dfrac{\Gamma \vdash q}{\Gamma \vdash p \lor q}$

Then:

1) $A \lor B$, Premise

$\qquad$ 2) $B$, Assumption

$\qquad$ 3) $B \lor A$, 2, $\lor$ Intro 0

4) $B \rightarrow (B \lor A)$, 2-3, $\rightarrow$ Intro

$\qquad$ 5) $A$, Assumption

$\qquad$ 6) $B \lor A$, 2, $\lor$ Intro 1

7) $A \rightarrow (B \lor A)$, 2-3, $\rightarrow$ Intro

8) $B \lor A$, 1, 4, 7, $\lor$ Elim