Fallacy

From Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Fallacy

A fallacy, also known as paralogia in modern psychology, is the use of invalid or otherwise faulty reasoning in the construction of an argument that may appear to be well-reasoned if unnoticed. The term was introduced in the Western intellectual tradition by the Aristotelian De Sophisticis Elenchis.

Fallacies may be committed intentionally to manipulate or persuade by deception, unintentionally because of human limitations such as carelessness, cognitive or social biases and ignorance, or potentially due to the limitations of language and understanding of language. These delineations include not only the ignorance of the right reasoning standard but also the ignorance of relevant properties of the context. For instance, the soundness of legal arguments depends on the context in which they are made.

Fallacies are commonly divided into "formal" and "informal." A formal fallacy is a flaw in the structure of a deductive argument that renders the argument invalid, while an informal fallacy originates in an error in reasoning other than an improper logical form. Arguments containing informal fallacies may be formally valid, but still fallacious.

A special case is a mathematical fallacy, an intentionally invalid mathematical proof with a concealed, or subtle, error. Mathematical fallacies are typically crafted and exhibited for educational purposes, usually taking the form of false proofs of obvious contradictions.

Overview

Fallacies are types of erroneous reasoning that render arguments logically unsound. According to The New Handbook of Cognitive Therapy Techniques, they include "unsubstantiated assertions that are often delivered with a conviction that makes them sound as though they are proven facts." Informal fallacies, in particular, are frequently found in mass media such as television and newspapers. Understanding fallacies may allow one to recognize them in either one's own or others' writing. Avoiding fallacies may help improve one's ability to produce sound arguments.

It can be difficult to evaluate whether an argument is fallacious, as arguments exist along a continuum of soundness and an argument that has several stages or parts might have some sound sections and some fallacious ones. Moreover, whether a specific argument is fallacious often depends on the content rather than the form of the argument. An example is a probabilistically valid instance of the formally invalid argument form of denying the antecedent or affirming the consequent.  Thus, "fallacious arguments usually have the deceptive appearance of being good arguments,  because for most fallacious instances of an argument form, a similar but non-fallacious instance can be found." Evaluating an instance of an argument as fallacious is therefore often a matter of evaluating the context of the argument.

Recognizing fallacies in everyday arguments may be difficult since arguments are often embedded in rhetorical patterns that obscure the logical connections between statements. Informal fallacies may also exploit the emotional, intellectual, or psychological weaknesses of the audience. Recognizing fallacies can develop reasoning skills to expose the weaker links between premises and conclusions to better discern between what appears to be true and what is true.

Argumentation theory provides a different approach to understanding and classifying fallacies. In the pragma-dialectical theory, for instance, an argument is regarded as an interactive protocol between individuals who attempt to resolve their disagreement on the merits of a case. The protocol consists of normative rules of interaction, and violations of these rules are considered fallacies because they frustrate the attempt at resolving the disagreement.

Fallacies are used in place of valid reasoning to communicate a point with the intention to persuade. Examples in the mass media today include but are not limited to propaganda, advertisements, politics, newspaper editorials, and opinion-based news shows.

Systems of classification

Fallacies are generally classified strictly by either their structure or their content, such as by classifying them as formal fallacies or informal fallacies, respectively. The classification of informal fallacies may be subdivided into categories such as linguistic, relevance through omission, relevance through intrusion, and relevance through presumption. Alternatively, fallacies may be classified by the process by which they occur, such as material fallacies (content), verbal fallacies (linguistic), and formal fallacies (error in inference). In turn, material fallacies may be placed into the more general category of informal fallacies. Verbal fallacies may be placed in either formal or informal classifications: Compare equivocation, which is a word- or phrase-based ambiguity, to the fallacy of composition, which is premise- and inference-based ambiguity.

Greek logic

The Greek philosopher Aristotle (384–322 BC) was the first to systematize logical errors into a list to make it easier to refute an opponent's thesis and thus win an argument. Aristotle's "Sophistical Refutations" (De Sophisticis Elenchis) identifies thirteen fallacies. He divided them up into two major types: linguistic fallacies and non-linguistic fallacies, some of which depend on language and others that do not. These fallacies are called verbal fallacies and material fallacies, respectively. A material fallacy is an error in what the arguer is talking about, while a verbal fallacy is an error in how the arguer is talking. Verbal fallacies are those in which a conclusion is obtained by improper or ambiguous use of words. An example of a language dependent fallacy is given as a debate as to who in humanity are learners: the wise or the ignorant. A language-independent fallacy is, for example:

