def to_cnf(expr, simplify=False):
    """
    Convert a propositional logical sentence s to conjunctive normal form.
    That is, of the form ((A | ~B | ...) & (B | C | ...) & ...)

    Examples
    ========

    >>> from sympy.logic.boolalg import to_cnf
    >>> from sympy.abc import A, B, D
    >>> to_cnf(~(A | B) | D)
    And(Or(D, Not(A)), Or(D, Not(B)))

    """
    expr = sympify(expr)
    if not isinstance(expr, BooleanFunction):
        return expr

    if simplify:
        simplified_expr = distribute_and_over_or(simplify_logic(expr))
        if len(simplified_expr.args) < len(to_cnf(expr).args):
            return simplified_expr
        else:
            return to_cnf(expr)

    # Don't convert unless we have to
    if is_cnf(expr):
        return expr

    expr = eliminate_implications(expr)
    return distribute_and_over_or(expr)

def to_dnf(expr, simplify=False):
    """
    Convert a propositional logical sentence s to disjunctive normal form.
    That is, of the form ((A & ~B & ...) | (B & C & ...) | ...)

    Examples
    ========

    >>> from sympy.logic.boolalg import to_dnf
    >>> from sympy.abc import A, B, C, D
    >>> to_dnf(B & (A | C))
    Or(And(A, B), And(B, C))

    """
    expr = sympify(expr)
    if not isinstance(expr, BooleanFunction):
        return expr

    if simplify:
        simplified_expr = distribute_or_over_and(simplify_logic(expr))
        if len(simplified_expr.args) < len(to_dnf(expr).args):
            return simplified_expr
        else:
            return to_dnf(expr)

    # Don't convert unless we have to
    if is_dnf(expr):
        return expr

    expr = eliminate_implications(expr)
    return distribute_or_over_and(expr)

def eliminate_implications(expr):
    """
    Change >>, <<, and Equivalent into &, |, and ~. That is, return an
    expression that is equivalent to s, but has only &, |, and ~ as logical
    operators.

    Examples
    ========

    >>> from sympy.logic.boolalg import Implies, Equivalent, \
         eliminate_implications
    >>> from sympy.abc import A, B, C
    >>> eliminate_implications(Implies(A, B))
    Or(B, Not(A))
    >>> eliminate_implications(Equivalent(A, B))
    And(Or(A, Not(B)), Or(B, Not(A)))
    """
    expr = sympify(expr)
    if expr.is_Atom:
        return expr  # (Atoms are unchanged.)
    args = map(eliminate_implications, expr.args)
    if expr.func is Implies:
        a, b = args[0], args[-1]
        return (~a) | b
    elif expr.func is Equivalent:
        a, b = args[0], args[-1]
        return (a | Not(b)) & (b | Not(a))
    else:
        return expr.func(*args)

 def test_symbolify__decimals(self):
     """Tests presence of decimal in value to be evaluated.
     """
     query_args = {'filter_string': 'AF > 0.5'}
     evaluator = VariantFilterEvaluator(query_args, self.ref_genome)
     EXPECTED_SYMBOLIC_REP = sympify('A')
     self.assertEqual(EXPECTED_SYMBOLIC_REP, evaluator.sympy_representation)
     self.assertEqual('AF > 0.5',
             evaluator.symbol_to_expression_map['A'])

    def test_variant_filter_constructor(self):
        """Tests the constructor.
        """
        query_args = {'filter_string': 'position > 5'}
        evaluator = VariantFilterEvaluator(query_args, self.ref_genome)
        EXPECTED_SYMBOLIC_REP = sympify('A')
        self.assertEqual(EXPECTED_SYMBOLIC_REP, evaluator.sympy_representation)
        self.assertEqual('position > 5',
                evaluator.symbol_to_expression_map['A'])

        query_args = {'filter_string': 'position>5 & GT= 2'}
        evaluator = VariantFilterEvaluator(query_args, self.ref_genome)
        EXPECTED_SYMBOLIC_REP = sympify('A & B')
        self.assertEqual(EXPECTED_SYMBOLIC_REP, evaluator.sympy_representation)
        self.assertEqual('position>5 ',
                evaluator.symbol_to_expression_map['A'])
        self.assertEqual('GT= 2',
                evaluator.symbol_to_expression_map['B'])

