EDB — 00N

view in whole PDF view in whole HTML

View

English

E10

[00N] A well-formed formula in propositional logic is a tautology if for each evaluation the formula is always true. Suppose \(A, B, C \) are well-formed formulas. Show that the following properties of connectives are tautologies.  1

\begin{eqnarray} {A⇒ A} & & \text{identity law} \nonumber \\ { ¬ (¬ A)⇔ A} & & \text{law of double negation} \nonumber \\ {A∨ A⇔ A}~ ~ ,~ ~ {A∧ A⇔ A} & & \text{laws of idempotence} \nonumber \\ {(A⇒ B) ⇔ (¬ B⇒ ¬ A)} & & \text{law of opposition,} \nonumber \\ & & \text{or of the contrapositive \footnotemark } \label{eqn:legge_ contrapposizione} \\ {(A⇒ B) ⇔ (¬ A∨ B)} ⇔ (¬ (A∧ ¬ B)) & & \text{equivalence of implication,} \nonumber \\ & & \text{conjunction and disjunction} \label{eq_ and_ or_ not_ 3r23n} \\ {A∧ B⇔ ¬ (¬ A∨ ¬ B)} & & \text{first law of De Morgan} \label{deMorgan_ 1} \\ {A∨ B⇔ ¬ (¬ A∧ ¬ B)} & & \text{second law of De Morgan} \label{deMorgan_ 2} \\ {A∧ (B∨ C) ⇔ (A∧ B) ∨ (A∧ C)} & & \text{distributive property of the conjunction } \nonumber \\ & & \text{with respect to the disjunction} \label{distrib_ and_ or} \\ {A∨ (B∧ C) ⇔ (A∨ B) ∧ (A∨ C)} & & \text{distributive property of the disjunction } \nonumber \\ & & \text{with respect to the conjunction} \label{distrib_ or_ and} \\ {A∧ B⇔ B∧ A} & & \text{commutative property of } {∧} \nonumber \\ { A∨ B⇔ B∨ A} & & \text{commutative property of } {∨} \nonumber \\ { A∧ (B∧ C)⇔ (A∧ B)∧ C} & & \text{associative property of } {∧} \nonumber \\ { A∨ (B∨ C)⇔ (A∨ B)∨ C} & & \text{associative property of} {∨} \label{assoc_ or} \end{eqnarray}

These last two properties allow to omit parentheses in sequences of conjunctions or disjunctions.

The property ??,??,?? they say that we could base all logic on connectives alone \(¬ \) and \(∧ \), (or on \(¬, ​​∨ \)).

Other important tautologies, often used in logical reasoning.

\begin{eqnarray} {A∨ ¬ A} & & \text{{excluded middle}} \nonumber \\ {¬ (A∧ ¬ A)} & & \text{law of non-contradiction} \nonumber \\ {(A∧ (A⇒ B)) ⇒ B} & & \text{modus ponens} \label{modus_ ponens} \\ {(¬ B∧ (A⇒ B)) ⇒ ¬ A} & & \text{modus tollens} \label{modus_ tollens} \\ {¬ A ⇒ (A⇒ B)} & & \text{negation of the antecedent} \nonumber \\ {B ⇒ (A⇒ B)} & & \text{affirmation of the consequent} \nonumber \\ {(A ⇒ (B⇒ C)) ⇒ ((A∧ B) ⇒ C)} & & \text{exporting} \nonumber \\ {((A⇒ B) ∧ (A⇒ C)) ⇒ (A⇒ (B∧ C))} & & \text{proof by parts} \nonumber \\ {((A⇒ C) ∧ (B⇒ C)) ⇒ ((A∨ B) ⇒ C)} & & \text{proof by cases} \nonumber \\ {((A⇒ B) ∧ (B⇒ C)) ⇒ (A⇒ C)} & & \parbox{\RightWidth }{hypothetical syllogism, or transitivity of implication } \nonumber \\ {(A∨ (A∧ B)) ⇔} { A∧ (A∨ B) ⇔ } & & \nonumber \\ {(A∨ F)⇔ (A∧ V) ⇔ A} & & \text{absorption laws} \nonumber \\ {{F ⇒ B}} & & \parbox{\RightWidth }{first law of Pseudo Scotus, or \em ex falso sequitur quodlibet } \nonumber \\ {A⇒ (¬ A⇒ B)} & & \text{second law of Pseudo Scoto} \nonumber \\ {(¬ A⇒ F) ⇔ A} & & \text{proof by contradiction} \nonumber \\ {((A∧ ¬ B) ⇒ F) ⇔ (A⇒ B)} & & \parbox{\RightWidth }{proof by contradiction, with hypothesis and thesis} \nonumber \\ {(¬ A⇒ A)⇒ A} & & \text{consequentia mirabilis} \end{eqnarray}

[[00P]]

  1. These lists are taken from Section 1.3 in [ 14 ] , or [ 32 ] .
  2. The clause \((¬ B⇒ ¬ A) \) is called "contrapositive" of \((A⇒ B)\).
Download PDF
Bibliography
Book index
  • tautology
  • formula, well-formed —, evaluation
  • evaluation, of well-formed formula
  • contrapositive
Managing blob in: Multiple languages
This content is available in: Italian English