1. "Coriscus is different from Socrates."
2. "Socrates is a man."
3. "Therefore, Coriscus is different from a man."

Indian logic

Indian logicians took great pains to identify fallacies in arguments. An influential collection of texts on logic and reason, the Nyāya Sūtras, attributed to Aksapada Gautama, variously estimated to have been composed between the 6th century BCE and the 2nd century CE, lists in its theory of inference five such reasons used in an argument that was further developed by later logicians.

1. Asiddha: It is the unproved reason that results in this fallacy. [Paksadharmata]
2. Savyabhichara: This is the fallacy of irregular reason.
3. Satpratipaksa: Here the reason is contradicted by another reason. If both have equal force, then nothing follows. 'Sound is eternal, because it is audible', and 'Sound is non-eternal, because it is produced'. Here 'audible' is counterbalanced by 'produced' and both are of equal force.
4. Badhita: When another proof (as by perception) definitely contradicts and disproves the middle term (reason). 'Fire is cold because it is a substance'.
5. Viruddha: Instead of proving something it is proving the opposite. 'Sound is eternal because it is produced'.

Whately's grouping

English scholar and theologian Richard Whately (1787–1863) defines a fallacy broadly as, "any argument, or apparent argument, which professes to be decisive of the matter at hand, while in reality it is not".

Whately divided fallacies into two groups: logical and material. According to Whately, logical fallacies are arguments where the conclusion does not follow from the premises. Material fallacies are not logical errors because the conclusion follows from the premises. He then divided the logical group into two groups: purely logical and semi-logical. The semi-logical group included all of Aristotle's sophisms except ignoratio elenchi, petitio principii, and non causa pro causa, which are in the material group.

Other systems of classification

Other famous methods of classifying fallacies are those of Francis Bacon and J. S. Mill. Bacon (Novum Organum, Aph. 33, 38 sqq.) divided fallacies into four Idola (Idols, i.e. False Appearances), which summarize the various kinds of mistakes to which the human intellect is prone. J. S. Mill discussed the subject in book five of his Logic, and Jeremy Bentham's Book of Fallacies (1824) contains valuable remarks.

Formal fallacy

Main article: Formal fallacy

A formal fallacy, deductive fallacy, logical fallacy or non sequitur (Latin for "it does not follow") is a flaw in the structure of a deductive argument that renders the argument invalid. The flaw can be expressed in the standard system of logic. Such an argument is always considered to be wrong. The presence of the formal fallacy does not imply anything about the argument's premises or its conclusion. Both may actually be true or may even be more probable as a result of the argument, but the deductive argument is still invalid because the conclusion does not follow from the premises in the manner described.

Even non-deductive arguments can be said to be fallacious: for example, an inductive argument that incorrectly applies principles of probability or causality. But "since deductive arguments depend on formal properties and inductive arguments don't, formal fallacies apply only to deductive arguments."

A logical form such as "A and B" is independent of any particular conjunction of meaningful propositions. Logical form alone can guarantee that, given true premises, a true conclusion must follow. However, formal logic makes no such guarantee if any premise is false; the conclusion can be either true or false. Any formal error or logical fallacy similarly invalidates the deductive guarantee. Both the argument and all its premises must be true for a conclusion to be true.

The term logical fallacy is in a sense self-contradictory because logic refers to valid reasoning, whereas a fallacy is the use of poor reasoning. Therefore, the term formal fallacy is preferred. In informal discourse, however, logical fallacy is used to mean an argument that is problematic for any reason.

The term non sequitur denotes a general formal fallacy, often meaning one that does not belong to any named subclass of formal fallacies, like affirming the consequent.

Common examples

Main article: List of fallacies § Formal fallacies

Ecological fallacy

An ecological fallacy is committed when one draws an inference from data based on the premise that qualities observed for groups necessarily hold for individuals; for example, "if countries with more Protestants tend to have higher suicide rates, then Protestants must be more likely to commit suicide."

Fallacy fork

