How many n ary truth functions

It is not minimally functionally complete because and are inter-definable. But it is functionally complete. Thus, showing that one can define these functions suffices for achieving functional completeness.

Definability should be thought as logical equivalence: one connective can be defined by means of others if and only if the formulas in the definition what is defined and what is doing the defining are logically equivalent. Presuppose the truth-tabular definitions of the connectives.

Russell was not aware that Peirce had already made the discovery in the 19 century. Prompted by this applause and urged on by the weight of renewed expectations, Sheffer, who was not a prolific author, returned to the task of taking further advantage of his discovery, but he did not succeed in advancing beyond his initial contribution.

Two other influential authors of an early logic textbook, David Hilbert and Wilhelm Ackermann, regarded this development as a rather unimpressive detail. No doubt, one reason is that a system that would have only the Sheffer Stroke as its connective would require use of unwieldy formulaic expressions. Abbreviation conventions would be needed, at a minimum.

Because one wants to be able to refer to other logical connectives besides the Sheffer Stroke, one actually lays out an expanded variant of SPL, which is called here SPLexp. The next goal is to obtain ML symbols from the OL, and this is done without danger of ambiguity because the context makes clear whether OL or ML is employed.

As is customary, when symbols are mentioned rather than used, they are placed within quotation marks. The formal language SPLexp has symbolic resources for single or atomic propositional variables up to the infinity of the natural numbers , and for logical connectives. It also has auxiliary symbols, and parentheses to be used only for the sake of preventing ambiguity of well-formed expressions.

For connectives, the expansive idiom includes symbols for all definable unary and binary connectives of the standard propositional logic. For present purposes, there is no need to supply names for all the definable connectives denoted by these symbols.

Definitions of the connectives are given by means of the familiar truth table. In brief,. N is the set of natural numbers. Symbols from the object language are appropriated, trusting that the context removes ambiguity. In general, if n is the number of inputs to the connective, the number of mathematically definable n-ary connectives in standard propositional logic is 2 raised to the n power.

An examination of the properties of the Sheffer Stroke begins after having the formal idiom SPLexp in place. Introductory logic textbooks usually omit references to the special properties of the Sheffer Stroke; more advanced logic texts and mathematical logic or metalogic texts always make special mention of this connective and of its dual, the NOR or Peirce Arrow connective.

The student of logic learns that the Sheffer Stroke or NAND, like NOR, has a remarkable characteristic that is called functional completeness or expressive completeness. No connective of lesser arity thus, zeroary or unary has this property, either. When alternative logics are investigated, a fundamental metalogical task consists in querying the existence of functionally complete functions, which may be called Sheffer Functions.

Present observations are limited to what is known as standard sometimes called classical logic: when it comes to alternative or non-classical logics, the connective defined as negation of conjunction should not be presumed to have the property of functional completeness. It should be borne in mind that negation and conjunction themselves have different, non-standard, meanings in alternative logics since they are defined over more than the two truth values of standard logic.

After defining functional completeness, it will be shown that indeed the Sheffer Stroke or NAND possesses this remarkable property. One needs to ask also why this is the case and why this is an important characteristic.

Roughly, what this means is that a complete system, and only a complete system, will have failures of proof or failures of derivation in all the cases, and only in the cases, in which one expects the corresponding semantical language to be failing in establishing semantic conclusions or logical truths.

Think of a logical truth as a semantical conclusion of any, including the empty, set of premises. A logical connective of a formal language is functionally complete with respect to if and only if every mathematically definable logical connective of can be defined in terms only of.

For the case of a binary connective that is functionally complete, all mathematically definable connectives can be defined by using only propositional variables and the connective. If one wants to define functional completeness in terms of the familiar semantic device of the truth table, one can do so in the following way:.

For example, this can be done by using only the Sheffer Stroke symbol, , for certain familiar connectives of the standard propositional logic. Two truth tables are considered identical if they agree on all the truth value outputs corresponding to the same valuations truth value assignments as inputs.

