Talk:Boolean algebra

Boole did not invent Boolean Algebra

According to a paper by Stanley Burris ( https://www.math.uwaterloo.ca/~snburris/htdocs/MYWORKS/PREPRINTS/aboole.pdf): "Contrary to popular belief Boole did not work with a two-element Boolean algebra, nor with the Boolean algebra of subsets of a given set. Boole was simply not doing Boolean algebra, nor Boolean rings."

Tashiro~enwiki (talk) 05:56, 26 December 2021 (UTC)

CS guy tackles modus ponens with mixed results

See the current status of my new section on Boolean algebra at modus ponens. For discussion, here's my addition just added:

The equivalent concept as formulated in Boolean algebra, the material conditional, expressing x implies y, is notated and defined by ${\textstyle x\rightarrow y=\neg {x}\vee y}$.

Modus ponens and modus tollens follow from the definition above, the rules of negation, and the commutative constant identity for disjunction:

${\begin{aligned}\neg {0}&=1\\\neg {1}&=0\\\neg {(\neg {x})}&=x\\(\neg {x}=y)&\rightarrow (x=\neg {y})\\x\vee 0&=x\\0\vee x&=x\\\end{aligned}}$

For modus ponens, assuming $x\rightarrow {y}=1$ (x implies y is true) and $x=1,$ we have:

${\textstyle 1=x\rightarrow y=1\rightarrow y=\neg {1}\vee y=0\vee y=y=1}$

For modus tollens, again assuming $x\rightarrow {y}=1$ and $y=0$, we have:

${\textstyle 1=x\rightarrow y=x\rightarrow 0=\neg {x}\vee 0=\neg {x}}$

${\textstyle \neg {1}=\neg (\neg {x})=x=0}$

This is Boolean algebra as filtered through how an ancient CS guy conceptualizes symbolic reasoning. Pedantic we can do. My problem is to make the rule set complete, I seemed to need to add a problematic rule:

$(\neg {x}=y)\rightarrow (x=\neg {y})$

This is problematic because it seems to hoist a level above the definition of rightarrow recently introduced.

I scanned the rules here at this page, and my extremely formal and pedantic justification for doing this seems lacking. I'm not even sure this page has defined equality as an operator resolving to a truth value (as common in many computer languages). A better mathematician than I will spot whether this is indeed an axiomatic gap at this page, or a merely an expository gap, or merely a gap of implied application, or even more merely the braino of an antique from across the aisle.

Also, if you can standardize the pedagogy, fill your boots. I was trying to avoid the arithmetic metaphor for this slight application, though perhaps that was misguided.

Note that I'm an extreme tumbleweed editor and I'm unlikely to return here; this is already far more time than I ordinarily expend in any one place. — MaxEnt 02:22, 14 October 2022 (UTC)

Just to be clear, my strange rule reads to a CS guy as "rewrites as" at the level of whole equations. I'm well aware this is a frame jump, even if it also happens to be algebraically sound. — MaxEnt 02:27, 14 October 2022 (UTC)

You seem to be looking for the law of the excluded middle, but this is a distinct axiom, and if it is rejected, then you get intuitionistic logic. From there, things snowball into Heyting algebras and assorted other logics. Much of it is not straight-forward. 67.198.37.16 (talk) 01:48, 28 April 2023 (UTC)

Countable boolean algebras?

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)

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)

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)

Duality

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

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

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

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

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

${\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$ or $Ki$ is the Boolean 0 or 1, respectively. 41.66.98.160 (talk) 22:43, 19 March 2024 (UTC)

Not edit warring

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)