Maarten Boudry and others have argued that formal, deductive fallacies rarely occur in real life and that arguments that would be fallacious in formally deductive terms are not necessarily so when context and prior probabilities are taken into account, thus making the argument defeasible and/or inductive. Boudry coined the term fallacy fork. For a given fallacy, one must either characterize it by means of a deductive argumentation scheme, which rarely applies (the first prong of the fork), or one must relax definitions and add nuance to take the actual intent and context of the argument into account (the other prong of the fork). To argue, for example, that one became nauseated after eating a mushroom because the mushroom was poisonous could be an example of the post hoc ergo propter hoc fallacy.

Informal fallacy

Main article: Informal fallacy

In contrast to a formal fallacy, an informal fallacy originates from a reasoning error other than a flaw in the logical form of the argument. A deductive argument containing an informal fallacy may be formally valid, but still remain rationally unpersuasive. Nevertheless, informal fallacies apply to both deductive and non-deductive arguments.

Though the form of the argument may be relevant, fallacies of this type are "types of mistakes in reasoning that arise from the mishandling of the content of the propositions constituting the argument".

Faulty generalization

A special subclass of the informal fallacies is the set of faulty generalizations, also known as inductive fallacies. Here, the most important issue concerns inductive strength or methodology (for example, statistical inference). In the absence of sufficient evidence, drawing conclusions based on induction is unwarranted and fallacious. With the backing of sufficient amounts of the right type of empirical evidence, however, the conclusions may become warranted and convincing (at which point the arguments are no longer considered fallacious).

Hasty generalization

Hasty generalization is described as making assumptions about a whole group or range of cases based on a sample that is inadequate (usually because it is atypical or just too small). Stereotypes about people ("frat boys are drunkards", "grad students are nerdy", "women don't enjoy sports", etc.) are common examples of the principle.

Hasty generalization often follows a pattern such as:

X is true for A.

X is true for B.

Therefore, X is true for C, D, etc.

While never a valid logical deduction, if such an inference can be made on statistical grounds, it may nonetheless be convincing. This is because with enough empirical evidence, the generalization is no longer a hasty one.

Relevance fallacy

The fallacies of relevance are a broad class of informal fallacies, generically represented by missing the point: presenting an argument that may be sound but fails to address the issue in question.

Argument from silence

An argument from silence is a faulty conclusion that is drawn based on the absence of evidence rather than on the presence of evidence.

Examples of informal fallacies

Main article: List of fallacies § Informal fallacies

Post hoc (false cause)

The post hoc fallacy assumes that because B comes after A, A caused B. It gets its name from the Latin phrase "post hoc, ergo propter hoc", which translates as "after this, therefore because of this".

Sometimes one event really does cause another one that comes later—for example, if one registers for a class and their name later appears on the roll, it's true that the first event caused the one that came later. But sometimes two events that seem related in time are not really related as cause and event. That is, temporal correlation does not necessarily entail causation. For example, if one eats a sandwich and then gets food poisoning, that does not necessarily mean the sandwich caused the food poisoning. Something else eaten earlier might have caused the food poisoning.

Slippery slope

For an argument to be a slippery slope type of argument, it must meet the requirements of that argumentation scheme. A slippery slope argument originates from a conversation or debate in which two actors take turns. It usually originates from one actor giving advice on a decision or act. Along the way, the actor must make additional choices on similar matters through which the actor enters the ‘grey area’ of the slippery slope. At this point, the actor potentially loses control over the direction of the arguments, thus leading to a ‘fatal’ outcome.

Such an argument is built up according to the following argumentation scheme: initial premise, sequential premise, indeterminacy premise, control premise, loss of control premise, catastrophic outcome premise, and conclusion. Slippery slope arguments may be defeated by asking critical questions or giving counterarguments.

There are several reasons for a slippery slope to be fallacious: for example, the argument is going too far into the future, it is a too complex argument whose structure is hard to identify, or the argument makes emotional appeals.

It may be that a slippery slope is not necessarily fallacious if context is taken into account and there is an effort to assess plausibility.

False analogy

Informally known as the "apples and oranges" fallacy, a false analogy uses unsound comparisons.

Straw man fallacy

The straw man fallacy refers to the refutation of a standpoint in an argument that was never proposed. The fallacy usually occurs in the presentation of an opponent's standpoint as more extreme, distorted, or simplistic than it actually is. Compared to criticizing the opponent's actual standpoint, this allows the arguer to offer a seeming refutation of what is, however, not the actual standpoint. Such an argument involves two arguers, with one criticizing the other's perspective. The reason for the straw man argument to be fallacious originates from the problem of how to deal with natural discourse. The opponent's argument is not reflected by the arguments that are proposed by the speaker.

