 |
 | This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics | | | Top | This article has been rated as Top-priority on the project's priority scale. |
|
 | This article is within the scope of WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.StatisticsWikipedia:WikiProject StatisticsTemplate:WikiProject StatisticsStatistics | | | Top | This article has been rated as Top-importance on the importance scale. |
|
 | This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science | | | High | This article has been rated as High-importance on the project's importance scale. | |
|
|
|
|
| Index
|
|
|
This page has archives. Topics inactive for 90 days are automatically archived by Lowercase sigmabot III if there are more than 5. |
The word "countable" does not appear in this article. Nor is it mentioned that some boolean algebras are not power sets. Never mind that there are (40-year-old) classification theorems for countable boolean algebras. I would love it if this was remedied, either in this article, or in some other. Alas, I am not finding such an exposition in Wikipedia. I do not have the wherewithal to be bold and write such content myself. Anyone? 67.198.37.16 (talk) 01:40, 28 April 2023 (UTC)[reply]
- Oooh, seems that Boolean algebras canonically defined begins to tackle this. Still, this article should mention this. 67.198.37.16 (talk) 02:05, 28 April 2023 (UTC)[reply]
- This article is not about Boolean algebras — that's at Boolean algebra (structure). This is about "Boolean algebra" as a mass noun — basically the same as the propositional calculus. --Trovatore (talk) 02:12, 28 April 2023 (UTC)[reply]
To find the dual operator one has to negate the operands and find the operator that provides the opposite results with the negated operands. Here are the truth tables of all 8 dual operator pairs:
(
a
{\displaystyle (a}
 |
∧
{\displaystyle \land }
 |
b
)
{\displaystyle b)}
 |
↔
{\displaystyle \leftrightarrow }
 |
¬
{\displaystyle \neg }
 |
(
¬
a
{\displaystyle (\neg {}a}
 |
∨
{\displaystyle \lor }
 |
¬
b
)
{\displaystyle \neg {}b)}
 |
