Maximum size of a set containing logical expressions Can you please help me with this problem?
"What is the maximum size of a set A of logical expressions that only use →, p, q : each pair of elements of A are not equivalent?"
I've found 6 different possible truth values. Is this the maximum size? If yes, how do I prove it?
Thanks!
 A: Represent a truth table for $(p, q)$ by a four-character string $abcd$, where each character is $T$ or $F$; the characters represent the truth value when $(p,q)$ is $(T,T)$, $(T,F)$, $(F,T)$, and $(F, F)$.  You are starting with $\tau(p )=TTFF$ and $\tau(q)=TFTF$.  Then combine all pairs with $\rightarrow$ until you stop getting new truth tables:
$$
\begin{eqnarray}
\tau(p\rightarrow p)&=&(TTFF\rightarrow TTFF)=TTTT=\tau(q\rightarrow q) \\
\tau(p\rightarrow q)&=&(TTFF\rightarrow TFTF)=TFTT \\
\tau(q\rightarrow p)&=&(TFTF\rightarrow TTFF)=TTFT
\end{eqnarray}
$$
Note that $(TTTT\rightarrow abcd)=abcd$ and $(abcd\rightarrow TTTT)=TTTT$, so the first entry can't give us anything new; also $(abcd \rightarrow abcd)=TTTT$, so we don't need to look at formulas of that form.  There are ten new combinations to try, but only five up to exchanging $p$ and $q$:
$$
\begin{eqnarray}
\tau(p\rightarrow (p\rightarrow q))&=&(TTFF\rightarrow TFTT)=TFTT \\
\tau(p\rightarrow (q\rightarrow p))&=&(TTFF\rightarrow TTFT)=TTTT \\
\tau((p\rightarrow q)\rightarrow p)&=&(TFTT\rightarrow TTFF)=TTFF \\
\tau((q\rightarrow p)\rightarrow p)&=&(TTFT\rightarrow TTFF)=TTTF \;\;(*) \\
\tau((p\rightarrow q)\rightarrow(q \rightarrow p))&=&(TFTT\rightarrow TTFT)=TTFT.
\end{eqnarray}
$$
The new entry $(*)$ is
$$
\tau((q\rightarrow p)\rightarrow p)=\tau(q \vee p)=TTTF.
$$
There are four new combinations to try now:
$$
\begin{eqnarray}
\tau(p\rightarrow (p\vee q))&=&(TTFF\rightarrow TTTF)=TTTT \\
\tau((p \vee q)\rightarrow q)&=&(TTTF\rightarrow TTFF)=TTFT \\
\tau((p\rightarrow q)\rightarrow(p\vee q))&=&(TFTT\rightarrow TTTF)=TTTF \\
\tau((p\vee q)\rightarrow(p\rightarrow q))&=&(TTTF\rightarrow TFTT)=TFTT.
\end{eqnarray}
$$
None of these give anything new, so you're done.  The generated set is
$$
A=\{p, q, p\rightarrow q, q\rightarrow p, {\mathsf{true}}, p\vee q\},
$$
which does have size $6$.
