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

DeMorgan's Law with Boolean Algebra

So I'm studying for an Assembly Language final tomorrow and I'm trying to simplify the following expression using Boolean Algebra. Here are the steps I've written so far, am I safe in assuming that ...
0
votes
1answer
15 views

Simplification of expressions?

The expression below fd < S && ld > e || fs > s && ld > e || fd > s && ld < e || fd < s && ld < e Is the ...
0
votes
1answer
56 views

Jayne's Equation 1.13 Derivation

Dear Stack Exchange Members, I'm reading 'Probability Theory - The Logic of of Science" by ET Jaynes, and I'm on pg. 11. Jayne's says: *"...For example, we shall presently have use for a rather ...
0
votes
0answers
99 views

Converting a boolean expression into CNF and DNF

Is there any systematic way to convert the following boolean expression (QUBO) into CNF or DNF? Here, $x_1, \ldots, x_n \in \{0, 1\}$, $a_1, \ldots, a_n \in \mathbb{Z}$ and $b_{1,1}, \ldots, b_{n,n} ...
0
votes
2answers
46 views

Boolean Algebra: Simplifying product of sums

I'm trying to simplify (A+B+C)(A+notB+C)(notA+B+notC) The K-map gives me (A+C)(notA+B+notC) but when I use boolean ...
2
votes
2answers
62 views

How to efficiently determine if any two propositional formulas are equivalent

Given any two arbitrary propositional formulas (but only using $\land, \lor, \lnot$), like $\lnot(A \land (B \lor \lnot B) \land C)$ and $\lnot C \lor \lnot A$, how can I (or a computer) efficiently ...
2
votes
1answer
56 views

An example of an ultrafilter

This is Theorem 3.5 (pp. 150) of the book "A course in universal algebra." http://www.math.uwaterloo.ca/~snburris/htdocs/UALG/univ-algebra.pdf Theorem 3.15. Let $\bf B$ be a Boolean algebra. (a) ...
0
votes
1answer
45 views

Complete subalgebra of regular open Boolean algebra generated from open intervals

Let $X$ be a totally ordered set, considered as a topological space with the order topology. The regular open subsets of $X$ (i.e., the sets $U = \operatorname{int} \operatorname{cl} U$) form a ...
1
vote
2answers
19 views

What is $A^c \cap B^c \cap C^c$

I am working with boolean algebra for my Navy coursework and I was wondering if anyone knew what the formula for $A^c \cap B^c \cap C^c$ is? Also does $A^c \cap B^c \cap C^c = (A \cap B \cap C)^c$? ...
0
votes
1answer
27 views

Trying to simplify boolean algebra a+ac+ab

I am trying to simplify A+AC+AB. I think I have solved it, but I want to double check its right, can it be simplified to A+A(C+b) and then again to A(C+B) as A+A = A?
1
vote
1answer
49 views

How many n-ary Boolean functions essentially dependent on each of their arguments?

How many n-ary Boolean functions essentially dependent on each of their arguments? essentially dependent means that $$f(b_1,…,b_{i−1},0,b_{i+1},…,b_n) \neq f(b_1,…,b_{i−1},1,b_{i+1},…,b_n)$$
1
vote
0answers
49 views

How to convert a mod 2 function to an expression in Boolean Algebra

I'm not sure if this is the right place to post it but I have a question I'm having a hard time understanding. The questions is: Convert the function $X^3Y + 2XZ + WX + W$ mod $2$ to an expression ...
0
votes
0answers
19 views

Are epimorphisms (defined via an obvious action) of free Boolean algebras whose set of generators is a group automorphisms?

