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

How can i turn the Boolean Equation pq+r into a switch circuit?

How can I turn the Boolean Equation $pq+r$ into a switch circuit? I have synthesized this and drawn the NOR gates circuit however I'm not sure how to go about drawing/constructing the switch circuit.
2
votes
1answer
55 views

Applying De Morgan's to express $pq+r$ in terms of NOR operator

In Boolean Algebras I have $pq+r$ which I think is the same as $(p+r)(q+r)$. Now, I need to use De Morgan's laws to synthesize this into the NOR form but I am not sure how to apply the laws here.
1
vote
1answer
46 views

Why is chosen for intersection instead of union?

Constructing a commutive monoid having idempotent elements (the underlying monoid of a Boolean ring) free over a set $X$, I arrive on a very natural way at monoid $M$ having the finite subsets of $X$ ...
0
votes
1answer
287 views

Zhegalkin polynomial Boolean algebra

I have to find the Zhegalkin polynomial of $ (x\rightarrow y)\rightarrow z $. Please tell me if this is right: my polynomial is of this kind $ a_{0} + a_{1}x + a_{2}y + a_{3}z + a_{4}xy + a_{5}yz + ...
2
votes
2answers
672 views

Proving hypothetical sylloligism (p implies q, q implies r, therefore p implies r) with boolean algebra

I'm trying to prove the hypothetical sylloligism using boolean algebra. We already have a solution using propositional logic, which relies on proof by contradiction. $(p \implies q) \wedge (q ...
0
votes
3answers
62 views

Terminology: algebras, sigma-algebras, complete algebras…

There are 2 things which create a lot of confusion in my mind. 1) I know that every sigma-algebra is an algebra. But not every algebra is a sigma-algebra. Put differently, it seems that ...
1
vote
1answer
41 views

AND using XOR and OR?

Is there a way to make an AND using only XOR and OR. I know that a XOR b = ab'+ba' but I have no idea how to proceed. Could it be impossible?
0
votes
2answers
93 views

How to simplify following boolean expression? A+A'BC+BC'?

please help I'm stuck. I'm trying to solve this. so far I have: a) a+b+c b) a+bc c) a+b d) a+b but for e) I can't progress further since I don't know how to deal with a'bc in this case. ...
0
votes
1answer
44 views

Finding conjunctive normal form of a Boolean polynomial

