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
votes
1answer
23 views

Simplifying Boolean algebra question

I'm not quite sure how to go about simplifying this boolean expression, any help would be great. X'Y'+X'Z'+Y'Z
0
votes
1answer
46 views

Converting large terms to disjunctive normal form (logic)

So hello everyone, I am doing some boolean logic and I have this exercise to convert the following term to DNF (disjunctive normal form), but it is so large that everything I try ends up being mega ...
1
vote
2answers
32 views

Simplify Boolean Algebra Expression

The problem is to simplify: $$ xz+\bar{x}y+zy $$ I have an answer key that says the answer is: $$ xz + \bar{x}y $$ I have no idea how they got this expression, though. The first thing I tried was to ...
5
votes
1answer
73 views

Is it possible to express “$P\leftrightarrow Q$” as a formula in $\to,\neg$ with $P$ only appearing once?

I want to write a propositional logic formula for the biconditional that only uses one side of the biconditional once in the formula. I expect it is impossible, but can anyone think of a proof? There ...
0
votes
1answer
31 views

Finding a simple function for a given Karnaugh diagram

I came across one question in which the Karnaugh map for some function is given and using it, i have to find a simple function which gets mapped onto that map. My Attempt: Corresponding to every ...
0
votes
3answers
26 views

How to define equivalency as NAND only function?

I am struggling a bit with boolean algebra. I need to represent equivalency as NAND only function. $(A * B) + (-A * -B)$ I am trying with the Morgan rule but I don't know if I can do that: $(A * ...
1
vote
2answers
56 views

Truth-functional completeness

Let the statement $?PQR$ be determined by the following truth-table. ...
2
votes
1answer
17 views

Need help proving that $ fRg \Leftrightarrow fg = f $ on $ B^{n} $ to $ B $ if and only if $ f(b_1,…,b_n) \leq g(b_1,…,b_n) $

I'm trying to gather my thoughts for proving the following claim: For $ fRg \Leftrightarrow fg = f$ on $B^{n}$ to $B$, show that $ fRg $ if and only if for any input values $ b_1,...,b_n $, we ...
1
vote
1answer
41 views

How can I rewrite this xor formula to generate cnf formulas

$$ \bigwedge_{c=1}^n\bigwedge_{i\epsilon S}\bigoplus_{r=1}^nX_{irc} $$ I have tried $$ \bigwedge_{c=1}^n\bigwedge_{i\epsilon S}\bigwedge_{r_1=1,r_2=1}^n(X_{ir_1c}\vee X_{ir_2c})\wedge(\neg ...
3
votes
2answers
70 views

Boolean Logic - Reduction - $a \vee (a \wedge b) = a$

How would I simplify / reduce the following equation using boolean identities/proofs? $$a \vee (a \wedge b) = a$$ So far I've used the distributivity identity and got $$(a\vee a) \wedge (a\vee b)$$ I ...
2
votes
3answers
59 views

Do brackets around negation signify negating the input or output - Boolean Algebra Logic Circuits

I know that $\overline{p + q}$ will result in the input to the logic gate being p, and q, and we can negate this by using an or gate, followed by a not gate, or we can just use a nor gate. However, ...
2
votes
1answer
43 views

Simplify this boolean algebra?

$$ \begin{align} &\lnot x_1(x_2\land\lnot x_3\lor x_3)\lor x_1(\lnot x_2\land\lnot x_3\lor x_2\land x_3)\\ &=\lnot x_1\land x_2\land\lnot x_3\lor\lnot x_1\land x_3\lor x_1\land\lnot ...
0
votes
3answers
30 views

If $A_1\cap…\cap A_n \neq \emptyset$, does $(A_1\cap…\cap A_n)^{c} =A_1^{c} \cup … \cup A_n^{c} = \emptyset$?

If I have some collection of sets such that $A_1\cap...\cap A_n \neq \emptyset$, then what happens if I apply the complement (denoted by superscript c) to both sides? i.e., $(A_1\cap...\cap A_n)^{c} ...
0
votes
2answers
64 views

Boolean algebra. For all x, y, and z in B, if x + y = x + z and x × y = x × z, then y = z.

In the statements below, $B$ is a Boolean algebra with $\times$ and $+$ for binary operations and ($\bar{a}$)is the complement of $a$. 4.) For all $x$, $y$, and $z$ in $B$, if $x + y = x + z$ and $x ...
1
vote
1answer
30 views

For all $a$ and $b$ in $B$, $(a \times b) + a = a$.

In the statements below, $B$ is a boolean algebra with $×$ and $+$ for binary operations. 3.) For all $a$ and $b$ in $B$, $(a ×b) + a = a$. This is what I have as an answer. Can someone confirm ...
0
votes
1answer
28 views

Why is this a boolean algebra

Let $A = \{a,b\}$. The $\mathcal P(A) = \{\emptyset,\{a\},\{b\},A\}$. Let $+$ be $\cup$, $\cdot$ be $\cap$, complement be set complement, $1$ be $A$, and $0$ be $\emptyset$. I need to explain why ...
1
vote
1answer
31 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.
0
votes
1answer
26 views

Applying De Morgans Laws to $a+bc+\overline{a}b\overline{c}d$ in terms of the NOR operator

I need to synthesize $f=a+bc+\overline{a}b\overline{c}d$ into the NOR form. Can I split this since I know that $a+bc=(a+b)(a+c)=\overline{\overline{a+b}+\overline{a+c}}$? I'm just not sure how to go ...
2
votes
1answer
44 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
41 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$ ...
1
vote
1answer
59 views

What is the number of self dual boolean functions?

The dual of a Boolean function $F(x_1,x_2 \dots x_n,+,\bullet)$, written as $F^D$, is the same expression as that of $F$ with $+$ and $\bullet$ swapped. $F$ is said to be self-dual if $F=F^D$. What is ...
2
votes
2answers
279 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 ...
1
vote
1answer
34 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
57 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
0answers
24 views

Simplifying conjunctive normal form

I have to simplify the following conjunctive normal form of a polynomial : $(x_1'+x_2+x_3+x_4)(x_1'+x_2+x_3+x_4')(x_1'+x_2'+x_3+x_4')$ I started off by using the fact that$(\alpha + \beta)(\alpha + ...
-1
votes
1answer
39 views

Boolean Algebras

simplify: (1) $f= pq+r$ (2) $g=a+bc+a'bc'd$
0
votes
1answer
32 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
vote
1answer
24 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 ...
0
votes
3answers
49 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
55 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
49 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 ...
0
votes
1answer
20 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
29 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: ...
5
votes
2answers
78 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
61 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
30 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 ...
1
vote
1answer
28 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 ...
0
votes
2answers
50 views

finding a boolean function with specific property

The problem I am trying to solve is: Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. My solution is $$\left(p\wedge\thicksim ...
2
votes
1answer
49 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 ...
2
votes
1answer
47 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
69 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
27 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
26 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
75 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
28 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
2answers
31 views

showing Boolean algebra equality

I have this exercise in my worksheet : Show that x (z ⊕ y) = xz ⊕ xy I reached this in solving it , but didn't reach the final equation x(z'y + zy') xz'y + xzy' please can someone show how
1
vote
2answers
61 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 ...
0
votes
1answer
54 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 ...
0
votes
2answers
27 views

Boolean function construction [duplicate]

I need some proof on this statement that not every boolean function is equal to a function constructed by only using ∨ and ∧. I need a boolean function that does not constructed using ∧ and ∨ which I ...
3
votes
1answer
85 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 ...