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

3
votes
1answer
45 views

Is this a valid re-write rule?

In my job (SQL developer) I frequently need to change search conditions (WHERE clauses, database constraints) from disjunctive normal form to conjunctive normal form (CNF). I confess I usually resort ...
1
vote
1answer
185 views

How to simplify the following expression through Boolean algebra

Disclaimer: This was a homework problem from the first assignment of the semester - the assignment has long since been graded. For the life of me I can't crack this one - I don't understand what I'm ...
3
votes
4answers
179 views

How is $((X\to Y)\to X)\to X$ a tautology?

$((X \rightarrow Y ) \rightarrow X) \rightarrow X$ converted to its disjunctive normal form is $X' + X$. Why/how does this show me why this formula a tautology?
1
vote
1answer
137 views

Convert $(X\lor Y)\land(W \lor Z)$ to disjunctive normal form

Using the distributive laws, I need to convert the formula $(X\lor Y )\land (W \lor Z)$ into disjunctive normal form. The answer needs to be equivalent to this formula by means of a truth table. Can ...
0
votes
2answers
42 views

Simplification of boolean algebra from “not s and p” to “not s”

I am trying to learn more about "Rules of Inference" and their application, but one thing always confuses me, and that is simplification "not s and p" to "not s". I have looked at some examples: ...
1
vote
1answer
70 views

Extending a Filter in a Well-Ordered Boolean Algebra to an Ultrafilter WITHOUT the Axiom of Choice

