Formal Logic/Sentential Logic/Expressibility

← Validity ↑ Sentential Logic Properties of Sentential Connectives →



Expressibility

edit

Formula truth tables

edit

A formula with n sentence letters requires   lines in its truth table. And, for a truth table of m lines, there are   possible formulas. Thus, for a sentence of n letters,   and the number of possible formulas is  .

For example, there are four possible formulas of one sentence letter (requiring a two-line truth table) and 16 possible formulas of two sentence letters (requiring a four-line truth table). We illustrate this with the following tables. The numbered columns represent the different possibilities for the column of a main connective.

 
  (i) (ii) (iii) (iv)
T T T F F
F T F T F

Column (iii) is the negation formula presented earlier.

 
    (i) (ii) (iii) (iv) (v) (vi) (vii) (viii) (ix) (x) (xi) (xii) (xiii) (xiv) (xv) (xvi)
T T T T T T T T T T F F F F F F F F
T F T T T T F F F F T T T T F F F F
F T T T F F T T F F T T F F T T F F
F F T F T F T F T F T F T F T F T F

Column (ii) represents the formula for disjunction, column (v) represents conditional, column (vii) represents biconditional, and column (viii) represents conjunction.

Expressing arbitrary formulas

edit

The question arises whether we have enough connectives to represent all the formulas of any number of sentence letters. Remember that each row represents one valuation. We can express that valuation by conjoining sentence letters assigned True under that valuation and negations of sentence letters assigned false under that valuation. The four valuations of the second table above can be expressed as

 
 
 
 

Now we can express an arbitrary formula by disjoining the valuations under which the formula has the value true. For example, we can express column (x) with:

(1)       

You can confirm by completing the truth table that this produces the desired result. The formula is true when either (a)   is true and   is false or (b)   is false and   is true. There is an easier way to express this same formula:  . Coming up with a simple way to express an arbitrary formula may require insight, but at least we have an automatic mechanism for finding some way to express it.

Now consider a second example. We want to express a formula of  ,  , and  , and we want this to be true under (and only under) the following three valuations.

      (i)   (ii)   (iii)
      True   False   False
      True   True   False
      False   False   True


We can express the three conditions which yield true as

 
 
 

Now we need to say that either the first condition holds or that the second condition holds or that the third condition holds:

(2)       

You can verify by a truth table that it yields the desired result, that the formula is true in just the interpretation above.

This technique for expressing arbitrary formulas does not work for formulas evaluating to False in every interpretation. We need at least one interpretation yielding True in order to get the formula started. However, we can use any tautologically false formula to express such formulas.   will suffice.

Normal forms

edit

A normal form provides a standardized rule of expression where any formula is equivalent to one which conforms to the rule. It will be useful in the following to define a literal as a sentence letter or its negation (e.g.  , and   as well as  , and  ).

Disjunctive normal form

edit

We say a formula is in disjunctive normal form if it is a disjunction of conjunctions of literals. An example is  . For the purpose of this definition we admit so called degenerate disjunctions and conjunctions of only one disjunct or conjunct. Thus we count   as being in disjunctive normal form because it is a degenerate (one-place) disjunction of a degenerate (one-place) conjunction. The degeneracy can be removed by converting it to the equivalent formula  . We also admit many-place disjunctions and conjunctions for the purposes of this definition, such as  . A method for finding the disjunctive normal form of a arbitrary formula is shown above.

Conjunctive normal form

edit

There is another common normal form in sentential logic, namely conjunctive normal form. A formula is in conjunctive normal form if it is a conjunction of disjunctions of literals. An example is  . Again, we can express arbitrary formulas in conjunctive normal form. First, take the valuations for which the formula evaluates to False. For each such valuation, form a disjunction of sentence letters the valuation assigns False together with the negations of sentence letters the valuation assign true. For the valuation

    :    False
    :    True
    :    False

we form the disjunction

 

The conjunctive normal form expression of an arbitrary formula is the conjunction of all such disjunctions matching the interpretations for which the formula evaluates to false. The conjunctive normal form equivalent of (1) above is

 

The conjunctive normal form equivalent of (2) above is

 

Interdefinability of connectives

edit

Negation and conjunction are sufficient to express the other three connectives and indeed any arbitrary formula.

           
           
                     


Negation and disjunction are sufficient to express the other three connectives and indeed any arbitrary formula.

           
           
                     


Negation and conditional are sufficient to express the other three connectives and indeed any arbitrary formula.

           
           
                     

Negation and biconditional are not sufficient to express the other three connectives.

Joint and alternative denials

edit

We have seen that three pairs of connectives are each jointly sufficient to express any arbitrary formula. The question arises, is it possible to express any arbitrary formula with just one connective? The answer is yes, but not with any of our connectives. There are two possible binary connectives each of which, if added to  , would be sufficient.

Alternative denial

edit

Alternative denial, sometimes called NAND. The usual symbol for this is called the Sheffer stroke, written as   (some authors use ↑). Temporarily add the symbol   to   and let   be True when at least one of   or   is false. It has the truth table :

 
     
T T F
T F T
F T T
F F T

We now have the following equivalences.

           
           
           
           
           

Joint denial

edit

Joint denial, sometimes called NOR. Temporarily add the symbol   to   and let   be True when both   and   are false. It has the truth table :

 
     
T T F
T F F
F T F
F F T

We now have the following equivalences.

           
           
           
           
           


← Validity ↑ Sentential Logic Properties of Sentential Connectives →