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
0answers
35 views

Boolean Algebra. Expand The Term

This is a question from a past exam paper, but strangely nowhere in my textbook do they cover it. Im just worried come exam they will throw a curve ball with a similar question. Please can someone be ...
0
votes
1answer
100 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
43 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
673 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
337 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
38 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
415 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
132 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
250 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
58 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 + ...
0
votes
1answer
3k 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
65 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
46 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.
0
votes
2answers
67 views

Product recommendation from user answered questions [closed]

This is my first question on MATHEMATICS, I'm normally asking and answering on Stack Overflow! Anyway, I have a specification at work for an app I'm building. The app should allow a user to answer a ...
2
votes
1answer
352 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
1answer
553 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
55 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
91 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
203 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 ...
3
votes
1answer
306 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
54 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
302 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
89 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 ...
2
votes
2answers
98 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
118 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
122 views

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

I have solved the equation like this: ...
2
votes
2answers
82 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
78 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
137 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
70 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
98 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
120 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
40 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
65 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
31 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
423 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
178 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
228 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
249 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 ...
0
votes
3answers
1k 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?" ...
0
votes
0answers
60 views

Boolean Algebra problem

Given two binary vectors $A=(a_1,..,a_n), B=(b_1,..,b_n) \in \varphi^n$, we define the Hamming's distance between $A$ and $B$, $\rho (A,B)$ as: $\rho(A,B)=\sum_{i=1}^{n}|a_i-b_i|$ And, for a vector ...
1
vote
1answer
71 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 ...
1
vote
0answers
39 views

Given a finite set of points construct a polynomial that meets the points.

Say I have a set of points in $\mathbb{Z}^3 \times \mathbb{Z}_2$ each of which represent part of a mapping $(z_1, z_2, z_3) \mapsto z_4 \in \mathbb{Z}_2$. How do I find the the simplest polynomial ...
3
votes
1answer
40 views

The set of all polynomial functions from $\mathbb{Z}^3 \rightarrow \mathbb{Z}/(2)$

Let $f:\mathbb{Z}^3 \rightarrow \mathbb{Z}_2$ be a polynomial function in $\mathbb{Z}[x_1, x_2, x_3]$. Then $f$ has the form $f(x_1, x_2, x_3) = c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_1 x_2 + c_5 x_1 ...
0
votes
1answer
106 views

Prove that S is a Boolean Algebra

Let $n\ge1\in\Bbb N$, we define the set of binary boolean vectors with $\varphi^n .$ Prove that $\varphi^n$ is a boolean algebra. So (...) I know that: Let $\varphi=\{0,1\}, \mathrm ...
1
vote
3answers
239 views

Is “(p AND q) OR r” logically equivalent to “p AND (q OR r)” ??

In the context of discreet math / boolean algebra / logic, is "(p AND q) OR r" logically equivalent to "p AND (q OR r)"? I believe so, but my professor said: ...
1
vote
2answers
188 views

Proving boolean algebra property

Let $S$ a boolean algebra; $a,b,c \in S$ prove that $(a'+b)'+(a'+b')'=a$ Then: $(a'+b)'+(a'+b')'= (a')'+b'+(a')'+(b')'=a+b'+a+b = (a+a)+(b+b')=a+1=1$ Maybe i'm wrong but I think that the problem is ...
-1
votes
1answer
84 views

boolean expression help simplify

Question 1 $$\begin{align*}A'BC + AB'C + ABC + A'B'C' &=A'B C + B' C (A +A') + ABC\\ &=A'B + C + B'C + ABC \end{align*}$$ Question 2 $$\begin{align*}A'B + B'C + CB &=A'B + C(B +B')\\ ...
1
vote
1answer
2k views

Boolean-expression simplification $F = AB'C + (A'B' + ABC'D)'$

Here are my solutions. Hence: I am stuck on where or what path I am going to take Problem: F = AB'C + (A'B' + ABC'D)' Solution 1 --------------- F = AB'C + (A'B' + ABC'D)' = AB'C + (A'B')' (ABC'D)' ...
1
vote
0answers
22 views

Proving a boolean algebra question [duplicate]

Let $\sqsubseteq$ be a boolean ordering of the boolean algebra $X$, which means that for each $x$ and $y$ the following applies: $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v ...