The non-trivial question now faced is whether such functionally complete connectives are definable and how high one has to ascend in arity to unary, binary, and so on before finding a functionally complete connective. The answer is that one can stop at the level of binary connectives in the case of the standard two-valued logic: the Sheffer functions the Sheffer Stroke and NOR are, each, functionally complete.

The details are examined below. One can also define functional completeness as a property of groups or sets of connectives. Sometimes one finds references to functional completeness as a property of systems of connectives. A set of connectives is functionally complete with respect to a formal language if and only if every mathematically definable connective of can be defined by using only members of. Such a set is then itself a member of the set of functionally complete sets of the language,.

This means that the one-member set singleton set with the Sheffer Stroke as its only member is a functionally complete set or is a member of the set of functionally complete sets. Of special interest is a proper subset of the functionally complete sets of connectives : sets that are minimally or non-redundantly functionally complete,. Here is what this means. A set of logical connectives is minimally functionally complete MFC if and only if it is functionally complete FC and also it is the case that no connective in the set can be defined by using other connectives in the set.

If so, then each connective in the set is independent of the other connectives or simply independent. This set is functionally complete. Since it has only one member, this set has to be MFC minimally functionally complete if it is FC functionally complete.

This is because there is only one connective; so, it is impossible for it to be defined in terms of other connectives in the set: this connective has to be independent! There are exactly two such MFC singletons in standard propositional logic up to binary connectives :. This section concludes by highlighting certain other properties possessed by the Sheffer Stroke connective.

This is done because having those properties is the underlying reason that the Sheffer Stroke connective is functionally complete. This brief investigation of those properties and of how they are related to functional completeness encapsulates the results established by the mathematicians Emil Post , and William Wernick Before examining the relationship between functional completeness and certain other logical properties of the Sheffer Stroke, there is a straightforward way of establishing that.

To do this, consider how one can use the truth-tabular definition of any connective to extract its Disjunctive Normal Form DNF. Here is an example. The same can be done with any connective regardless of its arity. This example is of a ternary or three-place connective. Extra columns are added to the truth table for illustrative purposes.

In these columns the truth values of the individual propositional variables are traced across the rows in which the connective receives T as its truth value; then, it is shown how the DNF is formed. The method is this: form conjunctions of the atomic propositional variables across each row in which the connective receives the truth value T; the variables are written as seen in the added row of the example.

Then form the inclusive disjunction of the conjunctions constructed in the previous step. Based on this truth table and the DNF that can be obtained, the definition of this connective in DNF could be given as follows:.

Note omission of outer parentheses. This includes the unary connectives. First, notice that negation is included in the set. The other three unary connectives are also definable as shown below. And when it comes to connectives of arity , the truth table shows the way to define them by using only connectives from the set , as above. There is redundancy in it because the connectives conjunction and inclusive disjunction are inter-definable as can be seen in light of the following so-called DeMorgan equivalences:.

The following two sets are not only FC functionally complete but also MFC minimally functionally complete :.

Now consider the Sheffer Stroke. In order to show that the set is FC, show that negation and either conjunction or inclusive disjunction are definable in terms of the Sheffer Stroke.

Because and are, each, functionally complete, if the symbolized connectives in any one of these sets are definable in terms of the connective in , then this latter set also must be functionally complete. It can be shown that, indeed, negation and inclusive disjunction, as well as conjunction, are definable in terms of the Sheffer Stroke. The truth table method can be used to verify that the following equivalences indeed obtain:.

These equivalences can be justified in another way. Taking advantage of certain valid equivalences of the standard propositional logic, which are used to make replacements of phrases by their equivalents without alteration to truth value, one has:. Emil Post , ; see also Pelletier and Martin, showed that any set of definable logical connectives of the standard propositional logic is functionally complete if and only if is not a subset of any of the following sets of connectives:.

