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

-1
votes
0answers
13 views

Trying to design combinatorial circuit

How do I figure out the design combinatorial circuit for $\bar pr + q$ $[(p\bar q) + (r + q)]s$ I cannot see to get the concept of doing that.
-2
votes
2answers
33 views

How to simplify this expression [on hold]

How to simplify AB(A+B)(C+C), I tried but it did not seems to be coming out correctly not sure why.
0
votes
1answer
691 views

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions $Q.S.U + (Q' + S').(R + V) + U.(R + V) + Q' + S.T.U$ $.$ = AND $+$ = OR This is what I have so far ...
0
votes
1answer
29 views

A question about a generated $\sigma$-algebra of a family set

Wikipedia's definition of Family of sets: In set theory, a collection $F$ of subsets of a given set $S$ is called a family of subsets of $S$, or a family of sets over $S$. So suppose $Ω$ is ...
6
votes
1answer
117 views

Construct an OR gate when missing input information

Is there a way to construct an OR gate when the input for one combination is unknown? For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = ...
2
votes
1answer
66 views

Proving $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ using Fitch notation

I'm supposed to prove the validity of the following $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ I'm very new to natural deduction, so I still haven't got a "feel" about it. I can prove ...
4
votes
1answer
67 views

extending automorphisms in complete boolean algebras

Suppose $A$ is a complete subalgebra of a complete boolean algebra $B$. Suppose $f : A \to A$ is an automorphism. Then $f$ can be extended to an automorphism of $B$. I can see this using the fact ...
2
votes
4answers
120 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 ...
1
vote
2answers
43 views

Build a 3 bit full adder using only XOR gate?

