Variable and term removal from Boolean formulae (Q1363769)

Disjunctive normal forms (DNF's) \(\Phi\) over a set (of variables) \(V= \{x_1, x_2, \dots, x_n\}\) are considered. A subset \(\pi\) of the set of all DNF's (over \(V)\) is called a property. The fulfilment of four conditions (1)--(4) is supposed where (1) the trivial DNF's \(\Lambda\) and \(\Phi\) (i.e. the simplest DNF's that represent the constants 0 and 1, resp.) belong to \(\pi\), (2) there is a DNF \(\Phi\) such that \(\Phi \notin \pi\), (3) whenever every term of a DNF \(\Phi\) is a single literal, then \(\Phi \in \pi\), (4) if \(\Phi \in \pi\) and \(\Phi'\) is got by deleting a term from \(\Phi\), then \(\Phi' \in \pi\). Strengthening Condition (4), we say that \(\pi\) is a term-induced property if the containment \(\Phi \in \pi\) and the sentence ``every term of \(\Phi\) belongs to \(\pi\)'' are equivalent. Let a property \(\pi\), a DNF \(\Phi\) and a subset \(S\) of \(V\) be given. Let \(\Phi \backslash S\) be the DNF which is obtained from \(\Phi\) by deleting each occurrence (noncomplemented or complemented) of the elements of \(S\), we say that \(S\) is a VD-set of \(\Phi\) for \(\pi\) if \(\Phi \backslash S\in \pi\). We can get \(2^{|S|}\) DNF's from \(\Phi\) by fixing the elements of \(S\) (to the values 0 or 1), we say that \(S\) is a VF-set of \(\Phi\) for \(\pi\) if all these \(2^{|S|}\) DNF's belong to \(\pi\). Let us mention two typical results. If \((\Phi,S\) are arbitrary and) \(\pi\) is a term-induced property, then the VD-sets and VF-sets coincide. For any \(\pi\), the task of finding a minimum cardinality VD-set is NP-hard.