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

1
vote
2answers
366 views

Boolean Algebra simplification: $X=((AB)'C(A'+(B+C)'))'$

I've had two statements I need to simplify, and I'm not sure about my work: $X=((AB)'C(A'+(B+C)'))'.\quad $ With this one, do you apply DeMorgan's theorem to the interiors of the brackets and ...
1
vote
1answer
729 views

Boolean Algebra Simplification - In sum of products form

How would you simplify this expression? I've been struggling with it for a while, but seem not to be getting anywhere near the right answer. Y = (A' + BD + C'D)' (B'CD')
3
votes
2answers
124 views

Monomorphisms and epimorphisms in the category of Boolean algebras

A Boolean algebra is a ring with unity all of whose elements are idempotent. We regard a zero ring $0$ as a Boolean algebra. Let $\mathcal{B}$ be the category of Boolean algebras. A morphism in ...
3
votes
2answers
4k 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 ...
0
votes
1answer
112 views

How are boolean expressions converted to NOR expressions?

What kind of rules help to convert an expression into a 3 input NOR expression? Do all variables have to be of the form (a+b+c)' + (d+e+f)'? What happens if there is an expression that is just (a')' ...
1
vote
1answer
66 views

Deriving truth table from English description

I'm trying to check if my truth table is correct since it largely depends on further parts of a larger problem. Here is the English description: The controller will turn on the headlights under the ...
1
vote
1answer
1k views

Simplify the boolean equation using boolean algebra rules

If I have the boolean equation: H = M'CD' + MC + MC' + CRD I think I can combine so that it's H = M'CD' + M(C + C') + CRD Does C + C' go to simplify to zero? So, I'm left with H = M'CD' + CRD
5
votes
1answer
110 views

What is a (-1)-morphism?

So, I read the John Baez essay "Lectures on n-categories and cohomology" and I understand the notion of a (-1)-category" and a (-2)-category" and how to derive them. However, I'm not totally clear on ...
5
votes
3answers
136 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 ...
1
vote
1answer
31 views

If $G$ is a generic ultrafilter, why $(\exists a\in A)(a\in G)\leftrightarrow \Sigma A\in G$?

Let $B$ be a complete Boolean Algebra. Let $G$ be a generic ultrafilter of $B$, that is, such that for any dense $D\subset B$ we have $D\cap G\neq \emptyset$. Why for all $A\subseteq B,$ $\Sigma A\in ...
1
vote
1answer
64 views

Fourier transformations in Simon's quantum paper

I am reading this paper by Simon. This is one of the earliest quantum algorithm papers. In the paper he presents a routine starting at the end of page six. The first step runs a Fourier transformation ...
1
vote
1answer
2k views

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 ...
0
votes
1answer
167 views

boolean algebra: DeMorgan's law confusion

the following function should be put into table values: $$y = \overline{(a*b*d+c)}$$ So the first thing i am doing is using DeMorgan to get rid of the "whole-term-negation": $$y = (\tilde a + \tilde b ...
1
vote
1answer
157 views

boolean algebra: simplify $ a* b *d + \tilde a *\tilde c*d + b* \tilde c* d$

Simplify the following function(algebraically): $$y = a*b*d + \tilde a *\tilde c*d + b *\tilde c *d$$ the solution is: $$a*b*d + \tilde a * \tilde c * d$$ which i checked via karnaugh and also ...
0
votes
1answer
52 views

Larger circuit design for same boolean function?

I've designed this circuit with 4 logic gates, and did Karnaugh map's simplification and Quine McCluskey method. However I found out that actually my circuit design is already optimized and I can't ...
0
votes
1answer
36 views

Distinct Karnaugh Maps grouping?

I got a table truth with some minterns which I mapped to a Karnaugh Map, then I can see an obvious choice for grouping. But I'm wondering wether in this case is possible to do any other different to ...
2
votes
1answer
211 views

How to write boolean expression as linear equations 2

I just posted How to write boolean expressions as linear equations and asked about a simple example. Here's what we know so far: Suppose a,b,c,d,e ∈ {0,1}. if the boolean expression is: a ≠ b, I ...
0
votes
1answer
70 views

Simplifying a short Boolean expression

\begin{align*} A’B + A’B’C + ABC’C’ + AB’ + AB’C’ &= A’B + A’B’C + ABC’ + AB’ + AB’C’ \\ &= A’(B +B’C) + ABC’ + AB’(C’+1) \\ &= ??? \end{align*} I'm stuck after this. Please help me!!
3
votes
2answers
175 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 ...
4
votes
1answer
82 views

Ideal:Kernel :: Filter:?

I understand that the notion of a filter is in some sense dual to the notion of an ideal, at least in the context of Boolean algebras1. Let $f:{\mathbf A} \to {\mathbf B}$ be a Boolean algebra ...
2
votes
2answers
152 views

Is there a way to prove a boolean operator isn't universal?

In boolean algebra, I could prove an operator is universal by implementing a NAND or NOR gate with it. But is there a way to prove a boolean operator isn't universal? I would like to know a general ...
2
votes
1answer
174 views

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. ...
1
vote
1answer
127 views

Binomial expansion through combinations.

If you have $(a+b)(c+d)(e+f)$ how can you expand this? Someone was mentioning that you get different combinations so that you get $adf+ade+acf+ace+bdf+bde+bce+bcf$? Is that the full expansion? As an ...
0
votes
1answer
282 views

Reduce to sum of products

I'm given the equation $F = (x+w)z' + x(y+z) + xz$ The inverse I got is $F' = [(x'+z)*(w'+z)]*[(x'+y')*(x'+z')]*[x'+z']$ To start I would expand $F'= [x'w' + x'z + zw'+zz] * [x'x' + x'z' + y'x' + ...
1
vote
0answers
296 views

Understanding Sum of product and complete sum of product

I have a pair of problems, the first two of my homework, and I'm already unclear on how finding SOP and CSOP for them work. The first: E=xy(1+z)y' It seems like this just reduces to 0, since 1+z ...
3
votes
1answer
152 views

Infix to Postfix

4 + x / b - a + 5 AND x AND y OR p OR q What is the tree and the postfix of the expression above? I find it tricky because I am not sure if AND has higher precedence than the arithmetic operators, ...
0
votes
1answer
91 views

Is it properly applied the Quine McCluskey algorithm by this?

I'm writing some code for implementing the Quine McCluskey algorithm and I simply need to clear out if my logic for implementation is ok. I get some number of minterms and combine each of them so ...
3
votes
1answer
199 views

Proof of $(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge (Q\Rightarrow P))$

Hi I've been working through Applied Mathematics for Database Professionals and I'm stuck trying to proof this equivalence: $$(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge ...
0
votes
1answer
82 views

Multiply the number $(1001)_{2}$ by 3 digit number

I want to multiply the number $(9)_{10} \rightarrow (1001)_{2}$ by a 3 digit binary number. 1) How I can extract the boolean equations? 2) Make a circuit of it. so what I did is just see what ...
0
votes
0answers
89 views

Can a Karnaugh map be solved in more than one way?

So I understand for doing a simplification by a K Map I should group my 1's (or even 0's) in $2^n$ elements, always trying to grup as much elements as possible. And I can group even adjacent elements ...
2
votes
2answers
1k views

How to apply De Morgan's law?

If for De Morgan's Laws $$( xy'+yz')' = (x'+y)(y'+z)$$ Then what if I add more terms to the expression ... $$(ab'+ac+a'c')' = (a'+b)(a'+c')(a+c)?$$
0
votes
1answer
125 views

Can't simplify this boolean algebra equation

So I've got an expression I have been trying to simplify and have the answer but I can't figure out how to get to it... can anyone help me out? Equation: $(A\wedge \lnot B \wedge \lnot C \wedge ...
3
votes
2answers
273 views

Is it possible to derive all the other boolean functions by taking other primitives different of $NAND$?

I was reading the TECS book (The Elements of Computing Systems), in the book, we start to build the other logical gates with a single primitive logical gate, the $NAND$ gate. With it, we could easily ...
0
votes
1answer
89 views

Logic Circuit Question

1) Write the boolean expression after every GATE 2) Write the boolean expression of GATE 3 3) Try to simplify the boolean expression of GATE3 I need to know if what I did its right + your advice ...
2
votes
2answers
155 views

Boolean simplification, 5 variables

I'm currently learning for my maths exam, and in the part about boolean algebra I came across an exercise that I can't seem to solve. I probably only need the first few steps to get started. $$ (xyz ...
2
votes
3answers
194 views

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'$$
5
votes
5answers
8k 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 + ...
3
votes
1answer
75 views

maximal antichain

I don't understand the definition of Jech (set theory) for "maximal antichain". Let $B$ a boolean algebra and $A$ a subalgebra of $B$. $W\subseteq A^+$ is a maximal antichain if $\sum W=1$ and $W$ ...
0
votes
2answers
110 views

Why is $ab + bc + c\bar{a} = ab + c\bar{a}$ true in binary?

I was simplifying the equation of a logic gates problem and I realized that ab + bc + cā and ab + cā followed the same truth ...
1
vote
1answer
45 views

completeness and saturation

Let $B$ a complete Boolean algebra. Suppose, for $\kappa$ cardinal, that $B$ is not $\kappa$-saturated. Then there exists a partition $W$ of $B$. Because of completeness, we have $B=\sum W\in B$. So ...
5
votes
2answers
197 views

Which law of logical equivalence says $P\Leftrightarrow Q ≡ (P\lor Q) \Rightarrow(P\land Q)$

I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
1
vote
1answer
103 views

Isomorphism Subalgebra

Given, the unit interval $I$ endowed with the Lebesgue measure $\mu$, and let $A$ be the (Boolean) algebra of Jordan measurable subsets of $X$ with respect to $\mu$, (i.e. those sets that satisfying ...
8
votes
3answers
474 views

Rationale behind truth values

I originaly asked a question on Programmers.SE to know why $0$ was consider $\text{false}$ and all the other [integral] values were considered $\text{true}$. That was a huge debate and many said it ...
0
votes
2answers
45 views

Generalization of Boolean OR?

I have been looking at the Boolean OR function and Im trying to find its integral analogue. What I mean is: Boolean AND (x, y) where x and y are Boolean Values with 0 = False, 1 = True is equivalent ...
3
votes
2answers
375 views

Reducing Boolean expressions

Just learning mathematical proof writing and came upon this interesting question Writing an expression using logic. $$(P \land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P ...
10
votes
2answers
343 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: ...
2
votes
0answers
40 views

Inferring simplest method to convert bit array 1 to bit array 2.

Consider the set of all bit arrays of length $n$. Now consider the set of all 1-to-1 functions that map from this set to this set. Now select a single function out of the latter set. Is there any ...
3
votes
1answer
120 views

Boolean Algebra Transform

I am revisiting Boolean algebra after a long while. Can somebody help show me how to simplify the LHS to get the RHS? $$abc * a'bc + (abc)' * (a'bc)'\quad = \quad \;b'+c'$$
2
votes
1answer
64 views

Filters of Boolean algebras which are Boolean algebras

Looking at some filters generated by elements of a finite Boolean algebra I have the impression that many/most/all of them are by themselves Boolean algebras (at least I didn't stumble upon a ...
1
vote
1answer
5k views

How does it evaluate A XOR B XOR C?

I am trying to solve the following combination, ...