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

2,224 questions
Filter by
Sorted by
Tagged with
33 views

### Proving $\|x=y\|\cdot \|\phi(x)\|\le\|\phi(y)\|$ in Boolean valued models

This question relates to the Boolean algebra approach to forcing. Fix a complete Boolean algebra $B$. I'm writing $\|\sigma\|$ for the Boolean value of $\sigma$, where $\sigma$ is a sentence of the ...
42 views

### Prove that with n variables there are 2^2^n possible boolean functions

I have tried looking it up on the Internet; however, most of the results did not make sense to me. I know that the statement is true, but how do you mathematically prove it? For reference the proof ...
42 views

### Polynomial size Boolean circuit for counting number of bits

Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
20 views

### Proof of Demorgan's theorem by Principle of Duality. Is it valid?

I chanced upon a seemingly "too good to be true" proof of Demorgan's theorem for boolean algebra, however I'm not quite sure if it's valid. The principle of duality states that for a boolean algebra, ...
106 views

### Proving the identity: (A\B) ∪ (B\C) = (A∪B) \ (B∩C)

Trying to prove the following identity: (A\B) ∪ (B\C) = (A∪B) \ (B∩C) I worked algebraically on the expression on the left and reached: (A\B) ∪ (B\C) = (A∩B') ∪ (B ∩ C') = ((A∩B') ∪ B) ∩ ((A∩B') ∪...
43 views