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

0
votes
2answers
178 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
187 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
26 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
116 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
85 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
64 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
44 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
78 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
58 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
71 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
83 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
153 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
108 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
37 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
31 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
70 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
38 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
46 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
29 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 ...
2
votes
0answers
40 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
98 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
1answer
167 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
64 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
29 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
2k views

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

I'd like to simplify the following expression "xy + x'z + yz": ...
0
votes
1answer
36 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
43 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
78 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
85 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 ...
1
vote
2answers
89 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 ...
4
votes
0answers
126 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 ...
1
vote
3answers
236 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
48 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
65 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
149 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
230 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 ...
6
votes
1answer
111 views

Boolean algebra gives rise to a ring

There is a well-known result that every boolean algebra $(R,0,1,\land,\lor,\neg)$ can be made a boolean ring by defining $$x\cdot y=x\land y\qquad\text{and}\qquad x+y=(x\land\neg y)\lor(y\land\neg ...
0
votes
0answers
50 views

consider a base 16 adder how to modify the adder so that it can perform a base 8 addition

Consider a base $16$ adder. How can I modify the adder so that it can perform a base $8$ addition? I expect this question will appear in my exam tomorrow; if anyone can give me a hint or a solution, ...
0
votes
0answers
21 views

unique children of a point in a boolean lattice

I am working with two-element boolean algebra, e.g. points composed of strings of $0$s and $1$s and bit-wise $AND$ and $OR$ to find maxima and minima. In the domain I'm working in, I need to assign ...
3
votes
1answer
88 views

Convergence of monotone boolean network in the worst case

I'm looking for (upper bound) convergence of increasing monotone boolean network (network composed only with OR, AND, identity ($f_i(x)=x_j$) functions) in asynchronous updating mode. It means that if ...
0
votes
1answer
73 views

Number of bit operations in nxn zero-one matrix boolean product

I was reading transitivity closure from the book Discrete Mathematics and Its Application by Kenneth Rosen It says that in the boolean product of nxn zero-one matrix, there are $n^2(2n-1)$ bit ...
0
votes
1answer
26 views

What is meant by $AB$ in boolean algebra?

I am endeavoring to teach myself Boolean Algebra. Oh what fun! From the questions I've read on this site, one of the most common notations I've seen is $AB$ (examples: here, here, and here). Problem ...
0
votes
1answer
58 views

consider a base-16 adder. explain how to modify the adder so that it can perform a base-10 addition

consider a base-16 adder. explain how to modify the adder so that it can perform a base-10 addition I found this when I searched in Google but not understand please guide me to understand this ...
2
votes
1answer
71 views

How to simplify Boolean expression: $(C'B')+(CB)$

I'm very weak in math and logic, and currently tried doing K-map, and got this as result: $$(C'B')+(CB)$$ My question is, can this be further simplified? I tried it myself, but I got $0$ (False). ...
3
votes
1answer
57 views

Boolean algebra with measures

Let $A,B$ be two Boolean algebra with measures $m,p$ thereon, respectively such that the measure algebra $(A,m)$ is isomorphic to the measure algebra $(B,p)$. Suppose that we have two isomorphic ...
1
vote
4answers
921 views

Simplifying P AND (P OR NOT Q)

How can I simplify this? I've tried invoking Demorgan's Law and I get P AND (NOT (NOT P AND Q)) but I can't seem to simplify this further. The answer is P, but how can I prove this?
2
votes
1answer
153 views

Stone Representation Theorem

Given two Boolean algebras $A$ and $B$ such that $A$ is a subalgebra of $B$. What is the relation between the Stone space of $A$ and the Stone space of $B$. The question maybe silly but I am getting ...
0
votes
1answer
46 views

Getting sum of products from products of sum

I need to write the following Boolean expression in the form of sum of products $F(A,B,C,D)= (A+B+C+D)(A'+B'+C+D')(A'+C)(A+D)(B+C+D)$ I just want to know how to deal with the missing letters. Is $ ...
0
votes
1answer
59 views

How many satisfying assignments are there in a set of 3-CNF clauses where no clause share the same variable?

Say I have a set of 3-CNF clauses $$\mathcal{S} = \{ x_1 \vee x_2 \vee \bar{x_3}, ~~x_4 \vee x_5 \vee x_6\}$$ where $\bar{x}$ is the negation of $x$. Each variable range over $\mathbb{Z}^2$. How ...