How many self-dual Boolean functions satisfy specific conditions?

  • Thread starter mathwo
  • Start date
  • Tags
    Function
In summary, for a Boolean function of n variables, the number of functions that are not self-dual and satisfy the condition f(0, 0, . . . , 0) = f(1, 1, . . . , 1) can be calculated by subtracting the number of self-dual functions from the total number of functions. And for the condition f(0, 0, . . . , 0) = 1, the number of independent function values must be taken into account.
  • #1
mathwo
1
0
A Boolean function of n variables is a mapping f : {0, 1}^n to {0, 1}. . Determine the number of Boolean functions f of n variables such that
(i) f is not self-dual and f(0, 0, . . . , 0) = f(1, 1, . . . , 1),
(ii) f is self-dual and f(0, 0, . . . , 0) = 1.
I think for the first part, i need to find the number of functions that is not self-dual, then find the number of functions i need from it? For the second part,i absolutely have no clue, please help me with this question.
 
Physics news on Phys.org
  • #2
For the first part, I would calculate the number of self-dual functions, and the number of functions where f(0, 0, . . . , 0) = f(1, 1, . . . , 1). As all self-dual functions satisfy that condition, both numbers are sufficient to get the answer.

For the second part: Well, you know f(1, 1, . . . , 1) as well. How many independent function values are left which you can choose?
 

What is a self-dual Boolean function?

A self-dual Boolean function is a type of Boolean function that has the same output when the inputs are inverted. In other words, the function remains unchanged when all of its inputs are switched to their opposite value.

What are some examples of self-dual Boolean functions?

Some common examples of self-dual Boolean functions include the NOT, NAND, NOR, and XNOR gates. These gates have the same output as their inverse when all inputs are inverted.

How are self-dual Boolean functions useful in computing?

Self-dual Boolean functions are useful in computing because they can simplify logic circuits and reduce the number of gates needed to implement a function. They also have applications in error detection and correction codes.

What is the difference between a self-dual and a complement function?

A self-dual function is a type of Boolean function that remains unchanged when all inputs are inverted, while a complement function is one that produces the opposite output when all inputs are inverted. In other words, a self-dual function is its own complement.

How are self-dual Boolean functions related to duality in Boolean algebra?

Self-dual Boolean functions are related to duality in Boolean algebra because they exhibit a fundamental property of duality, which is that switching all inputs and outputs in a function results in an equivalent function. This duality is important in the analysis and simplification of Boolean expressions.

Similar threads

A Constructing PDFs for Max Likelihood Density Estimation Problem
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Null space of dual map of T = annihilator of range T
    • Calculus and Beyond Homework Help
Replies
0
Views
450
I How to determine if a set is a semiring or a ring?
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
MHB All boolean functions are computed by a depth 2 circuit
    • Set Theory, Logic, Probability, Statistics
Replies
20
Views
4K
I How to calculate expectation and variance of kernel density estimator?
    • Set Theory, Logic, Probability, Statistics
Replies
9
Views
2K
I Probability: why can we use the Dirac delta function for a conditional pdf?
    • Set Theory, Logic, Probability, Statistics
Replies
12
Views
3K
MHB Please help with bool algebra and logic things
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
MHB Finding MLE for $\theta$ of Statistical Product Model
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
I On (real) entire functions and the identity theorem
    • Calculus
Replies
2
Views
791
Convex Optimization: Dual Function Definition
    • Calculus and Beyond Homework Help
Replies
4
Views
1K

Hot Threads

Recent Insights

Back
Top