Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


fom
Posts:
1,968
Registered:
12/4/12


Permutation Independent Boolean Comparison
Posted:
Dec 4, 2013 1:27 PM


The following paper has a somewhat interesting subject. Namely, it has to do with comparing Boolean functions on the basis of their signatures.
www.researchgate.net/publication/2772583_Limits_of_using_Signatures_for_Permutation_Independent_Boolean_Comparison/file/9fcfd50c06bfd9fc25.pdf?origin=publication_detail
Problems arise because of symmetries in the function signatures.
Recently, I posted a link discussing the Horton graph on 96 points. The automorphism group for that graph had order 96. So, that graph has the smallest number of points capable of being put into onetoone correspondence with its automorphism group.
I arrived at that graph by consideration of the structure of a single binary truth table. The automorphism group,
Z/2 x Z/2 x S_4
reflects 3 factors. First, given two symbols to represent truth and falsity for the purpose of a deductive calculus, one has 2 possible assignments. Second, one has two propositional variables. Third, there are 4 possible orderings for the rows.
I doubt very much if anyone has thought of considering the graph theory of information complexity for truth tables. The assumption that propositional variables are independent is not dissimilar to what I have read concerning algorithmically random reals. So, this class of graphs would be characterized by having the same number of vertices as the order of their automorphism groups.
One might imagine that the sequence of interesting groups would be something like,
Z/2 x S_3 x S_8
Z/2 x S_4 x S_16
Z/2 x S_5 x S_32
etc.
One question which would naturally arise is whether graphs matching those orders and having those automorphism groups exist for every truth table. It seems unlikely.
Notice that the basic Boolean functions would be the only representations whose component subgroups all correspond with orders less than the polynomial degrees of Galois theory.
And, I seem to recall Mr. Greene whining one time about why things seemed so hard.
chuckle



