The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Topic: Permutation Independent Boolean Comparison
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  

Posts: 1,968
Registered: 12/4/12
Permutation Independent Boolean Comparison
Posted: Dec 4, 2013 1:27 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

The following paper has a somewhat interesting
subject. Namely, it has to do with comparing
Boolean functions on the basis of their

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

Z/2 x S_3 x S_8

Z/2 x S_4 x S_16

Z/2 x S_5 x S_32


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


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.