Variable and term removal from Boolean formulae

DOI10.1016/S0166-218X(96)00028-5MaRDI QIDQ1363769zbMATH OpenOpenAlexFDO

Authors Oya Ekin, Yves Crama, Peter L. Hammer

Publication date 26 January 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

Boolean functions disjunctive normal forms VD-sets VF-sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Variable and term removal from Boolean formulae

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363769)