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.

25
votes
2answers
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$, ...
7
votes
4answers
420 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 $...
9
votes
5answers
47k views

Prove XOR is commutative and associative?

Through the use of Boolean algebra, show that the XOR operator ⊕ is both commutative and associative. I know I can show using a truth table. But using boolean algeba? How do I show? I totally have ...
6
votes
4answers
1k views

Why, logically, is proof by contradiction valid?

How does proof by contradiction work logically? Normally in a proof we might have a true premise leading to a true conclusion, i.e. it is true that $T \rightarrow T$. But then how does proof by ...
0
votes
2answers
274 views

Not every boolean function is constructed from $\wedge$ (and) and $\vee$ (or)

Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. Here is my solution, can I ask for a feed back on my solution please? $p∧q$ ...
36
votes
14answers
5k views

Still struggling to understand vacuous truths

I know, I know, there are tons of questions on this -- I've read them all, it feels like. I don't understand why $(F \implies F) \equiv T$ and $(F \implies T) \equiv T$. One of the best examples I ...
4
votes
4answers
4k views

Show that $ \{\lnot,\leftrightarrow\} $ is not functional complete

I have to prove that this set of logical operators is not functional complete - $$ \{\lnot,\leftrightarrow\} $$ i've tried implement this set by $ \{\rightarrow,\lor\} $ which is not functional ...
3
votes
2answers
651 views

'Algebraic' way to prove the boolean identity $a + \overline{a}*b = a + b$

For me, it is pretty clear that $a + \overline{a}*b = a + b$, because the first $a$ in the or will make sure that if the second term must be 'evaluated', $a$ will ...
15
votes
7answers
44k views

how many semantically different boolean functions are there for n boolean variables?

In short, this is an assignment question for a course I am taking - the exact wording is this: "Given n Boolean variables, how many 'semantically' different Boolean functions can you construct?" Now,...
5
votes
2answers
13k views

How to prove that a set of logical connectives is functionally complete(incomplete)?

How to prove that a set of logical connectives is functionally complete(incomplete)? For example, we are given this set: $ \left\{\begin{matrix} f = (01101001) \\ g = (1010) \\ h = (01110110) \\ \...
2
votes
1answer
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 ...
2
votes
2answers
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) ...
10
votes
2answers
550 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: $...
7
votes
2answers
6k 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 ...
17
votes
6answers
76k 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 + ...
6
votes
6answers
10k 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 ...
2
votes
1answer
1k views

Proof of for-all / there-exists “negation”?