def compile_rule(s):
    """
    Transforms a rule into a SymPy expression
    A rule is a string of the form "symbol1 & symbol2 | ..."

    Note: This function is deprecated.  Use sympify() instead.

    """
    import re
    return sympify(re.sub(r'([a-zA-Z_][a-zA-Z0-9_]*)', r'Symbol("\1")', s))

    def test_variant_filter_constructor(self):
        """Tests the constructor.
        """
        query_args = {'filter_string': 'position > 5'}
        evaluator = VariantFilterEvaluator(query_args, self.ref_genome)
        EXPECTED_SYMBOLIC_REP = sympify('A')
        self.assertEqual(EXPECTED_SYMBOLIC_REP, evaluator.sympy_representation)
        self.assertEqual('position > 5',
                evaluator.symbol_to_expression_map['A'])

        # Test &.
        query_args = {'filter_string': 'position>5 & GT= 2'}
        evaluator = VariantFilterEvaluator(query_args, self.ref_genome)
        EXPECTED_SYMBOLIC_REP = sympify('A & B')
        self.assertEqual(EXPECTED_SYMBOLIC_REP, evaluator.sympy_representation)
        self.assertEqual('position>5 ',
                evaluator.symbol_to_expression_map['A'])
        self.assertEqual('GT= 2',
                evaluator.symbol_to_expression_map['B'])

        # Test decimals.
        query_args = {'filter_string': 'AF > 0.5'}
        evaluator = VariantFilterEvaluator(query_args, self.ref_genome)
        EXPECTED_SYMBOLIC_REP = sympify('A')
        self.assertEqual(EXPECTED_SYMBOLIC_REP, evaluator.sympy_representation)
        self.assertEqual('AF > 0.5',
                evaluator.symbol_to_expression_map['A'])

        # Test hyphens
        QUERY = 'EXPERIMENT_SAMPLE_LABEL = C-E5-2'
        query_args = {'filter_string': QUERY}
        evaluator = VariantFilterEvaluator(query_args, self.ref_genome)
        EXPECTED_SYMBOLIC_REP = sympify('A')
        self.assertEqual(EXPECTED_SYMBOLIC_REP, evaluator.sympy_representation)
        self.assertEqual(QUERY, evaluator.symbol_to_expression_map['A'])

        # Test quotes
        QUERY = 'EXPERIMENT_SAMPLE_LABEL = "C-E5-2"'
        query_args = {'filter_string': QUERY}
        evaluator = VariantFilterEvaluator(query_args, self.ref_genome)
        EXPECTED_SYMBOLIC_REP = sympify('A')
        self.assertEqual(EXPECTED_SYMBOLIC_REP, evaluator.sympy_representation)
        self.assertEqual(QUERY, evaluator.symbol_to_expression_map['A'])

def POSform(variables, minterms, dontcares=None):
    """
    The POSform function uses simplified_pairs and a redundant-group
    eliminating algorithm to convert the list of all input combinations
    that generate '1' (the minterms) into the smallest Product of Sums form.

    The variables must be given as the first argument.

    Return a logical And function (i.e., the "product of sums" or "POS"
    form) that gives the desired outcome. If there are inputs that can
    be ignored, pass them as a list, too.

    The result will be one of the (perhaps many) functions that satisfy
    the conditions.

    Examples
    ========

    >>> from sympy.logic import POSform
    >>> minterms = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1],
    ...             [1, 0, 1, 1], [1, 1, 1, 1]]
    >>> dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
    >>> POSform(['w','x','y','z'], minterms, dontcares)
    And(Or(Not(w), y), z)

    References
    ==========

    .. [1] en.wikipedia.org/wiki/Quine-McCluskey_algorithm

    """
    from sympy.core.symbol import Symbol

    variables = [sympify(v) for v in variables]
    if minterms == []:
        return False

    minterms = [list(i) for i in minterms]
    dontcares = [list(i) for i in (dontcares or [])]
    for d in dontcares:
        if d in minterms:
            raise ValueError('%s in minterms is also in dontcares' % d)

    maxterms = []
    for t in product([0, 1], repeat=len(variables)):
        t = list(t)
        if (t not in minterms) and (t not in dontcares):
            maxterms.append(t)
    old = None
    new = maxterms + dontcares
    while new != old:
        old = new
        new = _simplified_pairs(old)
    essential = _rem_redundancy(new, maxterms)
    return And(*[_convert_to_varsPOS(x, variables) for x in essential])

