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
2
votes
1answer
33 views

Proving $\|x=y\|\cdot \|\phi(x)\|\le\|\phi(y)\|$ in Boolean valued models

This question relates to the Boolean algebra approach to forcing. Fix a complete Boolean algebra $B$. I'm writing $\|\sigma\|$ for the Boolean value of $\sigma$, where $\sigma$ is a sentence of the ...
-2
votes
2answers
42 views

Prove that with n variables there are 2^2^n possible boolean functions

I have tried looking it up on the Internet; however, most of the results did not make sense to me. I know that the statement is true, but how do you mathematically prove it? For reference the proof ...
1
vote
2answers
42 views

Polynomial size Boolean circuit for counting number of bits

Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
0
votes
0answers
20 views

Proof of Demorgan's theorem by Principle of Duality. Is it valid?

I chanced upon a seemingly "too good to be true" proof of Demorgan's theorem for boolean algebra, however I'm not quite sure if it's valid. The principle of duality states that for a boolean algebra, ...
3
votes
5answers
106 views

Proving the identity: (A\B) ∪ (B\C) = (A∪B) \ (B∩C)

Trying to prove the following identity: (A\B) ∪ (B\C) = (A∪B) \ (B∩C) I worked algebraically on the expression on the left and reached: (A\B) ∪ (B\C) = (A∩B') ∪ (B ∩ C') = ((A∩B') ∪ B) ∩ ((A∩B') ∪...
2
votes
1answer
43 views

Stone representation theorem and $\sigma$-isomorphism

By Stone representation theorem we know that every Boolean algebra $\mathcal{B}$ is (Boolean) isomoprhic to the Boolean algebra of the clopen-sets of its associated Stone space. If $\mathcal{B}$ is a $...
-5
votes
1answer
74 views

Is is possible to determine if a given number is xor combination of some numbers?

I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$...
0
votes
2answers
25 views

Given one of De Morgan's laws, prove the other from it using equivalences.

I have one of De Morgan's laws (in propositional logic). I would like to prove the other law from the first using a sequence of equivalences (Resolution). One is not allowed to use truth tables or ...
1
vote
0answers
32 views

Beginner question, linear algebra over $\mathbb Z_2$. Xor forward and backward transform.

Being an electrical engineer, I have mostly worked in continous domains with $\mathbb R, \mathbb C$ as fields for elements of functions as well as matrices. Now this question relates to operations in $...
0
votes
1answer
31 views

Boolean algebra simplification with DeMorgan Laws [closed]

I can't simplify the following expression: $$x·y'+z+(x'+y)·z'$$ I've tried to multiply the last term with the guys in the parentheses but I can't go any longer. Thanks in advance.
1
vote
3answers
33 views

I cant simplify this A’B’C + A’BC + A’BC’ + AB’C + ABC boolean expression to A'B+C

I have to get this expression A’B’C + A’BC + A’BC’ + AB’C + ABC to A'B+C. I did this but i cant finish itm i dont know how to. A’B’C + A’BC + A’BC’ + AB’C + ABC A'B(C+C')+C(A'B'+AB'+AB) A'B+C(A'B'+...
0
votes
1answer
32 views

Conditional and Biconditional Statements Exercise

Going through Velleman's How to Prove it, I came across the problem: Prove $(P \rightarrow R) \wedge (Q \rightarrow R) = (P \vee Q) \rightarrow R$ Solution: $$(\neg P \vee R) \wedge (\neg Q \vee R)...
0
votes
1answer
45 views

What is activity of argument in boolean function and the norm of a function?

1) I having problem understanding the concepts of activity of specific variable of a boolean function. For instance if we are given F= (x1'x2)XOR(x3 v x4')x5 ...
0
votes
2answers
41 views

NOT ((NOT A AND NOT B) OR (A AND NOT B)) simplification using de morgans law

I had my AS mock exam today, and this question came up. I've checked it on calculators and it says it simplifies to B, which is what I got in the exam, but I'm not entirely sure how I got there. My ...
0
votes
2answers
33 views

Boolean Algebra with and without top

In Wikipedia, the Boolean algebra is defined as a 6-tuple $(A,\wedge,\vee,\neg,0,1)$. In Kuratowski1976, on the other side in the definition on page 34, there is no $1$. Halmos1963 has the $1$. ...
0
votes
2answers
27 views

How to understand this boolean function notation?

I came across the following definition of a particular boolean function: $$ f(x_3, x_2, x_1, x_0) = (1101\phantom{a} 0001\phantom{a} 1101\phantom{a} 0001) $$ I am not sure how to interpret this ...
0
votes
0answers
38 views

Boolean Algebra simplification help

A'B'CD' + A'BCD + AB'C'D + AB'CD + ABC'D' I have tried using a k map and I got it down to AC'D' + A'B'CD' + A'BCD + AB'CD. Also I think AB'C'D + AB'CD can be simplified to ABD' Trying to simplify ...
0
votes
0answers
47 views

Difference between two indicator functions

I have an indicator function $\mathbb{1}(A)$ that equals to one if A is true. I am interested in simplifying the following difference between indicator functions: $$ \mathbb{1}\left\{\sum_{j^{\prime}\...
0
votes
0answers
15 views

About countable boolean algebras

my question is concerning the article from book "countable boolean algebras and decidability", Goncharov. here we sat homomorphism from A to B image 1 here we define composition of ideals (I×J), and ...
0
votes
2answers
51 views

Associative Law for Boolean Logic

The associative law states that for the logic formula: $$(A \wedge B) \wedge C = A \wedge (B \wedge C)$$ $$(A \vee B) \vee C = A \vee (B \vee C)$$ I asked myself would the associative law hold for ...
0
votes
1answer
47 views

Need help - Boolean Logic -Deductive Reasoning

I am trying to self study Probability Theory. Below is an equation that came up from the chapter about Plausible Reasoning. The goal is to prove that below equation can be deduced to the following: ...
2
votes
2answers
40 views

Example of a finite Heyting algebra that is not Boolean

Simple question: what are some simple examples of a finite Heyting Algebras, that is not also a Boolean Algebra?
1
vote
1answer
36 views

How do I move from the $5$ NAND-gate xor solution to the $4$ NAND-gate xor solution?

When trying to make boolean functions out of logic gates, I tried to make the NAND ($\uparrow$) equivalent for the XOR function: $(a \land \lnot b) \lor (\lnot a \land b)$ $$\begin{align} (a \land \...
0
votes
1answer
39 views

Question concerning Boolean Algebra of pairs

I am reading a book "Boolean Algebra" by R.L. Goodstein. In section 2.19 of the chapter "Self dual system of axioms", I am not able to comprehend what the author is trying to say in the first line of ...
0
votes
2answers
48 views

Question regarding Boolean Algebra of pairs

Why is the union of $(A_1, B_1), (A_2, B_2)$ defined as $(A_1 \cup A_2, B_1 \cap B_2)$ and why is the intersection of $(A_1, B_1), (A_2, B_2)$ defined as $(A_1 \cap A_2, B_1 \cup B_2)$? What is the ...
1
vote
1answer
28 views

Characterisation of a maximal filter

Let $F \subset B$ be a proper filter. Prove that $F$ is maximal if and only if for all $p \in B$ with the property that $p \wedge q \ne 0$, for all $q \in F$, the $p$ is also in $F$. I've used a ...
1
vote
2answers
52 views

Simplifying propositional formula

[a ^ ¬(b^c^d)] V [a^b^ ¬(c^d)] V [¬a^b^¬(c^d)] V [a^b^¬c^d] V [a^b^c^¬d] =[a^¬(b^c^d)] V [b^¬(c^d)] V [a^b^¬c^d] V [a^b^c^¬d] =[a^¬(b^c^d)] V [b^¬c] V [b^¬d] V [a^b^¬c^d] V [a^b^c^¬d] =[a^¬b] V [a^¬...
0
votes
0answers
29 views

Seeking set of solutions to make a boolean expression true

I have a boolean expression filled with values that I don't know. Here is the example I'm working with: ...
0
votes
0answers
7 views

Tseytin transformation for equations with more than 2 inputs

My goal is to transfer logical equations, such as $x_1=x_2\ NAND \ x_3$ into CNF form. From the Wikipedia page of Tseytin transformations, I learned that a direct translation exists for equations with ...
0
votes
1answer
32 views

Simplification of the boolean expression using boolean algebra

Simplify the following expressions to the simplest expression using De Morgan's theorem and Boolean algebra. ABC+A'CD+B'CD =(AB+A'D+B'D)C =(AB+(A'+B')D)C =(AB+(AB)'D)C can anyone simplify it ...
3
votes
1answer
57 views

Jech Set Theory (3rd Edition) Exercise 7.33

I have managed to free some time for my Set theory quest and have almost concluded chapter 7 (filters and Boolean algebras) of Jech. At this point I am left with only two exercises that I don't fully ...
4
votes
1answer
96 views

Is it possible to express disjunction through conjunction and implication?

This question is about Boolean functions. Is it possible to express disjunction $x\lor y$ through conjunction $x\land y$ (or simply $xy$) and implication $x\to y$?
0
votes
1answer
25 views

Simplify the expression: $\sim ((p\rightarrow (\sim q \vee r))\wedge (\sim p \wedge \sim q \wedge \sim r ))$

Simplify the expression: $\sim ((p\rightarrow (\sim q \vee r))\wedge (\sim p \wedge \sim q \wedge \sim r ))$ Correct answer: $p\vee q\vee r$ I don't know how to start on this problem. Are there ...
0
votes
0answers
24 views

Represent the following function $X \rightarrow Y$

Let the functions $\blacktriangle $ and $\blacktriangledown$ be defined as $X\blacktriangle Y = \sim (X\wedge Y) $ and $X\blacktriangledown Y = \sim (X\vee Y)$ Represent the following function ( ...
0
votes
0answers
33 views

a) Show De Morgan's law $\sim (X\blacktriangle Y) \leftrightarrow (\sim X\blacktriangledown \sim Y)$

Let the functions $\blacktriangle $ and $\blacktriangledown$ be defined as $X\blacktriangle Y = \sim (X\wedge Y) $ and $X\blacktriangledown Y = \sim (X\vee Y)$ a) Show De Morgan's law $\sim (X\...
3
votes
1answer
48 views

Describing type spaces

I have been getting stuck on this type of question: "Let $T$ be this and that theory. Give a concrete description of $S_n(T)$ for each $n$." I don't see how to start with this kind of problem. ...
0
votes
1answer
31 views

Simplify Boolean expression (ABCD) or (ABC’D’) or (A’B’CD)

I know the answer but I wanna know how to get there. The answer is (A or C)(A or B’)(A’ or B)(C or D’)(C’ or D) This has the same truth table, and in this form you can simplify further to (A or C) (...
1
vote
0answers
9 views

Does Sørensen–Dice Coefficient only account for true positives?

I'm working in a project on medical image segmentation which uses the Dice Score as part of the loss function, but I got some doubts with the commonly adopted implementation. The definition of Dice ...
8
votes
4answers
670 views

Is there a general effective method to solve Smullyan style Knights and Knaves problems? Is the truth table method the most appropriate one?

Below, an attempt at solving a knight/knave puzzle using the truth table method. Are there other methods? Source : https://en.wikipedia.org/wiki/Knights_and_Knaves
1
vote
1answer
43 views

What is the relationship between propositional calculus, set theory, and Boolean algebra?

The connective $∧$ (conjunction) in propositional logic is essentially the same as ∩ (intersection) in set theory if one thinks of 'false' as 'not a member' and 'true' as 'a member'. De Morgan's laws, ...
0
votes
1answer
30 views

if $B$ is a boolean algebra and $a\neq b$ in $B$ there exist an ultrafilter containing $a$ but not $b$.

Suppose $a$ and $b$ are distinct elements in a boolean algebra $B$. I am trying to show there is an ultrafilter on $B$ containing $a$ but not $b$. Does this follow from the fact (is this a fact?) that ...
1
vote
1answer
50 views

Simplifying logic formula

I'm trying to learn some alghoritms of boolean logic and I encountered a problem wich i don't understand. There is a expression and I don't understand how to simplify it. $$(A \wedge \neg B) \vee(\...
0
votes
1answer
36 views

Boolean Algebra (Matrix?)

I am new to Boolean Algebra and I'd just like to know: Is it possible to encode boolean logic into a matrix such that successive powers of that matrix perform logical computations? For example, given ...
0
votes
2answers
32 views

Absorption laws in Boolean algebra

Does anyone know how to prove the absorption laws in Boolean algebra? i.e. $$x + (x * y) = x$$ $$x * (x + y) = x$$ Thankyou so much
0
votes
5answers
53 views

Simplify (p v (r v q)) ∧ ~(~q ∧ ~r)

I understand that ~(~q ∧ ~r) simplifies down to (q v r), but I don't understand how the answer to this question is ...
0
votes
0answers
32 views

Boolean function: prime implicants - disjunctive minimal form

I applied the Quine-McCluskey method to determine the respective prime implicants for a boolean functions and find a disjunctive minimal form. We have the function \begin{equation*}f(x_1, x_2, x_3, ...
0
votes
0answers
25 views

Do Boolean Algebra,propositional logic,and set theory share laws of operation?

There's a lot of laws that have same ideas in Logic operations and operations of set. (Examples : I.$((P∧Q)∨R) = ((P∨R)∧(Q∨R))$ and $((A∩B)∪C) = (A\cup C)\cap(B\cup C)$,II.De Morgan's Laws.etc) ...
1
vote
1answer
16 views

Relationship between algebras of sets

Let $\mathcal{N}$ and $\mathcal{M}$ be algebras of sets on $S$ and $T$ respectively. Let $\mathcal{N}\times\mathcal{M}$ the algebra generated by the rectangles in $S\times T$ (i,e the sets with the ...
0
votes
2answers
33 views

Subset proof, show A⊆B

So I was reviewing this question and Im lost on how to do this question, and Ive seen to of misplaced the notes. The question is as follows: if (A ∩ C) ⊆ (B ∩ C) and (A ∩ C̅) ⊆ (B ∩ C̅) then A ⊆ B ...
0
votes
0answers
18 views

Extension of a homomorphism on a boolean algebra into a complete boolean algebra

I'm trying to prove the following: Let $A$ be a subalgebra of a Boolean algebra $B$, let $u\in B$ and let $A(u)$ be the algebra generated by $A\cup\{u\}$. If $h$ is a homomorphism from $A$ into ...