Section 1.5: Problem 1 Solution »

Section 1.5: Sentential Connectives

A -place Boolean function is a function from to .
  • For convenience, -place Boolean functions are and .
  • Every wff defines (realizes) a boolean function: where .
  • For , iff (assuming ), and iff .
If is an -place Boolean function, , then there is a wff such that .
  • The proof uses so-called disjunctive normal form (DNF), which is where each 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 by substituting for all sentence symbols their negations, and replacing with and vice versa.
  • Therefore, the set of connective symbols is complete.
Symbol Description
conjunction; and
disjunction; or (inclusive)
reversed conditional
exclusive or
nor=neither nor
nand=not both
less than
greater than

Completeness of sets of connective symbols

Binary connective symbols.
  • Among the 10 really binary connective symbols, is complete for , and is not complete for .
  • At the same time, and are not complete.
  • More minimal (independent) complete sets of connective symbols: , (the only two connective symbols complete by themselves), , and .
Ternary connective symbols.
  • , and even are not complete, where is the majority rule.
  • and are not complete, but is complete, where is the minority rule.
  • More minimal (independent) complete sets of connective symbols: (where the first one is “if then , otherwise ”), and .
    • There is no set of connectives of size or more that is both complete and independent (due to Post).

Resolution on

For wff , we define where , , is defined by substituting for in . Then for every not using such that . That is, is best we can say is true knowing is true without using sentence symbol . Moreover, is satisfiable iff is satisfiable.
  • This also implies that for there exists using only symbols found both in and such that .
  • 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 in the first-order logic.