def is_cnf(expr):
    """
    Test whether or not an expression is in conjunctive normal form.

    Examples
    ========

    >>> from sympy.logic.boolalg import is_cnf
    >>> from sympy.abc import A, B, C
    >>> is_cnf(A | B | C)
    True
    >>> is_cnf(A & B & C)
    True
    >>> is_cnf((A & B) | C)
    False

    """
    expr = sympify(expr)

    # Special case of a single disjunction
    if expr.func is Or:
        for lit in expr.args:
            if lit.func is Not:
                if not lit.args[0].is_Atom:
                    return False
            else:
                if not lit.is_Atom:
                    return False
        return True

    # Special case of a single negation
    if expr.func is Not:
        if not expr.args[0].is_Atom:
            return False

    if expr.func is not And:
        return False

    for cls in expr.args:
        if cls.is_Atom:
            continue
        if cls.func is Not:
            if not cls.args[0].is_Atom:
                return False
        elif cls.func is not Or:
            return False
        for lit in cls.args:
            if lit.func is Not:
                if not lit.args[0].is_Atom:
                    return False
            else:
                if not lit.is_Atom:
                    return False

    return True

def POSform(variables, minterms, dontcares=[]):
    """
    The POSform function uses simplified_pairs and a redundant-group
    eliminating algorithm to convert the list of all input combinations
    that generate '1' (the minterms) into the smallest Product of Sums form.

    The variables must be given as the first argument.

    Return a logical And function (i.e., the "product of sums" or "POS"
    form) that gives the desired outcome. If there are inputs that can
    be ignored, pass them as a list too.

    The result will be one of the (perhaps many) functions that satisfy
    the conditions.

    Examples
    ========

    >>> from sympy.logic import POSform
    >>> minterms = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1],
    ...             [1, 0, 1, 1], [1, 1, 1, 1]]
    >>> dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
    >>> POSform(['w','x','y','z'], minterms, dontcares)
    And(Or(Not(w), y), z)

    References
    ==========

    .. [1] en.wikipedia.org/wiki/Quine-McCluskey_algorithm

    """
    variables = [str(v) for v in variables]
    from sympy.core.compatibility import bin
    if minterms == []:
        return False
    t = [0] * len(variables)
    maxterms = []
    for x in range(2 ** len(variables)):
        b = [int(y) for y in bin(x)[2:]]
        t[-len(b):] = b
        if (t not in minterms) and (t not in dontcares):
            maxterms.append(t[:])
    l2 = [1]
    l1 = maxterms + dontcares
    while (l1 != l2):
        l1 = _simplified_pairs(l1)
        l2 = _simplified_pairs(l1)
    string = _rem_redundancy(l1, maxterms, variables, 2)
    if string == '':
        return True
    return sympify(string)

def SOPform(variables, minterms, dontcares=None):
    """
    The SOPform function uses simplified_pairs and a redundant group-
    eliminating algorithm to convert the list of all input combos that
    generate '1' (the minterms) into the smallest Sum of Products form.

    The variables must be given as the first argument.

    Return a logical Or function (i.e., the "sum of products" or "SOP"
    form) that gives the desired outcome. If there are inputs that can
    be ignored, pass them as a list, too.

    The result will be one of the (perhaps many) functions that satisfy
    the conditions.

    Examples
    ========

    >>> from sympy.logic import SOPform
    >>> minterms = [[0, 0, 0, 1], [0, 0, 1, 1],
    ...             [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]]
    >>> dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
    >>> SOPform(['w','x','y','z'], minterms, dontcares)
    Or(And(Not(w), z), And(y, z))

    References
    ==========

    .. [1] en.wikipedia.org/wiki/Quine-McCluskey_algorithm

    """
    from sympy.core.symbol import Symbol

    variables = [sympify(v) for v in variables]
    if minterms == []:
        return False

    minterms = [list(i) for i in minterms]
    dontcares = [list(i) for i in (dontcares or [])]
    for d in dontcares:
        if d in minterms:
            raise ValueError('%s in minterms is also in dontcares' % d)

    old = None
    new = minterms + dontcares
    while new != old:
        old = new
        new = _simplified_pairs(old)
    essential = _rem_redundancy(new, minterms)
    return Or(*[_convert_to_varsSOP(x, variables) for x in essential])

