# Math Help - predicate logic

1. ## 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?

2. Hi

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

$
\forall x(\exists n( x=2n+1)\Rightarrow \forall y(y|x\Rightarrow\exists m(y=2m+1)))$

3. Hi Plato,
shouldn't you write $(O(x)\wedge(y|x))$ (I mean with parenthesis) in your formula ?

4. Originally Posted by thehollow89
[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]$.

5. Originally Posted by clic-clac
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.

6. Originally Posted by thehollow89
“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)

7. @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.

8. ## Logic: order of precedence

Hello Plato
Originally Posted by Plato
...
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.

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.

10. ## Logic: order of precedence

Hello Plato
Originally Posted by Plato
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'?

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.