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

126 questions
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$, ...
420 views

1k views

### Boolean Algebra, Simplification: Don't know the method used

Here's the Karnaugh map: The answer I should be getting from the Karnaugh should be: T = R ∙ (CGM)' I'm really not seeing how this was arrived at through any ...
4k views

### proof of functional completeness of logical operators

If I know that the set of operators {∨, & , ¬} is functionally complete, how do I go about proving/disproving the functional completeness of the following set of operators? a) $\{\vee,\neg\}$ b) ...
550 views

187 views

### Changing conjunction and disjunction in equivalent boolean functions.

I have some difficulties to prove that if two equivalent boolean functions contain only ∧, ∨ and $\neg$ than we can change ∧ to ∨ and vice versa and the result functions will remain equivalent. There'...
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 ...
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 ...
550 views

### Any two countable atomless Boolean algebras are isomorphic

How to prove that Any two countable atomless Boolean algebras are isomorphic. This is an exercise of Jech - Set theory book for which I have some difficulty.
476 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' direction....
143 views

### Why do I keep running into contradictions in this problem (Knights and Knaves variation)?

Edit: I've attempted to solve this another way and posted it as a possible answer. Hesitant to accept it, and would appreciate if anyone could go over it and confirm it's the way to go. There is an ...
514 views

### The completion of a Boolean algebra is unique up to isomorphism

Jech defines a completion of a Boolean algebra $B$ to be a complete Boolean algebra $C$ such that $B$ is a dense subalgebra of $C$. I am trying to prove that given two completions $C$ and $D$ of $B$, ...
127 views

3k 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 ...
202 views

### Is there a logic gate (NAND, OR, etc.) which forms a group under the set $\{0,1\}?$

Many of the binary logic operators satisfy algebraic properties like associativity, closure, and having an inverse. I was wondering if you could form a group, or any other algebraic structure using ...
13k views

### self dual boolean function

How many self-dual Boolean functions of n variables are there?Please help me how to calculate such like problems. A Boolean function $f_1^D$ is said to be the dual of another Boolean function $f_1$ ...
131 views

### FOUR-algebra - boolean algebra?

Belnap’s logic contains the the truth values 'true' ($t$), 'false' ($f$), 'unknown' ($\bot$) and 'paradox' ($\top$). Each of these is represented by a pair of bits: \begin{align} t &\rightarrow (...
732 views

### Cardinality of the set of ultrafilters on an infinite Boolean algebra

Let $\mathfrak B$ be a Boolean algebra with an infinite power $\kappa$. My question is how many ultrafilters does it have? $\kappa$ or $2^\kappa$? Or even smaller?
1k views

### How to write boolean expressions as linear equations

I want to convert a set of boolean expressions to linear equations. In some cases, this is easy. For example, suppose $a, b, c$ $\in$ {0,1}. Then if the boolean expression is: $a$ $\ne$ b, I could use ...