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

5
votes
2answers
49 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 ...
-1
votes
1answer
58 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
20 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
137 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
42 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
7 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
66 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
39 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
61 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
25 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
20 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
27 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
30 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
34 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
54 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
46 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
51 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
68 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
41 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
63 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
31 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
44 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
30 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
22 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
44 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
12 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
71 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
17 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
25 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
50 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
13 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
26 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
25 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
57 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
42 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
20 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 ...
0
votes
0answers
20 views

Connection between Directed Acyclic Graphs and Boolean Functions

I am given a set of $n$ vertices and testing some properties over the set of all directed graphs over them (i.e. acyclicity and bipolarity). I already done this by generating every undirected graph ...
1
vote
2answers
68 views

Why cant AND and NOT represented only with IMPLICATION?

Can someone please explain why can't I use only implication to represent AND and NOT with proof as well? I know that I can represent OR simply by using implication. Was thinking if I could find ...
3
votes
0answers
83 views

Axioms as recreational mathematics

Before modern group theory, mathematicians studied concrete permutation groups: algebraically closed subsets of the set of all bijections on a set $X$ in which all inverses was included. This was the ...
0
votes
1answer
35 views

$f(x) = x$ or a , if $f(x)$ and $a$ is known find $x$ boolean algebra

I am new to boolean algebra. I am facing difficulty solving this problem: Given $f(x) = x \lor a$, for some $f(x)$ and $a$, deduce the value of $x$. Can someone provide me the solution with ...
0
votes
3answers
56 views

Designing a circuit to verify operation of an OR gate.

Consider the following image: I need to design a circuit that verifies the logical operation of the OR gate. In the above image, the LED will be on (f = 1) if the or gate is working properly. I can ...
0
votes
1answer
47 views

Are Boo and BooRng really isomorphic?

In ACC on the top of page 34, I read: The construct Boo of boolean algebras is isomorphic to the construct BooRng of boolean rings and ring homomorphisms. This contradicts my intuition since ...
0
votes
1answer
40 views

AND, OR, NOT, and creating turing complete programming languages

Suppose I have an arbitrary computing language, and the following holds: Let all constants be finite, and assume we are computing in binary. An arbitrary number of inputs, A, and outputs, B, can be ...
0
votes
1answer
44 views

Boolean algebra proof and cancellation law

I have a Boolean algebra with some elements $a,b,c$. I have to show this: $(a ∧ b) ∨ (a′ ∧ c) ∨ (b ∧ c) = (a ∧ b) ∨ (a′ ∧ c)$. Now I have done other such proofs before but this one I got lost in. I ...
2
votes
2answers
68 views

DNF Form of XOR Operator with N Arguments

I’m working on this problem: Explain how to express $p$ using the boolean connectives AND, OR, and NOT so that the resulting expression has length polynomial in $n$. $$p(x_1\cdots x_n) = x_1 \oplus ...