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

Is it possible to express disjunction through conjunction and implication?

This question is about Boolean functions. Is it possible to express disjunction $x\lor y$ through conjunction $x\land y$ (or simply $xy$) and implication $x\to y$?
Evgeny Makarov
  • 81
5
votes
3 answers

How to convert between Sum Of Products and Product of sums?

I have a Boolean expression. we'll call it F. for instance, F = ab' + ad + c'd + d'. Assuming I did all the necessary steps too get F complement , i.e. F'. I got: F' = b'd + ac'd'. How do I get the Product of sums form of F?
Billie
  • 3,449
5
votes
3 answers

Simplify $A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$

How do you simply the following equation? $$X = A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$$ Here is what I did: $$\begin{eqnarray} X & = & A'B'C'D'+A'CD'(B'+B) + ACD'(B+B') \\ & =& A'B'C'D'+CD'(A'+A) \\ & = & D'(A'B'C'+C) \end{eqnarray}$$ Is…
clueless
  • 53
5
votes
2 answers

Definitions of Boolean algebras

One definition I find of a Boolean algebra in the book that I am following (V. Manca, Logica matematica, 'matematical logic') is determined by the binary operations $\land$ and $\lor$ and the unary operation $\lnot$ on a set such that…
Self-teaching worker
  • 5,058
4
votes
1 answer

How to know the boolean formula of a boolean function?

Suppose A binary boolean function is showed by a true table. How can I know the (simplest) boolean formula which is interpreted by that function?
zty
  • 43
4
votes
1 answer

identity and inverse/complement elements in a boolean algebra

In a boolean algebra, $0$ (the lattice's bottom) is the identity element for the join operation $\lor$, and $1$ (the lattice's top) is the identity element for the meet operation $\land$. For an element in the boolean algebra, its inverse/complement…
Tim
  • 47,382
4
votes
1 answer

Convert boolean expression into SOP and POS

Convert the following expression into SOP (sum of products) and POS (product of sums) canonical forms using boolean algebra method: $(ac + b)(a + b'c) + ac$ Attempt at solution: $(ac + b)(a + b'c) + ac$ $(a + b)(c + b)(a + b')(a + c) +…
larry21
  • 41
4
votes
1 answer

Functionally complete sets of boolean functions

A (finite) set of boolean functions $S=\{f_1,\ldots,f_n\}$ is called functionally complete if every boolean function (of a finite number of variables) can be presented as a finite composition of functions from $S$. For example, $$\{ f_1(x_1)=\neg…
user35603
  • 3,002
4
votes
4 answers

Why is $A' + AB' + B$ always true?

I only know how to prove that $A'+AB'+B$ is always true with a truth table, but not boolean algebra. I haven't found a suitable law to solve this. A little guidance is much appreciated~ Edit: Thank you so much all for your answers! Really helped…
Vero
  • 85
4
votes
1 answer

Label unlabeled Karnaugh map according to given truth table

Assuming I have an unlabeled but filled out Karnaugh map and a truth table with variables, what algorithm can I follow to find the correct label (variable) for each row and column of the map? Example:
Valentin Metz
  • 145
4
votes
1 answer

Can (x'y' + xy) be simplified?

I started with (AB' + A'B)' and ended up with (A'B' + AB). Is this all the farther I can go? I feel like this is always going to be true, but I'm not sure how to prove it algebraically.
Marty
  • 251
4
votes
1 answer

Is there a unique minimal expression for every boolean function?

Is there a unique minimal expression for every boolean function? I've heard that there are some boolean expressions for which the minimal form is not unique. What are the characteristics of this kind of functions?
Felipe Aguirre
  • 173
4
votes
2 answers

What is the proper name for the set of non-zero length-$n$ bit strings that start with $0$?

Consider a set $X$ which contains strings of $n$ bits. Each string starts with zero and it is non-zero string. For example n=3 $$ 001\\ 010\\ 011 $$ and for $n=4$ $$ 0 0 0 1\\ 0 0 1 0\\ 0 1 0 0\\ 0 0 1 1\\ 0 1 0 1\\ 0 1 1 0\\ 0 1 1 1 $$ Is there a…
seteropere
  • 627
4
votes
1 answer

Proving the family of constructible sets is a boolean algebra.

A constructible set is a finite union of locally closed sets. A locally closed set is the intersection of an open set and a closed set. I need to show that this is closed under finite unions and complementation to show it is a boolean algebra. The…
Devilo
  • 297
4
votes
1 answer

Definition of the boolean combination

Recently I have found such a thing like ,,finite boolean combination of open sets" (of a topological space). Unfortunatlety I haven't found anywhere the precise definition of such combination. Does anyone know where could I find it? The only thing…
pw1822
  • 698
1
2
3
…
64 65