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 socalled 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  
identity  
negation  
conjunction; and  
disjunction; or (inclusive)  
conditional  
biconditional  
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 firstorder logic (studied in the next chapter), but the proof is different, as there is no analogue of in the firstorder logic.