Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - Propotional Logic Problem

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    15

    Propositional Logic Problem

    Hi...
    I have an excercise that is keeping me up all day and night..
    The problem is:
    "There is an infinite set of formulae T=<a_0,a_1,a_2,....> and those formulae involve atoms from a finite set M=<p_1,p_2,p_3,.....,p_n>.
    Show that if a_i \models a_i _+_1 , i=0,1,2,.., then there is a natural number m\leq2^n which a_m \equiv a_m_+_1

    Thank you in advance..
    Last edited by nick1978; December 14th 2010 at 07:29 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    780
    Here are some hints. Consider only the formulas a_0,\dots, a_{2^n+1}.

    There are 2^n valuations on n variables. For each valuation, how does the sequence a_0,\dots, a_{2^n+1} of truth values look like? Can we have a_i=a_{i+2}\ne a_{i+1}?

    Use pigeonhole principle where pigeons are pairs of formulas (a_0,a_1), (a_1,a_2),\dots,(a_{2^n},a_{2^n+1}) that can have different truth values for some valuation and holes are valuations.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2010
    Posts
    15
    by a_i=a_{i+2}\ne a_{i+1} you mean  a_i \models a_{i+2} \nvDash a_{i+1}????
    Last edited by nick1978; December 15th 2010 at 03:53 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2010
    Posts
    15
    Thank you very much...
    I ll try to follow your hints and tips..
    I Hope to solve this since i m new to maths....
    and finally sleep before 6AM(everyday)...
    many many thnx
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2010
    Posts
    15

    Question

    how about some sets theory?
    proving that, If S(a_i) the set of interpretations that satisfy a_i, S(a_{i+1}) the set of interpretations that satisfy a_{i+1}, then a_i \models a_{i+1} Iff S(a_i) \subseteq S(a_{i+1})

    also from the above
    a_i \equiv a_{i+1} Iff S(a_i) = S(a_{i+1})

    Then i say the max compinations of interpetation for n atoms is 2^n
    this as far as i got, and i don't know if i m right..



    then since a_i \models a_{i+1} then S(a_0) \subseteq S(a_1) \subseteq S(a_2)\subseteq........\subseteq S_{max}(a)=2^n)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2010
    Posts
    15
    Quote Originally Posted by emakarov View Post
    Here are some hints. Consider only the formulas a_0,\dots, a_{2^n+1}.

    There are 2^n valuations on n variables. For each valuation, how does the sequence a_0,\dots, a_{2^n+1} of truth values look like? Can we have a_i=a_{i+2}\ne a_{i+1}?



    Use pigeonhole principle where pigeons are pairs of formulas (a_0,a_1), (a_1,a_2),\dots,(a_{2^n},a_{2^n+1}) that can have different truth values for some valuation and holes are valuations.
    By a_i=a_{i+2}\ne a_{i+1} you mean a_i \models a_{i+2} \nvDash a_{i+1}????
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    780
    Quote Originally Posted by nick1978 View Post
    If S(a_i) the set of interpretations that satisfy a_i, S(a_{i+1}) the set of interpretations that satisfy a_{i+1}, then a_i \models a_{i+1} Iff S(a_i) \subseteq S(a_{i+1})

    also from the above
    a_i \equiv a_{i+1} Iff S(a_i) = S(a_{i+1})

    then since a_i \models a_{i+1} then S(a_0) \subseteq S(a_1) \subseteq S(a_2)\subseteq........\subseteq S_{max}(a)=2^n
    I agree, and I like this idea. We have a sequence of 2^n+1 set inclusions S(a_0) \subseteq S(a_1) \subseteq S(a_2)\subseteq\dots\subseteq S(a_{2^n+1}), and the number of elements in the last set is at most 2^n. This means that at least one of the inclusions must be non-strict.

    by a_i \models a_{i+2} \nvDash a_{i+1} you mean a_i \models a_{i+2} \nvDash a_{i+1}????
    No, I was referring to the truth values of a_i, a_{i+1} and a_{i+2} under some fixed interpretation. Fix an interpretation I, and let I(a_k) denote the truth value, say 0 or 1, of a_k at I. Then the sequence I(a_0),\dots,I(a_{2^n+1}) is monotonic. There is at most one k such that 0=I(a_k)\ne I(a_{k+1})=1. Thus, each interpretation distinguishes at most two consecutive formulas. Since there are 2^n+1 pairs of formulas in the sequence and only 2^n interpretations, two formulas must be equal under all interpretations.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Dec 2010
    Posts
    15
    you are a saint for even looking into my problem. can't find words to express my graditute...
    Another way i tried is by using Complete induction
    For only one atom n=1 , n=k etc..but no luck there....
    At least with your guidance i will try and finaly have some sleep...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Dec 2010
    Posts
    15
    Quote Originally Posted by emakarov View Post
    I agree, and I like this idea. We have a sequence of 2^n+1 set inclusions S(a_0) \subseteq S(a_1) \subseteq S(a_2)\subseteq\dots\subseteq S(a_{2^n+1}), and the number of elements in the last set is at most 2^n. This means that at least one of the inclusions must be non-strict.

    Thnx I m full of ideas .. i have some ideas even in my dream when i sleep if i sleep ..but i can't reach to a conclusion
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    780
    If S(a_0) \subset S(a_1) \subset S(a_2)\subset\dots\subset S(a_{2^n+1}) and each inclusion is strict, then |S(a_0)| < |S(a_1)| < |S(a_2)|<\dots< |S(a_{2^n+1})|. (Here |A| denotes the number of elements in a set A.) There are 2^n+1 "less than" signs, and for each of them its right-hand side must be at least one greater than the left-hand side. Therefore, 2^n + 1\le |S(a_0)| + 2^n + 1\le |S(a_{2^n+1})|. However, this is impossible because |S(a_{2^n+1})|\le 2^n.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Dec 2010
    Posts
    15
    That seems a good start for the allnight session of PL.I ll try to involve the m counter...in this....thnx again....for all your trouble...
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Dec 2010
    Posts
    15
    Thnx to your help i think i am one step before solving the problem..
    |S(a_i)|<|S(a_{i+1})|\leq2^n

    |S(a_0)| < |S(a_1)| < |S(a_2)|<\dots< |S(a_{2^n+1})|\leq2^n
    So we want to prove that there is a natural number m\leq2^n
    which gives a_m \equiv a_m_+_1
    How can we prove that...
    i feeel so close to the solution but lack the basis..
    Thnx again
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    The sequence of numbers you have should be nonnegative and must be integers. They must be monotonically nondecreasing.
    Is it possible to have the strictly increasing chain values that does not exceed 2^n?

    If not, then there must be a point where (it cannot increase, but it cannot decrease either, which means) ...
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Dec 2010
    Posts
    15
    i can't express it with mathimatical terms..i know that the sequence has an upper limit 2^n...but i can't present the right formula to say m\leq2^n IFF a_m \equiv a_{m+1}
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    You already have everything.

    The basic idea is you are using proof by contradiction.
    You know for a fact that
    |S(a_0)| \leq |S(a_1)| \leq |S(a_2)|\leq\dots\leq |S(a_{2^n+1})|\leq2^n

    Now, assume that for no m does a_m\equiv a_{m+1}.
    This means the inequalities must be strict:
    |S(a_0)| < |S(a_1)| < |S(a_2)| < \dots < |S(a_{2^n+1})| \leq 2^n

    But this lead to a contradiction because this forces |S(a_0)| < 0 .

    This means the initial assumption was incorrect, and there must exist an m s.t. a_m\equiv a_{m+1}.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: October 4th 2011, 06:34 AM
  2. Help with logic problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 10th 2010, 04:37 PM
  3. Logic problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 17th 2009, 07:19 PM
  4. Logic problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 24th 2007, 06:58 AM
  5. another logic problem....PLEASE HELP
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2007, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum