# Boolean Lattice Implementation

Let $$X = \{1,2,\dots n\}$$, and $$Y= \{ S\subset X: |S|\le 2\}$$. I am interested in "avoidance sets" $$A \subset Y$$ which logically are supposed to correspond to $$f(A):=\bigwedge_{a\in A} \lnot a$$ in the Boolean lattice defined over $$\mathcal{P}(X)$$. (if $$A = \{\}$$ it shall correspond to $$X$$, the maximal element of our lattice)

Given a list of avoidance sets $$A_1,A_2,\dots A_k$$, I want to return an avoidance set $$A’$$ such that $$f(A’)$$ is the least upper bound of $$\bigvee_{1\le i \le k} f(A_i)$$. (by least upper bound I mean the least upper bound which can be represented by an avoidance set)

Can this be done in time linear to $$\sum_{1\le i \le k} |A_i|$$? (you may assume that all the sets $$A_i$$ are simplified, i.e. if $$\{a\}\in A_i$$ and $$\{b\}\in A_i$$ then $$\{a,b\} \not \in A_i$$)