Mixing
checking validity of given first order logic
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Apologies if this question is already posted.As it is hard to search $LaTeX$ in google and first order logic in nothing without $LaTeX$ .But i am sure i have different doubt than that of already posted one!
Question
Check if the given formula is valid or not.
$1.forall x exists y P(x,y) Rightarrow exists y forall x P(x,y)$
$2.forall x (P(x) Rightarrow Q(x))Rightarrow left ( forall x P(x) Rightarrow forall x Q(x) right )$
My Approach
$1.forall x exists y P(x,y) Rightarrow exists y forall x P(x,y)$
$x=textset of all boys$
$y=textset of all girls$
$P(x,y)=textx loves y$
LHS=All boys loves some girls
RHS=some girl is loved by every boy.
Hence $LHS rightarrow RHS $ is not valid as LHS=true and RHS=false
$2.forall x (P(x) Rightarrow Q(x))Rightarrow left ( forall x P(x) Rightarrow forall x Q(x) right )$
$x=textset of natural numbers$
$P(x)=x textwhich is multiple of 4$
$Q(x)= textEven natural numbers $
LHS= $forall x (P(x) Rightarrow Q(x))$ which is always true.
RHS=$left ( forall x P(x) Rightarrow forall x Q(x) right )$
which says that if everything is multiple of $4$ then everything is even which is not true.
Hence $LHS rightarrow RHS $ is not valid as LHS=true and RHS=false
But i feel that $2$ is incorrect.
Please help!
discrete-mathematics logic first-order-logic predicate-logic
edited Jul 20 at 9:32
Mauro ALLEGRANZA
60.7k346105
asked Jul 20 at 8:13
laura
1,238521
 |Â
show 2 more comments
up vote
0
down vote
favorite
Apologies if this question is already posted.As it is hard to search $LaTeX$ in google and first order logic in nothing without $LaTeX$ .But i am sure i have different doubt than that of already posted one!
Question
Check if the given formula is valid or not.
$1.forall x exists y P(x,y) Rightarrow exists y forall x P(x,y)$
$2.forall x (P(x) Rightarrow Q(x))Rightarrow left ( forall x P(x) Rightarrow forall x Q(x) right )$
My Approach
$1.forall x exists y P(x,y) Rightarrow exists y forall x P(x,y)$
$x=textset of all boys$
$y=textset of all girls$
$P(x,y)=textx loves y$
LHS=All boys loves some girls
RHS=some girl is loved by every boy.
Hence $LHS rightarrow RHS $ is not valid as LHS=true and RHS=false
$2.forall x (P(x) Rightarrow Q(x))Rightarrow left ( forall x P(x) Rightarrow forall x Q(x) right )$
$x=textset of natural numbers$
$P(x)=x textwhich is multiple of 4$
$Q(x)= textEven natural numbers $
LHS= $forall x (P(x) Rightarrow Q(x))$ which is always true.
RHS=$left ( forall x P(x) Rightarrow forall x Q(x) right )$
which says that if everything is multiple of $4$ then everything is even which is not true.
Hence $LHS rightarrow RHS $ is not valid as LHS=true and RHS=false
But i feel that $2$ is incorrect.
Please help!
discrete-mathematics logic first-order-logic predicate-logic
edited Jul 20 at 9:32
Mauro ALLEGRANZA
60.7k346105
asked Jul 20 at 8:13
laura
1,238521
Why you are using $ne$ ? In order to check if a FOL formula is valid or not you have to consider possible interpretation; more specifically, for a formula with a conditional ($Rightarrow$), if you can find an int where the LHS is TRUE and the RHS is FALSE, then you jave showed that the formula is not valid.
– Mauro ALLEGRANZA
Jul 20 at 8:19
1
Applying it to your example 2 above, we have that (in the RHS) $forall x P(x)$ is FALSE, because it is not true that every natural number is a multiple of $4$ and thus the RHS $forall x P(x) Rightarrow forall x Q(x)$ is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:21
@MauroALLEGRANZA by $neq$ i meant $true Rightarrow false $ only ..thanks byw ...i updated it !
– laura
Jul 20 at 8:22
1
So again: in 2 the LHS is TRUE while the RHS is FALSE $Rightarrow$ FALSE, which is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:26
1
By the way, 2 is valid: try with a proof by contradiction: assume LHS TRUE and assume that RHS is FALSE, that means: $forall x Px$ is TRUE and $forall x Qx$ is FALSE, and see what happens.
– Mauro ALLEGRANZA
Jul 20 at 8:27
 |Â
