Search code examples
booleanboolean-logicboolean-expression

Shannon expansion in a boolean function


According to this page in Wikipedia (https://en.wikipedia.org/wiki/Boole%27s_expansion_theorem) The Shannon expansion or decomposition theorem, also known as Boole's expansion theorem is an identity that allows the expansion of any logic function to broken down into parts. in other word:

F = X . F (X = 1) + X' . F (X = 0)

so I tried to implement this logic in a simple C++ code and it didn't work, here is what I tried:

#include <iostream>
#define f(x,y,z) (((x) & (y)) | ((x) & (z)))
using namespace std;
int main()
{
    unsigned int a = 0x215f8;
    unsigned int b = 0x77012;
    unsigned int c = 0x33548;

    cout << f(a,b,c) << endl;
    cout << (((~a) & f(0,b,c)) | ((a) & f(1,b,c))) << endl;
    return 0;
}

what I'm I missing?

EDIT:

the output of the program is:

136536

0

Solution

  • the mistake I was doing is that I was using Shannon expansion theorem in it's fondamental form, the shannon expansion should work on the set B={0,1} so when we try to extend this idea to integers we should consider all aspects of that extension, the shannon expasion in the boolean space is f(a,b,c) = a'.f(0,b,c) + a.f(1,b,c) my mistake is that I used that exact form while I should instead use f(a,b,c) = a'.f(0,b,c) + a.f(MAX_UNSIGNED_INT,b,c) which will put a constant with all 1's in it, this works:

    #include <iostream>
    #include <limits.h>
    #define f(x,y,z) (((x) & (y)) | ((x) & (z)))
    using namespace std;
    int main()
    {
        unsigned int a = 0x215f8;
        unsigned int b = 0x77012;
        unsigned int c = 0x33548;
    
        cout << f(a,b,c) << endl;
        cout << (((~a) & f(0,b,c)) | ((a) & f(UINT_MAX,b,c))) << endl;
        return 0;
    }