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
12 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 ...
-3
votes
1answer
33 views

How to solve the following Boolean function? [on hold]

How to solve this Boolean function: $$( ( ( A + (A+B)')' + ( (A+B)' + B )' )'$$ I've derived the function from the following picture which is the NOR implementation of XNOR gate . If you want know ...
0
votes
3answers
19 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
5 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. ...
0
votes
0answers
26 views

Boolean Algebra - Simplify $A(C+D'B)+A'$ [on hold]

Need help simplifying this question $$A(C+D'B)+A'.$$ equals to $A'+AC+AD'B$ though I do not know where to go from here using the boolean simplification theorem.
2
votes
2answers
15 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
31 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 ...
2
votes
1answer
23 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
27 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
19 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
38 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
12 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
23 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
35 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

canonical to algebraic form with don't cares [closed]

How do I transform the canonical form of a logic expression to its algebraical equivalent? For example: $$ f(a,b,c) = \sum \{3,7\} = \not abc + abc $$ But what would it look like for: $$ ...
0
votes
0answers
16 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
30 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
17 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
85 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
17 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
21 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
8 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
41 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
10 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
29 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
24 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
18 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
23 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
33 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$. ...
0
votes
2answers
37 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
63 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: ...
0
votes
1answer
13 views

K-Map multiple representations

I have a K-Map for a given function and need to figure out the minimal form. This map involves don't-cares. My question is: Do I need to use the don't-cares in my minimal form. I will show you why I ...
0
votes
1answer
23 views

Disjunction as sum operation in Boolean Ring

Boolean ring is defined with operations of ring multiplication corresponding to conjunction or meet ∧, and ring addition to exclusive disjunction or symmetric difference (not disjunction ∨). I ...
0
votes
1answer
26 views

Prove System is Boolean Algebra

There is a mathematical system with 2 operators # and & and 4 different inputs/variables. The 2 operators are defined in the picture. Chart I need to prove that the system is boolean algebra and ...
0
votes
1answer
18 views

Simplify Boolean Expression Given Truth Table

Truth Table I have the truth table above which gives the minterm expression $$F = (\neg a \land \neg b \land c) \lor (\neg a \land b \land \neg c) \lor (a \land \neg b \land \neg c) \lor (a \land b ...
0
votes
2answers
22 views

Help with Boolean Expression Simplification

I know that $$(\neg a \land \neg b \land \neg c) \lor (a \land \neg b \land c) \lor (\neg a \land b \land \neg c) \lor (a \land b \land c )$$ and $$(\neg a \land \neg b \land \neg c) \lor (a \land ...
1
vote
2answers
37 views

How to show that $f(w,x,y,z)=wx'y'+xz+w'x'y$ isn't universal?

First, I will note that I don't need a formal prove. short explanation is enough. The only way I know to show that an operator isn't universal, is by showing that you can't implement $NOT$ with it. ...
0
votes
0answers
15 views

Design a circuit for a function

I am so confused on this problem. We are given a function $f$ and told to design a circuit that has four inputs labeled $b_3,...,b_0$, and an output $f$, where $f = 1$ if the 4-bit input pattern is a ...
0
votes
1answer
38 views

Sum-of-products for a function

I am not quite sure if I am understanding this correctly or not. Here is the problem: "Find the simplest sum-of-products form for the function $f$ using the don't-care condition $d$, where $f = ...
0
votes
0answers
25 views

What will be the answer to this K-Map?

I have a K-Map and I need to figure out which expression isn't equivalent to the provided K-Map. Here is the K-Map (and the question). We know that both options (a) and (b) are equivalent, and both ...
2
votes
3answers
45 views

Solving a boolean expression

I am trying to solve the following Boolean expression: $$a + \neg{a} b + \neg{a} \neg b c + \neg a \neg b \neg c d + \dots$$ The question asked was to use Boolean algebra in order to solve the above ...
0
votes
0answers
56 views

Can anybody explain me how to solve logical equations with using matrices?

Task:I need to find N, with which number of solutions is 32. \begin{cases} (X_1 \land X_2) \oplus (X_1 \land X_3) \oplus (X_2 \land X_3) =X_1 \land (\lnot( X_2 \land X_3)) \\ (X_2 \land X_3) \oplus ...
0
votes
0answers
31 views

On a theorem concerning free Boolean algebras

In Sikorski's book "Boolean Algebras" (3rd edition), p. 42, one finds the following theorem: In order that $\mathfrak{A}$ be a free Boolean algebra with $n$ free generators, it is necessary and ...
0
votes
1answer
56 views

Is it possible to solve such system of Boolean equations?

During a discrete mathematics test I got this question. I did not see it in my course and I am baffled, because I don't even know from where to start. All I found on google for such subject were ...
0
votes
1answer
30 views

What is the value of 0 XNOR 1 XNOR 1? [closed]

We know that for 3 variables $(A=0,B=1,C=1)$, $f_1 = (A \mathop{\text{ XNOR }} B \mathop{\text{ XNOR }} C) = 1$, since the input has even number of $1$'s. But if we were to do this step by step, $f_2 ...
0
votes
2answers
87 views

Why is $a \implies b$ is true when $a$ is false [duplicate]

I understand that: $True \implies True$, is true. $True \implies False$, is False. But why is it that $False \implies True$, is True. and $False \implies False$, is True. If $a$ is false I ...
3
votes
2answers
118 views

Intuition for orthogonality in $\{0, 1\}^n$

In the beginning of [Kanerva 1988] a boolean algebra over $$ \{0, 1\}^n $$ with bitwise OR and AND is introduced. Example for bitwise OR: $$101 + 001 = 101$$ Example for bitwise AND: $$101 * 001 = ...
0
votes
1answer
31 views

Adjust the result of a boolean expression

I need to solve this in boolean algebra: $$B(A+(B'+ A)')$$ Here is my attempt: $$B(A+(B'+ A)')=B(A+(BA'))=B((AA')+(AB))=B(0+AB)=B(AB),$$ and the result should be just $B$. Should I just decide ...