Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Questions regarding Boolean algebras as structures, or regarding functions defined from/to Boolean algebras fit into this tag very nicely. For Boolean logic use the tag propositional logic

learn more… | top users | synonyms

32
votes
0answers
1k views

Is this *really* a categorical approach to *integration*?

Here's an article by Reinhard Börger I found recently whose title and content, prima facie, seem quite exciting to me, given my misadventures lately (like this and this); it's called, "A Categorical ...
31
votes
1answer
1k views

Universal binary operation and finite fields (ring)

Take Boolean Algebra for instance, the underlying finite field/ring $0, 1, \{AND, OR\}$ is equivalent to $ 0, 1, \{NAND\} $ or $ 0, 1, \{ NOR \}$ where NAND and NOR are considered as universal gates. ...
22
votes
2answers
1k views

Any two points in a Stone space can be disconnected by clopen sets

Let $B$ be a Stone space (compact, Hausdorff, and totally disconnected). Then I am basically certain (because of Stone's representation theorem) that if $a, b \in B$ are two distinct points in $B$, ...
17
votes
2answers
2k views

Why are Boolean Algebras called “Algebras”?

Boolean algebras aren't algebras (to the best of my understanding). So why are they called algebras? Wouldn't it make more sense to call them a "Boolean system" or a "Boology" or something else like ...
15
votes
6answers
21k views

Is XOR a combination of AND and NOT operators?

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?
10
votes
1answer
235 views

Stone's Representation Theorem and The Compactness Theorem

If you're working on $\mathsf {ZF}$ and you assume the compactness theorem for propositional logic, then you have the prime ideal theorem, and thus you can show that the dual of the category of ...
10
votes
2answers
422 views

A matrix w/integer eigenvalues and trigonometric identity

Any intuition and/or rigorous arguments on the proofs of the following statements would be appreciated: Let $n$ be a natural number. (a) Consider the following Toeplitz/circulant symmetric matrix: $...
10
votes
1answer
196 views

Saturated Boolean algebras in terms of model theory and in terms of partitions

Let $\kappa$ be an infinite cardinal. A Boolean algebra $\mathbb{B}$ is said to be $\kappa$-saturated if there is no partition (i.e., collection of elements of $\mathbb{B}$ whose pairwise meet is $0$ ...
10
votes
1answer
647 views

What are the algebras of the double powerset monad?

Let $\mathscr{P} : \textbf{Set} \to \textbf{Set}^\textrm{op}$ be the (contravariant) powerset functor, taking a set $X$ to its powerset $\mathscr{P}(X)$ and a map $f : X \to Y$ to the inverse image ...
9
votes
3answers
799 views

Rationale behind truth values

I originaly asked a question on Programmers.SE to know why $0$ was consider $\text{false}$ and all the other [integral] values were considered $\text{true}$. That was a huge debate and many said it ...
9
votes
2answers
273 views

The ring of idempotents

Let $R$ be a commutative ring. Then its ring of idempotents $I(R)$ consists of the idempotent elements of $R$, with the same multiplication as in $R$, but with the new addition $x \oplus y := x+y-2xy$....
8
votes
3answers
25k views

De-Morgan's theorem for 3 variables?

The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'. I didn't find the answer for my question, therefore I'll ask here: ...
8
votes
1answer
1k views

Examples of topologies in which all open sets are regular?

An open subset U of a space X is regular if it equals the interior of its closure, as we learn from the Wikipedia glossary of topology. Furthermore, the regular open subsets of a space (any space) ...
8
votes
2answers
87 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - $...
7
votes
5answers
24k views

Duality principle in boolean algebra

All the definitions I came across so far stated, that if a statement is true, then also its dual statement is true and this dual statement is obtained by changing + ...
7
votes
1answer
214 views

Example of Boolean Algebra that satisfies distributive law but violates complete distributive law

More precisely, I'm interested to know the example of Boolean Algebra $B$, such that for any $a, b, c \in B$, $a \cap (b \cup c) = (a \cap b) \cup (a \cap c)$, but there exists $\{ P_{ij}:i\in I, j \...
7
votes
1answer
117 views

Existence of surjective homomorphism between Boolean algebras $\Lambda\subset\mathscr P(\mathscr B)\to\mathscr B$ (in ZF)

I am trying to prove the following theorem, due to Tarski according to W. A. J. Luxemburg on Reduced powers of the real number system and equivalents of the Hahn-Banach extension theorem: Given a ...
6
votes
4answers
4k views

An “atom” in Boolean algebra

Could someone explain what an atom in Boolean algebra means? I am acquainted with ring theory and group theory but not Boolean algebra. As far as I can tell from browsing around, it is something like ...
6
votes
2answers
255 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
6
votes
3answers
236 views

Peculiar examples to the Stone Representation Theorem

The Stone Representation theorem states that every Boolean algebra is isomorphic to a field of sets. That is, a Boolean algebra whose elements are sets, and sums, products, negation are union, ...
6
votes
2answers
140 views

Can we describe multiplication on $\mathbb{F}_{2^n}$ as action on subsets of $n$-element set?

The symmetric difference between two set $A$ and $B$ denoted $A \triangle B$ is defined as the set $(A - B) \cup (B - A)$ or equivalently $(A \cup B) - (A \cap B)$. Some years ago I was quite excited ...
6
votes
3answers
1k views

How to prove a set of sentential connectives is incomplete?

On Page 52, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Show that $\{\lnot, \# \}$ is not complete. A set of connective symbols is complete, if every function $G : \{F, T\}^n ...
6
votes
4answers
123 views

Can this set of rules perform all Boolean operations?

I never worked in this field before, I just thought about this set of rules and never saw something similar before. I apologise if I don't use the right mathematical vocabulary for my question. ...
6
votes
2answers
210 views

Axioms for atomless Boolean algebras

I'm embarrassed to be asking, but: "Write down a set of axioms for the theory of atomless Boolean algebras." This is Exercise 1.14 in Chapter 9 of "Models and Ultraproducts" by Bell and Slomson. I'm ...
6
votes
1answer
417 views

Definitionally equivalence between Boolean algebras and Boolean rings

On page 17, Introduction to Boolean Algebras,Steven Givant,Paul Halmos(2000): Motivated by this set-theoretic example, we can introduce into every Boolean algebra $A$ operations of addition and ...
6
votes
1answer
284 views

Simple functions and axiom of choice

The question I have is more of a curiosity, and that is why I decided to post here instead of Mathoverflow. Before posing the question, let me set up some background. Background: Let $\Omega$ be a ...
6
votes
1answer
393 views

Non-isomorphic countable Boolean algebras

I'm trying to solve the next exercise: Construct a sequence $\mathcal{B}_0,\mathcal{B}_1, \ldots$ of countable Boolean algebras such that for all $m \neq n$ then $\mathcal{B}_m \ncong \mathcal{B}_n$. ...
6
votes
1answer
261 views

A free boolean algebra

Consider the following definition: The boolean algebra $A$ is generated freely with the subset $G \subseteq A$ if for every boolean algebra $B$ and map $f:G \mapsto B$ there is precisely one ...
6
votes
1answer
164 views

Construct an OR gate when missing input information

Is there a way to construct an OR gate when the input for one combination is unknown? For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = T$:...
6
votes
3answers
493 views

Is there an $O(n^2)$ test to determine if an $n \times n$ Boolean matrix $B$ has an inverse?

D.E. Rutherford shows that if a Boolean matrix $B$ has an inverse, then $B^{-1}= B^T$, or $BB^T=B^TB=I$. I have two related questions: The only invertible Boolean matrices I can find are ...
6
votes
1answer
115 views

Boolean algebra gives rise to a ring

There is a well-known result that every boolean algebra $(R,0,1,\land,\lor,\neg)$ can be made a boolean ring by defining $$x\cdot y=x\land y\qquad\text{and}\qquad x+y=(x\land\neg y)\lor(y\land\neg x)\,...
5
votes
6answers
5k views

how to solve system of linear equations of XOR operation?

how can i solve this set of equations ? to get values of $x,y,z,w$ ? $$\begin{aligned} 1=x \oplus y \oplus z \end{aligned}$$ $$\begin{aligned}1=x \oplus y \oplus w \end{aligned}$$ $$\begin{aligned}0=x ...
5
votes
3answers
168 views

Can Boolean ring without unit be embedded into a boolean ring?

While going through a book (Lectures on Boolean algebra, Halmos) I got struck at the following question : Prove that every Boolean ring without a unit can be embedded in a Boolean ring with a unit. ...
5
votes
3answers
184 views

proving logical equivalence $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$

I am currently working through Velleman's book How To Prove It and was asked to prove the following $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$ This is my work thus far $...
5
votes
4answers
393 views

Non-isomorphic atomless Boolean algebras

All countable atomless algebras are isomorphic. Can one give an example of a pair of mutually non-isomorphic atomless Boolean algebras of cardinaliy continuum?
5
votes
2answers
271 views

Which law of logical equivalence says $P\Leftrightarrow Q ≡ (P\lor Q) \Rightarrow(P\land Q)$

I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
5
votes
2answers
5k views

Determining don't-care values in a Karnaugh Map

I'm having a hard time understanding how to find the don't-care values in a Karnaugh map. What does it even mean? If I have a boolean function, say $f(a,b,c,d)=a'bc+abc'+bc'd+a'bc'd$, how would I ...
5
votes
1answer
135 views

How to multiply out a statement form?

I got this form: (not M or V) and (A or not M) and (not B or M) and (B or V) and (A or not V) and (not A or B) Or: $$(\neg M\vee V) \wedge (A\vee\neg M) \wedge (\neg B \vee M) \wedge (B\vee V)...
5
votes
1answer
239 views

Boolean algebras of projections

Suppose $X$ is a Banach space with an unconditional basis $(e_n)$. Then, one may easily define a Boolean algebra of projections in $\mathcal{L}(E)$ which is isomorphic to the power-set of $\mathbb{N}$ ...
5
votes
1answer
132 views

Is it possible to express “$P\leftrightarrow Q$” as a formula in $\to,\neg$ with $P$ only appearing once?

I want to write a propositional logic formula for the biconditional that only uses one side of the biconditional once in the formula. I expect it is impossible, but can anyone think of a proof? There ...
5
votes
2answers
115 views

Boolean algebra question.

Is there a way to show that $$A\bar{B}C\bar{D}+D=A\bar{B}C+D$$ using the rules of boolean algebra? I tried several methods such as expanding D with $$D(D+\bar{D})$$ or adding $$D\bar{D}$$ to the ...
5
votes
1answer
245 views

Efficient division using binary math

I'm writing code for an FPGA and I need to divide a number by $1.024$. I could use floating and/or fixed point and instantiate a multiplier but I would like to see if I could do this multiplication ...
5
votes
2answers
649 views

Simplify $(A+C)(AD+AD) + AC + C$ using Boolean algebra

I have solved the equation like this: ...
5
votes
3answers
2k views

Counting Rows of a Truth Table that Satisfy a Condition

How can I mathematically count the number of rows in a truth table of n-inputs that will satisfy a certain boolean condition? For example, say I have a 4-input truth table that will in turn have 16 ...
5
votes
3answers
6k views

Simplify $A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$

How do you simply the following equation? $$X = A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$$ Here is what I did: $$\begin{eqnarray} X & = & A'B'C'D'+A'CD'(B'+B) + ACD'(B+B') \\ & =&...
5
votes
1answer
107 views

Adjoint for functor involving Boolean rings

Let $R$ be a a commutative ring with a unit element, then one can associate to $R$ a Boolean ring $B(R)$, as in this text by Bergman, last line of page 594. (I guess this is a very classical thing. ...
5
votes
1answer
314 views

Mixed Boolean Arithmetic Identity

I'm trying to prove/derive the equivalence of the following formula: $$ x*y = (x \land y) * (x \lor y) + (x \land \neg y) * (\neg x \land y) $$ whereas $(\land, \lor, \neg)$ correspond to bitwise ...
5
votes
2answers
236 views

Stone duality for ideals and filters (exercise)

In A Course in Universal Algebra (Burris, Sankapannavar), the exercise 4.4.7-8, p.158, says: Let $A$ be a Boolean algebra. Denote $A^\ast:=\{\text{ultrafilters of }A\}$, and give $A^\ast$ the ...
5
votes
1answer
188 views

Cantor-Bernstein theorem for $\sigma$-complete Boolean algebras.

I am working on problem 7.28 from Jech's Set Theory: Let A and B be σ-complete Boolean algebras. Let a and b be elements of A and B respectively. If A is isomorphic to B$\upharpoonright$b and B is ...
5
votes
1answer
140 views

What is a (-1)-morphism?

So, I read the John Baez essay "Lectures on n-categories and cohomology" and I understand the notion of a (-1)-category" and a (-2)-category" and how to derive them. However, I'm not totally clear on ...