Repository: sympy/sympy

Issue:
Exclusive or (XOR) of a bool symbol and its negation should return True
When using `simplify` we obtain the following basic simplications:
```
>>> from sympy import *
>>> a = symbols('a') 
>>> simplify(a&~a) 
False
>>> simplify(a|~a) 
True
>>> simplify(a^~a) 
a ^ ~a
```
But it is straightforward that `simplify(a^~a) == True` regardless of `a` being `True` or `False`.

Digging a bit into `sympy\logic\boolalg.py` it seems that the function `Xor` does not recognize the immediate simplification either, despite evaluating `a^a` correctly:
```
>>> from sympy import *
>>> a = symbols('a') 
>>> Xor(a, ~a)       
a ^ ~a
>>> Xor(a,a)           
False
```

Discussion:

Patch:
diff --git a/.mailmap b/.mailmap
index a3d4cdf7c6..ab3bc2dd05 100644
--- a/.mailmap
+++ b/.mailmap
@@ -633,7 +633,6 @@ George Pittock <gpittock4@gmail.com>
 George Waksman <waksman@gwax.com>
 Georges Khaznadar <georgesk@debian.org>
 Georgios Giapitzakis Tzintanos <giorgosgiapis@mail.com>
-Gerald Teschl <gerald.teschl@univie.ac.at>
 Gert-Ludwig Ingold <gert.ingold@physik.uni-augsburg.de>
 Gilbert Gede <gilbertgede@gmail.com> <ggede@Gilbert-Gedes-MacBook.local>
 Gilbert Gede <gilbertgede@gmail.com> <ggede@ucdavis.edu>
