Concept
Boolean function
Overview
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
f
:
{
0
,
1
}
k
→
{
0
,
1
}
{\displaystyle f:\{0,1\}^{k}\to \{0,1\}}
, where
{
0
,
1
}
{\displaystyle \{0,1\}}
is known as the Boolean domain and
k
{\displaystyle k}
is a non-negative integer called the arity of the function. In the case where
k
=
0
{\displaystyle k=0}
, the function is a constant element of
{
0
,
1
}
{\displaystyle \{0,1\}}
. A Boolean function with multiple outputs,
f
:
{
0
,
1
}
k
→
{
0
,
1
}
m
{\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}
with
m
>
1
{\displaystyle m>1}
is a vectorial or vector-valued Boolean function (an S-box in symmetric cryptography).
There are
2
2
k
{\displaystyle 2^{2^{k}}}
different Boolean functions with
k
{\displaystyle k}
arguments; equal to the number of different truth tables with
2
k
{\displaystyle 2^{k}}
entries.
Every
k
{\displaystyle k}
-ary Boolean function can be expressed as a propositional formula in
k
{\displaystyle k}
variables
x
1
,
.
.
.
,
x
k
{\displaystyle x_{1},...,x_{k}}
, and two propositional formulas are logically equivalent if and only if they express the same Boolean function.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
Any such select set is called the set of postulates, or premises, from which the reasoning proceeds. The reasoning is nothing else than the exhibition of the whole pattern of general conditions involved in the pattern derived from the selected postulates.
Alfred North Whitehead, Science and the modern world
States what Boolean function is.
Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Boolean function is.
If there were anywhere an infinity of things to count, an unintelligible supposition, it would by no means be true that any selection of things from that series would be the equivalent of all things in the series, except in so far as equivalence meant that they could be arranged in the same type of series as that from which they were drawn.
John Dewey, Creative Intelligence
States what Boolean function is.
Philosophers who discussed Boolean function
Related ideas
- Exclusive or
- Negation
- Logical equivalence
- Social choice theory
- Logical conjunction
- Logical connective
- Function (mathematics)
- Mathematics
- Logical NOR
- Truth table
- Sheffer stroke
- Boolean domain
- Arity
- Logic
- Fuzzy logic
- Computer science
- Boolean algebra
- Truth function
- Venn diagram
- Computational complexity theory
- Logical disjunction
- Algebraic normal form
- Parity function
- Negation normal form
Place in the tradition
Part of Intuitionistic logic.