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

28
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
844 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$, ...
13
votes
0answers
407 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
6k 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
206 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
326 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
142 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
784 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
419 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
181 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
198 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
6
votes
3answers
496 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
161 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
266 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
181 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}_0 \ncong \mathcal{B}_1$. ...
6
votes
2answers
323 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 ...
5
votes
3answers
106 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
119 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
252 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
169 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
123 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
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
3answers
131 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, ...
5
votes
1answer
196 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
61 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
68 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
165 views

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

I have solved the equation like this: ...
5
votes
3answers
487 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
2k 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
166 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
96 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
152 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
221 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
201 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
102 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
420 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
1answer
101 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
2k 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
7k 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
271 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
2answers
203 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
4answers
5k 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
2answers
161 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
77 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
210 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
192 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
201 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
79 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 ...
3
votes
2answers
218 views

Is it possible to derive all the other boolean functions by taking other primitives different of $NAND$?

I was reading the TECS book (The Elements of Computing Systems), in the book, we start to build the other logical gates with a single primitive logical gate, the $NAND$ gate. With it, we could easily ...
3
votes
2answers
2k 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 ...