analytics

Wednesday, November 4, 2015

algebraic boolean algebra to prove De Morgan's laws

For 2 binary variables, which may also represent truth and falseness, we can solve for algebraic expressions representing the usual boolean operations like below... we just solve
a*x+b*y+c*x*y+d
algebraically for the four conditions in the truth table to get the coefficients...
Here I solve for ~(x OR y)
 which is:
So the equation above ranging over the binary parameters is:
regular OR is:
and it's easily proven that to negate any expression multiply the expression by -1 and add 1, the OR above is -1*(NOR) +1 for example, and the NOR is -1*(OR) +1 as well. Just see that any time the expression evaluates to 1,  1*(-1)+1 = 0 and when it evaluates to 0, 0*(-1)+1 = 1

So to prove de Morgan's laws we need an AND as well...
So de Morgan's laws are that  ~(x AND y) = (~x OR ~y)...
So ~AND is the same as -x*y + 1 to negate x*y, and then we multiply each variable in the or expression by -1 and add 1 to get...
And simplification shows we have equality...

**Powers and composing**

Sometimes when composing by substituting one of these expressions in for a variable in another, you get powers of a variable, but this is resolved by noting that any counting number power of 1 is 1 and any likewise for 0 is 0... For example This is substituing (X or Y) in for x and ~(x OR y) in for Y in the expression for (x AND y):
In the above the powers of a variable were removed to get to the bottom line to show that (x OR y) AND ~(x OR y) is always false or 0... I think this type of exponent elimination and algebraic simplification makes the 16 possible basic expressions from the 16 truth tables closed under composition...

**3 or more variables**

For 3 variables you solve this equation for the 8 possibilities of the unknowns:
and in general you have coefficients for multiplying the variables 0 at a time (the constant factor),  1 at a time, 2 at a time, etc. up to n at a time for n variables... This is 2^n coefficients because the number of coefficients is the same cardinality as the power set on n items which is 2^n, and there are 2^n possiblities of variables making 2^n linear equations in the coefficients so it can be solved...

**Fuzzy Logic**

Using the expression for OR which is x +y - x*y, I wonder if it's true that if x has a 25% chance of happening and y has a 37% chance of happening, that we can plug in those values and get:

That x OR y has a 52% chance of happening, I'll have to write a program and see whether empirically this checks out... For fuzzy logic you'd have to do away with the rule that exponents disappear of course...

No comments:

Post a Comment