How many self-dual Boolean functions satisfy specific conditions?

  • Thread starter Thread starter mathwo
  • Start date Start date
  • Tags Tags
    Function
AI Thread Summary
The discussion focuses on determining the number of self-dual Boolean functions under specific conditions. For the first condition, the approach involves calculating the total number of Boolean functions that are not self-dual and satisfy f(0, 0, ..., 0) = f(1, 1, ..., 1). The second condition requires identifying self-dual functions where f(0, 0, ..., 0) = 1, prompting a consideration of the independent function values available for selection. The participants emphasize the need to analyze both self-dual and non-self-dual functions to arrive at the correct counts. Overall, the thread seeks clarity on the calculations and logic behind these Boolean function properties.
mathwo
Messages
1
Reaction score
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
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?
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top