Measurement fallacy

Some of the fallacies described above may be committed in the context of measurement. Where mathematical fallacies are subtle mistakes in reasoning leading to invalid mathematical proofs, measurement fallacies are unwarranted inferential leaps involved in the extrapolation of raw data to a measurement-based value claim. The ancient Greek Sophist Protagoras was one of the first thinkers to propose that humans can generate reliable measurements through his "human-measure" principle and the practice of dissoi logoi (arguing multiple sides of an issue). This history helps explain why measurement fallacies are informed by informal logic and argumentation theory.

Knowledge value measurement fallacy

The increasing availability and circulation of big data are driving a proliferation of new metrics for scholarly authority, and there is lively discussion regarding the relative usefulness of such metrics for measuring the value of knowledge production in the context of an "information tsunami."

For example, anchoring fallacies can occur when unwarranted weight is given to data generated by metrics that the arguers themselves acknowledge are flawed. For example, the limitations of the journal impact factor (JIF) are well documented, and even JIF pioneer Eugene Garfield notes that, "while citation data create new tools for analyses of research performance, it should be stressed that they supplement rather than replace other quantitative and qualitative indicators." To the extent that arguers jettison the acknowledged limitations of JIF-generated data in evaluative judgments or leave behind Garfield's "supplement rather than replace" caveat, they commit anchoring fallacies.

A naturalistic fallacy can occur, for example, in the case of sheer quantity metrics based on the premise "more is better" or, in the case of developmental assessment in the field of psychology, "higher is better".

A false analogy occurs when claims are supported by unsound comparisons between data points. For example, the Scopus and Web of Science bibliographic databases have difficulty distinguishing between citations of scholarly work that are arms-length endorsements, ceremonial citations, or negative citations (indicating the citing author withholds endorsement of the cited work). Hence, measurement-based value claims premised on the uniform quality of all citations may be questioned on false analogy grounds.

As another example, consider the Faculty Scholarly Productivity Index of Academic Analytics. This tool purports to measure overall faculty productivity, yet it does not capture data based on citations in books. This creates a possibility that low productivity measurements using the tool commit argument from silence fallacies, to the extent that such measurements are supported by the absence of book citation data.

Ecological fallacies can be committed when one measures the scholarly productivity of a sub-group of individuals (e.g. "Puerto Rican" faculty) via reference to aggregate data about a larger and different group (e.g., "Hispanic" faculty).

Intentional fallacy

Sometimes a speaker or writer uses a fallacy intentionally. In any context, including academic debate, a conversation among friends, political discourse, advertising, or comedic purposes, the arguer may use fallacious reasoning to try to persuade the listener or reader, by means other than offering relevant evidence, that the conclusion is true.

Examples of this include the speaker or writer:

1. Diverting the argument to unrelated issues with a red herring (Ignoratio elenchi)
2. Insulting someone's character (argumentum ad hominem)
3. Assuming the conclusion of an argument, a kind of circular reasoning, also called "begging the question" (petitio principii)
4. Making jumps in logic (non sequitur)
5. Identifying a false cause and effect (post hoc ergo propter hoc)
6. Asserting that everyone agrees (argumentum ad populum, bandwagoning)
7. Creating a false dilemma (either-or fallacy) in which the situation is oversimplified, also called false dichotomy
8. Selectively using facts (card stacking)
9. Making false or misleading comparisons (false equivalence or false analogy)
10. Generalizing quickly and sloppily (hasty generalization) (secundum quid)
11. Using an argument's connections to other concepts or people to support or refute it, also called "guilt by association" (association fallacy)
12. Claiming that a lack of proof counts as proof (appeal to ignorance)

In humor, errors of reasoning are used for comical purposes. Groucho Marx used fallacies of amphiboly, for instance, to make ironic statements; Gary Larson and Scott Adams employed fallacious reasoning in many of their cartoons. Wes Boyer and Samuel Stoddard have written a humorous essay teaching students how to be persuasive by means of a whole host of informal and formal fallacies.

When someone uses logical fallacies intentionally to mislead in academic, political, or other high-stakes contexts, the breach of trust calls into question the authority and intellectual integrity of that person.

Assessment: pragmatic theory

