Boolean
Semiotics, Reductionism,
and the
Degeneracy of Binary
J.M.Richfield
5. Underdetermination
and Boolean semantics.
6. Designational
aspects of Boolean operations.
7. Generalisations
of Boolean functions.
ABSTRACT:
In work on Boolean functions of radix greater than 2, it is usual to define them in terms of truth tables and to represent them as higher-radix generalisations of radix-2 functions such as AND or EXCLUSIVE OR. Not all such defined functions turn out to be identical, partly because, as it turns out, there are many ways to define such higher-radix functions and partly because all deviate non-trivially from the intended correspondence to lower radix functions. Discrepancies are unavoidable, as they stem from the degeneracy of low-radix operations; restriction of the number of logical states in the domain of a function reduces the capacity to distinguish semantic attributes.
Conversely, many semantic attributes which are necessarily separate in higher radices, coincide in low-radix operations. In no higher radix can one operation combine all the features of the paradoxically powerful low-radix operation. The familiar cases of semantic attributes are inseparable in given radix-2 operations, so those attributes tend to be conflated in common use. In higher radices distinctions between those semantic attributes are inescapable and this has led to confusion.
One product of this investigation is a convenient model for the philosophical concepts of generalisation, reductionism and kinds. A basis emerges for discussion of useful and pernicious aspects of these concepts.
1. Introduction
This article arose from a presentation I made in the 1990s.
Dyadic, radix-2 Boolean operations are used so widely that their nature is seldom questioned, but their familiarity does not imply the insight that non-academic users tend to assume. Their apparent barren obviosity is misleading, in spite of the increasing prominence of higher-radix logic (3). Inspection of the nature of Boolean operations reveals problems in generalisation in terms of adicity and radix, and yields models for such concepts as reductionism and generalisation. Models of such simplicity may tempt one to over-simplification in some contexts, but they offer formidable criteria for evaluation of loose use of such terms.
Mathematics and symbolic logic are only peripherally relevant to this discussion. No theorems are presented. The subject matter may prove useful in formal logic and related fields, but has more to do with semiotics and philosophy.
2. Terminology
Some more or less standard terminology of semiotics may be paraphrased as follows, but readers familiar with the field might prefer to skip this section:
SYNTACTICS dealing with the relationship between signs in a
statement; for instance:
"sum = addend + augend"
and
"addend augend + sum ="
can mean the same thing if the former uses an infix syntax and the latter uses
a postfix syntax. In this example the
sign relationship comprising the syntax consists in the relative sequence of
the signs, so that there are limits to how far one can change the sequence
without violating the syntax. Although
the syntax does not depend on the meaning, the converse is not generally true. Exchange their syntaxes, and the statements
do not in general retain their meaning.
SEMANTICS dealing with the relationship between sign and meaning;
exemplified most famously by:
"When I use a word" Humpty Dumpty said in a rather scornful tone,
"it means just what I choose it to mean... I meant by 'impenetrability' that
we've had enough of that subject." Assignment
of meaning to a sign is essentially arbitrary.
As with any arbitrary relationship, a convention is needed if the
relationship is to be of use in communication.
Alice
had had to ask what Humpty Dumpty meant.
In Swift's description of the Grand Academy of Lagado (4), is what looks like an attempt to avoid the problems of semantics entirely: "a scheme for entirely abolishing all words whatsoever... since words are only names for things, it would be more convenient for men to carry about them such things as were necessary to express the particular business they are to discourse on... Another great advantage proposed by this invention was that it would serve as a universal language..."
One problem with this pioneering view of the medium as the message, is that any material designatum has many more attributes than are intended in most utterances. This introduces ambiguity. It can be difficult to know what is intended when one is presented with a lump of lead: metal? lead? something heavy? poison? In short, semantics is not mocked.
EMPIRICS dealing with the relationship between signs and the communication
medium.
For instance, a certain woman did not know whether to laugh or cry when she
received a letter about her brother. The
handwriting was very bad and the ink had run and if a certain letter was an
"o", he was reported to have shot himself. Stamper (1) describes empirics as focussing
on "... issues facing a designer of equipment used for handling signs. Empirics grew out of the work of
telecommunications engineers." The
more abstract view I take sits better with the current topic.
PRAGMATICS dealing with the relationship between signs and communicators;
concise and unambiguous examples are hard to give, as pragmatics lends itself
poorly to formal treatment. This
suggests that the field is a conglomeration and in need of radical
dissection. One melodramatic examples might
be the difference of effect on the recipient of a message in the form of a
flickering light, depending on whether or not he is subject to flicker
epilepsy. For another, consider an
intended compliment: "You are deliciously chubby." This might be clearly audible and
syntactically and semantically flawless, yet fail utterly with a girl who had
been trying to lose weight.
In substance, this description is due partly to Stamper (1) but emphasises a more analytic approach to the subject, as exemplified in the definition of empirics.
The paraphrase of these four aspects of semiotics deviates in some ways from the spirit of Carnap (2), who regarded pragmatics as the most global aspect of linguistic communications, semantics as being semiotics abstracted from the user, and syntax as being semiotics abstracted also from meaning. In the present discussion, the terminology and conceptual structure amount to an extension and adjustment of classic concepts of semiotics to accord with information theory and metalogic. One might argue about how far this extension is justified, but the concepts are useful in suitable contexts. In the discussion the generalisation is developed even further. Some conventional terminology is retained for convenience in unfamiliar roles.
The following terms either are coined, or are not used according to usual convention, or otherwise merit discussion:
SYMBOLICS deals with the relationship between semantics of a symbol and its physical manifestation; the choice of sign in which a meaning is conveyed is a matter of symbolics. It may be written in a choice of scripts or colours, or conveyed in light or sound. Considerations of symbolics arise in high relief in some sets of Chinese (and perhaps in other ideographic languages) in which a single graphic symbol may represent the same concept in all the languages, but each language uses a different spoken word for the same concept. Stamper would regard this as an aspect of syntactics, but in the present context the distinction is useful.
The DESIGNATUM of a sign is that entity signified or designated by the sign. The rather clumsy term and its derivatives are adopted from Carnap (2) in preference to coining more felicitous but less familiar terms. In the literature there are several other terms with essentially the same meaning, as writers on the subject have been prolific in coining equivalent terminology. Cynical comment on the pragmatic implications might be out of place here.
Carnap uses the term "designatum" in a looser sense than some of his contemporaries; for instance, he permits a sentence to "designate" a proposition. This raises no difficulties in this paper and I place no restriction on such terminology, though it leads into some hazardous territory. For instance, a circumlocution does not normally count as a sign or designator; to deduce from the fact that the cube root of the mass of a given planet is that of Venus and that therefore Venus is the planet under discussion, is not the common way we refer to Venus. The fact that one could construct a convention to do so is of little interest here. However, names such as "the morning star" (ignoring the fact that technically Mercury is sometimes a morning star, or that for Martians Earth would be a more prominent morning star), or Sol II, Venus, or Ishtar, as used to indicate the planet, all have the same planet as designatum in that context.
The DESIGNATIONAL SET of a given designatum, is the set, not of logical necessity finite or even well-defined, of all signs, irrespective of medium or language, which signify that designatum in context. Whether two instances of the same sign should count as two separate elements of the designational set, is not a question addressed here.
A DESIGNATIONAL ATTRIBUTE or DESIGNATIONAL ASPECT is an attribute or aspect of a designatum. Such an aspect or attribute need not be unique to a given designatum. There are certainly cases where a small set of attributes is sufficient to determine a designatum, i.e. be unique to it; some Boolean functions are easy to specify uniquely with what is apparently a single attribute. There is for example, just one radix-2 dyadic function that corresponds to logical non-equivalence, though, as I will show, that function turns out to have many other attributes. Conversely, such an apparently atomic attribute will always, it seems, be decomposable into more elementary aspects which do not uniquely determine a function. Examples will be discussed later.
In most cases, restriction of the set of designational attributes of a designatum, yields a generalisation of that designatum. For example, the designatum of the astronomic sign "Venus", has many designational attributes; it is a planet, a mass, an aggregation of loose objects, a globe, a source of light (not necessarily an original source), an object orbiting between the earth and the sun, an obscurer of light, morning star, evening star; the list of the designational attributes of this entity is large (it is hard to imagine any entity with a very small set of designational attributes; in fact a good case could be made for regarding most of its aspects as arising from its relationships with other elements in the universe. For instance, for Venus to be an obscurer of light, it is necessary and sufficient that there be suitably-placed illuminators and illuminands. From this point of view, the number of attributes of an entity seems to be infinite, or at least physically large).
However, all the designational aspects here attributed to Venus also apply to Mercury, this being a consequence of generalisation, as described below.
It is an intuitively attractive idea, that any designatum can in principle be identified uniquely by a suitably chosen set of designational attributes. One might in fact argue that a hypothetical entity that cannot in principle be so identified, is not in any meaningful sense a designatum nor even an entity.
BOOLEAN OPERATION and FUNCTION are defined
in the present context in terms of a context-free
function table (truth table) in a given finite set. In practice the set is usually small, with
elements represented as integers. For examples
see especially tables 4.1 & 4.2.
The function table is adequate for unambiguous definition of a given Boolean
function, but this reductionistically ignores semantic aspects. Semantics matters little in most such cases,
but, as I will show, there are semantic aspects which become relevant when
there is any question of changing either the adicity or the radix of the
function.
An ATTRIBUTE of a Boolean function is an aspect of the relationship between the argument and function values, or between the function and its observers. For example, attributes of the dyadic, radix-2 EXCLUSIVE OR include "logical non-equivalence", "radix-2 addition" and "subtraction modulo 2". The semantic-free truth table for each of these is the same, but in the general sense it is invalid to speak of all of the attributes as being different names for the same function; it may seem valid as long as one is limited to radix-2, but that is because the radix is degenerate relative to higher radices (see below).
The ADICITY of a Boolean function is the dimension of the table defining the function. An n-ADIC function, i.e. a function taking n arguments, can be represented by an n-dimensional table. The table is exhaustive, catering for every permutation of n arguments. Also, every instance of that operation on elements of the set of possible arguments, yields an element of the same set, i.e. the set of defined operands is closed under application of the function.
Given set S, defined by its elements sharing at least set F of designational aspects, let G be a subset of F. Then:
GENERALISATION from S is the
identification of superset T of S, where T is defined by its elements sharing at least the set G of designational aspects.
T is a GENERALISATION OF S IN TERMS OF
F-G;
S is DISTINGUISHED or DIFFERENTIATED
BY F-G FROM T-S IN T.
The smaller F-G is, the
more can be asserted about S from
its inclusion in T and the more
easily can S be distinguished from T-S
in T. The power of a distinction and its converse
generalisation depend on how few attributes suffice for separations and
unifications of groups of entities. So
for instance, separation of atoms into
chemical elements according to their number of protons is a powerful means of
distinction. It is a single, sufficient
criterion. Separation of elements into
groups according to their orbitals is a fairly powerful, though less so,
involving more considerations and more qualifications. Separation of elements into stable and
radioactive classes is weak to the point of invalidity. Not only is nuclear instability poorly
correlated with atomic number, but it is a quantitative attribute and there is
no point at which one can clearly state that a given nucleus is absolutely
stable.
DECOMPOSITION refers to a designational aspect in F-G which does not disappear in a generalisation, but is DECOMPOSED into multiple, more
restrictive designational aspects which do
not coincide in each element of T-S.
For instance, consider the set of finite, continuous, open-ended straight line
segments of non-zero length: any of them can be divided into two open subsegments
at any single point. Generalise the set in terms of dimension, to include
multi-dimensional polyhedra. The new set
is now decomposible into subsets in which different means of division are
necessary, not always according to dimension; eg one can define 4-dimensional
polyhedra that can be divided at some single point, and two-dimensional
polyhedra that can not. Analogous decompositions can be defined at higher
dimensions, of course, eg divisibility by lines, planes etc.
MERGENCE or DEGENERACY are the converse of decomposition. In mergence or degeneracy some designational aspects become respectively inseparable or meaningless. So, we see, in two dimensions all polyhedra degenerate into polygons and can be divided by straight lines, and in one dimension polyhedra degenerate into lines and each can be divided by a single point. In zero dimensions degeneracy reduces polyhedra into a single point and the distinctions between, say, circles and cubes disappears.
AMBIGUATION is when a designational aspect which distinguishes one subset in S in terms of other aspects, occurs in
various subsets in T, so that a term
of distinction in S becomes ambiguous in T and further designational aspects
become necessary for distinction.
For example, in the set of arthropods, true flight distinguishes certain
insects from the rest of the arthropods, since bees can fly but lobsters and
lice cannot, but in generalising the set (say, in terms of phylum) to include the
entire kingdom of animals, flight as an attribute is ambiguated to include
certain birds and bats at least, and these are not arthropods.
Semantics is intrinsic to the complex of entity, observer and sign. This can be generalised in terms of communications and even of sentience, taking the term "observer", as in quantum theory, not to imply sentience, but merely interaction with the designatum in terms of the abstracted sign. A sign in turn, is material at least in that it obeys the laws of physics and hence of thermodynamics. Paradoxically, this applies even when the designatum of a sign has no material existence. For instance, accept as given that there exists no such thing as a gas giant planet called Bathrys inside the orbit of Mercury in this solar system. The planet Bathrys accordingly, having no material existence, is independent of the laws of thermodynamics and all other laws constraining the behaviour of material objects. Any sign which represents Bathrys, however, such as its name in this description, IS materially existent and comprises information which has certain limitations on how it may behave or be represented. For instance, every representation of the sign must involve matter or energy or both (say, sound or light or ink on paper or neurological states or the like).
Generalising semiotics in terms of signs, ie to attributes determining interactions in general, may supply attractive metaphors in other fields. The discussion at the end of the paper deals with this point.
Although semiotics does not deal with the designatum in isolation, the subject is not independent of semiotics. For one thing, apart from being intrinsically distinct, any sign or any designatum must be distinguishable from others by a suitable subset of its attributes if signs are to convey information. The assignment of signs and the ability to distinguish designata are functions of the complex of observer and designatum. For example, the same knife might be regarded as gift, totem, weapon, tool, weight, float, reflector, or what have you. Each view depends partly on intrinsic aspects and partly on the designatum's relationship to the assigner of significance.
3. Rationale
Several Boolean functions of radix greater than 2 are commonly represented as higher-radix generalisations of radix-2 operations such as AND or EXCLUSIVE OR. In so far as these operations suffice for the intended applications, this is no more than a point of terminology, but more fundamentally it is misleading in that the resulting operation is typically regarded as a say, true radix-n & (AND), rather than an ad hoc operation which happens to share a subset of the designational aspects of radix-2 &. Different authors therefore often select different higher-radix functions for nominally the same concept.
Terms such as & and º (EQUIVALENCE) are normally used in a limited and ad hoc sense, but as the requirement grows for extended concepts, the extension of the meaning of a term presents problems. If generalisation in terms of adicity and radix raised no problems, then it should be easy to define an abstract function which unmistakably defines say, &. This & should retain the bulk of its attributes as seen in dyadic radix-2, enabling the user to apply it wherever he pleases in the same way as he is used to applying it in radix-2.
Unfortunately such generalisations sacrifice many designational aspects. It turns out that low-radix operations are necessarily degenerate with respect to higher radices, in that restricting the number of states in their domain sacrifices the capacity to distinguish, or even represent, various designational aspects of the higher radix operators. This is distinct from mere quantitative reduction of the information capacity of the digits on which an operation is defined; it is not just a matter of how many distinct arguments an operation can take, but the number of different ways it can yield a function. There are also traps to increasing the adicity of a function, as many different polyadic functions can be constructed which subsume any one function of lower adicity.
Conversely, designational attributes which are necessarily separate in higher radices, may coincide in low-radix operations. In no high radix can one operation then combine all the attributes of the paradoxically powerful low-radix operation. It is impossible to generalise a Boolean operation in terms of radix, while retaining all other non-trivial designational attributes.
Also, a function-table designed to meet a requirement for some conceptually pure logical operation unavoidably entails other designational aspects. Often such aspects, extraneous or not, do not coincide in any higher-radix analogue of the function, while single aspects crop up in many distinct functions. Thus generalisation in terms of radix or adicity gives severe decomposition and ambiguation.
For lack of familiar circumstances which uncouple them, it is common to conflate distinct designational aspects which are inseparable in a given radix-2 operation. These sets of attributes form the concept of the operation as normally envisaged. On generalisation in terms of adicity and radix, they decompose and attributes incompatible in lower radices ambiguate, so that the analogy becomes tenuous and debatable. To regard & as a kind, becomes practically untenable and application of the term in high adicity or radix becomes arbitrary. In higher radices distinctions emerge between attributes which are normally regarded as equivalent. Difficulties arise which might be regarded in semiotic terms as stemming from failure to distinguish between extrinsic syntactic and intrinsic designational aspects of the functions.
A by-product of this investigation, is a convenient model for generalisation, reductionism and kinds; and a basis for discussion of the beneficial and pernicious aspects of many semiotic activities.
4. Function table notation.
In the literature, there is no uniformity in notation for function tables, much less any established notation for some concepts important in the present discussion. In the present discussion relevant points of notation include:
The digits: Given radix b, xÎb means that x is one of the symbols assigned as a radix-b digit, typically a numeral such that 0£x<b.
The function value: To specify the function for an a-adic operation W, write the argument tuples A, B... of digits, radix b, one below the other, such that:
Each possible
permutation of a radix-b digits occurs in exactly one column. This requires ba columns.
For the most part, upper case symbols represent sets or tuples and lower
case, sometimes subscripted, their members.
Below the other tuples an a+1th tuple,
the function tuple F is such
that the digit fi takes the value of the function of the
operation on the ordered column of digits above it, ai,
bi...
written:
fi=W(ai, bi,...) or fi=aibi...
The sequence of digits in A is such as to minimise the value of A, regarded as
an unsigned number in positional notation.
Subject to this restriction, the value of B is similarly minimal and so
in turn are the values of any following argument tuples. Call this the horizontal function table
notation. eg:
Table 4.1
A = 0011 (Note that the A tuple has the lowest possible
numeric value.)
B = 0101 (Note that the B tuple has the lowest possible matching value.)
F = 1101 (This function
tuple, which by way of example represents the logical
implication operation, can also be represented as a number, in this case denary 13.)
On rotation round a 45 degree axis this gives:
A B F
0 0 ½ 1
0 1 ½ 1
1 0 ½ 0
1 1 ½ 1
Here
the rows of the A, B columns form the binary counting
sequence (counting from 0 to 3 in this case) and the 13 of the logical
implication is now vertical.
Alternatively, using the digits of the argument tuples as co-ordinates, the
function tuple can be written as a ba matrix:
0 1
0½1 1
1½0 1
For any radix b and adicity a, the function tuple F is ba digits long.
Because the function tuple has the radix b, the number bba is how many such distinct
operations may be defined. It follows that any function tuple can be
represented as an unsigned number F in any
convenient notation, typically denary
Such an a-adic radix-b function, with function tuple of value F forms a triple. Together
with a symbol to represent the operation, a useful notation may represent it as
a quadruple comprising the operation symbol, the function tuple, the radix and
the adicity: (W,F,b,a), which reduces the
need to invent ad hoc symbols. However,
some of the values are usually implicit in the context and accordingly
omitted. For instance, if there is an
conventially established symbol for the operation, that symbol can replace the
first two members of the quadruple. Similarly, it is not normally necessary to
specify the adicity and radix, so that a single operation symbol is normally
all that is needed. This notation is
convenient for defining operation symbols.
For example, consider the following function tables, illustrating dyadic and
triadic, radix-2 and radix-3 functions:
Table 4.2
A = 0011
B = 0101 0 1
F = 0110 (=6) = 0½0
1 (W,6,2,2)
= (Å,2,2) = Å
½1 0 The standard exclusive or.
A = 000 111 222
B = 012 012 012 0 1 2
F = 000 010 002 (=8310) = 0½0 0 0 (W,83,3,2)
= (&,3)
1| 0
1 0 One function which
2|0
0 2 could
be defined as
ternary
dyadic &.
A = 00001111
B = 00110011 0011 (W,105,2,3) = (º,2,3)
C = 01010101 0101
F = 10000001 (=12910) = 0|1001
1½0110
To associate
these functions with operation symbols, expressions such as
(Å,6,2,2), (&,83,3,2),
and (º,129,2,3), define the symbols Å, & and º as binary dyadic EXCLUSIVE
OR, ternary dyadic AND, and
binary triadic EQUIVALENCE,
respectively. Nulladic and monadic
definitions also fit comfortably into this scheme. It may also prove desirable to use super- and
subscripts to avoid ambiguity or specify generalisation.
This is the notation used here:FWab
Such notation
can be useful for example, in comparing
2&3 , 83&3 and 113&3 as candidates for radix-3 dyadic AND.
Ad hoc
variations on the notation may be convenient.
For instance, the
co-ordinates can usually be omitted from the F matrix. Also, where a>2,
a-adic operations are
inconvenient to represent, so their a-dimensional
cubes can be decomposed into 1- or 2-dimensional tuples, typically with
higher-significance co-ordinates down the left and the minor co-ordinates
across the top.
5. Underdetermination and Boolean semantics
Semantic-free generalisation of a Boolean function defined in function table notation is a difficult concept and may not be strictly meaningful. For one thing, one might regard the mere concept of set membership as semantic, which immediately taints all forms of generalisation. Even if this view is relaxed, some semantics are implicit in such concepts as similarity of digits or large versus small digit values.
By way of compromise, for purposes of illustration, accept that semantic-free generalisation in terms of radix requires that in a higher radix function table, argument tuples that occur in a lower radix yield the same function digits as in the lower radix. This cannot dictate any other constraint on the rest of the function digits than that they be elements of the higher radix say, b+1 eg table 5.1:
Table 5.1
The scope for generalisation of radix-2 (Å,6,2,2) to (Å,F,3,2).
0011 000 111 222
0101 012 012 012
0110 01* 10* ***
The places represented by the asterisks can independently take any value in b+1, so such generalisation in terms of radix alone entails decomposition by a factor of (b+1)(b+1)a - bba, giving 243 radix-3 possibilities alone.
Generalisation in terms of adicity is even more debatable, but one scheme gives
decomposition by a factor of bba+1-b, as illustrated in table 5.2.
Table 5.2
The scope for
generalisation of radix-2 (Å,6,2,2) to (Å,F,2,3).
00001111
0011 00110011
0101 01010101
0110 0110****
The places represented by the asterisks can independently take any value in b, so such generalisation in terms of adicity alone entails decomposition by a factor of (b+1)(b+1)a - bba, giving 16 triadic possibilities alone.
By many standards these are underestimates, but the point is that even taken conservatively, when neglecting semantics, even the strictest generalisation leads to explosive decomposition.
In semantic generalisation it is on the other hand possible to describe the assigned significance of designational aspects of the function according to clear criteria for generalisation. To design an operation of given characteristics, one might construct a function table with the desired values. In practice, in the minimal radix which will support the concept in question, such semantic specifications are usually consistent with just one table. Take the example of radix-2 dyadic non-equivalence. Only (Å,6,2,2) meets the constraints, but it coincides with an operation designed to invert selected argument bits, yet another to perform subtraction and one to do addition modulo 2 in radix-2; and many others. There is no doubt that the operations separately conceived are
unavoidably identical as no other FWab will do for any of them. Nor can one tell from the argument and function values alone, which of the intentions is being fulfilled and if one were to embody the respective operations in distinct physical mechanisms, then swapping devices would not affect black-box users.
In such cases the view that users are merely exploiting distinct facilities of a redundant function is unsound, but attractive. As long as the symbolics are held constant, each user could supply every valid argument and be satisfied with every possible function. The distinction is in the designational aspect, not in the operation. In turn, specification of a designational aspect as relevant in a given context is at once a semantic and a symbolic act. Whether the semantic or symbolic aspects of the act dominate, is debatable and depends on the intent.
It is clear that design of the function amounts to the selection of one element of a finite set and definition amounts to the allocation of designational aspects on which the selected semantics are based. Freedom of choice does not include freedom from extraneous designational aspects entailed by the choice of function.
Normally this is regarded as a non-problem and the applications as equivalent, making the question meaningless, but that is a retreat to the semantic-free position. Outside observers may not see the difference between what the respective users do, but user views may be so distinct that naive users often deny the identity of the functions.
Before dismissing this as the natural and negligible consequence of dealing with bairns and fools, try the lyngo thought experiment: The languages lango, lengo, longo and lungo have identical vocabularies and syntax, ie every word in any of the languages exists in all of them and as the same part of speech. However, their semantics are completely disjoint, in that no word in any of them has a similar meaning in any other. Consequently, any intelligible utterance in one language is similarly intelligible, though not necessarily plausible, sensible or even meaningful in every other. Furthermore, assume that if and only if word w of meaning m in lango corresponds to word x of meaning m in lengo, then word w of meaning n in longo corresponds to word x of meaning n in lungo.
To meet those conditions it need not be that every concept expressed in a word in any of them occurs in every other. In fact it might be that no, some or every word in lango and lengo corresponds exactly in meaning to an equivalent in longo and therefore in lungo. It is interesting to contemplate languages with no corresponding concepts in their vocabularies, and unkind impulse tempts one to select various professional jargons and human speech as cases in point, but in this paper, it happens to be convenient to assume that all four lyngos correspond exactly in every meaning assigned to corresponding terms.
Now consider a translator from lango or longo, to lengo or lungo respectively. An observer could not prove from the process, either the import of the message or which translation were being undertaken, even if he were fluent in all four languages. It is, for example, possible for a lango/lengo translation of an intelligible and sensible statement, to seem to an observer to be an equally acceptable longo/lungo translation. While the two possible translations are mechanistically equivalent, it is reductionistic to claim that there is no more to it. Specifically, in excluding all but the mechanism of translation, that view approves the relationship beween components of the statements, but ignores the relationships between the statements and the rest of the universe. Apart from the semantics, the pragmatics could be totally different; for example, a lango/lengo command to achieve a given end, might coincide with a longo/lungo command to achieve the opposite end; let us say to make war or love, as the case might be.
Compare this matter of verbal semiotics with a bit manipulation in which the significance of the bits or their values are unstated, or with a binary device in which the states have not been assigned bit values. Imagine discovering a device of unknown application. It has two input switches whose combined states determine the state of one output switch. On inspection the following table of closed and open states emerges:
Table 5.3
Input switch A: OOCC
Input switch B: OCOC
Output switch : OCCO
Physically this is undebatable, but semantically it can equally validly be written in radix-2 notation as either:
Input switch A: 0011 or 1100
Input switch B: 0101 1010
Output switch : 0110 1001
or in truth-value terms as either:
Input
switch A: FFTT or TTFF
Input switch B: FTFT TFTF
Output switch : FTTF TFFT
each corresponding
optionally to
either of the numeric
tables.
Just as in the lyngo case, all the views shown are equally valid and describe the same underlying physical realities. But if they were therefore actually identical, then how could it be that of the numeric interpretations, some are complements of others? And that each of the numeric cases can be taken as either of the truth-value cases? To claim that the operation the device performs is the equivalence operation is exactly as valid as to claim it to be non-equivalence; but to state that therefore equivalence is nothing but non-equivalence is not persuasive. And the confusion grows as one examines other radix-2 functions in such a context. Like equivalence and non-equivalence, some functions emerge in complementary pairs from one device, but in some cases the pairs are highly non-complementary, eg ÷ (inclusive OR) and & (AND) are paired. Still more counter-intuitively perhaps, some functions are unaffected by the ambiguity and give only one result, no matter what meaning is assigned to the switch states.
These assignments are also inherently symbolic and semantic. They amount to association of symbols with designata. The following table lists the conversion of function resulting from permutation of the values assigned to binary switch states:
Table 5.4
OOOO ¾ CCCC OOOC « OCCC
OOCO « COCC OOCC = OOCC
OCOO « CCOC OCOC = OCOC
OCCO ¾ COOC COOO « CCCO
COCO = COCO CCOO = CCOO
Generalisation in terms of radix, of the assignment of significance to distinct states, rapidly increases the number of semantic options. Specifically, for b-state switches in the device, there are b! possible assignments of function.
If one allows generalisation of a function in terms of radix, but tries to retain given semantic attributes, then reductionistic problems of degeneration and decomposition arise. The novice who once resisted the notion of using the same operation for different objectives, later sneers at anyone who cannot see that the objectives are in fact identical. This is to fall into the opposite error. That the objectives are in fact distinguishable, emerges in generalisation. For example, modulus addition and subtraction are identical in radix-2 and they both generalise trivially to higher radices, but not to the same functions. Nor, because of ambiguation, can one assign a function in a given higher radix to which the lower-radix operation corresponds uniquely without added semantic information. For example, does modulus 4 addition in radix-4, correspond to modulus 4, 6 or 8 in radix-8, or modulus 12 or 16 in radix 16? Each is consistent with a designational aspect of modulus-4 addition, without invalidating the others as context-free generalisations from the radix-2 operation in which all coincide. They are simply generalised in different terms and on further generalisation into higher radices, each decomposes further.
Decomposition of semantic generalisation in terms of radix is usually more restricted than non-semantic, but it is also easier to find terms in which to generalise the semantics of the digits. For instance, a 1-bit in radix-2 can be taken to correspond to a 1- 5- or 9-digit in radix-10, as being the same digit; half the radix; or b-1. Greater creativity is not excluded, and with it, greater decomposition.
In this connection, the lyngo metaphor is by no means played out. Consider a fifth lingo, perhaps English. Having watched an otherwise uncommunicative translator between an unidentified pair of the languages and been none the better informed for our effort, we then see her translate the source text into lingo, which, in structure and vocabulary, has no simple correspondence to the other lyngos. The semantic ambiguity vanishes and it is clear that the two possible processes which had been contemplated were only identical in isolation and differed in their relationship to the rest of the universe. After, but only after, distinguishing designational aspects are established, is it possible to generalise the translation by defining what would and what would not constitute an acceptable translation into any other language.
Obviously, the possible options, once any translation has been seen, are a small subset of all possible translations, but the point is that even given full information on the translation and being able to deduce from it the full text of any other translation in the same direction, one remains practically ignorant on all points of semantic relevance. One could construct analogous cases for any number of hypothetical lyngos from two up without affecting the case except in the degree of ambiguity. Other generalisations are possible, but they are in terms of semantics. Generalisation of a message's semantics is valid in principle, but as it implies loss of the burden of the message, it is of restricted interest.
From some some points of view, semantics and symbolics are so closely associated that precise distinction between them depends on context. For instance, the choice of sign in which a meaning is conveyed without loss of information, is largely a matter of symbolics. It may be written in a choice of scripts or colours, or conveyed in light or sound. Besides, as in some Chinese languages, various sounds could be associated with a single script. The process of translation between written lyngos could be drastically affected by whether the script were idiographic or phonetic, and how far the alphabets corresponded. If one regards this as change of language then the differences are partly in the semantics, but if no change in language is recognised, then only symbolics is involved and in a sense related more closely to syntactics than semantics. In such a view, lango, lengo, longo and lungo are one language in various symbolic states. Whether lingo is included in the set depends on how much its differences in structure interfere with the conservation of information in the process of translation. It seems fairly clear that when a message in one medium cannot be conveyed in another medium without rephrasing if at all, then more than just symbolics is involved. But when symbols correspond exactly, correct distinction between semantics and symbolics becomes a question of semantics.
It is particularly important to observe, both in the abstract Boolean tables of various radixes and adicities shown here, and in the physical likes of the mysterious switching device in the foregoing description, that they illustrate the philosophical principle of underdetermination in science. (See reference 5 for a discussion of underdetermination). As shown here, any Boolean table of any radix or adicity can be extended to an arbitrary degree, as illustrated by the addition of asterisks to a table, or of switches to the mystery device. That extension exactly corresponds to the degree of underdetermination of any system under investigation. This is of course only one aspect of the concept of underdetermination, but it is compelling and even quantitative.
6. Designational aspects of Boolean operations.
Any operation which can be exhaustively represented by the FWab notation, is by that very fact context-free and deterministic. It is also comprehensive and closed, in that every a-tuple of argument digits yields an element of b. There is no provision for randomness or for historical or positional dependencies, such as arithmetic carries. Many of the considerations in this paper apply to less restricted operations, but they will not be discussed here. Generalisation of a Boolean operation in terms of function tuple, radix or adicity , tends to cause a lot of decomposition, as each is a major component of the function definition.
Consider table 6.1, of radix-2, dyadic truth table function tuples of the argument tuples A, B. The column headed F gives the hexadecimal encoding of the function tuple as an identifier.
Table 6.1
Truth-table values for radix-2, dyadic Boolean functions. In this sense the adicity refers not to how many operands are shown, but to how many of the given operands make any difference to the value yielded. For instance, 0Wgives the same output, no matter what the arguments. are. In this sense it is nulladic.
A: 0011
B: 0101 Adicity
F
0 0000 a=0 False; 0; b-2; (Sum of operands)/(a+b)
1 0001 a=2 &; MIN(ai, bi); selective zero; Mod b multiply;
(0 if ai<>bi, else ai); majority of operands=1
2 0010 a=2 ai>bi; (bi=0 & ai); ~(aiÞbi); zero non-oscillating digits.
3 0011 a=1 ai; (ai>0)Û(fi=1); bi divisible by ai; (ai*a+bi)/b
4 0100 a=2 bi>ai; ~(biÞai); ai=0 & bi;
5 0101 a=1 bi; NOP; ai divisible by bi
6 0110 a=2 XOR; ¹;
non-equivalence; Selective oscillation;
Mark
differences with MAX(ai, bi);
Modulus ±; Odd parity; ABS(ai-bi)
7 0111 a=2 OR; MAX(ai, bi); set selected bits ON;
(Sum of
operands+b)/(a+1)
8 1000 a=2 NOR; selective oscillation/zero; majority of operand digits 0
9 1001 a=2 XNOR; º; selective oscillation; even parity;
complement addition mod-b;
A 1010 a=1 (bi=0); (bi>0)Û(fi¹1); ai not divisible by bi;
non-selective toggle of bits
B 1011 a=2 (biÞai); (ai³bi)
C 1100 a=1 (ai=0); (ai>0)Û(fi¹1); bi not divisible by ai
D 1101 a=2 (aiÞbi); (bi³ai)
E 1110 a=2 NAND; selective set off or flip.
F 1111 a=0 TRUE; ON; b/2; a/b
On the right are a few deliberately miscellaneous designational aspects; multiplying instances is too easy. No function can substitute for any other without adjustment. For instance, although 6W and 9W were shown to be distinguished only by the assigned symbology of bits, they can serve several similar purposes, but with modified arguments, or inverted bit symbolics. Again, 1W, 2W, 4W and 8W all zero bits selectively, but with different arguments and with side effects varying in inversion of non-selected bits.
Another point is the apparently atomic nature of many of the designational aspects mentioned. This is an illusion, as is hinted at by such descriptions as of 0W yielding values two less than b. Any zeroing function can be described in such terms, and the introduction of the concept of a constant function of the radix value immediately gives scope for generalisation in terms of that constant. Accordingly, 0W and FW generalise to any nulladic source of constant digits in any radix. Using definitions involving calculation with b or a, one also can generalise to non-constant generators. Similar principles apply to the other functions; and this is just one simple variation on a broad theme.
It is interesting, but beyond the scope of this paper, to speculate whether there is a systematic basis for dealing exhaustively with the designational aspects of the
FWab functions. The following classes are illustrative and arbitrary.
A function is selective with respect to given effects when any specified one of those effects can be achieved by suitable selection of a given subset (typically just one) of the operand digits. For example, with CW (or 12W if one insists on a decimal representation of the radix) one can force a 0- or 1-bit in the result with respectively a 1- or 0-bit in the first operand. Selectivity is very common in the everyday Boolean functions. Those most frequent in computer instruction sets. For example: &, ÷, and Å are often regarded merely as selective turning of bits off or on, or inverting them.
More elaborate selectivity occurs in higher radices, eg to radix 4:
Table 6.2
0000 1111 2222 3333
0123 0123 0123 0123
0000 1230 3012 0123, or, giving the function in hexadecimal for convenience:
6CC61BW4
This offers four options: zeroing; modulus increment and decrement; and no
effect.
While only nulladic functions are unambiguously non-selective, many functions are only trivially selective. Some functions permit discrimination of a number of classes of digits in a tuple, by applying appropriate digits in a matching argument tuple and inspecting the result digits, eg:
Table 6.3
The radix-4 function:
0000111122223333
0123012301230123
0323313223033231, ie:
3BDEB3EDW4
permits one to detect any digit by the
fact that in the result, digits smaller than 2 correspond to the argument
digits being identical.
Slightly higher selectivity occurs where F is 0312101322013220, 0333323333133332 or 0111101111011110. In the first the digit 0 indicates equality, in the second 3 indicates inequality and in the third zeros and ones respectively indicate equality and inequality. All these are cases in the generalisation of 6W and 9W.
Finer
discrimination is possible, culminating in full identification when the
function matrix is a latin square, so that:
w,
x, y, z Î b; (xy=z)&(xw=z)« (y=w).
Another class of discrimination is ordering, where result digits reflect the sequence of digits in the operands, eg:
Table 6.4
0000111122223333
0123012301230123
0111301133013330
Here a 0 result indicates that the argument digits were equal, a 1 indicates that the first argument was the smaller, and a 3 that the first was the larger.
Quantificatory functions on the other hand, reflect the degree of difference between the operand digits. They necessarily include an additive entity, usually written 0. Typical examples are the modulus subtractions.
Define repetitive
operation as repeated application of a function to a set of
operands, where a given operand is replaced after each cycle by the result of
the previous operation, so:
aWb=c
aWc=d
aWd=e . . .
A cyclic operation is one which on repetition, always yields cyclic results, ie the pattern of repetition includes the first result. Boolean cycles are fixed, because the operations are deterministic. The operation may be selective in: the length of various cycles; the sequence of values in distinct cycles of the same length; and in some operands not behaving cyclically. A nulladic cycle is a source of a fixed cycle of digits. A monadic cycle is a source of any of a set of cycles depending on the value of the first operand.
An exhaustive cyclic operation is non-selective and for radix-b, is of period b. If b has d divisors, there can in principle be up to d distinct cycle lengths and for a given cycle length, there can be up to b distinct cycles, if distinct phases of cycle are counted as distinct cycles.
All these are directions of proliferation in generalising the cyclic operations: 0W, 6W, 9W, AW, CW, FW in terms of radix.
Cyclic operations are important in such applications as toggling or swapping values. In radix-2 either 6W or 9W, usually the former, can selectively toggle values and can be used to swap values through the three successive operations a=aWb; b=aWb; a=aWb.
Longer swap cycles exist, based on different constraints, but it is easy to show that where an operation has just one output value, at least three cycles are needed for swapping two values.
A toggle operation has a cycle length of 2 so that (xy=z)«(xz=y).
3-cycle swap operations are symmetrical toggle operations, that is where: (xy=yx)&((xy=z)«(xz=y)). These apply to dyadic operations. I leave it at that until an identified need for polyadic swaps suggests a useful definition for such a class of operations.
7. Generalisations of Boolean functions.
Assignment of relative importance to different terms of generalisation is largely arbitrary. Perhaps an objective criterion could be constructed in terms of the degree of decomposition or ambiguation or cost in information. All such parameters depend largely on the choice of terms of generalisation. The following sequence is convenient in context, but is not intrinsically canonical, even assuming that such a thing exists.
The most fundamental generalisation may be in terms of symbolics. Permutation of assignment of states to significance of digits, can radically transform functions. This option was largely covered in the lyngo discussion and here we merely note that the most obvious rate of decomposition is modest, less than b!
Once the symbolics are settled, the next most fundamental level of generalisation might be in terms of semantics. Whether a digit value is regarded as large, or undefined, or true, or probable, or conditionally equatable to another, affects the meaning of a function; even the question of whether it is meaningful at all. This emerges immediately in discussion of generalisation in terms of the function tuple, and intermittently thereafter.
Generalisation in terms of function tuple amounts ultimately to dealing with entire range
of FWab for constant a, b, but such a broad
interpretation is of little interest. On
the other hand, in designing a function of specific nature, small adjustments
to F are often hotly
debated.
Consider radix-3 &, where 0, 1,
2 are taken as respectively false, true, undefined. Three of several possibilities are commonly
in contention:
Table 7.1
(A) (B) (C)
000111222 000111222 000111222
012012012 012012012 012012012
002012222 000012022 000011012
Such distinctions reflect basic differences in the semantics underlying the design of functions. Some define the result of any operation on undefined operands as undefined, as in table 7.1, example (A). This is sometimes justified in practice, but it is not universally compelling. The definition of a function may compel certain results if certain operands are present; eg in example (B) a zero among the operands of & forces a zero result. It then wastes information to insist on every undefined operand forcing an undefined result. Conversely, as in example (C), an undefined operand might be taken as no operand, and have no effect on the other operands.
The validity of such options is constrained by the semantics of the function being
generalised. For example, 1&2 comfortably forces 0 according to such definitions as:
fi:=MIN(ai, bi) or mod b multiply;
but according to:
fi:=(0 if ai¹bi, else ai),
it depends on the definition of inequality.
In generalisation to b=3 and 2=undefined, an
operand of 2 forces a result of 2 if equality/inequality with undefined is
undefined.
Next, consider generalisation in terms of adicity. An a-adic operation has a operand tuples. That subset of a-adic functions in which some n of the argument tuples do not affect the function tuple, may be regarded in appropriate context as (a-n)-adic. Such a context must allow for the permutation of the argument tuples as a significant designatum
in
some functions. For examples, in table
6.1, inspect FW22 to see that
0W22 ;
3W22 ;
5W22 ;
AW22 ;
CW22 and FW22 respectively
amount to:
0W12 ; 1W12 ; 1W12 ; 2W12 ; 2W12 and 3W12 .
In turn, 0W12 can be taken as
equivalent to 0W02
and 3W12 can be taken as
equivalent to 1W02
Commutativity and associativity are vacuous designational aspects of nulladic and monadic operations, but in dyadic operations, commutativity amounts to the function matrix being symmetrical about the top left diagonal.
There are bb(b+1)/2 such matrices out of bbb or just more than the square root of the count
of all the possible matrices. For higher
adicities, the designational aspects of commutativity and associativity
decompose and are subsumed in the general designational aspect of sensitivity
to the permutation of operands. This
ranges from total insensitivity, as in modulus addition, through partial
dependence on operand order, to there being unique function values for each
argument permutation.
Sensitivity to operand permutation can be applied to every designational aspect of an operation. For instance, an identity element is normally taken to be unconditional, but in some functions, an element only acts as an identity element in certain positions. For brevity, ignore this aspect except in special cases.
The most obvious generalisation in terms of adicity is construction of a high-adicity function table equivalent to repeated application of a dyadic function. As shown in the discussion on generalisation, this gives only a subset of of possible functions. For high adicities, one can construct devices or abstractions in which permutations of operand digits give results varying as far as the radix permits.
Some assignments of semantics give other paradigms for generalisation. If say, & is taken to indicate a majority of non-zero operands, then one gets significantly different patterns from when & means that any zero operand forces a zero result. Also, the effect of undefined values among operands is totally different. Consider the following examples, where
a=3, b=3, 0<1<2, 0=FALSE, 1=TRUE, 2=UNDEFINED:
Table 7.2
Underlined result digits are those which involve no generalisation in terms of adicity:
A: 000000000111111111222222222
B: 000111222000111222000111222
C: 012012012012012012012012012
F1 000000000000011011000011012: Force result = lowest operand.
F2 000000000000012021000021012: Multiplication modulus b.
F3 000000000000012022000011022: 0 forces 0, else 2 forces 2.
F4 000001011001011111011111112: Quotient
(sum of operands)/b (or /a).
F5 000010112010111012002012222: Result =
commonest, lowest
operand.
F6 002002222002012222222222222: 2 forces 2, else 0 forces 0.
Note that these functions are not merely physically different in many respects; semantically they are mutually exclusive. And yet, each of them is a valid generalisation in terms of radix and adicity from a valid assignment of significance to
1&22 in which the degeneracy of the smaller radix and adicity united all views in one function.
The most frequent function generalisations are perhaps in terms of radix. The first inkling that there are restrictions to meaningful generalisation, in that arbitrary retention of designational aspects is constrained, is in the fact that many important features are reflected in the configuration of the matrix and this in turn is restricted by mathematical considerations. For instance, even and odd latin square matrices, if they are to be symmetrical, cannot have similar diagonals.
To support a
3-cycle swap operation, it follows from the prerequisite:
(xy=yx)&((xy=z)«(xz=y)),
that the F matrix must form a
latin square symmetrical about the the diagonal from the top left. In radix-2 there are just two such, corresponding
to 6Å, and 9º. The former is modulus b addition or subtraction, as preferred. For larger b, modulus or absolute subtraction are no longer swap functions, but
there are other configurations than for modulus addition which define swap
functions. For example, the following
radix-8 and radix-10 matrices all define 3-cycle swap functions:
Table 7.3
01234567 01765432 46570213
10325476 10237654 64751302
23016745 72156340 57462031
32107654 63514207 75643120
45670123 57643021 01237654
54761032 46320715 23016745
67452301 35402176 10325476
76543210 24071563 32104567
0123456789 0123456789 4732056189
1032674598 1234067895 7465132098
2301865947 2340178956 3640281957
3210789456 3401289567 2504319876
4687091325 4001395678 0123498765
5768902134 5678901234 5381907624
6459120873 6789512340 6219870543
7594318062 7895623401 1098765432
8945237601 8956734012 8957624301
9876543210 9567840123 9876543210
The functions defined as truth tables by the matrices in table 7.3, differ radically different in semantics except that all are radix generalisations of lower-radix swap functions. It is not easy to find many other semantic aspects they all share with each other or with 6Å or 9º. Rather than multiply instances excessively, consult the table of radix-2 functions and their semantics. There is not one of them which can be generalised in terms of radix without sacrificing some of their designational aspects. In fact, there very few designational aspects which can be kept together at all in generalisation. Subtle differences in definition at the radix-2 level can affect this, which can show that what seemed equivalent definitions at first, turn out to be distinct aspects which happen to coincide in radix-2, and are so different as to generalise to totally disjoint functions
above radix-2. For instance, 0W22 if regarded as generating 0-digits, generalises to totally different functions from when taken to generate (b-2)-digits.
FW22 can be taken to generate b-1 or b/2 or
1-digits. In one case it always
generates
larger digits than generated by 0W22 generalisations, in other cases it coincides in certain radices and thereafter generates lower digits than they do.
This example demonstrates also that functions which seem totally distinct in radix-2, actually coincide in some designational aspects in certain radices.
8. Discussion
Plainly the definition of an operation in terms of the behaviour of a finite-state device, or even of a function table, is usually unavoidably redundant in that more implications are entailed than explicitly intended. There are always various interpretations appropriate to the behaviour of a given finite state machine. The operation of a finite-state machine cannot even necessarily be uniquely associated with any function table, before one has allocated symbols to states and significance to symbols,
Even given the symbolics and the significance of the symbols, which enable one to set up exhaustive function tables, the functions themselves can be represented as finite-state machines and subject to many interpretations. Some abstractions of these interpretations can be imposed on various functions, but there are restrictions to which can be imposed on more than one function.
Confusion of the function as physically defined, with the abstraction which is the incentive for a given application of the function, could perhaps best be corrected by defining the operation in terms of the relevant designational aspects. For instance, where difficulties could arise, instead of defining a function as say, 6Å, one could specify that it is intended as indicating that not all the arguments are true, or whatever the operative aspect may be. This minimises problems of consistency when generalising in terms of radix or adicity, for instance. Of course, it does not in general eliminate the problems of decomposition on generalisation. Attributes combined in one radix or adicity, may be incompossible in other cases.
This suggests the concept of semantic spaces.
Call the space whose dimensions are a, b, F and the designational attributes are the universal Boolean function space. A point in this space is said to be occupied if a function exists at those co-ordinates, else it is empty. The semantic space of any attribute is the set of occupied points sharing it as a co-ordinate in the universal space. Admittedly, I can think of no non-trivial case where the semantic space of attributes can be demonstrated with any rigor, so this discussion is somewhat academic.
If some set of attributes can be shown to coincide in all points where any one member of the set occurs, then call that attribute set atomic. It may be difficult to justify regarding those attributes as non-equivalent, as it is hard to see how they might meaningfully be dealt with independently. Conversely, if an attribute turns out to decompose, ie to apply only in part to some function, then regard it as a compound of atomic attributes and it is only for convenience that one might refer to it as an attribute in its own right. Then a comprehensive definition of a function in terms of the designational aspects intended by the designer, is the semantic space common to those designational aspects. This basis for definition lacks the misleading aspects of definition in terms of function tables.
In the clear definition of attributes and the effects of changing them, Boolean functions offer an attractive medium for demonstrating the difficulties of assigning the concept of a kind to a generalisation in terms of a simple attribute. Other attributes which had seemed to be aspects of each other may separate and some which had seemed to be opposite, could sometimes coincide.
Where an entity is by definition a member of a series of entities, such that some of its attributes are simpler than other members of the set, leaving some of the attributes of other set members meaningless in the context of the simpler member, this is degeneracy. Much as a circle is in a sense a degenerate case of an ellipse, and a point is a
degenerate case of either a circle, a line, a polygon or a polyhedron, so 6Å2 is degenerate in failing to distinguish between modulus addition and subtraction, for example. In general, every low-radix or low-adicity Boolean function is degenerate with respect to higher radices or adicities, but this is nowhere more obvious in non-trivial cases than in contrasting radix-2 functions with higher radices.
Reductionism is variously defined, often with pejorative intent. The aspect mainly relevant here, is that certain aspects of a complex entity can be understood in terms of the natures of its components. Boolean functions and their generalisations offer convenient models for analysing such concepts, both defined in terms of function tables and in terms of semantic space.
Critics of reductionism in real life tend to discount its valid applications as well as its abuses. One strong valid claim is that no demand may be made of a compound system, that contradicts the nature of any of its parts. This claim refers only indirectly to any relationship the part may have to the rest of the system.
To illustrate the relevance to Boolean functions, consider a function with high a or b as a homologue of a low a or b function. It is no objection that the higher radix or adicity imply operand and function values absent from the simpler case, but homology fails if any that are present in both cases cannot be shown to match. for instance, in table 7.1, all three examples of the radix-3 functions could be taken as extensions of the Boolean
1&22 , because all the function bits corresponding to radix-2 arguments also correspond
to the function digits for 1&22 .
Should the function tuple F however, take the value, say, 102012222, then it is hard to
sustain the view that the homology with 1&22 is valid. This F treats zero arguments
differently from the way that 1&22 does.
However, the question of semantics still obtrudes. Even when in 1&22 , one regards the operation as yielding zero if the operands include at least one 0-bit, else yielding a 1-bit. This justifies rejection of any candidate homology which yields anything but 0- or 1-bits, or yields anything but a 0-bit from operands which include a 0-bit. However, alternative definitions, equally restrictive, yield different results, eg: let any set of operands including precisely two 1-digits yield a 1-digit, and let all others yield 0; or let all operand sets yield 1 if and only if there is a prime number of 1-digits among the operand digits.
Less restrictive definitions make their own irreducible demands, eg that any & operation yields the minimal operand digit, or the non-negative sum of operands minus 1. Some definitions are so loose that homologous operations are not unique for given a, b. By way of analogy, a shaped piece of soda glass may play a part which is so complex as to defy prediction, or even analysis. Its role in a system might depend on its hardness, softness, refractive index, transparency, opacity, taste, size, shape, or a vast number of combinations of attributes. It may play one role or many, in one complex structure or many, but however holistic one's view of the system, no behaviour may be demanded that requires inappropriate behaviour of such a component, say superconductivity at 900K and 1 Pascal.
Conversely, the dangers of reductionism are very real. Given a set of empirical observations and abstracting attributes from them is necessarily an arbitrary task.
Various abstractions of the behaviour of 1&22 all constrain its results fully. Some
constrain the results of &ab for all higher a, b as well. Given 1&22 as a component of a complex of homologous functions, no more than one of the abstractions mutually exclusive for some permissible a, b can be valid. This is at once a danger and a virtue of reductionistic analysis and synthesis. Predictions are unreliable, but may be falsifiable.
But truths may co-exist. Remember all the attributes of the piece of glass, for example. Some attributes coincide in special cases only, and such cases tend to be of low a, b. For
instance, the definitions of & in the previous paragraphs coincide only in 1&22 . Other
abstractions which coincide in and rigidly describe 1&22 , may ambiguate rapidly with larger a, b. If all that could be specified were that that the first argument columns whose
digits contained the bits comprising the arguments of 1&22 as subsets, yield 0001, then any increase in a or b would permit a vast variety of alternatives, eg:
Table 8.1
0000.....
000111.....
01201.....
00*01***...
This places little constraint on generalisation in terms of a or b, yet in real life, for any
FW22 the four bits of F are reminiscent of four empirical observations of the interactions in a deterministic system of many variables. One might demand the assumption that no observation of any combinations of arguments give any information necessarily of use in predicting the probable behaviour of any other. That would raise the complex question of simplicity. From one point of view the simplest assumption is of the least possible predictability, as that demands least of the structure within the complex. From another, null structure is a special case and in the absence of information, is no likelier than any other possible case. The most parsimonious assumption then becomes that no structure is any more plausible than any other.
Neither in real life nor in mathematics is the assumption of null structure the commonest. When interaction in a structure is recognised, it is commonly rewarding to look for analogous interactions or related patterns (not necessarily similar), in the rest of the structure. There are usually many valid candidate analogies and ideally every new observation reduces the number of survivors. Thus, although the reductionistic examination of cases does not automatically clarify the whole structure, progressive observation can yield progress, perhaps via repeated blind alleys.
In
investigating physical realities, the complexity of the subject is analogous to
a horizontal function table of which only the bottom left part is partly
visible, eg:
Table 8.2
.
....
...........
000000000....
000111..22.....
012...............
. . .
012.................
The adicity in such a table is uncertain in that it is not practical to identify the number of variables affecting any outcome. One is forced to neglect or fudge the effects of those whose effects are near the threshold of demonstrability. The radix is hard to demonstrate because the number of possible types of variables is also hard to demonstrate, especially if their effects are small or unpredictable.
Ignoring problems such as real-life uncertainties of observation, the reductionistic approach has been to attempt to hold the subject of an investigation to the lowest a, b possible. In some cases a consistent table results which more or less accounts for the observations. On the whole, this has been by far the most successful approach in inductive investigation of the nature of the world and it seems likely to remain so. The intellectual dangers include the real risk of taking the neat, small result for the whole table - a frequent error in the history of science. Identification of higher levels of interaction is then analogous to incrementing a, and introducing new states and effects is analogous to incrementing b.
Problems include identifying the threshold at which one may legitimately neglect a dimension of adicity or extra states in the radix. Although neglect of indetectable parameters is unavoidable in real life, some workers seem to make a virtue of the necessity, to the extent of effectively denying the reality of the neglected factors. Not only are indetectable data ignored, but so are inconsistent data, and even data inconsistent with established theory.
Another common error is unjustified attribution of observations to accepted classes of cause or interaction. This is analogous to reducing the radix by conflating fundamentally distinct states.
The converse error is to attribute significance of non-existent, or at least unobservable states and interactions. Superstitions and astrology are examples. The error deserves the respect due to popular acclaim however, as it is the basis of a world-wide, multi-billion-dollar industry in quackery, pseudoscience, gambling and the like. If the democratic counting of heads is the royal road to truth, then this is no fallacy. In science, its history is honourable too; rooted misconceptions have often delayed progress for centuries.
Both types of
error abound in software debugging, where the tendencies alternate between
overlooking the possibility that real devices need not be limited to ideal
behaviour; and blaming problems on every hypothetical cause but one's own
error.
Part of the argument against reductionism is essentially quantitative: that the complexity of a really large system renders it intractable to prediction. For instance, the study of atoms does not enable one to predict the existence and behaviour of oceans and okapis. In real life this is true as far as it goes, though there should be a theory of intractability before the claim achieves rigor. In this model system, the question is less clear. In high adicities there room for confusion, and if one permits the combination of isolated Boolean functions in suitable contexts, all sorts of cellular automata and universal computers are possible. But these cases are not the prime material for this discussion.
9. Conclusion
The structure of the Boolean function is clearly a very convenient medium for displaying the effects of simplification or complication of a system by changing the number of interactions or the variety of entities involved. The effects supply metaphors for reasoning and research. It is equally clear that options for increasing the complexity of a system are so numerous and varied as to make nonsense of attempts to impose a compelling unique scheme for homology. This is compounded by unavoidable ambiguation. Options for simplification are fewer, even unique, and are at the cost of mergence or loss of attributes, in which respect the simpler systems are degenerate.
References.
1 Stamper, R.K. Information: Mystical Fluid or Subject for Scientific
Enquiry? The Computer Journal, Vol. 28, No. 3, 1985, pp 195-199
2 Carnap, R. Introduction to Semantics and Formalisation of Logic.
Harvard University Press, 1959
3 Special Issue on Multvalued Logic, IEEE Trans. Comput., vol C-30,
July 1981
4 Swift, J. Gulliver's Travels, (Book) Part 3, Chapter v. ca 1726
5 Stanford, Kyle, "Underdetermination of Scientific Theory", The Stanford Encyclopedia of Philosophy (Winter 2021 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/win2021/entries/scientific-underdetermination/>.
