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

-1
votes
0answers
11 views

How to prove that this system of boolean functions is functionally complete? [on hold]

How to prove that this system of boolean functions is functionally complete using other systems of boolean functions. Express operators from a functionally complete set with functions from my set: ...
0
votes
1answer
15 views

Boolean Alegebra De morgans rule 2

hi i am told to perform a simplification using demorgans rule 2. Here is the question ' = Equals Not B . (C + B')' I got B' + (C' + B'') then B' + (C' + B) Now i dont know where ...
0
votes
1answer
14 views

Boolean Algebra expanding using absorption

Hi I have a question regarding the absorption law. I was told that I cannot expand ab = ab + abc by writing ab = ab(1+c). However, I believe you can expand xy = xyz' + xyz by doing xy = xy(z' + z) . ...
0
votes
2answers
48 views

Precedence of nested NOTs in boolean algebra

I have the following equation: $y = \overline{\overline{\overline{x_{1} + \overline{x_{2}}} .x_{2}.x_{1}} + \overline{x_{3}.\overline{x_{1}+x_{2}} + x_{2}}}$ I'm trying to solve it in four ways: ...
0
votes
0answers
6 views

proving properties of (graph) dominance defined via a system of equations

Some notions on graphs can be defined via a system of equations with values in a lattice. For example, dominance $d(v_1, v_0)$ ($v_1$ dominates $v_0$) in a graph $g$ is defined by a system $\forall ...
3
votes
1answer
16 views

Boolean expressions from multiplication to addition and vice-versa

I am trying to change these Boolean expressions into expressions that do not use multiplication. Bolds indicate complements. a) abc b) (ab +c)d And these to ones that do not use addition. c) a + b ...
1
vote
2answers
27 views

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

I am stucked at trying to prove that the set $\{N\}$ of one logical connective is inadequate where $N$ is a quaternary connective that is defined as follows: $N(w,x,y,z)=((x\land y)\land(w\lor z))$ ...
0
votes
3answers
51 views

Boolean Algebra - proof without associativity?

I would like to prove the following: $(x\cdot y) + (\overline{x} + \overline{y}) = 1$ without the Associativity Property. I can't seem to do this algebraically (without truth tables).
1
vote
1answer
14 views

Does disjunction of two Boolean algebra cuts always produce their ideal sum?

Let $(B, 0, 1, \leq, \wedge, \vee, \neg)$ be a Boolean algebra. For a subset $A \subseteq B,$ denote by $L(A) = \{l \in B \mid (\forall a\in A) \, l \leq a\}$ the set of all lower bounds of $A,$ and ...
0
votes
0answers
13 views

how to convert XOR to DNF form?

If I have the expression $X$ xor $Y$ , how do I convert it to DNF form? and $X$ implies $Y$? I only got to the point where I make the truth table for the functions, but after that I could not apply ...
0
votes
1answer
17 views

How do I input this Boolean Expression into a K map?

Determine the minimum SOP, sum of products expression using K-Map F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’ Do i have to actually simplify it first by multiplying ...
1
vote
1answer
26 views

How to simplify Boolean Expression $\bar B + \bar C (B + A)$

I trying to figure out how $ \bar B + \bar C (B + A)$ simplifies to $ \bar B + \bar C$.
0
votes
0answers
11 views

What are The applications of Fast Walsh–Hadamard Transform.

There is a problem requiring the expect value of the intersection of two random subsets selected from a universal set, with the values and the probabilities of subsets given. My friend said it could ...
0
votes
0answers
25 views

Identifying a SSOP (standard sum of products) expression…

Say you're asked to identify a standard sum of products (SSOP) expression from 4 or 5 options... 3 of them are definitely not SSOP (variables are missing between the terms)... however two of the ...
1
vote
1answer
14 views

xor-ing vectors

This question might be wrong on mathematics, but I don't know where else to put it. I have a given equation, and there is one calculation step, that I don't understand. I thought, I have to xor ...
2
votes
0answers
20 views

Does a logical matrix representing sets have a name or special properties?

Imagine a collection of separate objects and several sets. These sets can be represented using a logical matrix. $M = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 ...
1
vote
1answer
27 views

Closedness of $\{ x \in 2^A : x(\neg p) = \neg x(p) \}$ for a Boolean algebra $A$ and $p \in A$

I'm reading Matthew Dirk's The Stone Representation Theorem for Boolean Algebras, and am trying to follow the proof of Proposition 3.4 on p.6: Proposition 3.4. Let $A$ be a Boolean algebra, and ...
0
votes
1answer
11 views

Finding Prime Implicants and Essential Prime Implicants for Boolean Functions

I am trying to solve a EE problem and am unsure whether I doing it correctly. The problem is: Find all the prime implicants for the following Boolean functions, and determine which are essential: ...
0
votes
1answer
28 views

Boolean algebras and rings

I know that M. H. Stone proved that there is a bijection between boolean algebras and boolean rings. The bijection I know is the following: to any given Boolen algebra $(L,\, \vee, \wedge)$ we ...
2
votes
3answers
63 views

Solving this logical puzzle by resolution doesn't work for me

In this document there is a logical puzzle: If the unicorn is mythical, then it is immortal. If the unicorn is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a ...
-4
votes
2answers
42 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
4answers
78 views

How to prove this tautology using equivalences?

I am trying to prove that the following is a tautology: $(A \implies (B \implies C)) \implies ((A \implies (C \implies D)) \implies (A \implies (B \implies D)))$ To make progress, I thought I'd ...
2
votes
1answer
55 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: ...
-1
votes
1answer
20 views

Number of Linear boolean-functions [closed]

How many linear boolean functions are there, if we have n variable?
0
votes
0answers
45 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 ...
0
votes
0answers
18 views

Boolean functions in functionally incomplete boolean operator sets

A set of boolean operators is called functionally complete if and only if any of the $2^{2^n}$ boolean functions in $n$ variables can be represented using a boolean expression that contains operators ...
0
votes
0answers
9 views

Secondary essential prime implicant

I am having problem understanding what excatly are secondary essential prime implicants. Essential prime implicants(PI) are clearly those which cover an output which no other PI is able to cover but ...
1
vote
1answer
40 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
77 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 ...
3
votes
3answers
66 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 ...
1
vote
1answer
21 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 ...
0
votes
2answers
30 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 = ...
0
votes
0answers
25 views

How many solutions does this boolean equation system has?

How many solutions does this boolean equation system has? $$\left\{ ...
3
votes
1answer
24 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
1answer
6 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 ...
0
votes
3answers
42 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. ...
2
votes
1answer
33 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 = ...
-1
votes
1answer
26 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
16 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 ...
3
votes
2answers
35 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 ...
0
votes
1answer
47 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
2answers
18 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
32 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
1answer
20 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 ...
0
votes
2answers
53 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 ...
1
vote
1answer
46 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$ ?
3
votes
1answer
35 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
22 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 ...
0
votes
5answers
55 views

Boolean Simplification of AB + A'+B'

Is there any way to simplify this function? Or is this the simplest equation? : AB + A'+B'
0
votes
0answers
32 views

Question on Boolean Algebra - Atomicity and Completeness

I am trying to solve some Boolean Algebra exercises from the book of Mathematical Logic by Cori and Lascar. I am having some problem in solving a question. Please help me. Thnx in advance. I was ...