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
vote
2answers
174 views

A detail in the proof of Stone representation Theorem

Let $(\mathcal{B},\sqcap,\sqcup,\leq)$ be a Boolean algebra. Let $x,y\in\mathcal{B}$. I want to prove the following implication: $$x\sqcap y'\leq 0\Rightarrow x\leq y$$ where $y'$ is the complement ...
1
vote
3answers
1k views

Show that $ \{\lnot,\leftrightarrow\} $ is not functional complete

I have to prove that this set of logical operators is not functional complete - $$ \{\lnot,\leftrightarrow\} $$ i've tried implement this set by $ \{\rightarrow,\lor\} $ which is not functional ...
0
votes
1answer
255 views

Find the disjunctive normal form and then simplify

Let $f(x,y,z,w)=zw+z'w'+xy'z'w+xyz'w$ Disjunctive normal form $zw(x'+x)(y'+y)+z'w'(x'+x)(y'+y)+xy'z'w+xyz'w=(zwx'+zwx)(y'+y)+(z'w'x'+z'w'x)(y+y')+xy'z'w+xyz'w$ ...
0
votes
1answer
31 views

Proving at boolean algebra

Must prove that $$(X+Y )=X+(X.Y')$$ i tried a lot of ways, using logic things and expanding this things, but cant reach the Y. $$(X+Y )=(X+X).(X+Y')$$ Whats the possible prove to this?
0
votes
2answers
49 views

Equivalent definitons of atom in a Boolean Algebra

I want to show that the following conditions are equivalent for a nonzero element $a$ in a Boolean algebra $\mathcal{B}$: 1) for all $x\in\mathcal{B},a\leq x$ or $a\leq x'$ 2) for all ...
0
votes
1answer
54 views

how do you factor this boolean equation?

How do you factor this boolean equation $A'B'CD+AB'CD'+AB'C'D+ABCD$ I need help with where do I start from. What are the factors?
0
votes
1answer
50 views

In a boolean matrix, what does the $n$ in $M_{R^n}$ represent?

I'm now learning about binary relations. I stumbled upon this question in the book: Given $A = \{1,3,5,6\}$ and $R$ is a relation over $A$, whose matrix is defined by $$\begin{pmatrix} 0 ...
1
vote
1answer
414 views

Simplifying Sums of Product Expression obtained from 8-3 Priority Encoder (Computer Science)

I have an example for simplifying expressions in sums of product form, but I can't figure out which algebraic theorem was used to get rid of some of the variables: Step 1. (A'B'C'D'E'F'G) + ...
1
vote
3answers
229 views

Correct progression from DNF to CNF?

Trying to figure out how to transform this predicate from disjunctive normal form to conjunctive normal form (repost of an earlier question): $$( P \land Q ) \lor ( R \land S ) \lor ( P \land S )$$ ...
1
vote
0answers
90 views

Are there impossible boolean constructions?

I was reading about logic and I remember, for example: That with the binary $\mathtt{NAND}$ connector can be used to assemble all the other binary connectors - I already know that there are primitive ...
3
votes
1answer
47 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
218 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 ...
4
votes
5answers
241 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
162 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
74 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
187 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
318 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
124 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
232 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
161 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
84 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
2k 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 ...
0
votes
1answer
364 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
52 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
10k 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
175 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 ...
3
votes
2answers
885 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
501 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 + ...
2
votes
1answer
32k 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
97 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
156 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
564 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
1k 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
83 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
652 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
225 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
2k 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
67 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
677 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
155 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
145 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
238 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
212 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
594 views

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

I have solved the equation like this: ...
3
votes
2answers
229 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
148 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
148 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
188 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)}} $$