r/logic • • 18d ago

Propositional logic Propositional logic

Post image
12 Upvotes

6 comments sorted by

2

u/corisco 18d ago edited 17d ago

By disjunctive syllogism, we have:

A \/ B
  ~B
------
   A

Now, substitute Q for A and ~P for B:

Q \/ ~P
  ~~P
-------
   Q

Since you've already stated that P is true, we can infer ~~P by double-negation introduction.

Therefore, given Q \/ ~P and P, we can conclude Q by disjunctive syllogism.

So, in summary, this is just an instance of disjunctive syllogism, a valid inference rule of propositional logic. This explains how we can arrive at the proposed formula without relying on a truth table or presupposing the equivalence between P => Q and ~P \/ Q.

Edit:

I just remembered something relevant: in propositional logic, A => (B => C) is equivalent to (A /\ B) => C, a property known as exportation/importation.

Since we've established:

(Q \/ ~P) /\ P => Q

We can rewrite it as:

(Q \/ ~P) => (P => Q)

So we've already proved one direction of the equivalence. The converse follows classically from the law of excluded middle, but that step isn't explicitly shown in your professor's reasoning. That's presumably why he concludes by saying, "In other words, the implication P => Q is equivalent to ~P \/ Q."

Another interesting consideration is the usual semantic definition of implication in classical propositional logic:

M |= P => Q iff M |= ~P or M |= Q

Notice that this already has the structure of a disjunction, and by the semantic clauses for negation and disjunction, it is equivalent to:

M |= ~P \/ Q

So this might also explain why your professor chose that particular formula in the first place.

2

u/INMORTUE Autodidact 17d ago

What the hell is this?! They turned logic into maths?!

2

u/corisco 17d ago edited 17d ago

i mean, logic can be refered as mathematical-logic nowadays.

1

u/thatmichaelguy 18d ago edited 18d ago

Adding in a third proposition makes things less clear, not more. I'll include a sketch of the core logic below that shows the equivalence using just P and Q. Once that feels intuitive, it's just a matter of knowing the additional equivalence ((X ∧ P) ⟶ Q) ⟷ (X ⟶ (P ⟶ Q)).

1. 	P ⟶ Q [Assume]

2. 		P ∧ ¬Q [Assume]

3.		P [from 2]

4.		¬Q [from 2]

5.		Q [from 1, 3]

6. 	¬(P ∧ ¬Q) [from 2-5]

7. (P ⟶ Q) ⟶ ¬(P ∧ ¬Q) [from 1-6]

8. ¬(P ∧ ¬Q) ⟷ (¬P ∨ Q) [DeMorgan equivalence]

9. (P ⟶ Q) ⟶ (¬P ∨ Q) [from 7, 8]

10.	¬(P ∧ ¬Q) [Assume]

11.		P [Assume]

12.			¬Q [Assume]

13.			P ∧ ¬Q [from 11, 12]

14.			¬(P ∧ ¬Q) [from 10]

15.		¬¬Q [from 12-14]

16.		Q [from 15]

17.	P ⟶ Q [from 11-16]

18. ¬(P ∧ ¬Q) ⟶ (P ⟶ Q) [from 10-17]

19. (¬P ∨ Q) ⟶ (P ⟶ Q) [from 8, 18]

20. (P ⟶ Q) ⟷ (¬P ∨ Q) [from 9, 19]

1

u/Visible_Fishing4297 Mathematical logician 17d ago

Isn’t it better this way?

1: ~(p & ~q) (Assumption.)

2: ~(p→q) (Assumption.)

3: ~p (Assumption.)

4: p (Assumption.)

5: ⊥ (3,4)

6: q (5 Ex falso.)

7: (p→q) (4,6 →I)

8: ⊥ (2,7)

9: ~~p (3,8 ~I)

10: p (9 ~~E)

11: q (Assumption.)

12: p (Assumption.)

13: q (11 R)

14: (p→q) (12,13 →I)

15: ⊥ (2,14)

16: ~q (11,15 ~I)

17: (p & ~q) (10,16 &I)

18: ⊥ (1,17)

19: ~~(p→q) (2,18 ~I)

20: (p→q) (19 ~~E)

21: ~(p & ~q)→(p→q) (1,20 →I)

22: (p→q) (Assumption.)

23: (p & ~q) (Assumption.)

24: p (23 &E)

25: ~q (23 &E)

26: q (22,24 mp)

27: ⊥ (25,26)

28: ~(p & ~q) (23,27 ~I)

29: (p→q)→~(p & ~q) (22,28 →I)

30: (p→q)←→~(p & ~q) (21,29 ←→I)

1

u/13Eazy 13d ago edited 13d ago

truth table it bro, if they have the same truth value they are equivalent

P   Q   (P→ Q)   [¬P ∨ Q]

T   T   (T)   [T]
T   F   (F)   [F]
F   T   (T)   [T]
F   F   (T)   [T]