If g is a monotone boolean function depending on all its variables, the property that each prime implicant of g intersects each prime clause of g in a singleton is a well-known necessary condition for g to be computable by a formula with no repeated variable, and only using the connectives and, or. We prove that the condition is also sufficient. Our proof uses matroid theory.
Functions computed by monotone Boolean formulas with no repeated variables / D. MUNDICI. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 66:(1989), pp. 113-114. [10.1016/0304-3975(89)90150-3]
Functions computed by monotone Boolean formulas with no repeated variables
MUNDICI, DANIELE
1989
Abstract
If g is a monotone boolean function depending on all its variables, the property that each prime implicant of g intersects each prime clause of g in a singleton is a well-known necessary condition for g to be computable by a formula with no repeated variable, and only using the connectives and, or. We prove that the condition is also sufficient. Our proof uses matroid theory.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
