Section 1.5: Problem 1 Solution »

# 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 ”), 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.