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

Page 1 of 1

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

### #1 rshah

Reputation: 2
• 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

Reputation: 7
• 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>

```

### #3 ishkabible

• spelling expret

Reputation: 1747
• Posts: 5,898
• 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