## Predicate Logic Proof Help

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
Rket12
Posts: 3
Joined: Thu Oct 24, 2013 6:59 am
Contact:

### Predicate Logic Proof Help

Hey, I need some help on my final questions for my predicate logic problem set. It'd be great if someone could help explain this to me!

---------------------------------------------------------------------
What is wrong with the following proof to the theorem?
The product of an even integer and an odd integer is even.
Proof: Suppose m is an even integer and n is an odd integer. If mn is even, then by definition of even there exists an integer r such that mn = 2r. Also, since m is even, there exists an integer p such that m = 2p, and since n is odd there exists an integer q such that n = 2q + 1. Thus mn = (2p)(2q + 1) = 2r where r is an integer. By definition of even, then mn is even as required.

---------------------------------------------------------------------
Assume the existence of predicates Prime(x), whose value is true if x is a prime, and x j y whose value is true if y is a multiple of x (y = xa for some integer a).
Rewrite the following in predicate logic and prove if true or false

1. If n is a positive integer that is not a multiple of 2 or a multiple of 3, then 4n + 3 is a prime number.

2. For some positive integer c, no matter how we choose a pair of positive integers x and y, we have x + y c * max{x, y}

nona.m.nona
Posts: 288
Joined: Sun Dec 14, 2008 11:07 pm
Contact:

### Re: Predicate Logic Proof Help

What is wrong with the following proof to the theorem?
The product of an even integer and an odd integer is even.
Proof: Suppose m is an even integer and n is an odd integer. If mn is even, then by definition of even there exists an integer r such that mn = 2r. Also, since m is even, there exists an integer p such that m = 2p, and since n is odd there exists an integer q such that n = 2q + 1. Thus mn = (2p)(2q + 1) = 2r where r is an integer. By definition of even, then mn is even as required.
Check the "if" and "then" in what is to be proved, and compare with the "if" and "then" of the proposed proof.
Assume the existence of predicates Prime(x), whose value is true if x is a prime, and x j y whose value is true if y is a multiple of x (y = xa for some integer a).
Is "j" the predicate? So the relation is j(x,y), which evaluates as "true" for y = nx?
Rewrite the following in predicate logic and prove if true or false

1. If n is a positive integer that is not a multiple of 2 or a multiple of 3, then 4n + 3 is a prime number.
Since (large) primes are rather difficult to locate, and since the above is a quite simple formula, it seems unlikely that the formula is correct. I would suggest proceeding by counter-example.
2. For some positive integer c, no matter how we choose a pair of positive integers x and y, we have x + y c * max{x, y}
I'm afraid I do not "follow" the above. It seems nonsensical. Has it been typed out accurately?

Rket12
Posts: 3
Joined: Thu Oct 24, 2013 6:59 am
Contact:

### Re: Predicate Logic Proof Help

Yes I made a mistake in the last one it should look like:

For some positive integer c, no matter how we choose a pair of positive integers x and y, we have x + y <= c * max{x, y}

I think I understand the other ones thank you for your help! This last one looks weird too me, I don't understand what max{x,y} means

nona.m.nona
Posts: 288
Joined: Sun Dec 14, 2008 11:07 pm
Contact:

### Re: Predicate Logic Proof Help

...the last one...should look like:

For some positive integer c, no matter how we choose a pair of positive integers x and y, we have x + y <= c * max{x, y}

I don't understand what max{x,y} means
The operator "max{a,b}" means "the larger of the two values a and b". The statement is proposing that there is some whole number c such that the product of c and the larger of x and y is larger than the sum of x and y.

To prove the statement, one might consider breaking this into cases; Case 1 is where x = y (so x + y = 2y), and Case 2 is where x < y (so x + y < 2y). The case where x > y is the same as Case 2, with x and y merely being reversed.

Rket12
Posts: 3
Joined: Thu Oct 24, 2013 6:59 am
Contact:

### Re: Predicate Logic Proof Help

Could you please elaborate a little further? I still don't quite understand how to prove it through cases such as those

nona.m.nona
Posts: 288
Joined: Sun Dec 14, 2008 11:07 pm
Contact:

### Re: Predicate Logic Proof Help

I can think of no way to "expand upon" the information already provided, as the answer has, essentially, already been provided to you. Kindly please reply with your thoughts and efforts thus far, as they followed from what you have been given. Thank you.