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
36 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
27 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
3answers
276 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 ...
6
votes
4answers
73 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
0answers
22 views

Characteristic polynomial of a 3-bit LFSR

So I am trying to solve part d of this question and using $IX - T$ I get the expression $(x+1) \oplus (X^2 + x + 1)$. I cannot solve it further. I am supposed to give a single polynomial. Can anyone ...
2
votes
0answers
78 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
24 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
12 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)
2
votes
1answer
68 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, ...
5
votes
2answers
56 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 ...
0
votes
1answer
60 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 ...
0
votes
1answer
23 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}$$ ...
5
votes
1answer
164 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 ...
1
vote
1answer
44 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 ...
0
votes
0answers
16 views

Drawing a precondition decomposition diagram to prove mutual exclusivity

I have a question on my exam papers relating to proving mutual exclusivity by composing a precondition decomposition diagram. The problem is I'm not sure how to actually construct the diagram. I've ...
1
vote
2answers
147 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 ...
2
votes
1answer
53 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
2answers
75 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 ...
0
votes
1answer
47 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
21 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
51 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 ...
0
votes
1answer
42 views

Solving a system of xor equations?

How can I solve the following system of xor equations? k0 ⊕ k2 ⊕ k3 = 0011 k0 ⊕ k2 ⊕ k4 = 1010 k0 ⊕ k1 ⊕ k2 ⊕ k3 = 0110 How can I solve this system to know the ...
0
votes
1answer
37 views

a bit complicated boolean simplification

