I will continue Part 1.
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 reads as “A and not A”. This equation can’t be true. If is true, it means “true and not true”, which is false according to Boolean logic. If 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 . Multiplying elements from this set is the same as the logical conjunction of elements from the set .
We can now apply DeMorgan’s Laws to find the equivalent for logical disjunction. Let’s say we take two elements from the set : and . We’ll compare this to two elements from the set : and . Then . 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:
There are two variables, and we can number as the first variable and as the second. That gives us two formulas, which I’ll refer to as and . 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…