show 2 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Apologies if this question is already posted.As it is hard to search $LaTeX$ in google and first order logic in nothing without $LaTeX$ .But i am sure i have different doubt than that of already posted one!
Question
Check if the given formula is valid or not.
$1.forall x exists y P(x,y) Rightarrow exists y forall x P(x,y)$
$2.forall x (P(x) Rightarrow Q(x))Rightarrow left ( forall x P(x) Rightarrow forall x Q(x) right )$
My Approach
$1.forall x exists y P(x,y) Rightarrow exists y forall x P(x,y)$
$x=textset of all boys$
$y=textset of all girls$
$P(x,y)=textx loves y$
LHS=All boys loves some girls
RHS=some girl is loved by every boy.
Hence $LHS rightarrow RHS $ is not valid as LHS=true and RHS=false
$2.forall x (P(x) Rightarrow Q(x))Rightarrow left ( forall x P(x) Rightarrow forall x Q(x) right )$
$x=textset of natural numbers$
$P(x)=x textwhich is multiple of 4$
$Q(x)= textEven natural numbers $
LHS= $forall x (P(x) Rightarrow Q(x))$ which is always true.
RHS=$left ( forall x P(x) Rightarrow forall x Q(x) right )$
which says that if everything is multiple of $4$ then everything is even which is not true.
Hence $LHS rightarrow RHS $ is not valid as LHS=true and RHS=false
But i feel that $2$ is incorrect.
Please help!
discrete-mathematics logic first-order-logic predicate-logic
edited Jul 20 at 9:32
Mauro ALLEGRANZA
60.7k346105
asked Jul 20 at 8:13
laura
1,238521
Apologies if this question is already posted.As it is hard to search $LaTeX$ in google and first order logic in nothing without $LaTeX$ .But i am sure i have different doubt than that of already posted one!
Question
Check if the given formula is valid or not.
$1.forall x exists y P(x,y) Rightarrow exists y forall x P(x,y)$
$2.forall x (P(x) Rightarrow Q(x))Rightarrow left ( forall x P(x) Rightarrow forall x Q(x) right )$
My Approach
$1.forall x exists y P(x,y) Rightarrow exists y forall x P(x,y)$
$x=textset of all boys$
$y=textset of all girls$
$P(x,y)=textx loves y$
LHS=All boys loves some girls
RHS=some girl is loved by every boy.
Hence $LHS rightarrow RHS $ is not valid as LHS=true and RHS=false
$2.forall x (P(x) Rightarrow Q(x))Rightarrow left ( forall x P(x) Rightarrow forall x Q(x) right )$
$x=textset of natural numbers$
$P(x)=x textwhich is multiple of 4$
$Q(x)= textEven natural numbers $
LHS= $forall x (P(x) Rightarrow Q(x))$ which is always true.
RHS=$left ( forall x P(x) Rightarrow forall x Q(x) right )$
which says that if everything is multiple of $4$ then everything is even which is not true.
Hence $LHS rightarrow RHS $ is not valid as LHS=true and RHS=false
But i feel that $2$ is incorrect.
Please help!
discrete-mathematics logic first-order-logic predicate-logic
edited Jul 20 at 9:32
Mauro ALLEGRANZA
60.7k346105
asked Jul 20 at 8:13
laura
1,238521
edited Jul 20 at 9:32
Mauro ALLEGRANZA
60.7k346105
edited Jul 20 at 9:32
Mauro ALLEGRANZA
60.7k346105
edited Jul 20 at 9:32
Mauro ALLEGRANZA
60.7k346105
60.7k346105
asked Jul 20 at 8:13
laura
1,238521
asked Jul 20 at 8:13
laura
1,238521
asked Jul 20 at 8:13
laura
1,238521
1,238521
Why you are using $ne$ ? In order to check if a FOL formula is valid or not you have to consider possible interpretation; more specifically, for a formula with a conditional ($Rightarrow$), if you can find an int where the LHS is TRUE and the RHS is FALSE, then you jave showed that the formula is not valid.
– Mauro ALLEGRANZA
Jul 20 at 8:19
1
Applying it to your example 2 above, we have that (in the RHS) $forall x P(x)$ is FALSE, because it is not true that every natural number is a multiple of $4$ and thus the RHS $forall x P(x) Rightarrow forall x Q(x)$ is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:21
@MauroALLEGRANZA by $neq$ i meant $true Rightarrow false $ only ..thanks byw ...i updated it !
– laura
Jul 20 at 8:22
1
So again: in 2 the LHS is TRUE while the RHS is FALSE $Rightarrow$ FALSE, which is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:26
1
By the way, 2 is valid: try with a proof by contradiction: assume LHS TRUE and assume that RHS is FALSE, that means: $forall x Px$ is TRUE and $forall x Qx$ is FALSE, and see what happens.
– Mauro ALLEGRANZA
Jul 20 at 8:27
 |Â
