Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Permutation Independent Boolean Comparison
Replies: 0

 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 one-to-one 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