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

Can anyone Simplify this Boolean expression?

The expression is: [AB {C+(BD)'} + (AB)']CD
1
vote
1answer
63 views

How can I express xNORy solely with NAND operations?

I've tried every which way I can think of to manipulate the algebra using the various laws I was given, but I cannot figure out a way to get $\overline{x+y}$ to convert to only NAND operations using ...
1
vote
1answer
101 views

Atomic Boolean lattice is weakly atomic

The book "Introduction to Lattices and Order" says at Exercise 10.12 that an atomic Boolean lattice is weakly atomic. Could you tell me why it holds?
1
vote
2answers
78 views

Construct countable Boolean algebra

How can I construct a countably infinite Boolean algebra with $n$ atoms, for $n \in \mathbb{N}$?
2
votes
3answers
5k views

Prove XOR is commutative and associative?

Through the use of Boolean algebra, show that the XOR operator ⊕ is both commutative and associative. I know I can show using a truth table. But using boolean algeba? How do I show? I totally have ...
2
votes
2answers
3k views

Simplifying the following expression using Boolean Algebra

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions . refers to AND + refers to OR a'.b'.c' + a.b'.c' + a.b.c' This is what I have so far. a'.b'.c' + ...
0
votes
2answers
19k views

How to convert between Sum Of Products and Product of sums?

I have a Boolean expression. we'll call it F. for instance, F = ab' + ad + c'd + d'. Assuming I did all the necessary steps ...
0
votes
2answers
102 views

Simplifying the expression using Boolean Algebra Part 2

Simplifying the expression using Boolean Algebra into sum-of-products (SOP) expressions . refers to AND + refers to OR Updated with new question ( (a + b) ∙ (a' + c') )' + (b + c')' + a∙b'∙c = ( (a ...
1
vote
1answer
287 views

Simplifying the expression using Boolean Algebra

Simplifying the expression using Boolean Algebra into sum-of-products (SOP) expressions . refers to AND + refers to OR (y' + x) ∙ (z + z') ∙ (y' + x') + (z + x'∙z) ∙ (x + y) This is what I have so ...
0
votes
0answers
56 views

Booleans: Solve Algebraically

Prove using Prove algebraically : 1) x'′⊕ y = x⊕y' = (x⊕y)' 2) x⊕1 = x' 3) x⊕x' = 1 4) (A+B)(A'C'+C)(B'+AC') = A'B $(A+B)(A'.C'+C)(B'+AC)' = A'B$ I know x⊕y = xy'+x'y But how do i deal with X'⊕Y? ...
6
votes
1answer
233 views

Non-isomorphic countable Boolean algebras

I'm trying to solve the next exercise: Construct a sequence $\mathcal{B}_0,\mathcal{B}_1, \ldots$ of countable Boolean algebras such that for all $m \neq n$ then $\mathcal{B}_m \ncong \mathcal{B}_n$. ...
0
votes
2answers
70 views

Boolean Simplification: Identifying a rule

I'm in the process of minimizing a boolean equation, and I've gotten it into the following form: $$\lnot B \lor (B \land \lnot C) \lor C$$ Just by looking at it, I can tell that this is always ...
0
votes
2answers
423 views

Product of Sums to Sum of Products

I apologize if this is a dumb question, but I'm having some trouble seeing how we can go from the Boolean equation ...
0
votes
1answer
108 views

Represent the three element chain as a subdirect product of subdirectly irreducible lattices.

Represent the three element chain as a subdirect product of subdirectly irreducible lattices. I know the two element chain as either a Boolean algebra or a semilattice,is subdirectly irreducible.In ...
0
votes
1answer
111 views

Help with simplifying boolean functions algebraically

I have 2 boolean functions that I am having some difficulty solving algebraically. NOTE: ~ means NOT, & means AND, + means OR 1) $(\sim b~\&~\sim d)+(b~\&~\sim ...
0
votes
1answer
456 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 ...
0
votes
2answers
342 views

Boolean Algebra equivalency

Which Boolean algebra laws are required to show that $$(\lnot y \land \lnot z) \lor (x \land ((\lnot y \land z) \lor (y \land \lnot z))) = (\lnot y \land \lnot z) \lor (x\land (\lnot (y \land ...
7
votes
1answer
191 views

Example of Boolean Algebra that satisfies distributive law but violates complete distributive law

More precisely, I'm interested to know the example of Boolean Algebra $B$, such that for any $a, b, c \in B$, $a \cap (b \cup c) = (a \cap b) \cup (a \cap c)$, but there exists $\{ P_{ij}:i\in I, j ...
2
votes
1answer
314 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 ...
1
vote
1answer
200 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, ...
1
vote
1answer
281 views

Composition of boolean function

In this problem we describe the boolean functions of $n$ variables like a vectors with lenght $2^n$ with standard assumption that $k$-th component of the vector $0\leq k \leq 2^n -1$ is thе value of ...
4
votes
2answers
313 views

Hypercube problem

$B$ is an n-dimensional hypercube, considered as undirected graph. Let $A$ be a subset of the vertices of $B$ such that $|A| \gt 2^{n-1}$. Let $H$ is a subgraph of $B$ induced by $A$. Prove that $H$ ...
5
votes
3answers
684 views

Counting Rows of a Truth Table that Satisfy a Condition

How can I mathematically count the number of rows in a truth table of n-inputs that will satisfy a certain boolean condition? For example, say I have a 4-input truth table that will in turn have 16 ...
0
votes
1answer
144 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
4k 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
100 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
157 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
166 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
115 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
260 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
624 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
180 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
125 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
73 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
86 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
203 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
110 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
175 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
265 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
50 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
294 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
431 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
220 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
188 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
107 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
488 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
155 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
107 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 ...