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
2answers
482 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 ...
1
vote
1answer
136 views

Simplifying Boolean Function

I am in a computer class with Karnaugh Maps and one of the questions is X 'Y Z + X 'Y 'Z + 'X Y 'Z + X Y Z and I need to simplify it where ' means not so 'x means not x. I think the answer is X 'Y ...
1
vote
2answers
133 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 ...
2
votes
2answers
168 views

Proving a Logic Equation

I have two information. $x+y = 1$ and $xy = 0$. Now,I need to prove this equation : $xz + x'y + yz = y + z$ What I tried: $z(x+y) + x'y = z + x'y$ Thats all What do you think?
0
votes
0answers
159 views

Simplifying Boolean expression: $F(a,b,c,d)$

I have a Boolean function below and I need to simplify it. F(a,b,c,d) = !a&&!b&&d || !a&&c&&!d || !a&&b&&!c || a&&!c&&!d || ...
5
votes
2answers
297 views

Simplify $(A+C)(AD+AD) + AC + C$ using Boolean algebra

I have solved the equation like this: ...
2
votes
2answers
139 views

Negation bar meaning?

I know that the horizontal bar on top means it's a negation. But I've never encountered one over more than one term like this one: $\overline{\bar{x} + \bar{y}x}(y + \overline{xy})$ Is that ...
2
votes
1answer
119 views

Commutative ring addition where $a^2 = a$

I'm trying to solve following question: If $a^2=a$ for all $a \in R$ where $R$ is a commutative ring, then $a+a=0$. I have tried to solve this problem for a while now and I'm more or less stuck. I ...
-1
votes
1answer
147 views

Boolean logic simplification

To simplify $$ A'B'C'D + A'B'CD' + A'BC'D' + A'BCD + AABC'D + ABCD' + AB'C'D' + AB'CD $$ I have no idea how to start the first step. Thanks in advance!!
1
vote
2answers
78 views

boolean logic simplify

To prove: $(X+Y)(X'+Z) = XZ + X'Y$ I try to simply $(X+Y)(X'+Z)$ to $XZ + X'Y + YZ$ then I have no idea how to simply further. Thanks in advance!!
0
votes
1answer
127 views

Simplify the expression below by using the Algebra laws:

Simplify the expression below by using the Algebra laws: $$ AB + \overline{(\bar AC + B)\cdot \overline{(\bar B \oplus C)}} $$
0
votes
2answers
129 views

Boolean algebra simplification

I have the equation (CD)+(BC'D'+A'B'C'D)+(C'D') and I can't seem to simplify it enough for my homework. I've tried multiple ways of simplifying the equation and I keep ending with an extra variable D. ...
1
vote
1answer
82 views

How to find/generate a 6 variable Bent Function?

I want to find a Bent Function with 6 variables. I read some papers about how to generate Boolean Functions, but I don't want to implement an algorithm from zero just to find one function. It is also ...
0
votes
3answers
77 views

Three Boolean Algebra Proofs - I just don't get it!

I'm having a very difficult time proving the following 3 expressions: $$\begin{align*} &x\cdot y\cdot z+x'\cdot z=y\cdot z+x'\cdot z\\ &x\cdot y+y\cdot z+x'\cdot z=x\cdot y+x'\cdot z\\ ...
0
votes
2answers
34 views

Discrete: Boolean Function

~(pV~q) v (~p^~q) is equal to ~p? I know the answer is yes and I've been using DeMorgans initially then distributive law after. However I keep messing up on the algebra. Help is appreciated so I can ...
2
votes
1answer
644 views

Simplify Boolean Expression ABC' + A'BC + A'B'C'

Can anyone help me simplify this boolean expression? ABC' + A'BC + A'B'C' EDIT: (only using AND gates (multiply [(x)(x)]) and OR gates (addition [+]))
2
votes
2answers
287 views

Steps to simplify a Boolean Expression

Simplify: (x ∧ y) ∨ (x ∧ ¬y) ∨ (¬x ∧ y) I need to simplify this using the using properties going step by step. I keep ending up with (x ∧ y) as the answer but when I map is out I get that is should ...
-1
votes
1answer
778 views

sum-of-products expansions of these Boolean functions

Find the sum-of-products expansions of these Boolean functions. $a)$ $F(x, y) = \text{~}x + y$ $b)$ $F(x, y) = x \text{~}y$ $c)$ $F(x, y) = 1$ $d)$ $F(x, y) = \text{~}y$
0
votes
1answer
656 views

Conclude the premise using rules of inference

