Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Questions regarding Boolean algebras as structures, or regarding functions defined from/to Boolean algebras fit into this tag very nicely. For Boolean logic use the tag propositional logic

learn more… | top users | synonyms

2
votes
2answers
23 views

simplifying boolean expression in minterm

i am trying to simply the equation and stuck. Sum symbol(2,4,6,7). It means $$ F = A'BC' + AB'C' + ABC' + ABC $$ $$ = A'BC' + AB'C' + AB(C' + C) $$ $$ = A'BC' + AB'C' + AB $$ After the last equation ...
0
votes
1answer
46 views

expanding boolean expression as maxterm

$$ F = A + B'C $$ The expression has bothered. I've tried to expand the expression in maxterm, however, I'm stuck on the $B'C $ part. My approach is like this $$ = A + (B'B) + (C'C) + B'C $$ $$ = (A + ...
0
votes
3answers
1k views

3 input XOR gate

I am just beginning in computer engineering and need help with a problem. I have to implement a circuit following the boolean equation A XOR B XOR C, however the XOR gates I am using only have two ...
1
vote
1answer
10k views

How does it evaluate A XOR B XOR C?

I am trying to solve the following combination, ...
1
vote
1answer
49 views

Reference for the fact: elements as union of atoms in a Atomic Boolean lattice [closed]

I need a reference to a book with the following statement: "In a Atomic Boolean Lattice every element is the union of the atoms under lie it". Does not matter if it is presented as a exercise.
1
vote
1answer
121 views

Consensus Theorem: Legal to use redundant terms to find more redundant terms?

When using the Consensus Theorem in Boolean algebra to minimize an expression, is it a legal move to find and add a redundant term to the expression and then use that term to find more redundant terms ...
1
vote
3answers
971 views

Boolean Algebra: Simplifying $\;xyz + x'y + xyz'$

Given the following expression: $xyz + x'y + xyz'\,$ where ($'$) means complement, I tried to simplify it by first factoring out a y so I would get $\;y(xz + x' + xz').\,$ At this point, it appears ...
0
votes
1answer
32 views

Basic Boolean Algebra Multiplication Question

I have the following term $$ t1: \overline {\overline{x1x2\Leftarrow\Rightarrow x1x3}\Leftarrow\Rightarrow x2x3} $$ which I already converted to this: $$ t2: ((x1x2\overline{x1x3} + ...
2
votes
1answer
49 views

Equivalent form of biconditional

I'm reading How to Prove It: A Structured Approach (Velleman) Second Ed. Doing all the end of chapter exercises for chapter 1 and having trouble on problem 5a which reads Show that $P ...
1
vote
1answer
36 views

The proof of that a → b is equivalent to ¬b → ¬a using algebraic identities by ArsDigita

I'm noob practicing with discrete math problems, and not sure if the solution ArsDigita provided for this one is correct or not: Prove that a → b is equivalent to ¬b → ¬a using algebraic identities. ...
1
vote
0answers
40 views

Monotonic operators in classical logic

Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
0
votes
1answer
35 views

Simple Boolean Algebra Question

I have the following term in front of me: $$(AB+AC+\overline BC+B\overline C)*(A+\overline B+C+D)$$ and just need to multiply the whole thing which should result in this: ...
1
vote
1answer
268 views

Understanding comparability in a partially ordered sets with Hasse diagrams

I'm doing a section on directed graphs and Hasse diagrams right now on partially ordered sets, and I'm trying to understand what it means for two elements in a Hasse diagram to be comparable. For ...
1
vote
1answer
35 views

Convert boolean expression to pos then nor only

I'm trying to convert a + xb + xyz to POS then to nor only. First I got, a'(x' + b')(x' + y' + z') by using the duality rule but then I get confused after that. Thanks.
0
votes
0answers
29 views

Find boolean function

Given $\mathbb{B} = \{true, false\}$, and function $f: \mathbb{B} \times \mathbb{B} \times \mathbb{B} \to \mathbb{B}, f(a,b,c) = a \land b \lor c,~ \forall a,b,c \in \mathbb{B}$. I want to find a ...
1
vote
1answer
156 views

Simplifying Boolean Function

I am in a computer class with Karnaugh Maps and one of the questions is X 'Y Z + X 'Y 'Z + 'X Y 'Z + X Y Z and I need to simplify it where ' means not so 'x means not x. I think the answer is X 'Y ...
2
votes
0answers
38 views

Solving equation set with boolean operators and very specific format

I have to write a program to solve a set of equations like the following (+ is XOR and * is ...
1
vote
1answer
3k views

Verify Demorgan's Law Algebraically

If $\overline X \equiv \text { not }X$, De Morgan's Laws are stated as: $ \overline{(A + B)}= \overline A\cdot \overline B$ $ \overline{(A\cdot B)} = \overline A + \overline B$ Verify the above ...
1
vote
1answer
64 views

Obtain the Boolean expression from the given circuit diagram

Currently having trouble understanding how to write out the boolean expression up to the exclusive or gate. Up to the third NAND gate I solved it to be AB+CD. But I get stumped on how to write out ...
1
vote
1answer
220 views

Is it possible to convert this expression into a NAND GATE Circuit?

I am trying to construct a logic circuit for the expression (NOT Q & P) OR R - using only NAND gates. I have tried this, can someone confirm if what I have done is correct? if not what do i need ...
1
vote
0answers
40 views

Coset state for non-abelian hidden subgroup problem

On page 14 of his classic paper, Quantum factoring, discrete logarithms and the hidden subgroup problem, Jozsa introduced a function $f$ for the non-abelian hidden subgroup representation of the graph ...
3
votes
0answers
62 views

A discrepancy in the total number of conjunctive normal forms and the number of distinct boolean functions.

Consider a set of truth literals $C$. The set $\{\text T, \text F\}^{\mathcal{P}(C)}$ is the set of all boolean functions over all subsets of $C$. This comes from the notation ...
0
votes
1answer
23 views

Proof of the following statement?

For one of the inclass problems, we had to prove the following statment using Properties of Boolean Algebra: xyz + x'y'z + x'yz + xyz' + x'y'z' = xy + yz + x'y' ...
1
vote
1answer
76 views

Gelfand duality restricted to the category of Stone spaces

It is well known that the category of unital commutative $C^\ast$-algebras is dually equivalent to the category $\mathbf{KHaus}$ of compact Hausdorff spaces. I have found that restricting the ...
1
vote
0answers
37 views

Product of binary Boolean operators

I'm interested in the set $\mathcal{P}_N$ of boolean functions of boolean variables $p_1, p_2, \ldots, p_N$ that can be written as products of operators of 2 variables only: $$ \phi(p_1, \ldots, p_N) ...
1
vote
1answer
56 views

Atoms in a Boolean algebra

I am trying to understand the concept of an atom in a Boolean algebra. To fix the ideas, let $X=\{a,b,c\}$ be a set, and $\mathcal{A}=\{\emptyset,\{a\},\{b,c\},X\}$ be one of the five possible ...
1
vote
0answers
129 views

Dual formula in propositional logic

There's something I don't understand in my course on propositional logic. In the case of x being a variable, the definition of its dual is x* = x. Right. However, further in the course, there's a ...
3
votes
1answer
92 views

Countable sum of atomic measures is atomic?

Let $(X,\Sigma)$ be a measurable space and $(\mu_n)$ a sequence of atomic measures defined on this space. Recall that a measure $\mu$ is atomic if for any measurable $A$ of measure $\mu(A)>0$ there ...
0
votes
1answer
38 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 ...
4
votes
2answers
286 views

A Boolean function with total influence 1 must be a dictatorship

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly ...
-2
votes
3answers
1k views

Boolean simplification A'B'C' + A'BC + ABC'

Gentlemen I need a hint to simply this expression since I'm quite rusty in my boolean algebra. A'B'C' + A'BC + ABC' I however have made thus far ...
-1
votes
1answer
45 views

How to reduce a Boolean Algebra expression/function

I need to reduce this expression: $$F(A,B,C,D) = A'B'C'D + A'B'CD + A'BC'D + A'BCD' + AB'C'D + ABC'D' + ABCD'$$ I also have the following solution: \begin{align*} &= \bar A \bar B D + ...
2
votes
1answer
37 views

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 ...
2
votes
1answer
5k views

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 ...
6
votes
4answers
114 views

Can this set of rules perform all Boolean operations?

I never worked in this field before, I just thought about this set of rules and never saw something similar before. I apologise if I don't use the right mathematical vocabulary for my question. ...
0
votes
1answer
61 views

Does $x(y+z)$ simplify to two variables in Boolean Algebra?

Question from the title. I'm just starting with Boolean algebra and my first set of exercises contains multiple problems which simplify to a variant of this. Am I "done" these problems, or can I still ...
2
votes
0answers
169 views

Coproducts and pushouts of Boolean algebras and Heyting algebras

I am having trouble of find a reference explaining how to compute coproduts and pushouts in the category of Boolean algebras and in the category of Heyting algebras. To be precise I am looking for ...
-1
votes
1answer
34 views

How to prove this equality?

I would like to prove the following using boolean algebra and not karnaugh maps but I'm stuck: CD' + CDAB' + C'D'AB' = CD' + CAB' + D'AB'
0
votes
1answer
18 views

Boolean Algebra Simplification

Can someone show me the steps of simplification for this Boolean expression? (!A!B!CD) + (!AB!C!D) + (!AB!CD) + (!ABCD) + (A!B!CD) + (ABCD)
4
votes
2answers
74 views

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

Mixed Boolean Arithmetic Identity

I'm trying to prove/derive the equivalence of the following formula: $$ x*y = (x \land y) * (x \lor y) + (x \land \neg y) * (\neg x \land y) $$ whereas $(\land, \lor, \neg)$ correspond to bitwise ...
3
votes
1answer
124 views

regular open (Boolean) algebra is complete

To prove that regular open (Boolean) algebra is complete, I tried to show following claim, but I couldn't. I saw this statement in Kunen's 'Set Theory' p.64 but in other books what I checked, ...
1
vote
1answer
51 views

Repeated XOR operations

Suppose you have a list of truth values with $2^k$ elements for any natural number $k$. If the first element of this list is denoted as $L(1)$, then we can come up with a new list by performing the ...
2
votes
1answer
82 views

Is there any $\sigma$-algebra where its elements are equal to a finite disjoint union of generators?

Let $X$ be a set and $\mathcal{B}$ be a family of subsets of $X$. Let $\Sigma$ be the smallest $\sigma$-algebra that contains all elements of $\mathcal{B}.$ Under which assumptions it holds that for ...
0
votes
1answer
37 views

Is it possible to check if this function is associative without checking all the cases?

Given a boolean function with the following table: $$\begin{matrix} {A}&{B}&{out}\\ {0}&{0}&{0}\\ {0}&{1}&{0}\\ {1}&{0}&{1}\\ {1}&{1}&{0} \end{matrix}$$ ...
0
votes
2answers
178 views

Proving equivalency using boolean algebra laws of logic

I have a question on my exam papers relating to proving equivalences using the laws of logic, but I'm not sure how to work it out as I don't have the solution paper. Can someone explain to me the ...
1
vote
2answers
498 views

Prove that if a and b are positive real numbers, then a + b $\geq$ ab

As the title states, the question is: Prove that if a and b are positive real numbers, then $a + b \geq ab$ For this proof, I'm supposed to prove by contrapositive. So, I get this as a general ...
0
votes
1answer
187 views

Simplifying Simple Boolean XOR Expression (!AB + A!B)

I am trying to simplify the 5 gate XOR from a A!B + !AB expression to a (A + B)!(A + B) implementation. How can I convert ...
0
votes
1answer
26 views

Find the numbers by XoR

I have 6 numbers M1, M2 and M3 and E1, E2 and E3 such that M1 xor M2 = E1 xor E2 M2 xor M3 = E2 xor E3 ...
0
votes
1answer
116 views

Triple XoR - Find relation between the numbers.

I have a = b^c; b = a^c; Is it possible to eliminate c and find a relation between a and b? I have 3 different ...