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
14 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. This is my first time posting on ...
0
votes
1answer
13 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
14 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
14 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
17 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
31 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
55 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) ...
-2
votes
1answer
39 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 ...
0
votes
2answers
35 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 ...
4
votes
1answer
41 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 ...
0
votes
1answer
45 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 ...
0
votes
3answers
57 views

finding a boolean function with specific property

The problem I am trying to solve is: Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. My solution is $$\left(p\wedge\thicksim ...
1
vote
3answers
56 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
26 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
1answer
27 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 ...
0
votes
2answers
27 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
17 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}$$ ...
0
votes
1answer
36 views

Single variable true or false statements

If I have a true or false statement S, depending on a varible x, is there some standard function or opperation in formal logic, that takes the statement S and the variable x, and outputs $1$ if ...
-3
votes
1answer
35 views

Exclusive or (XOR) proof [duplicate]

The question is to prove: X'⊕ Y = X⊕Y' = (X⊕Y)' State laws used (' meaning negation) Thank You
2
votes
1answer
36 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 ...
1
vote
0answers
32 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
0answers
23 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
19 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 ...
0
votes
1answer
34 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
19 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
11 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
68 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 ...
0
votes
1answer
601 views

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions $Q.S.U + (Q' + S').(R + V) + U.(R + V) + Q' + S.T.U$ $.$ = AND $+$ = OR This is what I have so far ...
1
vote
1answer
12 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
21 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 ...
-2
votes
0answers
5 views
0
votes
1answer
41 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
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, ...
0
votes
0answers
11 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?
4
votes
2answers
472 views

calculating number of boolean functions

I would just like to clarify if I am on the right track or not; I have these questions: Consider the Boolean functions $f(x,y,z)$ in three variables such that the table of values of $f$ contains ...
1
vote
1answer
21 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
41 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 ...
1
vote
2answers
64 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 ...
0
votes
0answers
29 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
13 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
16 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 ...
3
votes
0answers
78 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 ...
8
votes
2answers
242 views

The ring of idempotents

Let $R$ be a commutative ring. Then its ring of idempotents $I(R)$ consists of the idempotent elements of $R$, with the same multiplication as in $R$, but with the new addition $x \oplus y := ...
0
votes
1answer
367 views

Convert expression to NAND only

Endless youtube videos and reading through notes later I am yet again stuck. I have to covert the following to NAND only $$\bar{A}\cdot\bar{B}\cdot\bar{C} + A\cdot\bar{B}\cdot C + A\cdot B\cdot ...
1
vote
4answers
4k 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
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
2answers
1k views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ...
0
votes
3answers
47 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
36 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 ...