1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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