Logical connectives
AND ${\displaystyle A\land B}$, ${\displaystyle A\cdot B}$, ${\displaystyle AB}$, ${\displaystyle A\&B}$, ${\displaystyle A\&\&B}$ equivalent ${\displaystyle A\equiv B}$, ${\displaystyle A\Leftrightarrow B}$, ${\displaystyle A\leftrightharpoons B}$ implies ${\displaystyle A\Rightarrow B}$, ${\displaystyle A\supset B}$, ${\displaystyle A\rightarrow B}$ NAND ${\displaystyle A{\overline {\land }}B}$, ${\displaystyle A\uparrow B}$, ${\displaystyle A\mid B}$, ${\displaystyle {\overline {A\cdot B}}}$ nonequivalent ${\displaystyle A\not \equiv B}$, ${\displaystyle A\not \Leftrightarrow B}$, ${\displaystyle A\nleftrightarrow B}$ NOR ${\displaystyle A{\overline {\lor }}B}$, ${\displaystyle A\downarrow B}$, ${\displaystyle {\overline {A+B}}}$ NOT ${\displaystyle \neg A}$, ${\displaystyle -A}$, ${\displaystyle {\overline {A}}}$, ${\displaystyle \sim A}$ OR ${\displaystyle A\lor B}$, ${\displaystyle A+B}$, ${\displaystyle A\mid B}$, ${\displaystyle A\parallel B}$ XNOR ${\displaystyle A\ {\text{XNOR}}\ B}$ XOR ${\displaystyle A{\underline {\lor }}B}$, ${\displaystyle A\oplus B}$ converse ${\displaystyle A\Leftarrow B}$, ${\displaystyle A\subset B}$, ${\displaystyle A\leftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

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}).^[1][2] Alternative names are switching function, used especially in older computer science literature,^[3][4] and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory.^[5]

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).^[6]

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 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 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

Properties

A Boolean function can have a variety of properties:^[7]

• 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
Zdroj:https://en.wikipedia.org?pojem=Boolean_function
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---