Show that two quantified statements are logically equivalent

  • #1
1,456
44

Homework Statement


Show that ##\forall x(P(x) \land Q(x)) \equiv \forall xP(x) \land \forall xQ(x)##

Homework Equations




The Attempt at a Solution


Based on my work from propositional logic, to show that two expressions are logically equivalent, then we have to show that ##\forall x(P(x) \land Q(x)) \Longleftrightarrow \forall xP(x) \land \forall xQ(x)## is a tautology; that is, it is always true. It is always true if they have the same truth values for all x in the domain. For propositional logic, it was a matter of listing out the finite combinations of truth values and showing that they are always the same. However, with predicate logic, we are dealing with an infinite domain of discourse, so we can't just list them off. How should I proceed then?
 
Last edited:

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,221
1,327
Show that ##\forall (P(x) \land Q(x)) \equiv \forall P(x) \land \forall Q(x)##
What variable does ##\forall## quantify? Did you mean ##( \forall x, P(x) \land Q(x)\ ) \equiv (\forall x, P(x))\land(\forall x, Q(x)) ##.

What assumptions and theorems have you studied in proposition logic ? "Universal generalization", "Existential instantiation" etc. ?
 
  • #3
1,456
44
What variable does ##\forall## quantify? Did you mean ##( \forall x, P(x) \land Q(x)\ ) \equiv (\forall x, P(x))\land(\forall x, Q(x)) ##.

What assumptions and theorems have you studied in proposition logic ? "Universal generalization", "Existential instantiation" etc. ?
I fixed the errors in the original post.

I was thinking that maybe I could use universal generalization to show that, if the LHS is true, then ##P(a) \land Q(a)## is true for all a in the domain. Then by universal generalization, we would have the RHS. However, I don't see how this establishes that the biconditional is a tautology, which is necessary to show that they are logically equivalent.
 
  • #4
Stephen Tashi
Science Advisor
7,221
1,327
However, I don't see how this establishes that the biconditional is a tautology, which is necessary to show that they are logically equivalent.
A biconditional is just two conditionals. Show each separately.
 
  • #5
1,456
44
A biconditional is just two conditionals. Show each separately.
If I show that LHS implies the RHS, and that the RHS implies the LHS, then I would show that one being true implies that the other is true. But in order for it to be a tautology, don't you have to also show that if one is false than the other must be false as well?
 
  • #6
Stephen Tashi
Science Advisor
7,221
1,327
If I show that LHS implies the RHS, and that the RHS implies the LHS, then I would show that one being true implies that the other is true. But in order for it to be a tautology, don't you have to also show that if one is false than the other must be false as well?
That will depend on how your text materials define the relation "##\equiv##".

Is there a theorem or definition in your materials that says: ## ( ( A \implies B) \land (B \implies A) ) \implies A \equiv B## ?
 
  • Like
Likes Mr Davis 97
  • #7
13,225
10,154
But in order for it to be a tautology, don't you have to also show that if one is false than the other must be false as well?
It is always a good idea to start this way: What does it mean, if one side were wrong? Can the other still be true?
And then the other way around.
 
  • Like
Likes Mr Davis 97

Related Threads on Show that two quantified statements are logically equivalent

Replies
2
Views
929
  • Last Post
Replies
3
Views
1K
Replies
2
Views
4K
  • Last Post
Replies
5
Views
1K
Replies
4
Views
4K
  • Last Post
Replies
4
Views
4K
Replies
4
Views
855
Replies
13
Views
3K
  • Last Post
Replies
2
Views
1K
Top