See also: Argumentation scheme

According to the pragmatic theory, a fallacy can be either a heuristic error or a ploy used intentionally to unfairly win an argument. There are always two parties to an argument containing a fallacy: the perpetrator and the intended victim.

The dialogue framework required to support the pragmatic theory of fallacy is built on the presumption that argumentative dialogue has both an adversarial component and a collaborative component. A dialogue has individual goals for each participant as well as shared goals that apply to all participants. A fallacy of the second kind is seen as more than simply a violation of the rule of reasonable dialogue. It is also a deceptive tactic of argumentation based on sleight-of-hand. Aristotle explicitly compared contentious reasoning to unfair fighting in athletic contests. But the roots of the pragmatic theory go back even further in history, to the Sophists. The pragmatic theory finds its roots in the Aristotelian conception of a fallacy as a sophistical refutation but also supports the view that many of the types of arguments traditionally labeled as fallacies are in fact reasonable techniques of argumentation that can be used, in many cases, to support legitimate goals of dialogue. Hence, under the pragmatic approach, each case needs to be analyzed individually to determine whether the argument is fallacious or reasonable.

Boolean function

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Boolean_function

A binary decision diagram and truth table of a ternary Boolean function

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually {true, false}, {0,1} or {-1,1}). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

A Boolean function takes the form ${\displaystyle f:\{0,1{\}}^k\to \{0,1\}}$, where ${\displaystyle \{0,1\}}$ is known as the Boolean domain and ${\displaystyle k}$ is a non-negative integer called the arity of the function. In the case where ${\displaystyle k=0}$, the function is a constant element of ${\displaystyle \{0,1\}}$. A Boolean function with multiple outputs, ${\displaystyle f:\{0,1{\}}^k\to \{0,1{\}}^m}$ with ${\displaystyle m>1}$ is a vectorial or vector-valued Boolean function (an S-box in symmetric cryptography).

There are ${\displaystyle 2^{2^k}}$ different Boolean functions with ${\displaystyle k}$ arguments; equal to the number of different truth tables with ${\displaystyle 2^k}$ entries.

Every ${\displaystyle k}$-ary Boolean function can be expressed as a propositional formula in ${\displaystyle k}$ variables ${\displaystyle x_1,...,x_k}$, and two propositional formulas are logically equivalent if and only if they express the same Boolean function.

Examples

The sixteen binary Boolean functions

See also: Truth table

The rudimentary symmetric Boolean functions (logical connectives or logic gates) are:

• NOT, negation or complement - which receives one input and returns true when that input is false ("not")
• AND or conjunction - true when all inputs are true ("both")
• OR or disjunction - true when any input is true ("either")
• XOR or exclusive disjunction - true when one of its inputs is true and the other is false ("not equal")
• NAND or Sheffer stroke - true when it is not the case that all inputs are true ("not both")
• NOR or logical nor - true when none of the inputs are true ("neither")
• XNOR or logical equality - true when both inputs are the same ("equal")

An example of a more complicated function is the majority function (of an odd number of inputs).

Representation

A Boolean function represented as a Boolean circuit

A Boolean function may be specified in a variety of ways:

• Truth table: explicitly listing its value for all possible values of the arguments
  • Marquand diagram: truth table values arranged in a two-dimensional grid (used in a Karnaugh map)
  • Binary decision diagram, listing the truth table values at the bottom of a binary tree
  • Venn diagram, depicting the truth table values as a colouring of regions of the plane

Algebraically, as a propositional formula using rudimentary Boolean functions:

• Negation normal form, an arbitrary mix of AND and ORs of the arguments and their complements
• Disjunctive normal form, as an OR of ANDs of the arguments and their complements
• Conjunctive normal form, as an AND of ORs of the arguments and their complements
• Canonical normal form, a standardized formula which uniquely identifies the function:
  • Algebraic normal form or Zhegalkin polynomial, as a XOR of ANDs of the arguments (no complements allowed)
  • Full (canonical) disjunctive normal form, an OR of ANDs each containing every argument or complement (minterms)
  • Full (canonical) conjunctive normal form, an AND of ORs each containing every argument or complement (maxterms)
  • Blake canonical form, the OR of all the prime implicants of the function

Boolean formulas can also be displayed as a graph:

• Propositional directed acyclic graph
  • Digital circuit diagram of logic gates, a Boolean circuit
  • And-inverter graph, using only AND and NOT

