Results 1 to 11 of 11

Math Help - predicate logic

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    44

    predicate logic

    I have to express this using quantifiers, divisibility, = <= <, etc. “If a natural number is odd, then all its divisors are odd.”

    I was thinking of, for all 2x+1, where x is a natural number, if 2x+1 is divisible by some value y, then y=2n+1 where n is a natural number. Not sure how to put it into a predicate logic and what not. Any help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    Yeah your idea seems good, using existence quantifiers it becomes:
    In \mathbb{N},

    <br />
\forall x(\exists n( x=2n+1)\Rightarrow \forall y(y|x\Rightarrow\exists m(y=2m+1)))
    Last edited by clic-clac; March 4th 2009 at 01:57 PM. Reason: cor
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi Plato,
    shouldn't you write (O(x)\wedge(y|x)) (I mean with parenthesis) in your formula ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by thehollow89 View Post
    [I]I have to express this using quantifiers, divisibility, = <= <, etc.
    If a natural number is odd, then all its divisors are odd.”
    "O(x) means that x is a odd natural number" & "y|x means y divides x"
    Assume the domain of natural numbers.
    \left( {\forall x} \right)\left( {\forall y} \right)\left[ {O(x) \wedge \left( {y|x} \right) \Rightarrow O(y)} \right].
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by clic-clac View Post
    shouldn't you write (O(x)\wedge(y|x)) (I mean with parenthesis) in your formula ?
    You certainly could do that. It may even be better for a beginner. But it is not necessary.
    In formal logic the order of precedence is:  \equiv \; \Rightarrow \; \vee \; \wedge \;\neg.
    That is P \Rightarrow Q \vee R \wedge S means P \Rightarrow \left[ {Q \vee \left( {R \wedge S} \right)} \right]

    But as I said, it is probably best to use grouping symbols in this forum.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by thehollow89 View Post
    “If a natural number is odd, then all its divisors are odd.”
    Predicates
    N(x) : x is a natural number.
    O(x) : x is an odd number.
    D(y,x) : y divides x
    Div(y,x) : y is a divisor of x

    \forall x[(N(x) \wedge O(x)) \rightarrow \forall y((N(y) \wedge \text{Div(y,x)}) \rightarrow (O(y) \wedge D(y,x)))] .

    (I used an outer bracket [] rather than () for readibility).

    Now, check several cases whether the above one is valid or not.

    case 1. x is a not a natural number (vacuously true)
    case 2. x is a natural number and x is not odd (vacuously true).
    case 3. x is a natural number and y is not a divisor of x or y is not a natural number (vacuously true).
    case 3. x is an odd natural number, y is a divisor of x and is not an odd natural number. (False)
    case 4. x is an odd natural number, y is a divisor of x and y does not divide x. (False)
    case 5. x is an odd natural number, y is a divisor of x and y is an odd natural number which divides x. (True)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    @Plato: Ok I didn't know such a thing (the order of precedence). I guess that may depend on how the theory was done! Thanks.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Logic: order of precedence

    Hello Plato
    Quote Originally Posted by Plato View Post
    ...
    In formal logic the order of precedence is:  \equiv \; \Rightarrow \; \vee \; \wedge \;\neg.
    ...
    Would you like to confirm that this order of precedence is from lowest precedence to highest? I think many people (myself included) would have written this in reverse order - from highest to lowest.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Grandad View Post
    Hello PlatoWould you like to confirm that this order of precedence is from lowest precedence to highest? I think many people (myself included) would have written this in reverse order - from highest to lowest.
    Reading from left to right the order of precedence is from highest to lowest.
    I am in the habit of following Copi’s conventions. Here is a example from his last book:
    P \Rightarrow Q \vee \neg R \wedge S\text{ is rendered }P \Rightarrow \left(Q \vee \left[ {\left( {\neg R}  \right)\wedge S} \right]\right).
    But as I said, in a forum such as this it is best to use groupings for clarity.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Logic: order of precedence

    Hello Plato
    Quote Originally Posted by Plato View Post
    Reading from left to right the order of precedence is from highest to lowest.
    I am in the habit of following Copi’s conventions. Here is a example from his last book:
    P \Rightarrow Q \vee \neg R \wedge S\text{ is rendered }P \Rightarrow \left(Q \vee \left[ {\left( {\neg R}  \right)\wedge S} \right]\right).
    But as I said, in a forum such as this it is best to use groupings for clarity.
    Sorry, but you leave me still confused. In your posting where you referred to an order of precedence, you said it was

    \equiv \; \Rightarrow \; \vee \; \wedge \; \neg

    and in this post, you say that this reads from left to right, highest to lowest.

    And yet your example would appear to demonstrate the opposite: namely that the highest precedence (i.e the operation that is carried out first) is given to \neg, then \wedge, and so on. Thus your interpretation of P \Rightarrow Q \vee \neg R \wedge S is exactly the same as mine.

    So are we talking at cross-purposes here, and we mean different things by 'highest to lowest'?

    Grandad


    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Grandad View Post
    And yet your example would appear to demonstrate the opposite: namely that the highest precedence (i.e the operation that is carried out first) is given to \neg, then \wedge, and so on. Thus your interpretation of P \Rightarrow Q \vee \neg R \wedge S is exactly the same as mine. So are we talking at cross-purposes here, and we mean different things by 'highest to lowest'?
    I think that is quite possibly the case. Perhaps I should have said that the order is in terms of the scope of the operator. Therefore, \neg has the least scope and  \equiv has the greatest scope. I can direct you to Symbolic Logic by I.M.Copi. He has an extensive discussion of this topic. The example I gave is copied directly out of that textbook.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2010, 07:53 AM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 29th 2010, 03:51 PM
  3. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 21st 2010, 08:39 PM
  4. Predicate Logic #2
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 21st 2010, 08:34 PM
  5. More predicate logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum