Generalization of Boole-Shannon expansion, consistency of Boolean equations and elimination by orthonormal expansion
Abstrak
The well known Boole -Shannon expansion of Boolean functions in several variables (with coefficients in a Boolean algebraB) is also known in more general form in terms of expansion in a setof orthonormal functions. However, unlike the one variable step of this expansion an analogous elimination theorem and consistency is not well known. This article proves such an elimination theorem for a special class of Boolean functions denoted B(�). When the orthonormal setis of polynomial size in number n of variables, the consistency of a Boolean equation f = 0 can be determined in polynomial number of B-operations. A characterization of B(�) is also shown and an elimination based procedure for computing consistency of Boolean equations is proposed. Comments: 15 pages, Revised June 18, 2013 Category: cs.CC, cs.SC, ms.RA ACM class: I.1.2, F.2.2, G.2 MSC class: 03G05, 06E30, 94C10.
Topik & Kata Kunci
Penulis (1)
V. Sule
Akses Cepat
PDF tidak tersedia langsung
Cek di sumber asli →- Tahun Terbit
- 2013
- Bahasa
- en
- Total Sitasi
- 6×
- Sumber Database
- Semantic Scholar
- Akses
- Open Access ✓