If one single logical connective is to be functionally complete by itself or if the singleton set with the function symbolized by as its only member is functionally complete , then the function must lack all of the above properties of connectives. In other words,. After briefly defining these interesting properties, it can be shown that, among definable binary connectives, only the Sheffer functions the Sheffer Stroke or NAND and the Peirce Arrow or NOR lack all of those properties when one considers all the definable unary and binary connectives of the standard propositional logic.

If one is examining a set of functions to determine whether it is functionally complete, check that there is at least one function in the set, which lacks one of the above properties; and perform this check for each property. So, one needs to ensure that, for each of the properties above, there is at least one function that lacks this property.

One can engage briefly the deeper analysis behind this seminal result, which can be called the Post Result while the test presented above can be called the Post Test : All the enumerated properties are so-called Hereditary Properties. This means that if a function or corresponding semantic connective has a property like this, then all functions that can be defined by using only must also have this property. But these hereditary properties are not characteristic of all definable functions.

In other words, there are definable functions that lack , for each hereditary property. A function that can indeed define, just by itself, all definable functions should not have any one of the hereditary properties because, if it had any such property, it would necessarily transmit it to every function it defines; but, then, the function could not define functions that lack this property.

Consider the case of binary functions, given the present inquiry. Note that these definitions of properties apply for n-ary functions in general. Note also that the two truth values. The table makes this point:. What does this mean in our case of binary logical connectives? There is a test, which follows from this definition, for determining whether a given binary connective is monotonic or not.

The test goes like this. This diagram arranges the pairs of truth values so that the arrows show the ordering just talked about. Next, write as a superscript for each pair of input values the truth value taken by the connective for that pair. For instance, for conjunction one has. There is failure of monotonicity if and only if there is at least one case in which one can proceed down the arrows from a T to an F superscript. This type of diagram is used below to show that the Sheffer Stroke is non-monotonic.

Since there are instances in which there is a shift in truth value of the connective from T to F as one goes down the red arrows, one can infer that this connective is not monotonic. The Sheffer Stroke is not among them. Likewise, the Sheffer Stroke fails to be included among the other types of connectives identified above. A logical connective is linear also called countable, counting, or affine if and only if it is the case that either all or none of the propositional inputs affect the truth value of the output.

This means that for a linear connective, and only in the case of such a connective, for each of its inputs, changing the value of the input results in one of the following two cases: either the output value always changes or it never changes. For present purposes, concentrate on unary and binary connectives and proceed straight to presenting a test that can be used to determine whether a connective is linear or not.

Here is how the test works: Check the cases in which the connectives takes T as its truth value. Call these the T-cases. Similarly, call the rest the F-cases. Then count the number of input variables that take T. If, and only if, the connective is linear, this number is always even for the T-cases and odd for the F-cases, or it is always odd for T-cases and even for the F-cases.

One can show that this is not the case for the Sheffer Stroke. Hence, the Sheffer Stroke is not countable. The rule is violated. The input variables that take T are even when the connective takes T as its truth value; but for the cases in which the connective takes F as its truth value, there is a mixture of even and odd numbers of input variables that are T.

Hence, the Sheffer Stroke is not a linear connective. The linear unary and binary connectives are as follows, and the Sheffer Stroke, again, is not among them. Consider the case of unary and binary connectives. The dual of a unary or binary connective, and respectively, can be defined as follows:.

Now, a connective has the property of self-duality if and only if it is its own dual. It is not among the members of the set of self-dual unary and binary connectives of the standard propositional logic. Finally, consider the two remaining properties of connectives, of interest for these purposes: truth-preservation and falsehood-preservation.

It can be shown again that the Sheffer Stroke lacks these properties as well. A connective is truth-preserving if and only if it yields the truth value T for all cases in which all its variable inputs are T. A connective is falsehood-preserving if and only if it yields the truth value F for all cases in which all its variable inputs are F.