In order to optimize electronic circuits, Boolean formulas can be minimized using the Quine–McCluskey algorithm or Karnaugh map.

Analysis

See also: Analysis of Boolean functions

Properties

A Boolean function can have a variety of properties:

• Constant: Is always true or always false regardless of its arguments.
• Monotone: for every combination of argument values, changing an argument from false to true can only cause the output to switch from false to true and not from true to false. A function is said to be unate in a certain variable if it is monotone with respect to changes in that variable.
• Linear: for each variable, flipping the value of the variable either always makes a difference in the truth value or never makes a difference (a parity function).
• Symmetric: the value does not depend on the order of its arguments.
• Read-once: Can be expressed with conjunction, disjunction, and negation with a single instance of each variable.
• Balanced: if its truth table contains an equal number of zeros and ones. The Hamming weight of the function is the number of ones in the truth table.
• Bent: its derivatives are all balanced (the autocorrelation spectrum is zero)
• Correlation immune to mth order: if the output is uncorrelated with all (linear) combinations of at most m arguments
• Evasive: if evaluation of the function always requires the value of all arguments
• A Boolean function is a Sheffer function if it can be used to create (by composition) any arbitrary Boolean function (see functional completeness)
• The algebraic degree of a function is the order of the highest order monomial in its algebraic normal form

Circuit complexity attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them.

Derived functions

A Boolean function may be decomposed using Boole's expansion theorem in positive and negative Shannon cofactors (Shannon expansion), which are the (k-1)-ary functions resulting from fixing one of the arguments (to zero or one). The general (k-ary) functions obtained by imposing a linear constraint on a set of inputs (a linear subspace) are known as subfunctions.

The Boolean derivative of the function to one of the arguments is a (k-1)-ary function that is true when the output of the function is sensitive to the chosen input variable; it is the XOR of the two corresponding cofactors. A derivative and a cofactor are used in a Reed–Muller expansion. The concept can be generalized as a k-ary derivative in the direction dx, obtained as the difference (XOR) of the function at x and x + dx.

The Möbius transform (or Boole-Möbius transform) of a Boolean function is the set of coefficients of its polynomial (algebraic normal form), as a function of the monomial exponent vectors. It is a self-inverse transform. It can be calculated efficiently using a butterfly algorithm ("Fast Möbius Transform"), analogous to the Fast Fourier Transform. Coincident Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients. There are 2^2^(k−1) coincident functions of k arguments.

Cryptographic analysis

The Walsh transform of a Boolean function is a k-ary integer-valued function giving the coefficients of a decomposition into linear functions (Walsh functions), analogous to the decomposition of real-valued functions into harmonics by the Fourier transform. Its square is the power spectrum or Walsh spectrum. The Walsh coefficient of a single bit vector is a measure for the correlation of that bit with the output of the Boolean function. The maximum (in absolute value) Walsh coefficient is known as the linearity of the function. The highest number of bits (order) for which all Walsh coefficients are 0 (i.e. the subfunctions are balanced) is known as resiliency, and the function is said to be correlation immune to that order. The Walsh coefficients play a key role in linear cryptanalysis.

The autocorrelation of a Boolean function is a k-ary integer-valued function giving the correlation between a certain set of changes in the inputs and the function output. For a given bit vector it is related to the Hamming weight of the derivative in that direction. The maximal autocorrelation coefficient (in absolute value) is known as the absolute indicator. If all autocorrelation coefficients are 0 (i.e. the derivatives are balanced) for a certain number of bits then the function is said to satisfy the propagation criterion to that order; if they are all zero then the function is a bent function. The autocorrelation coefficients play a key role in differential cryptanalysis.

The Walsh coefficients of a Boolean function and its autocorrelation coefficients are related by the equivalent of the Wiener–Khinchin theorem, which states that the autocorrelation and the power spectrum are a Walsh transform pair.

Linear approximation table

These concepts can be extended naturally to vectorial Boolean functions by considering their output bits (coordinates) individually, or more thoroughly, by looking at the set of all linear functions of output bits, known as its components. The set of Walsh transforms of the components is known as a Linear Approximation Table (LAT) or correlation matrix; it describes the correlation between different linear combinations of input and output bits. The set of autocorrelation coefficients of the components is the autocorrelation table, related by a Walsh transform of the components to the more widely used Difference Distribution Table (DDT) which lists the correlations between differences in input and output bits (see also: S-box).

