2 Replies - 2252 Views - Last Post: 08 January 2016 - 04:47 PM

#1 rshah  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 37
  • Joined: 21-October 15

How many different functions are there in bool->bool->bool?

Posted 31 October 2015 - 03:40 PM

Hey guys!

I've got a question:

Quote

How many different (in the sense of calculating different truth-tables) functions are there in bool -> bool -> bool?


My answer to this question (which was wrong), was:

Quote

Because of a possible result of only true and false, we can say that there are 2nc (2 to the power of the number of different combinations). For two variables we can have four combinations: a, a ̅, b and b ̅. Similarly if we have 4 variables, there are 2x2x2x2=24 combinations for them. Hence we can say there are 2n combinations between the variables. Therefore we get 2nc = 2^(〖(2〗^n)) combinations between them all.


Can anyone help explain as to why this is wrong? And maybe give me a better answer? Thanks!

Is This A Good Question/Topic? 0
  • +

Replies To: How many different functions are there in bool->bool->bool?

#2 gonzaw  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 46
  • Joined: 18-December 12

Re: How many different functions are there in bool->bool->bool?

Posted 30 December 2015 - 08:43 PM

Generally, if you have a function "a -> b", then there are "#b ^ #a" possible instances (i.e definitions) for it, considering #a the number of instances of type a and #b the number of instances of type b.
For example, #Bool = 2 because it has 2 instances (True+False).

In your example, you have a function "Bool -> Bool -> Bool" which is equivalent to "Bool -> (Bool -> Bool)". Because of the above rule,
#(Bool -> (Bool -> Bool)) = #(Bool -> Bool) ^ #Bool

By using the same definition on "#(Bool -> Bool)" we get:
#(Bool -> (Bool -> Bool)) = #(Bool -> Bool) ^ #Bool = (#Bool ^ #Bool) ^ #Bool

We can simplify it to this then:
#(Bool -> (Bool -> Bool)) = (#Bool ^ #Bool) ^ #Bool = #Bool ^ (#Bool * #Bool) = 2 ^ (2*2) = 2 ^ 4 = 16


Therfore there are 16 possible functions for "Bool -> Bool -> Bool". I can enumerate them all here:
<Result for True*True, Result for True*False, Result for False*True, Result for False*False>

1) <True, True, True, True>
2) <True, True, True, False>
3) <True, True, False, True>
4) <True, True, False, False>
5) <True, False, True, True>
6) <True, False, True, False>
7) <True, False, False, True>
8) <True, False, False, False>
9) <False, True, True, True>
10) <False, True, True, False>
11) <False, True, False, True>
12) <False, True, False, False>
13) <False, False, True, True>
14) <False, False, True, False>
15) <False, False, False, True>
16) <False, False, False, False>


Was This Post Helpful? 2
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1744
  • View blog
  • Posts: 5,896
  • Joined: 03-August 09

Re: How many different functions are there in bool->bool->bool?

Posted 08 January 2016 - 04:47 PM

Here is how I like to think about this. The number of functions of type Bool -> Bool -> Bool is the same as the number of binary boolean relations. Well each boolean relation is a subset of {0, 1} x {0, 1}. So there are 4 total values in the set so the size of the power set (and hence the number of binary boolean relations) is 24. Thus there are 2^4=16 functions of type Bool -> Bool -> Bool
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1