The truth-preserving and falsehood-preserving unary and binary connectives of the standard propositional logic are given below, and, once again, the Sheffer Stroke is not among them.

The same tests could be applied on the other Sheffer function, the NOR connective, to show that this connective is also excluded from all these sets. No other unary or binary connectives would be excluded from all these sets. Therefore, the Sheffer Stroke and NOR are functionally complete and are the only connectives among unary and binary connectives that are functionally complete. It can be shown that any logical connective, regardless of arity, is functionally complete if it has a property that is called complete symmetry.

It can then be ascertained that no unary connectives have this property and that the only binary connectives that have the property are the two Sheffer functions. A binary logical connective is completely symmetrical if and only if the following conditions hold. In the literature, other functionally complete connectives or, rather, their associated Boolean functions are also called Sheffer functions. This applies in the case of non-standard or alternative logics, but these fall outside the scope of this article.

In the case of the standard propositional logic, a Sheffer function is a function of any arity n n 2 that is, taken by itself, functionally complete.

The relevant fact to consider is this: Regardless of arity, a connective is functionally complete if it is completely symmetrical. This result applies only in the case of the standard two-valued propositional logic. The definition of a completely symmetrical n-ary connective is now given:. Here is a suggestive sketch of a proof of the fact that is functionally complete insofar as it is completely symmetrical. Assume a completely symmetrical n-ary connective,. Now, take the case of the truth table that can be constructed for.

This truth table must have only four rows, since there are exactly two propositional variables; it will have n columns since the function is n-ary. This yields exactly two cases: one in which the two truth values are T and one case in which the two truth values are both F.

The first case has the truth table for the Sheffer Stroke; the second case has the truth table for the NOR connective. In either case, the connective can be defined in terms of a functionally complete connective either the Sheffer Stroke or NOR. Accordingly, every definable function can be defined in terms of since is itself definable in terms of a functionally complete connective.

This shows that is itself functionally complete. Apply the Post Test to determine whether a given set of functions is functionally complete,which means that by using only the functions in the set, all mathematically possible functions of the formal language can be defined. There are examples of sets of functions of the standard propositional logic, which are functionally complete, and one can see how the members of these sets lack, taken together, the hereditary properties discussed above. The Sheffer Stroke, and the Peirce Arrow, lack all those properties; therefore, the one-member sets that have as their single members the Sheffer Stroke or the Peirce Arrow are functionally complete.

On the other hand, some sets are not functionally complete because some of the identified hereditary properties are not lacked by any one function in the given set. It can be shown that the Sheffer Stroke possesses the property of functional completeness by examining its polynomial representation, which were introduced in section 1a; and the result is:.

Linearity can be defined for the polynomial representations of the functions as absence of any multiplicational products from the polynomial.

This also means that all definable unary functions are linear since they have the general form. So, no unary function can be functionally complete since it has to be linear. By examining the polynomial representation of the Sheffer Stroke we see that it is non-linear as it has a multiplicative product in it. Therefore, it lacks the hereditary property of linearity. Next, establish that the Sheffer Stroke is not self-dual. For a binary function in polynomial form, the self-duality condition can be given as follows.

In fact, the dual of the Sheffer Stroke is the other binary function that is functionally complete, the Peirce Arrow, whose polynomial representation is indeed:. Finally, it can be shown that the Sheffer Stroke is not truth-preserving and is not falsehood-preserving. The significance of the Sheffer Stroke connective for mathematical logic and metalogic the study of formal systems of logic is evident from the observations made in the preceding section regarding the properties of this connective.

Those properties are shared by its dual, the NOR connective. These two connectives are the only binary connectives that are functionally or expressively complete. They are also the first such connectives discovered to have this property as one ascends from zeroary or unary connectives.

