Numbers for Boolean functions

Discussion in 'Math' started by Bit-per-Beat, Aug 22, 2008.

  1. Bit-per-Beat

    Thread Starter New Member

    Aug 22, 2008
    Hello there,
    I came up with a way to assign a unique number (whole number) between 0 and 2^(2^n)-1 to each Boolean function of n Boolean variables.
    I have a couple questions:
    1) Do you think this may have any interesting applications?
    2) Have you seen before a similar type of functional? (A function from the set of Boolean functions to the set of whole numbers).
    This would be an expression for the general formula:

    N(f) = Sum(over all Boolean/Binary vectors x1,..,xm; f(x1,..xm) times 2^Sum(for k=1,..,m; xk times 2^(k-1) ) )

    The number is calculated from the Boolean function by interpreting "True" as "1" and "False" as "0," and then evaluating a polynomial of powers of two, with coefficients given by the function, and exponents also being themselves polynomials of powers of two, with coefficients given by the variables, and exponents given by the sub-indexes of the variables (minus 1).

    I have posted additional details in this page:

    Please take a look because I appreciate very much any feedback, questions, comments, and/or suggestions about this linear ordering of Boolean functions.
  2. Ratch

    New Member

    Mar 20, 2007

    I looked over the material of your link. Most of it is topics and content covered in any good digital logic book. Especially the formula 2^2^n, which is the heart of your discussion. Other than a theoretical understanding, I did not see any practical application in either the text books or your discussion. Specifically about applying it to reduce Boolean expressions. If you could provide a practical application for this material, I would be more inclined to look further into it.

  3. Bit-per-Beat

    Thread Starter New Member

    Aug 22, 2008
    Thank you, Ratch,

    That is right, currently I do not know if this functional could be used to simplify Boolean expressions.
    I was thinking more about re-writing Boolean expressions in a numerical language.
    The main point of the functional is not just to count all 2^(2^n) Boolean functions but to order them, identifying each one with a number.
    Here are a few examples:

    "True" becomes 1()
    "Not P" becomes 1(P)
    "P nor Q" becomes 1(P,Q)
    "P or Q" becomes 14(P,Q)
    "P and Q" becomes 8(P,Q)
    "P nand Q" becomes 7(P,Q)
    "P xor Q" becomes 6(P,Q)
    "P implies Q" becomes 13(P,Q)
    "P if and only if Q" becomes 9(P,Q)
    "At most one of P, Q, R is True" becomes 23(P,Q,R)

    The idea here is using numbers as Boolean functions to write down Boolean expressions because "the logic" is "already contained" within each number.
    For example, the distributivity of "or" over "and":

    a or (b & c) = [ (a or b) & (a or c) ]

    can be expressed with numbers as follows:

    9( 14( a, 8(b,c) ) , 8( 14(a,b) , 14(a,c) ) )

    If I find a way in which the numbers could help to simplify Boolean expressions, I will sure post it here. It's an interesting topic.

    Thanks again very much for your feedback.
  4. studiot

    AAC Fanatic!

    Nov 9, 2007
    I also looked over you link and I agree with Ratch that I saw nothing new in the webpage, although it was comprehensively and comprehensibly set out.

    However I understood your point to be one of synthesis not reduction. That is you can use a (denary?) code to build up a Boolean expression, by expanding into powers of 2.

    I was undecided as to whether this was new, but it looks remarkably like generating masking or complementing codes when returned to binary.

    Anyway well done if you thought of this for yourself.
  5. Bit-per-Beat

    Thread Starter New Member

    Aug 22, 2008
    Thank you very much, Studiot.
    Yes, I thought of this ordering functional for myself.

    You are right; almost nothing in the page is new. The only thing that could be new (and I have no clue whether it is) would be the general formula for calculating a unique number out of each and every Boolean function.

    Both in books and web pages I have seen at least two different ways of ordering the 16 Boolean functions of two variables. However, I have never seen one consistent way of extending these orderings all the way to infinity, covering every possible number of variables, and expressed through a single formula. That is why is asked the question in this forum, just in case someone could direct me to an earlier source.

    Thank you for mentioning the topics of generating masking or complementing codes.
    I will look into that too for any possible connection.

    BTW, since applying the formula implicitly orders the Boolean vectors (x1,..,xm) as well, this general organizing principle allows you to interpret every big enough whole number as a characteristic function, or a particular set of subsets of {1,..,m}.

    Considering that graphs, topologies, probability spaces, and other such structures are formally described as an element of the power set of the power set (second order) of the underlying basic set where the structure is defined, this opens the door to letting the binary system reveal a variety of properties of individual numbers.
  6. studiot

    AAC Fanatic!

    Nov 9, 2007
    Not convinced this qualifies as a functional.

    A functional is a map from a vector space to a scalar field.

    I don't think either you domain or codomain satisfy these requirements. But I am quite willing to be shown to be wrong here?

    Your whole subject is worth pursuing, in case it does lead to worthwhile applications.
  7. Bit-per-Beat

    Thread Starter New Member

    Aug 22, 2008
    You are right, Studiot,

    I was (maybe improperly) using the word "functional" in the sense of a function whose argument is itself a function.

    Boolean functions can be seen as Boolean vectors. That is how they look like when you write them out as truth tables anyway. In that way they may be considered as members of a vector space. But in that case the scalar field would have to be Z2, the two-element set {0,1} with the operations of multiplication (usual), and addition modulus 2 ( 1+1=0 ).

    As you point out, that is not the co-domain of my function, because the numbers given by the formula for Boolean functions cover all whole numbers, not just 0 and 1.

    I am going to do a little research, to double check the definitions, variants, and acceptable uses. I may need to erase the word "functional" from my page.

    A little side note:
    If f and g are Boolean functions of m Boolean variables x1,..,xm; and g is "the negation of f," meaning
    g(x1,..,xm) = not( f(x1,..,xm) )

    then N(f) + N(g) = 2^(2^n) - 1

    Thank you very much for the correction.
  8. Bit-per-Beat

    Thread Starter New Member

    Aug 22, 2008
    Dear Studiot,

    This is what I found after a little research on functionals.

    Mathematicians started studying functionals at least as early as the mid 1700’s, as part of the Calculus of Variations. The original goal was comparing different functions to maximize or minimize a value that depended not only on one numerical argument under a single function but on the global behavior of entire functions as whole objects.
    Today Functional Analysis is a vast branch of mathematics, devoted to the study of large classes of real and complex functions, and functionals defined on those domains. This area of math has lots of applications to Physics, and it naturally puts its main focus on functions that are either continuous, or integrable, or differentiable, or that share some other similar characteristic. Very often these sets of functions are vector spaces over the scalar fields of real or complex numbers. There are plenty of results that make heavy use of the linear properties of vector spaces to deduce properties of these functionals.
    However, the concept of a vector space was completely formalized only around the end of the 1800’s.
    During the second half of the 18th century, and the first half of the 19th, I doubt anyone defined a functional using vector spaces. Certainly at that time nobody used the concept of a vector space to avoid using the word “function” when referring to sets of functions. They do that today to achieve greater generality, and precision. Back then many still referred to functions as "variable magnitudes."
    In that earlier era, the definition of a functional was simply “a function of functions,” or “a map that takes a function as its argument, and assigns a number to it.”
    That is the sense in which I use the word functional for my formula. I am not doing Functional Analysis or Calculus of Variations. Boolean functions as such are discrete objects, not continuous. That would be the main difference here, with respect to the modern definition of a functional within those disciplines.
    The concept of a functional came up in the “continuous” realm of math, and it developed enormously, to the point where now the concept has become totally specific; just a function from a vector space to the scalar field over which the vector space is defined. This definition is precise and formal but it is also very dry, and to some extent masks much of the history behind the study of functionals.
    However, in my opinion, there is no valid reason to refrain from using the word “functional” in its original, more informal sense, when it comes to functions with a discrete domain and co-domain. I would venture to say there is no established tradition regarding the word “functional” within the realm of discrete math but only in the world of “continuous math,” a.k.a. Calculus and Analysis. So I feel free to continue using this word for the purpose of ordering Boolean functions.

    Below are some documents using the earlier definition, or pointing to it.

    Thanks again.

    “Introductory Real Analysis” – Kolmogorov & Fomin
    Dover, 1975; ISBN=0-486-61226-0; Chapter 3, Section 12, page 108:
    “Suppose T is a function space, i.e., a space whose elements are functions. Then a real function on T is called a functional.”
  9. Bit-per-Beat

    Thread Starter New Member

    Aug 22, 2008
    Hey, here is a way to calculate the numbers of the "projection functions."
    More explicitly,
    If x1,..,xm are Boolean variables then among the 2^(2^m) Boolean functions defined on these variables, there are m particular functions (I call them "projection functions") that mirror exactly one of the variables and disregard the rest.
    For j = 1,..,m we have
    fj(x1,..,xm) = xj

    Now, here is how to calculate the ordinal numbers corresponding to these f1,..,fm projection functions:

    N(fj) = [ (2^(2^(j-1)))*(2^(2^m)-1) ] / [ (2^(2^(j-1)))+1 ]

    For m=2
    if we have the two variables P (1st) and Q (2nd) then
    the above formula gives the correct values (as seen in the ordering of all 16 truth tables):

    N(P) = 10
    N(Q) = 12
  10. Bit-per-Beat

    Thread Starter New Member

    Aug 22, 2008
    Hello there,

    I just included three more columns in the list of the 16 Truth Tables of 2 Boolean variables.
    The new columns show the interpretation of each Number / Boolean function as:
    1) a set of smaller numbers
    2) a hypergraph based on those sets
    3) an event = subset of possible outcomes in a random experiment with two binary-outcome, independent trials

    here is the location of that table in the page: