Formal Logic/Sentential Logic/Properties of Sentential Connectives

← Expressibility

↑ Sentential Logic

Substitution and Interchange →

Properties of Sentential Connectives

Here we list some of the more famous, historically important, or otherwise useful equivalences and tautologies. They can be added to the ones listed in Interdefinability of connectives. We can go on at quite some length here, but will try to keep the list somewhat restrained. Remember that for every equivalence of $\varphi \,\!$ and $\psi \,\!$ , there is a related tautology $\varphi \leftrightarrow \psi \,\!$ .

Bivalence

Every formula has exactly one of two truth values.

\vDash \ \mathrm {P} \lor \lnot \mathrm {P} \,\!

Law of Excluded Middle

\vDash \ \lnot (\mathrm {P} \land \lnot \mathrm {P} )\,\!

Law of Non-Contradiction

Analogues to arithmetic laws

Some familiar laws from arithmetic have analogues in sentential logic.

Reflexivity

Conditional and biconditional (but not conjunction and disjunction) are reflexive.

\vDash \ \mathrm {P} \rightarrow \mathrm {P} \,\!

\vDash \ \mathrm {P} \leftrightarrow \mathrm {P} \,\!

Commutativity

Conjunction, disjunction, and biconditional (but not conditional) are commutative.

\mathrm {P} \land \mathrm {Q} \,\!

\mathrm {Q} \land \mathrm {P} \,\!

\mathrm {P} \lor \mathrm {Q} \,\!

\mathrm {Q} \lor \mathrm {P} \,\!

\mathrm {P} \leftrightarrow \mathrm {Q} \,\!

\mathrm {Q} \leftrightarrow \mathrm {P} \,\!

Associativity

Conjunction, disjunction, and biconditional (but not conditional) are associative.

(\mathrm {P} \land \mathrm {Q} )\land \mathrm {R} \,\!

\mathrm {P} \land (\mathrm {Q} \land \mathrm {R} )\,\!

(\mathrm {P} \lor \mathrm {Q} )\lor \mathrm {R} \,\!

\mathrm {P} \lor (\mathrm {Q} \lor \mathrm {R} )\,\!

(\mathrm {P} \leftrightarrow \mathrm {Q} )\leftrightarrow \mathrm {R} \,\!

\mathrm {P} \leftrightarrow (\mathrm {Q} \leftrightarrow \mathrm {R} )\,\!

Distribution

We list ten distribution laws. Of these, probably the most important are that conjunction and disjunction distribute over each other and that conditional distributes over itself.

\mathrm {P} \land (\mathrm {Q} \land \mathrm {R} )\,\!

(\mathrm {P} \land \mathrm {Q} )\land (\mathrm {P} \land \mathrm {R} )\,\!

\mathrm {P} \land (\mathrm {Q} \lor \mathrm {R} )\,\!

(\mathrm {P} \land \mathrm {Q} )\lor (\mathrm {P} \land \mathrm {R} )\,\!

\mathrm {P} \lor (\mathrm {Q} \land \mathrm {R} )\,\!

(\mathrm {P} \lor \mathrm {Q} )\land (\mathrm {P} \lor \mathrm {R} )\,\!

\mathrm {P} \lor (\mathrm {Q} \lor \mathrm {R} )\,\!

(\mathrm {P} \lor \mathrm {Q} )\lor (\mathrm {P} \lor \mathrm {R} )\,\!

\mathrm {P} \lor (\mathrm {Q} \rightarrow \mathrm {R} )\,\!

(\mathrm {P} \lor \mathrm {Q} )\rightarrow (\mathrm {P} \lor \mathrm {R} )\,\!

\mathrm {P} \lor (\mathrm {Q} \leftrightarrow \mathrm {R} )\,\!

(\mathrm {P} \lor \mathrm {Q} )\leftrightarrow (\mathrm {P} \lor \mathrm {R} )\,\!

\mathrm {P} \rightarrow (\mathrm {Q} \land \mathrm {R} )\,\!

(\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {P} \rightarrow \mathrm {R} )\,\!

\mathrm {P} \rightarrow (\mathrm {Q} \lor \mathrm {R} )\,\!

(\mathrm {P} \rightarrow \mathrm {Q} )\lor (\mathrm {P} \rightarrow \mathrm {R} )\,\!

\mathrm {P} \rightarrow (\mathrm {Q} \rightarrow \mathrm {R} )\,\!

(\mathrm {P} \rightarrow \mathrm {Q} )\rightarrow (\mathrm {P} \rightarrow \mathrm {R} )\,\!

\mathrm {P} \rightarrow (\mathrm {Q} \leftrightarrow \mathrm {R} )\,\!

(\mathrm {P} \rightarrow \mathrm {Q} )\leftrightarrow (\mathrm {P} \rightarrow \mathrm {R} )\,\!

Transitivity

Conjunction, conditional, and biconditional (but not disjunction) are transitive.

\vDash \ (\mathrm {P} \land \mathrm {Q} )\land (\mathrm {Q} \land \mathrm {R} )\rightarrow \mathrm {P} \land \mathrm {R} \,\!

\vDash \ (\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {Q} \rightarrow \mathrm {R} )\rightarrow (\mathrm {P} \rightarrow \mathrm {R} )\,\!

