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
-3 votes
0 answers
12 views

please solve this $F = xyz + xy' + x'y'z' + xyz'$ [closed]

please solve this $F = xyz + xy' + x'y'z' + xyz'$
user avatar
1 vote
0 answers
12 views

Isomorphism between Boolean algebras $D$ and $B * (D : B)$ (Exercise 16.4 of Jech)

Let $B,D$ be two complete Boolean algebras in $V$ such that $B$ embeds into $D$ as a complete Boolean subalgebra. Let $V^B$ be the Boolean-valued model (w.r.t. $B$). Let $\dot{G}$ be the canonical ...
user avatar
  • 7,538
1 vote
1 answer
61 views

Absolute definition of 'True' and 'False' in Mathematical Logic

I searched for the definition of Truth. According to this Wikipedia: https://en.m.wikipedia.org/wiki/Truth , Truth is the property of being in accord with fact or reality. when I searched for the ...
user avatar
1 vote
2 answers
34 views

Showing that $x^3 + y = y^3 + x$ is an equivalence relation

I am asked to prove that: $x^3 + y = y^3 + x$ is an equivalence relation. So far I have the following: Reflexive: $m^3 +m = m^3 +m$ Symmetric: $m^3 + n = n^3 + m \rightarrow n^3 + m = m^3 + n$ ...
user avatar
0 votes
0 answers
16 views

Boolean algebra simplify with use of complex gates

