def test_to_cnf():
    assert to_cnf(~(B | C)) == And(Not(B), Not(C))
    assert to_cnf((A & B) | C) == And(Or(A, C), Or(B, C))
    assert to_cnf(A >> B) == (~A) | B
    assert to_cnf(A >> (B & C)) == (~A | B) & (~A | C)
    assert to_cnf(A & (B | C) | ~A & (B | C), True) == B | C
    assert to_cnf(A & B) == And(A, B)

    assert to_cnf(Equivalent(A, B)) == And(Or(A, Not(B)), Or(B, Not(A)))
    assert to_cnf(Equivalent(A, B & C)) == \
        (~A | B) & (~A | C) & (~B | ~C | A)
    assert to_cnf(Equivalent(A, B | C), True) == \
        And(Or(Not(B), A), Or(Not(C), A), Or(B, C, Not(A)))
    assert to_cnf(A + 1) == A + 1

def compute_known_facts():
    """Compute the various forms of knowledge compilation used by the
    assumptions system.
    """
    # Compute the known facts in CNF form for logical inference
    fact_string = " -{ Known facts in CNF }-\n"
    cnf = to_cnf(known_facts)
    fact_string += "known_facts_cnf = And( \\\n   ",
    fact_string += ", \\\n    ".join(map(str, cnf.args))
    fact_string += "\n)\n"

    # Compute the quick lookup for single facts
    from sympy.abc import x
    mapping = {}
    for key in known_facts_keys:
        mapping[key] = set([key])
        for other_key in known_facts_keys:
            if other_key != key:
                if ask(x, other_key, Assume(x, key, False), disable_preprocessing=True):
                    mapping[key].add(Not(other_key))
    fact_string += "\n\n -{ Known facts in compressed sets }-\n"
    fact_string += "known_facts_dict = { \\\n   ",
    fact_string += ", \\\n    ".join(["%s: %s" % item for item in mapping.items()])
    fact_string += "\n}\n"
    return fact_string

 def process_conds(cond):
     """
     Turn ``cond`` into a strip (a, b), and auxiliary conditions.
     """
     a = -oo
     b = oo
     aux = True
     conds = conjuncts(to_cnf(cond))
     t = Dummy('t', real=True)
     for c in conds:
         a_ = oo
         b_ = -oo
         aux_ = []
         for d in disjuncts(c):
             d_ = d.replace(re, lambda x: x.as_real_imag()[0]).subs(re(s), t)
             if not d.is_Relational or (d.rel_op != '<' and d.rel_op != '<=') \
                or d_.has(s) or not d_.has(t):
                 aux_ += [d]
                 continue
             soln = _solve_inequality(d_, t)
             if not soln.is_Relational or \
                (soln.rel_op != '<' and soln.rel_op != '<='):
                 aux_ += [d]
                 continue
             if soln.lhs == t:
                 b_ = Max(soln.rhs, b_)
             else:
                 a_ = Min(soln.lhs, a_)
         if a_ != oo and a_ != b:
             a = Max(a_, a)
         elif b_ != -oo and b_ != a:
             b = Min(b_, b)
         else:
             aux = And(aux, Or(*aux_))
     return a, b, aux

    def ask(self, query):
        """Checks if the query is true given the set of clauses.

        Examples
        ========

        >>> from sympy.logic.inference import PropKB
        >>> from sympy.abc import x, y
        >>> l = PropKB()
        >>> l.tell(x & ~y)
        >>> l.ask(x)
        True
        >>> l.ask(y)
        False
        """
        if len(self.clauses) == 0:
            return False
        from sympy.logic.algorithms.dpll import dpll

        query_conjuncts = self.clauses[:]
        query_conjuncts.extend(conjuncts(to_cnf(query)))
        s = set()
        for q in query_conjuncts:
            s = s.union(q.atoms(C.Symbol))
        return bool(dpll(query_conjuncts, list(s), {}))

def compute_known_facts(known_facts, known_facts_keys):
    """Compute the various forms of knowledge compilation used by the
    assumptions system.
    """
    from textwrap import dedent, wrap

    fact_string = dedent('''\
    from sympy.logic.boolalg import And, Not, Or
    from sympy.assumptions.ask import Q

    # -{ Known facts in CNF }-
    known_facts_cnf = And(
        %s
    )

    # -{ Known facts in compressed sets }-
    known_facts_dict = {
        %s
    }''')
    # Compute the known facts in CNF form for logical inference
    LINE = ",\n    "
    HANG = ' '*8
    cnf = to_cnf(known_facts)
    c = LINE.join([str(a) for a in cnf.args])
    mapping = single_fact_lookup(known_facts_keys, cnf)
    m = LINE.join(['\n'.join(
        wrap("%s: %s" % item,
            subsequent_indent=HANG,
            break_long_words=False))
        for item in mapping.items()])
    return fact_string % (c, m)

def satisfiable(expr, algorithm="dpll2"):
    """
    Check satisfiability of a propositional sentence.
    Returns a model when it succeeds

    Examples:

    >>> from sympy.abc import A, B
    >>> from sympy.logic.inference import satisfiable
    >>> satisfiable(A & ~B)
    {A: True, B: False}
    >>> satisfiable(A & ~A)
    False

    """
    expr = to_cnf(expr)
    if algorithm == "dpll":
        from sympy.logic.algorithms.dpll import dpll_satisfiable

        return dpll_satisfiable(expr)
    elif algorithm == "dpll2":
        from sympy.logic.algorithms.dpll2 import dpll_satisfiable

        return dpll_satisfiable(expr)
    raise NotImplementedError

def dpll_satisfiable(expr):
    """
    Check satisfiability of a propositional sentence.
    It returns a model rather than True when it succeeds

    >>> from sympy.abc import A, B
    >>> from sympy.logic.algorithms.dpll import dpll_satisfiable
    >>> dpll_satisfiable(A & ~B)
    {A: True, B: False}
    >>> dpll_satisfiable(A & ~A)
    False

    """
    clauses = conjuncts(to_cnf(expr))
    if False in clauses:
        return False
    symbols = sorted(_find_predicates(expr), key=default_sort_key)
    symbols_int_repr = set(range(1, len(symbols) + 1))
    clauses_int_repr = to_int_repr(clauses, symbols)
    result = dpll_int_repr(clauses_int_repr, symbols_int_repr, {})
    if not result:
        return result
    output = {}
    for key in result:
        output.update({symbols[key - 1]: result[key]})
    return output

def dpll_satisfiable(expr):
    """
    Check satisfiability of a propositional sentence.
    It returns a model rather than True when it succeeds

    Examples
    ========

    >>> from sympy.abc import A, B
    >>> from sympy.logic.algorithms.dpll2 import dpll_satisfiable
    >>> dpll_satisfiable(A & ~B)
    {A: True, B: False}
    >>> dpll_satisfiable(A & ~A)
    False

    """
    clauses = conjuncts(to_cnf(expr))
    if False in clauses:
        return False
    symbols = sorted(_find_predicates(expr), key=default_sort_key)
    symbols_int_repr = range(1, len(symbols) + 1)
    clauses_int_repr = to_int_repr(clauses, symbols)

    solver = SATSolver(clauses_int_repr, symbols_int_repr, set())
    result = solver._find_model()

    if not result:
        return result
    # Uncomment to confirm the solution is valid (hitting set for the clauses)
    #else:
        #for cls in clauses_int_repr:
            #assert solver.var_settings.intersection(cls)

    return dict((symbols[abs(lit) - 1], lit > 0) for lit in solver.var_settings)

def compute_known_facts():
    """Compute the various forms of knowledge compilation used by the
    assumptions system.
    """
    # Compute the known facts in CNF form for logical inference
    fact_string = "# -{ Known facts in CNF }-\n"
    cnf = to_cnf(known_facts)
    fact_string += "known_facts_cnf = And(\n    "
    fact_string += ",\n    ".join(map(str, cnf.args))
    fact_string += "\n)\n"

    # Compute the quick lookup for single facts
    mapping = {}
    for key in known_facts_keys:
        mapping[key] = set([key])
        for other_key in known_facts_keys:
            if other_key != key:
                if ask_full_inference(other_key, key):
                    mapping[key].add(other_key)
    fact_string += "\n# -{ Known facts in compressed sets }-\n"
    fact_string += "known_facts_dict = {\n    "
    fact_string += ",\n    ".join(
        ["%s: %s" % item for item in mapping.items()])
    fact_string += "\n}\n"
    return fact_string

