Predicate logic quesion


by GTL
Tags: logic, predicate, quesion
GTL
GTL is offline
#1
Oct21-10, 09:37 PM
P: 3
1. The problem statement, all variables and given/known data
Let p(n) and q(n) be predicates. For each pair of statements below, determine
whether the two statments are logically equivalent. Justify your answers.
a)
(i) ∀n (p(n) ∧ q(n))
(ii) (∀n p(n)) ∧ (∀n q(n))

b)
(i) ∃n st (p(n) ∧ q(n))
(ii) (∃n st p(n)) ∧ (∃n st q(n))

There are several questions in the same vein but these two are examples
2. Relevant equations



3. The attempt at a solution
I'm having a hard time wrapping my head around this problem. All the problems that I've worked on before are for individual values of n, I don't know how to go about proving or disproving for questions like this. I know I can prove they are equivalent by showing i) <-> ii) but I can't even tell whether the statements are equivalent or not let alone writing the proof.
1. The problem statement, all variables and given/known data



2. Relevant equations



3. The attempt at a solution
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Mark44
Mark44 is online now
#2
Oct22-10, 01:14 AM
Mentor
P: 21,067
Quote Quote by GTL View Post
1. The problem statement, all variables and given/known data
Let p(n) and q(n) be predicates. For each pair of statements below, determine
whether the two statments are logically equivalent. Justify your answers.
a)
(i) ∀n (p(n) ∧ q(n))
(ii) (∀n p(n)) ∧ (∀n q(n))

b)
(i) ∃n st (p(n) ∧ q(n))
(ii) (∃n st p(n)) ∧ (∃n st q(n))

There are several questions in the same vein but these two are examples
2. Relevant equations
What are the symbols that don't render correctly (the ones showing as boxes)?
Quote Quote by GTL View Post


3. The attempt at a solution
I'm having a hard time wrapping my head around this problem. All the problems that I've worked on before are for individual values of n, I don't know how to go about proving or disproving for questions like this. I know I can prove they are equivalent by showing i) <-> ii) but I can't even tell whether the statements are equivalent or not let alone writing the proof.
GTL
GTL is offline
#3
Oct22-10, 02:02 AM
P: 3
Quote Quote by Mark44 View Post
What are the symbols that don't render correctly (the ones showing as boxes)?
Symbols are not rendering properly? hmm they seem to be working on my system. All the symbols in part a are Universal Quantifiers (upside down 'A') and all the symbols in part b are Existential Operators (backwards E). I have attached the screencap of the question if that makes it any clearer
Attached Thumbnails
Untitled.jpg  

sylas
sylas is offline
#4
Oct22-10, 02:14 AM
Sci Advisor
sylas's Avatar
P: 1,750

Predicate logic quesion


What methods can you use for justifications? Can you use informal reasoning, or should you use some kind of axiomatic proof?

In any case, do you have any intuition as which pairs are/aren't equivalent?

If you think a pair is NOT equivalent, then you can give a counter example.

If you think a pair IS equivalent, then you should be able to prove an implication in both directions.

But tell me your intuition first.

Cheers -- sylas

PS. Most computers should display the characters okay. They are Unicode characters 0x2200 (∀) and 0x2203 (∃). You need a font that includes them, and the capacity to manage unicode.
GTL
GTL is offline
#5
Oct22-10, 03:23 AM
P: 3
Quote Quote by sylas View Post
What methods can you use for justifications? Can you use informal reasoning, or should you use some kind of axiomatic proof?

In any case, do you have any intuition as which pairs are/aren't equivalent?

If you think a pair is NOT equivalent, then you can give a counter example.

If you think a pair IS equivalent, then you should be able to prove an implication in both directions.

But tell me your intuition first.

Cheers -- sylas

PS. Most computers should display the characters okay. They are Unicode characters 0x2200 (∀) and 0x2203 (∃). You need a font that includes them, and the capacity to manage unicode.
I am reasonably confident that pair a) is equivalent. My reasoning is that if i) ∀n (p(n) ∧ q(n)) is true for certain values of n then it means that that same value of n makes p(n) true and q(n) true, which would make the ii) true as well. If i) is false then it means that either p(n) or q(n) computed false for a certain value of n, this would make ii) false as well. Again, I don't know if this reasoning is sound or not. This question had 2 more parts one involving

