2022 Developer Survey is open! Take survey.

# Questions tagged [boolean-algebra]

The tag has no usage guidance.

253 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

### How many different boolean functions exist up to permutation of its $n$ variables

i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them ...
1 vote
23 views

### Why do we use {+1, -1} in place of {0, 1} for the Fourier analysis of boolean functions?

I want to know what will change if we keep on using {0,1} for our Fourier analysis of boolean functions? What are the things, which can not be performed with {0,1} and can be done with {+1, -1}?
• 11
1 vote
19 views

### Fourier Dimension of Boolean functions

I was recently reading about Fourier dimension of Boolean functions. What I understand is that if we take the Fourier expansion of $f: \{\pm1\}^n \to \{\pm1\}$ and consider the monomials with non zero ...
15 views

### Boolean Expression and Logic Circuit

In a fish tank, the health of goldfish depends on the pH value of the water, temperature and oxygen level of the water in the tank. A sensor based control system is to be developed to make a healthy ...
1 vote
152 views

### Clarification regarding linear boolean functions!

I am a little confused when it comes to linear boolean functions. According to this post: What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to ...
• 13
10 views

### simplification of boolean expression using k-map

I have the following boolean expression which has to be solved using K-map: ...
1 vote
19 views

### How to come up with combination a short-circuit evaluation table?

(a || b) || (c && d)) Given the above, how do I derive the table below: a b c d output T - - - TRUE F T - - TRUE F F T T TRUE F F T F FALSE F F F - FALSE I'm told that this is short ...
• 11
1 vote
39 views

### Influence of a variable in composition of Boolean functions

Suppose $f$ and $g$ are Boolean functions without a constant term, and where every variable has the same influence. How to show every variable will have the same influence in $f \circ g$? To me it ...
56 views

### Is $f(X)f^d(X) = 0$ for a Boolean function $f$?

I'm currently trying to understand a step in the proof for in the Crama and Hammer book on Boolean Functions. The proof is Proposition 4.12, which claims that the self-dualization of Boolean $f$ is ...
• 419
1 vote
45 views

### Is [F(a, b, c) = a' + b] functionally or logically complete?

I'm having a problem determining whether [F(a, b, c) = a' + b] is functionally(logically) complete or not. I would really appreciate it if you could help me. P.S: I can't have 1 or 0 as input.
28 views

### Can element occur in a CNF formula?

For example, is $(X \vee 1)$ a valid formula in conjunctive normal form (CNF)? If yes, then I would have to consider such formulas when trying to prove a statement about all CNF formulas.
• 103
1 vote
29 views

### Is there an algorithm for generating non comparable boolean vectors?

First some context: A Boolean Network of $n$ components is a function $f$ from the set $\{0,1\}^n$ (set of vectors of $n$ components whose values are 0 or 1) to itself. The dynamical behavior of a ...
• 111
18 views

### sum of Boolean characters larger degree

I was curious if someone knew the answer/reference for the following. So it is well-known that if $S\in \{0,1\}^n$, then $$\frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{\langle S, x\rangle}=1$$ if and ...
28 views

### Is there an efficient way to generate a pseudo-boolean function from a linear constraint?

I would like to define a pseudo-boolean function $f$ such that $f(x) = 0$ for all logically valid combinations of $x\in{0,1}$ and $f(x) > 0$ for all logically invalid combinations of $x\in{0,1}$. ...
• 121
25 views

### graph representation of a Boolean function

I'm trying to classify a certain family of Boolean functions, and need to represent the function as a graph. Is there any well-known graph representation for a Boolean function that captures the ...
42 views

### Stalmarck's method: x ≡ x → z, does z have to be true?

I have been researching Ståmarck's method 1. In the paper cited here, some rules are given. Rules are made of triplets (x, y, z) such that: y $\to$ z $\equiv$ x where x, y and z are booleans which ...
• 53
1 vote
21 views

### Is there a known relationship between Kolmogorov Complexity of a binary string and the logic optimization of the corresponding Boolean function?

I haven't thought about how to go about proving it or finding a counterexample (I probably don't have the right background), but it seems intuitive to me that, given some representation of a Boolean ...
27 views

### Can anyone solve this? Is the answer 4 or 7. I'm confused

I'm trying to solve this but I'm confused with different answers. I'm getting 4 but the answer written is 7. Please guide me.
1 vote
32 views

• 309
241 views

### Can every sentence of first-order logic be converted into an equisatisfiable equation in Boolean algebra?

There may be some theoretical literature, unknown to me, that addresses this question. If possible, I would like a practical approach to this problem. My attempt involves the use of an equational ...
92 views

### For a logic gate to be universal, must it necessarily be able to perform duplication?

It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to ...
• 103
1 vote