How to get all the minimum true condition from an expression

Question

I need help in extracting the entire minimum true condition from an expression (e.g. where where in sql)

says that I have an expression like:

For example, 1:

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

For example, 2:

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

For example, 3:

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

NOTE: '|' represent 'OR' '|' represent 'OR' and '&' represent 'AND' , therefore it is necessary to break the big condition into all possible minimum true conditions.

Please suggest ...

Answer 1

So, it looks like it will help you simplify your expression in the sum of products. Having it in the sum of the forms of the products, you will have a number of different options, each of which will be the only right one if all the values ​​that it contains are true.

One way to deal with this is to use a compound template. We will start with the 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 know how many possibilities for this expression, as well as an easy way to get the Nth option. The convention for the latter method is that all values ​​must be true for the nth possibility. For the second method, external enumerations are all expressions that must be ORed together, while each of the internal expressions must be AND together.

There will be three implementations. A ValueExpression , which represents only one value, AndExpression , which represents AND expressions of N together, and OrExpression , which represent ORing N expressions together.

The value is the easiest 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 }; } } 

And the expression is a little more. The number of possibilities for AND expression is the product of the number of ANDed possibilities.

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

starts at 0; for 0, the result requires ANDing combining the first possibility of each of the subexpressions. For the first opportunity, we add one to the first subexpression. Each time n grows, we increase the permutation that we get from the first subexpression. When we pass it, it returns to zero, and the next subexpression rises by one. This is basically like a count, but where each digit represents one of the subexpressions and where the basis of this digit is the number of possibilities for this subexpression.

 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 an OR expression, it is similar to, but still different from, the AND version.

The number of possibilities is a sum, not a product of samples of internal expressions.

To get the nth opportunity, we return only elements from one of the capabilities of one of the subexpressions, instead of returning one of them, 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 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 does not handle parsing the expression, just processing it after parsing it.

Here is the 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); 

What prints:

ABC + ABD

AB changed as an OR expression (your second example):

AC + BC + AD + BD

Your third option may be presented as:

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

which when printed leads to:

A + B + C

Answer 2

I understand what you are asking for is a set of expressions, each of which involves input. That is, if any of these expressions is true, then the input is true.

Putting it this way, we will see that we do this by rewriting the input into a large clause, and then listing the terms. In other words, you want to rewrite your input in the Disjunctive normal form . Wikipedia tells us that “all logical formulas can be converted to a 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 the set of all children (you can apply this algorithm recursively to each of them). If you have an “and” at the top, run this recursively for each child, and then return all the “and” combinations using one of the options for each of the children.

So, for example, if you have (A | B | C), which gives you the answers A, B, C. If you have (A and (B | C)), you get only A for the left child and B, C for the right child. Therefore, combining them, you get two answers: A & B and A & C.

And if you have no, you can use De Morgan's law to insert it so you can continue to use the two rules above.

PS I answer "how to get all the answers", which asks your text, and not "how to get the smallest answer", which asks the name. This is an easy step to review all the answers and choose the smallest one.

Answer 3

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

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

Where

X, Y => expression; x => JOIN B identity - all items in list A connected to each item in list B using "&".
MERGE B - simply merges items in lists A and B

Let's look at an example of your first example to prove this: Expression - ((A & B ) & (C | D)) . Let X -> (A & B) and Y -> (C | D)

Now

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

Similarly, other examples can be sorted. In addition, the solution that you provided in Example 1 is incorrect, it should be as above.