- 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]]
EDB — 00N
View
English
Authors:
"Mennucci , Andrea C. G."
.
Bibliography
Book index
- [15] P.G. Hinman. Fundamentals of Mathematical Logic. Taylor & Francis, 2005. ISBN 9781568812625. URL https://books.google.it/books?id=xA6D8o72qAgC.
- [33] to3em. Tautologia — Wikipedia, l’enciclopedia libera, 2016. URL http://it.wikipedia.org/w/index.php?title=Tautologia&oldid=81165325. [Online; in data 29-luglio-2016].
Book index
- tautology
- formula, well-formed —, evaluation
- evaluation, of well-formed formula
- contrapositive
Managing blob in: Multiple languages