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
48 views

Can you calculate the common volume on excel using Boolean Operation

I would like to calculate the common volume of a solid like the one below but at different angles. I can achieve this using ANSYS Design but I was wondering whether it is possible to calculate this on ...
1
vote
1answer
33 views

Proof of distributivity of implication over implication

The Wikipedia page on the distributive property claims one should be able to distribute implication over implication (Distribution of implication): $$ P \...
0
votes
1answer
908 views

boolean algebra minterm and maxterm expansion

I have an expression I'm not sure if i got right. The expression is $$ f(a,b,c) = a(b + c') $$ what i did was multiplied them out and added missing variables. which gave me $$ abc + abc' + ac'b + ac'...
-1
votes
3answers
50 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 ...
0
votes
0answers
42 views

What is the logical expression of undecidability? [closed]

undecidability = not false and not true = not (false or true) decidability = false or true then can true and false coexist? and, if we express undecidability of true or false in logic, ...
1
vote
0answers
23 views

Parameter activity in boolean expression

As a Continuation to my first question I have found a way for determining the activity of each parameter. Activity definition: activity of each parameter is its contribution to get the whole ...
0
votes
1answer
65 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 ...
3
votes
1answer
39 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 ...
0
votes
1answer
2k views

Number of self dual functions and number of inputs for which self dual function is 1

I came across this slides which states following two theorems: Theorem There are $2^{2^{n-1}}$ different self-dual functions of $n$ variables. Theorem Let $f$ be a self-dual function of $n$ ...
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
21 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
112 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') ∪...
-5
votes
1answer
77 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$,$...
2
votes
1answer
44 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 $...
1
vote
1answer
41 views

Boolean functions question

I am trying to solve exercise 1.29(a) from Ryan ODonell's Analysis of Boolean Functions which says that given $ f:\mathbb{F}_{2}^{n} \rightarrow\{-1,1\} $ such that $ dist(f,\chi_{S^{*}})=\delta $ for ...
0
votes
1answer
763 views

finding essential prime implicants

F(w,x,y,z)=Σ(0,1,2,4,5,6,7,10,15) which one is correct, or both wrong. i'm confused about finding prime implicants at top right and bottom right
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 $...
9
votes
5answers
48k views

Prove XOR is commutative and associative?

Through the use of Boolean algebra, show that the XOR operator ⊕ is both commutative and associative. I know I can show using a truth table. But using boolean algeba? How do I show? I totally have ...
0
votes
1answer
33 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
35 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
91 views

Precision on the incompleteness of the field of clopen subsets of the Cantor space

Let $F$ be the field of clopen subsets of the Cantor space $2^\omega$. Then $F$ is countable, atomless, and incomplete. Question: What does incomplete mean precisely? Does that mean that not every ...
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
2answers
34 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
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
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 ...
3
votes
2answers
283 views

Poset is complete iff it is cocomplete

In Awodey's Category Theory, page 130, he says: A poset is (co)-complete if it is so as a category, thus if it has all set-indexed meets (resp. joins). For posets, completeness and cocompleteness ...
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}\...
1
vote
0answers
62 views

Relative consistency of ZF with respect to IZF

Is there a forcing argument of this fact? Can anybody point me to the place? The reason I'm asking is because I was reading Heyting-Valued Models for Intuitionistic Set Theory by R.J. Grayson, yet ...
1
vote
1answer
954 views

Simplify ABC+AB'C+A'BC+A'B'C+A'B'C'

ABC+AB'C+A'BC+A'B'C+A'B'C', AC + A'BC + A'B'C + A'B'C', C(A+A'B+A'B') + A'B'C', C(A + A'(B+B') + A'B'C', C ( A + A') + A'B'C', C + A'B'C', but true answer is C+A'B. Help me, what I missed?
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: ...
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 \...
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?
4
votes
1answer
696 views

Is the minimal conjunctive normal form for positive formula unique? If so, how do you calculate it?

I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms. $$A$$ $$A \land (A \lor B)$$ The minimal example is $A$. Does ...
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. ...
1
vote
1answer
3k views

How many presentable boolean functions with n attributes are linear separable?

The aim is to find a formula for the question. For $n=2$ i get $2^{2^n}=16$ possible functions. This is the solution for a boolean function with 2 attributes: ...
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 ...
0
votes
1answer
40 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
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: ...
1
vote
1answer
884 views

How can I rewrite this xor formula to generate cnf formulas

$$ \bigwedge_{c=1}^n\bigwedge_{i\epsilon S}\bigoplus_{r=1}^nX_{irc} $$ I have tried $$ \bigwedge_{c=1}^n\bigwedge_{i\epsilon S}\bigwedge_{r_1=1,r_2=1}^n(X_{ir_1c}\vee X_{ir_2c})\wedge(\neg X_{ir_1c}\...
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
59 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 ...
8
votes
4answers
673 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
4
votes
1answer
97 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$?