output=list or one of expressions or group

a list of one or more of the symbols expressions or group, or one of the symbols expressions or group.

The symbol group corresponds to the symmetry group for expr. The group is a permutation group; its elements are those permutations which preserve the Boolean structure of expr. If there are no nontrivial symmetries the group will be the trivial group.

The symbol expressions is the list of subexpressions of expr on which the permutations act.

The SymmetryGroup command computes the group of symmetries of a given Boolean expression expr.

The result is a Group object and can be examined using the tools in the GroupTheory package.

The expression expr must be in conjunctive normal form (CNF). If not already in CNF, expr can be converted to CNF using Normalize; alternatively, Tseitin may be used to find an equisatifiable expression in CNF.

A symmetry of a Boolean expression expr is a mapping f of each variable to some other variable or negated variable, such that the image of expr after applying f to each of its variables is a Boolean formula which is equivalent to expr.

$\mathrm{with}\left(\mathrm{Logic}\right)\:$

$\mathrm{expr}≔\left(a\mathbf{or}b\mathbf{or}\mathbf{not}c\right)\mathbf{and}\left(c\mathbf{or}d\mathbf{or}\mathbf{not}e\right)$

$\mathrm{expr}≔\left(a\mathbf{or}b\mathbf{or}\mathbf{not}c\right)\mathbf{and}\left(c\mathbf{or}d\mathbf{or}\mathbf{not}e\right)$

$G≔\mathrm{SymmetryGroup}\left(\mathrm{expr}\right)$

$G≔⟨\left(1\,10\right)\left(2\,4\right)\left(3\,8\right)\left(5\,6\right)\left(7\,9\right)\left(11\,12\right)\,\left(1\,2\right)\left(6\,7\right)\,\left(4\,10\right)\left(5\,9\right)⟩$

$\mathrm{GroupTheory}:-\mathrm{IsAbelian}\left(G\right)$

$\mathrm{false}$

$\mathrm{GroupTheory}:-\mathrm{IdentifySmallGroup}\left(G\right)$

$8,3$

$G,L≔\mathrm{SymmetryGroup}\left(\mathrm{expr}\,\mathrm{output}=\left[\mathrm{group}\,\mathrm{expressions}\right]\right)$

$G,L≔⟨\left(1\,10\right)\left(2\,4\right)\left(3\,8\right)\left(5\,6\right)\left(7\,9\right)\left(11\,12\right)\,\left(1\,2\right)\left(6\,7\right)\,\left(4\,10\right)\left(5\,9\right)⟩,\left[a\,b\,c\,d\,e\,\neg a\,\neg b\,\neg c\,\neg d\,\neg e\,a\vee b\vee \left(\neg c\right)\,c\vee d\vee \left(\neg e\right)\right]$

$\mathrm{gen}≔\mathrm{Perm}\left(\left[\left[1\,10\right]\,\left[2\,4\right]\,\left[3\,8\right]\,\left[5\,6\right]\,\left[7\,9\right]\,\left[11\,12\right]\right]\right)$

$\mathrm{gen}≔\left(1\,10\right)\left(2\,4\right)\left(3\,8\right)\left(5\,6\right)\left(7\,9\right)\left(11\,12\right)$

$\mathrm{GroupTheory}:-\mathrm{ElementOrder}\left(\mathrm{gen}\,G\right)$

$2$

$\mathrm{zip}\left(\mathrm{`=`}\,L\,L\left[\mathrm{convert}\left(\mathrm{gen}\,\mathrm{permlist}\,\mathrm{nops}\left(L\right)\right)\right]\right)$

$\left[a=\neg e\,b=d\,c=\neg c\,d=b\,e=\neg a\,\neg a=e\,\neg b=\neg d\,\neg c=c\,\neg d=\neg b\,\neg e=a\,a\vee b\vee \left(\neg c\right)=c\vee d\vee \left(\neg e\right)\,c\vee d\vee \left(\neg e\right)=a\vee b\vee \left(\neg c\right)\right]$

$\mathrm{expr}≔\left(x\mathbf{or}y\mathbf{or}z\right)\mathbf{and}\left(\mathbf{not}x\mathbf{or}\mathbf{not}y\mathbf{or}\mathbf{not}z\right)\mathbf{and}\left(\mathbf{not}x\mathbf{or}\mathbf{not}y\mathbf{or}\mathbf{not}z\right)$

$\mathrm{expr}≔\left(x\mathbf{or}y\mathbf{or}z\right)\mathbf{and}\mathbf{not}\left(x\mathbf{and}y\mathbf{and}z\right)\mathbf{and}\mathbf{not}\left(x\mathbf{and}y\mathbf{and}z\right)$

$G,L≔\mathrm{SymmetryGroup}\left(\mathrm{expr}\,\mathrm{output}=\left[\mathrm{group}\,\mathrm{expressions}\right]\right)$

$G,L≔⟨\left(2\,3\right)\left(5\,6\right)\,\left(8\,9\right)\,\left(1\,2\right)\left(4\,5\right)⟩,\left[x\,y\,z\,\neg x\,\neg y\,\neg z\,x\vee y\vee z\,\left(\neg x\right)\vee \left(\neg y\right)\vee \left(\neg z\right)\,\left(\neg x\right)\vee \left(\neg y\right)\vee \left(\neg z\right)\right]$

$\mathrm{GroupTheory}:-\mathrm{GroupOrder}\left(G\right)$

$12$

$\mathrm{expr}≔\left(a\mathbf{and}\mathbf{not}b\mathbf{or}\mathbf{not}c\mathbf{or}d\right)\mathbf{and}\left(d\mathbf{or}a\right)\mathbf{and}\mathbf{not}\left(a\mathbf{and}c\right)$

$\mathrm{expr}≔\left(a\mathbf{and}\mathbf{not}b\mathbf{or}\mathbf{not}c\mathbf{or}d\right)\mathbf{and}\left(d\mathbf{or}a\right)\mathbf{and}\mathbf{not}\left(a\mathbf{and}c\right)$

$\mathrm{SymmetryGroup}\left(\mathrm{expr}\right)$

Error, (in Logic:-SymmetryGroup) not in conjunctive normal form

$\mathrm{expr\_cnf}≔\mathrm{Normalize}\left(\mathrm{expr}\,\mathrm{form}=\mathrm{CNF}\right)$

$\mathrm{expr\_cnf}≔\left(a\vee d\right)\wedge \left(\left(\neg a\right)\vee \left(\neg c\right)\right)\wedge \left(a\vee d\vee \left(\neg c\right)\right)\wedge \left(d\vee \left(\neg b\right)\vee \left(\neg c\right)\right)$

$G≔\mathrm{SymmetryGroup}\left(\mathrm{expr\_cnf}\right)$

$G≔⟨⟩$

$\mathrm{GroupTheory}:-\mathrm{GroupOrder}\left(G\right)$

$1$

Fadi A. Aloul, Arathi Ramani, Igor L. Markov, Karem A. Sakallah. "Solving difficult instances of Boolean satisfiability in the presence of symmetry." IEEE Trans. CAD Integr. Circ. Syst. 22(9), 1117–1137 (2003). doi:10.1109/TCAD.2003.816218

The Logic[SymmetryGroup] command was introduced in Maple 2020.

For more information on Maple 2020 changes, see Updates in Maple 2020.