In a message dated 1/12/2002 7:56:11 PM Central Standard Time, thinkit8@lycos.com writes:Now in general a truth table or x arguments is 2^(2^x), 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. |