Discrete mathematics: first order (predicate) logic

S

salvatorekate95

New member
Joined
Sep 20, 2014
Messages
9
Translate into English the following first-order formulae and determine which of them represent true propositions when interpreted in R:

\(\displaystyle \mbox{1) }\, \forall x\, (x\, =\, x^2\, \rightarrow\, x\, <\, 0)\)

\(\displaystyle \mbox{2) }\, \forall x\, (x\, >\, 0\, \rightarrow\, x^2\, >\, x)\)

\(\displaystyle \mbox{3) }\, \forall x\, \left(x\, =\, 0\, \lor\, \lnot(x\, +\, x\, =\, x)\right)\)

\(\displaystyle \mbox{4) }\, \exists x \forall y\, (x\, > y)\)

\(\displaystyle \mbox{5) }\, \forall x\, \forall y\, \left(x\, >\, y\, \rightarrow\, \exists z\, (x\, >\, z\, \land\, z\, >\, y)\right)\)
 
Last edited by a moderator:
salvatorekate95 said:
Translate into English the following first-order formulae and determine which of them represent true propositions when interpreted in R:

\(\displaystyle \mbox{1) }\, \forall x\, (x\, =\, x^2\, \rightarrow\, x\, <\, 0)\)

\(\displaystyle \mbox{2) }\, \forall x\, (x\, >\, 0\, \rightarrow\, x^2\, >\, x)\)

\(\displaystyle \mbox{3) }\, \forall x\, \left(x\, =\, 0\, \lor\, \lnot(x\, +\, x\, =\, x)\right)\)

\(\displaystyle \mbox{4) }\, \exists x \forall y\, (x\, > y)\)

\(\displaystyle \mbox{5) }\, \forall x\, \forall y\, \left(x\, >\, y\, \rightarrow\, \exists z\, (x\, >\, z\, \land\, z\, >\, y)\right)\)
Click to expand...
You seem to have the wrong idea. This is not a homework service. Post your work so we can help.

Here is #4. Some number is greater than every number.
 
Last edited:
No, that is what #4 says. #5 says "given any two numbers there exist a third number between them."
 
1. False. Example: x=1, 1^2=1 and 1>0
2. True. 2^2=4 and 4>2
3. I don't know what it says.
4. I think that it is false but I can't explain it.
5. True?
 
salvatorekate95 said:
4. I think that it is false but I can't explain it.
5. True?
Click to expand...
4. Is there a number that is greater that every number?

5. Suppose \(\displaystyle x<y\) then
\(\displaystyle \begin{align*} \dfrac{x}{2}&<\dfrac{y}{2}….(1)\text{divide by two}\\\dfrac{x+y}{2}&<y….(2)\text{add y/2 to (1)} \\x&<\dfrac{x+y}{2}….(3)\text{add x/2 to (1)} \\x&<\dfrac{x+y}{2}<y….(4)\text{combine 2 & 3 }\end{align*}\)
 
salvatorekate95 said:
1. False. Example: x=1, 1^2=1 and 1>0
2. True. 2^2=4 and 4>2
3. I don't know what it says.
4. I think that it is false but I can't explain it.
5. True?
Click to expand...

You need to learn the notation
\(\displaystyle \exists\text { x is 'there exists an x'}\)
\(\displaystyle \forall x\text { is 'for all x'}\)
∧ is the logical 'and'
∨ is the logical 'or'
¬ is the logical 'not'
\(\displaystyle >\text{ is the 'greater than' sign}\)
and so forth.

1. o.k.
2. What about \(\displaystyle \frac{1}{2}\)
3. see below
4. consider y + 1
5. consider \(\displaystyle \frac{x+y}{2}\)

