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
1answer
150 views

An exercise of Boolean algebras

On page 87, Introduction to Boolean Algebras,Steven Givant,Paul Halmos(2000) Give an example of a subalgebra $B$ of a Boolean algebra $A$ and of a subset $E$ of $B$ such that $E$ has a supremum ...
2
votes
2answers
5k 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) \\ ...
1
vote
0answers
105 views

Question regarding implicant chart of Quine-McCluskey algorithm

In https://en.wikipedia.org/wiki/Quine-McCluskey#Example, at the end of Step 1, there is a table that shows the number of 1's, minterms, 0-cube and size-2 implicants and size-4 implicants. But I am ...
2
votes
1answer
158 views

Infitive distributive law in boolean valued models

I'm posting the problem 2.14 and 2.15 of the book "Set theory" of J.L. Bell. These problem are proposed after the forcing relation chapter and I'm new in this kind of stuff, so I have some little ...
3
votes
2answers
171 views

Prove $(x+yz)(y'+x)(y'+z')=x(y'+z')$ in Boolean algebra

How can we prove $(x+yz)(y'+x)(y'+z')=x(y'+z')$ in a Boolean algebra $B$?
1
vote
1answer
139 views

Question on a mapping between a Boolean algebra and an algebra of sets

On page 81, Set Theory, Jech(2006), to prove the Stone's Representation Theorem, a mapping $\pi$ is defined as Let $B$ be a Boolean algebra. We let $$S=\{p:p \text{ is an ultrafilter on }B\}.$$ ...
2
votes
4answers
119 views

Proof that $B \land ( B \lor C) = B$?

In my logic design exam today I was given this question: Show that: $$ B \land ( B \lor C) = B $$ It's asking for a proof for this expression. Could someone please explain how such expression ...
6
votes
1answer
302 views

Definitionally equivalence between Boolean algebras and Boolean rings

On page 17, Introduction to Boolean Algebras,Steven Givant,Paul Halmos(2000): Motivated by this set-theoretic example, we can introduce into every Boolean algebra $A$ operations of addition and ...
6
votes
3answers
734 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 ...
1
vote
0answers
225 views

When to Stop Simplifying a Well-Formed Formula?

I mean simplifying a wff(well-formed formula)in which, only $\lor$, $\land$, $()$and $\lnot$ are allowed, as minimizing the occurence of connective symbols( $\land$ and $\lor$). It's self-evident ...
5
votes
1answer
126 views

How to multiply out a statement form?

I got this form: (not M or V) and (A or not M) and (not B or M) and (B or V) and (A or not V) and (not A or B) Or: $$(\neg M\vee V) \wedge (A\vee\neg M) \wedge (\neg B \vee M) \wedge (B\vee ...
3
votes
1answer
74 views

Find the solutions of Boolean equations

It's given 4 Boolean equations. I need to find the number of solutions of each. $a)\ x_{1}x_{2}\oplus x_{2}x_{3}\oplus\ ...\ \oplus\ x_{n-1}x_{n}=1$ $b)\ x_{1}x_{2}\vee x_{2}x_{3}\vee\ ...\ \vee\ ...
0
votes
1answer
95 views

Manipulation of Axioms for Boolean algebras

The laws of Boolean algebras are given. The identity laws (13): $p \land 1 = p$, $p \lor 0= p$, the complement laws (14): $p \land p' = 0 $, $p \lor p' =1$, the commutative laws (18): $p \land q = ...
0
votes
1answer
281 views

Solve Boolean system of equations

How can I solve a set of boolean equationst to get a,b,c and d. Like: w = a*b*c*d x = !a*b*d y = !b*a*d + !c*a*d + !a*b*c + !d*!a*b z = a*c w, x, y, z are ...
0
votes
1answer
126 views

general strategies for maximizing boolean simplification from a specific example

I'm trying to completely simplify $$F_0 =A' B' C' D' + A' B' C' D + A B' C' D' + A B' C' D + A B' C D$$ I got as far as $$\begin{align} &= A’B’C’ + A B' C' D' + A B' D\\ &= A’B’C + ...
1
vote
1answer
187 views

Problem 1.30 (The Maximum Principle is equivalent to the axiom of choice) (J.Bell, Boolean-valued Models and Independence Proofs, 3rd edition)

Problem 1.30 (The Maximum Principle is equivalent to the axiom of choice) (i) Let $\{a_i : i ∈ I\} ⊆ B$ satisfy $\bigvee_{i∈I} a_i = 1$. A partition of unity $\{b_i : i ∈ I\}$ in B is called a ...
1
vote
0answers
353 views

Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
1
vote
2answers
53 views

Boolean algebra proof - point me in the right direction?

I wish to formulate a proof that if $x+y = x+z$ and $xy$ = $xz$ then $y=z$. I'm just beginning my study of Boolean algebra, but is $y=z$ not self evident from the stated equations?
2
votes
1answer
378 views

Boolean Algebra on Circuits

Can I use boolean algebra to simplify electric circuits installed on buildings, establishments (etc.) using the blueprint of the buildings fluorescent lamp circuit system and electric fan circuit ...
1
vote
4answers
599 views

Knights and Knaves

A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie. You meet four inhabitants: Bozo, Marge, Bart and Zed. Bozo says," ...
1
vote
1answer
278 views

What does the complement mean as it relates to Boolean Algebra?

For a lattice to be a Boolean Algebra it must be a distributive lattice and contain complements. What does the word complement mean?
3
votes
3answers
217 views

A function whose value is either one or zero

First I apologize in advance for I don't know math's English at all and I haven't done math in almost a decade. I'm looking for a function whose "domain/ensemble of definition" would be ℝ (or maybe ...
1
vote
1answer
123 views

The cardinality of finite Boolean lattice

A book (Introduction to Lattices and Order) says that we can prove that the cardinality of any finite Boolean lattice $B$ is a power of 2 by induction on $|B|$ with the following lemma: If a lattice ...
1
vote
1answer
489 views

Simplifying Boolean Expression

I am asked to simply the following expression $$F(a,b,c) = c’ab + c’b’ + aba + b’cb + abc + c’b$$ using the Boolean identities and finding $F'(a, b, c)$ using DeMorgan’s law I have been trying for ...
0
votes
1answer
3k views

Boolean algebra - sum of products form

I have a logic circuit where the output can be represented with the following boolean expression (1)$\overline {xy}$ + x $\bar y z$ + $\overline {\bar x + z} $ + y Using truth tables I found the ...
1
vote
2answers
167 views

Semantic parsing of a sentence from “The mathematical analysis of logic” By Goerge Boole, 1847

Having the pleasure of reading some original text, I was wondering if someone can translate two small statements on the second half of page 11 from ...
2
votes
1answer
115 views

Is it possible, in Boolean Algebra, to add arbitrarily a new term to both sides of an expression?

First of all, i'm sorry for my english. I'll try to do my best to explain myself. I've been trying to look for it on the internet, but i'm not sure about the answer. I hope someone can help me here ...
1
vote
2answers
1k views

Simplifying boolean function using boolean algebra

How to simplify the following expression : A'BCD + AB'CD' + AB'CD + ABC'D + ABCD' + ABCD ? It should get AC + BCD + ABD using Kmap but using boolean algebra i am stuck no matter how i try .
0
votes
2answers
209 views

Element chasing style proof applied to Boolean algebra problem

I would like to apply an element chasing style proof to the following problem: Let $P$, $Q$ and $R$ be elements of a Boolean algebra. Prove that if $$ \tag 1 P + Q = P + R$$ and $$\tag 2 P ...
2
votes
1answer
54 views

Does a complete subalgebra A of a complete boolean B algebra always intersect all dense subsets of B?

I'm trying to show that if $(B, i)$ is the (BA) completion of any partial order $P$ and $A$ is a complete subalgebra of $B$, then $i^{-1}[A]$ is a complete suborder of $P$. Pure hunch says it's ...
0
votes
1answer
88 views

Give all Boolean algebras on the finite set

Given a finite set $X=\{1,2,3\}$, are the following all the Boolean algebras? $A_1=\{\{1\},\{2\}\},$ $A_2=\{\{1\},\{3\}\},$ $A_3=\{\{2\},\{3\}\},$ $A_4=\{\{1\},\{1,2\}\},$ $A_5=\{\{1\},\{1,3\}\},$ ...
1
vote
2answers
5k views

Simplifying Boolean Function with Karnaugh Maps

Given the boolean function f(x,y,z) = xyz + xyz' + xy'z + xy'z' + x'yz + x'y'z + x'y'z' (where x' = not x) In a three variable Karnaugh Map: ...
1
vote
1answer
239 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 ...
0
votes
1answer
151 views

Boolean Algebra Simplification Help, Need AND's, OR's, NOT's only

I'm having a very hard time simplifying this: A!B!C+ABC+!A!BC+!AB!C The objective here is to simplify the equation until it can be expressed in "AND"'s "OR"'s and "NOT"'s. I have to create an ...
1
vote
1answer
63 views

If X is a subset of a complete boolean algebra, must there be a finite $Y \subset X$ s.t. sup(Y) = sup(X)?

The question came up when I was trying to prove the compactness of the stone space S(B) of a complete boolean algebra B. Using only the basic facts regarding ultrafilters and boolean algebras, I ...
0
votes
2answers
93 views

Is this boolean algebra problem solvable?

My professor is of no help at all. He's foreign and is giving assignments that are written poorly, and is teaching stuff far beyond what he's supposed to be teaching at this level. Nonetheless, he's ...
1
vote
1answer
541 views

Boolean Algebra Distributive Laws

Given that $x\cdot(y+z)=(x\cdot y)+(x\cdot z)$ and $x+(y\cdot z)=(x+y)\cdot (x+z)$, what is the name for the opposite of those rules? Say I'm trying to prove the opposite, and I need to simplify from ...
1
vote
1answer
633 views

compare 3 variables in MATLAB

I am wondering how to compare 3 variables in MATLAB, because MATLAB is comparing first 2 and then result against 3rd. To illustrate with example: (-1 == -1 == -1) ans = ...
2
votes
2answers
68 views

Is there a name for the set $\{T,F\}$?

Is there a name for the set containing the two Boolean values, i.e. $\{T,F\}$? I am also thinking if $B = \{T,F\}$, and $B^n = \underbrace{B \times B\times B ... \times B}_n$, then is there a proper ...
1
vote
2answers
802 views

Boolean Simplification: (A+C)(!A+B)(B+C) = BC

How might I solve this? I can't find any problem similar to this, and I always end up with the wrong terms. If (AB) = 0 and (A+B) = 1, prove that (A+C)(!A+B)(B+C) = BC
3
votes
3answers
139 views

Boolean Algebra

There seems to be some discrepancy between my answer and the solution's. Can somebody please tell me what I have done wrong? Thanks! $$\begin{align} \left(A \lor B\right) \land \left(B \lor C\right) ...
0
votes
2answers
79 views

toggle boolean and more

Recently I used this to toggle a Boolean value, b being the current value and self.status being the result self.status = (b-1)*(b-1) This rather than use an if ...
5
votes
2answers
539 views

calculating number of boolean functions

I would just like to clarify if I am on the right track or not; I have these questions: Consider the Boolean functions $f(x,y,z)$ in three variables such that the table of values of $f$ contains ...
0
votes
2answers
226 views

is the following a Boolean Algebra?

Boolean Algebra: $$D_{30}=\{n:n\mid30\}= \{1,2,3,5,6,10,15,30\}$$ I don't know how to test that this is a boolean algbra (a BA is a distributive lattice with $T,F$ in which every element has a ...
0
votes
1answer
110 views

Proving if equations are products of XOR

I have to prove analytically to see if these equations are exclusively or. $$A⊕ A=0$$ Do I solve this by using the truth table? ...
1
vote
0answers
86 views

Generating Input Binary Combination Dynamically

this is probably right forum to post this question I am currently working on a application where there is a requirement to generate binary combination of input signals in a truth table. The signal ...
0
votes
2answers
541 views

Show that $x \wedge y = x \iff x \vee y= y$ using the following properties

Suppose $L$ is a set with binary operations $\wedge$ and $\vee$, along with the special $T$ and $F$ (for an $x,y,z \in L$) such that the following rules hold: $x\wedge T=x$; $x\vee y=T$ ...
1
vote
1answer
91 views

How to prove distributivity in Boolean Rings

A Boolean ring is a ring which all of its elements are idempotent, i.e. $a ^{2}=a$. I know that If we interpret multiplication and addition in such a ring, as meet and joint respectively, then Boolean ...
0
votes
1answer
236 views

Boolean simplification

So I am giving this expression D +B’C’ + CD’ +A B’C and I ask to simplify it When working through it I get D+B'C'+CD'+AB'C D'(A'B'+CD'+AB) D'(A'B'+A(B'+B)) D'(A'B'+AC') D'(B'+A) Am I on the right ...
0
votes
1answer
75 views

Boolean Function

A Boolean expression is given: (A B)’ + B C’ +A’ C = F. Construct the logical circuit and draw the timing diagram of the output F. I am not sure where to start.