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
0answers
9 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.
-1
votes
2answers
27 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
27 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 ...
2
votes
1answer
65 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 ...
1
vote
2answers
42 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 ...
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 ...
-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?
2
votes
0answers
64 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
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 ...
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 ...
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 ...
-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
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
56 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 ...
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$ ?
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 ...
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.
5
votes
0answers
55 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
65 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$
6
votes
1answer
113 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 = ...
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
66 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?
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 ...
2
votes
1answer
33 views

Stuck at simplifying boolean expression

I'm getting stuck at the following boolean expression. z + (x'y) + (xy') + (xt') + (yt') In my solutions its simplified and the (yt') term is gone. How do they simplify this? I really cant see ...
0
votes
1answer
31 views

Boolean algebra-Boolean ring. Stone Theorem?

I am interested in knowing which theorem is responsible for the following statement: Every Boolean algebra can become a Boolean ring by taking the ring addition to be $A\oplus B = (A \land \lnot B) ...
1
vote
0answers
21 views

reducing Boolean expression to minimum literals

I'm finding it tough to simplify these types of expressions. Here's my problem: $(a+b+c')(a'b'+c)$ I have to reduce this to the minimum number of literals. So far I've only broken it down to: ...
2
votes
2answers
44 views

Why is the dual of a filter an ideal?

Jech's set theory, (3rd edition) says that if $F$ is a filter on $S$ Let $I = \left\{ {S - X: X \in F}\right\}$ then $I$ is an ideal of $S$ (dual to $F$). However, let $X,Y \subset S$, $X \in I$ ...
1
vote
1answer
20 views

Simplifying a Boolean function from a Kernaugh Map

Given the three variable Karnaugh Map: x\yz 00 01 11 10 \___________________ 0 | 0 1 1 0 1 | 1 0 0 1 I am supposed to write a ...
1
vote
1answer
28 views

Boolean Algebra fundementals

A disjunction A OR B truth table has A , B , and A OR B but mine has A ,B C, with A or B or C could some please explain this
0
votes
0answers
19 views

Simplification to DNF

To get right to the point. I have written a test which required me to Simplify to DNF. And the following equation gives me trouble. Here is the equation: ...
4
votes
1answer
48 views

Boolean algebras, Stone theorem and being isomorphic to a field of sets

I'm a little bit confused about duality between boolean algebras and topological spaces or sets. I know the following theorem (which is due to Stone, as far as I know): Every boolean algebra $B$ ...
0
votes
2answers
21 views

Boolean Alegebra De morgans rule 2

hi i am told to perform a simplification using demorgans rule 2. Here is the question ' = Equals Not B . (C + B')' I got B' + (C' + B'') then B' + (C' + B) Now i dont know where ...
0
votes
1answer
20 views

Boolean Algebra expanding using absorption

Hi I have a question regarding the absorption law. I was told that I cannot expand ab = ab + abc by writing ab = ab(1+c). However, I believe you can expand xy = xyz' + xyz by doing xy = xy(z' + z) . ...
0
votes
2answers
54 views

Precedence of nested NOTs in boolean algebra

I have the following equation: $y = \overline{\overline{\overline{x_{1} + \overline{x_{2}}} .x_{2}.x_{1}} + \overline{x_{3}.\overline{x_{1}+x_{2}} + x_{2}}}$ I'm trying to solve it in four ways: ...
0
votes
0answers
9 views

proving properties of (graph) dominance defined via a system of equations

Some notions on graphs can be defined via a system of equations with values in a lattice. For example, dominance $d(v_1, v_0)$ ($v_1$ dominates $v_0$) in a graph $g$ is defined by a system $\forall ...
3
votes
1answer
27 views

Boolean expressions from multiplication to addition and vice-versa

I am trying to change these Boolean expressions into expressions that do not use multiplication. Bolds indicate complements. a) abc b) (ab +c)d And these to ones that do not use addition. c) a + b ...