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
201 views

Boolean Algrebra: Karnaugh Map

Using the Karnaugh map, express the following function: F(0, 1, 4, 5, 8, 10, 11, 12, 13, 15)
0
votes
2answers
178 views

Every boolean function is constructed from $\wedge$'s and $\vee$'s

Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. Here is my solution, can I ask for a feed back on my solution please? $p∧q$ ...
16
votes
2answers
796 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$, ...
2
votes
1answer
763 views

Boolean Algebra, Simplification: Don't know the method used

Here's the Karnaugh map: The answer I should be getting from the Karnaugh should be: T = R ∙ (CGM)' I'm really not seeing how this was arrived at through any ...
10
votes
2answers
310 views

A matrix w/integer eigenvalues and trigonometric identity

Any intuition and/or rigorous arguments on the proofs of the following statements would be appreciated: Let $n$ be a natural number. (a) Consider the following Toeplitz/circulant symmetric matrix: ...
0
votes
2answers
64 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 ...
2
votes
2answers
204 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 ...
1
vote
2answers
50 views

Assignment for discrete mathematics

How can I prove that not every boolean function is equal to a boolean function constructed by only using ∧ and ∨?.Need help in proving it.
1
vote
3answers
57 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. ...
1
vote
1answer
570 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
2k views

How to prove that a set of logical connectives is functionally complete(incomplete)?

How to prove that a set of logical connectives is functionally complete(incomplete)? For example, we are given this set: $ \left\{\begin{matrix} f = (01101001) \\ g = (1010) \\ h = (01110110) \\ ...
0
votes
1answer
99 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)}} $$
10
votes
7answers
5k views

Is XOR a combination of AND and NOT operators?

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?
4
votes
6answers
2k views

how to solve system of linear equations of XOR operation?

how can i solve this set of equations ? to get values of $x,y,z,w$ ? $$\begin{aligned} 1=x \oplus y \oplus z \end{aligned}$$ $$\begin{aligned}1=x \oplus y \oplus w \end{aligned}$$ $$\begin{aligned}0=x ...
4
votes
1answer
195 views

Lindenbaum algebra is a free algebra

The following is a continuation of this question. I would like to prove that the Lindenbaum algebra is a free algebra. Hopefully I would like to hear hints on how to proceed in the 'right' ...
3
votes
2answers
111 views

How to write boolean expressions as linear equations

I want to convert a set of boolean expressions to linear equations. In some cases, this is easy. For example, suppose $a, b, c$ $\in$ {0,1}. Then if the boolean expression is: $a$ $\ne$ b, I could use ...
3
votes
3answers
158 views

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an ...
2
votes
1answer
217 views

Free boolean algebra

Consider the following definition: Let $X$ be a set and $e : X \mapsto A$ a mapping to a boolean algebra $A.$ We say that $A$ is free over $X$ (with respect to $e$) if for every mapping $f:X ...
2
votes
1answer
111 views

Extending the logical-or function to a low degree polynomial over a finite field

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Is there ...
1
vote
1answer
183 views

Fiction variables?

In every Boolean function $f(x_1, x_2,\ldots, x_n)$, for every $i$ ($1\le i\le n$), $x_i$ is called fiction variable if and only if when for every Boolean assessment for the rest variables $x_1, ...
0
votes
1answer
51 views

Boolean Queries in First Order Logic

I understand first order logic and how its constructed but I have some trouble understanding how the following statement and its FO query are formed. This is from a book. ...
6
votes
3answers
460 views

How to prove a set of sentential connectives is incomplete?

