Subject: Re: [lojban] multiple logical connectives

From: [email-masked]
Date: Sun, 13 Jan 2002 16:59:14 EST

In a message dated 1/12/2002 7:56:11 PM Central Standard Time, 
[email-masked] writes:

> Now in general a truth table or x arguments is 2^(2^x), 
> right?
A bit abbreviated, but an x-placed connective (or any compound of x component 
sentences) requires 2^x lines to consider when each sentential component can 
take on one of two truth values. Since on each given line the compound or 
connective can take on again one of those two values, there are 2^(2^x) 
different truth functions (compounds or connextives) of x components.

<Repeated connectives give you 16^(x-1)>
I gather this means that combining x components with connectives, without 
repetition of components -- or changes of order or grouping, gives you this 
many compounds. This is correct again (for x> 1), though changes of order 
and grouping give more, while equivalences among apparently different forms 
reduces the number. I don't off-hand remember whether there is a formula for 
how many distinct ones you get in this way or not, and, if there is, what it 
is. In any case, it is generally smaller than the number of possible truth 
functions of that many arguments -- and always is for x>2.

<My question is, for x=3, can the connectives give you the full 
trutch table?>

Yes -- indeed for any number the set of 2-place connectives (indeed just AND 
and NOT or just OR and NOT or either NAND or NOR by itself) is sufficient for 
all connectives of any number of components. BUT many cases at each level 
will require that some components be repeated. There are, in fact, several 
kinds of normal forms the (at the cost of considerable repetition) can 
construct the defining expression for any function directly from the truth 
table. The simplest is disjunctive normal form, the disjunction (OR) of the 
forms representing lines on a truth table on which the function evaluates to 
True. This representation is just the conjunction (AND) of the component 
sentences or their negations depending upon whether that component is 
assigned True or False on that line. The result clearly has exactly the same 
truth table as the function in question. QED
Happily, many functions at each level have simpler definitions and quite a 
few can be defined without repetition, but they are often rather odd sorts 
and simple ones (so it seems) turn out to be rather hard. Easy 
generalizations in useful terms also are not easy to come by in many 
"natural" cases. 
Lojban has tended to get around this by taking on a "set of claims" approach 
for especially useful cases like "some three of the folowing." But these can 
-- in principle -- be done with just connectives.