diff --git a/sympy/combinatorics/fp_groups.py b/sympy/combinatorics/fp_groups.py
index d74ab39230..00310827f7 100644
--- a/sympy/combinatorics/fp_groups.py
+++ b/sympy/combinatorics/fp_groups.py
@@ -508,7 +508,7 @@ def elements(self):
 
         '''
         P, T = self._to_perm_group()
-        return T.invert(P.elements)
+        return T.invert(P._elements)
 
     @property
     def is_cyclic(self):
diff --git a/sympy/combinatorics/perm_groups.py b/sympy/combinatorics/perm_groups.py
index 0dea5e8aaa..396158a568 100644
--- a/sympy/combinatorics/perm_groups.py
+++ b/sympy/combinatorics/perm_groups.py
@@ -1,5 +1,5 @@
 from math import factorial as _factorial, log, prod
-from itertools import chain, product
+from itertools import chain, islice, product
 
 
 from sympy.combinatorics import Permutation
@@ -149,8 +149,7 @@ def __new__(cls, *args, dups=True, **kwargs):
     def __init__(self, *args, **kwargs):
         self._generators = list(self.args)
         self._order = None
-        self._elements = []
-        self._center = None
+        self._center = []
         self._is_abelian = None
         self._is_transitive = None
         self._is_sym = None
@@ -805,7 +804,7 @@ def coset_transversal(self, H):
             raise ValueError("The argument must be a subgroup")
 
         if H.order() == 1:
-            return self.elements
+            return self._elements
 
         self._schreier_sims(base=H.base) # make G.base an extension of H.base
 
@@ -832,7 +831,7 @@ def coset_transversal(self, H):
         # contains all the elements of G^(l) so we might just as well
         # start with l = len(h_stabs)-1
         if len(g_stabs) > len(h_stabs):
-            T = g_stabs[len(h_stabs)].elements
+            T = g_stabs[len(h_stabs)]._elements
         else:
             T = [identity]
         l = len(h_stabs)-1
@@ -963,9 +962,7 @@ def center(self):
         of ``.centralizer()``
 
         """
-        if not self._center:
-            self._center = self.centralizer(self)
-        return self._center
+        return self.centralizer(self)
 
     def centralizer(self, other):
         r"""
@@ -1379,7 +1376,7 @@ def identity(self):
 
     @property
     def elements(self):
-        """Returns all the elements of the permutation group as a list
+        """Returns all the elements of the permutation group as a set
 
         Examples
         ========
@@ -1387,13 +1384,25 @@ def elements(self):
         >>> from sympy.combinatorics import Permutation, PermutationGroup
         >>> p = PermutationGroup(Permutation(1, 3), Permutation(1, 2))
         >>> p.elements
-        [(3), (3)(1 2), (1 3), (2 3), (1 2 3), (1 3 2)]
+        {(1 2 3), (1 3 2), (1 3), (2 3), (3), (3)(1 2)}
 
         """
-        if not self._elements:
-            self._elements = list(self.generate())
+        return set(self._elements)
 
-        return self._elements
+    @property
+    def _elements(self):
+        """Returns all the elements of the permutation group as a list
+
+        Examples
+        ========
+
+        >>> from sympy.combinatorics import Permutation, PermutationGroup
+        >>> p = PermutationGroup(Permutation(1, 3), Permutation(1, 2))
+        >>> p._elements
+        [(3), (3)(1 2), (1 3), (2 3), (1 2 3), (1 3 2)]
+
+        """
+        return list(islice(self.generate(), None))
 
     def derived_series(self):
         r"""Return the derived series for the group.
diff --git a/sympy/logic/boolalg.py b/sympy/logic/boolalg.py
index 4727a3e704..d91301eb24 100644
--- a/sympy/logic/boolalg.py
+++ b/sympy/logic/boolalg.py
@@ -1046,6 +1046,7 @@ def _eval_simplify(self, **kwargs):
         # And and Or, we only simplify the partial expressions before using
         # patterns
         rv = self.func(*[a.simplify(**kwargs) for a in self.args])
+        rv = rv.to_anf()
         if not isinstance(rv, Xor):  # This shouldn't really happen here
             return rv
         patterns = _simplify_patterns_xor()
diff --git a/sympy/ntheory/residue_ntheory.py b/sympy/ntheory/residue_ntheory.py
index 1257314c10..aa43ae8cdc 100644
--- a/sympy/ntheory/residue_ntheory.py
+++ b/sympy/ntheory/residue_ntheory.py
@@ -1432,7 +1432,7 @@ def _discrete_log_pollard_rho(n, a, b, order=None, retries=10, rseed=None):
     raise ValueError("Pollard's Rho failed to find logarithm")
 
 
-def _discrete_log_pohlig_hellman(n, a, b, order=None, order_factors=None):
+def _discrete_log_pohlig_hellman(n, a, b, order=None):
     """
     Pohlig-Hellman algorithm for computing the discrete logarithm of ``a`` to
     the base ``b`` modulo ``n``.
@@ -1465,18 +1465,18 @@ def _discrete_log_pohlig_hellman(n, a, b, order=None, order_factors=None):
 
     if order is None:
         order = n_order(b, n)
-    if order_factors is None:
-        order_factors = factorint(order)
-    l = [0] * len(order_factors)
 
-    for i, (pi, ri) in enumerate(order_factors.items()):
+    f = factorint(order)
+    l = [0] * len(f)
+
+    for i, (pi, ri) in enumerate(f.items()):
         for j in range(ri):
             aj = pow(a * pow(b, -l[i], n), order // pi**(j + 1), n)
             bj = pow(b, order // pi, n)
             cj = discrete_log(n, aj, bj, pi, True)
             l[i] += cj * pi**j
 
-    d, _ = crt([pi**ri for pi, ri in order_factors.items()], l)
+    d, _ = crt([pi**ri for pi, ri in f.items()], l)
     return d
 
 
@@ -1513,36 +1513,7 @@ def discrete_log(n, a, b, order=None, prime_order=None):
     """
     n, a, b = as_int(n), as_int(a), as_int(b)
     if order is None:
-        # Compute the order and its factoring in one pass
-        # order = totient(n), factors = factorint(order)
-        factors = {}
-        for px, kx in factorint(n).items():
-            if kx > 1:
-                if px in factors:
-                    factors[px] += kx - 1
-                else:
-                    factors[px] = kx - 1
-            for py, ky in factorint(px - 1).items():
-                if py in factors:
-                    factors[py] += ky
-                else:
-                    factors[py] = ky
-        order = 1
-        for px, kx in factors.items():
-            order *= px**kx
-        # Now the `order` is the order of the group and factors = factorint(order)
-        # The order of `b` divides the order of the group.
-        order_factors = {}
-        for p, e in factors.items():
-            i = 0
-            for _ in range(e):
-                if pow(b, order // p, n) == 1:
-                   order //= p
-                   i += 1
-                else:
-                    break
-            if i < e:
-                order_factors[p] = e - i
+        order = n_order(b, n)
 
     if prime_order is None:
         prime_order = isprime(order)
@@ -1552,7 +1523,7 @@ def discrete_log(n, a, b, order=None, prime_order=None):
     elif prime_order:
         if order < 1000000000000:
             return _discrete_log_shanks_steps(n, a, b, order)
-        return _discrete_log_pollard_rho(n, a, b, order, order_factors)
+        return _discrete_log_pollard_rho(n, a, b, order)
 
     return _discrete_log_pohlig_hellman(n, a, b, order)
 


Test patch:
diff --git a/sympy/combinatorics/tests/test_perm_groups.py b/sympy/combinatorics/tests/test_perm_groups.py
index 1e01e89e92..41be445fa8 100644
--- a/sympy/combinatorics/tests/test_perm_groups.py
+++ b/sympy/combinatorics/tests/test_perm_groups.py
@@ -806,7 +806,7 @@ def test_elements():
     from sympy.sets.sets import FiniteSet
 
     p = Permutation(2, 3)
-    assert set(PermutationGroup(p).elements) == {Permutation(3), Permutation(2, 3)}
+    assert PermutationGroup(p).elements == {Permutation(3), Permutation(2, 3)}
     assert FiniteSet(*PermutationGroup(p).elements) \
         == FiniteSet(Permutation(2, 3), Permutation(3))
 
diff --git a/sympy/logic/tests/test_boolalg.py b/sympy/logic/tests/test_boolalg.py
index ed37f7afe2..53de73f190 100644
--- a/sympy/logic/tests/test_boolalg.py
+++ b/sympy/logic/tests/test_boolalg.py
@@ -355,6 +355,7 @@ def test_simplification_boolalg():
     assert And(Eq(x - 1, 0), Eq(x + 2, 2)).simplify() == False
     assert And(Ne(x - 1, 0), Ne(x + 2, 2)).simplify(
         ) == And(Ne(x, 1), Ne(x, 0))
+    assert simplify(Xor(x, ~x)) == True
 
 
 def test_bool_map():