How to simplify Boolean algebra, And most importantly, "simplify" means at the least use of logic gates | including (nand,nor,xor,exnor...) The Boolean algebra(including K-maps , Quine–...
user avatar
  • 1
1 vote
1 answer
27 views

How to prove that the derivatives of bent functions are balanced? [closed]

Function $F:\mathbb F_2^m\rightarrow \mathbb F_2^n$ is bent iff $$ v \cdot F$$ is bent for all nonzero $v\in \mathbb F_2^n.$ Why is this equivalent to saying $F$ is bent iff $$D_a F = F(x)+F(x+a)$$ is ...
user avatar
  • 49
1 vote
1 answer
24 views

How to show these two Boolean expressions are the same?

How do I show using the laws of Boolean algebra that: $$ (a \wedge c) \, \vee \, (a \wedge b) \, \vee \, (b \wedge c) \equiv (\bar{a} \wedge b \wedge c) \, \vee \, (a \wedge \bar{b} \wedge c) \, \vee ...
user avatar
  • 425
-2 votes
0 answers
21 views

Boolean Algebra: (𝐴𝐵′ + 𝐴′𝐶)′(𝐴 + 𝐶)

can anyone help me simplify (𝐴𝐵′ + 𝐴′𝐶)′(𝐴 + 𝐶) using Boolean laws. My friend told me the answer is AB, this is for my assignment.
user avatar
  • 1
2 votes
1 answer
60 views

I cant smplify the five variable boolean algebra.

I've tried for many times to simplify the five variable boolean algebra but can't get it done. Question $$F = \bar{A}\bar{B}\bar{C}\bar{D}E + \bar{A}\bar{B}C\bar{D}E + \bar{A}B\bar{C}\bar{D}E + \bar{...
user avatar
-1 votes
0 answers
28 views

simplification of boolean expression using k-map

I have the following boolean expression which has to be solved using K-map: ...
user avatar
0 votes
0 answers
22 views

Is every complete Boolean algebra a complete subalgebra of some powerset algebra?

Is every complete Boolean algebra $B$ a complete subalgebra of some powerset algebra $P(X)$, in the sense that the inclusion map preserves infinite meets and joins?
user avatar
-1 votes
0 answers
38 views

Finite state Kleene star machine

I want to represent finite-state machine but I have problems with opening brackets $(a^*dc^* + acd^*)^*$. Should it be $a^*d^*c^* + a^*c^*d^*$? Should I use the first or second image option?
user avatar
  • 1
-3 votes
0 answers
25 views

Convert from CNF to DNF

I have $$f(x4) = (x1∨¬x2)*(x2∨¬x3)*(x2∨x4)*(x3∨¬x4)$$ and I need to solve this using distributive law $x(y∨z)=xy∨xz$ and $A*0=0,\;$ $A∨0=A$ and $A∨A*B=A.$ but I can't understand the last line of the ...
user avatar
  • 1
0 votes
0 answers
35 views

Extending the inclusion map of Boolean algebras using Sikorski's extension theorem (Exercise 7.31 of Jech)

Exercise 7.31 of Jech's Set Theory says: If $B$ is a Boolean algebra and $A$ is a regular subalgebra of $B$ then the inclusion mapping extends to a (unique) complete embedding of the completion of $A$...
user avatar
  • 7,538
0 votes
1 answer
38 views

Karnaugh map and boolean simplification yield unsatisfactory results.[Solved]

My binary logic for my circuit is \begin{array}{|c|c|c|c|c|c|} A &B &C &D &Hallway &Stairs\\\hline 0 &0 &0 &0 &0 &0\\ 0 &0 &0 &1 &1 &1\\ 0 &...
user avatar
1 vote
1 answer
36 views

How is it the case that: Any complete lattice is a Boolean algebra.

In the book “A Functorial Model Theory” by Nourani (pg152), it is stated that However, I didn’t understand what does he mean? Because a complete lattice is not even necessarily distributive whereas ...
user avatar
  • 187
0 votes
2 answers
47 views

Is it possible to convert boolean operations to addition/multiplication modulo $2$?

I mean, is it possible to convert AND OR NOT to simple algebraic expressions? If it's not ...
user avatar
0 votes
0 answers
13 views

Why are the row space and column space lattices of a boolean matrix inverses of each other?

We define the row/column space of a matrix $A$ to be all possible sums of rows/columns of $A$. The row space ($V(A)$) and column space ($W(A)$) form a lattice. See example matrix and respective row ...
user avatar
3 votes
1 answer
137 views

Clarification of the definition of a clone

I've begun studying boolean algebra in mathematical logic, after studying a course on abstract algebra which ended with the definition of boolean lattices, so I'm familiar with some algebraic ...
user avatar
  • 1,121
0 votes
1 answer
47 views

How to proof the property of cofactor?

I'm studying formal verification, and I am faced with the problem: Let $f$, $g$ be Boolean functions. Proof or disproof that $$\neg(f_v) = (\neg f)_v$$ $$(f ⊕ g)_v = (f_v ⊕ g_v)$$ where $f_v$ denote ...
user avatar
  • 15
0 votes
0 answers
20 views

Generating Monotone Boolean Function

I recently went thru an article over Generating Monotone Boolean Function (at https://www.mathpages.com/home/kmath094/kmath094.htm ) but couldn't understand the concept of using 2 monotone functions ...
user avatar
  • 1
1 vote
0 answers
40 views

$FA_{\kappa}(\mathbb{P}) \iff BFA_{\kappa}(\mathbb{P})$, if $\mathbb{P}$ is a $\kappa^+$-cc poset.

I'm trying to prove the question in the title, where the axioms are enunciated like $FA_{\kappa}(\mathbb{P})$ is the assertion that for each colection $\{I_{\alpha} : \alpha < \kappa\}$ of maximal ...
user avatar
  • 1,254
0 votes
0 answers
25 views

Question on Quotient algebra

I was wondering if anybody could help me to solve the following problem I have been thinking about. Manny thanks in advance. Consider the quotient algebra $\mathcal{P}(̩\omega)/fin$, where is fin the ...
user avatar
0 votes
0 answers
27 views

I am missing something important with Boolean Algebra

It seems that almost every Boolean expression I try and solve, I always find a Boolean Discrepancy . I could go back and use a different property, theorem, or law at different points of the process, ...
user avatar
0 votes
1 answer
27 views

Simplification of sum of products

I have the following equation: A'BC + AB'C + ABC' + ABC I know I can simplify one part of the equation factoring AB(C' + C) = AB I looked at the results in an online solver and the simplification of ...
user avatar
0 votes
0 answers
19 views

How to solve $(a+bc)(d'+bc)(a'+d')$ using Boolean algebra

I have done this. is this correct? If wrong, what is needed to be changed? $(a+bc)(d'+dc)(a'+d')$ $ = ad'a' + abcd' + bcd'a' + bcbcd'$ $ = d' + abcd' + bcd'a' + bcbcd'$ $ = d' + bcd' (a + a' + bc)$ $ =...
user avatar
3 votes
1 answer
53 views

Efficient solving of Boolean linear equations systems

Let us assume that we have a collection of 1000 boolean variables: $x_1,...,x_{1000}$ From this collection we sample 10 variables $n$ times with repetition; $100<n<1000$ We construct a boolean ...
user avatar
  • 239
-1 votes
3 answers
38 views

$\overline{(a+\overline{b})\cdot (\overline{a}+b)}$ simplification boolean algebra

For context: I am learning Boolean Algebra by myself for fun and one of the questions in the book I am reading was a long boolean expression and the task was to simplify it to be the XOR boolean ...
user avatar
1 vote
1 answer
42 views

Is plus sign the correct notation for Disjunction in boolean algebra?

As far as I know, the disjunction is notated as $\vee$ in boolean algebra However, in some context, I saw that people usually tend to use the plus sign + to notate the disjunction like this: $$f(x, y) ...
user avatar
  • 13
0 votes
0 answers
35 views

Is there a general poset representation that specializes to power set lattices in case of finite boolean algebras?

I read here that every finite, complemented, distributive lattice is isomorphic to a power set lattice. Is there a general order preserving mapping from a poset $P$ to a set inclusion poset $S$, such ...
user avatar
  • 123
0 votes
2 answers
21 views

Can a CNF formula contain no clause or contain empty clause?

The definition of CNF formula that i found at internet is that CNF formula is a conjunction of clause, and clause is a disjunction of literal. But i haven't found anywhere the answer of whether a CNF ...
user avatar
  • 103
0 votes
0 answers
24 views

Decimal analogue to boolean AND operator?

I am looking for a way of expressing something like: $\sum{a_k} \sum{b_k}, \, a_k \in \mathbb{R}, \, b_k \in \mathbb{R} \tag{1}$ with the caveat that I would like the result to be negative in the case ...
user avatar
1 vote
1 answer
36 views

How can I prove that A or ((not A) and B) is equivalent to A or B?

I tried AND'ing the leftmost A with itself to keep the expression balanced, but then I wasn't able to put A and (not A) in evidence. I was also trying to apply De Morgan's Theorem, but I cannot AND ...
user avatar
0 votes
0 answers
23 views

Comparing distributions of binary valued vectors: covariance matrix is enough?

Say we have two discrete distributions, $\vec{y}\sim p_y$ and $\vec{x}\sim p_x$, for both of which, data vectors have binary-valued entries: $\vec{y}\in\{0,1\}^n$ $\vec{x}\in\{0,1\}^n$, where $n$ is ...
user avatar
  • 73
7 votes
2 answers
150 views

Why is this part of the composed proposition false?

Currently I'm studying logic, but I do not understand a certain step. It is the step from row $2$ to $3$. I see that $-q$ is the common factor on both sides of the middle or operator, but I did not ...
user avatar
  • 545
1 vote
1 answer
43 views

Is the collection of set algebras of a finite set itself a Boolean algebra?

For example, say $\Omega$ is a finite set and $(\Omega,S,\mu)$ is a probability triple defining the uniform distribution over atoms of $\Omega$. The meet algebra of two sub-algebras of $S$ is well ...
user avatar
0 votes
2 answers
32 views

Tautology problem

Show that $((p \vee q) \wedge \neg (\neg p \wedge (\neg q \vee \neg r))) \vee ( \neg p \wedge \neg q) \vee (\neg p \vee r )$ is a tautology (without using truth table). After simplification I got $ ((...
user avatar
1 vote
1 answer
48 views

Examples of Complete Atomless Boolean Algebras

What are some natural examples of complete atomless Boolean algebras? I am aware of the regular open algebra on the Euclidean space. But are there more? Thanks!
user avatar
3 votes
2 answers
127 views

Characterising functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying special equations

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ be a function. Is it possible that $$ \sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(x+a)}= 0, $$...
user avatar
  • 23.1k
4 votes
1 answer
130 views

Every boolean function is multiplicative with probability greater than $1/2$

Let $f:\left\{-1,1\right\}^n\to\left\{-1,1\right\}$. How to show that $$ P_{{x,y,z}} \{f(xyz)=f(x)f(y)f(z)\} \ge 1/2? $$ where $x,y,z$ are distributed uniformly and independently on $\left\{-1,1\right\...
user avatar
  • 23.1k
0 votes
0 answers
37 views

$(p \rightarrow q) \land (\lnot p\rightarrow q) \equiv q$

Prove that $(p \rightarrow q) \land (\lnot p\rightarrow q)$ is logical equivalent to $q$ by using a chain of logical equivalences. The question states explicitly not to use a truth table. I tried the ...
user avatar
  • 588
0 votes
0 answers
10 views

Is this expression in a POS form?(doesn't matter if it is in a canonical form)

A'B' + A'CD + A'DE' and I sould convert it to POS, is what I worte below correct?(I already mentioned that it should necessarily be in a canonical form) (A')(B' + CD + DE')
user avatar
0 votes
0 answers
26 views

Meaning of expression

I am studying boolean algebra, would anybody know what the below symbol before the letter means: Thanks
user avatar
0 votes
0 answers
27 views

Boolean Algebra - What does this mean

I am reading a book on Boolean Algebra and at one point it had this expression: It said that if a,b (weird E) (weird B), then a or b = b or a Any idea what the "weird" E means and the whole ...
user avatar
2 votes
0 answers
104 views

Reversing a complex boolean function

I am trying to reverse-engineer the DRAM address function of a memory controller. This is a function that maps a physical address to a DRAM bank. More formally, I am trying to find functions $f_i$ for ...
user avatar
  • 71
0 votes
0 answers
35 views

Bidistributive implies boolean algebra

Honestly I'm not sure if this question is appropriate here so I will likely remove it after I get an answer unless I am told otherwise. This comment on reddit https://www.reddit.com/r/math/comments/...
user avatar
  • 130
1 vote
1 answer
63 views

I'm studying boolean algebra in the discrete mathematics

problem Let $a_4a_3a_2a_1a_0$ be a 5- bits binary numbers (each $a_i=0$ or $1$). Write an expression in Boolean algebra that evaluates to $1$ when odd number of bits of the number is $1$ and $0$ ...
user avatar
  • 55
1 vote
0 answers
32 views

Generalization of Łoś theorem to infinitary logic

"It is straightforward to check that, essentially by the same proof as for $\mathcal{L}_{\omega \omega}$, Łos’s Theorem 0.6 holds for $ \mathcal{L}_{\kappa \kappa } $ and ultraproducts by $\kappa$...
user avatar
0 votes
1 answer
62 views

Filters in Boolean Algebras

I started to study set theory; my question is about definition of filters in Cori-Lascar's book Mathematical Logic. Definition (Filter): A filter in a Boolean Algebra $\mathcal{A}=(A,+,\times,0,1)$ is ...
user avatar
0 votes
0 answers
17 views

How many 3 variable monotonically increasing boolean function exist?

Assume the definition of monotonically boolean function is a boolean function either is constant or is the sum of products with all positive literals. How many functions exist with three variables?
user avatar

1
2 3 4 5
59