Maximum size of a set containing logical expressions

[alejandro7]

Hi

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!

 

[Stephen Tashi]

I've found 6 different possible truth values.

Perhaps you mean "truth tables".

Is this the maximum size? If yes, how do I prove it?

I haven't worked the problem. I don't see an elegant way to prove it.

If you have a set of truth tables for propositional functions A_1, A_2,..A_N that are each functions of (p,q) then you can attempt to produce functions with a new truth tables by looking at all possible pairs of statements of the form "A_i -> A_j".

Beginning with A_1 = p, A_2= q, N=2, you would examine p ->p , p ->q, q->q, q->p.

Adding any functions that have new truth tables, you form a larger set. Then try to produce new truth tables from the larger set in a similar manner. If you generate a set where no new tables can be produced by the above method, I'd say you have the largest possible set of functions involving only p,q, and ->.