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
1answer
166 views

Better compression for a positive DNF than via BDD

I am experimenting with compressing positive disjunctive normal form (DNF). When I use binary decision diagrams (BDDs) related algorithms I don't get very good results. For example the algorithms ...
1
vote
1answer
23 views

Injectivity of Stone embedding

Let $\mathcal{B}$ be a Boolean algebra, $X$ the set of ultrafilters of $\mathcal{B}$ and $\sigma:\mathcal{B}\longrightarrow\mathcal{P}(X)$ the map sending $b\in\mathcal{B}$ to the set of ultrafilters ...
0
votes
1answer
168 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$ ...
1
vote
3answers
344 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
27 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?
1
vote
1answer
62 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
1answer
29 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?
1
vote
4answers
128 views

Infinite boolean sequence

I was given the following problem: Let $V_1, V_2, \dots$ be an infinite sequence of Boolean variables. For each natural number $n$, define a proposition $F_n$ according to the following rules: ...
1
vote
2answers
176 views

Boolean Algebra: Can this be simplified further?

AB+CD+A’BD+A’BC+AB’D+AB’C AB+CD+A’B(D+C)+AB’(D+C) CD+(AB+A'B(D+C)+AB’(D+C)) CD+(AB+B(D+C)+A(D+C)) CD+AB+(B(D+C)+A(D+C)) CD+AB+(A+B)(D+C) This is what I got, but ...
0
votes
1answer
40 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 ...
3
votes
1answer
604 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 ...
1
vote
1answer
294 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
0answers
78 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 ...
1
vote
3answers
144 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 )$$ ...
0
votes
2answers
215 views

Trouble with boolean algebra as used in logic

I'm having trouble knowing how to continue on with this problem, I don't know what to turn the equivalent sign into and I cant really continue with that side, can anyone help me out? Do I just say ...
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 ...
2
votes
1answer
165 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
166 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
64 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 ...
5
votes
1answer
175 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
vote
1answer
122 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
40 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: ...
0
votes
2answers
109 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$ ...
2
votes
1answer
63 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
159 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
1answer
144 views

Boolean Algebra Simplification Help, Need AND's, OR's, NOT's only

I'm having a very hard time simplifying this: A!B!C+ABC+!A!BC+!AB!C The objective here is to simplify the equation until it can be expressed in "AND"'s "OR"'s and "NOT"'s. I have to create an ...
1
vote
3answers
4k views

Boolean function simplification

I'm having problems with the following expression: (A'+B)'+B(A'+AC)+ABC' And here is what I tried to simplify: ...
0
votes
1answer
134 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
345 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 ...
1
vote
1answer
62 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 ...
0
votes
2answers
113 views

Rewrite equivalent boolean function for p ⇔ q

Using only the operators ⇒ (conditional) and ∼ (negation) Rewrite p ⇔ q How should I go about this? Thanks
2
votes
4answers
158 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 ...
0
votes
2answers
46 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, ...
17
votes
2answers
885 views

Any two points in a Stone space can be disconnected by clopen sets

Let $B$ be a Stone space (compact, Hausdorff, and totally disconnected). Then I am basically certain (because of Stone's representation theorem) that if $a, b \in B$ are two distinct points in $B$, ...
0
votes
2answers
3k 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
2answers
422 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$ ...
1
vote
1answer
1k views

Simplify the boolean equation using boolean algebra rules

If I have the boolean equation: H = M'CD' + MC + MC' + CRD I think I can combine so that it's H = M'CD' + M(C + C') + CRD Does C + C' go to simplify to zero? So, I'm left with H = M'CD' + CRD
0
votes
1answer
106 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
91 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
69 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.
1
vote
2answers
67 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
196 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
214 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 ...
2
votes
2answers
59 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 ...
1
vote
1answer
113 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
140 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
135 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 || ...
1
vote
2answers
77 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!!
2
votes
2answers
122 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 ...