I don't know if this is the right place to ask this, but I'm trying to design the logic for a simple calculator and I was wondering how can you build/design a 3 bit full adder using only XOR (one or ...
2
votes
0answers
65 views

Countably closed Boolean algebra of subsets of the real plane,

The following problem was in The American Mathematical Monthly : A generalized rectangle is $E \times F$ for any subsets $E,F$ of $\Bbb R$ (the reals). If $\mathscr{B}$ is the smallest countably ...
-1
votes
0answers
7 views

The total number of $n$-variable of boolean functions which are symmetric and self-dual? (For an add integer $n$)

For an odd integer $n$, what is the total number of $n$-variable Boolean functions that are symmetric and self-dual?
1
vote
0answers
24 views

Simple Boolean Algebra Exercise but stuck

I have the following exercise that I can't really solve or I am not happy with the result: If Team A loses, Team B and C will lose too If the Teams A and B win, Team C will lose If Team B ...
0
votes
2answers
16 views

Notation of a boolean function

I'm studying Boolean algebra but I was confused as the notation of a Boolean function. When I write/denote a Boolean function that way, what does that mean? $$ f: \mathbb{Z}^2_2 ...
0
votes
0answers
10 views

Solving boolean equation

Assume we want to solve, with f and g boolean functions f=-g' this has the same solutions as f(-g')'+f'(-g')=0 -fg-f'g'=0 Is this statement correct or am i completely wrong?
2
votes
2answers
44 views

Boolean algebra laws

Can someone explain to me why in Boolean algebra $$ f(x,y,z,t)=z+x'y+xy'+xt'+yt' =z+x'y+xy'+xt'$$ I have no clue why u can just leave out the last term, is it due to some ...
3
votes
2answers
5k views

self dual boolean function

How many self-dual Boolean functions of n variables are there?Please help me how to calculate such like problems. A Boolean function $f_1^D$ is said to be the dual of another Boolean function ...
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
1answer
16 views

Boolean Algebra and negation

$$ -(A \ast -B) \ast -(-A \ast B) $$ My understanding is that the above logic is equal to $$ (-A \ast B) \ast (A \ast -B) = (-A \ast A) \ast (-B \ast B) = \mathrm{FALSE} $$ but my ...
1
vote
0answers
36 views

Generators of free Boolean algebras

Suppose $\mathfrak{A}$ is a free Boolean algebra and $G$ a countable set of free generators of $\mathfrak{A}$. What is the cardinality of $\mathfrak{A}$ if $G$ is countably infinite, but we only ...
0
votes
2answers
65 views

Proof for $\forall x A \Leftrightarrow \neg \exists x \neg A$

I try to proof, that $\forall x A(x) \Leftrightarrow \neg \exists x \neg A(x)$ I know how to prove, that $\forall x A(x) \Rightarrow \exists xA(x)$, but I don't understand how to get negation.
0
votes
2answers
2k 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 ...
2
votes
1answer
9k views

Question on essential prime implicants

I am having some trouble understand essential prime implicants. So if a minterm is not covered by another overlapping rectangle, then that is an EPI. However, if we make a K-map for ...
1
vote
2answers
992 views

Convert expression to NAND only

Endless youtube videos and reading through notes later I am yet again stuck. I have to covert the following to NAND only $$\bar{A}\cdot\bar{B}\cdot\bar{C} + A\cdot\bar{B}\cdot C + A\cdot B\cdot ...
3
votes
1answer
90 views

Are there any free or fascist boolean algebras?

A boolean algebra is an algebra with the binary operations $\wedge$, $\vee$, an unary operation $\neg$, and constants $0$, and $1$, satisfying axioms. A heyting algebra is an algebra with the binary ...
2
votes
1answer
71 views

Is there a connection between Boolean algebra and probability?

Is there a unifying abstraction that links Boolean algebra and probability theory? Both Boolean algebra and probability provide us the means to answer questions about set participation. On the one ...
-1
votes
2answers
42 views

Boolean Algebra Problem ABCC' [closed]

Hi I just want to ask the answer of this Boolean Algebra problem.. $$ABCC' + B + A'B $$ How to simplify that one?
0
votes
1answer
24 views

Boolean equation - bitwise AND operator

I have equation: (x AND B) XOR x = C where x - is unknown variable, B and C are constant. I need just one solution x that will satisfy this equation. How I can do this?
1
vote
1answer
39 views

Universal 2-bit gates

I'd like to show that there is no set of 2 bit reversible gates which is universal. I'm not sure as to where & how do I start here? I tried to assume by contradiction that such a set exists, thus ...
1
vote
3answers
4k views

simplifying using Boolean Algebra.

I was doing the following question. Using the following rules of boolean algebra: _ law 1: X+X=1 law 2: X.1=X law 3:X.Y+X.Z = X.(Y+Z) simplify: ...
1
vote
1answer
33 views

Boolean functions

Boolean function f(x1,x2,x3): If f(x1,x2,x3)= TRUE then f(TRUE,x2,x3)= TRUE ...
1
vote
1answer
57 views

Counting switching functions

By using 16 bit binary in BCD , how many switching functions can exist ? Now , since this is BCD anything above 1001 is invalid. Considering 16 bits : 1001 1001 1001 1001 Above is number of possible ...
1
vote
1answer
78 views

Quotient of Cohen forcing

How do we know that the quotient of the Boolean algebra associated with Cohen forcing by a generic filter is either atomic or isomorphic to the Cohen forcing? I know that Cohen forcing is the unique ...
0
votes
1answer
12 views

Question on M-generic filter

Let B a complete boolean algebra and $b, c\in B$ and M a model of ZFC. Why do we have that if $c\in G\,\, \forall G$ M-generic ultrafilter such that $b\in G$ then $b\le c$ ?
6
votes
2answers
234 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
1
vote
1answer
16 views

Simple question on predense set in a boolean algebra

Let B a complete boolean algebra and D a subsets of B. Then D is predense below $ b\in B $, i.e. the downward closure of D is dense below b, iff $b\le \bigvee D$.Proving this equivalence seemed like ...
4
votes
1answer
51 views

Any two countable atomless Boolean algebras are isomorphic

How to prove that Any two countable atomless Boolean algebras are isomorphic. This is an exercise of Jech - Set theory book for which I have some difficulty.
0
votes
1answer
8k 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 ...
5
votes
0answers
57 views

FOUR-algebra - boolean algebra?

Belnap’s logic contains the the truth values 'true' ($t$), 'false' ($f$), 'unknown' ($\bot$) and 'paradox' ($\top$). Each of these is represented by a pair of bits: \begin{align} t &\rightarrow ...
0
votes
1answer
30 views

How does Absorption work in boolean algebra?

So I understand the basic outlines of the property: $a(a+b)=a$ From that its pretty clear to me that no matter what $b$ is the result will be $a$ regardless. However I don't understand how that ...
1
vote
1answer
66 views

Is Belnap's four valued-logic a boolean algebra?

Belnap's logic contains the the truth values 'true' (t), 'false' (f), 'unknown' ($\bot$) and 'paradox' (T). Each of these is represented by pair a of bits: t $\rightarrow$ (1,0) f $\rightarrow$ (0,1) ...
1
vote
0answers
31 views

boolean algebra - belnap logic

How to find out wether an algebra is a correct boolean algebra? So if we have the following algebra (rejects to belnap-logic theorems): $ \langle \{ w,f, \top , \bot \} , \wedge \vee \neg \rangle$
8
votes
2answers
64 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
0
votes
3answers
68 views

How to convert a truth table to boolean expression?

If I have a huge truth table, it's hard for me to construct an expression. I know a problematic method, the Disjunctive Normal Form. But I found that I cannot reduce the huge expression. ...
0
votes
0answers
27 views

Complexity of computing a posiform of a quadratic pseudo-boolean function

I am reading the chapter 13, Pseudo-Boolean functions, of Boolean Functions: Theory, Algorithms, and Applications by Crama et. al. In section 13.2, the authors introduce the idea of Posiform. The ...
0
votes
1answer
16 views

Boolean algebra consensus theory

I want to simplify $wxy + x'z + y'z + wz = wxy + x'z + y'z$ but I can't seem to use the consensus theorem at the right place. I tried factoring cases for $x$ and $x'$ and $y$ and $y'$ but I don't ...
0
votes
1answer
49 views

Finite boolean algebra can be embedded into $\mathcal P(n)$.

I am trying to show that every finite boolean algebra can be embedded into $\mathcal P(n)$ for some large $n$. Any hints?
1
vote
2answers
2k views

Find DNF and CNF of an expression

I want to find the DNF and CNF of the following expression $$ x \oplus y \oplus z $$ I tried by using $$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$ but it got all messy. I also ...
0
votes
2answers
31 views

How do you find the minterm list of a boolean expression containing XOR?

Let's say I have a boolean expression, such as F1 = x'y' ⊕ z . How do I go about finding the minterm list for that expression? The method I've tried is to take each term, such as x'y' and z, ...
0
votes
1answer
33 views

Reduce Boolean Expression

Note: A B = A and B A + B = A or B The expression: r = a̅ c̅ b + a̅ c b̅ + a c̅ b̅ + a c b Simplify?
1
vote
2answers
69 views

Calculation of Shannon entropy given the mutual information of Binary strings

Suppose $A$ and $B$ two different binary strings of length $l$. Suppose the Mutual Information (https://en.wikipedia.org/wiki/Mutual_information) of $A$ and $B$ is known to be $I$. Now suppose ...