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

Homework Help: Question about logic and recurrence relation

  1. Sep 28, 2010 #1
    1. The problem statement, all variables and given/known data
    find a logical expression using only ∧ and ¬ operators which is logically equivalent to (p ∨ q)

    3. The attempt at a solution
    losing direction
    what should I first consider?

    There is another question about recurrent relation.

    Suppose that a mathematical expression can only be formed by the following symbols: 0, 1,
    2, …, 9, ×, +, /. Some examples are “0 + 9”; “2 + 2 × 8”; “1 / 5 + 6”. Let an be the the number
    of such mathematical expression of length n (e.g. “0 + 9” is considered of length 3). Find a
    recurrence relation for an and compute the closed form for an.
    [Some clarification: We define a number as follows
    - 0, 1, 2, …, 9 is a number
    - If x is a number, then x0, x1, …, x9 is a number
    We define a valid expression as follows
    - E is a valid expression if E is a number
    - If E, F are valid expressions, then E + F, E × F, E / F are also valid expressions.
    For example: 1+50/4 is an expression of length 6, and 09×00/5 is an expression of length 7.]

    Totally no idea about this question.
     
  2. jcsd
  3. Sep 28, 2010 #2

    fss

    User Avatar

    You should consider what it means to be logically equivalent, then look up "tautologies."
     
  4. Sep 28, 2010 #3
    What do you mean is finding something [tex]\rightarrow[/tex] ( p[tex]\vee[/tex]q ) and make it a tautology?
     
  5. Sep 28, 2010 #4

    fss

    User Avatar

    I do not understand what the above question is asking.

    Do you understand what it means when two statements are logically equivalent?
     
  6. Sep 28, 2010 #5
    It means p[tex]\leftrightarrow[/tex]q is a tautology.

    Maybe I make some mistakes with my question. And after I know that, what should I do next?
    Just guessing or there is a systematic way to work out the solution.
     
  7. Sep 28, 2010 #6

    fss

    User Avatar

    It's not guessing, but it's not really "systematic" because it's a very simple question. All you need to do is use what you know about tautologies to construct an equivalent statement. The original statement p v q has a very simple logical equivalent that you should be able to deduce with only a little thinking once you find the proper tautological statement.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook