| Version 12 |
Version 11 |
| \PMlinkescapeword{equivalence} |
\PMlinkescapeword{equivalence} |
| \PMlinkescapeword{combination} |
\PMlinkescapeword{combination} |
| \PMlinkescapeword{terms} |
\PMlinkescapeword{terms} |
| \PMlinkescapeword{similar} |
\PMlinkescapeword{similar} |
|
|
| In propositional logic, the usual way of forming a proposition out of existing propositions is by attaching a designated symbol to the existing propositions. This designated symbol is call a \emph{logical connective}, or simply a \emph{connective}. Given a connective, the number of propositions needed to form a new proposition is a fixed integer, and is called the \emph{arity} of the connective. For example, if $\#$ is a logical connective of arity 3, and $p,q,r$ are three existing propositions, then $\#pqr$ is the proposition formed by attaching $\#$ to the $p,q$ and $r$ in order. $0$-ary connectives are also allowed. |
A \emph{logical connective} is a distinguished truth function. The classical logical connectives are:{\footnote{Logical {\em implication} $\to$ and logical {\em is equivalent to} $\leftrightarrow$ symbols are typically used for logicians. Nevertheless, the symbols $\Rightarrow$ for material implication and $\Leftrightarrow$ for material equivalence are commonly used in the literature. In particular, $\to$ is usually reserved for the concept of limit.}} |
|
|
| The common classical logical connectives are:{\footnote{Logical {\em implication} $\to$ and logical {\em is equivalent to} $\leftrightarrow$ symbols are typically used for logicians. Nevertheless, the symbols $\Rightarrow$ for material implication and $\Leftrightarrow$ for material equivalence are commonly used in the literature. In particular, $\to$ is usually reserved for the concept of limit.}} |
|
| \begin{itemize} |
\begin{itemize} |
| \item |
\item |
| $\lnot$: \PMlinkname{logical not}{Negation}; |
$\lnot$: \PMlinkname{logical not}{Negation}; |
|
|
| \item |
\item |
| $\lor$: logical or; |
$\lor$: logical or; |
|
|
| \item |
\item |
| $\land$: logical and; |
$\land$: logical and; |
|
|
| \item |
\item |
| $\rightarrow$ or $\supset$: material implication; and |
$\rightarrow$ or $\supset$: material implication; and |
|
|
| \item |
\item |
| $\leftrightarrow$ or $\equiv$: \PMlinkname{material equivalence}{Biconditional}. |
$\leftrightarrow$ or $\equiv$: \PMlinkname{material equivalence}{Biconditional}. |
| \end{itemize} |
\end{itemize} |
| The symbols $\supset$ and $\equiv$ are due to Russell. |
The symbols $\supset$ and $\equiv$ are due to Russell. |
|
|
| Usually, given a logical connective $\#$, a truth function is associated. The arity of the truth function is defined to be the arity of the connective. When there is no confusion, the symbol for the associated truth function is the same as the symbol of the connective. A truth function of small arity can be easily represented by a table, called the \emph{truth table} of the truth function. The truth functions and truth tables associated with the connectives listed above are |
Any truth function of any finite arity can be written as a finite combination of these connectives. However, the collection is redundant; the final three symbols, $\land$, $\rightarrow$, and $\leftrightarrow$, can be defined in terms of prior ones. By DeMorgan's law, we can define logical and by |
|
|
| \begin{itemize} |
|
| \item |
|
| $\lnot$: $\lnot: \boldsymbol{2} \to \boldsymbol{2}$ given by $\lnot(x)=1-x$; |
|
|
|
| \begin{center} |
|
| \begin{tabular}{cc} |
|
| $P$ & $\lnot P$ \\ |
|
| \hline |
|
| F & T \\ |
|
| T & F |
|
| \end{tabular} |
|
| \end{center} |
|
|
|
| \item |
|
| $\lor$: $\lor: \boldsymbol{2}^2 \to \boldsymbol{2}$ given by $\lor(x,y)=\max(x,y)$; |
|
|
|
| \begin{center} |
|
| \begin{tabular}{ccc} |
|
| $P$ & $Q$ & $P \lor Q$ \\ |
|
| \hline |
|
| F & F & F \\ |
|
| F & T & T \\ |
|
| T & F & T \\ |
|
| T & T & T |
|
| \end{tabular} |
|
| \end{center} |
|
|
|
| \item |
|
| $\land$: $\land: \boldsymbol{2}^2 \to \boldsymbol{2}$ given by $\land(x,y)=\min(x,y)$; |
|
|
|
| \begin{center} |
|
| \begin{tabular}{ccc} |
|
| $P$ & $Q$ & $P \land Q$ \\ |
|
| \hline |
|
| F & F & F \\ |
|
| F & T & F \\ |
|
| T & F & F \\ |
|
| T & T & T |
|
| \end{tabular} |
|
| \end{center} |
|
|
|
| \item |
|
| $\rightarrow$: $\rightarrow: \boldsymbol{2}^2 \to \boldsymbol{2}$ given by $\rightarrow(x,y)=\max(1-x,y)$; and |
|
|
|
| \begin{center} |
|
| \begin{tabular}{ccc} |
|
| $P$ & $Q$ & $P \rightarrow Q$ \\ |
|
| \hline |
|
| F & F & T \\ |
|
| F & T & T \\ |
|
| T & F & F \\ |
|
| T & T & T |
|
| \end{tabular} |
|
| \end{center} |
|
|
|
| \item |
|
| $\leftrightarrow$: $\leftrightarrow: \boldsymbol{2}^2 \to \boldsymbol{2}$ given by $\rightarrow(x,y)=1-((x+y) \pmod 2)$. |
|
|
|
| \begin{center} |
|
| \begin{tabular}{ccc} |
|
| $P$ & $Q$ & $P \leftrightarrow Q$ \\ |
|
| \hline |
|
| F & F & T \\ |
|
| F & T & F \\ |
|
| T & F & F \\ |
|
| T & T & T |
|
| \end{tabular} |
|
| \end{center} |
|
|
|
| \end{itemize} |
|
|
|
| Note that $0$ and $1$ have been converted to $F$ and $T$ in the tables above. |
|
|
|
| Any truth function of any finite arity can be written as a finite combination of these connectives (see the entry on functional completeness). However, the collection is redundant; the final three symbols, $\land$, $\rightarrow$, and $\leftrightarrow$, can be defined in terms of prior ones. By DeMorgan's law, we can define logical and by |
|
| \[ |
\[ |
| P\land Q := \lnot P\lor \lnot Q. |
P\land Q := \lnot P\lor \lnot Q. |
| \] |
\] |
| Material implication can be defined by |
Material implication can be defined by |
| \[ |
\[ |
| P\rightarrow Q := \lnot P\lor Q. |
P\rightarrow Q := \lnot P\lor Q. |
| \] |
\] |
| Finally, material equivalence can be defined by |
Finally, material equivalence can be defined by |
| \begin{align*} |
\begin{align*} |
| P\leftrightarrow Q |
P\leftrightarrow Q |
| &:= (P\rightarrow Q)\land(Q\rightarrow P) \\ |
&:= (P\rightarrow Q)\land(Q\rightarrow P) \\ |
| &= \lnot(\lnot P\lor Q)\lor\lnot(\lnot Q\lor P). |
&= \lnot(\lnot P\lor Q)\lor\lnot(\lnot Q\lor P). |
| \end{align*} |
\end{align*} |
| Hence $\lnot$ and $\vee$ suffice to define all other connectives. |
Hence $\lnot$ and $\vee$ suffice to define all other connectives. |
|
|
| In the late 19th century and early 20th century, Charles Sanders Peirce and H.M. Sheffer independently discovered that a single binary connective suffices to define all logical connectives. Two such connectives are |
In the late 19th century and early 20th century, Charles Sanders Peirce and H.M. Sheffer independently discovered that a single binary connective suffices to define all logical connectives. Two such connectives are |
| \begin{itemize} |
\begin{itemize} |
| \item |
\item |
| $\uparrow$: the \emph{Sheffer stroke} (sometimes denoted by $|$) and |
$\uparrow$: the \emph{Sheffer stroke} (sometimes denoted by $|$) and |
|
|
| \item |
\item |
| $\downarrow$: the \emph{Peirce arrow} (sometimes denoted by $\bot$). |
$\downarrow$: the \emph{Peirce arrow} (sometimes denoted by $\bot$). |
| \end{itemize} |
\end{itemize} |
|
|
| The Sheffer stroke is defined by the truth table |
The Sheffer stroke is defined by the truth table |
| \begin{center} |
\begin{center} |
| \begin{tabular}{ccc} |
\begin{tabular}{ccc} |
| $P$ & $Q$ & $P \uparrow Q$ \\ |
$P$ & $Q$ & $P \uparrow Q$ \\ |
| \hline |
\hline |
| F & F & T \\ |
F & F & T \\ |
| F & T & T \\ |
F & T & T \\ |
| T & F & T \\ |
T & F & T \\ |
| T & T & F |
T & T & F |
| \end{tabular} |
\end{tabular} |
| \end{center} |
\end{center} |
| Observe that $P\uparrow Q$ is true if and only if either $P$ or $Q$ is false. For this reason, the Sheffer stroke is sometimes called \emph{alternative denial} or \emph{NAND}. |
Observe that $P\uparrow Q$ is true if and only if either $P$ or $Q$ is false. For this reason, the Sheffer stroke is sometimes called \emph{alternative denial} or \emph{NAND}. |
|
|
| The Peirce arrow is defined by the truth table |
The Peirce arrow is defined by the truth table |
| \begin{center} |
\begin{center} |
| \begin{tabular}{ccc} |
\begin{tabular}{ccc} |
| $P$ & $Q$ & $P \downarrow Q$ \\ |
$P$ & $Q$ & $P \downarrow Q$ \\ |
| \hline |
\hline |
| F & F & T \\ |
F & F & T \\ |
| F & T & F \\ |
F & T & F \\ |
| T & F & F \\ |
T & F & F \\ |
| T & T & F |
T & T & F |
| \end{tabular} |
\end{tabular} |
| \end{center} |
\end{center} |
| The proposition $P\downarrow Q$ is true if and only if both $P$ and $Q$ are false. For this reason, the Peirce arrow is sometimes called \emph{joint denial} or \emph{NOR}. |
The proposition $P\downarrow Q$ is true if and only if both $P$ and $Q$ are false. For this reason, the Peirce arrow is sometimes called \emph{joint denial} or \emph{NOR}. |
|
|
| To show the sufficiency of the Sheffer stroke, all we have to do is define both $\lnot$ and $\lor$ in terms of $\uparrow$. The proposition $P\uparrow P$ asserts that either $P$ is false, or $P$ is false; thus we can define $\lnot$ by $\lnot P := P\uparrow P$. We define $\lor$ by |
To show the sufficiency of the Sheffer stroke, all we have to do is define both $\lnot$ and $\lor$ in terms of $\uparrow$. The proposition $P\uparrow P$ asserts that either $P$ is false, or $P$ is false; thus we can define $\lnot$ by $\lnot P := P\uparrow P$. We define $\lor$ by |
| \[ |
\[ |
| P \lor Q := (P\uparrow P)\uparrow(Q\uparrow Q), |
P \lor Q := (P\uparrow P)\uparrow(Q\uparrow Q), |
| \] |
\] |
| since this asserts that either $P\uparrow P$ is false (that is, that $P$ is true) or that $Q\uparrow Q$ is false (that is, that $Q$ is true). |
since this asserts that either $P\uparrow P$ is false (that is, that $P$ is true) or that $Q\uparrow Q$ is false (that is, that $Q$ is true). |
|
|
| We can show the sufficiency of the Peirce arrow in a similar way. Define |
We can show the sufficiency of the Peirce arrow in a similar way. Define |
| \[ |
\[ |
| \lnot P := P\downarrow P |
\lnot P := P\downarrow P |
| \] |
\] |
| and |
and |
| \[ |
\[ |
| P\lor Q := (P\downarrow Q)\downarrow(P\downarrow Q). |
P\lor Q := (P\downarrow Q)\downarrow(P\downarrow Q). |
| \] |
\] |
| This expression asserts that $P\downarrow Q$ is false, that is, that it is false that both $P$ and $Q$ are false. By DeMorgan's law, this is equivalent to asserting that at least one of $P$ and $Q$ is true. |
This expression asserts that $P\downarrow Q$ is false, that is, that it is false that both $P$ and $Q$ are false. By DeMorgan's law, this is equivalent to asserting that at least one of $P$ and $Q$ is true. |
