Mathematics Stack Exchange
Mathematics Stack Exchange

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.

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.

A Boolean algebra uses Boolean variables, typically denoted by capital letters, e.g. $A,B$, which can only take the values $0$ or $1$. Operators are $\land$ (conjunction), $\lor$ (disjunction) and $\lnot$ (negation).

For Boolean logic use the tag .

3083 questions
4
votes
2 answers

Is every quotient algebra of a Boolean algebra isomorphic to a subalgebra?

Is every (non-trivial) quotient of a Boolean algebra isomorphic to a subalgebra of that Boolean algebra? And conversely is every subalgebra isomorphic to a quotient algebra?
Andrew Bacon
  • 1,297
4
votes
1 answer

Negation of XOR

I feel pretty confident with expanding an XOR, but when it is negated, it throws me for a loop a bit. The problem I am trying to prove: $$\overline{x_1 \bigoplus x_2} \bigoplus x_3 = \bar{x_1}\bar{x_2}\bar{x_3} + x_1x_2\bar{x_3} + \bar{x_1}x_2x_3 +…
Tanner
  • 321
4
votes
0 answers

Simplifying bitwise expressions

Using various methods it is possible to simply boolean expressions consisting of boolean operators and binary variables. In programming languages another closely related set of operators exists: bitwise operators (on Wikipedia). These operators…
Peter Fisher
  • 41
4
votes
2 answers

Number of self dual functions and number of inputs for which self dual function is 1

I came across this slides which states following two theorems: Theorem There are $2^{2^{n-1}}$ different self-dual functions of $n$ variables. Theorem Let $f$ be a self-dual function of $n$ variables, and let $|f|$ be the number of inputs a for…
Mahesha999
  • 2,053
4
votes
1 answer

$\sim p$ ,$\sim\sim\sim\sim\sim p$ , and $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p$ . Which of these are equal?

I made an attempt on this question. Please guide me if its wrong. Consider the following boolean fuctions: $\sim p$ ,$\sim\sim\sim\sim\sim p$ , and $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p$ . Which of these are equal? $\sim p$ and…
Roneel Kumar
  • 83
4
votes
1 answer

Exercise 1.9 in Rotman's homological algebra: ideals in boolean rings

We consider the Boolean ring $\mathcal{B}X$ of subsets of $X$, with the operations of symmetric difference as addition and intersection as multiplication. One direction of part iii of the exercise then reads as follows: A nonempty subset…
H.Durham
  • 926
3
votes
4 answers

Why can't a Venn diagram constitute a proof?

I'm reading Boolean Algebra and Its Applications and come across this statement about Venn diagrams: It should be remembered that such diagrams do not constitute proofs, but rather represent illustrations which make the laws seem plausible. But I…
jds
  • 2,274
  • 3
  • 24
  • 35
3
votes
2 answers

Sum of Products (Boolean Algebra)

I am having real trouble getting to the corrects answers when asked to simply Sum of products expressions. For instance: Determine whether the left and right hand sides represent the same function: a) $x_1\bar{x}_3+x_2x_3+\bar{x}_2\bar{x}_3 =…
Nick
  • 489
3
votes
2 answers

Quotient of boolean algebra by an ideal

The homomorphism theorem states that every boolean ideal $I$ of a boolean algebra $A$ is the kernel of a boolean isomorphism. I'm reading a paper where the author presents a short proof of this theorem, saying that the following definition of…
Tarc
  • 509
3
votes
1 answer

Represent boolean OR opperator in non-boolean math notation

I'm trying to represent the boolean opperation OR in a regular formula, I am familiar with the boolean algebra notation, I came up with this (A+B)/(A+B) this works for all binary values except if both A=0 and B=0 is there a simple alternative that…
Hedinn
  • 133
3
votes
1 answer

Inverse of a Boolean Function

Assume that I have a multi-output Boolean function $f(x_1,x_2,x_3,x_4) = (y_1,y_2,y_3,y_4)$. Is there a direct way of computing the inverse, that is, $g$ such that $g(y_1,y_2,y_3,y_4) = (x_1,x_2,x_3,x_4)$? Naturally, I could construct function $g$…
kostaspap
  • 131
  • 1
  • 4
3
votes
2 answers

Negation bar meaning?

I know that the horizontal bar on top means it's a negation. But I've never encountered one over more than one term like this one: $\overline{\bar{x} + \bar{y}x}(y + \overline{xy})$ Is that equivalent to: ($\neg{(\bar{x} + \bar{y}x))}(y +…
Kevin Doyon
  • 283
3
votes
3 answers

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: ~(A + 0) Then couldn't I distribute the not: ~A + ~0 ~A + 1 1 What did I do wrong that got me to ~A = 1? Did I mess with…
gbe
  • 197
3
votes
1 answer

Boolean algebra is dense if and only if it has no atoms

I'm doing Exercise 11 from chapter 2 of "Introduction to Mathematical Logic" from Cori and Lascar. In this context, 'dense' means for all $a < b$, there's a $c$ with $a < c < b$. The solutions on the back of the book proceed as follows:…
atreju
  • 140
3
votes
1 answer

Full Adder boolean Algebra simplification

I have an expression here from the Full Adder circuit, used for binary addition. One equation used to make it work, is this one: $$C = xy + xz + yz \tag{1}$$ Now, the book transforms this equation into this: $$C = z(x'y + xy') + xy \tag{2}$$ In the…
Nafiul Islam
  • 579
1 2
3
…
64 65