IEICE TRANSACTIONS on Fundamentals
Horn Functions with a Single Two-Negated Term
Summary :
Horn functions are Boolean functions where each of the prime implicants contains at most one negative literal. A class of Boolean functions is considered in this letter where a single term containing two negative literals is added by logical-or operation to a Horn function. We show that the function does not have any prime implicant containing three negative literals. We also show that if two terms containing two negative literals are added to a Horn function, then it may have many prime implicants all of which contain three negative literals. We show that it is P-complete to determine whether a given Boolean function in disjunctive normal form of the considered class is a tautology.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.11 pp.3264-3266
- Publication Date
- 2005/11/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietfec/e88-a.11.3264
- Type of Manuscript
- LETTER
- Category
- General Fundamentals and Boundaries
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Naoki KAWAMURA, Shigeki IWATA, "Horn Functions with a Single Two-Negated Term" in IEICE TRANSACTIONS on Fundamentals,
vol. E88-A, no. 11, pp. 3264-3266, November 2005, doi: 10.1093/ietfec/e88-a.11.3264.
Abstract: Horn functions are Boolean functions where each of the prime implicants contains at most one negative literal. A class of Boolean functions is considered in this letter where a single term containing two negative literals is added by logical-or operation to a Horn function. We show that the function does not have any prime implicant containing three negative literals. We also show that if two terms containing two negative literals are added to a Horn function, then it may have many prime implicants all of which contain three negative literals. We show that it is P-complete to determine whether a given Boolean function in disjunctive normal form of the considered class is a tautology.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.11.3264/_p
Copy
@ARTICLE{e88-a_11_3264,
author={Naoki KAWAMURA, Shigeki IWATA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Horn Functions with a Single Two-Negated Term},
year={2005},
volume={E88-A},
number={11},
pages={3264-3266},
abstract={Horn functions are Boolean functions where each of the prime implicants contains at most one negative literal. A class of Boolean functions is considered in this letter where a single term containing two negative literals is added by logical-or operation to a Horn function. We show that the function does not have any prime implicant containing three negative literals. We also show that if two terms containing two negative literals are added to a Horn function, then it may have many prime implicants all of which contain three negative literals. We show that it is P-complete to determine whether a given Boolean function in disjunctive normal form of the considered class is a tautology.},
keywords={},
doi={10.1093/ietfec/e88-a.11.3264},
ISSN={},
month={November},}
Copy
TY - JOUR
TI - Horn Functions with a Single Two-Negated Term
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3264
EP - 3266
AU - Naoki KAWAMURA
AU - Shigeki IWATA
PY - 2005
DO - 10.1093/ietfec/e88-a.11.3264
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2005
AB - Horn functions are Boolean functions where each of the prime implicants contains at most one negative literal. A class of Boolean functions is considered in this letter where a single term containing two negative literals is added by logical-or operation to a Horn function. We show that the function does not have any prime implicant containing three negative literals. We also show that if two terms containing two negative literals are added to a Horn function, then it may have many prime implicants all of which contain three negative literals. We show that it is P-complete to determine whether a given Boolean function in disjunctive normal form of the considered class is a tautology.
ER -
English
