Category:Transitive-symmetric function

Definition

A transitive-symmetric Boolean function is a Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] with the following property: For every two input bits [math]i[/math] and [math]j[/math], there exists a permutation [math]\sigma[/math] with [math]\sigma(i) = j[/math] so that [math]f(x) = f(\sigma(x))[/math].

Informally, a transitive-symmetric Boolean function where every two bits are treated equally.

Properties

• Every symmetric Boolean function is transitive-symmetric, but not vice versa (for example, the Tribes function is transitive-symmetric but not symmetric).

References