PlanetMath: logical connective

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (38)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

logical connective

(Definition)

A logical connective is a distinguished truth function. The classical logical connectives are:¹

$\lnot$ : logical not;
$\lor$ : logical or;
$\land$ : logical and;
$\rightarrow$ or $\supset$ : material implication; and
$\leftrightarrow$ or $\equiv$ : material equivalence.

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

$\displaystyle P\land Q := \lnot P\lor \lnot Q.$

Material implication can be defined by

$\displaystyle P\rightarrow Q := \lnot P\lor Q.$

Finally, material equivalence can be defined by

$\displaystyle P\leftrightarrow Q$	$\displaystyle := (P\rightarrow Q)\land(Q\rightarrow P)$
	$\displaystyle = \lnot(\lnot P\lor Q)\lor\lnot(\lnot Q\lor P).$

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

$\uparrow$ : the Sheffer stroke (sometimes denoted by $\vert$ ) and
$\downarrow$ : the Peirce arrow (sometimes denoted by $\bot$ ).

The Sheffer stroke is defined by the truth table

		$P \uparrow Q$
F	F	T
F	T	T
T	F	T
T	T	F

Observe that $P\uparrow Q$ is true if and only if either

is false. For this reason, the Sheffer stroke is sometimes called alternative denial or NAND.

The Peirce arrow is defined by the truth table

		$P \downarrow Q$
F	F	T
F	T	F
T	F	F
T	T	F

The proposition $P\downarrow Q$ is true if and only if both

and

are false. For this reason, the Peirce arrow is sometimes called joint denial or 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 is false, or is false; thus we can define $\lnot$ by $\lnot P := P\uparrow P$ . We define $\lor$ by

$\displaystyle P \lor Q := (P\uparrow P)\uparrow(Q\uparrow Q),$

since this asserts that either $P\uparrow P$ is false (that is, that

is true) or that $Q\uparrow Q$ is false (that is, that

is true).

We can show the sufficiency of the Peirce arrow in a similar way. Define

$\displaystyle \lnot P := P\downarrow P$

and

$\displaystyle 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

and

are false. By DeMorgan's law, this is equivalent to asserting that at least one of

and

is true.

Footnotes

...¹: Logical implication $\to$ and logical 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.