I was recently playing around with delta-epsilon proofs for limits, which, when true, have the following form: $$\forall \epsilon > 0, \exists \delta>0 , p \implies q$$ Where $p = (\text{for ...
6
votes
2answers
517 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
4
votes
1answer
688 views

Is the minimal conjunctive normal form for positive formula unique? If so, how do you calculate it?

I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms. $$A$$ $$A \land (A \lor B)$$ The minimal example is $A$. Does ...
4
votes
4answers
29k views

Can someone explain consensus theorem for boolean algebra

In boolean algebra, below is the consensus theorem $$X⋅Y + X'⋅Z + Y⋅Z = X⋅Y + X'⋅Z$$ $$(X+Y)⋅(X'+Z)⋅(Y+Z) = (X+Y)⋅(X'+Z)$$ I don't really understand it? Can I simplify it to $$X&#...
0
votes
2answers
97 views

How to prove boolean ordering question

Let $\sqsubseteq$ be the boolean ordering of $X$, so for every $x$ and $y$ applies $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v \sqsubseteq a$ and $w \sqsubseteq b$. Show that ...
0
votes
2answers
176 views

Can AND, OR and NOT be used to represent any truth table?

there are $2^{2^n}$ truth tables for n inputs. We know that NAND and NOR can be used to represent every truth table in two inputs. What about three inputs. Is it possible or not? If not, why?
5
votes
1answer
88 views

Existence of a Boolean algebra with a unique ultrafilter in ZF

ZFC proves every infinite Boolean algebra has infinitely many ultrafilters. If every ultrafilter over $\omega$ is principal, then $\mathcal{P}(\omega)/\mathrm{fin}$ has no ultrafilter. Is it ...
1
vote
1answer
343 views

What is the symbol you'd use for Boolean results?

What I mean is that $\mathbb{CRZ}$ etc. are used for different classes of numbers, allowing me to do stuff like this: $$f:\mathbb{R}\to\mathbb{R}$$ $$f:x\mapsto 3x$$ But say I have an expression ...
1
vote
1answer
206 views

Proving $A+A'B=A+B$ without truth tables [duplicate]

How can I prove the Boolean algebraic rule $$A+A'B=A+B$$ without using a truth table? With the truth table, it is easy to see that the two are equal, but how can I prove it using lesser Boolean ...
0
votes
2answers
53 views

How do I prove if a set of operations is complete?

For example $\{\land, \lnot\}$ apparently forms a functionally complete set as it can form any logical expression. But I don't really know what this means or how you show it. Do we just show that ...
0
votes
2answers
7k views

Simplify Sum of Products: $\;A'B'C' + A'B'C + ABC'$ [closed]

How would you simplify the following sum of products expression using algebraic manipulations in boolean algebra? $$A'B'C' + A'B'C + ABC'$$
0
votes
1answer
4k views

simplify boolean expression: xy + xy'z + x'yz'

As stated in the title, I'm trying to simplify the following expression: $xy + xy'z + x'yz'$ I've only gotten as far as step 3: $xy + xy'z + x'yz'$ $=x(y+y’z) + x’(yz’)$ $=x(y+y’z)+x(y’+z)$ But I ...
114
votes
0answers
6k 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 ...
8
votes
2answers
342 views

When a lattice is a lattice of open sets of some topological space?

When a lattice $(L,\leqslant)$ is a lattice of open (or closed) sets of some topological space $(X,\tau)$? Which conditions have to be satisfied? We may assume that $X$ is $T_1$.
4
votes
1answer
18k views

Boolean algebra operation precedence?

In my discrete mathematics class we wrote down the truth table for some Boolean functions and in that table they go in the following order: ¬, ∧, ∨, →, ~, ⊕, |, ↓ So, I assumed that this is the ...
2
votes
1answer
689 views

Free boolean algebra

Consider the following definition: Let $X$ be a set and $e : X \mapsto A$ a mapping to a boolean algebra $A.$ We say that $A$ is free over $X$ (with respect to $e$) if for every mapping $f:X \...
0
votes
1answer
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'...
9
votes
4answers
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 ...
6
votes
4answers
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 ...
4
votes
1answer
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.
4
votes
1answer
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....
4
votes
3answers
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 ...
3
votes
3answers
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$, ...
2
votes
1answer
127 views

What is the “official” name for these boolean algebra rules?

In boolean algebra, we have the following simplification rules: $$P + (\ldots P \ldots) = P + (\ldots 0 \ldots)$$ and $$P \cdot (\ldots P \ldots) = P \cdot (\ldots 1 \ldots)$$ (Here $\;\ldots P \...
2
votes
1answer
223 views

How to Solve this Boolean Equations?

I have a Boolean Equations, described as below, $$\neg \mathbf{x} = \mathbf{M}\cdot \neg(\mathbf{M} \cdot \mathbf{x})$$ in which $\mathbf{M}$ is an $n\times n$ Boolean matrix, and $\mathbf{x}$ is an $...
5
votes
3answers
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 ...
5
votes
3answers
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 ...
5
votes
2answers
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$ ...
4
votes
1answer
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 (...
4
votes
1answer
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?
4
votes
2answers
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 ...
3
votes
2answers
613 views

Power set representation of a boolean ring/algebra

Let $R$ be a finite boolean ring. It's known that there's a boolean algebra/ring isomorphism $R\cong \mathcal P(\mathsf{Bool}(R,\mathbb Z_2))$. I'm trying to get a feel for this. The subsets of $\...
3
votes
3answers
216 views

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an ...
3
votes
1answer
200 views

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let's consider the following two aspects: 1.) IEP transforms at least ...