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

0
votes
2answers
21 views

Boolean bit OR operation on a Finite Field

How can I express $x \vee y$ in $GF_2$? I know that XOR is $GF_2[x]+GF_2[y]$ and AND is $GF_2[x]*GF_2[y]$ for instance. But I cannot figure out bitwise disjunction. This may be because OR does not ...
0
votes
0answers
64 views

Can a brouwerian lattice be extended into a boolean algebra?

Can an arbitrary brouwerian lattice (=locale = frame) be extended into a boolean algebra? What do I mean by "extended"? I don't know. All I know is that our brouwerian lattice is a sub-poset of the ...
1
vote
2answers
311 views

Boolean Algebra simplification: $X=((AB)'C(A'+(B+C)'))'$

I've had two statements I need to simplify, and I'm not sure about my work: $X=((AB)'C(A'+(B+C)'))'.\quad $ With this one, do you apply DeMorgan's theorem to the interiors of the brackets and ...
1
vote
1answer
129 views

Is an algebraic formula to test real numbers equality?

Is there a formula to test numbers equality ? Let $x$ and $y$ real numbers. If $x=y$ the formula will results $1$. Else the formula will results $0$. I'm not searching for an algorithmic solution ...
1
vote
1answer
563 views

Boolean Algebra Simplification - In sum of products form

How would you simplify this expression? I've been struggling with it for a while, but seem not to be getting anywhere near the right answer. Y = (A' + BD + C'D)' (B'CD')
0
votes
0answers
36 views

Hyperbent Boolean Circuit

Can anyone familiar with Boolean algebra show me an actual circuit diagram of a hyperbent Boolean function? I have not been able to find one in the literature. Thank you!
0
votes
1answer
88 views

How are boolean expressions converted to NOR expressions?

What kind of rules help to convert an expression into a 3 input NOR expression? Do all variables have to be of the form (a+b+c)' + (d+e+f)'? What happens if there is an expression that is just (a')' ...
0
votes
0answers
58 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 ...
1
vote
1answer
65 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 ...
5
votes
1answer
99 views

What is a (-1)-morphism?

So, I read the John Baez essay "Lectures on n-categories and cohomology" and I understand the notion of a (-1)-category" and a (-2)-category" and how to derive them. However, I'm not totally clear on ...
3
votes
1answer
301 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?
1
vote
1answer
31 views

If $G$ is a generic ultrafilter, why $(\exists a\in A)(a\in G)\leftrightarrow \Sigma A\in G$?

Let $B$ be a complete Boolean Algebra. Let $G$ be a generic ultrafilter of $B$, that is, such that for any dense $D\subset B$ we have $D\cap G\neq \emptyset$. Why for all $A\subseteq B,$ $\Sigma A\in ...
1
vote
0answers
345 views

Number of canonical expressions

There is a question: What is the number of canonical expressions that can be developed over a 3-valued boolean algebra? I was trying to solve this. Canonical expression is the combination of ...
1
vote
1answer
60 views

Fourier transformations in Simon's quantum paper

I am reading this paper by Simon. This is one of the earliest quantum algorithm papers. In the paper he presents a routine starting at the end of page six. The first step runs a Fourier transformation ...
0
votes
1answer
128 views

boolean algebra: DeMorgan's law confusion

the following function should be put into table values: $$y = \overline{(a*b*d+c)}$$ So the first thing i am doing is using DeMorgan to get rid of the "whole-term-negation": $$y = (\tilde a + \tilde b ...
2
votes
1answer
177 views

How to write boolean expression as linear equations 2

I just posted How to write boolean expressions as linear equations and asked about a simple example. Here's what we know so far: Suppose a,b,c,d,e ∈ {0,1}. if the boolean expression is: a ≠ b, I ...
1
vote
1answer
145 views

boolean algebra: simplify $ a* b *d + \tilde a *\tilde c*d + b* \tilde c* d$

Simplify the following function(algebraically): $$y = a*b*d + \tilde a *\tilde c*d + b *\tilde c *d$$ the solution is: $$a*b*d + \tilde a * \tilde c * d$$ which i checked via karnaugh and also ...
0
votes
1answer
50 views

Larger circuit design for same boolean function?

I've designed this circuit with 4 logic gates, and did Karnaugh map's simplification and Quine McCluskey method. However I found out that actually my circuit design is already optimized and I can't ...
0
votes
1answer
35 views

Distinct Karnaugh Maps grouping?

I got a table truth with some minterns which I mapped to a Karnaugh Map, then I can see an obvious choice for grouping. But I'm wondering wether in this case is possible to do any other different to ...
0
votes
1answer
60 views

Help at solving boolean function.

I`m having some difficulties solving a boolean expression (I am converting it to CNF form). The expression is: $$F = (Q_1 \to P1 \land \lnot P_2) \lor Q_1 \land P_2 \lor P_1$$ So i do not know, ...
3
votes
2answers
136 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 ...
2
votes
2answers
131 views

Is there a way to prove a boolean operator isn't universal?

In boolean algebra, I could prove an operator is universal by implementing a NAND or NOR gate with it. But is there a way to prove a boolean operator isn't universal? I would like to know a general ...
2
votes
1answer
148 views

Proving $(xyz)' = x'+y'+z'$

I'm trying to prove that $(xyz)' = x'+y'+z'$ using theorems/axioms. I tried this but I just want to make sure if its the correct route or if I've done something "illegal"/wrong. ...
1
vote
1answer
104 views

Binomial expansion through combinations.

If you have $(a+b)(c+d)(e+f)$ how can you expand this? Someone was mentioning that you get different combinations so that you get $adf+ade+acf+ace+bdf+bde+bce+bcf$? Is that the full expansion? As an ...
0
votes
1answer
184 views

Reduce to sum of products

I'm given the equation $F = (x+w)z' + x(y+z) + xz$ The inverse I got is $F' = [(x'+z)*(w'+z)]*[(x'+y')*(x'+z')]*[x'+z']$ To start I would expand $F'= [x'w' + x'z + zw'+zz] * [x'x' + x'z' + y'x' + ...
1
vote
0answers
216 views

Understanding Sum of product and complete sum of product

I have a pair of problems, the first two of my homework, and I'm already unclear on how finding SOP and CSOP for them work. The first: E=xy(1+z)y' It seems like this just reduces to 0, since 1+z ...
3
votes
1answer
104 views

Infix to Postfix

4 + x / b - a + 5 AND x AND y OR p OR q What is the tree and the postfix of the expression above? I find it tricky because I am not sure if AND has higher precedence than the arithmetic operators, ...
3
votes
1answer
174 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 ...
0
votes
1answer
198 views

Single Complement Variable + 1

Is a complement + 1 = 1? For example A' + 1 = 0; I was thinking it was (I'm new to boolean algebra) since A' = 0, and 0 + 1 in boolean algebra is just 1. Of course, A can be anything, but assuming ...
0
votes
1answer
78 views

Multiply the number $(1001)_{2}$ by 3 digit number

I want to multiply the number $(9)_{10} \rightarrow (1001)_{2}$ by a 3 digit binary number. 1) How I can extract the boolean equations? 2) Make a circuit of it. so what I did is just see what ...
0
votes
0answers
82 views

Can a Karnaugh map be solved in more than one way?

So I understand for doing a simplification by a K Map I should group my 1's (or even 0's) in $2^n$ elements, always trying to grup as much elements as possible. And I can group even adjacent elements ...
3
votes
2answers
212 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 ...
0
votes
1answer
104 views

Can't simplify this boolean algebra equation

So I've got an expression I have been trying to simplify and have the answer but I can't figure out how to get to it... can anyone help me out? Equation: $(A\wedge \lnot B \wedge \lnot C \wedge ...
1
vote
1answer
394 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: ...
0
votes
1answer
83 views

Logic Circuit Question

1) Write the boolean expression after every GATE 2) Write the boolean expression of GATE 3 3) Try to simplify the boolean expression of GATE3 I need to know if what I did its right + your advice ...
2
votes
2answers
98 views

Boolean simplification, 5 variables

I'm currently learning for my maths exam, and in the part about boolean algebra I came across an exercise that I can't seem to solve. I probably only need the first few steps to get started. $$ (xyz ...
10
votes
1answer
205 views

Stone's Representation Theorem and The Compactness Theorem

If you're working on $\mathsf {ZF}$ and you assume the compactness theorem for propositional logic, then you have the prime ideal theorem, and thus you can show that the dual of the category of ...
2
votes
3answers
172 views

Simplify Boolean Algebra

How do I simplify the following expression with Boolean Algebra? Please show what you used to simplify so I can understand. $$ABC + AB'C' + ABC' + A'B'C'$$
0
votes
1answer
370 views

The input represent a 4-bit unsigned binary number, the output W, is 1 if the number is multiple of 2 or 3 but not both.

I completely understand how to make a truth table and the entire concept of boolean algebra. However, I am confused how to make the truth table for the above information. Because the input is a 4-bit ...
3
votes
1answer
60 views

maximal antichain

I don't understand the definition of Jech (set theory) for "maximal antichain". Let $B$ a boolean algebra and $A$ a subalgebra of $B$. $W\subseteq A^+$ is a maximal antichain if $\sum W=1$ and $W$ ...
0
votes
2answers
103 views

Why is $ab + bc + c\bar{a} = ab + c\bar{a}$ true in binary?

I was simplifying the equation of a logic gates problem and I realized that ab + bc + cā and ab + cā followed the same truth ...
5
votes
2answers
168 views

Which law of logical equivalence says $P\Leftrightarrow Q ≡ (P\lor Q) \Rightarrow(P\land Q)$

I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
1
vote
1answer
41 views

completeness and saturation

Let $B$ a complete Boolean algebra. Suppose, for $\kappa$ cardinal, that $B$ is not $\kappa$-saturated. Then there exists a partition $W$ of $B$. Because of completeness, we have $B=\sum W\in B$. So ...
0
votes
1answer
4k views

How to simplify in boolean algebra

I have some homework I can't seem to figure out. The assignment causing problems is devided into two parts; The first is to determine the inverse formula for a given formula (so the S = F'). The ...
0
votes
3answers
380 views

Simplifying Boolean Algebra

I am trying to prove that BC + !A!B + !A!C = ABC +!A I have attempted using De Morgan laws, and substituting X for !A!B and ...
10
votes
2answers
321 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: ...
1
vote
1answer
92 views

Isomorphism Subalgebra

Given, the unit interval $I$ endowed with the Lebesgue measure $\mu$, and let $A$ be the (Boolean) algebra of Jordan measurable subsets of $X$ with respect to $\mu$, (i.e. those sets that satisfying ...
7
votes
3answers
413 views

Rationale behind truth values

I originaly asked a question on Programmers.SE to know why $0$ was consider $\text{false}$ and all the other [integral] values were considered $\text{true}$. That was a huge debate and many said it ...
0
votes
2answers
41 views

Generalization of Boolean OR?

I have been looking at the Boolean OR function and Im trying to find its integral analogue. What I mean is: Boolean AND (x, y) where x and y are Boolean Values with 0 = False, 1 = True is equivalent ...
2
votes
0answers
38 views

Inferring simplest method to convert bit array 1 to bit array 2.

Consider the set of all bit arrays of length $n$. Now consider the set of all 1-to-1 functions that map from this set to this set. Now select a single function out of the latter set. Is there any ...