Consider the set:

c1 = {h1, h2, h3, h4, h5, h6, s1, s2, s3, s4, s5, s6};

How to build a list of all possible logical sentences based on the set 'c1' and logical operators '>', '<', '&', '||' and the numbers 'k', 'f'. One of the results is for example: 'h1 <k && h2 <f || h5> k && s6> f '. Assumption: we always use the sign '>' or / and '<' and the number 'k' or / and 'f'. The sentence contains at least 3 elements from the set 'c1', at least one logical character '&', '||'.


1 Answer 1


Let's set up our atoms:

symbols = {a, b, c};
relations = {Less, Greater};
values = {k, f};
operators = {And, Or};

Now we construct the next "level":

simplePredicates = Construct @@@ Tuples[{relations, symbols, values}]
(* {a < k, a < f, b < k, b < f, c < k, c < f, a > k, a > f, b > k, b > f, c > k, c > f} *)

The constraint that we have at least three of these in any And/Or expression leads to:

predicateGroups = Subsets[simplePredicates, {3, Length@simplePredicates}];
(* 4017 *)

At this point I didn't know a built-in way to do the next level all at once, so I created helper functions. The idea is that for each predicateGroup, we'll find all tuples of the operators of size one less that the size of the predicateGroup (think of infix form). Now for the given predicate group, I want to take each of these operator lists in turn and apply those operators. InfixConstructList does this recursively for one of the operator lists.

InfixConstructList[{}, atoms_List] := atoms;
InfixConstructList[{op_, ops___}, atoms_List] := 
  InfixConstructList[{ops}, {op @@ Take[atoms, UpTo[2]], Splice[Drop[atoms, UpTo[2]]]}]

CompoundPredicates maps InfixConstructList over the operator lists we generate for each predicateGroup.

CompoundPredicates[preds : {_, __}] := 
  InfixConstructList[#, preds] & /@ Tuples[operators, Length@preds - 1]

And finally, map this over our predicateGroups

result = Flatten[CompoundPredicates /@ predicateGroups];
(* 265576 *)

And, as I suspected, this may very well be intractable for the 12 symbols you want to start with as atoms (the list c1). I haven't thought much about making a more efficient implementation, but let's just consider the number of possibilities. With 12 symbols to start with, we have 24 pairs at the lowest level, and that gives us almost 2^24 ways to pick these pairs. 2^24 is 16777216. Now we have two choices for every "slot" that is "between" pairs for each of these groupings. Our group sizes range from 3 to 24, so let's just look at, say the case of 10-pair groups. For each such 10-pair group, we have 512 ways to insert the (And/Or)s. If that were the average, we'd be over 8 billion (but of course that's not the average).

So, even if someone can come up with an efficient algorithm, what could you possibly do with all of these expressions?

Or maybe I did the math wrong. Or maybe I misunderstood the problem.

  • $\begingroup$ You're right. There will be a lot of results. So let's limit the scope. Let 'values = {0}'. Also, let simplePredicates = predicateGroups We also need to check the logical correctness of sentences because e.g. a <0 && b <0 && c <0 && a> 0 && b> 0 && c> 0 is not a true sentence: a <0 ..and .. a> 0 $\endgroup$
    – ralph
    Commented Oct 26, 2022 at 8:23
  • $\begingroup$ Map [TautologyQ, result] does not fully resolve the problem: e.g. the case remains: a <0 && b <0 && c <0 && a> 0 && b> 0 && c> 0 where we still have illogicality e.g. a <0 && a> 0 $\endgroup$
    – ralph
    Commented Oct 26, 2022 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.