(universal quantifier used here for those who can't see the symbol)
d)
(i) ∀n (p(n) V q(n))
(ii) (∀n p(n)) V (∀n q(n))


These two statements, I think are also equivalent based on similar reasoning to that of a). The questions with the existential operators also *seem* to be equivalent to me, for example for b) the existential operator question if there is a number n such that i) is true then that would make ii) true as well and vice-verse as both p(n) and q(n) need to be true for the whole thing to be true (similar logic can to be used if one of the statements computes false implieing either p(n) or q(n) is false and hence making both statements false) therefore logically equivalent. But I don't think I'm right as I find it hard to believe that they'll give four examples of a certain kind of question in the problem set and have the answer to each one of them be: "they are logically equivalent" without a single disproof. (part c is the exact same question as part b except with '^' replaced with 'V').

Just in the process of writing this post some ideas are starting to become clearer in my head and I can even see an outline of a proof in there but I'm just not confident in my reasoning to be sure that my thought process is sound, esp since I think that each pair is logically equivalent which I find hard to believe in the context of the assignment; it leads me to conclude that there is some grave error in my reasoning which could mean that everything I did with this question could be potentially wrong and I'm totally off.

(as for methods of justification, I don't even know any details about axioms beyond what they mean in the broadest sense lol. This is for an introductory Discrete Math course so I don't think the proof needs to be too hardcore as long as it makes sense)
sylas
sylas is offline
#6
Oct22-10, 04:10 AM
Sci Advisor
sylas's Avatar
P: 1,750
Quote Quote by GTL View Post
I am reasonably confident that pair a) is equivalent. My reasoning is that if i) ∀n (p(n) ∧ q(n)) is true for certain values of n then it means that that same value of n makes p(n) true and q(n) true, which would make the ii) true as well. If i) is false then it means that either p(n) or q(n) computed false for a certain value of n, this would make ii) false as well.

That would seem to be a good enough justification to me. The reasoning IS sound, even if not formalized.

However, your intuitions are leading astray in the other questions. For example, in this one, try to spell it out again, from scratch, and in BOTH directions.

(i) ∀n (p(n) V q(n))
(ii) (∀n p(n)) V (∀n q(n))


These two statements, I think are also equivalent based on similar reasoning to that of a).
Similar reasoning won't cut it. You need to give your reasons, standing by themselves and independently of what you said in (a). They are different formulae; the reasoning does not transpose that easily.

The questions with the existential operators also *seem* to be equivalent to me, for example for b) the existential operator question if there is a number n such that i) is true then that would make ii) true as well and vice-verse as both p(n) and q(n) need to be true for the whole thing to be true (similar logic can to be used if one of the statements computes false implieing either p(n) or q(n) is false and hence making both statements false) therefore logically equivalent. But I don't think I'm right as I find it hard to believe that they'll give four examples of a certain kind of question in the problem set and have the answer to each one of them be: "they are logically equivalent" without a single disproof. (part c is the exact same question as part b except with '^' replaced with 'V').
Careful there. I'll won't tell you what's wrong here, but think it through carefully, first for going from (b i) to (b ii), and then think it through all over again for going from (b ii) to (b i).

(as for methods of justification, I don't even know any details about axioms beyond what they mean in the broadest sense lol. This is for an introductory Discrete Math course so I don't think the proof needs to be too hardcore as long as it makes sense)
That seems fine. It's a really good idea to have the intuitions clear in your head, and then later on that can let you find axioms if you need to be more formal. For now... informal justification is fine.

Try again... :-) sylas


Register to reply

Related Discussions
predicate logic proof Engineering, Comp Sci, & Technology Homework 1
Propositional and Predicate Logic General Math 0
Predicate Logic Help! Set Theory, Logic, Probability, Statistics 0
Predicate Logic help please Introductory Physics Homework 7
homework help: predicate logic Introductory Physics Homework 10