Questions tagged [boolean-algebra]

Boolean algebras are structures which behave similar to a power set with complement, intersection and union. Use this tag for questions about Boolean algebras as structures, or about functions defined from/to Boolean algebras. For Boolean logic use the tag propositional-calculus.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

Proving Lindenbaum-Tarski is dens

I need to prove that the Lindenbaum-Tarski algebra is dense in the sense that: if $ [\phi] \leqslant [\psi] $ then there is an $\chi $ such that $ [\phi] \leqslant [\chi] $ and $[\chi] \leqslant [...
1
vote
0answers
36 views

Closure operators on powerset lattices generated by Galois connections from relations

In the book "Residuated Lattices: An Algebraic Glimpse at Substructural Logics" by Galatos, Jipsen, Kowalski and Ono they have this result (Lemma 3.8(2) page 147) If $\gamma$ is a closure ...
0
votes
0answers
34 views

Is the author's truth table incorrect or is my understanding of the order of operations wrong?

To understand enough about Karnaugh maps to solve this problem on 4Clojure (which hosts problems for the programming language, Clojure), I've studied the wiki articles on K-maps, Boolean Algebra, Set ...
0
votes
1answer
45 views

Showing all boolean functions can be expressed by only conjunctions or negations

Let $f:$ {T,F}$^n \rightarrow$ {T,F}, i.e a function of n boolean variables. Show that each $f$ can be expressed as a formula of only conjunctions and negations, and give an upper bound for the number ...
2
votes
2answers
37 views

What is “X happens whenever Y happens”?

This page says "$X$ happens whenever $Y$ happens" translates to $Y \implies X$. But I feel $Y\implies X$ allows $X$ to be $True$ when $Y$ is $False$, which does not seem to be correct for &...
0
votes
1answer
21 views

Simplifying Boolean algebra… What am I missing?

I'm reviewing boolean algebra, but I'm having trouble with a basic simplification: $$\begin{equation}\begin{aligned} &x'z'+ xyz +xz'\\ &= z'(x+x')+xyz\\ &= z'+xyz\\ &= ??? \\ &...
0
votes
0answers
50 views

Boolean Algebra Simplification Unknown Step Introduce Variables

I've been trying to interpret a logical proposition for several days. I need to simplify, I can't do it with the laws that I know, but using online tools I can find the result, but in the step by step ...
0
votes
1answer
28 views

commutative ring to boolean algebra

Let X be a set. We know that $(P(X),\triangle, \cap )$ is a commutative ring with the zero-element $ \emptyset $ and the one-element $X$. $P(X)$ is the power set, $\triangle$ the symmetrical ...
0
votes
0answers
15 views

Amalgamation of Boolean Algebras

In this question of mine, How to prove Craig's interpolation using amalgamation? (which, unfortunately, didn't receive any answers, but has now a bounty!), it was pointed out to me that the first ...
-2
votes
2answers
26 views

Prove that A’C + A’B + BC equals C (A XOR B)’ + A’B [closed]

Prove $$A’C + A’B + BC = C (A \oplus B)’ + A’B$$ Here is what i have tried: $$A’C + A’B + BC = C(A’+B) + A’B$$ Now, need to prove $(A \oplus B)’ = A’+B$ $$(A \oplus B)’ = A'B'+AB = \text{now what??}$$
2
votes
1answer
29 views

proof that any boolean function can be written in canonical form

It's bugging me for a while but although I can vaguely see that when writing canonical forms we kind "build them" in a way specificly to make it be true but I can't grasp exactly why it is ...
1
vote
1answer
54 views

How do I simplify $\overline{X}\overline{Y} + YZ + \overline{X}Y\overline{Z}$?

$$\overline{X}\overline{Y} + YZ + \overline{X}Y\overline{Z}$$ I'm having a lot of trouble simplifying this boolean expression. I used commutative property and re-arranged it as my first step: $$\...
2
votes
1answer
25 views

Are bits defined in a Boolean ring?

Premise: I'm not a mathematician, please be patient. Anyway, if I consider the Galois field $GF(2)$ and two operations $+$ (inclusive or, also denoted with $\lor$) and $\neg$ (negation), where, given $...
4
votes
2answers
41 views

Completeness of a quantifier-free axiomatization of Boolean algebra using partial-ordering

Consider the following set of axioms: $a \leq a$ $(a \leq b \mathrel{\&} b \leq a) \Rightarrow a = b$ $(a \leq b \mathrel{\&} b \leq c) \Rightarrow a \leq c$ $0 \leq a \mathrel{\&} a \leq ...
1
vote
1answer
18 views

Nice description of the Heyting implication for clopen upsets

By the Priestley duality, we know that a lattice can be represented as the clopen upsets of its prime filters space $X$, namely via the map $$ \eta: a \in L \longmapsto \lbrace x \in X \mid x \ni a \...
1
vote
1answer
54 views

why is a regular open (closed) set called “regular”?

Certainly it doesn't have to have an obvious reason other than being sort of "simple" or "nice", but its resemblance to the "regular" in "regular semigroup" (...
0
votes
1answer
21 views

How to simplify my if conditions using Boolean Logic?

My code: ...
1
vote
1answer
22 views

Boolean Property Simplification

I was wondering if there is a term/property/name to describe this simplification: $$A + \overline{A}B = A + B$$ thank you
1
vote
1answer
16 views

Reduce to lowest possible gates

I am trying to reduce (¬A V ¬B) V (A ⊕ B ) to be expressed by the lowest possible number of gates. So far by expanding the XOR gate and using Demorgan's and distributive laws, I have come down to this ...
0
votes
1answer
37 views

Precison on atomless $\sigma$-algebras and their cardinality

Suppose I have an infinite $\sigma$-algebra $\mathcal{A}$ generated by a fixed set of generators whose cardinality is stricly larger than $\aleph_0$. In other words, the set of generators of $\mathcal{...
0
votes
3answers
57 views

Prove that the set {¬,∧,∨} is functionally complete.

So far I have been using the given set to prove the functional completeness of other sets, but I don't know how to prove this one. That seems to be the case for similar questions too.Do I need to ...
0
votes
1answer
25 views

equality in the Boolean algebra of the power set of the power set

Let $A$ be a Boolean algebra, let $p$ be a probability measure an $A$. Let $N = \{1,2,3,...,n\}$ for a fixed $n \in \mathbb{N}$, and let $\epsilon$ be a function from the set of all subsets of $N$ (...
0
votes
1answer
81 views

Cardinality of atomless sigma-algebras

I know that an infinite $\sigma$-algebra $\mathcal{A}$ has at least cardinality $\mathfrak{c}=2^{\aleph_0}$. Suppose now that $\mathcal{A}$ is $\alpha$-generated ($\alpha>\omega$). Clearly, $\...
0
votes
0answers
18 views

Boolean Vector Space basis decomposition

Given $V$ a Boolean Vector Space (i.e., a vector space over $K=\{0,1\}$) of finite dimension, it is known that for every linearly independent sets $A$,$B$, there is $A' \subset B $ such that $|A'| \...
0
votes
0answers
25 views

Solving systems of equations with bitwise operations

There are $x_1,x_2,...,x_k$ as positive integers that are less than $2^n$ with leading zeros (every variable has $n$ binary digits). Given $m$ equations, find all binary digits of these variables that ...
2
votes
0answers
37 views

Enumerating separating subcollections of a set

Let $S$ be a (finite) set, and let $C \subseteq 2^S$ be a collection of subsets of $S$. We say that a subcollection $C' \subseteq C$ is separating if for any two elements of $S$ there exists a subset ...
0
votes
1answer
28 views

Cannot simplify boolean expression (ab'c+bc')' [closed]

I've been trying to simplify the boolean expression $$ (ab'c+bc')' = (ab'c)'(bc')' = a'b+a'c+bc+b'c'. $$ The book gives as a solution: $bc$ Please let me know if I am doing something wrong. Thank you.
0
votes
0answers
13 views

Estimate $\max_{f\in A} L (f)$

We put $\displaystyle| \alpha | = \sum_{i=1}^{n} \alpha_i 2^{i-1} $ for each $\alpha$ from $\{0, 1\}^n$. Let A consists of all Boolean functions $f$, such that $f (x) = f (y), $ if $ | x | = | y | \ (\...
-1
votes
1answer
39 views

DNF conversion of this statement

How to convert this to DNF? $(x\lor{\neg{y}\lor{z}})\land{(\neg{x}\lor{\neg{z}})}$ I have tried de morgans and have got no where. I'm pretty sure its the distributive law but cant work out the steps ...
0
votes
1answer
36 views

Are boolean operations unique?

Are the well known operations of logic sum and logic product (defined by their two truth tables) the unique couple of operations (defined on a two elements set) that realize the axioms of: ...
0
votes
0answers
21 views

For which $n$ symmetric boolean function is monotone

I've got a symmetric function of the form: $$\sum_{\displaystyle1 \le i_1 <...<i_{\left\lceil{\frac{n}{2}}\right\rceil}\le n}\displaystyle x_{i_1}\cdots x_{i_{\left\lceil{\frac{n}{2}}\right\...
0
votes
0answers
27 views

Is this Boolean function monotone, linear and self-dual?

I have a Boolean function, which looks like this: $ f(x,y,z)= (x∨y∧\neg z)∨ y\rightarrow \neg(x\rightarrow z) $ I simplified it to this: $ (\neg x ∧ \neg y )∨ (x ∧ \neg z) $ The questions that I ...
0
votes
0answers
17 views

Find a set of variables for which an specific expression evaluates to true

Description. I have $m \in \mathbb N$ and three possible logical expressions, which I immediately presented in the most convenient notation: $X \to Y = \lnot X \lor Y$ $X \to \lnot Y = \lnot X \lor \...
0
votes
1answer
32 views

Simplify the expression: $A'BC' + A'BC + AB'C + ABC' + ABC$

The online calculator(not posting the name because I don't know if its's allowed) is giving me a different result and I can't find what I'm doing wrong: Mine: $A'BC' + A'BC + AB'C + ABC' + ABC= BC'(A'+...
1
vote
1answer
26 views

Show that the Boolean lattice $B_{n}$ is isomorphic to the $n$-fold product of the chain $[2]$.

For two posets $\left(\Pi_{1}, \preceq_{1}\right)$ and $\left(\Pi_{2}, \preceq_{2}\right)$ we define their (direct) product with underlying set $\Pi_{1} \times \Pi_{2}$ and partial order $$ \left(x_{1}...
1
vote
2answers
30 views

How to simplify $\operatorname{P} ( { C |B,A} )P( { B |A} )P( A ) + P( { {\bar B} |A} )P( A )$?

How to simplify the following probability $\operatorname{P} ( { C |B,A} )P( { B |A} )P( A ) + P( { {\bar B} |A} )P( A )$ $ = P\left( {A,B,C} \right) + P\left( {A,\bar B} \right)$ Can $P\left( {A,B,C} \...
0
votes
3answers
55 views

Predicate logic difficulty [closed]

If $∀x∃y P(x, y)$ is true, can the following be true? $∀x∀yP(x, y)$ or $∃x∀yP(x, y)$ or $∃x∃yP(x, y) $ I understand the order of $X$ and $Y$ matters when the quantifiers are different but can the ...
0
votes
0answers
15 views

Equivalent expression of $p' \cup (p\cap q')$

The proposition $p' \cup (p\cap q')$ is equivalent to $1.$ $p\cup q'$ $2.$ $p\to q'$ $3.$ $q\to p$ $4.$ $p\cap q'$? The given expression can be written as $(p'\cup p)\cap (p'\cup q')=1\cap (p'\cup q')...
0
votes
2answers
55 views

Simplify the Boolean expression A'BC + A'BD' + AB' + AC + ABC + ACD

I'm trying to simplify the expression: A'BC + A'BD' + AB' + AC + ABC + ACD I got to the expression: BC + AC + A'BD' + AB' I know this expression is equvalant to the one above because I verified using ...
0
votes
1answer
26 views

How do I solve the following example using Kmap?

I am trying to solve the SOP function: Em(0,1,2,6,8,9,10). Here's what I got in the table: ...
1
vote
2answers
42 views

An expression for the multilinear joint XOR polynomial over $\{1,-1\}^n$

Preliminary: If $g:\{0,1\}^n\rightarrow \{0,1\}$ then there is a unique multilinear polynomial $f:\{1,-1\}^n\rightarrow \{1,-1\}$ such that $f((-1)^{a_1},\ldots,(-1)^{a_n})=(-1)^{g(a)}$ of all $a\in \{...
1
vote
0answers
36 views

Size of minimal sigma algebra generated by a finite partition

This is what I have to prove: If $A_1, A_2, \ldots , A_N$ partition the set $X$ then cardinality of $\sigma$-algebra generated by $A_1, A_2, \ldots , A_N$ is $2^N$. I claim that $\sigma \left( \{ A_1, ...
0
votes
0answers
24 views

How to simplify boolean function

How can I reduce the expression: $(A + B' + C)(A + B' + C') $ to $ \Rightarrow A + B' + C'$
1
vote
1answer
36 views

I found two definitions for an atom in a boolean algebra, but cannot find a proof of their equivalence.

I want to show that the following definitions for an atom $a$ are equivalent for a nonzero element $a$ in a Boolean algebra $\mathcal{B}$: for all $x\in\mathcal{B},a\leq x$ or $x\land a=0$ for all $...
2
votes
2answers
19 views

Filter and ultrafilter properties in Boolean algebra

In a Boolean algebra $(\mathbb{B}, \vee, \wedge, 0, 1, \neg)$, a ultrafilter $U \subseteq \mathbb{B}$ satisfies If $a \wedge b \in U \iff a \in U$ and $b \in U$. If $a \vee b \in U \iff a \in U$ or $...
1
vote
1answer
19 views

Boolean algebra's filter as a partially order's filter

This is a basic question I'm trying to figure out: why the Boolean's filter definition corresponds to the order-theoretic definition of filter ? Here follows the relevant definitions. Definition 1 (...
0
votes
0answers
56 views

$u_1\vee u_2\vee u_3\vee\dots\vee u_m = u$

Let $u\neq 0$ be any element of Boolean Algebra. Let $u_1,u_2,u_3,\dots,u_m$ be all atoms in $A$ such that $u_1\leq u,u_2 \leq u,\dots, u_m\leq u$. Prove that $u_1\vee u_2\vee u_3\vee\dots\vee u_m = u$...
1
vote
0answers
22 views

Boolean circuits and the definition of a certain function in terms of right-continuity

In an unpublished paper I have read, the concept of a signal trajectory is used. A signal trajectory of a Boolean circuit is defined to be a non-zeno and right-continuous function $h : \mathbb{R^+} \...
0
votes
2answers
53 views

How to simplify boolean expressions.

I'm struggling to understand what rules to apply when simplifying boolean expression. For example: $$ B+(A\cdot(C+B) \overline C) $$ I'm not sure how to simplify this expression. Here is my attempt. ...
0
votes
1answer
22 views

Can logical equivalence be simplified in terms of simpler logical operators

I have been researching the net for an answer, but sadly to no avail. I know implication can be simplified into simpler operators using de Morgan's and associative laws (such as this post here ...

1
2 3 4 5
54