Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Maximum size of a set containing logical expressions

  1. Jan 30, 2014 #1

    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?

  2. jcsd
  3. Jan 31, 2014 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    Perhaps you mean "truth tables".

    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 ->.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook