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
votes
1answer
52 views

boolean algebra simplification for x(1 +bc') + x'(b' + bc)

in this equation using boonlean algebra: X(1 +BC') + X'(B' + BC). can i simplify (1 +BC') = 1 and (B' + BC) = B' +C? i used truth table and they have the same result, but i do not know how to solve ...
0
votes
1answer
64 views

Boolean Algebra Syntax

Six alphabets, A,B,C,D,E, and F have to be arranged in six numbered positions(1-6). How many ways can you arrange them so that A is not in position numbered 1 , B a is not in position numbered 2 and C ...
2
votes
2answers
103 views

How to find the minimum expression(s) of a set of fixed-width bit fields?

If we define $x_1 x_2 \cdots x_n$ as a bit field of width $n$, and each element $x_i$ may be $0$, $1$, or wildcard $*$. A set of 4-width bit fields $\{0000, 0001, 0100, 0101\}$ can be aggregated ...
0
votes
1answer
48 views

Help with getting the right direction on a boolean algebra question

Need some help getting in the right direction for answering the following question: Prove the following property and interpret this in $\mathcal P \left ({V} \right)$: if $x+ \bar y=$ 1, then ...
5
votes
1answer
118 views

Independent families versus generators in boolean algebras

Let $\kappa$ be an infinite cardinal. A family $\mathcal{A} \subseteq \mathcal{P}(\kappa)$ is independent if, for all $A_1,\ldots,A_n\in\mathcal{A}$ and $i_1,\ldots,i_n\in\{0,1\}$, we have $$ ...
3
votes
1answer
71 views

Do all equational theorems of Boolean algebra not involving complementation also hold for all bounded distributive lattices?

Or we might ask the question in the negative: Do there exist equational theorems of Boolean algebra involving only the operations $\wedge,\vee$ and the constants $\top$ and $\bot$ that fail to be ...
1
vote
1answer
62 views

Where can I learn more about these two functions obtained from IFF and XOR?

Given a set $X$, write $\mathrm{heaps}(X)$ for the set of all finite heaps (or 'multisets', if you prefer) on $X$. Under this definition, it is well-known that if a binary operation $*$ on a set $X$ ...
4
votes
1answer
107 views

Can we convert this statement about sets into a statement of propositional logic?

A question was just asked here about proving $$A⊆(B∪C)⟺A\setminus C⊆B.$$ We can prove this statement directly, using the concepts of first-order logic. "Suppose $x \in A \setminus C$ and that ...
2
votes
3answers
104 views

Given $x \wedge y=\mathbf{F}$, how to simplify $x \wedge \lnot y$?

Given that the boolean expression $x \wedge y=\mathbf{F}$, how to simplify $x \wedge \lnot y$? Is the above question equivalent to the following question? Find z so that $\lnot(x \wedge ...
2
votes
0answers
47 views

Algebraization of attribute-value logic

Jürgen Wedekind ("Classical logics for attribute-value languages", can be googled up) has defined an attribute-value logic as a fragment of predicate logic. There are no predicates except for ...
0
votes
2answers
497 views

Can these nested if-then-else be turned into a boolean formula?

I have this logic statement: (A and x) or (B and y) or (not (A and B) and z) The problem is that accessing A and B are rather expensive. Therefore I'd like ...
2
votes
2answers
100 views

Boolean Algebra-Simplification Assistance Needed

I have to show that (!(P.Q) + R)(!Q + P.!R) => !Q by simplifying it using De Morgan's Laws. Here is what I did but I'm not sure it's right. (!(P.Q) + R)(!Q + P.!R) => !Q (!P + !Q + R)(!Q + P.!R) ...
3
votes
3answers
203 views

Existence of maximal boolean-algebra sublattice (preserving top and bottom) of finite distributive lattice

If I regard a modal logic as some sort of many-valued logic, a "modal operator" projecting into a classical propositional logic context could sometimes be useful. Such an operator would provide a ...
0
votes
2answers
240 views

The Rotate and Shift operations in a Finite Field

Do the Rotate and Shift operations in $GF_2$ have simple expressions in a finite field? The Rotate operation $ROT[x,n]$ left rotates by n-bits. So $ROT[(0,1,1,1),2]=(1,1,0,1)$. The Shift operation ...
0
votes
2answers
30 views

Boolean bit OR operation on a Finite Field

How can I express $x \vee y$ in $GF_2$? I know that XOR is $GF_2[x]+GF_2[y]$ and AND is $GF_2[x]*GF_2[y]$ for instance. But I cannot figure out bitwise disjunction. This may be because OR does not ...
1
vote
2answers
401 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
847 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')
4
votes
2answers
136 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 ...
2
votes
2answers
5k 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
132 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
68 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
2k 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
121 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
149 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
35 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
67 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
3k 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
208 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
168 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
59 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
241 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
72 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
242 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
87 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
180 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
220 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
143 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
424 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
376 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
216 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
100 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
210 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
94 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
96 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
2k 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
140 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
318 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
96 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 ...
1
vote
2answers
225 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 ...