def to_cnf(expr):
    """Convert a propositional logical sentence s to conjunctive normal form.
    That is, of the form ((A | ~B | ...) & (B | C | ...) & ...)

    Examples:

        >>> from sympy.logic.boolalg import to_cnf
        >>> from sympy.abc import A, B, D
        >>> to_cnf(~(A | B) | D)
        And(Or(D, Not(A)), Or(D, Not(B)))

    """
    expr = sympify(expr)
    expr = eliminate_implications(expr)
    return distribute_and_over_or(expr)

def _is_form(expr, function1, function2):
    """
    Test whether or not an expression is of the required form.

    """
    expr = sympify(expr)

    # Special case of an Atom
    if expr.is_Atom:
        return True

    # Special case of a single expression of function2
    if expr.func is function2:
        for lit in expr.args:
            if lit.func is Not:
                if not lit.args[0].is_Atom:
                    return False
            else:
                if not lit.is_Atom:
                    return False
        return True

    # Special case of a single negation
    if expr.func is Not:
        if not expr.args[0].is_Atom:
            return False

    if expr.func is not function1:
        return False

    for cls in expr.args:
        if cls.is_Atom:
            continue
        if cls.func is Not:
            if not cls.args[0].is_Atom:
                return False
        elif cls.func is not function2:
            return False
        for lit in cls.args:
            if lit.func is Not:
                if not lit.args[0].is_Atom:
                    return False
            else:
                if not lit.is_Atom:
                    return False

    return True

def eliminate_implications(expr):
    """Change >>, <<, and Equivalent into &, |, and ~. That is, return an
    expression that is equivalent to s, but has only &, |, and ~ as logical
    operators.
    """
    expr = sympify(expr)
    if expr.is_Atom:
        return expr     ## (Atoms are unchanged.)
    args = map(eliminate_implications, expr.args)
    if expr.func is Implies:
        a, b = args[0], args[-1]
        return (~a) | b
    elif expr.func is Equivalent:
        a, b = args[0], args[-1]
        return (a | Not(b)) & (b | Not(a))
    else:
        return expr.func(*args)

def SOPform(variables, minterms, dontcares=[]):
    """
    The SOPform function uses simplified_pairs and a redundant group-
    eliminating algorithm to convert the list of all input combos that
    generate '1'(the minterms) into the smallest Sum of Products form.

    The variables must be given as the first argument.

    Return a logical Or function (i.e., the "sum of products" or "SOP"
    form) that gives the desired outcome. If there are inputs that can
    be ignored, pass them as a list too.

    The result will be one of the (perhaps many) functions that satisfy
    the conditions.

    Examples
    ========

    >>> from sympy.logic import SOPform
    >>> minterms = [[0, 0, 0, 1], [0, 0, 1, 1],
    ...             [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]]
    >>> dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
    >>> SOPform(['w','x','y','z'], minterms, dontcares)
        Or(And(Not(w), z), And(y, z))

    References
    ==========

    .. [1] en.wikipedia.org/wiki/Quine-McCluskey_algorithm

    """
    variables = [str(v) for v in variables]
    if minterms == []:
        return False
    l2 = [1]
    l1 = minterms + dontcares
    while (l1 != l2):
        l1 = _simplified_pairs(l1)
        l2 = _simplified_pairs(l1)
    string = _rem_redundancy(l1, minterms, variables, 1)
    if string == '':
        return True
    return sympify(string)

def compile_rule(s):
    """
    Transforms a rule into a SymPy expression
    A rule is a string of the form "symbol1 & symbol2 | ..."

    Note: this is nearly the same as sympifying the expression, but
    this function converts all variables to Symbols -- there are no
    special function names recognized.

    Examples
    ========

    >>> from sympy.logic.boolalg import compile_rule
    >>> compile_rule('A & B')
    And(A, B)
    >>> compile_rule('(~B & ~C)|A')
    Or(A, And(Not(B), Not(C)))
    """
    import re
    return sympify(re.sub(r'([a-zA-Z_][a-zA-Z0-9_]*)', r'Symbol("\1")', s))

