Horn Functions with a Single Two-Negated Term

Naoki KAWAMURA; Shigeki IWATA

doi:10.1093/ietfec/e88-a.11.3264

Horn Functions with a Single Two-Negated Term

Naoki KAWAMURA, Shigeki IWATA

Full Text Views

0

Share
Cite this

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

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://globals.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 -