Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [boolean-algebra]

Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Use this tag for questions about Boolean algebras as structures, or about functions defined from/to Boolean algebras. For Boolean logic use the tag propositional-calculus.

0
votes
1answer
52 views

Boolean Expression Simplification Problem

I started with a big problem and through various simplifications I've arrived at a point where I don't quite know what else to do. I've tried to further simplify but I keep running into issues. ...
0
votes
0answers
30 views

Show that the Lindenbaum-Tarski algebra is free over the set of propositional variables

Show that the Lindenbaum-Tarski algebra is free over the set of propositional variables. I was given that statement to prove. My lecturer said we need to show that any map from said set to a given ...
0
votes
2answers
39 views

Simplify boolean expression, so close but yet so far

$$F(w,x,y,z) = w'y' + w'z + x' + yz + y'z'$$ The simplest form is apparently $w'y' + x' + yz + y'z'$, but for the life of me, I cannot figure out how, no matter what trick I use.
2
votes
1answer
153 views

Tseytin transformation example

I am trying to understand Tseytin transformation and I can't really find any reliable info on the internet. I pretty much understand the steps until I get to the point I have to convert all ...
1
vote
0answers
39 views

why does a closed circuit represent a false proposition? (Claude Shannon thesis)

In reading through Claude Shannon's paper: A Symbolic Analysis of Relay and Switching Circuits. As a software engineer, I got confused by Shannon's choice to have 0 as representing a closed circuit, ...
2
votes
0answers
98 views

How many distinct subsets of binary boolean operators are closed under composition?

Question: There are $2^4=16$ distinct binary boolean operators. Two operators are regarded the same if one can be obtained from the other by exchanging the operands (input). It is easy to see only $...
0
votes
1answer
31 views

How to choose a set of boolean functions with a specified probability of getting a 1

So let's say I have a boolean function $f(x)$ that takes in a size k binary vector and outputs a binary scalar. Each function is defined as a $2^k$ vector. For example $f((0,0)) = 0, f((0,1)) = 1, f((...
6
votes
2answers
73 views

Is $P(tautology) = 1$? What are the connections between logic and probability?

It's well-known that sets are "isomorphic" to logic: if we treat $\varphi(A_1, A_2)$ as a shorthand for $\forall x: \varphi(x \in A_1, x \in A_2)$ then $A \land B \equiv A \cap B$ and $A \rightarrow B ...
-1
votes
1answer
29 views

Ordered Sets and Lattices

