Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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?)

share|cite|improve this answer
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?

share|cite|improve this answer
  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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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