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

29
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. ...
17
votes
2answers
877 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$, ...
15
votes
0answers
505 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 ...
11
votes
7answers
8k 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
210 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
340 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
143 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$ ...
8
votes
1answer
857 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) ...
7
votes
3answers
450 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 ...
7
votes
1answer
188 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 ...
6
votes
2answers
203 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
6
votes
1answer
131 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 := ...
6
votes
3answers
592 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
166 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
270 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
219 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
2answers
359 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
460 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 ...
5
votes
3answers
127 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
3answers
132 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
4answers
271 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
186 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
1answer
124 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 ...
5
votes
1answer
199 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
2answers
3k 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
75 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
81 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
2answers
237 views

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

I have solved the equation like this: ...
5
votes
3answers
622 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
3k 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
175 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
1answer
98 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
154 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
251 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 ...
5
votes
1answer
212 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 ...
5
votes
1answer
103 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 ...
5
votes
1answer
108 views

Independent families versus generators in boolean algebras

Let $\kappa$ be an infinite cardinal. A family $\mathcal{A} \subseteq \mathcal{P}(\kappa)$ is independent if, for all $A_1,\ldots,A_n\in\mathcal{A}$ and $i_1,\ldots,i_n\in\{0,1\}$, we have $$ ...
4
votes
6answers
3k 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 ...
4
votes
3answers
9k 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: ...
4
votes
2answers
301 views

Hypercube problem

$B$ is an n-dimensional hypercube, considered as undirected graph. Let $A$ be a subset of the vertices of $B$ such that $|A| \gt 2^{n-1}$. Let $H$ is a subgraph of $B$ induced by $A$. Prove that $H$ ...
4
votes
3answers
152 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, ...
4
votes
5answers
7k 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 + ...
4
votes
1answer
26 views

Going from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨~q)

I am confused on how to go from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨ ~q). I know they are equal because I plugged them into a truth table and all of the rows have the same values. What would be some ...
4
votes
2answers
252 views

Convert Circuit SAT to 3-SAT

I am trying to convert Integer Factorization to $3-SAT$. So far I managed to convert it to Circuit SAT, but I don't know how to make the final step. This is how it look for 3*3 multiplication: ...
4
votes
2answers
172 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 ...
4
votes
1answer
91 views

Can we convert this statement about sets into a statement of propositional logic?

A question was just asked here about proving $$A⊆(B∪C)⟺A\setminus C⊆B.$$ We can prove this statement directly, using the concepts of first-order logic. "Suppose $x \in A \setminus C$ and that ...
4
votes
1answer
219 views

Lindenbaum algebra is a free algebra

The following is a continuation of this question. I would like to prove that the Lindenbaum algebra is a free algebra. Hopefully I would like to hear hints on how to proceed in the 'right' ...
4
votes
1answer
206 views

Question about Boolean algebra and ultrafilters

In the following $B$ denotes a Boolean algebra and $\bar{x}$ is the complement of $x$. In my notes there is the following theorem: If $U \subset B$ is an ultrafilter on $B$ then for every $x \in B$ ...
4
votes
1answer
217 views

A Boolean function with total influence 1 must be a dictatorship

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly ...
4
votes
1answer
82 views

Ideal:Kernel :: Filter:?

I understand that the notion of a filter is in some sense dual to the notion of an ideal, at least in the context of Boolean algebras1. Let $f:{\mathbf A} \to {\mathbf B}$ be a Boolean algebra ...