Given a list of logical formulas:

  • f1: A&B
  • f2: A&D&C
  • f3: B&D&E
  • f4: A&B&C
  • f5:
  • fn: ...

In this case I want A&B as the longest formula which is common to at least two formulas. Is there a simple algorithm to find the longest formula that could be performed on paper?

  • $\begingroup$ As I already got two downvotes: Does the question need more information or something else? $\endgroup$ – Yeti Nov 12 '17 at 19:21
  • 2
    $\begingroup$ Maybe people are wondering what you mean by "greatest common formula". I guess you mean the longest formula that's common to at least two formulas? $\endgroup$ – Bjørn Kjos-Hanssen Nov 13 '17 at 5:45
  • $\begingroup$ @BjørnKjos-Hanssen Yes, you are right. I was not able to express this myself. I will edit the question. $\endgroup$ – Yeti Nov 13 '17 at 9:51
  • 1
    $\begingroup$ Is A&C also a valid answer? $\endgroup$ – Raphael Nov 15 '17 at 22:58
  • $\begingroup$ Will all of your formulas be conjunctions of variables, or could they be something more complicated? What's the definition of "common to two formulas"? $\endgroup$ – D.W. Nov 16 '17 at 0:23

For each pair of formulas $f_i,f_j$ from your list, find the longest formula common to both $f_i,f_j$. If things are as in your example, this is as simple as a set intersection. That gives you $n(n-1)/2$ candidates. Take the candidate that is the longest.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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