def compute_known_facts(known_facts, known_facts_keys):
    """Compute the various forms of knowledge compilation used by the
    assumptions system.

    This function is typically applied to the results of the ``get_known_facts``
    and ``get_known_facts_keys`` functions defined at the bottom of
    this file.
    """
    from textwrap import dedent, wrap

    fact_string = dedent(
        '''\
    """
    The contents of this file are the return value of
    ``sympy.assumptions.ask.compute_known_facts``.

    Do NOT manually edit this file.
    Instead, run ./bin/ask_update.py.
    """

    from sympy.core.cache import cacheit
    from sympy.logic.boolalg import And, Not, Or
    from sympy.assumptions.ask import Q

    # -{ Known facts in Conjunctive Normal Form }-
    @cacheit
    def get_known_facts_cnf():
        return And(
            %s
        )

    # -{ Known facts in compressed sets }-
    @cacheit
    def get_known_facts_dict():
        return {
            %s
        }
    '''
    )
    # Compute the known facts in CNF form for logical inference
    LINE = ",\n        "
    HANG = " " * 8
    cnf = to_cnf(known_facts)
    c = LINE.join([str(a) for a in cnf.args])
    mapping = single_fact_lookup(known_facts_keys, cnf)
    items = sorted(mapping.items(), key=str)
    keys = [str(i[0]) for i in items]
    values = ["set(%s)" % sorted(i[1], key=str) for i in items]
    m = (
        LINE.join(
            [
                "\n".join(wrap("%s: %s" % (k, v), subsequent_indent=HANG, break_long_words=False))
                for k, v in zip(keys, values)
            ]
        )
        + ","
    )
    return fact_string % (c, m)

 def ask(self, query):
     """TODO: examples"""
     if len(self.clauses) == 0: return False
     query_conjuncts = self.clauses[:]
     query_conjuncts.extend(conjuncts(to_cnf(query)))
     s = set()
     for q in query_conjuncts:
         s = s.union(q.atoms(Symbol))
     return bool(dpll(query_conjuncts, list(s), {}))

 def ask(self, query):
     """TODO: examples"""
     if len(self.clauses) == 0: return False
     from sympy.logic.algorithms.dpll import dpll
     query_conjuncts = self.clauses[:]
     query_conjuncts.extend(conjuncts(to_cnf(query)))
     s = set()
     for q in query_conjuncts:
         s = s.union(q.atoms(C.Symbol))
     return bool(dpll(query_conjuncts, list(s), {}))

def _laplace_transform(f, t, s, simplify=True):
    """ The backend function for laplace transforms. """
    from sympy import (re, Max, exp, pi, Abs, Min, periodic_argument as arg,
                       cos, Wild, symbols)
    F = integrate(exp(-s*t) * f, (t, 0, oo))

    if not F.has(Integral):
        return _simplify(F, simplify), -oo, True

    if not F.is_Piecewise:
        raise IntegralTransformError('Laplace', f, 'could not compute integral')

    F, cond = F.args[0]
    if F.has(Integral):
        raise IntegralTransformError('Laplace', f, 'integral in unexpected form')

    a = -oo
    aux = True
    conds = conjuncts(to_cnf(cond))
    u = Dummy('u', real=True)
    p, q, w1, w2, w3 = symbols('p q w1 w2 w3', cls=Wild, exclude=[s])
    for c in conds:
        a_ = oo
        aux_ = []
        for d in disjuncts(c):
            m = d.match(abs(arg((s + w3)**p*q, w1)) < w2)
            if m:
                if m[q] > 0 and m[w2]/m[p] == pi/2:
                    d = re(s + m[w3]) > 0
            m = d.match(0 < cos(abs(arg(s, q)))*abs(s) - p)
            if m:
                d = re(s) > m[p]
            d_ = d.replace(re, lambda x: x.expand().as_real_imag()[0]).subs(re(s), t)
            if not d.is_Relational or (d.rel_op != '<' and d.rel_op != '<=') \
               or d_.has(s) or not d_.has(t):
                aux_ += [d]
                continue
            soln = _solve_inequality(d_, t)
            if not soln.is_Relational or \
               (soln.rel_op != '<' and soln.rel_op != '<='):
                aux_ += [d]
                continue
            if soln.lhs == t:
                raise IntegralTransformError('Laplace', f,
                                     'convergence not in half-plane?')
            else:
                a_ = Min(soln.lhs, a_)
        if a_ != oo:
            a = Max(a_, a)
        else:
            aux = And(aux, Or(*aux_))

    return _simplify(F, simplify), a, aux