show 2 more comments
Why you are using $ne$ ? In order to check if a FOL formula is valid or not you have to consider possible interpretation; more specifically, for a formula with a conditional ($Rightarrow$), if you can find an int where the LHS is TRUE and the RHS is FALSE, then you jave showed that the formula is not valid.
– Mauro ALLEGRANZA
Jul 20 at 8:19
1
Applying it to your example 2 above, we have that (in the RHS) $forall x P(x)$ is FALSE, because it is not true that every natural number is a multiple of $4$ and thus the RHS $forall x P(x) Rightarrow forall x Q(x)$ is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:21
@MauroALLEGRANZA by $neq$ i meant $true Rightarrow false $ only ..thanks byw ...i updated it !
– laura
Jul 20 at 8:22
1
So again: in 2 the LHS is TRUE while the RHS is FALSE $Rightarrow$ FALSE, which is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:26
1
By the way, 2 is valid: try with a proof by contradiction: assume LHS TRUE and assume that RHS is FALSE, that means: $forall x Px$ is TRUE and $forall x Qx$ is FALSE, and see what happens.
– Mauro ALLEGRANZA
Jul 20 at 8:27
Why you are using $ne$ ? In order to check if a FOL formula is valid or not you have to consider possible interpretation; more specifically, for a formula with a conditional ($Rightarrow$), if you can find an int where the LHS is TRUE and the RHS is FALSE, then you jave showed that the formula is not valid.
– Mauro ALLEGRANZA
Jul 20 at 8:19
Why you are using $ne$ ? In order to check if a FOL formula is valid or not you have to consider possible interpretation; more specifically, for a formula with a conditional ($Rightarrow$), if you can find an int where the LHS is TRUE and the RHS is FALSE, then you jave showed that the formula is not valid.
– Mauro ALLEGRANZA
Jul 20 at 8:19
1
1
Applying it to your example 2 above, we have that (in the RHS) $forall x P(x)$ is FALSE, because it is not true that every natural number is a multiple of $4$ and thus the RHS $forall x P(x) Rightarrow forall x Q(x)$ is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:21
Applying it to your example 2 above, we have that (in the RHS) $forall x P(x)$ is FALSE, because it is not true that every natural number is a multiple of $4$ and thus the RHS $forall x P(x) Rightarrow forall x Q(x)$ is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:21
@MauroALLEGRANZA by $neq$ i meant $true Rightarrow false $ only ..thanks byw ...i updated it !
– laura
Jul 20 at 8:22
@MauroALLEGRANZA by $neq$ i meant $true Rightarrow false $ only ..thanks byw ...i updated it !
– laura
Jul 20 at 8:22
1
1
So again: in 2 the LHS is TRUE while the RHS is FALSE $Rightarrow$ FALSE, which is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:26
So again: in 2 the LHS is TRUE while the RHS is FALSE $Rightarrow$ FALSE, which is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:26
1
1
By the way, 2 is valid: try with a proof by contradiction: assume LHS TRUE and assume that RHS is FALSE, that means: $forall x Px$ is TRUE and $forall x Qx$ is FALSE, and see what happens.
– Mauro ALLEGRANZA
Jul 20 at 8:27
By the way, 2 is valid: try with a proof by contradiction: assume LHS TRUE and assume that RHS is FALSE, that means: $forall x Px$ is TRUE and $forall x Qx$ is FALSE, and see what happens.
– Mauro ALLEGRANZA
Jul 20 at 8:27
 |Â
show 2 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2857410%2fchecking-validity-of-given-first-order-logic%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Why you are using $ne$ ? In order to check if a FOL formula is valid or not you have to consider possible interpretation; more specifically, for a formula with a conditional ($Rightarrow$), if you can find an int where the LHS is TRUE and the RHS is FALSE, then you jave showed that the formula is not valid.
– Mauro ALLEGRANZA
Jul 20 at 8:19
1
Applying it to your example 2 above, we have that (in the RHS) $forall x P(x)$ is FALSE, because it is not true that every natural number is a multiple of $4$ and thus the RHS $forall x P(x) Rightarrow forall x Q(x)$ is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:21
@MauroALLEGRANZA by $neq$ i meant $true Rightarrow false $ only ..thanks byw ...i updated it !
– laura
Jul 20 at 8:22
1
So again: in 2 the LHS is TRUE while the RHS is FALSE $Rightarrow$ FALSE, which is TRUE.
– Mauro ALLEGRANZA
Jul 20 at 8:26
1
By the way, 2 is valid: try with a proof by contradiction: assume LHS TRUE and assume that RHS is FALSE, that means: $forall x Px$ is TRUE and $forall x Qx$ is FALSE, and see what happens.
– Mauro ALLEGRANZA
Jul 20 at 8:27