|---|
| 0 | 0 | 0 | | | 1 | 1 | 1 |
| 0 | 0 | 1 | | | 1 | 1 | 0 |
| 1 | 0 | 0 | | | 0 | 1 | 1 |
| 1 | 1 | 1 | | | 0 | 0 | 0 |
|
|
(
a
{\displaystyle (a}
|
∧
¯
{\displaystyle {\overline {\land }}}
 |
b
)
{\displaystyle b)}
|
↔
{\displaystyle \leftrightarrow }
|
¬
{\displaystyle \neg }
|
(
¬
a
{\displaystyle (\neg {}a}
|
∨
¯
{\displaystyle {\overline {\lor }}}
 |
¬
b
)
{\displaystyle \neg {}b)}
|
|---|
| 0 | 1 | 0 | | | 1 | 0 | 1 |
| 0 | 1 | 1 | | | 1 | 0 | 0 |
| 1 | 1 | 0 | | | 0 | 0 | 1 |
| 1 | 0 | 1 | | | 0 | 1 | 0 |
|
|
(
a
{\displaystyle (a}
|
→
{\displaystyle \rightarrow }
 |
b
)
{\displaystyle b)}
|
↔
{\displaystyle \leftrightarrow }
|
¬
{\displaystyle \neg }
|
(
¬
a
{\displaystyle (\neg {}a}
|
←
¯
{\displaystyle {\overline {\leftarrow }}}
 |
¬
b
)
{\displaystyle \neg {}b)}
|
|---|
| 0 | 1 | 0 | | | 1 | 0 | 1 |
| 0 | 1 | 1 | | | 1 | 0 | 0 |
| 1 | 0 | 0 | | | 0 | 1 | 1 |
| 1 | 1 | 1 | | | 0 | 0 | 0 |
|
|
(
a
{\displaystyle (a}
|
←
{\displaystyle \leftarrow }
 |
b
)
{\displaystyle b)}
|
↔
{\displaystyle \leftrightarrow }
|
¬
{\displaystyle \neg }
|
(
¬
a
{\displaystyle (\neg {}a}
|
→
¯
{\displaystyle {\overline {\rightarrow }}}
 |
¬
b
)
{\displaystyle \neg {}b)}
|
|---|
| 0 | 1 | 0 | | | 1 | 0 | 1 |
| 0 | 0 | 1 | | | 1 | 1 | 0 |
| 1 | 1 | 0 | | | 0 | 0 | 1 |
| 1 | 1 | 1 | | | 0 | 0 | 0 |
|
|
(
a
{\displaystyle (a}
|
p
1
{\displaystyle \operatorname {p_{1}} }
 |
b
)
{\displaystyle b)}
|
↔
{\displaystyle \leftrightarrow }
|
¬
{\displaystyle \neg }
|
(
¬
a
{\displaystyle (\neg {}a}
|
p
1
¯
{\displaystyle \operatorname {\overline {p_{1}}} }
 |
¬
b
)
{\displaystyle \neg {}b)}
|
|---|
| 0 | 0 | 0 | | | 1 | 1 | 1 |
| 0 | 0 | 1 | | | 1 | 1 | 0 |
| 1 | 1 | 0 | | | 0 | 0 | 1 |
| 1 | 1 | 1 | | | 0 | 0 | 0 |
|
|
(
a
{\displaystyle (a}
|
p
2
{\displaystyle p_{2}}
 |
b
)
{\displaystyle b)}
|
↔
{\displaystyle \leftrightarrow }
|
¬
{\displaystyle \neg }
|
(
¬
a
{\displaystyle (\neg {}a}
|
p
2
¯
{\displaystyle {\overline {p_{2}}}}
 |
¬
b
)
{\displaystyle \neg {}b)}
|
|---|
| 0 | 0 | 0 | | | 1 | 1 | 1 |
| 0 | 1 | 1 | | | 1 | 0 | 0 |
| 1 | 0 | 0 | | | 0 | 1 | 1 |
| 1 | 1 | 1 | | | 0 | 0 | 0 |
|
|
(
a
{\displaystyle (a}
|
↔
{\displaystyle \leftrightarrow }
|
b
)
{\displaystyle b)}
|
↔
{\displaystyle \leftrightarrow }
|
¬
{\displaystyle \neg }
|
(
¬
a
{\displaystyle (\neg {}a}
|
↔
¯
{\displaystyle {\overline {\leftrightarrow }}}
 |
¬
b
)
{\displaystyle \neg {}b)}
|
|---|
| 0 | 1 | 0 | | | 1 | 0 | 1 |
| 0 | 0 | 1 | | | 1 | 1 | 0 |
| 1 | 0 | 0 | | | 0 | 1 | 1 |
| 1 | 1 | 1 | | | 0 | 0 | 0 |
|
|
(
a
{\displaystyle (a}
|
⊤
{\displaystyle \top }
 |
b
)
{\displaystyle b)}
|
↔
{\displaystyle \leftrightarrow }
|
¬
{\displaystyle \neg }
|
(
¬
a
{\displaystyle (\neg {}a}
|
⊥
{\displaystyle \bot }
 |
¬
b
)
{\displaystyle \neg {}b)}
|
|---|
| 0 | 1 | 0 | | | 1 | 0 | 1 |
| 0 | 1 | 1 | | | 1 | 0 | 0 |
| 1 | 1 | 0 | | | 0 | 0 | 1 |
| 1 | 1 | 1 | | | 0 | 0 | 0 |
|
Motivation:
In lambda calculus for instance Boolean values can be represented by the
K
{\displaystyle K}
and
K
i
{\displaystyle Ki}
combinators.
Let
K
{\displaystyle K}
be a function that takes two arguments and returns the first (selector-1) and let
K
i
{\displaystyle Ki}
be a function that returns the second (selector-2).
K
:=
λ
a
b
.
a
K
i
:=
λ
a
b
.
b
{\displaystyle {\begin{aligned}K&:=\lambda {}ab.a\\Ki&:=\lambda {}ab.b\end{aligned}}}
Lambda calculus is written in prefix-notation, so the leftmost symbol is the operator.
K
K
K
i
⇔
K
K
i
K
K
i
⇔
K
i
{\displaystyle {\begin{aligned}KKKi&\Leftrightarrow K\\KiKKi&\Leftrightarrow Ki\end{aligned}}}
Suppose we try to figure out which combinator should be 0 and which one should be 1 by applying
K
{\displaystyle K}
and
K
i
{\displaystyle Ki}
to pairs of
K
{\displaystyle K}
and
K
i
{\displaystyle Ki}
. There are 64 ways to combine tree of
K
{\displaystyle K}
,
K
i
{\displaystyle Ki}
and two variables to form such a binary function application. The 32 triplets with
K
{\displaystyle K}
or
K
i
{\displaystyle Ki}
in the operator position merely select an argument. Almost half of the others are duplicates with renamed variables.
Let's have a look at the ones with just one of the variables (either a or b) first.
a
K
i
a
⇔
a
K
i
K
i
⇔
K
i
a
a
K
⇔
a
K
K
⇔
K
a
a
a
⇔
a
a
K
i
⇔
a
K
a
⇔
a
K
K
i
⇔
a
a
K
i
K
⇔
{
K
i
when
a
=
K
K
when
a
=
K
i
{\displaystyle {\begin{aligned}aKia\Leftrightarrow aKiKi&\Leftrightarrow Ki\\aaK\Leftrightarrow aKK&\Leftrightarrow K\\aaa\Leftrightarrow aaKi\Leftrightarrow aKa\Leftrightarrow aKKi&\Leftrightarrow a\\aKiK&\Leftrightarrow {\begin{cases}Ki&{\text{when }}a=K\\K&{\text{when }}a=Ki\end{cases}}\end{aligned}}}
If we bind the variables with lambda expressions, we get all four possible Boolean unary operators - but not unambiguously.
λ
a
.
a
K
i
K
i
⇔
{
⊥
if
K
i
=
0
⊤
if
K
i
=
1
λ
a
.
a
K
K
⇔
{
⊤
if
K
=
1
⊥
if
K
=
0
λ
a
.
a
K
K
i
⇔
a
λ
a
.
a
K
i
K
⇔
¬
a
{\displaystyle {\begin{aligned}\lambda {}a.aKiKi&\Leftrightarrow {\begin{cases}\bot &{\text{if }}Ki=0\\\top &{\text{if }}Ki=1\end{cases}}\\\lambda {}a.aKK&\Leftrightarrow {\begin{cases}\top &{\text{if }}K=1\\\bot &{\text{if }}K=0\end{cases}}\\\lambda {}a.aKKi&\Leftrightarrow a\\\lambda {}a.aKiK&\Leftrightarrow \neg {}a\end{aligned}}}
Now let's have a look at the expressions with both variables.
λ
a
b
.
b
a
a
⇔
a
p
1
b
λ
a
b
.
a
b
b
⇔
a
p
2
b
λ
a
b
.
a
a
b
⇔
λ
a
b
.
a
K
b
⇔
{
a
∨
b
if
K
=
1
a
∧
b
if
K
=
0
λ
a
b
.
a
b
a
⇔
λ
a
b
.
a
b
K
i
⇔
{
a
∧
b
if
K
i
=
0
a
∨
b
if
K
i
=
1
λ
a
b
.
a
b
K
⇔
{
a
→
b
if
K
=
1
a
←
¯
b
if
K
=
0
λ
a
b
.
b
a
K
⇔
{
a
←
b
if
K
=
1
a
→
¯
b
if
K
=
0
λ
a
b
.
a
K
i
b
⇔
{
a
←
¯
b
if
K
i
=
0
a
→
b
if
K
i
=
1
λ
a
b
.
b
K
i
a
⇔
{
a
→
¯
b
if
K
i
=
0
a
←
b
if
K
i
=
1
{\displaystyle {\begin{aligned}\lambda {}ab.baa&\Leftrightarrow a\operatorname {p_{1}} b\\\lambda {}ab.abb&\Leftrightarrow a\operatorname {p_{2}} b\\\lambda {}ab.aab\Leftrightarrow \lambda {}ab.aKb&\Leftrightarrow {\begin{cases}a\lor b&{\text{if }}K=1\\a\land b&{\text{if }}K=0\end{cases}}\\\lambda {}ab.aba\Leftrightarrow \lambda {}ab.abKi&\Leftrightarrow {\begin{cases}a\land b&{\text{if }}Ki=0\\a\lor b&{\text{if }}Ki=1\end{cases}}\\\lambda {}ab.abK&\Leftrightarrow {\begin{cases}a\rightarrow b&{\text{if }}K=1\\a{\overline {\leftarrow }}b&{\text{if }}K=0\end{cases}}\\\lambda {}ab.baK&\Leftrightarrow {\begin{cases}a\leftarrow b&{\text{if }}K=1\\a{\overline {\rightarrow }}b&{\text{if }}K=0\end{cases}}\\\lambda {}ab.aKib&\Leftrightarrow {\begin{cases}a{\overline {\leftarrow }}b&{\text{if }}Ki=0\\a\rightarrow b&{\text{if }}Ki=1\end{cases}}\\\lambda {}ab.bKia&\Leftrightarrow {\begin{cases}a{\overline {\rightarrow }}b&{\text{if }}Ki=0\\a\leftarrow b&{\text{if }}Ki=1\end{cases}}\end{aligned}}}
We get 8 of 16 Boolean binary operators but because of duality it is impossible to decide whether
K
{\displaystyle K}
or
K
i
{\displaystyle Ki}
is the Boolean 0 or 1, respectively. 41.66.98.160 (talk) 22:43, 19 March 2024 (UTC)[reply]
Hi, I remade the edit as an accident, I didn't notice it was reverted. The logical connectives sidebar really does fit better in the "Operations" section semantically speaking, but I was moving it to the lead because that section looked crowded in my monitor, since the template pushed the table downwards and created a big blank space. As to whether it's useless, I think the template is useful as soon as any logical notation is featured, since it shows different notational variants for each of the connectives, so readers who are used to, say, & instead of ∧, will not be confused by the discrepancy between what they're used to and the article. But if you don't want it in the lead, again, I don't actually care enough to undo your edits, I did it by accident because I thought I must have forgotten to do it. Thiagovscoelho (talk) 18:55, 23 March 2024 (UTC)[reply]
The article suggests that Boolean algebra uses the same notation as propositional logic, but this is incorrect. Modern Boolean algebra uses the same notation as elementary algebra (i.e., the dot symbol, plus sign, etc.). Could an established editor research with mainstream sources and update the article? Thanks.... 2600:1008:A111:42FB:3041:712:E13E:4B2F (talk) 17:36, 21 July 2024 (UTC)[reply]
- Boolean algebras and Boolean rings are equivalent structures, one using logical connectives as operators, and the other using arithmetic operations. You are asserting that Boolean rings are more used in modern mathematics. This seems not true. If this were true, the exclusive or (the multiplication of Boolean rings) would be more used than the ordinary or. This is not the case. D.Lazard (talk) 18:46, 21 July 2024 (UTC)[reply]
- The OP did not say in modern mathematics, so may well have been thinking of in electronics (see e.g. [1], [2], [3]). catslash (talk) 01:38, 12 May 2025 (UTC)[reply]
I had a recent edit reverted here, and I disagree with the person who reverted my edit: https://en.wikipedia.org/w/index.php?title=Boolean_algebra&oldid=prev&diff=1347514512
The picture I am talking about is the one showing the AND, OR, and NOT gates under the "Digital logic gates" section. It shows both a triangular not gate, and a circular not gate on the output of the triangular one. The output of those two not gates would be the same as the input: x => ¬¬x = x. Mikk0384 (talk) 07:29, 15 April 2026 (UTC)[reply]
- The picture is clearly intended to show a single NOT gate. The shape is the same as in the article NOT gate. If two NOT gates would be intended, they should be joined by a line, not glued together. In any case, it would be highly confusing to have, in the same context, two different symbols for the same type of gate. So, I agree with the revert of your edit, and I'll revert it again. D.Lazard (talk) 08:51, 15 April 2026 (UTC)[reply]
- I’ve never heard of a triangle being an inverter. Where did you see that idea? In my world, a triangle indicates a buffer that repeats the logic signal (rarely needed). Johnuniq (talk) 09:16, 15 April 2026 (UTC)[reply]
level-4 vital article is rated C-class on Wikipedia's content assessment scale.
