How to get all minimum true condition out of a expression

Question

I need help in extracting all minimum true condition out of a expression (like where clause in sql)

lets say i have a expression like:

Eg 1:

((A & B ) & (C | D))
output should be:
((A & B) | C)
((A & B) | D)

Eg 2:

((A | B) & (C | D))
output should be:
(A & C)
(A & D)
(B & C)
(B & D)

Eg 3:

(A | B | C)
output should be :

(A)
(B)
(C)

NOTE: '|' represent 'OR' and '&' represent 'AND', so want to break a big condition into all possible smallest true conditions.

Please suggest...

Answer 1

So it seems that what would help you is to have a way of simplifying your expression into a sum of products. By having it in sum of products form you will have a series of different options, each of which will be the only one to be correct if all of the values it contains are true.

One way of dealing with this is to use the composite pattern. We'll start out with our IExpression interface:

public interface IExpression<T>
{
    int NumberOfPossibilities();

    IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities();
    IEnumerable<ValueExpression<T>> GetNthPossibility(int n);
}

The key points here are the first and last methods. We need to be able to know how many possibilities there are for a given expression as well as a simple way of getting the Nth possibility. The convention for the last method is that all of the given values need to be true for the Nth possibility. For the second method the outer enumerable are all expressions to be ORed together, while each of the inner expressions need to be ANDed together.

There will be three implementations. A ValueExpression that represents just one value, an AndExpression that represents ANDing N expressions together, and an OrExpression that represents ORing N expressions together.

The Value is the simplest to implement:

public class ValueExpression<T> : IExpression<T>
{
    public T Value { get; set; }
    public ValueExpression(T value)
    {
        Value = value;
    }

    public int NumberOfPossibilities()
    {
        return 1;
    }

    public IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities()
    {
        return new[] { new[] { this } };
    }

    public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
    {
        return new[] { this };
    }
}

The And expression is a tad more involved. The number of possibilities for an AND expression is the product of the number of possibilities being ANDed.

To get the Nth possibility you can think of it as such:

start at 0; for 0 the result requires ANDing together the first possibility of each of the sub-expressions. For the 1st possibility we add one to the first sub-expression. Each time n goes up we increase the permutation we get from the first sub expression. When we pass it's count it goes back to zero and the next sub-expression goes up by one. It's basically like counting, but where each digit represents one of the sub-expressions and where the base of that digit is the count of the possibilities for that sub-expression.

public class AndExpression<T> : IExpression<T>
{
    private IList<IExpression<T>> expressions;
    public AndExpression(IList<IExpression<T>> expressions)
    {
        this.expressions = expressions;
    }

    public int NumberOfPossibilities()
    {
        return expressions.Aggregate(1,
            (acc, expression) => acc * expression.NumberOfPossibilities());
    }

    IEnumerable<IEnumerable<ValueExpression<T>>> IExpression<T>.Possibilities()
    {
        return Enumerable.Range(0, NumberOfPossibilities())
            .Select(n => GetNthPossibility(n));
    }

    public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
    {
        for (int i = 0; i < expressions.Count; i++)
        {
            int count = expressions[i].NumberOfPossibilities();
            foreach (var value in expressions[i].GetNthPossibility(n % count))
                yield return value;

            n /= count;
        }
    }
}

For the OR expression it's similar to, but still distinct from, the AND version.

The number of possibilities is the sum, not the product of the counts of the inner expressions.

To get the nth possibility we only return the items from one of the possibilities of one of the sub expressions, rather than returning one from each as AND does.

public class OrExpression<T> : IExpression<T>
{
    private IList<IExpression<T>> expressions;
    public OrExpression(IList<IExpression<T>> expressions)
    {
        this.expressions = expressions;
    }

    public int NumberOfPossibilities()
    {
        return expressions.Sum(expression => expression.NumberOfPossibilities());
    }

    public IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities()
    {
        return Enumerable.Range(0, NumberOfPossibilities())
            .Select(n => GetNthPossibility(n));
    }

    public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
    {
        for (int i = 0; i < expressions.Count; i++)
        {
            int count = expressions[i].NumberOfPossibilities();
            if (n < count)
                return expressions[i].GetNthPossibility(n);
            else
                n -= count;
        }

        throw new ArgumentOutOfRangeException();
    }
}

Here is a simple function to print out an expression as a string:

public static void PrintPossibilities<T>(IExpression<T> expression)
{
    Console.WriteLine(string.Join(" + ", expression.Possibilities()
            .Select(possibility =>
                string.Concat(possibility.Select(value => value.Value)))));
}

Note that this doesn't handle parsing the expression, merely processing it once it's been parsed.

Here is a test of your first example:

var AB = new AndExpression<string>(new[]{
    new ValueExpression<string>("A"),
    new ValueExpression<string>("B")});

var CD = new OrExpression<string>(new[]{
    new ValueExpression<string>("C"),
    new ValueExpression<string>("D")});

var exp = new AndExpression<string>(new IExpression<string>[] { AB, CD });

PrintPossibilities(exp);

Which prints:

ABC + ABD

AB changed to be an OR expression (your second example) prints:

AC + BC + AD + BD

Your third option can be represented as:

var third = new OrExpression<string>(new[]{
    new ValueExpression<string>("A"),
    new ValueExpression<string>("B"),
    new ValueExpression<string>("C")});

which when printed results in:

A + B + C

Answer 2

What I understand you're asking for is a set of expressions, each of which implies the input. That is, if any of those expressions is true, then the input is true.

Putting it that way, we can see that what we're doing it rewriting the input into a big disjunction, and then listing the terms. In other words, you're looking to rewrite your input into a Disjunctive normal form. Wikipedia tells us that "All logical formulas can be converted into disjunctive normal form. However, in some cases conversion to DNF can lead to an exponential explosion of the formula."

So: if you have an "or" at the top, return a set of all the children (you can apply this algo recursively to each of them). If you have an "and" at the top, run this recursively for each children and then return all combinations of "and"ing one of the options for each children.

So for example if you have (A|B|C) that gives you A,B,C as the answers. If you have (A & (B|C)) then you get just A for the left child, and B,C for the right child. So putting them together you get the two answers: A&B and A&C.

And if you have a "not", you can use De Morgan's law to push it in, so you can keep on using the two rules above.

P.S. I'm answering "how to get all answers" which is what your text asks, as opposed to "how to get the smallest answer" which is what the title asks. It's an easy step to consider all the answers and pick the smallest one.

Answer 3

I came up with the following algorithm, I think this can help you find the Minimal true conditions in an expression.

eval(X & Y) => eval(X) JOIN eval(Y)
eval(X | Y) => eval(X) MERGE eval(Y)
eval(x) = x

Where,

X, Y => expression; x => identity
A JOIN B - every elements in list A joined with each element of list B with a '&'.
A MERGE B - simply merge elements in list A & B

Let us take example of your first example to prove it: Expression - ((A & B ) & (C | D)). Let X -> (A & B) and Y -> (C | D)

Now,

eval(X & Y) => eval(X) JOIN eval(Y)
eval(X) => eval(A) & eval(B) => ['A'] JOIN ['B'] => ['A & B']
eval(Y) => eval(C) MERGE eval(D) => ['C'] MERGE ['D'] => ['C','D']
eval(X & Y) => ['A & B'] JOIN ['C','D'] => ['A & B & C', 'A & B & D']

Similarily, other examples can be sorted out. Also, the solution you have provided in example 1 is wrong, it should be as above.