1
$\begingroup$

I am reading a book called "The Haskell Road to Logic, Maths and Programming"

A question in the book is: "How many truth tables are there for 2-letter formula's"

The answer in the answer sheet is: "A two-letter formula has a truth table with four rows. The value at every row can be either t of f, so there are 2^4 = 16 truth tables altogether."

Now I don't understand, how a 2 letter formula, can have 16 truth tables? Let's say P ⇒ Q It will look like:

P    Q    (P⇒Q)
T    T    T
T    F    F
F    T    T
F    F    T

Now how can this have 16 tables? It looks like one table to me.

$\endgroup$
1
  • $\begingroup$ Their explanation rightfully (but unjustifiably) assumes that every truth table with four rows is attainable from a two letter formula. $\endgroup$
    – Git Gud
    May 5, 2016 at 19:16

2 Answers 2

Reset to default
4
$\begingroup$

For different formulae, the third column above can have different 4-tuples of T or F. So there are $2^4$ different formulae. For example, $P\wedge Q$,

$$\begin{array}{cc|c} P&Q&P\wedge Q\\\hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&F \end{array}$$

is another truth table with a different 4-tuple $(T,F,F,F)$.

In fact, for any integer $0\le n\le 2^4-1$, let $b_i\in\{0,1\}$ be the $i$th bit of $n$ ($i = 0,1,2,3$), then $f_n$ is a new function defined by

$$\begin{array}{cc|c} P&Q&f_n(P,Q)\\\hline 0&0&b_0\\ 0&1&b_1\\ 1&0&b_2\\ 1&1&b_3 \end{array}$$

$\endgroup$
1
  • $\begingroup$ Thank you for answering, I get it now :) $\endgroup$
    – Mazzy
    May 5, 2016 at 19:12
3
$\begingroup$

What they are asking is how many possible relationships like this are there. You have 4 rows, first 2 columns are fixed, last column has 4 entries with T/F each, so $2^4=16$ total choices.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.