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

2
votes
2answers
74 views

'Algebraic' way to prove the boolean identity $a + \overline{a}*b = a + b$

For me, it is pretty clear that $a + \overline{a}*b = a + b$, because the first $a$ in the or will make sure that if the second term must be 'evaluated', $a$ will ...
1
vote
0answers
169 views

Logical operations precedence and calculator program

I write the C library intended to be used in evaluating math expressions. It should support boolean algebra also. So at the moment I'm stuck with boolean precedence. I'm not a mathematician so that's ...
2
votes
2answers
59 views

What to do with a hanging $1$ in a Karnaugh map?

I am learning about Karnaugh maps to simplify boolean algebra expressions. I have this: $$\begin{bmatrix} & bc & b'c & bc' & b'c' \\ a & 0 & 1 & 1 & 0\\ a' & 1 &...
1
vote
1answer
62 views

Simplify Boolean equations

I have simplified following Boolean expressions. Can somebody tell me whether they are right or wrong? 1) F1 = ~(~A ~B C + ~(AB)C) ~(~A ~B C) = ~(~A) + ~(~B) + ~C -------> Apply DeMorgan's law to ...
1
vote
1answer
63 views

Simplying Boolean-Logic Expression

Can you help me simplify this or is this the simplified form? A = (X + Y + Z) (X + ~Y + ~Z) (~X + Y + ~Z) (~X + ~Y + Z) Here's my attempt: ...
0
votes
1answer
44 views

Boolean algebra: $(x+y)(x’+z)(y+z) = (x+y)(x’+z)$

Could someone explain to me how this simplification is derived? $(x+y)(x’+z)(y+z) = (x+y)(x’+z)$
0
votes
1answer
53 views

Boolean Equivalence using Karnaugh Maps

If I had two functions, where each letter represents a state: f(1) = CD + AB f(2) = AC + AD + BC How could I find the minimum term that would need to be added to the second function to make the ...
1
vote
1answer
85 views

Dense Boolean subalgebras

I was reading this page and, in the third part of the first remark I found the definition of dense sub-algebra of a Boolean algebra. It is stated that there are various equivalent definitions of this ...
1
vote
1answer
54 views

Where do I start with $\sim((P\wedge Q)\vee \sim(P\vee Q))$?

can anyone tell me in a table form how to start with this $\sim((P\wedge Q)\vee \sim(P\vee Q))$ I am confused on how to do this part $\sim(P\wedge Q)$, which one we do first, inside brackets or ...
0
votes
1answer
63 views

Nand this Boolean Algebra Function?

I'm trying to convert this Expression that I got from minterms given to me by my professor to use only NANDS. I swear it should be right, but the output Multisim is giving me is false. minterms(0,1,2,...
2
votes
2answers
141 views

How can I calculate if a given point is wrapped inside a pentagon?

If I have a pentagon and I know the coordinates of it's nodes, how do I calculate if a point is wrapped inside it? An example to clarify what I mean: Assume that we know the coordinates of the ...
0
votes
1answer
611 views

Proof of the identity of a Boolean equation $Y+X'Z+XY' = X+Y+Z$

How to prove the following the identity of a Boolean equation? $$ Y+X'Z+XY'=X+Y+Z $$ I have tried : $ \space\space\space\space\space Y+X'Z+XY'\\ =X'Z+XY'+Y\\ =X'Z+XY'+Y(X+X')\\ =X'Z+XY'+XY+...
3
votes
1answer
94 views

Countable sum of atomic measures is atomic?

Let $(X,\Sigma)$ be a measurable space and $(\mu_n)$ a sequence of atomic measures defined on this space. Recall that a measure $\mu$ is atomic if for any measurable $A$ of measure $\mu(A)>0$ there ...
3
votes
1answer
122 views

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let's consider the following two aspects: 1.) IEP transforms at least ...
0
votes
3answers
3k 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
178 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
48 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
1answer
77 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
19 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
35 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
-1
votes
1answer
96 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
68 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
132 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
54 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
33 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 * B)...
1
vote
2answers
146 views

Truth-functional completeness

Let the statement $?PQR$ be determined by the following truth-table. ...
2
votes
1answer
22 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
311 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 X_{ir_1c}\...
3
votes
2answers
113 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
261 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
50 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 x_2\land\...
0
votes
3answers
33 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
200 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
40 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
40 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
56 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.
-1
votes
1answer
35 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
68 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
52 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$ ...
2
votes
1answer
517 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
1k 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
49 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
200 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. ...
-1
votes
1answer
43 views

Boolean Algebras

simplify: (1) $f= pq+r$ (2) $g=a+bc+a'bc'd$
0
votes
1answer
59 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
76 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
80 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 sigma-...
1
vote
1answer
78 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
149 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
43 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 ...