On Page 52, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Show that $\{\lnot, \# \}$ is not complete. A set of connective symbols is complete, if every function $G : \{F, T\}^n ...
6
votes
2answers
188 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
5
votes
3answers
2k views

Simplify $A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$

How do you simply the following equation? $$X = A'B'C'D' + A'B'CD' + A'BCD' + ABCD' + AB'CD'$$ Here is what I did: $$\begin{eqnarray} X & = & A'B'C'D'+A'CD'(B'+B) + ACD'(B+B') \\ & ...
3
votes
1answer
40 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 ...
3
votes
1answer
167 views

Proof of $(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge (Q\Rightarrow P))$

Hi I've been working through Applied Mathematics for Database Professionals and I'm stuck trying to proof this equivalence: $$(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge ...
3
votes
2answers
192 views

Is it possible to derive all the other boolean functions by taking other primitives different of $NAND$?

I was reading the TECS book (The Elements of Computing Systems), in the book, we start to build the other logical gates with a single primitive logical gate, the $NAND$ gate. With it, we could easily ...
3
votes
1answer
277 views

Cardinality of the set of ultrafilters on an infinite Boolean algebra

Let $\mathfrak B$ be a Boolean algebra with an infinite power $\kappa$. My question is how many ultrafilters does it have? $\kappa$ or $2^\kappa$? Or even smaller?
3
votes
4answers
1k views

An “atom” in Boolean algebra

Could someone explain what an atom in Boolean algebra means? I am acquainted with ring theory and group theory but not Boolean algebra. As far as I can tell from browsing around, it is something like ...
2
votes
1answer
61 views

What does quotienting by a congruence mean?

I have come across quotient algebras in my different mathematics courses. I know of quotienting with normal groups, quotienting with ideals etc. While studying Boolean Algebra I encounter quotienting ...
2
votes
2answers
124 views

How to prove that $(A \lor B) \land (\lnot A \lor B) = B$

I know this is fairly basic, and I understand that it becomes $$ \begin{align} (A \land \lnot A) \lor B \\ F \lor B \\ B \end{align} $$ However, I can't work out how to prove that it becomes that ...
2
votes
1answer
2k views

Boolean Algebra - Product of Sums

I converted from a truth table to sum of products and simplified that easily. What I am having problems with is simplifying the product of sums for that same truth table. I have: NOTE: $A' = ...
2
votes
1answer
245 views

Number of non degenerate boolean functions

I got in my lecture the formula that describe the number of nondegenerate Boolean functions of $n$ variables (or how many boolean functions have no fictitious variables), but we don't have proof for ...
2
votes
3answers
7k views

Boolean Simplification of A'B'C'+AB'C'+ABC'

My question is how do I reduce A'B'C'+AB'C'+ABC' (note that (') stands for a bar over the letter). To get (A+B')C'. I'm so lost just been trying to get it for awhile only using the 10 boolean ...
1
vote
1answer
66 views

Whats wrong with this reasoning…

Suppose I have two non-distinguishable balls (for example two white ones) and I color them with red and green, then a combinatorial reasoning could go like this. Suppose I enumerate the balls, ball ...
1
vote
1answer
29 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 ...
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 ...
1
vote
1answer
43 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 ...
1
vote
1answer
61 views

Deriving truth table from English description

I'm trying to check if my truth table is correct since it largely depends on further parts of a larger problem. Here is the English description: The controller will turn on the headlights under the ...
1
vote
1answer
441 views

Implement using only XOR gates F=A'B'C'D+A'B'CD'+A'BC'D'+A'BCD+AB'CD

How can we implement the function: F=A'B'C'D+A'B'CD'+A'BC'D'+A'BCD+AB'CD without simplifying it and using ONLY XOR gates (not using AND/OR gates) ? NOT gates are usable too, since they can be ...
1
vote
1answer
3k views

Boolean Algebra, 4-variable Expression Simplification

I have the following Boolean expression: $$w'x'y'z + wx'y'z + xz + xyz'\tag{1}$$ Upon doing my own work, I can only get as far as: $$zx + xy + zy'\tag{2}$$ Now, when I put the original equation ...
1
vote
1answer
148 views

Find an optimal 4-tuple which satisfies a boolean expression

(I have post a question with bounty for several days (Find a best 4-tuple which fulfils a variable boolean formula), but unfortunately got no answer yet. Here I simplify it to a smaller problem and ...
1
vote
1answer
354 views

How many presentable boolean functions with n attributes are linear separable?

The aim is to find a formula for the question. For n=2 i get (2^(2^n)=16 possible functions. This is the solution for a boolean function with 2 attributes: ...
1
vote
2answers
415 views

boolean algebra - theorems

I have a homework question "Show the following is true using theorems. State which theorem you use at each step." This is just one of many problems I have! So, if you can help me with this one problem ...
0
votes
0answers
47 views

Whats wrong with this reasoning… A Textbook Example?

This question is directly related to another one, as I see it the faulty reasoning is applied in the proof I will giving next: Lemma: Suppose we have $b$ boolean functions with two arguments (like ...
0
votes
1answer
30 views

Homomorphism between a ring which is a boolean algebra and one which is not.

I remember reading in a textbook that there can exist a homomorphism between a ring which is a boolean algebra and one which is not. Can anyone give me some example of this.
0
votes
3answers
133 views

Using rules of inference (Leibniz) to prove theorems.

Leibniz: If $A \equiv B$ is a theorem, then so is $C[p:= A] \equiv C[p:= B]$. Note: p is "fresh" means p doesn't occur in $A, B, C$. I am trying to understand how to use Leibniz rule of inference for ...
0
votes
3answers
78 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
2answers
274 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 ...
0
votes
0answers
56 views

Modify boolean equation to get 3 input NOR equation using boolean algebra rules

I was taking a look at this link http://lizarum.com/assignments/boolean_algebra/chapter3.html to try and solve an equation I have. The original equation is: H = MC + MC' + CRD + M'CD' I simplified ...