שליף לוגיקה פורמלית - formal logic cheatsheet

Valid vs. Invalid form

1. Valid Form:
   Premises true → Conclusion must be true

2. Invalid Form:
   Premises true → Conclusion may or may not be true

3. An invalid form can have true premises and a true conclusion in specific cases, but this doesn't make it valid overall.

Example:
"If it's raining, the streets are wet." (Valid P->Q)
vs.
"If the streets are wet, it's raining." (Invalid Q->P).

The latter commits the fallacy of affirming the consequent because it can be that the streets are wet due to rain but it can also be the result of a burst water main - a counterexample that proves the invalidity of the form.

 

Inference Rules

Propositional Inference Rules

Rule	Symbolized	Explanation
Conjunction Introduction	&I	From P, Q, conclude P & Q
Conjunction Elimination	&E	From P & Q, conclude P or Q
Disjunction Introduction	∨I	From P, conclude P ∨ Q
Disjunction Elimination	∨E	aka Constructive Dilemma
Conditional Elimination	→E	aka Modus Ponens; From P → Q, P, conclude Q
Conditional Introduction	→I	Hypothesize the antecedent then derive the conclusion
Negation Introduction	~I	Hypothesize P, then show through RAA that it is not possible

Predicate Inference Rules

Rule	Symbolized	Explanation
Universal Elimination	∀E	From ∀xFx, conclude Fa
Universal Introduction	∀I	From Fa, conclude ∀xFx, provided a is representative of the domain a is not an active assumption a is not in the conclusion
Existential Elimination	∃E	From ∃xFx, hypothesize Fa a must be unused previously a is not in the conclusion
Existential Introduction	∃I	From Fa, conclude ∃xFx
Identity Introduction	=I	Assert a = a at any line
Identity Elimination	=E	If a = b, replace a with b

 

Proof Strategies

Before going into the trouble of writing your proof, try to explain to a "rubber ducky" how the conclusion follows from the premises?



Having trouble? Try using a concrete example.

Strategy	How to?
Atomic Formula	Hypothesize the negation of the conclusion, reach a contradiction (RAA), then apply ~I and ~E.
Negated Formula	Hypothesize the formula without the negation and derive a contradiction to conclude with ~I.
Conjunction	Prove each conjunct separately, then conjoin with &I.
Disjunction	Prove one of the disjuncts, then apply ∨I. If (1) fails, try Reductio Ad Absurdum (RAA).
Conditional	Hypothesize the antecedent and show the consequent follows (→I).
Biconditional	Use two conditionals.
Nothing works 1?	If a premise is a disjunction, try Constructive Dilemma (CD).
Nothing works 2?	Add a hypothesis whose negation, via RAA, would support the proof.
Nothing works 3?	Does the conclusion follow from the premises?

 

Derived Rules

Rule Name	How to?	Explanation
Reiteration	From P, conclude P	P can be reused in the proof.
Contradiction	From P, ~P, conclude any well-formed formula (WFF)	From a contradiction any statement follows.
Modus Tollens	From P → Q, ~Q, conclude ~P	Denying the consequent denies the antecedent.
Absorption	From P → Q, conclude P → (P & Q)	Strengthening the consequent.
Hypothetical Syllogism	From P → Q, Q → R, conclude P → R	Transitivity of conditionals.
Disjunctive Syllogism	From P ∨ Q, ~P, conclude Q	Eliminating a disjunct.
Constructive Dilemma	From P ∨ Q, P → R, Q → S, conclude R ∨ S	Choosing between two implications.

 

Equivalences

Equivalence	Explanation
Double Negation	P ↔ ~~P
Tautology	P ↔ (P & P) or P ↔ (P ∨ P)
Material Implication	(P → Q) ↔ (~P ∨ Q)
Transposition	(P → Q) ↔ (~Q → ~P)
Exportation	((P & Q) → R) ↔ (P → (Q → R))
De Morgan’s Laws	~(P ∨ Q) ↔ (~P & ~Q)
	~(P & Q) ↔ (~P ∨ ~Q)
Commutation	(P ∨ Q) ↔ (Q ∨ P)
	(P & Q) ↔ (Q & P)
Distribution	(P & (Q ∨ R)) ↔ ((P & Q) ∨ (P & R))
	(P ∨ (Q & R)) ↔ ((P ∨ Q) & (P ∨ R))
Association	((P ∨ Q) ∨ R) ↔ (P ∨ (Q ∨ R))
	((P & Q) & R) ↔ (P & (Q & R))

 

Quantifier Exchange (QE)

Equivalence
∀xFx ↔ ~∃x~Fx
~∀xFx ↔ ∃x~Fx
∀x~Fx ↔ ~∃xFx
~∀x~Fx ↔ ∃xFx

 

Examples

Prove: P → Q ⊢ ~P V Q (Material Implication)

1 P→Q            Premise
2 | ~(~PVQ)      Hypothesis for ~I (Negation Introduction)
3 | ~~P&~Q       2 DM (De Morgan's Law)
4 | ~~P          3 &E (Conjunction Elimination)
5 | P            4 ~E (Negation Elimination)
6 | ~Q           3 &E
7 | Q            1,5 MP (Modus Ponens)
8 | Q&~Q         6,7 &I (Conjunction Introduction)
9 ~~(~PVQ)       2-8 ~I
10 ~PVQ          9 ~E

 

Prove: ~(P ∨ Q) → (~P & ~Q)

1 ~(P ∨ Q)                    Premise
2   |  P                      Hypothesis for ~I (Negation Introduction)
3   | P ∨ Q                   ∨I (Disjunction Introduction)
4   | (P ∨ Q) & ~(P ∨ Q)      1,3 &I (Conjunction Introduction)
5   ~P                        2-4 ~I
6   | Q                       Hypothesis for ~I
7   | Q ∨ P                   ∨I
8   | P ∨ Q                   Commutation
9   | (P ∨ Q) & ~(P ∨ Q)      1,3 &I
10  ~Q                        6-9 ~I
11  ~P & ~Q                   5,10 &I

    

Prove: ∀x(Px ∨ Qx),∀x(Px → Rx) ⊢ ∀x(Qx ∨ Rx)

1  ∀x(Px ∨ Qx)          Premise
2  ∀x(Px → Rx)          Premise
3  Pa ∨ Qa              1 ∀E (Universal Elimination)
4  Pa → Ra              2 ∀E
5  |  Pa                →I(Condition Introduction)
6  |  Ra                4,5  MP (Modus Ponens)
7  |  Qa ∨ Ra           6  ∨I (Disjunction Introduction)
8  Pa → (Qa ∨ Ra)       5-7 →I
9  |  Qa                Hypothesis for →I
10 |  Qa ∨ Ra           9  ∨I
11 Qa → (Qa ∨ Ra)       9-10 →I
12 Qa ∨ Ra              3,8,11 Constructive Dilemma
13 ∀x(Qx ∨ Rx)          12 ∀I (Universal Introduction)

    

Prove: ∀x(Px→Mx) ⊢ ∃xPx→∃xMx

1  ∀x(Px→Mx)      Premise
2  |  ∃xPx        Hypothesis for →I (Condition Introduction)
3  |  |  Pa       Hypothesis for ∃E (Existential Elimination)
4  |  |  Pa→Ma    1 ∀E (Universal Elimination)
5  |  |  Ma       3,4  MP (Modus Ponens)
6  |  |  ∃xMx     5 ∃I (Existential Introduction)
7  |  ∃xMx        2,3-6 ∃E
8  ∃xPx→∃xMx      2-7 →I

Prove: ∀x(Px & Qx)→R, ∀x(Px → Qx), ∀xPx ⊢ R

1 ∀x(Px → Qx)          Premise
2 ∀x(Px & Qx) → R      Premise
3 ∀xPx                 Premise
4  | ~R                Hypothesis for ~I (Negation Introduction)
5  | ~∀x(Px & Qx)      2,4 MT (Modus Tollens)
6  | ∃x~(Px & Qx)      5 QE (Quantifier Exchange)
7  | | ~(Pa & Qa)      Hypothesis for ∃E (Existential Elimination)
8  | | Pa → Qa         1 ∀E (Universal Elimination)
9  | | Pa              3 ∀E
10 | | Qa              8,9 MP (Modus Ponens)
11 | | Pa & Qa         9,10 &I (Conjunction Introduction)
12 | | ⊥               7,11 ⊥I (Contradiction Introduction)
13 | ⊥                 6,7-12 ∃E
14 ~~R                 4-13 ~I  
15 R                   14 DN (Double Negation)

Encode the Barber Paradox: a barber who shaves only those men who do not shave themselves where the paradox arises when one asks if the barber shaves himself, leading to a contradiction.

This proof is not yet validated indefinitely:

1 ∀x Man(x)                                                                Premise
2 Shave(x,y)                                                                 Premise
3 b                                                                                 Premise; is the barber
4   | ∃y(∀x(Man(x) → (Shave(y,x) ↔ ¬Shave(x,x)))  Hypothesis for ~I (Negation Introduction); Hypothesize that there is a someone that can shave anyone except himself
5   || ∀x(Man(x) → (Shave(b,x) ↔ ¬Shave(x,x))        Hypothesis for ∃E (Existential Elimination); A barber exists
6   || Shave(b,b) ↔ ¬Shave(b,b)                                   When substituting x for b; The barber tries to shave himself
7   ||| Shave(b,b)                                                            Hypothesis for ~I (Negation Introduction); In the case that the barber shaves himself
8   ||| Shave(b,b) → ¬Shave(b,b)                                  6 ↔E (Bidirectional Elimination); If the barber shaves himself than he can't 
9   ||| ¬Shave(b,b)                                                          7,8 →E (Condition Elimination); So the conclusion is that the barber can't shave himself
10 ||| ¬Shave(b,b) & Shave(b,b)                                    6,9 &I (Conjunction Introduction); A barber can't shave and not shave himself
11 ||  ¬Shave(b,b)                                                           6-10 ~I; A barber can't shave himself
12 ||  ¬Shave(b,b) → Shave(b,b)                                   6 ↔E; If the barber can't shave himself than he needs to
13 ||  Shave(b,b)                                                             11,12 →E; So the barber needs to shave himself
14 ||  ⊥                                                                            5-14 ⊥I (Contradiction Introduction); A barber can't shave and not shave himself, there's a contradiction
15 | ⊥                                                                              4, 5-14  ∃E; It's an absurdity, all the steps brings the argument to a contradiction that can't be settled
16 ~∃y(∀x(Man(x) → (Shave(y,x) ↔ ¬Shave(x,x)))  4-15 ~I; A barber that shaves anyone who can't shave himself is not possible

 

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים