Register to reply 
Predicate logic quesion 
Share this thread: 
#1
Oct2110, 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 


#2
Oct2210, 01:14 AM

Mentor
P: 21,297




#3
Oct2210, 02:02 AM

P: 3




#4
Oct2210, 02:14 AM

Sci Advisor
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. 


#5
Oct2210, 03:23 AM

P: 3

(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 viceverse 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) 


#6
Oct2210, 04:10 AM

Sci Advisor
P: 1,750

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