Examination of such properties belongs to what is known as Metalogic sometimes called Metatheory. The possibility of economizing in the use of theoretical resources is greatly appealing to mathematicians and scientists. What is claimed is simply that parsimony or economy of resources is a methodological and theoretical requirement that good theories must meet. Formal systems of logic, and formal languages, have expressive resources that are symbolic.

Economic use of those resources means using in the construction and implementation of the theory as few such resources as is possible without loss of any systemic powers of expression.

Ideally, economy dictates that only one resource of a certain kind is to be used, if such a resource is available or definable and is effective in the construction of all the remaining expressive resources. For the reduction to be effective, of course, it must be the case that all other connectives of any arity must be definable in terms of the single connective symbol; in this way all the other connectives can be eliminated as expressive resources without causing a loss of the ability to express what those symbols refer to.

The advantages obtained from reduction of resources can be concrete in the case of implementations or applications of formal systems. For instance, in the construction of logic gates in electronic circuitry, the gate-types NAND and NOR are the electronic-theoretical interpretations of the same Boolean functions that are propositionally interpreted as the Sheffer connectives.

Discoveries of this kind signal that a reduction in complexity is feasible, and this result can have economic and design advantages. In practice, the advantage claimed from this reduction is outweighed by the fact that writing out well-formed expressions becomes prohibitively unwieldy if only one kind of connective symbol is used. One can think of this challenge as posing a trade-off between economy of resources and notational convenience.

Or the trade-off is between reducing the type of resource for instance, gate used and needed, on the one hand, and the length or extension of the constructions that will have to be made, on the other.

The notational version being used in this way is significantly more unwieldy than a notational version a grammar that uses more, not fewer, connective symbols. Consider the formula. It is possible to adopt conventions that remove its complexity to some degree. On the other hand, two other pioneering writers of logic textbooks, Hilbert and Ackermann, were unimpressed and reported on the Sheffer Stroke as if they were referring to trivia. Certainly, the Sheffer functions do not add to the logical system of standard propositional logic in any way.

The simplification they make possible is an internal matter. If there are other logics for which, hypothetically, Sheffer functions are not available, this does not automatically mean that there is something wrong with those other systems insofar as they are assessed as formally constructed languages.

It was the influential thinker Ludwig Wittgenstein who attributed far-reaching significance to the fact that Sheffer functions are available. He did this in a somewhat obscure fashion in an influential logical-philosophical work. In his Tractatus Logico-Philosophicus , 5. It is not clear that Wittgenstein knew that there are two binary functions with the same property of being functionally complete.

Wittgenstein uses a rather eccentric function, known in the literature as the N-operator , which has attracted attention and even led to disputes.

A technical study of the subject is given by Soames ; see also Geach, Because the language that is needed is that of first-order or predicate logic, a propositional variable atom is a predicate symbol, of any arity n, accompanied by n individual constants all of which have as specified referents members of the universe of discourse or domain.

Consider a grammar that comprises symbol letters for 22, individual constants, predicate non-logical constants, and the operator symbol. Instead he legislates:. This means that the N-operator can be defined through the following logical equivalences insofar as the additional symbols are allowed in the metalanguage. Take, as example, the case of a unary predicate constant:.

The symbolic language cannot sort out more than one individual variable within the scope of another variable. It can express a formula like the following:. Sign up to join this community. The best answers are voted up and rise to the top. Stack Overflow for Teams — Collaborate and share knowledge with a private group.

Create a free Team What is Teams? Learn more. Asked 5 years ago. Active 4 years, 8 months ago. Viewed times. Bram28 Staki42 Staki42 2, 9 9 silver badges 25 25 bronze badges. Add a comment. Active Oldest Votes. And finally, no, I don't think induction makes this any easier. Bram28 Bram28 I've actually considered solving this like you before, but is there any way how to write that down formally correct?

Or does it, in this case, suffice for a correct proof to "describe" the process like you did? I'll se when it's corrected. Sign up or log in Sign up using Google. Sign up using Facebook.