Section 1.5: Sentential Connectives

A $k$ -place Boolean function is a function from $\{F,T\}^{k}$ to $\{F,T\}$ .

For convenience, $0$ -place Boolean functions are $F$ and $T$ .
Every wff $\alpha$ defines (realizes) a boolean function: $B_{\alpha}(\overrightarrow{X})=\overline{v}(\alpha)$ where $v(A_{i})=X_{i}$ .
For $\alpha,\beta$ , $\alpha\vDash\beta$ iff $B_{\alpha}(\overrightarrow{X})\le B_{\beta}(\overrightarrow{X})$ (assuming $F\le T$ ), and $\vDash\beta$ iff $B_{\beta}(\overrightarrow{X})\equiv T$ .

If $G$ is an $n$ -place Boolean function, $n\ge1$ , then there is a wff $\alpha$ such that $B_{\alpha}\equiv G$ .

The proof uses so-called disjunctive normal form (DNF), which is $(\alpha_{11}\wedge\ldots\wedge\alpha_{1n_{1}})\vee\ldots\vee(\alpha_{k1}\wedge\ldots\wedge\alpha_{kn_{k}})$ where each $\alpha_{ij}$ is either a sentence symbol or the negation of a sentence symbol.
- The conjunctive normal form (CNF) is the conjunction of disjunctions, and can be obtained from the DNF of $\neg\alpha$ by substituting for all sentence symbols their negations, and replacing $\wedge$ with $\vee$ and vice versa.
Therefore, the set of connective symbols $\{\wedge,\vee,\neg\}$ is complete.

$n$	Symbol	Description
$0$	$\bot$	$F$
	$\top$	$T$
$1$	$A$	identity
	$\neg$	negation
$2$	$\wedge$	conjunction; and
	$\vee$	disjunction; or (inclusive)
	$\rightarrow$	conditional
	$\leftrightarrow$	biconditional
	$\leftarrow$	reversed conditional
	$+$	exclusive or
	$\downarrow$	nor=neither nor
	$\vert$	nand=not both
	$<$	less than
	$>$	greater than

Completeness of sets of connective symbols

Binary connective symbols.

Among the 10 really binary connective symbols, $\{\neg,\square\}$ is complete for $\square\in\{\wedge,\vee,\rightarrow,\leftarrow,\downarrow,\vert,<,>\}$ , and is not complete for $\square\in\{\leftrightarrow,+\}$ .
At the same time, $\{\wedge,\vee,\rightarrow,\leftarrow,\leftrightarrow\}$ and $\{\neg,\leftrightarrow,+,\bot,\top\}$ are not complete.
More minimal (independent) complete sets of connective symbols: $\{\downarrow\}$ , $\{\vert\}$ (the only two connective symbols complete by themselves), $\{\rightarrow,\bot\}$ , and $\{\wedge,\leftrightarrow,+\}$ .

Ternary connective symbols.

$\{\#\}$ , $\{\#,\bot\}$ and even $\{\neg,\#\}$ are not complete, where $\#$ is the majority rule.
$\{M\}$ and $\{\neg,M\}$ are not complete, but $\{M,\bot\}$ is complete, where $M$ is the minority rule.
More minimal (independent) complete sets of connective symbols: $\{[\alpha[\beta]\gamma],\top,\bot\}$ (where the first one is “if $\beta$ then $\alpha$ ,
otherwise $\gamma$ ”), and $\{\wedge,+^{3},\bot,\top\}$ .
- There is no set of connectives of size $5$ or more that is both complete and independent (due to Post).

Resolution on

For wff $\alpha$ , we define $\alpha_{*}^{A}=\alpha_{\top}^{A}\vee\alpha_{\bot}^{A}$ where $\alpha_{\square}^{A}$ , $\square\in\{T,F\}$ , is defined by substituting $\square$ for $A$ in $\alpha$ . Then $\alpha\vDash\alpha_{*}^{A}\vDash\beta$ for every $\beta$ not using $A$ such that $\alpha\vDash\beta$ . That is, $\alpha_{*}^{A}$ is best we can say is true knowing $\alpha$ is true without using sentence symbol $A$ . Moreover, $\alpha$ is satisfiable iff $\alpha_{*}^{A}$ is satisfiable.

This also implies that for $\alpha\vDash\beta$ there exists $\gamma$ using only symbols found both in $\alpha$ and $\beta$ such that $\alpha\vDash\gamma\vDash\beta$ .
This latter fact (the previous bullet point) is also true in the first-order logic (studied in the next chapter), but the proof is different, as there is no analogue of $\alpha_{*}^{A}$ in the first-order logic.

Subpages

Section 1.5: Sentential Connectives

Section 1.5: Sentential Connectives

Completeness of sets of connective symbols

Resolution on A

Resolution on