|
|
|
Viewing Version
1
of
'logical connective'
|
[ view 'logical connective'
|
back to history
]
| Title of object: |
logical connective |
| Canonical Name: |
LogicalConnective |
| Type: |
Definition |
| Created on: |
2006-12-08 16:43:31 |
| Modified on: |
2006-12-08 16:43:31 |
| Classification: |
msc:03B05 |
| Defines: |
Sheffer stroke, alternative denial, NAND, Peirce arrow, joint denial, NOR |
Revision comment (for changes between this and next version):
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
|
Content:
\PMlinkescapeword{equivalence}
\PMlinkescapeword{combination}
\PMlinkescapeword{terms}
\PMlinkescapeword{similar}
A \emph{logical connective} is a distinguished truth function. The classical logical connectives are:
\begin{itemize}
\item
$\lnot$: logical not;
\item
$\lor$: logical or;
\item
$\land$: logical and;
\item
$\rightarrow$: material implication; and
\item
$\leftrightarrow$: logical equivalence.
\end{itemize}
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.
\]
Material implication can be defined by
\[
P\rightarrow Q := \lnot P\lor Q.
\]
Finally, logical equivalence can be defined by
\begin{align*}
P\leftrightarrow Q
&:= (P\rightarrow Q)\land(Q\rightarrow P) \\
&= \lnot(\lnot P\lor Q)\lor\lnot(\lnot Q\lor P).
\end{align*}
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
\begin{itemize}
\item
$\uparrow$: the \emph{Sheffer stroke} (sometimes denoted by $|$) and
\item
$\downarrow$: the \emph{Peirce arrow} (sometimes denoted by $\bot$).
\end{itemize}
The Sheffer stroke is defined by the truth table
\begin{center}
\begin{tabular}{ccc}
$P$ & $Q$ & $P \uparrow Q$ \\
\hline
F & F & T \\
F & T & T \\
T & F & T \\
T & T & F
\end{tabular}
\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}.
The Peirce arrow is defined by the truth table
\begin{center}
\begin{tabular}{ccc}
$P$ & $Q$ & $P \uparrow Q$ \\
\hline
F & F & T \\
F & T & F \\
T & F & F \\
T & T & F
\end{tabular}
\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}.
To show the sufficiency of Sheffer stroke, all we have to do is define both $\lnot$ and $\lor$. 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),
\]
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 Peirce arrow in a similar way. Define
\[
\lnot P := P\downarrow P
\]
and
\[
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. |
|
|
|
|
|
