# Paper-based algorithm to find longest formula which is common to at least two formulas

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?

• As I already got two downvotes: Does the question need more information or something else? – Yeti Nov 12 '17 at 19:21
• 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? – Bjørn Kjos-Hanssen Nov 13 '17 at 5:45
• @BjørnKjos-Hanssen Yes, you are right. I was not able to express this myself. I will edit the question. – Yeti Nov 13 '17 at 9:51
• Is A&C also a valid answer? – Raphael Nov 15 '17 at 22:58
• 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"? – 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.