Let $G$ be a group. Consider $B$, the free Boolean algebra with generating set (I'll call them "variables") $G$. Let $F$ be some formula (that is, some fixed element of $B$). Define an endomorphism ...
0
votes
0answers
30 views

Number of elements in a Boolean algebra

Consider a set $X$ consisting of $n$ elements Does the Boolean algebra of all subsets of $X$ (i.e. the power set of $X$) have $2^n$ or $2^{2^n}$ elements? I came across both answers, which confuses ...
0
votes
1answer
48 views

Simplifying Boolean Function with Karnaugh Map

How to write Product-of-sum(POS) and Sum-of-product(SOP) Above K-Map? I already write POS please check my answer.
0
votes
1answer
45 views

Proof for $∃xA⇔¬∀x¬A$

I want to prove, that $∃xA⇔¬∀x¬A$, using classic axioms. I think, I have to start with the following step: $∃xA⇔∃x¬¬A$ But I do not know, how to make this step, using axioms: $∃x¬¬A⇔¬∀x¬A$
2
votes
3answers
44 views

How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$

I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help. If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$. ...
0
votes
1answer
18 views

Simplifying a Boolean Expression 2

The boolean expression is as follows: (¬A^¬B^¬C)∨(A^¬B^C)∨(A^B^¬C)∨(A^B^C) I have found that A⊕(¬B^¬C) is equal to the above but I have absolutely no idea on how to get this result, I have spent ...
1
vote
2answers
36 views

Inequality with respect to transitivity

Given a relation R, R is said to be transitive if aRb ∧ bRc, then aRc. The unequal relation (≠) is not transitive, for instance a≠b ∧ b≠c, then a≠c is an invalid consequent of the antecedent (a≠b ∧ ...
0
votes
2answers
28 views

Joins in lattices and sublattices

Let $A$ be a lattice, and $B$ be a sublattice of $A$. Why is the join of $A$ included in the join of $B$? That is, why is $\bigcup_{t\in T}^{A} a_t\leq\bigcup_{t\in T}^{B} a_t$? (I am tempted to ...
0
votes
1answer
23 views

Product of maxterms

Please help me break the ice in understanding how we derive a product of maxterms, say, for: $xy+x'z $ I could be missing some concept here in this but be patient with me. I have also done SOP and ...
1
vote
1answer
23 views

Is there any way to simplify the following boolean expression?

I was trying to manipulate with litarals and minterms of this booleans expression but it really did not lead to anything that could simplify the expression further.. Not sure if I am doing it wrong or ...
1
vote
2answers
19 views

Proving relation in boolean algebra, need help

Here is the logic equation and I am trying to prove the relation ($'$ stands for complement): $$𝑥_1𝑥_3' + 𝑥_2'𝑥_3' +𝑥_1𝑥_3 +𝑥_2'𝑥_3 = 𝑥_1'𝑥_2' + 𝑥_1𝑥_2 + 𝑥_1𝑥_2'$$ What I am doing: ...
0
votes
1answer
49 views

Least and greatest element of the $(\mathbb{N}, |)$

Consider the relation | on $\mathbb{N}$, where $\mathbb{N} = \{0,1,2,... \}$ and $n|m$ means $n$ divides $m$. I know that the pair $(\mathbb{N}, |)$ is a partial order, : (1) Find the least and ...
0
votes
1answer
61 views

Duality Principle in Boolean Algebra - Why do I alway get !F instead of F?

I have the function: F = !(a && d || b || c) Now i apply the duality principle and exchange all * with + ...
1
vote
1answer
24 views

How can I prove that (x and ¬y) or (¬x and y) = ¬((x and y) or (¬x and ¬y))?

I'm stuck at this problem: (x and ¬y) or (¬x and y) = ¬((x and y) or (¬x and ¬y)) Basically what I have to do is to convert the right side of the equation to the left side using boolean algebra. I ...
0
votes
0answers
24 views

How to prove that $abd = abcd + abc'd$ for all general occassions

It is true for example that $abd = abcd + abc'd$. Each of the terms on the right part of the equation contains all the used letters. Is there anyway to prove that any term is equal to the sum of the ...
0
votes
1answer
34 views

Simplifying boolean algebra expression $(AB+AC)'+A'B'C$

$$\eqalign{(AB+AC)'+A'B'C&=\overline{(AB+AC)}+\overline A \,\overline BC\\&=(\overline A+\overline B)(\overline A+\overline C)+\overline A\,\overline BC\\&=\overline A+\overline ...
1
vote
0answers
27 views

Boolean algebra-dual of an expression

Can anyone think of an expression that is equal to its dual ? I've been trying to solve this for the past 2 hours, but nothing comes to mind.
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.
2
votes
3answers
96 views

Implementing logic functions using only an OR gate with one input inverted

I've been looking at logic gates, boolean expressions and Karnaugh maps. I ran into a question regarding whether it was possible to implement all logic functions using only one logic gate: an OR gate ...
0
votes
1answer
219 views

How to simplify the Boolean function $A'B'C + A'BC' + ABC + AB'C'$?

So the question I have asks to implement the circuit with $XOR$ gates. So I am 3/4 through the problem when I am having problems simplifying the Boolean expressions below: $$A'B'C + A'BC' + ABC + ...
0
votes
1answer
39 views

Boolean algebra - neutral elements

I am searching for the neutral elements of following Boolean expressions: -NOT -NAND -NOR The neutral element of NOR should be 0 (false) but the others? I think for NOT and NAND there are no neutral ...
1
vote
1answer
160 views

Is infinite boolean algebra atomless?

I got two questions: 1) Does there exist an infinite Boolean algebra which contains an atom? I answered yes. 2) Does there exist an infinite Boolean algebra B such that for every b contained in B ...
1
vote
1answer
181 views

Finding the atoms and elements of a Lindenbaum–Tarski algebra

Let B be the Lindenbaum–Tarski algebra with three variables $p,q,r$ (1) Find all the atoms of $B$. (2) How many elements of does $B$ have? So I think I know what an atom is, but I'm still not sure ...
0
votes
2answers
66 views

How to simplify the given boolean expression to simplest form? [duplicate]

I have the expression xy+xy'z+x'yz'. I have tried a number of ways to simplify it. What approach will ensure that this expression is reduced to its simplest form?
1
vote
0answers
56 views

question in math logic: find the d.n.f. and c.n.f.

The question is as follows: Find the disjunctive and conjunctive normal forms of the following: $$ (A \to (B \to C)) \to ((A \to \neg C) \to (A \to \neg B)) $$ My solution is as follows, but I ...
0
votes
2answers
35 views

How to proof tautology without truth table in this case? [closed]

Hej, i got stucked while finding a solution to proof the following is a tautology. Can someone help me out please with a good tip? Thanks in advance
0
votes
1answer
37 views

simplify boolean expression: xy + xy'z + x'yz'

As stated in the title, I'm trying to simplify the following expression: $xy + xy'z + x'yz'$ I've only gotten as far as step 3: $xy + xy'z + x'yz'$ $=x(y+y’z) + x’(yz’)$ $=x(y+y’z)+x(y’+z)$ But I ...
0
votes
1answer
66 views

Boolean Algebra, using DeMorgan's law

I have obtained this function: $$(\overline{A}*D) + (\overline{A}*C) + (\overline{B}*\overline{D})$$ ... after I have used Karnaugh Map to simplify the canonical expression. And now, I am needing ...
0
votes
1answer
79 views

Write the following Boolean expression in product of sums form?

Write the following Boolean expression in product of sums form: a'b + a'c' + abc is it correct if I write it as the following ? (a+b')(a+c)(a'+b'+c')
2
votes
1answer
69 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 ...
0
votes
2answers
154 views

How to express other logical operations via Pierce's arrow?

x↑y, x⇒y, and x⇔y. So I have really given my best, but all I could do is express the conjunction, disjunction, negation, and impilcation.
0
votes
0answers
58 views

Defining an example of a Boolean algebra (Discrete Math)

This question is listed in my textbook: Give an example of a Boolean algebra B and elements $x$, $y$, $z$ in $B$ such that $x + z = y + z$, but $x \neq y$. Now, I believe this means I have to ...
0
votes
1answer
27 views

Simplify (x'+y)'(x+y)' with boolean algebra

So I'm doing some homework and trying to simplify (x'+y)'(x+y)'. So far these are the steps I've completed, but I'm not 100% sure that they're appropriate. $(x'+y)'(x+y)' = (x'+y)'(x’y’)$ ...
0
votes
1answer
43 views

Karnaugh map minimal representation

Find the minimal representation for: f(w,x,y,z)= summation m(0,5,6,8,13.14)+d(4,9,11,12) I was a little confused what to do with the don't cares but I used all of them.. Based on the Karnaugh map ...
4
votes
2answers
70 views

Can this expression $(\neg B \land \neg D) \lor (\neg A \land B \land C) \lor (A \land C \land D)$ be further simplified?

I have assignment for computer architecture where I have to simplify a big boolean function: f(a, b, c, d) = a'b'c'd + a'bcd' + abcd + a'bcd + a'b'cd' + ab'cd' + ab'c'd' + ab'cd + a'b'c'd' ...
0
votes
1answer
39 views

Show that a interval from a boolean algebra is also a boolean algebra and that a function is surjective

We have an boolean algebra $(B,\lor, \land, ', 0, 1)$ and $b \in B - \{0\}$. We consider $[0,b] = \{x \in B | 0\le x\le b \} \subset B$, where $\le$ means an order relationship introduced in the ...
0
votes
2answers
20 views

Boolean algebra simplification

Is this the simplest form of the expression? Given: $$x'y'z+x'yz'+x'yz$$ My work: $$x'y(z'+z)+x'yz'= x'y+x'yz= x'y(z)$$
0
votes
2answers
28 views

how does $(p\to q)\lor r \lor s$ effect $(p\leftrightarrow q) \lor r \oplus s$

If we know that $\lnot p \lor q \lor r \lor s=\top$, then what is the value of: $(\lnot p \land \lnot q) \lor (p \land q) \lor(r \land \lnot s) \lor (\lnot r \land s)$ I tried doing it with a truth ...