Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [boolean-algebra]

Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Use this tag for questions about Boolean algebras as structures, or about functions defined from/to Boolean algebras. For Boolean logic use the tag propositional-calculus.

114
votes
0answers
6k 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 ...
36
votes
14answers
5k views

Still struggling to understand vacuous truths

I know, I know, there are tons of questions on this -- I've read them all, it feels like. I don't understand why $(F \implies F) \equiv T$ and $(F \implies T) \equiv T$. One of the best examples I ...
32
votes
1answer
2k 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. ...
25
votes
2answers
2k 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$, ...
21
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 ...
19
votes
6answers
69k 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?
17
votes
6answers
76k 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 + ...
16
votes
3answers
72k 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: ...
15
votes
7answers
44k views

how many semantically different boolean functions are there for n boolean variables?

In short, this is an assignment question for a course I am taking - the exact wording is this: "Given n Boolean variables, how many 'semantically' different Boolean functions can you construct?" Now,...
13
votes
1answer
1k 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 ...
11
votes
4answers
53k views

Find DNF and CNF of an expression

I want to find the DNF and CNF of the following expression $$ x \oplus y \oplus z $$ I tried by using $$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$ but it got all messy. I also ...
11
votes
2answers
2k 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) ...
11
votes
1answer
317 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 ...
11
votes
1answer
270 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
3answers
1k 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 ...
10
votes
2answers
550 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: $...
9
votes
6answers
5k views

Example of use De Morgan Law and the plain English behind it.

I am currently reading "Discrete Mathematics and Its Applications, 7th ed", p.29. Example: Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer”. ...
9
votes
4answers
8k 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 ...
9
votes
2answers
346 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
5answers
47k views

Prove XOR is commutative and associative?

Through the use of Boolean algebra, show that the XOR operator ⊕ is both commutative and associative. I know I can show using a truth table. But using boolean algeba? How do I show? I totally have ...
8
votes
4answers
643 views

Is there a general effective method to solve Smullyan style Knights and Knaves problems? Is the truth table method the most appropriate one?

Below, an attempt at solving a knight/knave puzzle using the truth table method. Are there other methods? Source : https://en.wikipedia.org/wiki/Knights_and_Knaves
8
votes
2answers
339 views

When a lattice is a lattice of open sets of some topological space?

When a lattice $(L,\leqslant)$ is a lattice of open (or closed) sets of some topological space $(X,\tau)$? Which conditions have to be satisfied? We may assume that $X$ is $T_1$.
8
votes
1answer
122 views

If $2^\mu$ and $2^\lambda$ are isomorphic as boolean algebras, is it true that $\mu = \lambda$?

The content of this question is: Is what I am going to say correct? It is well known that given two cardinals $\lambda < \mu$ it might be the case that $2^{\lambda} = 2^{\mu}$. Even stronger, ...
8
votes
2answers
415 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 - $...
8
votes
1answer
162 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 ...
7
votes
2answers
6k views

All finite boolean algebras have an even number of elements?

This seems obvious but I wanted to check, since I don't see it mentioned anywhere. If we define a boolean algebra as having at least two elements, then that algebra has a minimal element (0) and a ...
7
votes
1answer
64k views

Question on essential prime implicants

I am having some trouble understand essential prime implicants. So if a minterm is not covered by another overlapping rectangle, then that is an EPI. However, if we make a K-map for $f(x,y,z)=xy+xz&#...
7
votes
4answers
417 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 $...
7
votes
2answers
88 views

For every cardinal $\kappa$ does there exist a Boolean algebra that has exactly $\kappa$ many ultrafilters?

For every cardinal $\kappa$ does there exist a Boolean algebra that has exactly $\kappa$ many ultrafilters? By Jech's Exercise I.7.25, I know that a Boolean algebra has at least as many ultrafilters ...
7
votes
1answer
333 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
754 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 ...
7
votes
2answers
254 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 ...
7
votes
0answers
91 views

Stone Duality: What are $\sigma$-Algebras Dual To?

Stone duality, one of many dualities between certain lattices and certain topological spaces, asserts that there is a contravariant categorical equivalence between the category $\text{Bool}$ of ...
6
votes
4answers
1k views

Why, logically, is proof by contradiction valid?

How does proof by contradiction work logically? Normally in a proof we might have a true premise leading to a true conclusion, i.e. it is true that $T \rightarrow T$. But then how does proof by ...
6
votes
6answers
10k 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 ...
6
votes
4answers
623 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?
6
votes
2answers
516 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
6
votes
3answers
438 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
202 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
4answers
3k views

Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.

I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$". Regarding this ...
6
votes
3answers
2k 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
2answers
112 views

Are there products in the category of $\sigma$-algebras and (reversed) $\sigma$-homomorphisms?

Let $\mathcal{A}$ be a $\sigma$-algebra on a set $X$, and $\mathcal{B}$ be a $\sigma$-algebra on a set $Y$. A map $h\colon\mathcal{B}\to\mathcal{A}$ is called a $\sigma$-homomorphism if $h(\emptyset)=\...
6
votes
4answers
396 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
1answer
751 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 ...
6
votes
2answers
296 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
2answers
307 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 ...
6
votes
1answer
521 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
295 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
95 views

Understanding the meaning of “soundness” and “completeness” in the context of Algebraic Logic

I'm reading this PDF as a further study from my Modal Logic course. I had no previous experience with algebraic logic before, so I'm having a bit of trouble understanding the exact meaning of ...
6
votes
1answer
639 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$. ...