Properties of Boolean functions/hard/binary
| Studies of Boolean functions |
| Properties of Boolean functions | |
|---|---|
| hard | soft |
| binary | binary |
| integer | integer |
| permutation | permutation |
Hard properties can be assigned to a BF, without referencing its arity.
Binary properties have the values true or false, so they partition all BF into a subset and the rest.
linear
[edit | edit source]Linear Boolean functions are Walsh functions and their complements.
seal
[edit | edit source]See Seal (discrete mathematics). Seal block is a broader property.
dense
[edit | edit source]no gaps before or between the atoms, i.e. valency = adicity (often called nondegenerate)
strong
[edit | edit source]BF is strong, iff strength = adicity, so its family has the biggest possible size 2adicity.
balanced
[edit | edit source]same number of true and false places, i.e. weight = 0.5
BF that are not balanced are light or heavy, i.e. their weight is below or above 0.5.
openness (ploidy)
[edit | edit source]| family | Boolean function | clan | ||
|---|---|---|---|---|
| haploid | shut | unopen | haploid | |
| diploid | unshut | ajar | ||
| open | diploid | |||
Equivalence classes that contain complementary BF shall be called haploid.
All others (forming pairs of distinct complements) shall be called diploid.
The openness of BF is based on the ploidy of families and clans.
Haploid families are part of haploid clans. (If the family contains complementary BF, they must also be in the clan.)
Diploid clans contain diploid families. (If the clan does not contain complementary BF, the family can not contain them either.)
But a haploid clan does not necessarily contain haploid families. (The clan contains complementary BF, but they are not necessarily in the same family.)
- BF are shut, iff they are in a haploid family. Unshut means open or ajar.
- BF are open, if they are ins diploid clan. Unopen means shut or ajar.
- BF are ajar, iff they are in a diploid family and a haploid clan. Ajar BF exist for adicities ≥ 4.
monotonic
[edit | edit source]no true place under false place (when places are arranged in a Hasse diagram) (counted by Dedekind numbers)
related to parity
[edit | edit source]| even evil (0) | even odious (2) |
| odd evil (1) | odd odious (3) |
- parity: BF is odd/even iff first place in truth table is true/false. Same as parity of the Zhegalkin index.
- depravity: BF is odious/evil iff last place in truth table is true/false. Same as parity of the binary weight of the Zhegalkin index.
- BF is ugly, iff parity and depravity are different (i.e. iff the quadrant is 1 or 2).
- quadrant = parity + 2 · depravity
| images for arity 3 | |||||
|---|---|---|---|---|---|
| odd | odious | ugly | quadrants | ||
| truth tables |
.svg) 1 1000 0000 |
.svg) 128 0000 0001 |
.svg) 129 1000 0001 |
 |
 |
| Zhegalkin indices |
.svg) 255 1111 1111 |
.svg) 254 0111 1111 |
.svg) | ||
- gender: BF is male/female, iff its root is sharp/blunt. See Gender of Boolean functions.
oddacity
[edit | edit source]BF is oddacious/evenacious, iff...
- ...the XOR of all members of its family is the tautology/contradiction.
- ...its valor is odd/even.
Most BF are oddacious.
There are no evenacious males. See Gender of Boolean functions § oddacity and gender.
This property may seem a bit silly (not to mention the name). But the numbers of evenacious BF whose weights are powers of two form the triangle A289537. See tiara Opal.