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

-4
votes
1answer
180 views

Do 'sum-of-products' and 'product-of-sums' represent the same function?

Do 'sum-of-products' and 'product-of-sums' represent the same function? Does it have be the same expression or not? In case it is different, what does it mean? Context: I've just made a Karnaugh map ...
2
votes
1answer
243 views

Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$. For example: ...
2
votes
2answers
97 views

Show that every boolean function with 3 variables can be represented with maximum number of 10 gates

I need to show that every Boolean function with 3 variables can be represented with maximum number of 10 gates, limited to the following: AND(2 ins), OR(2 ins), NOT(1 in). I tried to find Boolean ...
3
votes
3answers
87 views

What's the relationship between continuity property of Lebesgue measure and continuity on a metric space?

This is a topic from Lebesgue measure in $\textit {Carothers' Real Analysis}$: I know how to prove Theorem 16.23. However, I can not figure out why he names this property as continuity? Besides ...
-2
votes
1answer
26 views

Number of Linear boolean-functions [closed]

How many linear boolean functions are there, if we have n variable?
0
votes
0answers
97 views

Translating English to symbolic logic

(Question prompt) The domain of discourse in this problem is the set of students and teachers at a school. Define the following predicates: • E(x, y): x has sent a letter to y. • P(x): x is a ...
1
vote
1answer
45 views

Prove that a boolean function using only $\vee$ and $\wedge$ must attain the value $1$ at least once

Please give me feedback on this Prove that a boolean function constructed only by using $\vee$ and $\wedge$ (without using $\sim$ ) must attain the value $1$ at least once.
4
votes
1answer
93 views

$\sim p$ ,$\sim\sim\sim\sim\sim p$ , and $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim p$ . Which of these are equal?

I made an attempt on this question. Please guide me if its wrong. Consider the following boolean fuctions: $\sim p$ ,$\sim\sim\sim\sim\sim p$ , and $\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim\sim ...
1
vote
1answer
127 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
2answers
8k views

Boolean Algebra: a+a'b = a+ab = a?

a(a'+b) = aa'+a'b = a'b (aa' = 0 in any case) a+a'b = 1a + a(a'+b) = a(1+a'+b) = a a+ab = a(a+b) = a => a+a'b = a+ab However when I use truth table to compare the result of a+a'b to a+ab when a = ...
1
vote
1answer
100 views

Essential Prime Implicants and Minterm Expressions

I have an exam for a university course shortly, and upon reviewing one of my assignments I have come to realize that I don't understand why I have lost marks/how to do a couple of questions. Hopefully ...
2
votes
1answer
131 views

karnaugh map simplification

I really wonder why my method is wrong. Could you explain step-by-step and why my methods wrong. Drawings includes just one time isn't it enough for simplification ? First boolen expression: $$ F = A'...
3
votes
1answer
43 views

How would one solve this boolean algebraic equation?

During software testing I needed to find at least one solution for this: (a or (b and c)) != ((a or b) and c) Where all variables are boolean. I can (and did) ...
0
votes
3answers
45 views

Prove that $x+(\overline{x}\cdot\overline{y})=x+\overline{y}$

Prove that $x+(\overline{x}\cdot\overline{y})=x+\overline{y}$ The values of both these boolean functions show that these 2 are equivalent. ...
3
votes
1answer
462 views

Cardinality of the set of ultrafilters on an infinite Boolean algebra

Let $\mathfrak B$ be a Boolean algebra with an infinite power $\kappa$. My question is how many ultrafilters does it have? $\kappa$ or $2^\kappa$? Or even smaller?
0
votes
1answer
13 views

how to simplify (x+y')X(x+z')?

Hi this is for a Discrete Math test I have today. I can barely understand the simplification of boolean expressions. Can anyone show me if the (x+y')X(x+z') can be simplified further, what are the ...
-1
votes
1answer
64 views

Boolean Expression Simplification XOR

I have been trying to express XOR in terms of just the '&' and '~' operators. I have managed to get the original XOR definition (~x & y) | (x & ~y) down to ~(x & y) & ~(~x & ~...
1
vote
1answer
420 views

Boolean Simplification

I'm having some trouble getting a handle with this course. We are starting Boolean algebra and my professor wants us simplify the following: (AB)'+(A'+B')'= (AB)'+BC+A'B'C'= I am assuming the "()" ...
2
votes
2answers
106 views

How to find the minimum expression(s) of a set of fixed-width bit fields?

If we define $x_1 x_2 \cdots x_n$ as a bit field of width $n$, and each element $x_i$ may be $0$, $1$, or wildcard $*$. A set of 4-width bit fields $\{0000, 0001, 0100, 0101\}$ can be aggregated ...
0
votes
1answer
64 views

Boolean Algebra: Is this equality or inequality?

Consider: $$xy + x'y' + yz = xy + x'y' +x'z$$ Is this equality true? I know I could a truth-table but I prefer doing it algebraically. I think there's something tricky here (Like adding a term, ...
1
vote
1answer
139 views

simplifying boolean expression in maxterm

Should I expand the equation to simplify? Π(1,4,5,6). It means $$ F = (A + B + C')(A' + B + C)(A' + B + C')(A' + B' + C) $$ I have expanded and found $$ = ( C' + AC + A'B)(A' + BC + B'C') $$ I haven't ...
0
votes
5answers
121 views

Boolean Simplification of AB + A'+B'

Is there any way to simplify this function? Or is this the simplest equation? : AB + A'+B'
1
vote
1answer
51 views

An effective way to find missing minterms

I've been messing with logic formulas lately and there was one thing that was often causing me headache. I'll describe it briefly. When using Quine-McClausky's algorithm for finding MDNF and MCNF, I ...
1
vote
1answer
138 views

How many binary bit strings of length 32 are there

How many binary bit strings of length 32 are there? I think I know the answer but I'm not sure...wouldn't it just be $2^5$ ?
2
votes
2answers
67 views

Simplifying $(\neg x\land \neg y \land \neg z) \lor (\neg x\land \neg y \land z) \lor (x\land \neg y \land z) \lor ( x\land y \land z)$

I'm looking at this logical formula: $(\neg x\land \neg y \land \neg z) \lor (\neg x\land \neg y \land z) \lor (x\land \neg y \land z) \lor ( x\land y \land z)$ Asked to simplify it as much as ...
1
vote
2answers
26 views

Boolean Algebra - reducing a function

Let $$f(w,x,y,z) = w'x'y'z' + w'x'yz' + wx'yz'$$ How can you reduce it to: $$x'z'(w' +y)$$ Thanks!
0
votes
1answer
27 views

A Criterion For a Set To Have all the Atoms of a Boolean Algebra

Let $\Omega$ be any set and let $\mathcal A$ be an algebra of sets in $\Omega$. An element $E\in \mathcal A$ is said to be an atom if there is no non-empty element $A\in \mathcal A$ such that $A\...
0
votes
1answer
37 views

Boolean algebra proof - I don't know why this is valid!

So this is the answer proof I was given, I'm stumped by the final application of the Idempotent law (where does that 1 come from!?) As I understood it a 0 or 1 can only come from a combination of A ...
0
votes
2answers
1k views

How many ways are there to sit 4 people from a group of 10 people around a circular table where two sittings are considered

How many ways are there to sit 4 people from a group of 10 people around a circular table where two sittings are considered the same when everyone has the same immediate left and immediate right ...
3
votes
1answer
56 views

How to prove an equality in a Lindenbaum-Tarski algebra?

Let $\mathscr{L}'= \mathscr{L}\cup \mathscr{C}$ be an extension of the language $\mathscr{L}$ with a new infinite set of constants $\mathscr{C}$, and $T$ be an $\mathscr{L}$ theory. I wish to show ...
2
votes
1answer
30 views

Each Element of an Algebra can be Partitioned into “Atoms”

Let $\Omega$ be any set and let $\mathcal A$ be an algebra of sets in $\Omega$. An element $E\in \mathcal A$ is said to be an atom if there is no non-empty element $A\in \mathcal A$ such that $A\...
2
votes
1answer
418 views

What is the difference between Boolean logic and propositional logic?

As far as I can see, they only employ different symbols but they operate in the same way. Am I missing something? I wanted to write "Boolean logic" in the tag box but a message came up saying that if ...
2
votes
2answers
23 views

simplifying boolean expression in minterm

i am trying to simply the equation and stuck. Sum symbol(2,4,6,7). It means $$ F = A'BC' + AB'C' + ABC' + ABC $$ $$ = A'BC' + AB'C' + AB(C' + C) $$ $$ = A'BC' + AB'C' + AB $$ After the last equation ...
0
votes
1answer
46 views

expanding boolean expression as maxterm

$$ F = A + B'C $$ The expression has bothered. I've tried to expand the expression in maxterm, however, I'm stuck on the $B'C $ part. My approach is like this $$ = A + (B'B) + (C'C) + B'C $$ $$ = (A + ...
0
votes
3answers
1k views

3 input XOR gate

I am just beginning in computer engineering and need help with a problem. I have to implement a circuit following the boolean equation A XOR B XOR C, however the XOR gates I am using only have two ...
1
vote
1answer
11k views

How does it evaluate A XOR B XOR C?

I am trying to solve the following combination, ...
0
votes
1answer
52 views

Reference for the fact: elements as union of atoms in a Atomic Boolean lattice [closed]

I need a reference to a book with the following statement: "In a Atomic Boolean Lattice every element is the union of the atoms under lie it". Does not matter if it is presented as a exercise.
1
vote
1answer
128 views

Consensus Theorem: Legal to use redundant terms to find more redundant terms?

When using the Consensus Theorem in Boolean algebra to minimize an expression, is it a legal move to find and add a redundant term to the expression and then use that term to find more redundant terms ...
1
vote
3answers
1k views

Boolean Algebra: Simplifying $\;xyz + x'y + xyz'$

Given the following expression: $xyz + x'y + xyz'\,$ where ($'$) means complement, I tried to simplify it by first factoring out a y so I would get $\;y(xz + x' + xz').\,$ At this point, it appears ...
0
votes
1answer
32 views

Basic Boolean Algebra Multiplication Question

I have the following term $$ t1: \overline {\overline{x1x2\Leftarrow\Rightarrow x1x3}\Leftarrow\Rightarrow x2x3} $$ which I already converted to this: $$ t2: ((x1x2\overline{x1x3} + \overline{x1x2}...
2
votes
1answer
50 views

Equivalent form of biconditional

I'm reading How to Prove It: A Structured Approach (Velleman) Second Ed. Doing all the end of chapter exercises for chapter 1 and having trouble on problem 5a which reads Show that $P \...
1
vote
1answer
44 views

The proof of that a → b is equivalent to ¬b → ¬a using algebraic identities by ArsDigita

I'm noob practicing with discrete math problems, and not sure if the solution ArsDigita provided for this one is correct or not: Prove that a → b is equivalent to ¬b → ¬a using algebraic identities. ...
1
vote
0answers
40 views

Monotonic operators in classical logic

Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
0
votes
1answer
36 views

Simple Boolean Algebra Question

I have the following term in front of me: $$(AB+AC+\overline BC+B\overline C)*(A+\overline B+C+D)$$ and just need to multiply the whole thing which should result in this: $$(AB+ABC+ABD+AC+A\...
1
vote
1answer
279 views

Understanding comparability in a partially ordered sets with Hasse diagrams

I'm doing a section on directed graphs and Hasse diagrams right now on partially ordered sets, and I'm trying to understand what it means for two elements in a Hasse diagram to be comparable. For ...
1
vote
1answer
35 views

Convert boolean expression to pos then nor only

I'm trying to convert a + xb + xyz to POS then to nor only. First I got, a'(x' + b')(x' + y' + z') by using the duality rule but then I get confused after that. Thanks.
0
votes
0answers
29 views

Find boolean function

Given $\mathbb{B} = \{true, false\}$, and function $f: \mathbb{B} \times \mathbb{B} \times \mathbb{B} \to \mathbb{B}, f(a,b,c) = a \land b \lor c,~ \forall a,b,c \in \mathbb{B}$. I want to find a ...
1
vote
1answer
157 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 +...
2
votes
0answers
39 views

Solving equation set with boolean operators and very specific format

I have to write a program to solve a set of equations like the following (+ is XOR and * is <...
1
vote
1answer
3k views

Verify Demorgan's Law Algebraically

If $\overline X \equiv \text { not }X$, De Morgan's Laws are stated as: $ \overline{(A + B)}= \overline A\cdot \overline B$ $ \overline{(A\cdot B)} = \overline A + \overline B$ Verify the above ...