\vDash \ (\mathrm {P} \leftrightarrow \mathrm {Q} )\land (\mathrm {Q} \leftrightarrow \mathrm {R} )\rightarrow (\mathrm {P} \leftrightarrow \mathrm {R} )\,\!

Other tautologies and equivalences

Conditionals

These tautologies and equivalences are mostly about conditionals.

\vDash \ \mathrm {P} \land \mathrm {Q} \rightarrow \mathrm {P} \qquad \qquad \vDash \ \mathrm {P} \land \mathrm {Q} \rightarrow \mathrm {Q} \,\!

\vDash \ \mathrm {P} \rightarrow \mathrm {P} \lor \mathrm {Q} \qquad \qquad \vDash \ \mathrm {Q} \rightarrow \mathrm {P} \lor \mathrm {Q} \,\!

\vDash \ (\mathrm {P} \rightarrow \mathrm {Q} )\lor (\mathrm {Q} \rightarrow \mathrm {R} )\,\!

\vDash \ \lnot \mathrm {P} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )\,\!

Conditional addition

\vDash \ \mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )\,\!

Conditional addition

{\mathrm {P}}\rightarrow {\mathrm {Q}}\,\!

\lnot \mathrm {Q} \rightarrow \lnot \mathrm {P} \,\!

Contraposition

\mathrm {P} \land \mathrm {Q} \rightarrow \mathrm {R} \,\!

\mathrm {P} \rightarrow (\mathrm {Q} \rightarrow \mathrm {R} )\,\!

Exportation

Biconditionals

These tautologies and equivalences are mostly about biconditionals.

\vDash \ \mathrm {P} \land \mathrm {Q} \rightarrow (\mathrm {P} \leftrightarrow \mathrm {Q} )\,\!

Biconditional addition

\vDash \ \lnot \mathrm {P} \land \lnot \mathrm {Q} \rightarrow (\mathrm {P} \leftrightarrow \mathrm {Q} )\,\!

Biconditional addition

\vDash (\mathrm {P} \leftrightarrow \mathrm {Q} )\lor (\mathrm {P} \leftrightarrow \lnot \mathrm {Q} )\,\!

\lnot (\mathrm {P} \leftrightarrow \mathrm {Q} )\,\!

\lnot \mathrm {P} \leftrightarrow \mathrm {Q} \,\!

\mathrm {P} \leftrightarrow \lnot \mathrm {Q} \,\!

Miscellaneous

We repeat DeMorgan's Laws from the Interdefinability of connectives section of Expressibility and add two additional forms. We also list some additional tautologies and equivalences.

\vDash \ \mathrm {P} \leftrightarrow \mathrm {P} \land \mathrm {P} \,\!

Idempotence for conjunction

\vDash \ \mathrm {P} \leftrightarrow \mathrm {P} \lor \mathrm {P} \,\!

Idempotence for disjunction

\vDash \ \mathrm {P} \rightarrow \mathrm {P} \lor \mathrm {Q} \,\!

Disjunctive addition

\vDash \ \mathrm {Q} \rightarrow \mathrm {P} \lor \mathrm {Q} \,\!

Disjunctive addition

\vDash \ \mathrm {P} \land \lnot \mathrm {P} \rightarrow \mathrm {Q} \,\!

\mathrm {P} \land \mathrm {Q} \,\!

\lnot (\lnot \mathrm {P} \lor \lnot \mathrm {Q} )\,\!

Demorgan's Laws

\mathrm {P} \lor \mathrm {Q} \,\!

\lnot (\lnot \mathrm {P} \land \lnot \mathrm {Q} )\,\!

Demorgan's Laws

\lnot (\mathrm {P} \land \mathrm {Q} )\,\!

\lnot \mathrm {P} \lor \lnot \mathrm {Q} \,\!

Demorgan's Laws

\lnot (\mathrm {P} \lor \mathrm {Q} )\,\!

\lnot \mathrm {P} \land \lnot \mathrm {Q} \,\!

Demorgan's Laws

{\mathrm {P}}\,\!

\lnot \lnot \mathrm {P} \,\!

Double Negation

Deduction and reduction principles

The following two principles will be used in constructing our derivation system on a later page. They can easily be proven, but—since they are neither tautologies nor equivalences—it takes more than a mere truth table to do so. We will not attempt the proof here.

Deduction principle

Let $\varphi \,\!$ and $\psi \,\!$ both be formulae, and let $\Gamma \,\!$ be a set of formulae.

\mathrm {If} \ \ \Gamma \cup \{\varphi \}\vDash \psi \mathrm {,\ then} \ \ \Gamma \vDash (\varphi \rightarrow \psi )\,\!

Reduction principle

Let $\varphi \,\!$ and $\psi \,\!$ both be formulae, and let $\Gamma \,\!$ be a set of formulae.

\mathrm {If} \ \ \Gamma \cup \{\varphi \}\vDash \psi \ \ \mathrm {and} \ \ \Gamma \cup \{\varphi \}\vDash \lnot \psi \mathrm {,\ then} \ \ \Gamma \vDash \lnot \varphi ,\!

\mathrm {If} \ \ \Gamma \cup \{\lnot \varphi \}\vDash \psi \ \ \mathrm {and} \ \ \Gamma \cup \{\lnot \varphi \}\vDash \lnot \psi \mathrm {,\ then} \ \ \Gamma \vDash \varphi \,\!

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.