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

simplifying boolean algebra expression [duplicate]

A very urgent question : Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : ...
0
votes
1answer
40 views

Boolean Expression Simplification

Dear all, I need help to simplify this Boolean algebra. Please give me a answer step by step. Thanks
0
votes
0answers
74 views

Find the disjunctive normal form of a function

so I am following in the textbook and have just been able to determine the disjunctive normal form of a function given a chart, but now these new questions say: ...
0
votes
0answers
28 views

What is the simplest form of the Boolean expression below? [duplicate]

I'm completely new to Boolean algebra, and I'm trying to simplify the expression below, using the distributive law, cancellation, negative absorption and De Morgan's theorem. I would start with the ...
2
votes
3answers
42 views

Boolean endomorphisms vs endofunctions on finite sets

I stumbled upon a funny fact: Let $\mathbf{Bool} = \{0, 1 \}$. For all functions $f: \mathbf{Bool} \to \mathbf{Bool}$ it is the case that $f^3 = f$. This got me excited and I was wondering whether ...
0
votes
1answer
46 views

How to give an assignment of boolean values such that this expression is evaluated to true?

Given the expression $E$, is there an assignment of boolean values ($true$ or $false$) that we can give to our variables such that this is evaluated to $true$? $E = (¬x + z + ¬v) · (¬v + w) ·(¬z + ...
0
votes
0answers
101 views

Convert expression to NAND only

Endless youtube videos and reading through notes later I am yet again stuck. I have to covert the following to NAND only $$\bar{A}\cdot\bar{B}\cdot\bar{C} + A\cdot\bar{B}\cdot C + A\cdot B\cdot ...
1
vote
4answers
85 views

Boolean Algebra simplify minterms

I have this equation $$\bar{A}\cdot\bar{B}\cdot\bar{C} + A\cdot\bar{B}\cdot C + A\cdot B\cdot \bar{C} + A \cdot B\cdot C$$ and need to simplify it. I have got as far as I can and spent a good 2 ...
0
votes
1answer
21 views

Demultiplexor Equation?

I am currently working on a project that requires a demultiplexor to be used. My problem is that I want to represent it in equation form, but no matter how much I try I cannot find the equation for a ...
2
votes
1answer
43 views

Inverse of a Boolean Function

Assume that I have a multi-output Boolean function $f(x_1,x_2,x_3,x_4) = (y_1,y_2,y_3,y_4)$. Is there a direct way of computing the inverse, that is, $g$ such that $g(y_1,y_2,y_3,y_4) = ...
-1
votes
2answers
87 views

Simplify Sum of Products: $\;A'B'C' + A'B'C + ABC'$

How would you simplify the following sum of products expression using algebraic manipulations in boolean algebra? $$A'B'C' + A'B'C + ABC'$$
0
votes
1answer
59 views

simplify boolean algebra expressions

Use Boolean algebra to simplify the expression for F1, where, F1 = A’.B’.C’.D’ + A’.B’.C.D’ + A’.B’.C.D + A’.B.C’.D + A’.B.C.D’ + F2 and F2 = A’.B.C.D + A.B’.C’.D’ + ...
0
votes
0answers
32 views

Definition of a linear extension (total order?) of a poset

Hey I have a question about the definition of a linear extension of a poset. If I was given a hasse diagram of a poset with relation <= (S, <=), how can I get the compatible total order of this ...
0
votes
0answers
52 views

Hasse diagram vs digraph and bounds question

I have attached a link to my hasse diagram I drew... Sorry about image size and rotation. So is it correct to say a hasse diagram is just a digraph with each internal vertice removed? So would my ...
0
votes
1answer
36 views

Convert 4-sat to 3-sat

I want to know in general how can I convert $4-SAT$ to 3-SAT. And I have a specific case that if you can help me optimize it to 3-SAT it will be greate. I want to do this so I be able to use sat ...
0
votes
1answer
68 views

How to prove this equality using boolean algebra?

I have approximately no idea on how to solve the following problem, so any help would very much be appreciated: $$x' y'+ x y = (x y' + x' y)'$$ I can't figure out how to prove the equalities ...
0
votes
2answers
52 views

Boolean Algebra - Why is the result 1?

Given: = !(A * (!B + C)) + !(!B * !C) = !A + (B * !C) + !B + C Where: ! = NOT + = OR * = AND I'm having some trouble to why !A + (B * !C) + !B + C simplifies to 1? Can someone shed some light on ...
0
votes
0answers
48 views

Doubt in K-map rule (loops)

Is it possible to mark a loop in k-map as in second figure in above diagram (indicated in blue). According to my knowledge the first figure is correct. Is figure 3 or 4 correct? Note: Consider ...
5
votes
1answer
143 views

Cantor-Bernstein theorem for $\sigma$-complete Boolean algebras.

I am working on problem 7.28 from Jech's Set Theory: Let A and B be σ-complete Boolean algebras. Let a and b be elements of A and B respectively. If A is isomorphic to B$\upharpoonright$b and B is ...
2
votes
2answers
48 views

How to write this as a boolean expression?

How can I write the following sentence as boolean expression: $$ \text{If two sides of triangle are the same, then two opposite angles are the same} $$ I konw it should be something like this: $$ a = ...
4
votes
2answers
151 views

Convert Circuit SAT to 3-SAT

I am trying to convert Integer Factorization to $3-SAT$. So far I managed to convert it to Circuit SAT, but I don't know how to make the final step. This is how it look for 3*3 multiplication: ...
2
votes
0answers
63 views

Fields of sets in which, if the l.u.b. of a subset exists at all, it is the union of the subset

I am learning about boolean algebras and how they can be represented as fields of sets. Stone's representation theorem tells us that every boolean algebra is isomorphic to a field of sets. Consider an ...
0
votes
2answers
31 views

Prove This Bool Expression

Prove $x'z+xyz+xy'z=z$ can you show how you solve this using Boolean Algebra. My main problem is when I do this $xz (y + y') = 1 $ So $1$ times $x =$ ?
1
vote
1answer
22 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 ...
1
vote
2answers
38 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
121 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
108 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
26 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
33 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
24 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
0answers
38 views

Free Product VS Direct Product of Boolean algebras

Could someone give me the definitions of Free Product and Direct Product of Boolean algebra (possibly Boolean algebras that carries measures) I have seen some definition of free product which ...
0
votes
1answer
37 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
220 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) + ...
0
votes
0answers
23 views

Can matrices be reduced in the same way that Karnaugh maps can be expressed as an equation?

I'm doing linear algebra, and boolean algebra for electronics and I'm wondering if there are any standard mathematical ways in linear to express a matrix more simply without resulting to graphical ...
1
vote
3answers
103 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 )$$ ...
2
votes
0answers
71 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
44 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
113 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
153 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
93 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
32 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
62 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
50 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
113 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
91 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
155 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 ...
0
votes
0answers
29 views

Event probability prediction from multiple observations

I am programming some fuzzy logic for an application I'm developing, and I'm not sure how to "combine" multiple fuzzy boolean observations into a guess. Each of my fuzzy boolean observations describes ...
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 ...