# Pigeon holes principle

Let $P$ be a group that it's elements are 257 sentences in which only atomic sentences from $A,B,C$ exist (i.e. $A \iff B,\space\space A \wedge B \wedge C, \space\space...$) Show that there exists two different $p_1, p_2 \in P$ so that the sentence $p_1 \iff p_2$ is a tautology.

Pigeons are the $257$ sentences but I can't think of a way to prove the asked.

-

HINT: Notice that $257=2^8+1$, so you might guess that there will be $2^8$ pigeonholes. You have three atomic sentences. They can have $2^3=8$ different combinations of truth values. How many different truth tables can you build from these $8$ combinations of truth values? Now notice that if $p_1\iff p_2$ is a tautology, then $p_1$ and $p_2$ have the same truth table. (Why?)

-
I don't really know how to answer the question How many different truth tables can you build from these $8$ combinations of truth values? We have $257$ so could it possibly be $257 \times 84$? It doesn't feel like it. – Georgey May 20 '13 at 18:11
@Georgey: Each truth table with three atomic sentences will have $8$ lines. (Why?) Say that it’s the truth table for some proposition $p$; on each of those $8$ lines $p$ will have a truth value, either T or F. How many different ways are there to assign those $8$ truth values? – Brian M. Scott May 20 '13 at 18:14
Each truth table with $n$ atomic sentences will have $2^n$ lines, because for each variable ($n$ variables) it can get truth or false values ($2$ values). So the answer for your second question if $2^8$? Because each truth value can get true or false value? – Georgey May 20 '13 at 18:17
@Georgey: That’s right. There are $2^8$ possible truth tables for a proposition $p$ containing at most the three atomic sentences $A,B$, and $C$. And $P$ contains $257$ propositions, so ... ? – Brian M. Scott May 20 '13 at 18:18
so according to Pigeonhole principle there are at least $\left \lceil \frac{257}{2^8} \right \rceil = \left \lceil \frac{257}{256} \right \rceil = 2$ sentences that have an identical truth table which means they're tautology. What I don't understand is why shouldn't I divide it to different cases. 1. where there are only $A$ and $B$ and 2. where there are $A$, $B$ and $C$? – Georgey May 20 '13 at 18:33

Consider the truth tables. How many different possible truth tables are there for sentences with three variables? What can you say about sentences that have the same truth table?

-
1. How many different truth-functions are expressible using just three propositional variables? (Hint: how many lines are there in a truth-table in three variables? how many truth-possibilities are there for each line? So how many different truth-functions in three variables in total?)

2. If there are $x$ different truth-functions in three variables and $y$ different wffs built up from three variables, and $x < y$, how might the pigeon hole principle be applied?

-