Properties of Boolean functions/hard

From testwiki
Revision as of 00:53, 15 March 2025 by imported>Watchduck (complement)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

<templatestyles src="Collapsible with classes/style.css" /> Template:Boolf header Template:Properties of Boolean functions/header

Hard properties can be assigned to a BF, without referencing its Template:Boolf-prop.

weight

Weight is the quotient of true and all places of the truth table. It is usually shown as an integer for a given arity (Template:Boolf-prop).
This triangle shows the numbers of BF by weight.

nonlinearity

Nonlinearity is the extent to which a BF is not linear. It is usually shown as an integer for a given arity (Template:Boolf-prop).

Atoms or atomvals are the relevant arguments of the BF. They correspond to the circles of an Euler diagram. The number of atoms is the Template:Boolf-prop.
I this project the letters A, B, C... correspond to atoms 0, 1, 2...   E.g. BC has atoms 1 and 2.

root

The root of a BF created by replacing its atoms with the set {0, ..., Template:Boolf-prop−1}.
When it is its own root, the BF is Template:Boolf-prop.

equivalence classes

Template:Anchor based on input negation and permutation: family (negation), faction (permutation), clan (both)   (Typically represented by Smallest Zhegalkin index.)

Template:Anchor extended by complement: super-family, super-faction, super-clan   (Families and clans can be self-complementary. Factions can not.)

(Further extension by half-complement leads to Template:Boolf-prop and Template:Boolf-prop, which are soft properties.)

prefect

The prefect is a way to assign each BF to a linear BF. A linear is assigned to itself.    (3-ary images)

These properties assign every almost every BF to a finite set of integers. The result for the contradiction is infinite. Soft equivalents have been defined to avoid this problem.
The cardinalities of the results are Template:Boolf-prop and Template:Boolf-prop.

complement

all places of the truth table negated, e.g. 0001 and 1110 Template:Spaces (LSB of the Zhegalkin index negated)
The complement of a set of BF is the set of complements. (Template:Boolf-prop and Template:Boolf-props can be self-complementary. Template:Boolf-prop can not.)

reverse

truth table reversed, e.g. 0001 and 1000

dual

complement of the reverse, e.g. 0001 and 0111