Recall the topic “Ordered sets and Lattices” that the set $D_m$ of divisors of $m$ is a bounded, distributive lattice with $$a+b = a\lor b =\operatorname{lcm}(a, b)$$ $$ab = a\land b =\gcd(a, b)$$ (...
0
votes
0answers
16 views

Can all the boolean expression be simplified without Karnaugh Map?

I know when Boolean expressions get too complex it is comfortable to use Karnaugh Map. But is it possible to simplify very complex Boolean expressions without this map, using just the laws?
0
votes
1answer
30 views

Is there a way to simplify of the next boolean expression?

Im trying to simplify the next expression $$A\bar{B}E+\bar{A}B\bar{E}$$ so the approach is to factor $E$ and ·$\bar{E}$ to get something like $$A\bar{B}+\bar{A}B (E+\bar{E})$$ (this step before is ...
3
votes
1answer
45 views

Opposite category of SET is Boolean Algebra

I'm reading introductory notes on category theory. While discussing the notion of opposite category, the author makes a remark that if we take opposite category of SET, that is $SET^{op}$ category, we ...
1
vote
1answer
34 views

Is it true that for a Boolean Algebra, $a'b+(abc)'+c(b'+a)=b'+c'$?

Analyze if the following statement is true or false: Suppose $(D,+,\cdot,',0,1)$ is a Boolean Algebra. Then $a'b+(abc)'+c(b'+a)=b'+c'$. My guess is that the statement is false. Let $D=D_{15}$ be the ...
0
votes
2answers
46 views

Proving uniqueness of solution in Boolean algebra

System: $a+x=1 \land a\cdot x=0$ has unique solution for x, for all values of $a \in B$. It is obvious that $x=a'$ is one solution , but how to prove the it is only one? I have tried assuming that ...
1
vote
1answer
27 views

Boolean Expression Simplification - Issue

I don't understand where to even begin with this problem. Any helpful tips would be nice. $(A \lor \lnot B \lor \lnot D) \land (\lnot B \lor C \lor D) \land (B \lor \lnot C \lor \lnot D)$
0
votes
0answers
35 views

Determine whether an integer can be constructed from other integers by applying bitwise AND and OR operations

Given binary numbers $b_1, b_2, ... , b_m < 2^n$ as well as their complements $b'_1, b'_2, ..., b'_m$ (with leading $1$'s if necessary, such that $b_i + b'_i = 2^n - 1$), is it possible to quickly ...
1
vote
2answers
37 views

Complementing a Boolean Function from Shannon's Expansion

Given a Boolean function $f: B^n \longrightarrow B$, using Shannon's expansion across variable $x$, I can write it as $f = xf_x + x^{'}f_{x^{'}}$. I want to complement $f$. Using Shannon's expansion ...
0
votes
1answer
34 views

Canonical Form Question

I have a quick question about some Boolean algebra. The problem is: F (A, B, C) = A + B And I want to expand it into canonical-sum form. The problem is there is no 'C' so I am unclear on how to ...
2
votes
1answer
38 views

Boolean expression simplification using 3 variables

(!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD) = (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(1) = (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(C + !C) = (!A B !C) + (B !C !D) + (!ACD) + (...
1
vote
2answers
30 views

Boolean expression simplification - Short problem

I don't know exactly how to simply this problem. I can clearly see that (A + B) is in all of them but I don't know what to do next. (A + B + C)(A + B + !C + D)(A + B + !C + !D) -- Edit 1 -- I am ...
0
votes
2answers
28 views

Can any boolean expression with OR operators be converted to only AND operators?

I'm fairly new to Boolean algebra and I was wondering, using Boolean theorems,can any Boolean expression with an OR operators in it be converted to an equivalent expression using only AND operators? ...
2
votes
1answer
30 views

Find a homomorphism that maps a point in a Boolean algebra into the image of a proper filter

Let $\mathbb B$ be a Boolean algebra. Let $F$ be a proper filter in $\mathbb B$ (i.e. $0 \notin F$), and let $I$ be its dual ideal. Suppose there exists $a \in \mathbb B$ such that $a \notin F \cup I$....
4
votes
1answer
44 views

$\kappa$-distributivity and Stone's Representation Theorem

On page 85 of Jech's Set Theory (3rd Edition), a complete Boolean algebra $B$ is defined to be $\kappa$-distributive if \begin{equation}\label{a}\tag{1} \prod_{\alpha < \kappa}\, \sum_{i \in I_\...
2
votes
2answers
301 views

Simplify [p∧ (¬(¬p v q)) ] v (p ∧ q) so that it become p, q, ¬p, or ¬q

Had a question on a test that asked for us to simplify (using rules of inference) the following proposition: [p∧ (¬(¬p v q)) ] v (p ∧ q) to p, q, or their negation (¬p, ¬q). Here is what I did: 1) [p∧...
1
vote
2answers
47 views

How to automatically create proofs in Boolean Algebra

Given a complete set of axioms (for example, associativity, communtative, distributivity, identity, annihilator, idepotence, and the "complementation" laws) for boolean algebra, I know any other true ...
0
votes
0answers
20 views

How do I derive the NOR expression of x'yz' + xy' + z using K-Maps?

How would I derive NOR boolean expression of this using K-maps? I know you can do it algebraically but I want to know how to do it using K-maps.
1
vote
1answer
27 views

Divisibility represented by Boolean logic

Some context: I was thinking about the feasibility of using SAT solvers to prove primality, especially of Mersenne primes, by showing that there exists no Boolean sequence $d_1,d_2, ..., d_{b'}$ that ...
0
votes
0answers
19 views

Finding arithmetic form of XOR function for 2+ bit numbers

There are many different ways to express Exclusive-OR function for 1-bit values (0 or 1). For example: $$ a \oplus b = \left\lvert a - b \right\rvert \tag{1} $$ or $$ a \oplus b = (a + b) \bmod 2 \...
0
votes
0answers
14 views

Let $a,b$ belong to an antichain $A$ of a Boolean algebra $B$. Show that $a \land b = 0$.

Suppose that $a,b$ belong to an antichain $A$ of a Boolean algebra $B$. Show that $a \land b = 0$. I know that this is often taken as the definition of an antichain for a Boolean algebra, but I can'...
0
votes
1answer
12 views

Restricting a filter in a Boolean algebra to a generating set and have it generate a filter

Let $B$ be a Boolean algebra and $S \subseteq B$ be a subset that generates $B$. Is it the case that every filter $x$ of $B$ is equal to the filter generated by $x \cap S$? What if $S$ itself is a ...
0
votes
1answer
37 views

Sum of product -

I am having some issue in minimize the following sum of products. My solution is: not A and not B or A and ((B and not C)or C) But I think it is not right.
0
votes
1answer
47 views

Show that this holds in every Boolean Algebra

Prove that this holds in every boolean algebra: $$ x\land y \land z' =x \space \space \text{iff}\space \space x \lor y =y \space \space and \space \space x\land z=0 $$ My guess is to start first with ...
0
votes
1answer
24 views

Is this a correct application of logical Absorption and Reduction?

Absorption: $$P \land (P \lor Q) = P$$ Reduction: $$P \land (\neg P \lor Q) = P \land Q$$ Starting with, $[\neg P \land (\neg P \lor Q)\land (P\lor \neg Q)\lor \neg P \land (\neg R \lor Q)\land (...
1
vote
2answers
35 views

How to distribute $(\neg 𝑃 \lor 𝑅) \land [((\neg 𝑃 \lor 𝑄) \land (𝑃 \lor \neg 𝑄))∨((\neg 𝑅 \lor 𝑄) \land (𝑅\lor \neg 𝑄))]?$

I see two possible ways to distribute this. I believe it is case 1. For brevity, Let \begin{align}A &= (\neg P \lor Q) & B &= (P \lor \neg Q) & C &=(\neg R \lor Q) & D &...
2
votes
1answer
27 views

How to apply Absorption to (¬𝑃∨𝑅∨𝑄)∧(¬𝑃∨𝑅∨¬𝑄)∧(¬𝑃∨𝑄)∧(¬𝑄∨𝑅) to obtain (¬𝑃∨𝑄)∧(¬𝑄∨𝑅)?

I am going through the accepted proof in this thread. There is a section that uses absorption for a final reduction into the desired result. How do I use two applications of absorption to: $(\neg ...
0
votes
1answer
18 views

How to use Adjacency to transform (¬𝑃∨𝑅)∧(¬𝑃∨𝑄)∧(¬𝑄∨𝑅) into (¬𝑃∨𝑅∨𝑄)∧(¬𝑃∨𝑅∨¬𝑄)∧(¬𝑃∨𝑄)∧(¬𝑄∨𝑅)?

I am going through the accepted proof in this thread. There is a section of the proof that uses Adjacency to transform (¬𝑃∨𝑅)∧(¬𝑃∨𝑄)∧(¬𝑄∨𝑅) into (¬𝑃∨𝑅∨𝑄)∧(¬𝑃∨𝑅∨¬𝑄)∧(¬𝑃∨𝑄)∧(¬𝑄∨𝑅). It ...
0
votes
3answers
79 views

Simplify (W + Y) (W' + X' + Y) (X' + Y' + Z')

Okay, so I started from ( (W + Y + Z')' (W' + X' + Y)' (X' + Y' + Z')' (W + Y + Z)' )' then simplified further to: ( W'Y'Z + WXY' + XYZ + W'Y'Z' )' then: (W + Y + Z')(W' + X' + Y)(X' + Y' + Z')(W ...
1
vote
2answers
37 views

How do I get Z' + X'Y' + XY from Z' + ZX'Y' + ZXY?

So I'm trying to simplify an equation using boolean algebra. I'm still very confused as to how all the rules work and such, but I feel like I'm very close to the answer. The original equation is (in ...
0
votes
0answers
14 views

Fundamental Logical Operations are monotone with their variables.

My question is more for understanding what i actually have to do. So, i have to prove that 1)A ∧ B and A ∨ B are increasing monotone in relation with A and in relation with B 2)A ̅ is monotone ...
0
votes
1answer
46 views

How to use distribution on (¬P∧R)∨(¬P∧¬Q)∨(R∧Q) to get the desired propositional formula?

I am going through the accepted proof listed in a previous thread and got stuck on a step where you use the distributivity property to go from: (¬P∧R)∨(¬P∧¬Q)∨(R∧Q) to: (¬P∨¬P∨R)∧(¬P∨¬Q∨R)∧(¬P∨¬P∨...
1
vote
2answers
56 views

prove the equivalence of a+b=b and a*b=a in the boolean algebra theorem [closed]

This is a question in the boolean algebra and their equivalence should be proved i the theorem 5 of the boolean algebra.Am capable of proving the theorem 5 but i still dont ahve a clue on how to start ...
0
votes
0answers
28 views

Find back equation copied with bad encoding

A student work I received, shows 3 expressions like this (quotes are from me) : ...
0
votes
0answers
21 views

Construct algebras $A_p \subseteq \mathscr(P) (X)$ with cardinality $|A_p | = 2^p$.

If $X$ is a set with $|X| \geq s$, for every $p \in \{1,2,...,s\} $, construct an algebra $\mathscr{A} _p \subseteq \mathscr{P} (X)$ such that $|\mathscr{A} _p | = 2^p$. I was thinking on doing this ...
0
votes
2answers
107 views

Assistance in completing the proof: (P → Q)∧(Q → R) is equivalent to (P → R)∧ [(P ↔ Q) ∨ (R ↔ Q)] using logical equivalencies

There is a proof in a previous thread that converts the two expressions (P → Q)∧(Q → R) and (P → R)∧ [(P ↔ Q) ∨ (R ↔ Q)] to a CNF-formula thereby proving their equivalencies. I am approaching the ...
3
votes
2answers
62 views

Do complete atomic boolean algebras form a full subcategory of boolean algebras?

I would like to know if a boolean morphism (that is an application that respects $\vee, \wedge, \neg, 0,1$) between two complete atomic boolean algebras is necessarily complete (it respects also ...
0
votes
1answer
100 views

Which properties of boolean algebra are used to prove the DeMorgan Laws?

Given a proof, I tried to analyze it and identify the properties of boolean algebra used at each step. However, I am stumped with the first line: $(a+b) + \sim(a) \cdot \sim(b) = (a + b + \sim(a))(a+b+...
0
votes
0answers
26 views

How to get product of sum expression of a Boolean function

Consider this Boolean expression: $x \oplus y \oplus xy$. What is the corresponding product of sum expression? So I want write as $(\cdots \oplus \cdots) (\cdots \oplus \cdots)$. Here $\oplus$ is ...
0
votes
1answer
34 views

How do i work this Boolean Algebra?

Simplify: ~P~VSTC + ~PV~STC + ~PVS~TC + ~PVSTC + P~V~STC + P~VS~TC + P~VSTC + PV~S~TC + PV~S TC + PVS~TC + PVST~C + PVSTC (hint: ending value only has seven terms...) I have no clue how or why that's ...
0
votes
0answers
31 views

What is the proper name for this set of zeroes and ones

Consider a set $X$ which contains strings of $n$ bits. Each string starts with zero and it is non-zero string. For example n=3 $$ 001\\ 010\\ 011 $$ and for $n=4$ $$ 0 0 0 1\\ 0 0 1 0\\ 0 1 0 0\\ 0 ...
1
vote
0answers
92 views

How to prove something is not a logical consequence of 2 propositions.

I have a question where I have to show that the third statement is not a logical consequence of the 1st two using a truth table. I've seen how you'd do if there are only two (How to prove logical ...