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
3
votes
1 answer

Proving $(xyz)' = x'+y'+z'$

I'm trying to prove that $(xyz)' = x'+y'+z'$ using theorems/axioms. I tried this but I just want to make sure if its the correct route or if I've done something "illegal"/wrong. (xyz)' = [(xy)z]' by associativity = [(x*y)'+z'] by DeMorgan's…
user1766888
  • 623
  • 3
  • 12
  • 24
3
votes
4 answers

Simplify Boolean Algebra

How do I simplify the following expression with Boolean Algebra? Please show what you used to simplify so I can understand. $$ABC + AB'C' + ABC' + A'B'C'$$
katrina
  • 41
3
votes
1 answer

How do I simplify $\overline{(\bar{X} + Z\bar{Y} + Y\bar{Z})(\bar{X}+Y\bar{Z})}$?

$\overline{(\bar{X} + Z\bar{Y} + Y\bar{Z})(\bar{X}+Y\bar{Z})}$ The farthest I've gotten is DeMorgans: $X(\bar{Z} + Y)(\bar{Y} + Z) + X(\bar{Y} + Z)$ The answer should be $X\bar{Y} + XZ$, but I'm unable to get anywhere close to it. I tried foiling…
S. Coughing
  • 61
3
votes
1 answer

Another question about subalgebras of $2^{2^S}$

This is a follow up to my earlier question Is this a complete and/or atomic subalgebra of $2^{2^S}$? For some infinite set $S$, let $W:=\mathcal{P}(S)$ $B:=\mathcal{P}(W)$ $F:= \{p\in B: \exists s\in S\text{ s.t. }p=\{w\in W:s\in w\}\text{ or…
Jeremy
  • 529
3
votes
1 answer

Prove that (in a Boolean algebra) if $a + x = b + x$, and $a + x′ = b + x′$, then $a = b$

The proof should be built of the following postulates, for a Boolean Algebra: P1. The operations (+) and (·) are commutative. P2. There exist in B distinct identity elements 0 and 1 relative to the operations (+) and (·), respectively. P3. Each…
Jay M
  • 277
3
votes
4 answers

Difficulty understanding proof by contradiction

Here's my understanding of proof by contradiction based on what I've read and I've been taught. We show $\neg P \implies (c \land \neg c)$ is always true. This is done by assuming $\neg P$ is true. Then, we realize that $(c \land \neg c)$ is…
Serendipitous Epiphany
  • 432
  • 3
  • 15
3
votes
2 answers

Proof of Associativity in Boolean Algebra

I must prove the most basic associativity in boolean algebra and there is two equation to be proved: (1) a+(b+c) = (a+b)+c (where + indicates OR). (2) a.(b.c) = (a.b).c (where . indicates AND). I have a hint to solve this: You can prove that both…
Hazım Türkkan
  • 51
3
votes
1 answer

Implement using only XOR gates F=A'B'C'D+A'B'CD'+A'BC'D'+A'BCD+AB'CD

How can we implement the function: F=A'B'C'D+A'B'CD'+A'BC'D'+A'BCD+AB'CD without simplifying it and using ONLY XOR gates (not using AND/OR gates) ? NOT gates are usable too, since they can be implemented from an XOR and an entry with the value "1".
Iulia
  • 41
  • 1
  • 3
3
votes
3 answers

Simplifying the Boolean expression $A'BC' + AB'C + ABC' + ABC$

I have this Boolean to simplify. $\bar AB\bar C + A\bar BC + AB\bar C + ABC$ I checked the final answer here. It gives the final simplification is $B\bar C + AC$ but I am confused here : $\bar AB\bar C + A\bar BC + AB\bar C + ABC$ $\bar AB\bar C +…
test team
  • 133
3
votes
0 answers

Write $(b+d)(a'+b'+c)$ in both minimal and canonical sum of products form

Write the following expression in both minimal and canonical sum of products form $$(b+d)(a'+b'+c).$$ I made the truth tables for both and got the following: $$a'b'c'd + a'b'cd + a'bcd + abcd' + ab'c'd + ab'cd + abcd.$$ I also tried distributing…
Prabhjot Mattu
  • 31
3
votes
2 answers

Show that a finite Boolean algebra is made of its atoms

Let $\mathcal{B}$ a finite boolean algebra. Only using the calculus rules about logic operators: and ($\land$), or ($\lor$) and not ($\neg$), how do I prove that every element $p \in \mathcal{B}$ is equal to a disjonction of atoms ? Define an atom…
Julien__
  • 2,455
3
votes
2 answers

Prove $(x+yz)(y'+x)(y'+z')=x(y'+z')$ in Boolean algebra

How can we prove $(x+yz)(y'+x)(y'+z')=x(y'+z')$ in a Boolean algebra $B$?
Amreek Singh
  • 31
3
votes
1 answer

Proving functional completeness

There are two functions f(x,y,z) = x'yz + xy' + y'z' g(x,y,z) = x'yz + x'yz' + xy Are these functions functionally complete ? For first one, We can have f(x,x,y) = (x + y)' which is NOR and is known to be functionally complete so f is…
Zephyr
  • 1,163
  • 1
  • 15
  • 30
3
votes
3 answers

Boolean Algebra

There seems to be some discrepancy between my answer and the solution's. Can somebody please tell me what I have done wrong? Thanks! $$\begin{align} \left(A \lor B\right) \land \left(B \lor C\right) \land \left(\lnot A \lor C \right) & = \left(A+B…
jyim
  • 77
3
votes
2 answers

Show that the Boolean identity: $(a'b' + c)(a + b)(b' + a'c')' = bc$ holds

I am having a little trouble getting the result on the right-hand side. I keep on evaluating down to $abc$, instead of $bc$. Here is my work below: $(a'b' + c)(a + b)(b' + a'c')'$ $=(aa'b' + ac + bc + a'bb')(b' + a'c')'$ [as $aa' = 0$] $=(ac +…
J. Doe
  • 39
  • 1
  • 6
1 2 3
…
64 65