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

2
votes
0answers
13 views

Construct an OR gate when missing input information

Is there a way to construct an OR gate when the input for one combination is unknown? For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = ...
7
votes
2answers
40 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
0
votes
3answers
33 views

How to convert a truth table to boolean expression?

If I have a huge truth table, it's hard for me to construct an expression. I know a problematic method, the Disjunctive Normal Form. But I found that I cannot reduce the huge expression. ...
0
votes
0answers
16 views

Complexity of computing a posiform of a quadratic pseudo-boolean function

I am reading the chapter 13, Pseudo-Boolean functions, of Boolean Functions: Theory, Algorithms, and Applications by Crama et. al. In section 13.2, the authors introduce the idea of Posiform. The ...
0
votes
1answer
12 views

Boolean algebra consensus theory

I want to simplify $wxy + x'z + y'z + wz = wxy + x'z + y'z$ but I can't seem to use the consensus theorem at the right place. I tried factoring cases for $x$ and $x'$ and $y$ and $y'$ but I don't ...
0
votes
0answers
10 views

Pure Literal Rule what if a variable exist only in negated form in CNF

I am trying to solve a simple SAT problem. The initial SAT is: ...
0
votes
1answer
43 views

Finite boolean algebra can be embedded into $\mathcal P(n)$.

I am trying to show that every finite boolean algebra can be embedded into $\mathcal P(n)$ for some large $n$. Any hints?
0
votes
2answers
23 views

How do you find the minterm list of a boolean expression containing XOR?

Let's say I have a boolean expression, such as F1 = x'y' ⊕ z . How do I go about finding the minterm list for that expression? The method I've tried is to take each term, such as x'y' and z, ...
0
votes
1answer
32 views

Reduce Boolean Expression

Note: A B = A and B A + B = A or B The expression: r = a̅ c̅ b + a̅ c b̅ + a c̅ b̅ + a c b Simplify?
1
vote
2answers
65 views

Calculation of Shannon entropy given the mutual information of Binary strings

Suppose $A$ and $B$ two different binary strings of length $l$. Suppose the Mutual Information (https://en.wikipedia.org/wiki/Mutual_information) of $A$ and $B$ is known to be $I$. Now suppose ...
2
votes
1answer
31 views

Stuck at simplifying boolean expression

I'm getting stuck at the following boolean expression. z + (x'y) + (xy') + (xt') + (yt') In my solutions its simplified and the (yt') term is gone. How do they simplify this? I really cant see ...
0
votes
1answer
27 views

Boolean algebra-Boolean ring. Stone Theorem?

I am interested in knowing which theorem is responsible for the following statement: Every Boolean algebra can become a Boolean ring by taking the ring addition to be $A\oplus B = (A \land \lnot B) ...
1
vote
0answers
11 views

reducing Boolean expression to minimum literals

I'm finding it tough to simplify these types of expressions. Here's my problem: $(a+b+c')(a'b'+c)$ I have to reduce this to the minimum number of literals. So far I've only broken it down to: ...
2
votes
2answers
42 views

Why is the dual of a filter an ideal?

Jech's set theory, (3rd edition) says that if $F$ is a filter on $S$ Let $I = \left\{ {S - X: X \in F}\right\}$ then $I$ is an ideal of $S$ (dual to $F$). However, let $X,Y \subset S$, $X \in I$ ...
1
vote
1answer
19 views

Simplifying a Boolean function from a Kernaugh Map

Given the three variable Karnaugh Map: x\yz 00 01 11 10 \___________________ 0 | 0 1 1 0 1 | 1 0 0 1 I am supposed to write a ...
1
vote
1answer
27 views

Boolean Algebra fundementals

A disjunction A OR B truth table has A , B , and A OR B but mine has A ,B C, with A or B or C could some please explain this
0
votes
0answers
17 views

Simplification to DNF

To get right to the point. I have written a test which required me to Simplify to DNF. And the following equation gives me trouble. Here is the equation: ...
4
votes
1answer
43 views

Boolean algebras, Stone theorem and being isomorphic to a field of sets

I'm a little bit confused about duality between boolean algebras and topological spaces or sets. I know the following theorem (which is due to Stone, as far as I know): Every boolean algebra $B$ ...
0
votes
2answers
21 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
19 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
52 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
8 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
22 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
33 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
55 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
16 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
16 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
19 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
32 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
18 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
26 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
22 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
29 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
18 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
29 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
73 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
50 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
80 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
61 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
24 views

Number of Linear boolean-functions [closed]

How many linear boolean functions are there, if we have n variable?
0
votes
0answers
51 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
24 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
11 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
44 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
85 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
72 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
27 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
89 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
27 views

How many solutions does this boolean equation system has?

How many solutions does this boolean equation system has? $$\left\{ ...