The truth table of p → (q → p)

• 222 classes, sizes dividing 768, adding to all 65,536 tables ×1
• a restriction shrinks the formula by at least the share of letters it frees ×1
• all 256 counted ×1
• and 114 functions of four letters need sixteen ×1
• and at three letters the construction is the true minimum, 10 ×1
• and neither does its best value over subsets ×1
• and no formula for it has fewer ×1
• and only parity and its negation need ten ×1
• as it is at four, 16 ×1
• at powers of two the construction meets it ×1
• Burnside's count matches the known number of classes ×1
• direct enumeration and Burnside's lemma agree ×1
• every corner meets one edge per variable, each edge counted once ×1
• every function of three letters has a circuit of at most four gates ×1
• every leaf of the formula is a variable ×1
• every one of parity's twelve edges joins a true corner to a false one ×1
• every opening bracket in the formula is closed ×1
• every set of more than half the corners has a corner of degree at least √n ×1
• exactly 56 three-letter functions express everything alone, the same 56 Post's criterion picks out ×1
• exactly one true needs exactly 4 gates ×1
• fixing the best letter always leaves at most (3/4)^(3/2) of the formula ×1
• for parity the bound is 16 ×1
• if a then b else c needs exactly 3 gates ×1
• Khrapchenko's quantity never exceeds the true formula size ×1
• leaves of the parity formula ×1
• leaves surviving the restriction x3 = 0, x4 = 1 ×1
• majority of p, q, r is a weighted vote ×1
• majority of three needs exactly 4 gates ×1
• majority's middle levels give ((n + 1)/2)² for odd n ×1
• no choice of corners can pass n², since each corner has at most n edges ×1
• no construction beats the count ×1
• no function has degree above its sensitivity squared ×1
• no function shrinks more slowly than the share of letters freed ×1
• odd number true needs exactly 2 gates ×1
• on majority the rule stops making mistakes ×1
• on parity it never does ×1
• one to four named functions ×1
• only nand and nor express everything alone ×1
• p, or both q and r is a weighted vote ×1
• parity is sensitive to every letter everywhere ×1
• parity needs the most letters of any function ×1
• parity of four letters needs exactly sixteen ×1
• parity of three letters needs exactly ten ×1
• parity reaches n² exactly ×1
• parity: an odd number of p, q, r is not a weighted vote ×1
• Post's criterion agrees with the closure ×1
• Post's criterion agrees with the closure on every pair ×1
• relabelling, negating letters or negating the answer keeps the count at four ×1
• the bound never exceeds the true size ×1
• the circuit drawn for exactly one true computes it ×1
• the circuit drawn for if a then b else c computes it ×1
• the circuit drawn for majority of three computes it ×1
• the circuit drawn for odd number true computes it ×1
• the constants and the parity of four letters each form a class of two ×1
• the construction never beats Khrapchenko's bound ×1
• the count lands within a small factor of 2ⁿ/n ×1
• the counts are 4, 14, 104 and 1,882 ×1
• the cube is drawn for two, three or four variables ×1
• the fixed tables add up to fourteen times the group's 96 elements ×1
• the formula and its disjunctive normal form agree on every row ×1
• the formula has between one and five variables ×1
• the formula is a non-empty string ×1
• the function is one this figure knows ×1
• the highlighted rows are the true ones, the false ones, or neither ×1
• the kinds account for every function that needs four gates ×1
• the matrix squared is n times the identity ×1
• the measure of how many tables have no symmetry climbs towards one ×1
• the nonzero entries are the cube's edges ×1
• the number of letters is a whole number between 2 and 4 ×1
• the option is one this view reads ×1
• the search is over the 3-cube or the 4-cube ×1
• the search reaches every function ×1
• the signed matrix is drawn for one to four letters ×1
• the table has one row per assignment ×1
• the table-and-selector construction is within a constant factor of the count ×1
• the top corner and its neighbours prove n for all true ×1
• the tree computes the parity of four letters ×1
• the two ends of an edge differ in exactly one variable ×1
• the two formulas hold ×1
• the value Andreev's function reads in the drawn instance ×1
• the view is one of cube, threshold, thresholdcount, perceptron, sensitivity, huang, signed, degree, circuits, costs, shannon, build, explicit, hardest, khrapcube, formulahist, khrapscatter, paritytree, paritygrowth, khrapfamilies ×1
• the weights account for all 7,581 functions ×1
• the weights and the cut give the function ×1
• the whole formula is consumed by the parser ×1
• three letters give fourteen classes up to permuting, negating letters and negating the output ×1
• twenty pairs f ≤ g among the six functions of two letters ×1
• with sixteen letters at its leaves ×1

The whole library · What the figures prove