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
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
22 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
20 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
67 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
16 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
39 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
30 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
19 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
24 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
39 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
16 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
42 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 = x_1(...
1
vote
0answers
33 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. $$\begin{array}{r|cccc}_{xy}\backslash^{wz}&00&01&11&10\\\hline00&0&\times&...
2
votes
3answers
47 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
63 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
39 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
62 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
39 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
97 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 don'...
3
votes
2answers
122 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
32 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 ...
2
votes
0answers
21 views

Expressing associativity as a Boolean SAT problem

Suppose we have a binary operation $B: S \times S \to S$ on a finite set $S$. We can encode $B$ as an array of $|S|^3$ Boolean values by setting $$ B_{ijk} \equiv \text{True} \quad \text{ iff } \quad ...
0
votes
0answers
35 views

Separation in Boolean algebras

I am looking for a separation-like result for Boolean algebras which is intuitively clear to me. Suppose that $B$ is a Boolean algebra whose set of positive elements $B^+$ does not have countable ...
0
votes
1answer
40 views

Number of self dual functions and number of inputs for which self dual function is 1

I came across this slides which states following two theorems: Theorem There are $2^{2^{n-1}}$ different self-dual functions of $n$ variables. Theorem Let $f$ be a self-dual function of $n$ ...
0
votes
1answer
31 views

PIT implies: In a boolean lattice, every filter can be enlarged to a maximal one

I am working through this proof of Herrlich's Axiom of Choice: $(1)\Rightarrow(2)$: How do you define the quotient lattice $B$ modulo a Filter? And why is the preimage of the maximal filter $\...
0
votes
0answers
47 views

Finding the principal disjunctive normal form (PDNF) of a Boolean expression

Find the principal disjunctive normal form (PDNF) of a Boolean expression $$((p\wedge q) \rightarrow r)\vee((p\wedge q)\rightarrow \neg r).$$ I tried by expanding it but I am stuck with the ...
1
vote
1answer
37 views

Boolean Algebra Product of Sums

I have a question to solve the following expression and get it in terms of product of sums (AB' + A'B)C And I tried taking the compliment of this ...
0
votes
1answer
61 views

Design a circuit for a light fixture

Design a circuit for a light fixture controlled by four switches, where flipping one of the switches turns the light on when it is off and turns it off when it is on and please explain your answer
1
vote
2answers
42 views

Basic boolean prove

I need to prove that given $$ f_1 = c + a'd' + bd' \quad\text{and}\quad f_2 = a'b'd' + a'bd' + ab'c + abd' $$ that $f_1 = f_2$. How do I manipulate $f_2$ to be exactly like $f_1$? I have tried a lot ...
-2
votes
1answer
67 views

How can i simplyfy this boolean equation?

Please help me simplify this formula by using boolean algebra rules: $F= x_1'x_2'x_3'x_4'+x_1'x_2'x_3x_4+x_1'x_2x_3'x_4'+x_1'x_2x_3x_4'+x_1x_2'x_3x_4.$ I know that the answer should be: $(x_1'x_3'...
1
vote
1answer
59 views

Questions about Boolean logic

Is there a systematic way to show that a set of Boolean operators is complete? Or is it more of an art than a science? Similarly, is there a systematic way to convert any Boolean expression in terms ...
1
vote
1answer
85 views

How to solve for a variable in xor equation?

I am very new to algebra with bitwise operators. If i have 5x ^ 7x ^ 9x = 22 is it possible for me to solve for x (if so how is it done)? Do normal algebra techniques hold (factoring out x etc.?) I ...
4
votes
1answer
40 views

How do I derive logical statements simply?

For example if I want to show the equation for $x \rightarrow y$, using truth tables it is the same as: $$(\neg x \wedge \neg y) \lor (\neg x \wedge y) \lor (x \wedge y)$$ Is there a methodical way ...
0
votes
1answer
44 views

how to draw a truth table for following logical expression?

It's a question in my assignment, which I don't really understand it. However, there is an example here. e.g. A computer uses the following logical expression to control a finger print scanner. F(...
2
votes
1answer
60 views

A generalized Boolean algebra gives rise to an implication algebra

A generalized Boolean algebra $G$ is relatively complemented distributive lattice with largest element 1. That is, an element $a\in G$ has a complement in any interval $[x\,,\,1]$ that contains $a$. ...