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
12 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)$$
0
votes
0answers
19 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
10 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
11 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
2answers
385 views

Writing a boolean formula and logic circuit that computes mux

Let $mux(p_{11}, p_{10}, p_{01}, p_{00}, x_1, x_0) = P_{x1x0}$ (with all variables bits). Write a boolean formula, and then draw a circuit, that computes mux. For ...
0
votes
0answers
8 views

Simplify Boolean Algebra Expresssion q1 [on hold]

X = ABCD +A' X = A' + BCD Can explain why A become A'+BCD?
0
votes
0answers
11 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
35 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$
0
votes
1answer
254 views

Boolean algebra simplification question

I'm trying to simplify the follow SOP expression: $\bar{A}$$\bar{B}$$\bar{C}$ + $\bar{A}$B$\bar{C}$ + $\bar{A}$BC + AB$\bar{C}$ Using a K-map (unless I've erred) it should simplify to: ...
2
votes
3answers
38 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
13 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
4answers
16k views

how to make a truth table from an boolean expression

I am trying to make a truth table from an SOP boolean algebra expression. I understand AND, OR, NOT truth tables. I just dont understand these types of tables and their outputs. This is the ...
4
votes
5answers
7k views

Duality principle in boolean algebra

All the definitions I came across so far stated, that if a statement is true, then also its dual statement is true and this dual statement is obtained by changing + ...
0
votes
1answer
16 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
2answers
27 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 ∧ ...
11
votes
7answers
8k views

Is XOR a combination of AND and NOT operators?

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?
0
votes
2answers
18 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
896 views

Simplify Boolean Product of Sums Function

I've got a product of sums expression: F=(A'+B+C')&(A+D')(C+D') I need to show it as a sum of products and then simplify it. Right now I got: F=(A'&D')+(A&B&C)+(B&D')+(C&D') ...
0
votes
1answer
40 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 ...
1
vote
1answer
17 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
17 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
38 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
18 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 ...
3
votes
2answers
457 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 exactly ...
0
votes
0answers
18 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
22 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
1answer
100 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
0answers
18 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
1answer
40 views

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

I try to proof, that $\forall x A \Leftrightarrow \neg \exists x \neg A$ I know how to proof, that $\forall x A \Leftrightarrow \exists xA$, but I don't understand, how to get negation.
1
vote
0answers
385 views

Number of canonical expressions

There is a question: What is the number of canonical expressions that can be developed over a 3-valued boolean algebra? I was trying to solve this. Canonical expression is the combination of ...
0
votes
1answer
32 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 + ...
2
votes
3answers
33 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
21 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 ...
0
votes
0answers
9 views

Simplify the Boolean functions using K-Map

I was able to derive these boolean expressions correctly from a circuit diagram. (Professor put answers up to compare) She now wants us to use a K-Map to simplify these functions. This where I am ...
0
votes
1answer
560 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 ...
6
votes
1answer
219 views

Non-isomorphic countable Boolean algebras

I'm trying to solve the next exercise: Construct a sequence $\mathcal{B}_0,\mathcal{B}_1, \ldots$ of countable Boolean algebras such that for all $m \neq n$ then $\mathcal{B}_m \ncong \mathcal{B}_n$. ...
0
votes
2answers
885 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 ...
1
vote
1answer
121 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
18k views

How to convert between Sum Of Products and Product of sums?

I have a Boolean expression. we'll call it F. for instance, F = ab' + ad + c'd + d'. Assuming I did all the necessary steps ...
0
votes
2answers
15 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
36 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
26 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
-1
votes
2answers
59 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.
1
vote
2answers
3k 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 ...
0
votes
1answer
25 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
19 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
30 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
0answers
12 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')
1
vote
1answer
28 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
0answers
20 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 ...