First question I have solved I belive... show, s -> (q -> r) <-> (s ^ q) -> r using the defintion of implication and Boolean algebra. s ->(~q V r) <-> ~ (s ^ q ) V r ~s V (~q V r ) <-> ~s ...
1
vote
4answers
4k views

how many semantically different boolean functions are there for n boolean variables?

In short, this is an assignment question for a course I am taking - the exact wording is this: "Given n Boolean variables, how many 'semantically' different Boolean functions can you construct?" ...
1
vote
1answer
190 views

Expressing boolean functions using the not or operator

I need to express these with $\downarrow$ $x+ y + z$ This one I think I can do, I guess at it and copy the wikipedia page since my book has no explanation on how to do this I get $(x \downarrow y ...
1
vote
0answers
60 views

Given a finite set of points construct a polynomial that meets the points.

Say I have a set of points in $\mathbb{Z}^3 \times \mathbb{Z}_2$ each of which represent part of a mapping $(z_1, z_2, z_3) \mapsto z_4 \in \mathbb{Z}_2$. How do I find the the simplest polynomial ...
3
votes
1answer
48 views

The set of all polynomial functions from $\mathbb{Z}^3 \rightarrow \mathbb{Z}/(2)$

Let $f:\mathbb{Z}^3 \rightarrow \mathbb{Z}_2$ be a polynomial function in $\mathbb{Z}[x_1, x_2, x_3]$. Then $f$ has the form $f(x_1, x_2, x_3) = c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_1 x_2 + c_5 x_1 ...
0
votes
1answer
127 views

Prove that S is a Boolean Algebra

Let $n\ge1\in\Bbb N$, we define the set of binary boolean vectors with $\varphi^n .$ Prove that $\varphi^n$ is a boolean algebra. So (...) I know that: Let $\varphi=\{0,1\}, \mathrm ...
1
vote
3answers
590 views

Is “(p AND q) OR r” logically equivalent to “p AND (q OR r)” ??

In the context of discreet math / boolean algebra / logic, is "(p AND q) OR r" logically equivalent to "p AND (q OR r)"? I believe so, but my professor said: ...
1
vote
2answers
334 views

Proving boolean algebra property

Let $S$ a boolean algebra; $a,b,c \in S$ prove that $(a'+b)'+(a'+b')'=a$ Then: $(a'+b)'+(a'+b')'= (a')'+b'+(a')'+(b')'=a+b'+a+b = (a+a)+(b+b')=a+1=1$ Maybe i'm wrong but I think that the problem is ...
-1
votes
1answer
108 views

Simplification of boolean expressions

Question 1 $$\begin{align*}A'BC + AB'C + ABC + A'B'C' &=A'B C + B' C (A +A') + ABC\\ &=A'B + C + B'C + ABC \end{align*}$$ Question 2 $$\begin{align*}A'B + B'C + CB &=A'B + C(B +B')\\ ...
1
vote
1answer
3k views

Boolean-expression simplification $F = AB'C + (A'B' + ABC'D)'$

