Boolean Functions as Formal Power Series (Part 2)

I will continue Part 1.

Suppose we have a Boolean function (from Boolean algebra).

Now the values of the Boolean variables might not be known. In fact, there is a question in computer science that pertains to this. The question basically goes,”Is it possible to assign truth values to the Boolean formula so that it is true?”. In other words, we would like to know if the solution to a particular equation could be true. For example, the equation (A \land \overline{A}) reads as “A and not A”. This equation can’t be true. If A is true, it means “true and not true”, which is false according to Boolean logic. If A is false, then it means “false and not false”, which is false.

This question is part of a very important problem in computer science, known to the experts as SAT. The problem is to find the quickest way to determine if a boolean formula can be true(aka “satisfied” in SAT terms).

So here I will explore finding a formal power series representation for a given Boolean function.

Let’s begin by comparing Boolean logic, and the results of multiplication from the set M = \{0, 1\}. Multiplying elements from this set is the same as the logical conjunction of elements from the set B = \{ \text{false}, \text{true} \}.

We can now apply DeMorgan’s Laws to find the equivalent for logical disjunction. Let’s say we take two elements from the set M: M_0 and M_1. We’ll compare this to two elements from the set B: B_0 and B_1. Then (1-((1-M_0) * (1-M_1))) \equiv B_0 \lor B_1. In other words, the lefthand side, where we do a bunch of subtracting from one, is equivalent to the logical disjunction on the right.

This is actually a solid basis for propositional logic. The details aren’t important, but it simply means that we can now form any Boolean function.

In Part 1, a power series for a Boolean variable was given. Now we can combine these formulas using multiplication, and a power series of ones, to get Boolean formulas.

For example, suppose we have the Boolean formula:
A \land B
There are two variables, and we can number A as the first variable and B as the second. That gives us two formulas, which I’ll refer to as f_0 and f_1. To get the result of this Boolean formula in a similar representation, we simply take the product of these two functions – well, almost. We are interested in the Hadamard product, which multiplies like terms together.

That is the real trick, and it is what I’m interested in learning more about. I’ll hopefully post a third part explaining this in detail…

Posted in Uncategorized | Tagged , , | Leave a comment

Boolean Functions as Formal Power Series (Part 1)

I’ve been interested, for years, in trying to solve NP hard problems using mathematical methods.

About a year ago, I found a way to represent Boolean functions as mathematical objects; really, as a formal power series.

To do so, we must consider the entire (Boolean) function. Then, the method for doing so becomes clear, although there are some unsolved problems associated with it.

We must first know the count of distinct Boolean variables in the function. Once this is known, the power series can be determined. In fact, for n variables, the (formal power series) function for variable m, 0 \leq m < n, is:

\displaystyle \frac{x^{2^m}(x^{2^n}-1)}{(x-1)(x^{2^m}+1)}

This series represents the bit $m$, ordered from least significant bit(LSb) to most significant bit(MSb), starting count at zero. That just gives us the bit that we’re interested in. The actual sequence is the numbers from zero to 2^n. The function gives us the binary representation of this bit(m) for those particular numbers, in order.

For anyone interested, I have a draft (although it’s very hard to read) that proves the correctness of this representation.

Posted in Uncategorized | Tagged , , | 3 Comments

Hello world!

Welcome to This is your first post. Edit or delete it and start blogging!

Posted in Uncategorized | 1 Comment