2

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!

hot_queen
  • 7,277
  • 20
  • 32
user125102
  • 35

1 Answers1

1

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$.

mjqxxxx
  • 41,358