| Version 9 |
Version 8 |
| \PMlinkescapeword{equivalence} |
\PMlinkescapeword{equivalence} |
| \PMlinkescapeword{combination} |
\PMlinkescapeword{combination} |
| \PMlinkescapeword{terms} |
\PMlinkescapeword{terms} |
| \PMlinkescapeword{similar} |
\PMlinkescapeword{similar} |
|
|
| A \emph{logical connective} is a distinguished truth function. The classical logical connectives are: |
A \emph{logical connective} is a distinguished truth function. The classical logical connectives are: |
| \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. |
|
|
|
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
|
Any truth function of any 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
|
| \[ |
\[ |
| 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, C. S. 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, C. S. 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. |