[FONT=MathJax_Main]3) [/FONT][FONT=MathJax_Main]∀[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]0[/FONT][FONT=MathJax_Main]∨[/FONT][FONT=MathJax_Main]¬[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main])[/FONT]
[FONT=MathJax_Main]∀[/FONT][FONT=MathJax_Math]x For all x[/FONT][FONT=MathJax_Main]
[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]0 either x is 0
[/FONT][FONT=MathJax_Main]∨ or
[/FONT][FONT=MathJax_Main]¬[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main])[/FONT] it is not the case that x+x is equal to x
 
pka said:
4. Is there a number that is greater that every number?

5. Suppose \(\displaystyle x<y\) then
\(\displaystyle \begin{align*} \dfrac{x}{2}&<\dfrac{y}{2}….(1)\text{divide by two}\\\dfrac{x+y}{2}&<y….(2)\text{add y/2 to (1)} \\x&<\dfrac{x+y}{2}….(3)\text{add x/2 to (1)} \\x&<\dfrac{x+y}{2}<y….(4)\text{combine 2 & 3 }\end{align*}\)
Click to expand...


4). In that case, 4 is false. There is not a real number that is greater than every number.

5). So it is true.
Example:
x=1 y=2
(1+2)2=1.5
1<1.5<2
 
Ishuda said:
You need to learn the notation
\(\displaystyle \exists\text { x is 'there exists an x'}\)
\(\displaystyle \forall x\text { is 'for all x'}\)
∧ is the logical 'and'
∨ is the logical 'or'
¬ is the logical 'not'
\(\displaystyle >\text{ is the 'greater than' sign}\)
and so forth.

1. o.k.
2. What about \(\displaystyle \frac{1}{2}\)
3. see below
4. consider y + 1
5. consider \(\displaystyle \frac{x+y}{2}\)

[FONT=MathJax_Main]3) [/FONT][FONT=MathJax_Main]∀[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]0[/FONT][FONT=MathJax_Main]∨[/FONT][FONT=MathJax_Main]¬[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main])[/FONT]
[FONT=MathJax_Main]∀[/FONT][FONT=MathJax_Math]x For all x[/FONT][FONT=MathJax_Main]
[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]0 either x is 0
[/FONT][FONT=MathJax_Main]∨ or
[/FONT][FONT=MathJax_Main]¬[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main])[/FONT] it is not the case that x+x is equal to x
Click to expand...



2. If x=1/2, then it is false. 0.5>0.25


3. if x=1 then [FONT=MathJax_Main]¬[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]) [/FONT]true.
if x=0 then 0+0=0. In that case 3 must be false?
 
Last edited:
salvatorekate95 said:
4). In that case, 4 is false. There is not a real number that is greater than every number.

5). So it is true.
Example:
x=1 y=2
(1+2)2=1.5
1<1.5<2
Click to expand...

4) \(\displaystyle \exists x \forall y\, (x\, > y)\)
Given any real number y, is x = y+1 greater than y?

5) True, that is an example. However giving an example (or a 1000 examples) of something doesn't prove it is true for everything. Fortunately, giving an example where it is false does prove that it is not true for everything.
 
Ishuda said:

4) \(\displaystyle \exists x \forall y\, (x\, > y)\)
Given any real number y, is x = y+1 greater than y?

5) True, that is an example. However giving an example (or a 1000 examples) of something doesn't prove it is true for everything. Fortunately, giving an example where it is false does prove that it is not true for everything.
Click to expand...



4) If x=y+1, so x is greater than y. And then 4 is true.

But 5 is true, right?
 
salvatorekate95 said:
4) If x=y+1, so x is greater than y. And then 4 is true.

But 5 is true, right?
Click to expand...
5 is true but you didn't prove it with just the example. You need to do something like the following
x < y => x + y < 2 y => (x+y)/2 < y
and similarly for the other side
x < y => 2 x < x + y => x < (x+y)/2
 
Last edited:
Yes, 5 is true but can you say why it is true? Can you give a proof. A "counter-example", a single example in which a statement if false is sufficient to prove that it is not always true. But a single example will not prove it is always true!

If x> y, can you write a formula for z, depending only on x and y? That would prove that such a z always exists.
 
You must log in or register to reply here.
Top