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