def simplify_logic(expr, simplify=True):
    """
    This function simplifies a boolean function to its
    simplified version in SOP or POS form. The return type is an
    Or or And object in SymPy. The input can be a string or a boolean
    expression.  The optional parameter simplify indicates whether to
    recursively simplify any non-boolean-functions contained within the
    input.

    Examples
    ========

    >>> from sympy.logic import simplify_logic
    >>> from sympy.abc import x, y, z
    >>> from sympy import S
    >>> b = '(~x & ~y & ~z) | ( ~x & ~y & z)'
    >>> simplify_logic(b)
    And(Not(x), Not(y))

    >>> S(b)
    Or(And(Not(x), Not(y), Not(z)), And(Not(x), Not(y), z))
    >>> simplify_logic(_)
    And(Not(x), Not(y))

    """
    expr = sympify(expr)
    if not isinstance(expr, BooleanFunction):
        return expr
    variables = _find_predicates(expr)
    truthtable = []
    for t in product([0, 1], repeat=len(variables)):
        t = list(t)
        if expr.xreplace(dict(zip(variables, t))) == True:
            truthtable.append(t)
    if simplify:
        from sympy.simplify.simplify import simplify
        variables = [simplify(v) for v in variables]
    if (len(truthtable) >= (2 ** (len(variables) - 1))):
        return SOPform(variables, truthtable)
    else:
        return POSform(variables, truthtable)

def simplify_logic(expr):
    """
    This function simplifies a boolean function to its
    simplified version in SOP or POS form. The return type is a
    Or object or And object in SymPy. The input can be a string
    or a boolean expression.

    Examples
    ========

    >>> from sympy.logic import simplify_logic
    >>> from sympy.abc import x, y, z
    >>> from sympy import S

    >>> b = '(~x & ~y & ~z) | ( ~x & ~y & z)'
    >>> simplify_logic(b)
    And(Not(x), Not(y))

    >>> S(b)
    Or(And(Not(x), Not(y), Not(z)), And(Not(x), Not(y), z))
    >>> simplify_logic(_)
    And(Not(x), Not(y))

    """
    from sympy.core.compatibility import bin
    expr = sympify(expr)
    variables = list(expr.free_symbols)
    string_variables = [x.name for x in variables]
    truthtable = []
    t = [0] * len(variables)
    for x in range(2 ** len(variables)):
        b = [int(y) for y in bin(x)[2:]]
        t[-len(b):] = b
        if expr.subs(zip(variables, [bool(i) for i in t])) is True:
            truthtable.append(t[:])
    if (len(truthtable) >= (2 ** (len(variables) - 1))):
        return SOPform(string_variables, truthtable)
    else:
        return POSform(string_variables, truthtable)

def simplify_logic(expr):
    """
    This function simplifies a boolean function to its
    simplified version in SOP or POS form. The return type is an
    Or or And object in SymPy. The input can be a string or a boolean
    expression.

    Examples
    ========

    >>> from sympy.logic import simplify_logic
    >>> from sympy.abc import x, y, z
    >>> from sympy import S

    >>> b = '(~x & ~y & ~z) | ( ~x & ~y & z)'
    >>> simplify_logic(b)
    And(Not(x), Not(y))

    >>> S(b)
    Or(And(Not(x), Not(y), Not(z)), And(Not(x), Not(y), z))
    >>> simplify_logic(_)
    And(Not(x), Not(y))

    """
    expr = sympify(expr)
    if not isinstance(expr, BooleanFunction):
        return expr
    variables = list(expr.free_symbols)
    truthtable = []
    for t in product([0, 1], repeat=len(variables)):
        t = list(t)
        if expr.subs(zip(variables, t)) == True:
            truthtable.append(t)
    if (len(truthtable) >= (2 ** (len(variables) - 1))):
        return SOPform(variables, truthtable)
    else:
        return POSform(variables, truthtable)