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
3answers
168 views

Simplifying a Sum of Products expression

I'm having some trouble with reducing the Sum of Products expressions for some questions on an upcoming exam. Below is the table (which is correct) for the first part of the question, the second part ...
1
vote
2answers
62 views

Finding the contrapositive of the statement “I go to school if it does not rain”

I got this question in a exam.There were two more statements in the examination(but they were quite clearly wrong).However I got stuck between these two statements.The contrapositive of the the ...
1
vote
1answer
38 views

The ability of a logical statement to represent a two-place truth function.

How can i determine which two-place truth functions can be represented using a logical statement built out of a subset of two logical connectors in $ \{\rightarrow, \wedge, \vee ,\equiv \}$ ? for ...
1
vote
0answers
35 views

Boolean Expression Simplification (De Morgan's)

I need to prove that: $$ !(!(X.W) + !(X.Z))) = X.W.Z $$ I have tried multiple approaches but cannot figure this out. Using DeMorgan's theorem, I break the negative sign binding $XW$, and $XZ$, and ...
0
votes
1answer
16 views

Finding number of Boolean algebras

How many Boolean algebras are there with four elements $0,1,a,b$ ? I don't know how to proceed with this. Any ideas ?
-1
votes
1answer
24 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
52 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
37 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
76 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
32 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
66 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
65 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
74 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
63 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
46 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
72 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
32 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
31 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
33 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
27 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
48 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
43 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
83 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
332 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
37 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
63 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
26 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
40 views

Boolean Algebras

simplify: (1) $f= pq+r$ (2) $g=a+bc+a'bc'd$
0
votes
1answer
34 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
26 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
50 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
56 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
58 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
22 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
82 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
62 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
29 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
52 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
54 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
75 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
86 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
29 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 ...