Talk:Boolean algebra

This is the talk page for discussing improvements to the Boolean algebra article. This is not a forum for general discussion of the subject of the article.

Add new text under old text. New to Wikipedia? Welcome! Learn to edit; get help. Start a new topic Assume good faith Be polite and avoid personal attacks Be welcoming to newcomers Seek dispute resolution if needed Article policies Neutral point of view No original research Verifiability Shortcut Talk:Boolean algebra (structure)

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Archives (index): 1, 2, 3, 4, 5Auto-archiving period: 3 months

This  level-4 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Top‑priority 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. Statistics Top‑importance 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. Computer science High‑importance 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. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Archives

Index Archive 1 Archive 2 Archive 3 Archive 4 Archive 5

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:

${\displaystyle (a}$ ${\displaystyle \land }$ ${\displaystyle b)}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg }$ ${\displaystyle (\neg {}a}$ ${\displaystyle \lor }$ ${\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	${\displaystyle (a}$ ${\displaystyle {\overline {\land }}}$ ${\displaystyle b)}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg }$ ${\displaystyle (\neg {}a}$ ${\displaystyle {\overline {\lor }}}$ ${\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
${\displaystyle (a}$ ${\displaystyle \rightarrow }$ ${\displaystyle b)}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg }$ ${\displaystyle (\neg {}a}$ ${\displaystyle {\overline {\leftarrow }}}$ ${\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	${\displaystyle (a}$ ${\displaystyle \leftarrow }$ ${\displaystyle b)}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg }$ ${\displaystyle (\neg {}a}$ ${\displaystyle {\overline {\rightarrow }}}$ ${\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
${\displaystyle (a}$ ${\displaystyle \operatorname {p_{1}} }$ ${\displaystyle b)}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg }$ ${\displaystyle (\neg {}a}$ ${\displaystyle \operatorname {\overline {p_{1}}} }$ ${\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	${\displaystyle (a}$ ${\displaystyle p_{2}}$ ${\displaystyle b)}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg }$ ${\displaystyle (\neg {}a}$ ${\displaystyle {\overline {p_{2}}}}$ ${\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
${\displaystyle (a}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle b)}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg }$ ${\displaystyle (\neg {}a}$ ${\displaystyle {\overline {\leftrightarrow }}}$ ${\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	${\displaystyle (a}$ ${\displaystyle \top }$ ${\displaystyle b)}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg }$ ${\displaystyle (\neg {}a}$ ${\displaystyle \bot }$ ${\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 ${\displaystyle K}$ and ${\displaystyle Ki}$ combinators. Let ${\displaystyle K}$ be a function that takes two arguments and returns the first (selector-1) and let ${\displaystyle Ki}$ be a function that returns the second (selector-2).

${\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.

${\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 ${\displaystyle K}$ and ${\displaystyle Ki}$ to pairs of ${\displaystyle K}$ and ${\displaystyle Ki}$. There are 64 ways to combine tree of ${\displaystyle K}$, ${\displaystyle Ki}$ and two variables to form such a binary function application. The 32 triplets with ${\displaystyle K}$ or ${\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.

${\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.

${\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.

${\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 ${\displaystyle K}$ or ${\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]