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

Boolean Algebra Simplification

How do I simplify the following equation? $\newcommand{\pn}{\phantom{\neg}}$ $$\begin{align*} \neg A\pn B \neg C \neg D\\ + \pn A\neg B\neg C\neg D\\ + \neg A\neg B\neg C\pn D\\ + \pn A\pn B\neg C\pn ...
0
votes
0answers
9 views

Intuition behind duality principle?

I'm looking for an intuitive explanation of the duality principle. I found this proof but it was way above my head, considering I just started Boolean Algebra a couple of days ago. I suspect most ...
0
votes
1answer
59 views

simple exercise in Cylindric algebra

I am trying to gain a better understanding of cylindric algebra, so I made up this example. Given a general rule that someone's father's father is his/her grandfather: $\forall_X ~ \forall_Y ~ ...
-2
votes
2answers
33 views

How to find a Boolean expression for a combinational logic circuit?

How to find the logic expression for a logic circuit? For example, this one. I am unsure what the circles before the gates exactly mean.
0
votes
0answers
7 views

Simplifying boolean expression A'(B'C + BD) + A(D(B'C + BC'))

I went from this A'B'CD' + A'B'CD + A'BC'D + A'BCD + AB'CD + ABC'D To this A'(B'C + BD) + A(D(B'C + BC')) Steps: ...
-2
votes
0answers
22 views

How many ways we can interpret $a_1$ or $a_2$ and $a_3$ or $a_4$ or $a_5$ or $a_6 \ldots a_n$? [closed]

In how many ways we can interpret $a_1$ or $a_2$ and $a_3$ or $a_4$ or $a_5$ or $a_6 \ldots a_n$? or, and can be exchangeable. Consider or, and as unknown operators.
3
votes
2answers
435 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 ...
1
vote
3answers
43 views

Show that (P→Q) ∧ (Q→R) is equivalent to (P→R) ∧ [(P↔Q) ∨ (R↔Q)]

I literally have no idea how to start this proof. I get to (P→Q) ∧ (Q→R) = (¬P ∨ Q) ∧ (¬Q ∨ R) and then I get stuck.
0
votes
3answers
18 views

Boolean Algebra - Why does (x'y' + x'y + xy' + xy) = 1

Have the answers to my Design Fundamentals homework but I do not know how they got the answer they did without $(x'y' + x'y + xy' + xy)$ equaling $1$. Thanks
0
votes
1answer
15 views
0
votes
1answer
26 views

Simplifying a logic function using boolean algebra

