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
1answer
22 views

Boolean Algebra, Proving expression

I've been struggling to prove this expression literally all day please help. A'B + A'C + B'C = A'B + B'C
0
votes
2answers
23 views

Simplify expression in Boolean algebra

In Boolean algebra, I need to prove that $AB+AB'C+BC'=AC+BC'$ and $(ABC)'(A+B+C)=A'B'C'$ Are both the questions correct?
1
vote
1answer
39 views

Boolean Algebra- Simplification

I'm attempting to simplify this and don't know if I'm doing it right. This is the problem: (a+b+c')(a'b'+c) Attempted solution: ...
3
votes
1answer
61 views

Negation of XOR

I feel pretty confident with expanding an XOR, but when it is negated, it throws me for a loop a bit. The problem I am trying to prove: $$\overline{x_1 \bigoplus x_2} \bigoplus x_3 = \bar{x_1}\bar{...
0
votes
1answer
21 views

Write PQ' in the form A'+B

I'm trying to find the negation of the sentence "All domestic cars are good". The sentence can be rewritten as "If a car is domestic, it is good". if P then Q is the boolean expression - P'+Q. The ...
1
vote
0answers
55 views

Simplifying bitwise expressions

Using various methods it is possible to simply boolean expressions consisting of boolean operators and binary variables. In programming languages another closely related set of operators exists: ...
1
vote
1answer
76 views

Prove the following boolean identity using Consensus theorem.

I have been trying to prove it for last 4 hours but couldn't find a solution. Please help me. $$(A+B')(B+C')(C+D')(D+A')=(A'+B)(B'+C)(C'+D)(D'+A)$$ I solved and got the following answer. $$(A'+B)(B'...
1
vote
1answer
49 views

If $*$ a functionally complete logical operator then $tautology *tautology $ is contradiction.

Would anyone please give me a hint to prove that if $*$ is a functionally complete binary connective and $@$ is a symbol for tautology, we must always have $ @*@$ is equivalent to contradiction (I ...
1
vote
1answer
63 views

Free product of the powerset algebras of group orbits. Interpretation

I am trying to interpretate the following sentence in the context of measures on groups and algebras, from J. Pawlikowski on "The Hahn-Banach theorem implies the Banach-Tarski paradox" Let $F$ be ...
0
votes
2answers
23 views

Resolution of a Boolean Function

I have to solve this simple boolean function : $$f_1 * f_2 = (x_1 + x_2) * (!x_1 + x_3)$$ The solution is : $x_1*x_3 + !x_1*x_2$ Can anyone make a step by step solution because after getting : $$...
1
vote
1answer
37 views

All possible set operations between sets

I was looking for some sort of generalization on set operations between different sets, and how that number of operations increases as the number of set increase as well. It can also be thought as the ...
1
vote
4answers
36 views

Simplify the boolean function below by using algebra laws.

I've been stuck on this question for some time, if anyone happens to solve it please explain step by step. $$(A +B ) \times ( A' + C ) \times ( B + C )$$
3
votes
1answer
60 views

Intuition for power-set structure of finite Boolean rings

A course I am taking has started to introduce Boolean rings: rings where every element is idempotent. It was proved that every finite Boolean ring $R$ is isomorphic to a power set ring $\wp (S)$ for ...
-3
votes
1answer
64 views

Why are there two different notations for negation in boolean logic?

For the boolean variable $x$, there are two notations for its negation: $\neg x$ and $\bar x$. So why are there two different notations?
0
votes
2answers
74 views

Karnaugh map and Circuit of a full adder

I have the following task: The addition can be implemented by the rules 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10. Full addition requires carry-in and ...
1
vote
2answers
55 views

Boolean equation

$$\text{Solve for}\space{x, y}$$ $${a_1, a_2, a_3, a_4, b_1, b_2} \; \text{ - variables}$$ $$\left\{ \begin{aligned} {a_1}\&x \oplus {a_2}\&y &= {b_1} \\ {a_3}\&x \oplus {a_4}\&y ...
0
votes
1answer
36 views

Is there a proof for the FOIL method in Boolean algebra?

The FOIL method is the special case of multiplying algebraic expressions using the distributive law and is shown here: What does the proof for this look like using Boolean algebra?
0
votes
0answers
21 views

m-bit parallel adder needed using full adder

How many full adder is needed to construct a m-bit parallel adder? I have construct a 4-bitparallel adder with 4 full adders. but can the number be reduced?
0
votes
0answers
30 views

Need help on clarification on a boolean algebra/logic gate question.

The question asked on my homework. I have a question on my home work that is confusing me. I went through and made a truth table and found the all of the values corresponding to the minterms that ...
1
vote
1answer
19 views

Can you simplify this Boolean expression any farther?

I was working through a problem for a Computer Engineering course and i was given this logic function F(A,B,C,D) = ~A~BC~D + ~AB~C~D + ~ABC~D + ABC~D After ...
0
votes
0answers
29 views

An intuition connected with Heyting implication

Suppose $L$ is a bounded lattice and let $\Rightarrow$ be its Heyting implication, i.e. the operation defined in the standard way: $x\Rightarrow y$ is the largest object of the set $\{u\in L\mid u\...
0
votes
3answers
38 views

Boolean Algebra - $ABC+B'=AC+B'$?

I'm doing a bit of homework, and it says to prove or disprove the statement $XZ+X'Y'+Y'Z'=XZ+Y'$ If you do a truth table and take the sum-of-products, you can eventually simplify the equation down ...
1
vote
1answer
13 views

Help with Boolean expression simplification with $4$ variables.

I've simplified this expression and am unsure if it's completely simplified. If it can be simplified, can you provide me with the answer and the steps/laws taken to do so? Thank you. $y’(z+x)+z’(xw+x’...
2
votes
2answers
24 views

Simplifying 4-term Boolean Expression

I am given a pretty lengthy Boolean expression: $$(¬A ∧ ¬B ∧ ¬C ∧ ¬D) ∨ (¬A ∧ B ∧ ¬C ∧ D) ∨ (A ∧ ¬B ∧ C ∧ ¬D) ∨ (A ∧ B ∧ C ∧ D)$$ which I am asked to simplify. The solution should be: $$((¬D ∨ B) ∧ ...
0
votes
1answer
63 views

Binary to Gray code using XOR boolean expressions

I have a question which asks to design a circuit to convert from binary to gray code, using a boolean expression. Now I understand you have to use XOR to achieve this. And I understand that XOR ...
1
vote
1answer
24 views

I need prove a boolean function

In need to prove with boolean algebra that XOR complement (negado) is equal to XNOR but i cant do it, can you help me? !(!xy+x!y)=xy+!x!y how to prove it?
0
votes
1answer
40 views

How to solve binary equation which has mod?

Three messages in binary format are sent $$ a_0 a_1 a_2 a_3 $$ and coded in binary format $$b_0 b_1 b_2 b_3 b_4 b_5 b_6$$ Symbols $$b_0,b_1,b_2,b_3,b_4,b_5,b_6$$ are the coefficients of the Boolean ...
0
votes
1answer
31 views

How to prove that any Boolean function can be simulated only using AND gate and NOT gate?

I want to see how to prove the functional completeness of NAND gate, but all the materials in the web I have reached just relies on the fact that the set $\{AND,NOT\}$ is complete and shows how to ...
0
votes
1answer
21 views

Representing Boolean expressions in a truth table.

Right so I'm trying to understand truth tables in the context of digital logic. And paticularly with lettered boolean expresssions. Now I do understand truth tables, you have either true or false as ...
0
votes
2answers
45 views

How does one simplify this boolean expression?

(a + b)(b' + c')(a + b' + c) where b' = b not and c' = c not. I tried distributive because I'm not very good at applying the properties when multiplication is applied but I can with addition. (a + ...
0
votes
0answers
15 views

Do we assume a value to be true be considered as 1 in algebraic manipulation?

In my Digital Logics class, we are doing boolean algebra. In the case where $ a * b * c $ (a and b and c) can we assume either of those values to be 1? so can we say that $a * b * c = 1 * b * c$, in ...
0
votes
2answers
32 views

(P and(not(not P or Q))) or( P and Q) equals P

I've been trying to verify the condition above but I get stuck on the passage : $$(P \land (P \land \lnot Q)) \lor (P \land Q)$$ I don't know how to simplify it since there are two ands and a not Q. ...
3
votes
3answers
40 views

How to prove these two sets are identical?

This is more a question of the methadology one should use to solve these type of questions: Say there is a set $V \subseteq X \subseteq Y$ and $U \subseteq Y$ such that $$X \setminus V = U \cap X $$ ...
0
votes
0answers
20 views

Hypercontractivity Lemma

In the proof of the Hypercontractivity Lemma here http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture13.pdf (3.4) what does it mean to split $p$ into $r + x_n*s$, why can we do this?
0
votes
0answers
33 views

Complete atomic boolean algebras as coalgebras of some endofunctor on Set

I was hoping to use the fact that CABAs are powersets with extra structure on the morphisms to find an endofunctor $F:\text{Set}\to\text{Set}$ with $\text{Set}^{op}\simeq\text{Coalg}F$. I started by ...
0
votes
2answers
21 views

Disjunctive Normal Form with Minimum variables

I am trying reduce this DNF function to minimal variables. $f(a,b,c,d)=(ac’+c)(a’bc+d’)+(cd’+b)(cd’+c)+abd’+abc’d$ I have reduced to $ac'd+bc+cd'+abc'$ but I know it can be reduced down to $ab +ad'+...
3
votes
1answer
125 views

Uppercase E notation for sets?

In Jónsson and Tarski's (1951) paper Boolean Algebras with Operators, Part I from the American Journal of Mathematics, they write formulae such as $L_i = \underset{u}{\mathbf{E}} \, [u \in At^m \text{...
1
vote
1answer
23 views

Brackets in Boolean ALgebra Distributive Law

What is the purpose of the brackets in all the examples I've seen of the distributive law? Why are there no brackets when distributing an AND term and there are when distributing an OR term? Could I ...
0
votes
0answers
15 views

AB'+B'C' NOR only gates

a few days ago I had my midterm exams in Boolean algebra, and one question bugs me. The final answer of the question was AB'+B'C' (A and not B or not B and not C), and we were supposed to draw a ...
0
votes
1answer
24 views

Boolean Algebra x+y=0 proof

So I am having a problem solving this proof of Boolean algebra. I am trying to prove that if x + y = 0 then x = 0 This is what I have tried ...
0
votes
0answers
14 views

Relationship between nonnegative real semiring module and boolean semiring module

In nonnegative matrix factorization, one attempts to factor a matrix $\mathbf{X} \in \mathbb{R}_{\geq 0}^{m \times n}$ into matrices $\mathbf{Z} \in \mathbb{R}_{\geq 0}^{m \times k}$ and $\mathbf{A} \...
1
vote
4answers
43 views

How to use xor properly

I need to know how to use XOR properly on more than two variables. I have following example. a xor b xor c Now, the way i understand it is that: a xor b = a * not b + not a * b That part is ...
1
vote
0answers
13 views

A polynomial majority function

Let us introduce a boolean function $F(x_1,x_2,x_3,...,x_n)$, where $F=1$ when most of the variables $x_1,x_2,...,x_n$ are equal to $1$ and $F=0$ otherwise. This is called a majority function. The ...
1
vote
1answer
37 views

Can every countable Boolean algebra be embedded into $\mathcal{P}(\mathbb{N})$?

Can every countable Boolean algebra be embedded into $\mathcal{P}(\mathbb{N})$? And if so, is the same true for countable semi-lattices?
0
votes
1answer
25 views

how solve the boolean expression [closed]

so my question is prove the following relation and solve the boolean expression. i'm stuck. because usually i solve the question is not like this. i) AB+ABC+ABC=AB ii) Z(Y+Z)(X+Y+Z)=Z
0
votes
1answer
19 views

Why does the M AND Q term disappear?

Trying to solve a Boolean algebra expression which simplifies midway down to $$(Q \lor (M \land \lnot N \land \lnot G)) \land (M \lor N \lor G)$$ It seems the final result of the distribution ...
2
votes
2answers
31 views

Why does this Boolean absorption law work?

It is said that $x \land (x \lor y) = x$ and $x \lor (x \land y) = x$ but I can't see how. When I use distributive law on $x \land (x \lor y)$ I get $(x \land x) \lor (x \land y)$ which is the same ...
0
votes
1answer
34 views

Problem with transformation of Boolean expressions

Having some problem with beginner boolean algebra. Somehow I can't figure out these two problems. Show that LHS is equal to RHS: $wx + w'y + xyz = wx + w'y.$ Can't find a way to "remove" $xyz$. $zy'...
0
votes
2answers
39 views

How can I prove the following logic equation?

I want to prove the following logic equation in logic algebra $$ a \bar b \bar e f + \bar a \bar b ef+ ac \bar d \bar e + \bar a c \bar d e+ \bar b \bar c f + \bar b d f = ac \bar d \bar e + \bar ...
2
votes
1answer
66 views

Boolean model containing both confusion and junk

I'm doing a course in Equational Programming, and really new to these materials. So we got a specification for Booleans: ...