I have to find the conjunctive normal form of the following Boolean Polynomial : $(x_1+x_2+x_3)(x_1x_2+x_1'x_3)'$ I simplified this polynomial to get $x_1x_2'+x_1x_2x_3'$ for which i then formed the ...
-1
votes
1answer
42 views

Boolean Algebras

simplify: (1) $f= pq+r$ (2) $g=a+bc+a'bc'd$
2
votes
3answers
14k views

Boolean Simplification of A'B'C'+AB'C'+ABC'

My question is how do I reduce A'B'C'+AB'C'+ABC' (note that (') stands for a bar over the letter). To get (A+B')C'. I'm so lost just been trying to get it for awhile only using the 10 boolean ...
1
vote
1answer
45 views

Simplification of a boolean polynomial

I have to simplify the following Boolean polynomial using $x\land y$ = $xy$ and $x\lor y$ = x+y : $xy'+x(yz)'+z$ =$xy'+x(y'+z')+z$ =$xy'+xy'+xz'+z$ =$xy'+xz'+z$ My book gives the following ...
1
vote
2answers
185 views

Boolean Simplification (ABCD)' + ((CD)'(B+D)'

I have to simplify (ABCD)' + ((CD)'(B+D)' function using boolean algebra. I simplified it using a truth table and got ...
2
votes
1answer
96 views

A boolean algebra is complete if its stone space is extremally disconnected

I have the following proof, but I don't understand one of the steps: Theorem 4.4. A Boolean algebra is complete iff its Stone space is exlremally disconnected. Proof. Identify the given ...
1
vote
1answer
62 views

Semantic consequence

I'm studying refutation trees in computer science II, but I have a big doubt: Let $\Gamma, \Psi \subseteq F_m$ Is the following hypothesis true? $\Gamma \vDash \Psi \iff \not\vDash\{\Gamma,\lnot ...
1
vote
2answers
72 views

Boolean Expression simplification help

Hi I am new to the board. Taking a computer architecture course and I am having trouble understanding further simplification on a question I got on a previous quiz. When I type in the expression ...
1
vote
1answer
17k views

Convert boolean expression into SOP and POS

Convert the following expression into SOP (sum of products) and POS (product of sums) canonical forms using boolean algebra method: $(ac + b)(a + b'c) + ac$ Attempt at solution: $(ac + b)(a + b'c) ...
0
votes
1answer
30 views

Boolean Simplification for Kmap

Diclaimer: This is not a homework assignment, it's a practice sheet that already has answers provided and is not graded in any way, however the steps are not shown hence the question. I'm having ...
0
votes
1answer
33 views

Boolean algebra simplification.

I start with: $$\bar{A}\bar{B}\bar{C}+\bar{A}BC+A\bar{B}\bar{C}+A\bar{B}{C}=A\bar{B}+\bar{B}\bar{C}+\bar{A}BC$$ then I did: ...
1
vote
1answer
35 views

Boolean Function with ^ and or

Please provide feedback on my answer to this question. Question: Prove that not every boolean function is equal to a boolean function constructed by only using ^ and or. Answer: True, Suppose that a ...
5
votes
2answers
95 views

Boolean algebra question.

Is there a way to show that $$A\bar{B}C\bar{D}+D=A\bar{B}C+D$$ using the rules of boolean algebra? I tried several methods such as expanding D with $$D(D+\bar{D})$$ or adding $$D\bar{D}$$ to the ...
2
votes
1answer
64 views

How to solve this boolean algebra problem?

Given two expressions: $$A\bar{D}+A\bar{C}D +A\bar{B}C + ABCD = Y$$ and $$BD+A\bar{C}D=Z$$ is there a way to simplify this using the rules for Boolean Algebra? I tried different combinations, but if I ...
1
vote
1answer
31 views

Can covering be done on two elements?

The covering rule is: $$B \bullet (B+C) = B$$ and $$B+(B \bullet C)=B$$ So does it follow from this rule that: $$B \bullet A \bullet \bar{C} + B \bullet D \bullet\bar{F} = B \bullet ...
2
votes
1answer
58 views

Arrow's Impossibility Theorem Using Boolean Algebra

I am currently working on a research project which involves using Boolean matrices for the proof of Arrow's Impossibility Theorem and various other lemmas and results related to quasi ordered sets. In ...
3
votes
1answer
100 views

Boolean Least Squares semidefinite relaxation

So I'm working on the Boolean least squares problem that comes up a lot in circuit design. In its raw form, it looks like this, $$\phi = \min \operatorname{trace}(A^TAX) - 2b^TAx + b^Tb$$ s.t. $$X = ...
2
votes
0answers
89 views

Simplify Product of Sums

Similar question to: Boolean Algebra - Product of Sums I was given a truth table and asked to give the sums-of-products and the product-of-sums expressions. I reduced the sums-of-products ...
1
vote
1answer
42 views

Proving Boolean Functions

Please check my answer to this question and give me feedback . Question: Either exhibit 333 different boolean functions on the three variables p,q,r, or prove that there aren't 333 different such ...
0
votes
1answer
27 views

Boolean Functions with p,q,r

Please give me feedback for my answer to this question. Question: (1) Are the boolean functions $(p \land \neg q) \lor ( \neg r \land q)$ and $(p \lor \neg q) \land (r \lor \neg q)$ equal?. Explain ...
2
votes
3answers
125 views

Construct XNOR with only OR gates

Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND ...
1
vote
1answer
35 views

Boolean-like algebra

Suppose one had an algebra that that follows most of the laws of Boolean algebra (associative, commutative, distributive, identity, annihilator, idempotent, double negation, De Morgan) but does not ...
0
votes
1answer
60 views

A well-defined operation on measure algebra

Let $(X,\cal{M},\mu)$ be a measure space, and for $E,F\in \cal{M}$ write $E \sim F$ iff $\mu(E \Delta F)=0$. Let $\widetilde{\cal{M}}$ be the set of equivalence classes in $\cal{M}$ for $\sim$; for ...
1
vote
2answers
125 views

How to prove the divisors of 15 form a Boolean algebra

This from Exercise 3.1 in "A Beginner's Guide to Discrete Mathematics" Let B be the set of all positive integer divisors of 15, that is B = {1, 3, 5, 15}. Prove that B forms a Boolean algebra with ...
3
votes
1answer
93 views

Prove if Tautology, Contradicton, or Neither. Is my proof ok?

Determine whether $((p \Rightarrow q) \Rightarrow r) \Leftrightarrow (p \Rightarrow (q \Rightarrow r))$ is a tautology, a contradiction, or neither. If $p,q,r = (0,0,0)$ then $((p \Rightarrow ...
1
vote
1answer
98 views

Alternative to xor(A,B,C)

How can we make a comprehensive statement, which will correspond to the truth table of xor (A, B, C) by combining logical operators AND (&), OR (|), XOR (xor) and NOT (!)?
2
votes
1answer
212 views

Convert a boolean function into K-map

I would like to know how can I convert the following boolean function into a truth table and accordingly construct the k-map $$F = A'B'C'+B'CD'+A'BCD'+AB'C'$$ thanks in advance :)
0
votes
1answer
42 views

Number of non-increasing boolean functions of $n$ booleans, up to permutations.

How many non-increasing boolean functions of $n$ boolean variables are there? I don't want to count functions that ignore some of their inputs. If two or more functions differ only by permuting their ...
19
votes
0answers
839 views

Is this $really$ a categorical approach to $integration$?

Here's an article by Reinhard Börger I found recently whose title and content, prima facie, seem quite exciting to me, given my misadventures lately (like this and this); it's called, "A Categorical ...
2
votes
1answer
94 views

How to prove that linear functions cannot represent binary functions

Yesterday, I thought about representing boolean algebra as linear functions: For some vector space $V$ and for some $A, B \subset V$ such that $A \ne \emptyset \,\wedge\, B \ne \emptyset ...
1
vote
5answers
74 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
2
votes
3answers
66 views

Proving $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$.

How do I prove using boolean algebra that $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$? I can see it in the logic table and it is logical, but I can't prove it mathematically.
1
vote
1answer
44 views

Number of Positive Definite Binary Matrices

How may positive definite matrices (over finite field- $F_p$) are possible? What is the criterion in getting those?
5
votes
6answers
4k views

how to solve system of linear equations of XOR operation?

how can i solve this set of equations ? to get values of $x,y,z,w$ ? $$\begin{aligned} 1=x \oplus y \oplus z \end{aligned}$$ $$\begin{aligned}1=x \oplus y \oplus w \end{aligned}$$ $$\begin{aligned}0=x ...
1
vote
2answers
67 views

Assignment for discrete mathematics

How can I prove that not every boolean function is equal to a boolean function constructed by only using ∧ and ∨?.Need help in proving it.
0
votes
3answers
98 views

Discrete Mathematics (boolean)

Either exhibit 333 different boolean functions on the three variables p; q; r, or prove that there aren’t 333 different such functions $p$ $q$ $r$ $0 0 0$ $001$ $010$ ...
0
votes
1answer
193 views

prove that there does not exists a boolean algebra containing only three element

please prove that there does not exists a Boolean algebra containing only three elements .prove it with example so that i can understand easily.i cant understand the question and i could not tried to ...
0
votes
1answer
130 views

How can I simplify this boolean equation for the multiplexer a little further?

I've obtained a formula through cannonical representation, which is: $$A\cdot \overline{B\cdot S}+A\cdot B\cdot \overline{S}+\overline{A}\cdot B\cdot S+A\cdot B \cdot S$$ And I'm trying to simplify ...
1
vote
0answers
145 views

What are three possible ways to express the following Boolean function with eight or fewer literals?

F= A'BC'D + AB'CD + A'B'C' + ACD' I assumed that the question was asking for me to simplify. I placed the terms into a kmap and have gotten SOP F= A'B'C' + A'C'D + AB'C + ACD' or POS F= ...
2
votes
0answers
61 views

Finding the atoms of a Boolean Algebra

I have a homework question that asks me to find the atoms of the Boolean Algebra that contains 256 Boolean functions "such as F1(x,y,z) = x + y +z, F2(x,y,z) = x + xz, F3(x,y,z) = xyz+ xyz and so on". ...
1
vote
0answers
21 views

Logic subject-reductio ad absurdum

Can you solve this using method reductio ad absurdum? 1)A ↔ (¬ B v C) ¬ A ¬ B 2)¬(R∧ (S v T)) 3)R∧¬ T S ¬R∧ S
2
votes
5answers
156 views

Value of $(a=1) \wedge (b=1) \wedge (c=2)$ given $a=1$, $b=2$ and $c=2$

How would I solve the following question. Assume $a=1$, $b=2$ and $c=2$ what is the value of the following Boolean expression $(a=1)$ AND $(b=1)$ AND $(c=2)$ I am kind of confused because I know ...