def _mellin_transform(f, x, s_, integrator=_default_integrator, simplify=True):
    """ Backend function to compute mellin transforms. """
    from sympy import re, Max, Min
    # We use a fresh dummy, because assumptions on s might drop conditions on
    # convergence of the integral.
    s = _dummy('s', 'mellin-transform', f)
    F = integrator(x**(s-1) * f, x)

    if not F.has(Integral):
        return _simplify(F.subs(s, s_), simplify), (-oo, oo), True

    if not F.is_Piecewise:
        raise IntegralTransformError('Mellin', f, 'could not compute integral')

    F, cond = F.args[0]
    if F.has(Integral):
        raise IntegralTransformError('Mellin', f, 'integral in unexpected form')

    a = -oo
    b = oo
    aux = True
    conds = conjuncts(to_cnf(cond))
    t = Dummy('t', real=True)
    for c in conds:
        a_ = oo
        b_ = -oo
        aux_ = []
        for d in disjuncts(c):
            d_ = d.replace(re, lambda x: x.as_real_imag()[0]).subs(re(s), t)
            if not d.is_Relational or (d.rel_op != '<' and d.rel_op != '<=') \
               or d_.has(s) or not d_.has(t):
                aux_ += [d]
                continue
            soln = _solve_inequality(d_, t)
            if not soln.is_Relational or \
               (soln.rel_op != '<' and soln.rel_op != '<='):
                aux_ += [d]
                continue
            if soln.lhs == t:
                b_ = Max(soln.rhs, b_)
            else:
                a_ = Min(soln.lhs, a_)
        if a_ != oo and a_ != b:
            a = Max(a_, a)
        elif b_ != -oo and b_ != a:
            b = Min(b_, b)
        else:
            aux = And(aux, Or(*aux_))

    if aux is False:
        raise IntegralTransformError('Mellin', f, 'no convergence found')

    return _simplify(F.subs(s, s_), simplify), (a, b), aux

def satisfiable(expr, algorithm="dpll2", all_models=False):
    """
    Check satisfiability of a propositional sentence.
    Returns a model when it succeeds.
    Returns {true: true} for trivially true expressions.

    On setting all_models to True, if given expr is satisfiable then
    returns a generator of models. However, if expr is unsatisfiable
    then returns a generator containing the single element False.

    Examples
    ========

    >>> from sympy.abc import A, B
    >>> from sympy.logic.inference import satisfiable
    >>> satisfiable(A & ~B)
    {A: True, B: False}
    >>> satisfiable(A & ~A)
    False
    >>> satisfiable(True)
    {True: True}
    >>> next(satisfiable(A & ~A, all_models=True))
    False
    >>> models = satisfiable((A >> B) & B, all_models=True)
    >>> next(models)
    {A: False, B: True}
    >>> next(models)
    {A: True, B: True}
    >>> def use_models(models):
    ...     for model in models:
    ...         if model:
    ...             # Do something with the model.
    ...             print(model)
    ...         else:
    ...             # Given expr is unsatisfiable.
    ...             print("UNSAT")
    >>> use_models(satisfiable(A >> ~A, all_models=True))
    {A: False}
    >>> use_models(satisfiable(A ^ A, all_models=True))
    UNSAT

    """
    expr = to_cnf(expr)
    if algorithm == "dpll":
        from sympy.logic.algorithms.dpll import dpll_satisfiable

        return dpll_satisfiable(expr)
    elif algorithm == "dpll2":
        from sympy.logic.algorithms.dpll2 import dpll_satisfiable

        return dpll_satisfiable(expr, all_models)
    raise NotImplementedError

def dpll_satisfiable(expr):
    """Check satisfiability of a propositional sentence.
    It returns a model rather than True when it succeeds
    >>> from sympy import symbols
    >>> A, B = symbols('AB')
    >>> dpll_satisfiable(A & ~B)
    {A: True, B: False}
    >>> dpll_satisfiable(A & ~A)
    False
    """
    clauses = conjuncts(to_cnf(expr))
    symbols = list(expr.atoms(Symbol))
    return dpll(clauses, symbols, {})

def test_to_cnf():
    A, B, C = symbols('ABC')
    assert to_cnf(~(B | C)) == And(Not(B), Not(C))
    assert to_cnf((A & B) | C) == And(Or(A, C), Or(B, C))
    assert to_cnf(A >> B) == (~A) | B
    assert to_cnf(A >> (B & C)) == (~A | B) & (~A | C)

    assert to_cnf(Equivalent(A, B)) == And(Or(A, Not(B)), Or(B, Not(A)))
    assert to_cnf(Equivalent(A, B & C)) == (~A | B) & (~A | C) & (~B | ~C | A)
    assert to_cnf(Equivalent(A, B | C)) == \
    And(Or(Not(B), A), Or(Not(C), A), Or(B, C, Not(A)))