Here are my solutions. Hence: I am stuck on where or what path I am going to take Problem: F = AB'C + (A'B' + ABC'D)' Solution 1 --------------- F = AB'C + (A'B' + ABC'D)' = AB'C + (A'B')' (ABC'D)' ...
1
vote
0answers
24 views

Proving a boolean algebra question [duplicate]

Let $\sqsubseteq$ be a boolean ordering of the boolean algebra $X$, which means that for each $x$ and $y$ the following applies: $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v ...
2
votes
0answers
101 views

Matrix of integers to boolean matrix

My Question is about converting a matrix of numbers, say each row is an item and each column is a feature of the item. The features are currently integers but I want to convert the feature ...
1
vote
1answer
272 views

Check if tautology (w/o truth table)

$(A+B)(A+C)(B+C) = AB + AC + BC$ is a tautology (checked with Wolfram Alpha) and not hard to see if you apply duality principle $(invert + * 0 1)$ But how to prove with simplyfication It'S not much ...
2
votes
2answers
72 views

Ist it a tautology w/o truth table

AB + CD = (A+C)(A+D)(B+C)(B+D) is a tautology (checked with wolfram alpha) I have to prove this whith boolean algebra but I don't get it right. That'S what I have: AB + CD = A(C+D)B(C+D) AB + CD = ...
0
votes
1answer
27 views

Create a simple expression that is larger than zero if and only if a-b > 0 and c-d < 0

Ok, this is simple but I cant figure out a solution to it. I have four signals, a, b, c, d. I want to generate a signal when a-b > 0 and c-d < 0. This signal should be in the form of an algebraic ...
0
votes
1answer
245 views

Using induction to prove universality of gate

Can we use induction to prove gate(like NAND) is universal. If so how?
1
vote
1answer
50 views

Are ordinal spaces extremally disconnected?

The wikipedia article on ordinal spaces claims that they are not extremally disconnected: However, they are not extremally disconnected in general (there is an open set, namely $\omega$, whose ...
3
votes
1answer
45 views

Looking for an algebraic structure

I'm looking for the name of algebraic structures (in which the elements are partially ordered) with the following properties: Top element defined, bottom optional; Join defined for all elements, ...
1
vote
4answers
5k views

Boolean Algebra: Simplifying multiple XOR and XNOR

Is there any way to simplify a combination of XOR and XNOR gates in the following expression? I have tried multiple boolean theorems and I have not been able to simplify this any further: The ...
-1
votes
1answer
74 views

Product of Sums Minimzation. Please help! [closed]

Minimize the product of sums expression. (x + y + z!)(x + y! + z)(x + y! + z!) Please help! I am not sure whether to factor out by grouping or to factor out a x etc.
0
votes
2answers
148 views

Rewrite equivalent boolean function for p ⇔ q

Using only the operators ⇒ (conditional) and ∼ (negation) Rewrite p ⇔ q How should I go about this? Thanks
2
votes
1answer
227 views

Converting into CNF Form

If you have disjunctive clause comprising of n literals for example $(X_1\cup X_2\cup X_3\cup\cdots \cup X_n)$. where $n\geq 4$. How you can convert it into CNF (Conjunctive Normal Form) of $n-2$ ...
1
vote
2answers
44 views

Question about poset and boolean ordering, inf and sup

We have a poset $(X, \sqsubseteq)$, and we define operations $+$ and $\cdot$ by $x+y=inf(x, y)$ and $x\cdot y=sup(x, y)$ ($+$ can be seen as union in sets and $\cdot$ as intersection in sets). The ...
0
votes
3answers
690 views

Boolean-expression simplification F = [ AB ( C + (BC)' ) + AB' ] CD'

Basing on that problem. All I have in my solution is this: mystep1:[AB(C +(B' + C')) + AB']CD' mystep2:[AB(CB'+ CC') + AB']CD' mystep3: [AB(CB') + AB']CD' mystep4:[B(A+C+B') + ...
2
votes
1answer
312 views

Solving Boolean Expressions with Theorems

I'm having the hardest time wrapping my head around this stuff. This is a homework problem, one of many. I just need some help on what to do. ...
1
vote
0answers
189 views

Sum-of-products to product-of sums conversion

I need to convert $A'B'C'$ from sum-of-products form to product-of-sums form. I used a K-map and I'm not sure if the answer is $C' + AB' + A'B' + A'B$ or just $AB' A'B' + A'B$. I think that by ...
1
vote
2answers
47 views

Boolean simplification of $AB'(B' + C)$

Simplifying $AB'(B'+ C)$, then using the distributive property I know I would get $AB'B' + AB'C$ I am just confused as to how to simplify $B'B'$
0
votes
1answer
80 views

Correctness of answers and question about sup en inf

In $A=\{2, 3, 6, 12, 36, 72, 108\}$ we define the relation $R$ by $aRb$ if $b=a$, or $b=2a$ or $b=3a$. Q1: Draw the graph of $R$ and list which properties $R$ has. A1: The properties are: ...
0
votes
1answer
91 views

Condition for the boolean algebra of clopen sets to be extremely disconnected.

Let $X$ be a topological space and let $\Gamma \mathcal O(X)$ be it's boolean algebra of clopen subsets. For compact totally disconnected space, show that $\Gamma \mathcal O(X)$ is complete (as a ...
2
votes
1answer
77 views

Can a minimal representation of a Boolean Function be 1 or 0

After using the Karnaugh map to find the minimal representation of a Boolean function, my answer is 1. Is 1 a valid answer for minimal representation? If yes, what is the implication of a Boolean ...
2
votes
2answers
130 views

Order of operations for logic operations?

I have some code, that does a comparison to find how many of set of values fall within a range defined by a mean±sd, like this: ...
0
votes
2answers
76 views

How to prove boolean ordering question

Let $\sqsubseteq$ be the boolean ordering of $X$, so for every $x$ and $y$ applies $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v \sqsubseteq a$ and $w \sqsubseteq b$. Show that ...