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
2answers
114 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
96 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 ...
0
votes
2answers
125 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
votes
1answer
141 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!!
0
votes
1answer
111 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
1answer
84 views

Is it properly applied the Quine McCluskey algorithm by this?

I'm writing some code for implementing the Quine McCluskey algorithm and I simply need to clear out if my logic for implementation is ok. I get some number of minterms and combine each of them so ...
1
vote
1answer
1k views

Full Adder boolean Algebra simplification

I have an expression here from the Full Adder circuit, used for binary addition. One equation used to make it work, is this one: $$C = xy + xz + yz \tag{1}$$ Now, the book transforms this equation ...
1
vote
1answer
174 views

Converting into CNF Form

If you have disjunctive clause comprising of n literals for example $(X_1\cup X_2\cup X_3\cup\cdots \cup X_n)$. where $n\geq 4$. How you can convert it into CNF (Conjunctive Normal Form) of $n-2$ ...
0
votes
3answers
70 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
32 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 ...
0
votes
1answer
119 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 ...
2
votes
2answers
212 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
vote
1answer
183 views

Transforming statements of a query language to propositional logic

I have a custom query language which expresses containment relations between variables. Containment in this context is simply an object (A) in programming language X (java/C#/python etc: a language ...
-1
votes
1answer
468 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
451 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 ...
3
votes
1answer
42 views

Looking for an algebraic structure

I'm looking for the name of algebraic structures (in which the elements are partially ordered) with the following properties: Top element defined, bottom optional; Join defined for all elements, ...
1
vote
3answers
425 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
1answer
147 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
49 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
43 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 ...
1
vote
2answers
256 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 ...
6
votes
2answers
200 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
5
votes
1answer
106 views

Independent families versus generators in boolean algebras

Let $\kappa$ be an infinite cardinal. A family $\mathcal{A} \subseteq \mathcal{P}(\kappa)$ is independent if, for all $A_1,\ldots,A_n\in\mathcal{A}$ and $i_1,\ldots,i_n\in\{0,1\}$, we have $$ ...
1
vote
0answers
24 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 ...
2
votes
0answers
94 views

Matrix of integers to boolean matrix

My Question is about converting a matrix of numbers, say each row is an item and each column is a feature of the item. The features are currently integers but I want to convert the feature ...
1
vote
1answer
221 views

Check if tautology (w/o truth table)

$(A+B)(A+C)(B+C) = AB + AC + BC$ is a tautology (checked with Wolfram Alpha) and not hard to see if you apply duality principle $(invert + * 0 1)$ But how to prove with simplyfication It'S not much ...
2
votes
2answers
63 views

Ist it a tautology w/o truth table

AB + CD = (A+C)(A+D)(B+C)(B+D) is a tautology (checked with wolfram alpha) I have to prove this whith boolean algebra but I don't get it right. That'S what I have: AB + CD = A(C+D)B(C+D) AB + CD = ...
3
votes
3answers
162 views

Existence of maximal boolean-algebra sublattice (preserving top and bottom) of finite distributive lattice

If I regard a modal logic as some sort of many-valued logic, a "modal operator" projecting into a classical propositional logic context could sometimes be useful. Such an operator would provide a ...
0
votes
1answer
24 views

Create a simple expression that is larger than zero if and only if a-b > 0 and c-d < 0

Ok, this is simple but I cant figure out a solution to it. I have four signals, a, b, c, d. I want to generate a signal when a-b > 0 and c-d < 0. This signal should be in the form of an algebraic ...
1
vote
1answer
44 views

Are ordinal spaces extremally disconnected?

The wikipedia article on ordinal spaces claims that they are not extremally disconnected: However, they are not extremally disconnected in general (there is an open set, namely $\omega$, whose ...
0
votes
1answer
127 views

Using induction to prove universality of gate

Can we use induction to prove gate(like NAND) is universal. If so how?
0
votes
1answer
243 views

How can you design a 3 bit adder using a 4 bit adder?

How can you design a 3 bit adder using a 4 bit adder? The description and/or the circuit's scheme would be great.
-1
votes
1answer
68 views

Product of Sums Minimzation. Please help! [closed]

Minimize the product of sums expression. (x + y + z!)(x + y! + z)(x + y! + z!) Please help! I am not sure whether to factor out by grouping or to factor out a x etc.
1
vote
1answer
497 views

Boolean Logical Algebra - Prove 4 nor gates to an xnor gate.

Need to reach the following conclusion (or maybe its the premise?) AB + A'B' = F http://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/XNOR_using_NOR.svg/256px-XNOR_using_NOR.svg.png
0
votes
3answers
476 views

Boolean-expression simplification F = [ AB ( C + (BC)' ) + AB' ] CD'

Basing on that problem. All I have in my solution is this: mystep1:[AB(C +(B' + C')) + AB']CD' mystep2:[AB(CB'+ CC') + AB']CD' mystep3: [AB(CB') + AB']CD' mystep4:[B(A+C+B') + ...
2
votes
1answer
189 views

Solving Boolean Expressions with Theorems

I'm having the hardest time wrapping my head around this stuff. This is a homework problem, one of many. I just need some help on what to do. ...
4
votes
1answer
81 views

Ideal:Kernel :: Filter:?

I understand that the notion of a filter is in some sense dual to the notion of an ideal, at least in the context of Boolean algebras1. Let $f:{\mathbf A} \to {\mathbf B}$ be a Boolean algebra ...
1
vote
2answers
39 views

Question about poset and boolean ordering, inf and sup

We have a poset $(X, \sqsubseteq)$, and we define operations $+$ and $\cdot$ by $x+y=inf(x, y)$ and $x\cdot y=sup(x, y)$ ($+$ can be seen as union in sets and $\cdot$ as intersection in sets). The ...
0
votes
1answer
81 views

Condition for the boolean algebra of clopen sets to be extremely disconnected.

Let $X$ be a topological space and let $\Gamma \mathcal O(X)$ be it's boolean algebra of clopen subsets. For compact totally disconnected space, show that $\Gamma \mathcal O(X)$ is complete (as a ...
1
vote
0answers
152 views

Sum-of-products to product-of sums conversion

I need to convert $A'B'C'$ from sum-of-products form to product-of-sums form. I used a K-map and I'm not sure if the answer is $C' + AB' + A'B' + A'B$ or just $AB' A'B' + A'B$. I think that by ...
1
vote
2answers
45 views

Boolean simplification of $AB'(B' + C)$

Simplifying $AB'(B'+ C)$, then using the distributive property I know I would get $AB'B' + AB'C$ I am just confused as to how to simplify $B'B'$
0
votes
1answer
72 views

Correctness of answers and question about sup en inf

In $A=\{2, 3, 6, 12, 36, 72, 108\}$ we define the relation $R$ by $aRb$ if $b=a$, or $b=2a$ or $b=3a$. Q1: Draw the graph of $R$ and list which properties $R$ has. A1: The properties are: ...
2
votes
1answer
67 views

Can a minimal representation of a Boolean Function be 1 or 0

After using the Karnaugh map to find the minimal representation of a Boolean function, my answer is 1. Is 1 a valid answer for minimal representation? If yes, what is the implication of a Boolean ...
4
votes
4answers
6k views

Duality principle in boolean algebra

All the definitions I came across so far stated, that if a statement is true, then also its dual statement is true and this dual statement is obtained by changing + ...
2
votes
2answers
95 views

Order of operations for logic operations?

I have some code, that does a comparison to find how many of set of values fall within a range defined by a mean±sd, like this: ...
0
votes
2answers
71 views

How to prove boolean ordering question

Let $\sqsubseteq$ be the boolean ordering of $X$, so for every $x$ and $y$ applies $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v \sqsubseteq a$ and $w \sqsubseteq b$. Show that ...
29
votes
1answer
1k views

Universal binary operation and finite fields (ring)

Take Boolean Algebra for instance, the underlying finite field/ring $0, 1, \{AND, OR\}$ is equivalent to $ 0, 1, \{NAND\} $ or $ 0, 1, \{ NOR \}$ where NAND and NOR are considered as universal gates. ...
0
votes
1answer
48 views

How do I solve this Boolean Algebra Problem?

Let A be an arbitrary but fixed Boolean algebra with operator $@$ and $*$ and $'$ and the zero and unit element be denoted by $0$ and $1$ respectively. let $x,y,z \in A$ if $a,y \in A$ such that ...
1
vote
1answer
53 views

Boolean Algebra: Explain why (M AND (NOT N)) OR (X AND M AND N) = (M AND NOT N) OR (X AND M)?

I have no idea how this is true, by what theorem, and I literally have been thinking about this for 3 hours now. I know it's really simple, but I just must not be in the right mindset to discover ...
2
votes
1answer
39 views

Need help for right direction simplifying boolean algebra formula

I have the following boolean algebra, where union is $+$ and intersection is $\cdot$ : $(x\cdot y)+((z+y)\cdot \bar{z})+y=y$ Is there a systematic way of doing this, or do you need to puzzle? My ...