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
16 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
votes
0answers
22 views

algebra boleana and huntington axioms [on hold]

Prove that there is an algebra onarit (that have only one member in the group "B") that meets with the Huntington axioms (without the axiom - at least 2 members in the group) edit: the aximos of ...
1
vote
1answer
27 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
29 views

Boolean functions

Boolean function f(x1,x2,x3): If f(x1,x2,x3)= TRUE then f(TRUE,x2,x3)= TRUE ...
1
vote
1answer
48 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
11 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
76 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
14 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
50 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
50 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
25 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
60 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$
2
votes
0answers
26 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
58 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
55 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
24 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
14 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
0answers
10 views

Pure Literal Rule what if a variable exist only in negated form in CNF

I am trying to solve a simple SAT problem. The initial SAT is: ...
0
votes
1answer
46 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
25 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
68 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
32 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
27 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
15 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
42 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
45 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
19 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
53 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
8 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
23 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 ...
1
vote
2answers
36 views

Proving that a set with a quaternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{N\}$ of one logical connective is inadequate where $N$ is a quaternary connective that is defined as follows: $N(w,x,y,z)=((x\land y)\land(w\lor z))$ ...
0
votes
3answers
55 views

Boolean Algebra - proof without associativity?

I would like to prove the following: $(x\cdot y) + (\overline{x} + \overline{y}) = 1$ without the Associativity Property. I can't seem to do this algebraically (without truth tables).
1
vote
1answer
17 views

Does disjunction of two Boolean algebra cuts always produce their ideal sum?

Let $(B, 0, 1, \leq, \wedge, \vee, \neg)$ be a Boolean algebra. For a subset $A \subseteq B,$ denote by $L(A) = \{l \in B \mid (\forall a\in A) \, l \leq a\}$ the set of all lower bounds of $A,$ and ...
0
votes
0answers
20 views

how to convert XOR to DNF form?

If I have the expression $X$ xor $Y$ , how do I convert it to DNF form? and $X$ implies $Y$? I only got to the point where I make the truth table for the functions, but after that I could not apply ...
0
votes
1answer
19 views

How do I input this Boolean Expression into a K map?

Determine the minimum SOP, sum of products expression using K-Map F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’ Do i have to actually simplify it first by multiplying ...
1
vote
1answer
35 views

How to simplify Boolean Expression $\bar B + \bar C (B + A)$

I trying to figure out how $ \bar B + \bar C (B + A)$ simplifies to $ \bar B + \bar C$.
0
votes
0answers
21 views

What are The applications of Fast Walsh–Hadamard Transform.

There is a problem requiring the expect value of the intersection of two random subsets selected from a universal set, with the values and the probabilities of subsets given. My friend said it could ...
0
votes
0answers
30 views

Identifying a SSOP (standard sum of products) expression…

Say you're asked to identify a standard sum of products (SSOP) expression from 4 or 5 options... 3 of them are definitely not SSOP (variables are missing between the terms)... however two of the ...
1
vote
1answer
16 views

xor-ing vectors

This question might be wrong on mathematics, but I don't know where else to put it. I have a given equation, and there is one calculation step, that I don't understand. I thought, I have to xor ...
2
votes
0answers
24 views

Does a logical matrix representing sets have a name or special properties?

Imagine a collection of separate objects and several sets. These sets can be represented using a logical matrix. $M = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 ...
1
vote
1answer
29 views

Closedness of $\{ x \in 2^A : x(\neg p) = \neg x(p) \}$ for a Boolean algebra $A$ and $p \in A$

I'm reading Matthew Dirk's The Stone Representation Theorem for Boolean Algebras, and am trying to follow the proof of Proposition 3.4 on p.6: Proposition 3.4. Let $A$ be a Boolean algebra, and ...
0
votes
1answer
25 views

Finding Prime Implicants and Essential Prime Implicants for Boolean Functions

I am trying to solve a EE problem and am unsure whether I doing it correctly. The problem is: Find all the prime implicants for the following Boolean functions, and determine which are essential: ...
0
votes
1answer
30 views

Boolean algebras and rings

I know that M. H. Stone proved that there is a bijection between boolean algebras and boolean rings. The bijection I know is the following: to any given Boolen algebra $(L,\, \vee, \wedge)$ we ...
2
votes
3answers
78 views

Solving this logical puzzle by resolution doesn't work for me

In this document there is a logical puzzle: If the unicorn is mythical, then it is immortal. If the unicorn is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a ...