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
16 views

More on a construction on two boolean lattices

Let $\mathfrak{A}$ and $\mathfrak{B}$ be (fixed) boolean lattices (with lattice operations denoted $\sqcup$ and $\sqcap$, bottom element $\bot$ and top element $\top$). I call a boolean funcoid a ...
1
vote
1answer
18 views

Boolean lattices vs boolean rings

Which kinds of theorems about boolean algebras are easier to prove with boolean rings (than with actual boolean lattices)? Give me at least one example, as an answer.
0
votes
0answers
12 views

Counting self dual functions

The dual of a function is defined as the same function with and/or operators exchanged .A function is self dual if dual of function and function itself are same.How many maximum self dual functions ...
0
votes
1answer
27 views

Simplifying a boolean expression without using sum-of-products

Yes this is for a school class, and no I'm not asking anyone to do my homework. This is from an example. I have a boolean algebra expression that I have to simplify. I also have the answer simplified ...
1
vote
1answer
25 views

Implement boolean function with OR-NAND and NOR-OR gates

This is the boolean function: F(A,B,C,D) = Σ (0,4,8,9,10,11,12,14) and so after using a K-map to minimize it, I came out with F(A,B,C,D) = C'D' + AB' + AD'. Now the other two parts of the problem were ...
0
votes
0answers
22 views

Boolean Algebra, simplify expression

I've been trying to simply this expression but all I have managed to do is get rid of a D'. I assume there must be more I can do but I can't find out what I'm supposed to do to it. If you can help me ...
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
36 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
52 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 = ...
0
votes
1answer
19 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
42 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
73 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. ...
1
vote
1answer
47 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
62 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
52 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
60 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
47 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
53 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
27 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
17 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
28 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
1answer
26 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 ...
0
votes
3answers
34 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. ...
2
votes
2answers
22 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
50 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
38 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
44 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
14 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
30 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
18 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
32 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
20 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 ...
3
votes
1answer
119 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 ...
1
vote
1answer
21 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
14 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
23 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
13 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
11 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
35 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?