Hypothesis: Let $B$ be a well-ordered boolean algebra and let $F \subseteq B$ be a filter on $B$. Goal: Show that $F$ can be extended to an ultrafilter without the axiom of choice (or any equivalent ...
2
votes
1answer
134 views

Is every Boolean algebra a separative partial order?

A partially ordered set $\langle P,\leq\rangle$ is separative iff it satisfies the following condition: \[ \neg x\leq y\Rightarrow\exists z(z\leq x\wedge z\bot y) \] where: \[ x\bot y\iff\neg\exists ...
1
vote
1answer
217 views

Minimization of boolean function using Quine–McCluskey algorithm

I have a boolean row. It looked like this: Y = 0,1,0,1,1,0,0,1,1,0,1,0,1,1,0,0 Then I converted it to: f(x1,x2,x3,x4) = 0101 ∪ 1001 ∪ 1010 ∪ 1100 I divided it into groups: 0 | - ...
0
votes
2answers
117 views

How to minimize $\bar{A}.\bar{C}+\bar{A}.B+A.C$ further?

$\bar{A}.\bar{C}+\bar{A}.B+A.\bar{B}.C+B.C$ $=>\bar{A}.\bar{C}+\bar{A}.B+A.\bar{B}.C+\color{Orchid }{(A+\bar{A}) }.B.C$ ...
5
votes
1answer
190 views

Efficient division using binary math

I'm writing code for an FPGA and I need to divide a number by $1.024$. I could use floating and/or fixed point and instantiate a multiplier but I would like to see if I could do this multiplication ...
-1
votes
1answer
143 views

Simplifying Boolean Algebra law

I've got a problem here that I could use help solving. I have simplified it to this point. Using Wolfram Alpha, I know it is still possible. My lecturer did it but I didn't catch all of it. It is ...
1
vote
1answer
75 views

Boolean algebra generated by value sets of polynomials over $\mathbb{N}$

Update For each polynomial $P \in \mathbb{N}[X]$, let $S_P = \{ P(n) \mid n \in \mathbb{N}\}$. Does the Boolean algebra generated by the subsets $S_P$ of $\mathcal{P}(\mathbb{N})$ such that $P$ is ...
1
vote
1answer
1k views

Is it logically valid to prove DeMorgan's laws using the duality of boolean algebra?

I'm taking an introductory course in boolean algebra, and have been assigned the task of proving DeMorgan's Laws (so, disclaimer, this is homework). One line of reasoning that I came up with would be ...
1
vote
1answer
353 views

Boolean formula over 64 Boolean variables X

This question comes from this homework assignment from ECS20 at UC Davis. Chess is played on an 8 x 8 board. A knight placed on one square can move to any unoccupied square that is at a distance ...
0
votes
2answers
50 views

Prove the following with equivalence statements.

I need to prove the following statement with equivalence statements. $\exists x \in D,(P(x) \Rightarrow Q(x)) \ \text{is equivalent to} \ (\forall x \in D, P(x)) \Rightarrow (\exists x \in D, ...
0
votes
2answers
5k views

Boolean Algebra A + AB = A

Hi I have a question about the following algebra rule A + AB = A My textbook explains this as follows A + AB = A This rule can be proved as such: Step 1: Dustributive Law: A + AB = A*1 = A(1+B) ...
2
votes
4answers
166 views

Proving logical equivalence: $P \Leftrightarrow P \vee (P \wedge Q)$

I'm a first year CS student about to write his first term test and this question is part of our practice package. I have not been successful in writing a sequence of equivalences to justify this ...
2
votes
2answers
566 views

Disjunctive normal form expansion

I do not understand this at all. Find the sum-of-products expansions of these Boolean functions. $F(x, y, z) = x + y + z$ $F(x, y, z) = (x + z)y$ $F(x, y, z) = x$ $F(x, y, z) = x y$ ...
0
votes
1answer
203 views

Minimize SOP and POS algebraically?

Is it possible to simplify an SOP (sum of products) or POS (product of sums) expression algebraically? I can only do it through k-maps. Example: $a'b'c'd' + a'b'c'd + a'b'cd' + a'b'cd + ab'c'd + ...
1
vote
1answer
16k 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) ...
2
votes
1answer
95 views

Boolean Simplification Problem

I have to simplify the figure I came up with the equation $$(ac+\bar b)\cdot (a+b+\bar c) \cdot (b+ac).$$ Help me out Attempted Answer: \begin{align*} (ac+\bar b)\cdot (a+b+c)\cdot (b+ac) ...
0
votes
1answer
92 views

Simplify the boolean expression to two literals

Expression: $$[AB'(C+BD) + A'B']C$$ I start off using the distributive law, and then nowhere to go. I need help.
2
votes
1answer
492 views

Trying to simplify the expression $A'B'C'D' + A'BC'D' + A'BC'D + AB'C'D$

So far I've got: $A'B'C'D' + A'BC'D' + A'BC'D + AB'C'D$ $= A'C'D'(B' + B) + C'D(A'B + AB')$ $= A'C'D'(1) + C'D(A \;\text{ XOR }\; B)$ $= C'[A'D' + D(A \;\text{ XOR }\; B)]$ Did I do this ...
1
vote
2answers
932 views

Trying to simplify $A'B'C'D + A'B'CD + A'BC'D + AB'CD + ABCD$

My solution so far: $A'(B'C'D + B'CD + BC'D) + A(B'CD + BCD)$ $= A'(C'D(B' + B) + B'CD) + A(CD(B'+B))$ $= A'(C'D(1) + B'CD) + A(CD(1))$ $= A'C'D + A'B'CD + ACD$ $= D(A'C' + AC) + A'B'CD$ $= ...
1
vote
2answers
73 views

Boolean Algebra - Demorgan Laws

I am given the problem: !((!A * B) * !((!B + C) * (!C * !D))) where ! = NOT, * = AND, and + = OR and I tried simplifying it using only Demorgan Laws (no absorption) and I got: (A + !B) + ((!B + ...
0
votes
1answer
353 views

Reducing a product-of-sums expression

f = ($x_1$ + $x_3$ + $x_4$) * ($x_1$ + $\overline x_2$ + $x_3$) * ($x_1$ + $\overline x_2$ + $\overline x_3$ + $x_4$) I've been working on this problem for a while but I cannot for the life of me ...
2
votes
2answers
220 views

Parity function proofing for every n>=1 using only AND, OR, 0, and 1

Consider the parity function: $F_n$($x_1$, $...$ ,$x_n$) $=$ $\oplus_{i=1}^n$$x_i$ where each $x_i$ is boolean. Prove that, for every $n \ge 1$, there is no way to compute $F_n$ using only ...
4
votes
1answer
1k views

Functionally complete sets of boolean functions

A (finite) set of boolean functions $S=\{f_1,\ldots,f_n\}$ is called functionally complete if every boolean function (of a finite number of variables) can be presented as a finite composition of ...
2
votes
2answers
63 views

For a valid chain of deduction in boolean algebra, does the chain of its dual hold as well?

For example, xy + x'z + yz = xy + x'z + yz(x+x') = xy + x'z + yzx + yzx' = xy + xyz + x'z + x'zy = xy(1+z) + x'z(1+y) = xy + x'z Hence xy + x'z + yz = xy + x'z. Also ...
0
votes
2answers
533 views

Writing a boolean formula and logic circuit that computes mux

Let $mux(p_{11}, p_{10}, p_{01}, p_{00}, x_1, x_0) = P_{x1x0}$ (with all variables bits). Write a boolean formula, and then draw a circuit, that computes mux. For ...
1
vote
1answer
137 views

Simplifying Boolean Function

I am in a computer class with Karnaugh Maps and one of the questions is X 'Y Z + X 'Y 'Z + 'X Y 'Z + X Y Z and I need to simplify it where ' means not so 'x means not x. I think the answer is X 'Y ...
1
vote
2answers
134 views

Is the following sentence a tautology: $(p\Rightarrow q)\vee(r \Rightarrow p)\vee(r\Rightarrow s)\vee(r\Rightarrow q)$?

If both $p$ and $q$ are false then ($p\Rightarrow q$) is true. If either $p$ or $q$ is true then one of ($r\Rightarrow p$) or ($r\Rightarrow q$) is true. If both $p$ and $q$ are true then all are ...
2
votes
2answers
177 views

Proving a Logic Equation

I have two information. $x+y = 1$ and $xy = 0$. Now,I need to prove this equation : $xz + x'y + yz = y + z$ What I tried: $z(x+y) + x'y = z + x'y$ Thats all What do you think?
0
votes
0answers
177 views

Simplifying Boolean expression: $F(a,b,c,d)$

I have a Boolean function below and I need to simplify it. F(a,b,c,d) = !a&&!b&&d || !a&&c&&!d || !a&&b&&!c || a&&!c&&!d || ...
5
votes
2answers
346 views

Simplify $(A+C)(AD+AD) + AC + C$ using Boolean algebra

I have solved the equation like this: ...
2
votes
2answers
154 views

Negation bar meaning?

I know that the horizontal bar on top means it's a negation. But I've never encountered one over more than one term like this one: $\overline{\bar{x} + \bar{y}x}(y + \overline{xy})$ Is that ...
2
votes
1answer
125 views

Commutative ring addition where $a^2 = a$

I'm trying to solve following question: If $a^2=a$ for all $a \in R$ where $R$ is a commutative ring, then $a+a=0$. I have tried to solve this problem for a while now and I'm more or less stuck. I ...
-1
votes
1answer
147 views

Boolean logic simplification

To simplify $$ A'B'C'D + A'B'CD' + A'BC'D' + A'BCD + AABC'D + ABCD' + AB'C'D' + AB'CD $$ I have no idea how to start the first step. Thanks in advance!!
1
vote
2answers
79 views

boolean logic simplify

To prove: $(X+Y)(X'+Z) = XZ + X'Y$ I try to simply $(X+Y)(X'+Z)$ to $XZ + X'Y + YZ$ then I have no idea how to simply further. Thanks in advance!!
0
votes
1answer
130 views

Simplify the expression below by using the Algebra laws:

Simplify the expression below by using the Algebra laws: $$ AB + \overline{(\bar AC + B)\cdot \overline{(\bar B \oplus C)}} $$
0
votes
2answers
131 views

Boolean algebra simplification

I have the equation (CD)+(BC'D'+A'B'C'D)+(C'D') and I can't seem to simplify it enough for my homework. I've tried multiple ways of simplifying the equation and I keep ending with an extra variable D. ...
1
vote
1answer
89 views

How to find/generate a 6 variable Bent Function?

I want to find a Bent Function with 6 variables. I read some papers about how to generate Boolean Functions, but I don't want to implement an algorithm from zero just to find one function. It is also ...
0
votes
3answers
78 views

Three Boolean Algebra Proofs - I just don't get it!

I'm having a very difficult time proving the following 3 expressions: $$\begin{align*} &x\cdot y\cdot z+x'\cdot z=y\cdot z+x'\cdot z\\ &x\cdot y+y\cdot z+x'\cdot z=x\cdot y+x'\cdot z\\ ...
0
votes
2answers
34 views

Discrete: Boolean Function

~(pV~q) v (~p^~q) is equal to ~p? I know the answer is yes and I've been using DeMorgans initially then distributive law after. However I keep messing up on the algebra. Help is appreciated so I can ...
2
votes
1answer
672 views

Simplify Boolean Expression ABC' + A'BC + A'B'C'

Can anyone help me simplify this boolean expression? ABC' + A'BC + A'B'C' EDIT: (only using AND gates (multiply [(x)(x)]) and OR gates (addition [+]))
2
votes
2answers
310 views

Steps to simplify a Boolean Expression

Simplify: (x ∧ y) ∨ (x ∧ ¬y) ∨ (¬x ∧ y) I need to simplify this using the using properties going step by step. I keep ending up with (x ∧ y) as the answer but when I map is out I get that is should ...
-1
votes
1answer
935 views

sum-of-products expansions of these Boolean functions

Find the sum-of-products expansions of these Boolean functions. $a)$ $F(x, y) = \text{~}x + y$ $b)$ $F(x, y) = x \text{~}y$ $c)$ $F(x, y) = 1$ $d)$ $F(x, y) = \text{~}y$
0
votes
1answer
712 views

Conclude the premise using rules of inference

First question I have solved I belive... show, s -> (q -> r) <-> (s ^ q) -> r using the defintion of implication and Boolean algebra. s ->(~q V r) <-> ~ (s ^ q ) V r ~s V (~q V r ) <-> ~s ...
1
vote
4answers
5k views

how many semantically different boolean functions are there for n boolean variables?

In short, this is an assignment question for a course I am taking - the exact wording is this: "Given n Boolean variables, how many 'semantically' different Boolean functions can you construct?" ...
1
vote
1answer
275 views

Expressing boolean functions using the not or operator

I need to express these with $\downarrow$ $x+ y + z$ This one I think I can do, I guess at it and copy the wikipedia page since my book has no explanation on how to do this I get $(x \downarrow y ...