Properties of Boolean functions

Studies of Boolean functions
not dependent on arity: Properties of Boolean functions
dependent on arity: Properties of truth tables

simple

edit
  • valency: number of relevant arguments (i.e. the number of circles needed to draw an Euler diagram, especially for a blightless BF)
  • adicity: Atoms are numbered from 0. The adicity of a BF is its biggest atom plus 1. The period length of its truth table  .
  • weight: quotient of true places and all places of the truth table   (0 for the contradiction, 1 for the tautology)

subsets

edit

Belonging to a subset can also be seen as a property.

  • linear: Walsh functions and their complements
  • seal: conjunctions of linears
  • dense: no gaps before or between the atoms, i.e. valency = adicity
  • balanced: same number of true and false places, i.e. weight = 0.5
  • monotonic: no true place under false place (when places are arranged in a Hasse diagram)   (counted by Dedekind numbers)

equivalence classes based on similarity

edit

see also:

basic (negation and permutation)

edit

family (negation)

edit

Functions can be turned into each other by negating inputs.

The 10 (exactly) 2-ary Boolean functions form three families, whose representative functions are AND, OR and XOR.   (See this table of 2-ary functions, where equivalents are in the same row.)

The lexicographically smallest truth tables are encoded in  A227722 = 0, 1, 3, 5, 6, 7, 15, 17, 18...

faction (permutation)

edit

Functions can be turned into each other by permuting inputs.
While families and clans can be self-complementary, factions can not. (Therefore the number of factions is always even.)

clan (negation, permutation)

edit

Functions can be turned into each other by negating and permuting inputs.

The lexicographically smallest truth tables are encoded in  A227723 = 0, 1, 3, 6, 7, 15...

super (extension with complement)

edit


partitions into blocks of equal size

edit

parity, depravity, quadrant

edit
quadrants
even evil (0) even odious (2)
odd evil (1) odd odious (3)

The parity and depravity of a Boolean function are based on the first and last place of its truth table.
It is odd (even), iff the first place is true (false). Its Zhegalkin index is also odd (even).
It is odious (evil), iff the last place is true (false). Its Zhegalkin index has odd (even) binary weight.
It is ugly, iff parity and depravity are different (i.e. iff the quadrant is 1 or 2).
The quadrant is an integer 0...3, and calculated as  .

prefect

edit

The prefect is a way to assign each BF to a linear BF. A linear is assigned to itself. The resulting equivalence class may be called prefecture.    (3-ary images)

other

edit

gender

edit

Gender is based on parity. For any positive arity there are slightly more males than females. See Gender of Boolean functions.