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
2answers
151 views

Example of a function between boolean lattices that preserves $(\top,\bot,\wedge,\vee)$ but not complements.

Its easy to find boolean lattices $A$ and $B$ together with a function $f : A \rightarrow B$ such that $f$ preserves both top and bottom elements, as well as binary meets, but not complements. ...
0
votes
4answers
95 views

Simplifying this boolean function

How can I completely simplify this equation using algebraic simplification rules? $$x'y'z + x'yz + xyz$$
0
votes
1answer
6k views

Simplify Boolean Product of Sums Function

I've got a product of sums expression: F=(A'+B+C')&(A+D')(C+D') I need to show it as a sum of products and then simplify it. Right now I got: F=(A'&D')+(A&B&C)+(B&D')+(C&D') ...
0
votes
1answer
50 views

Boolean function on $\{0,1\}^n$ comprising just binary AND and OR gates

Let $f:\{0,1\}^n\to\{0,1\}$ be a boolean function computed by logical circuit comprising just binary AND and binary OR gates (assume that the circuit doesn't have any feedback). Let $PARITY:\{0,1\}^n\...
0
votes
1answer
99 views

Truth table to prove statements

A, B and C. When questioned A says ''If B did not do it, then it was C." B says ''A and C did it together or C did it alone". C says ''We all did it together." How would i be able to put these into ...
0
votes
1answer
46 views

Write $p \rightarrow \lnot q$ in CNF form with only and ,or and brackets

Write $p \rightarrow \lnot q$ in CNF form with only and, or, and/or brackets How on earth would I even do this? Completely lost! Any help appreciated.
0
votes
1answer
44 views

Boolean algebra (ISO)

Let $\mathfrak{A}$ be a Boolean algebra and $E$ be an element in $\mathfrak{A}$. The set of all subelements of $E$ forms a Boolean algebra, denoted by $\mathfrak{A}_E$. Suppose that $I$ be the ...
0
votes
1answer
255 views

Boolean formula vs boolean function.

Is there a technical difference between boolean formulas and boolean functions?
1
vote
2answers
65 views

How to simplify this using boolean algebra?

My paper is due tomorrow and there is only the last exercise left for me to do. However, I don't have any sufficient notes or examples on how to simplify it. Any help would be appreciated! A'B'C' + A'...
0
votes
1answer
33 views

Explain one statement about Stone Space

In this page Stone Space This is no clear for me "The points in S(B) are the ultrafilters on B, or equivalently the homomorphisms from B to the two-element Boolean algebra" I think I means every ...
1
vote
1answer
53 views

What is the underlying math in this relation?

Suppose we have the constraint $$.7x_1+.4x_2+.5x_3<1,$$ $$x_1,x_2,x_3\in\{0,1\}$$ Then we can convert it to a Boolean expression with binary variables of the form $$(\neg x_{1}\wedge\neg x_{2})\...
2
votes
1answer
70 views

Can the obvious “product” of complete atomistic Boolean algebras be realized as a categorial product?

Let $X$ and $Y$ denote sets, and $\eta_X,\eta_Y : X,Y \rightarrow X+Y$ denote the natural injections to the disjoint union. Then intuitively, the "product" of the Boolean algebras $2^X$ and $2^Y$ ...
1
vote
1answer
65 views

Convert a Boolean expression to a linear expression?

Suppose we have a Boolean expression $$(\neg x_{1}\wedge\neg x_{2})\vee\left(\neg x_{1}\wedge\neg x_{3}\right),$$ which we need to be true. Is there a method to convert this to a linear expression of ...
0
votes
1answer
231 views

How can I get a product-of-sums from this sum-of-products?

I have this function: $$f(A,B,C,D) = A'B' + CD' + ABC + A'B'CD' + ABCD'$$ I used a Karnaugh map to minimize the function to: $$Minimum SOP = A'B' + C D' + A B C$$ How can I turn this into a ...
3
votes
1answer
32 views

Represent boolean OR opperator in non-boolean math notation

I'm trying to represent the boolean opperation OR in a regular formula, I am familiar with the boolean algebra notation, I came up with this (A+B)/(A+B) this works ...
0
votes
3answers
106 views

Can this Boolean expression be simplified any further?

I have simplified a Boolean expression to $$(\lnot a \land \lnot b \land \lnot c) \lor (a \land (b \lor c)).$$ Is there any way to simplify this further, e.g. using De Morgan's or anything?
0
votes
1answer
126 views

Proving that a given operator is universal.

I've got the next operator: $L(W,X,Y)=(W+Y)X'$ I need to prove whether the operator is universal, And if it isn't is: {$L,1$} or {$L,0$} are universal. I know that what i need to do is either ...
1
vote
3answers
72 views

Where did I go wrong with this Boolean simplification?

I am completely new to Boolean algebra, and I've tried to simplify this expression. All I did is tried to follow my lecturers methods, but I don't think it's right, and I have no idea how to do it. ¬...
0
votes
1answer
41 views

Do these equivalence classes have any special property!

Suppose that $\lambda$ be a measure on the interval $I=[0,1]$, and Let $\mathcal{N}$ be the family of null sets. It is known that "measure algebra $\mathcal{B}$ " is the algebra of all measurable ...
1
vote
2answers
54 views

My Boolean Expression Simplifications are correct or not?

1) I just want to know that my steps are correct or not? what are the missing steps. please help me. 2) Actually I can not simplify this is. So what are the missing steps at my trying path? please ...
0
votes
2answers
2k views

problem simplifying boolean algebra expression using consensus theorem

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 : Terms 1 & 3 ---...
1
vote
0answers
37 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
53 views

Boolean Expression Simplification

Dear all, I need help to simplify this Boolean algebra. Please give me a answer step by step. Thanks
2
votes
3answers
73 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
78 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 + ...
2
votes
4answers
469 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
24 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
360 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) = (x_1,x_2,x_3,...
-1
votes
2answers
2k 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'$$
1
vote
1answer
376 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
305 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
57 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
344 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
187 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
114 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
813 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: ...
0
votes
1answer
50 views

Homework: Conjunctive Normal Form

The way I understand CNF is as an expression containing AND's of OR's. So an AND-GATE with 3 inputs (A, B and C) should just be A AND B AND C. But apparently this is incorrect. Any guidance would be ...
2
votes
0answers
66 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
43 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
25 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
197 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$ $DNF=zwx'y'+zwx'y+zwxy'+zwxy+z'w'x'y'+...
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
50 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 $x,y\in\...
0
votes
1answer
55 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
52 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
426 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) + (A'B'C'D'...
1
vote
3answers
237 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
91 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 ...