I have the the following logic function (where $'$ is NOT) $f(a, b, c) = abc + ab'c + a'bc + a'b'c + ab'c'$ I have to simplify it as much as possible using only boolean algebra (no truth tables, ...
5
votes
3answers
110 views

proving logical equivalence $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$

I am currently working through Velleman's book How To Prove It and was asked to prove the following $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$ This is my work thus far ...
2
votes
2answers
850 views

How to apply De Morgan's law?

If for De Morgan's Laws $$( xy'+yz')' = (x'+y)(y'+z)$$ Then what if I add more terms to the expression ... $$(ab'+ac+a'c')' = (a'+b)(a'+c')(a+c)?$$
3
votes
3answers
52 views

Curious identity involving symmetric difference

While studying the properties of measurable null sets, I found the following identity: $\bigcup_i B_k\triangle B_i=\bigcup_i B_i - \bigcap_i B_i $ Or in other words, the value of the expression is ...
0
votes
1answer
331 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') ...
2
votes
1answer
57 views

Constructing order embeddings between Boolean algebras from embeddings from their finite subalgebras

Suppose that $A$ and $B$ are two complete atomic Boolean algebras and $R$ is a relation between $A$ and $B$ with the following property: If $Rab$ and $A^\prime$ is a finite Boolean subalgebra of ...
1
vote
1answer
274 views

Examples of boolean functions in conjunctive normal form

Give an $n$-variable Boolean function $f(x_1; x_2; \cdots ; x_n)$ in conjunctive normal form so that $f$ is $1$, respectively, (a) If at least one of the $n$ variables is $1$; (b) If at most one of ...
0
votes
1answer
19 views

Where am I going wrong with this Boolean simplification problem?

I am self-studying the Nand2Tetris course. I am trying to simplify the Or logic gate as much as possible to simplify my HDL-specified circuit. Using the Sum of Products, I write the following for ...
-1
votes
1answer
23 views

Proper ideal of Boolean ring

Let M be proper ideal of Boolean ring R. Which of the following is/are true? 1.$R/M$ is Boolean ring. 2.$R/M$ $\cong$ $Z_2$ if and only if M is maximal ideal.
1
vote
1answer
27 views

How to know the boolean formula of a boolean function?

Suppose A binary boolean function is showed by a true table. How can I know the (simplest) boolean formula which is interpreted by that function?
0
votes
1answer
462 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 ...
2
votes
1answer
36 views

Follow-Up Help with Truth Tables

I've been trying to solve this circuit problem(and understand it frankly), and I wanted to double check my thought process with the community helpfully. After running the circuit out, I have $A+ \bar ...
0
votes
2answers
628 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 ...
3
votes
1answer
34 views

Simplify a boolean algebra expression: xy + xz' + x'yz

I need to simplify xy + xz' + x'yz into xz' + yz. I know that these expressions are equal in truth value, but I'm not sure how ...
0
votes
1answer
14 views

K-Map reduction

There's an exercise which states that depending on certain rules a led(of different colour) shall turn on or not. There are four leds, so I've made four functions (One each led, through Karnaugh Map ...
0
votes
2answers
31 views

showing Boolean algebra equality

I have this exercise in my worksheet : Show that x (z ⊕ y) = xz ⊕ xy I reached this in solving it , but didn't reach the final equation x(z'y + zy') xz'y + xzy' please can someone show how
1
vote
1answer
3k views

Boolean algebra operation precedence?

In my discrete mathematics class we wrote down the truth table for some Boolean functions and in that table they go in the following order: ¬, ∧, ∨, →, ~, ⊕, |, ↓ So, I assumed that this is the ...
0
votes
2answers
352 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 ...
5
votes
3answers
122 views

Can Boolean ring without unit be embedded into a boolean ring?

While going through a book (Lectures on Boolean algebra, Halmos) I got struck at the following question : Prove that every Boolean ring without a unit can be embedded in a Boolean ring with a unit. ...
1
vote
2answers
2k 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 ...
3
votes
1answer
206 views

Solving special boolean equation set

I have boolean equation sets that look like this (where ^ means xor): eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0 eq 2: 1^x1^x3^x10^x12^x17 = 0 eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0 ...
0
votes
1answer
172 views

Convert expression to NAND only

Endless youtube videos and reading through notes later I am yet again stuck. I have to covert the following to NAND only $$\bar{A}\cdot\bar{B}\cdot\bar{C} + A\cdot\bar{B}\cdot C + A\cdot B\cdot ...
2
votes
1answer
436 views

Trying to simplify the expression $A'B'C'D' + A'BC'D' + A'BC'D + AB'C'D$

So far I've got: $A'B'C'D' + A'BC'D' + A'BC'D + AB'C'D$ $= A'C'D'(B' + B) + C'D(A'B + AB')$ $= A'C'D'(1) + C'D(A \;\text{ XOR }\; B)$ $= C'[A'D' + D(A \;\text{ XOR }\; B)]$ Did I do this ...
2
votes
2answers
48 views

How to simplify this Boolean expression

F=(A+B+C)(A+B+C')(A+B'+C') I used sop method and I am left with A+BC', so the above expression should leave me with (A+B)(A+C'). Iam not able to get to this answer. Help is appreciated.
1
vote
2answers
122 views

Is the following sentence a tautology: $(p\Rightarrow q)\vee(r \Rightarrow p)\vee(r\Rightarrow s)\vee(r\Rightarrow q)$?

If both $p$ and $q$ are false then ($p\Rightarrow q$) is true. If either $p$ or $q$ is true then one of ($r\Rightarrow p$) or ($r\Rightarrow q$) is true. If both $p$ and $q$ are true then all are ...
0
votes
1answer
31 views

Simplifying $(A'+ D) \times [(B \times C) + D']$ in Boolean algebra

$(A'+ D) \times [(B \times C) + D']$ I can rewrite as $(A' + D) \times (D' + B) \times (D' + C)$. Is there a way of simplifying to get to the step of $D' + D = 1$ or $D' \times D = 0$ or any other ...
0
votes
2answers
208 views

Not every boolean function is constructed from $\wedge$ (and) and $\vee$ (or)

Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. Here is my solution, can I ask for a feed back on my solution please? $p∧q$ ...
0
votes
2answers
27 views

Boolean function construction [duplicate]

I need some proof on this statement that not every boolean function is equal to a function constructed by only using ∨ and ∧. I need a boolean function that does not constructed using ∧ and ∨ which I ...
0
votes
1answer
33 views

Homework: Conjunctive Normal Form

The way I understand CNF is as an expression containing AND's of OR's. So an AND-GATE with 3 inputs (A, B and C) should just be A AND B AND C. But apparently this is incorrect. Any guidance would be ...
0
votes
2answers
57 views

Boolean functions built from $\wedge$ and $\vee$ [duplicate]

Prove that not every Boolean function is equal to a Boolean function constructed by only $\wedge$ and $\vee$. Please can you help me giving some hint.
0
votes
2answers
40 views

What is a Boolean Function?

Please explain to me what a Boolean function is, and how do I make an expression. If the statement states that $f=$"she is out of work" and $s=$"she is spending more", how can I write symbolically ...
0
votes
0answers
30 views

how solve this boolean algebra F=A⊗B⊙C=

the function is F=A⊗B⊙C I need to apply De Morgan’s Laws and after that reduce the equation to the simplest form off-course I know how to apply De Morgan’s Laws and reduce but I'm confused about ...
0
votes
1answer
52 views

truth table for followings

Hi I am new to this site. I got an assessment to complete tomorrow. Its about Computer programming, and i am having trouble with these questions. Can anyone please help me. Using truth tables show ...
3
votes
2answers
76 views

Example of a function between boolean lattices that preserves $(\top,\bot,\wedge,\vee)$ but not complements.

Its easy to find boolean lattices $A$ and $B$ together with a function $f : A \rightarrow B$ such that $f$ preserves both top and bottom elements, as well as binary meets, but not complements. ...
0
votes
1answer
54 views

Prove $(A\wedge B)\vee(A\wedge-B\wedge C)\vee(B\wedge-C)=(A\wedge C)\vee(B\wedge-C)$

Let A, B and C be digital inputs. Prove that the following boolean equation holds true for any given values for inputs. (A AND B) OR (A AND (NOT B) AND C) OR (B AND (NOT C)) = (A AND C) OR (B AND ...
1
vote
3answers
53 views

The negation of an implication statement

$$\neg(A \longmapsto B)\lor \neg B$$ Does this this expression simplify to:? $$\neg A\longmapsto\neg B\lor \neg B$$ Which further simplifies to: $$\neg A\longrightarrow\neg B$$
1
vote
1answer
45 views

One implication (on Measure)

Please be noted that charges are finitely additive measures and measure are countably additive ones. Theorem 2.1. Let $\mu$ be a charge on a Boolean algebra $B$. Each of the following conditions ...
1
vote
1answer
34 views

Boolean Algebra and Godel

Can anyone give an example of a theorem in Boolean Algebra that isn't immediately obvious to someone with a computer that can construct a truth table? Clearly no propisition that can be proved using ...
0
votes
1answer
24 views

Simplifying a function using POS and boolean algaebra

I have a function, $$ f = (A+B\cdot \overline C) $$ I am trying to simplify it this form using the inverse function $\overline f$ from the truth table (by anding the rows which form a '0' result). ...
1
vote
1answer
26 views

Simplifying from POS using boolean algeabra

I have a boolean function, f expressed in the Product of Sum form. $$f = (A+B+C)\cdot(A+B+ \overline C)\cdot(\overline A + \overline B + \overline C) $$ On simplification I get, $$ f = ((A+B) + (C ...