# 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.

3,033 questions
Filter by
Sorted by
Tagged with
28 views

### Transform to CNF (conjunctive normal form)

I am trying to convert the following expression to CNF (conjunctive normal form): $\left(A\Rightarrow B\right)\Rightarrow\left(A\Rightarrow C\right)$ As my first steps I am removing the implications ...
67 views

### How to prove below two logic formulas?

Below 2 formulas are used for SM3 algorithm, first one is FF2 & second one is GG2. FF2(X,Y,Z) = $(X \land Y) \lor (X \land Z) \lor (Y \land Z)$ GG2(X,Y,Z) = $(X \land Y) \lor (\lnot X \land Z)$ ...
16 views

56 views

### What is Mathematical equation for (x * a) XOR (x * b) XOR (x * c)?

The question is; how to calculate (x * a) XOR (x *b) XOR (x *c)? Definitions are; x, a, b, c are all large hexadecimal numbers known by default. Solutions are; to ...
1 vote
90 views

1 vote
98 views

### Sublattices of rank n of the Boolean algebra and partial orders

Let $f(n)$ be the number of sub lattices of rank n the Boolean algebra $B_n$. I want to show that $f(n)$ is also the number of partial orders of $P$ on $[𝑛]$. I have read this question from Counting ...
39 views

### Countable generation of the Borel measure algebra

Consider the Borel sigma-algebra on $\mathbb{R}$ quotiented by the ideal of measure-zero sets (see definitions below). This forms a measure algebra. My question is whether this measure algebra is ...
55 views

### How to form a CNF of following formula [closed]

We got an exercise to make a CNF out of the following formula: $$G = ((A \vee \neg B \vee C) \wedge (C \vee D)) \vee ((A \vee \neg C) \wedge (B \wedge D))$$ I've tried to make an equivalent equation ...
50 views

### Is there a proof of Pratt's lemma on Chu spaces?

This isn't the typical Pratt's lemma. In his notes$^\color{magenta}{\star}$, Pratt claimed the following without proof: A simple case of interference is given by a Chu space having a constant row. If ...
77 views

1 vote
47 views

### Generalized boolean algebra structure on connected subset of euclidean space

This is a curiosity question that I've been grappling with as I've been reading more about lattice theory: Is it possible to endow some connected subset of $\mathbb{R}^n$ with a generalized boolean ...
28 views

### Boolean algebra derivative - expression independent of the value of certain variable

I'm given the following expression: $I=((xw \implies (y \bar z)) \Leftrightarrow x \bar w) \overline{(xy \bar z w)}$ This expression simplifies to $x \bar w \lor x \bar y \lor xz$. Now, I know that ...
29 views

### Logic function for $c=a-b$ where $a,b \in [0,31]$.

I need to create a switching function that performs the subtraction $c=a-b$ where $a,b \in [0,31]$. Now, my workbook has realized $c=a+b, a,b \in [0,15]$ using two functions (each with three arguments)...
21 views

### Does always exist a homomorphism from a power set Boolean algebra to the 2-element Boolean algebra $\mathbf2$?

Wikipedia states: "there may exist many homomorphisms from a Boolean algebra B to 2". I would be very grateful for any references to the literature that there always exists a homomorphism ...
2k views

### What am I doing wrong to get A = ~A

(Sorry if this is a bad question, I am new to boolean algebra) If there is a simple expression: ~A Couldn't I convert it to: ...
17 views

### Regular Open closure Commutes with Intersection

I have looked in Halmos and Engelking, which would be the natural places to look, and could not find anything related to this. I am trying to understand how the complete Boolean algebra of regular ...
30 views

### Expression for transitive matrices

I am trying to find a mathematical expression for the number of all possible transitive boolean matrices of order nxn. For example, T_1^n = n(n - 1)^3 + \frac{1}{6}n(n - 1)^4(n - 2) + \frac{1}{6}n(n ...
1 vote
30 views

### Converting from binary to RC(Radix Complement - Two's complement) and back from RC to binary

Assume we have a negative number X. To convert X from binary to Radix Complement we perform two's complement (Complement on the digits) + 1. Now to convert X from Radix Complement we can perform two'...
1 vote
145 views

### Prove that if x and y are real numbers, then max(x,y) + min(x,y) = x+y. [duplicate]

Prove that if x and y are real numbers, then max(x,y) + min(x,y) = x+y. [Hint: Use a proof by cases, with the two cases corresponding to x≥y and x<y, respectively.] Using hint, I supposed two cases ...
105 views

### Satisfiability in an Heyting algebra implies satisfiability in a Boolean algebra for propositional logic?

Let $\mathcal{L}$ be a propositional language and let $\text{Prop}(\mathcal{L})$ be the set of all the propositions of the language $\mathcal{L}$. Let $(H,\wedge,\vee,\rightarrow,1,0)$ be an Heyting ...
43 views

### Boolean XOR conversion- rewriting to XOR in simplifed form

I have a Boolean Expression simplified to: BC + AC + A'B'C' and get to this be rewriting: C(B + A) + A'B'C' I need to rewrite to (A + B) XOR C' I can check with a Truth Table and can show they are ...
38 views

### Every boolean algebra is a product of the binary boolean algebra.

I am reading 'From Peirce to Skolem: A neglected chapter in the history of logic'. There the author mentions that the Stone representation theorem 'says that every Boolean algebra is a subalgebra of a ...
1 vote
50 views

### Complete Boolean algebras and second-countability

In Wikipedia's article "Complete Boolean algebra, the following example is given: The Boolean algebra of all Baire sets modulo meager sets in a topological space with a countable base is ...
1 vote