Counting Falsifying Assignments of a 2-CF via Recurrence Equations

We consider the problem - #2UNSAT (counting the number of falsifying assignments for two conjunctive forms). Because #2SAT(F) = 2 super(n) - #2UNSAT(F), results about #2UNSAT can dually be established for solving #2SAT. We establish the kind of two conjunctive formulas with a minimum number of falsi...

Full description

Saved in:
Bibliographic Details
Published in:Engineering letters 2015-04, Vol.23 (2)
Main Authors: Luna, Guillermo De Ita, Romero, J Raymundo Marcial, Flores, Fernando Zacarias, Gonzalez, Meliza Contreras, Lopez, Pedro Bello
Format: Article
Language:English
Subjects:
Computation
Counting
Formulas (mathematics)
Mathematical analysis
Mathematical models
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem - #2UNSAT (counting the number of falsifying assignments for two conjunctive forms). Because #2SAT(F) = 2 super(n) - #2UNSAT(F), results about #2UNSAT can dually be established for solving #2SAT. We establish the kind of two conjunctive formulas with a minimum number of falsifying assignment. As a result, we determine the formulas with a maximum number of models among the set of all 2-CF formulas with a same number of variables. We have shown that for any 2-F sub(n) with n variables, #UNSAT(F sub(n))> or = #SAT(F sub(n)) with the exception of totally dependent formulas. Thus, if #UNSAT(F sub(n)) [< or =] p(n) for a polynomial on n, then #SAT(F sub(n)) [< or =] p(n) too, and then #SAT(F sub(n)) can be computed in polynomial time on the size of the formula.
ISSN:1816-093X
1816-0948