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

Ist it a tautology w/o truth table

AB + CD = (A+C)(A+D)(B+C)(B+D) is a tautology (checked with wolfram alpha) I have to prove this whith boolean algebra but I don't get it right. That'S what I have: AB + CD = A(C+D)B(C+D) AB + CD = ...
0
votes
1answer
27 views

Create a simple expression that is larger than zero if and only if a-b > 0 and c-d < 0

Ok, this is simple but I cant figure out a solution to it. I have four signals, a, b, c, d. I want to generate a signal when a-b > 0 and c-d < 0. This signal should be in the form of an algebraic ...
1
vote
1answer
526 views

Using induction to prove universality of gate

Can we use induction to prove gate(like NAND) is universal. If so how?
1
vote
1answer
60 views

Are ordinal spaces extremally disconnected?

The wikipedia article on ordinal spaces claims that they are not extremally disconnected: However, they are not extremally disconnected in general (there is an open set, namely $\omega$, whose ...
3
votes
1answer
47 views

Looking for an algebraic structure

I'm looking for the name of algebraic structures (in which the elements are partially ordered) with the following properties: Top element defined, bottom optional; Join defined for all elements, ...
1
vote
4answers
11k views

Boolean Algebra: Simplifying multiple XOR and XNOR

Is there any way to simplify a combination of XOR and XNOR gates in the following expression? I have tried multiple boolean theorems and I have not been able to simplify this any further: The ...
0
votes
2answers
181 views

Rewrite equivalent boolean function for p ⇔ q

Using only the operators ⇒ (conditional) and ∼ (negation) Rewrite p ⇔ q How should I go about this? Thanks
3
votes
1answer
319 views

Converting into CNF Form

If you have disjunctive clause comprising of n literals for example $(X_1\cup X_2\cup X_3\cup\cdots \cup X_n)$. where $n\geq 4$. How you can convert it into CNF (Conjunctive Normal Form) of $n-2$ ...
1
vote
2answers
49 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
1k 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
574 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
237 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
54 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
92 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: ...
1
vote
1answer
110 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
81 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
224 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
81 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
53 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
60 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
43 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
56 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
104 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
51 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
131 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
72 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
67 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
122 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
51 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
769 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
107 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
221 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
289 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
34 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
434 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
1k 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
156 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
7k 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
141 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
71 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
133 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
163 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
36 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
70 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
5k 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
255 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
180 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 ...