Discrete Math. (Logically equivalent)

In summary, the conversation discusses the rules of inference for quantifiers and whether two statements involving the existential and universal quantifiers are logically equivalent. The conversation includes a clarification of the second statement and concludes that they are not equivalent.
  • #1
persian52
13
0
See attachment for the question.

----------------
∀x ∈ D, if P(x) then Q(x). this means ∀x P(x) -> Q(x).
all you have to do is find a value for x
∀x this means for ALL x right
so you can choose ANY element
but for the E its only things in the domain
so all you have to do is choose an x that's not in E's domain
and then you can say therefore its not logically equivalent.

I think am wrong.

----------------
Please help me out with this problem.
thank you in advance.
 

Attachments

  • hmassig.jpg
    hmassig.jpg
    10.5 KB · Views: 427
  • table2.png
    table2.png
    15.1 KB · Views: 520
Physics news on Phys.org
  • #2
The question is a little unclear. First, you list four rules of inference for quantifiers in cut form. OK. Then, since you are talking about the all quantifier, I presume you want to refer to the first one. So, you start with
[itex]\forall[/itex] x [itex]\in[/itex] D (P(x)[itex]\Rightarrow[/itex] Q(x))
Then, instance with c, P(c)[itex]\Rightarrow[/itex] Q(c). No problem here.
But then you say that you can choose any c, including one not in the domain (of the quantifier, I presume you mean, in this case D), which contradicts your original statement which bounded your quantifier to D.
Then you start mentioning "E": I am not sure whether you are referring to the existential quantifier [itex]\exists[/itex] or the set membership relation [itex]\in[/itex].
Then you say that "it's" not logically equivalent. So far, no equivalence has been mentioned, so what is "it"? and what is it not equivalent to?
Please clarify your question, and then I would be glad to help.
 
  • #3
^There were two pages to what he posted. The question asks about:

[itex] \exists x ( P(x) \rightarrow Q(x) ) [/itex], and
[itex] (\forall x) P(x) \rightarrow (\exists x) Q(x) [/itex]

Are they logically equivalent? No. There is more than one way to argue it. One obvious thing to take note of is that the in the first statement, the existential binds both instances of little x.
This statement can be translated as "there exists an object such that P(x) implies Q(x)" (same x)

There is more than one structural difference between the first statement and the second. Can you think of any?
 
  • #4
Before one could even touch the question as to whether the two statements are equivalent, one would have to make sure that they both make sense. The first one, of course, does, but the second one does not even make sense. What is meant, I think, is
[itex]\forall[/itex]x P(x) [itex]\rightarrow[/itex][itex]\exists[/itex]y Q(y).

Once that has been cleaned up, one can proceed to show that they are not equivalent.
 
  • #5
^Come to think of it, nomadreid is absolutely correct. I had parsed the notation to the only thing that made sense in my mind (what you wrote), assuming it was just a strange notation. But I haven't seen it elsewhere.
 
  • #6
thank you guys for the help!
 

1. What is discrete math and how is it different from other branches of mathematics?

Discrete math is a branch of mathematics that deals with discrete objects and structures, as opposed to continuous ones. It focuses on topics such as logic, set theory, combinatorics, graph theory, and algorithms. Unlike other branches of math, which deal with continuous quantities and functions, discrete math deals with countable objects and structures.

2. What are some real-life applications of discrete math?

Discrete math has a wide range of applications in various fields, including computer science, engineering, economics, and social sciences. It is used to solve problems related to networks, coding, scheduling, and decision making, among others. For example, discrete math is used in designing efficient algorithms for search engines, optimizing transportation routes, and predicting stock market trends.

3. What does it mean for two statements to be logically equivalent?

Two statements are considered logically equivalent if they have the same truth value in every possible scenario. In other words, they are either both true or both false in every case. This concept is crucial in discrete math, as it allows us to simplify complex logical expressions and make precise deductions and conclusions.

4. How do you determine if two logical statements are equivalent?

To determine if two logical statements are equivalent, you can use truth tables, logical equivalences, or proof techniques such as direct proof, proof by contradiction, or proof by contraposition. These methods involve systematically analyzing the structure and truth values of the statements to determine if they are equivalent or not.

5. How can discrete math help improve problem-solving skills?

Discrete math involves thinking abstractly and logically, which can help improve problem-solving skills. It teaches you how to break down complex problems into smaller, more manageable parts, and how to use logical reasoning to arrive at solutions. These skills are valuable not only in mathematics but also in many other areas of life.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
824
  • Set Theory, Logic, Probability, Statistics
Replies
0
Views
990
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
855
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
917
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Back
Top