def dpll_satisfiable(expr):
    """Check satisfiability of a propositional sentence.
    It returns a model rather than True when it succeeds
    >>> from sympy import symbols
    >>> A, B = symbols('AB')
    >>> dpll_satisfiable(A & ~B)
    {A: True, B: False}
    >>> dpll_satisfiable(A & ~A)
    False

    References: Implemented as described in http://aima.cs.berkeley.edu/
    """
    clauses = conjuncts(to_cnf(expr))
    symbols = list(expr.atoms(Symbol))
    return dpll(clauses, symbols, {})

def compute_known_facts(known_facts, known_facts_keys):
    """Compute the various forms of knowledge compilation used by the
    assumptions system.

    This function is typically applied to the variables
    ``known_facts`` and ``known_facts_keys`` defined at the bottom of
    this file.
    """
    from textwrap import dedent, wrap

    fact_string = dedent(
        '''\
    """
    The contents of this file are the return value of
    ``sympy.assumptions.ask.compute_known_facts``.  Do NOT manually
    edit this file.
    """

    from sympy.logic.boolalg import And, Not, Or
    from sympy.assumptions.ask import Q

    # -{ Known facts in CNF }-
    known_facts_cnf = And(
        %s
    )

    # -{ Known facts in compressed sets }-
    known_facts_dict = {
        %s
    }
    '''
    )
    # Compute the known facts in CNF form for logical inference
    LINE = ",\n    "
    HANG = " " * 8
    cnf = to_cnf(known_facts)
    c = LINE.join([str(a) for a in cnf.args])
    mapping = single_fact_lookup(known_facts_keys, cnf)
    m = (
        LINE.join(
            [
                "\n".join(wrap("%s: %s" % item, subsequent_indent=HANG, break_long_words=False))
                for item in mapping.items()
            ]
        )
        + ","
    )
    return fact_string % (c, m)

 def process_conds(conds):
     """ Turn ``conds`` into a strip and auxiliary conditions. """
     a = -oo
     aux = True
     conds = conjuncts(to_cnf(conds))
     u = Dummy('u', real=True)
     p, q, w1, w2, w3, w4, w5 = symbols('p q w1 w2 w3 w4 w5', cls=Wild, exclude=[s])
     for c in conds:
         a_ = oo
         aux_ = []
         for d in disjuncts(c):
             m = d.match(abs(arg((s + w3)**p*q, w1)) < w2)
             if not m:
                 m = d.match(abs(arg((s + w3)**p*q, w1)) <= w2)
             if not m:
                 m = d.match(abs(arg((polar_lift(s + w3))**p*q, w1)) < w2)
             if not m:
                 m = d.match(abs(arg((polar_lift(s + w3))**p*q, w1)) <= w2)
             if m:
                 if m[q] > 0 and m[w2]/m[p] == pi/2:
                     d = re(s + m[w3]) > 0
             m = d.match(0 < cos(abs(arg(s**w1*w5, q))*w2)*abs(s**w3)**w4 - p)
             if not m:
                 m = d.match(0 < cos(abs(arg(polar_lift(s)**w1*w5, q))*w2)*abs(s**w3)**w4 - p)
             if m and all(m[wild] > 0 for wild in [w1, w2, w3, w4, w5]):
                 d = re(s) > m[p]
             d_ = d.replace(re, lambda x: x.expand().as_real_imag()[0]).subs(re(s), t)
             if not d.is_Relational or \
                d.rel_op not in ('>', '>=', '<', '<=') \
                or d_.has(s) or not d_.has(t):
                 aux_ += [d]
                 continue
             soln = _solve_inequality(d_, t)
             if not soln.is_Relational or \
                soln.rel_op not in ('>', '>=', '<', '<='):
                 aux_ += [d]
                 continue
             if soln.lts == t:
                 raise IntegralTransformError('Laplace', f,
                                      'convergence not in half-plane?')
             else:
                 a_ = Min(soln.lts, a_)
         if a_ != oo:
             a = Max(a_, a)
         else:
             aux = And(aux, Or(*aux_))
     return a, aux