Predicate Logic Proof Help  TOPIC_SOLVED

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

Predicate Logic Proof Help

Postby Rket12 on Thu Oct 24, 2013 7:01 am

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}
Rket12
 
Posts: 3
Joined: Thu Oct 24, 2013 6:59 am

Sponsor

Sponsor
 

Re: Predicate Logic Proof Help  TOPIC_SOLVED

Postby nona.m.nona on Thu Oct 24, 2013 10:43 am

Rket12 wrote: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.

Rket12 wrote: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?

Rket12 wrote: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.

Rket12 wrote: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?
nona.m.nona
 
Posts: 252
Joined: Sun Dec 14, 2008 11:07 pm

Re: Predicate Logic Proof Help

Postby Rket12 on Thu Oct 24, 2013 3:39 pm

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
Rket12
 
Posts: 3
Joined: Thu Oct 24, 2013 6:59 am

Re: Predicate Logic Proof Help

Postby nona.m.nona on Thu Oct 24, 2013 5:51 pm

Rket12 wrote:...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.
nona.m.nona
 
Posts: 252
Joined: Sun Dec 14, 2008 11:07 pm

Re: Predicate Logic Proof Help

Postby Rket12 on Thu Oct 24, 2013 7:17 pm

Could you please elaborate a little further? I still don't quite understand how to prove it through cases such as those
Rket12
 
Posts: 3
Joined: Thu Oct 24, 2013 6:59 am

Re: Predicate Logic Proof Help

Postby nona.m.nona on Thu Oct 24, 2013 9:44 pm

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.
nona.m.nona
 
Posts: 252
Joined: Sun Dec 14, 2008 11:07 pm


Return to Discrete Math