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
46 views

Question about poset and boolean ordering, inf and sup

We have a poset $(X, \sqsubseteq)$, and we define operations $+$ and $\cdot$ by $x+y=inf(x, y)$ and $x\cdot y=sup(x, y)$ ($+$ can be seen as union in sets and $\cdot$ as intersection in sets). The ...
0
votes
3answers
829 views

Boolean-expression simplification F = [ AB ( C + (BC)' ) + AB' ] CD'

Basing on that problem. All I have in my solution is this: mystep1:[AB(C +(B' + C')) + AB']CD' mystep2:[AB(CB'+ CC') + AB']CD' mystep3: [AB(CB') + AB']CD' mystep4:[B(A+C+B') + ...
2
votes
1answer
431 views

Solving Boolean Expressions with Theorems

I'm having the hardest time wrapping my head around this stuff. This is a homework problem, one of many. I just need some help on what to do. ...
1
vote
0answers
210 views

Sum-of-products to product-of sums conversion

I need to convert $A'B'C'$ from sum-of-products form to product-of-sums form. I used a K-map and I'm not sure if the answer is $C' + AB' + A'B' + A'B$ or just $AB' A'B' + A'B$. I think that by ...
1
vote
2answers
49 views

Boolean simplification of $AB'(B' + C)$

Simplifying $AB'(B'+ C)$, then using the distributive property I know I would get $AB'B' + AB'C$ I am just confused as to how to simplify $B'B'$
0
votes
1answer
84 views

Correctness of answers and question about sup en inf

In $A=\{2, 3, 6, 12, 36, 72, 108\}$ we define the relation $R$ by $aRb$ if $b=a$, or $b=2a$ or $b=3a$. Q1: Draw the graph of $R$ and list which properties $R$ has. A1: The properties are: ...
0
votes
1answer
96 views

Condition for the boolean algebra of clopen sets to be extremely disconnected.

Let $X$ be a topological space and let $\Gamma \mathcal O(X)$ be it's boolean algebra of clopen subsets. For compact totally disconnected space, show that $\Gamma \mathcal O(X)$ is complete (as a ...
2
votes
1answer
79 views

Can a minimal representation of a Boolean Function be 1 or 0

After using the Karnaugh map to find the minimal representation of a Boolean function, my answer is 1. Is 1 a valid answer for minimal representation? If yes, what is the implication of a Boolean ...
2
votes
2answers
164 views

Order of operations for logic operations?

I have some code, that does a comparison to find how many of set of values fall within a range defined by a mean±sd, like this: ...
0
votes
2answers
76 views

How to prove boolean ordering question

Let $\sqsubseteq$ be the boolean ordering of $X$, so for every $x$ and $y$ applies $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v \sqsubseteq a$ and $w \sqsubseteq b$. Show that ...
0
votes
1answer
51 views

How do I solve this Boolean Algebra Problem?

Let A be an arbitrary but fixed Boolean algebra with operator $@$ and $*$ and $'$ and the zero and unit element be denoted by $0$ and $1$ respectively. let $x,y,z \in A$ if $a,y \in A$ such that ...
1
vote
1answer
57 views

Boolean Algebra: Explain why (M AND (NOT N)) OR (X AND M AND N) = (M AND NOT N) OR (X AND M)?

I have no idea how this is true, by what theorem, and I literally have been thinking about this for 3 hours now. I know it's really simple, but I just must not be in the right mindset to discover ...
2
votes
1answer
41 views

Need help for right direction simplifying boolean algebra formula

I have the following boolean algebra, where union is $+$ and intersection is $\cdot$ : $(x\cdot y)+((z+y)\cdot \bar{z})+y=y$ Is there a systematic way of doing this, or do you need to puzzle? My ...
-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
119 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
109 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
105 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
532 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
101 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
249 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
403 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
857 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
138 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
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
69 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
122 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
69 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
213 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
37 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
243 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
247 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
184 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
228 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. ...