Predicate Logic: Are These Statements Logically Equivalent?

[GTL]

Homework Statement

Let p(n) and q(n) be predicates. For each pair of statements below, determine
whether the two statements 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

Homework Equations

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.

 

[Mark44]

Homework Statement

Let p(n) and q(n) be predicates. For each pair of statements below, determine
whether the two statements 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

Homework Equations

What are the symbols that don't render correctly (the ones showing as boxes)?

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]

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

 

[sylas]

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]

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]

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