I'm trying to simplify the following boolean expression: [(A' (C+D)')'] (A) + ( B (DC) + (D'C') + A + CB' What I got is A + (C+D) + B [(DC) + (D'C')] + A + CB' A(A+C) + D + B[1] + A +CD' A + D ...
0
votes
2answers
37 views

What's the name of this law in Boolean algebra?

I forgot the name of a law in Boolean algebra, and I can't think of how to ask this question to a search engine. It's the law that states that the disjunction of a variable with the conjunction of its ...
0
votes
1answer
58 views

Properties of distributive lattices and congruences.

Let $L$ be a lattice and let $a,b,c,d \in L$. Show that: $\theta(a,b) \subseteq \theta(c,d)$ iff $\langle a,b\rangle \in \theta(c,d)$ $\theta(a,b)=\theta(a \wedge b, a \vee b)$ Where $\theta$ is ...
4
votes
1answer
47 views

$\land,\lor$ and $\lnot$ determinate a functionally complete basis

I read that a Boolean algebra is defined by the binary operations $\land$ and $\lor$ and the unary operation $\lnot$ on a set such that $$\varphi\land(\psi\land \chi)=(\varphi\land \psi)\land ...
-2
votes
1answer
53 views

using boolean law to simplify equation

I need to use boolean laws to simlfy the folliwng: a) (A+B)(C+D)+(A+B)(C'+D')= what I did for a) (A+B)(C+D)+(A+B)(C'+D') (A+B)[(C+D)+(C'+D')) (A+B(C+B)+(A+B)(c'+D') (A+B(C+B)+(A+B)(c'+D') Am I ...
1
vote
3answers
73 views

Propositional Logic : Why is ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)

I was working my way through some Propositional Logic and had the following doubt : Why is this true : ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ ...
0
votes
1answer
56 views

The congruence class of a distributive lattice

I need to prove the next thing: For every non-empty ideal $I$ of a lattice $L$ consider the relation $\theta(I)$ defined by: $ \theta(I) = \{⟨a, b⟩ : ( \exists c \in I) a \vee c = b \vee c\}$ Prove ...
0
votes
2answers
70 views

how to prove boolean identities

I'm working on 2 boolean proofs (¬p⊕q)=(p⊕¬q=¬(p⊕q) <- I assume its equality law i'm not sure how to do this problem(I verified using truth table but I need to do algebraically) ...
0
votes
2answers
32 views

Boolean Algebra simplify

The question is to simplify $$xy'z+wxy'z'+wxy+w'x'y'z'+w'x'yz'$$ Using K-map, the answer is $wx + w'x'z' + xy'z$ However, the question wants me to simplify algebraically, stating laws beside. I ...
0
votes
2answers
18 views

If the following statements in which a, b, c,d are involved are simultaneously true, find the values of a-d

Can you please help me solve this ? This exercise says that we have the following statements: $$\lnot a \rightarrow b\tag{1}$$ $$\lnot a \Leftrightarrow c\tag{2}$$ $$\lnot b \rightarrow d\tag {3}$$ ...
2
votes
1answer
50 views

How to get from the statement $(AB'+C'A'+C'B')$ to equivalent statement $(AB'+C'A')$?

I've been working a Boolean algebra problem for probably 2 hours at this point, and while I arrive at a much simplified equivalent expression, there's a simpler one yet. Basically, I start out with a ...
0
votes
1answer
31 views

What is the universe of a sub algebra generated by $ \{(a \wedge b)\vee(c \wedge b') : a,c \in C\}$ ?

I need to prove the next thing, Let $B$ be a Boolean algebra and $C$ a proper subalgebra of $B$. Let $b ∈ B−C$. Prove that the set $ \{(a \wedge b)\vee(c \wedge b') : a,c \in C\}$ is the universe of ...
1
vote
0answers
35 views

Distributivity of lattices and prime ideals.

I need help proving that, if $L$ is a lattice with the property that for every nonempty proper filter $F$ and every ideal $I$ such that $F \bigcap I = \emptyset$ then there is a prime filter $G$ such ...
0
votes
1answer
23 views

If a set X has the finite meet property, then there is an ultrafilter such that X is a subset of it.

I need to prove that if $X \subseteq B$ is a set with the finite meet property, then there exists an unltrafilter $U$ of $B$ such that $X \subseteq U$. I know that the finite meet property means that ...
1
vote
0answers
34 views

Does the class of all periodic subsets of $\mathbb{Z}$ of peroid greater than $k$ form a field of sets?

We say that a subset $X\subseteq \mathbb{Z}$ is a periodic subset of $\mathbb{Z}$ of period $k$ if the set obtained from $X$ by adding $k$ to each element of $X$ is $X$ itself. Does the class of all ...
0
votes
1answer
52 views

$p\implies q = p'\vee q$ and duality

I'm reading Halmos's Lectures on Boolean Algebras. The title is a definition and he then also defines $p\iff q= (p\implies q)\wedge (q\implies p)$. Then the following: The source of these ...
0
votes
0answers
23 views

For every congruence of B, any equivalence class determines completely the congruence.

I am trying to prove that for every congruence $\theta$ of a boolean algebra $B$, any equivalence class determines completely the congruence $\theta$. My strategy is to prove first that the ...
0
votes
0answers
15 views

Problem in the correspondence between boolean rings and boolean algebra through characteristic functions

I was working on the relation between boolean algebras and boolean ring and that they are in fact, the same object. But I find something which seems to be incorrect, It's quite long and I try to give ...
0
votes
1answer
78 views

Discrete Math Predicate Logic

Consider truth assignments involving only the propositional variables $x_0, x_1, x_2, x_3$ and $y_0, y_1, y_2, y_3$. Every such truth assignment gives a value of $1$ (representing true) or ...
1
vote
1answer
25 views

Set of Numbers when added in any combination always produce unique result

What I'm looking for is a set of numbers that when added in any combination they always have a unique sum? Is this called something? I have searched on google for hours and I'm having a hard time ...
0
votes
1answer
26 views

A question about truth tables

Hello guys i have a question, I am trying to make a truth table which consists out of 4 variables F(A,B,C,D) = B'D + A'D + BD Is it true on the truth table when for example in B'D we have 0001 or ...
0
votes
1answer
76 views

Boolean algebra Simplification of “xy + x'z + yz” [closed]

I'd like to simplify the following expression "xy + x'z + yz": ...
0
votes
0answers
16 views

Homomorphism from a four-element Boolean algebra

I have a set like: $$ S = \{0, a, b, 1\} $$ I need to show all homomorphisms from a four-element Boolean algebra to another four-element Boolean algebra. How to find and write them?
0
votes
1answer
30 views

All subalgebras of eight-element Boolean algebra

Let's assume that we have a set: $$ X = \{a, b, c\} $$ Is it true, that a Boolean algebra of this set is like below? $$ P(X) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, ...
1
vote
1answer
28 views

Number of subalgebras of the power set algebra

Let $X=\{a,b,c\}$ and $\mathcal{P}X=\{\emptyset,X,\{a\},\{b\},\{c\},\{a,b\}.\{a,c\},\{b,c\}\}$. I can only see 4 subalgebras of $\mathcal{P}X$, namely: $\mathcal{F}_0=\{\emptyset,X\}$ ...
0
votes
1answer
62 views

Stone space of finite Boolean algebras

Is the Stone space of every finite Boolean algebra a finite discrete space (for every finite Boolean algebra is complete, atomic, and isomorphic to the power set of its atoms; and finite discrete ...
0
votes
0answers
53 views

Trying to prove Equivalency using Boolean Algebra

The question presented was to use boolean algebra to show that XY’Z + X’Y’Z’ + XY’Z’ + X’YZ’ ≡ XYZ’ + XY’Z + XY’Z’ + XYZ’ I've tried using various laws of Boolean algebra, but the answer that I ...
0
votes
0answers
22 views

Automorphism groups of Boolean algebras and atomicity

Let $A$ be a complete Boolean algebra, $B$ a complete Boolean subalgebra of $A$, $G$ a group of automorphisms of $A$. Finally let $Fix_G(A)$ be the subalgebra of $A$ that is fixed by every ...