Real polynomial form

On the unit hypercube

Any Boolean function ${\displaystyle f(x):\{0,1{\}}^n\to \{0,1\}}$ can be uniquely extended (interpolated) to the real domain by a multilinear polynomial in ${\displaystyle {\mathbb{R}}^n}$, constructed by summing the truth table values multiplied by indicator polynomials:

$${\displaystyle f^{\ast }(x)=\sum _{a\in {\{0,1\}}^n}f(a)\prod _{i:a_i=1}{x}_i\prod _{i:a_i=0}(1-x_i)}$$

For example, the extension of the binary XOR function ${\displaystyle x\oplus y}$ is

$${\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}$$

which equals

$${\displaystyle x+y-2xy}$$

Some other examples are negation (${\displaystyle 1-x}$), AND (${\displaystyle xy}$) and OR (${\displaystyle x+y-xy}$). When all operands are independent (share no variables) a function's polynomial form can be found by repeatedly applying the polynomials of the operators in a Boolean formula. When the coefficients are calculated modulo 2 one obtains the algebraic normal form (Zhegalkin polynomial).

Direct expressions for the coefficients of the polynomial can be derived by taking an appropriate derivative:

$${\displaystyle \begin{array}{lclll}{f}^{\ast }(00)& =& (f^{\ast })(00)& =& f(00)\\ f^{\ast }(01)& =& ({\mathrm{\partial }}_1{f}^{\ast })(00)& =& -f(00)+f(01)\\ f^{\ast }(10)& =& ({\mathrm{\partial }}_2{f}^{\ast })(00)& =& -f(00)+f(10)\\ f^{\ast }(11)& =& ({\mathrm{\partial }}_1{\mathrm{\partial }}_2{f}^{\ast })(00)& =& f(00)-f(01)-f(10)+f(11)\end{array}}$$

this generalizes as the Möbius inversion of the partially ordered set of bit vectors:

$${\displaystyle f^{\ast }(m)=\sum _{a\subseteq m}(-1{)}^{|a|+|m|}f(a)}$$

where ${\displaystyle |a|}$ denotes the weight of the bit vector ${\displaystyle a}$. Taken modulo 2, this is the Boolean Möbius transform, giving the algebraic normal form coefficients:

$${\displaystyle \hat{f}(m)=\underset{a\subseteq m}{⨁}f(a)}$$

In both cases, the sum is taken over all bit-vectors a covered by m, i.e. the "one" bits of a form a subset of the one bits of m.

When the domain is restricted to the n-dimensional hypercube ${\displaystyle [0,1{]}^n}$, the polynomial ${\displaystyle f^{\ast }(x):[0,1{]}^n\to [0,1]}$ gives the probability of a positive outcome when the Boolean function f is applied to n independent random (Bernoulli) variables, with individual probabilities x. A special case of this fact is the piling-up lemma for parity functions. The polynomial form of a Boolean function can also be used as its natural extension to fuzzy logic.

On the symmetric hypercube

Often, the Boolean domain is taken as ${\displaystyle \{-1,1\}}$, with false ("0") mapping to 1 and true ("1") to -1 (see Analysis of Boolean functions). The polynomial corresponding to ${\displaystyle g(x):\{-1,1{\}}^n\to \{-1,1\}}$ is then given by:

$${\displaystyle g^{\ast }(x)=\sum _{a\in {\{-1,1\}}^n}g(a)\prod _{i:a_i=-1}\frac{1-x_i}{2}\prod _{i:a_i=1}\frac{1+x_i}{2}}$$

Using the symmetric Boolean domain simplifies certain aspects of the analysis, since negation corresponds to multiplying by -1 and linear functions are monomials (XOR is multiplication). This polynomial form thus corresponds to the Walsh transform (in this context also known as Fourier transform) of the function (see above). The polynomial also has the same statistical interpretation as the one in the standard Boolean domain, except that it now deals with the expected values ${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$ (see piling-up lemma for an example).

Applications

Boolean functions play a basic role in questions of complexity theory as well as the design of processors for digital computers, where they are implemented in electronic circuits using logic gates.

The properties of Boolean functions are critical in cryptography, particularly in the design of symmetric key algorithms (see substitution box).

In cooperative game theory, monotone Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory.