שליף לוגיקה פורמלית - 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	How to?
Reiteration	From P, conclude P
Contradiction	From P, ~P, conclude any well-formed formula (WFF)
Modus Tollens	From P → Q, ~Q, conclude ~P
Absorption	From P → Q, conclude P → (P & Q)
Hypothetical Syllogism	From P → Q, Q → R, conclude P → R
Disjunctive Syllogism	From P ∨ Q, ~P, conclude Q
Constructive Dilemma	From P ∨ Q, P → R, Q → S, conclude R ∨ S

 

Equivalences

Equivalence	Explanation
Double Negation	P ↔ ~~P
Tautology	P ↔ (P & P) or P ↔ (P ∨ P)
Material Implication	(P → Q) ↔ (~Q → ~P)
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

 

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

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