How to express propositional functions with multiple quantifiers using “AND” and "OR'?
$begingroup$
Consider the quantifier "for every" , it simply means variable '$x$' has to be true for all values of '$x$' upon a propositional function $P(x)$. So we could 'AND' all the values from domain of 'x' and find whether its true.
For example: $forall x[P(x)]$ is equivalent to : $P(x_1) land P(x_2) land dots land P(x_n)$
Similar case for "there exists", atleast one of them has to be true. So OR could be used
$exists x[P(x)]$ is equivalent to : $P(x_1) lor P(x_2) lor dots lor P(x_n)$
What I am asking is when it comes to proposition involving more than one quantifiers. How to express it in above form ?
For example, consider a proposition involving 2 variables $P(x,y)$.
Consider $exists x forall x[P(x,y)]$. How can I write it using 'AND' and 'OR'
logic first-order-logic predicate-logic quantifiers
edited Dec 24 '18 at 14:36
Bram28
63.3k44793
asked Dec 23 '18 at 7:53
Mathews GeorgeMathews George
194
$endgroup$
add a comment |
$begingroup$
Consider the quantifier "for every" , it simply means variable '$x$' has to be true for all values of '$x$' upon a propositional function $P(x)$. So we could 'AND' all the values from domain of 'x' and find whether its true.
For example: $forall x[P(x)]$ is equivalent to : $P(x_1) land P(x_2) land dots land P(x_n)$
Similar case for "there exists", atleast one of them has to be true. So OR could be used
$exists x[P(x)]$ is equivalent to : $P(x_1) lor P(x_2) lor dots lor P(x_n)$
What I am asking is when it comes to proposition involving more than one quantifiers. How to express it in above form ?
For example, consider a proposition involving 2 variables $P(x,y)$.
Consider $exists x forall x[P(x,y)]$. How can I write it using 'AND' and 'OR'
logic first-order-logic predicate-logic quantifiers
edited Dec 24 '18 at 14:36
Bram28
63.3k44793
asked Dec 23 '18 at 7:53
Mathews GeorgeMathews George
194
$endgroup$
add a comment |
$begingroup$
Consider the quantifier "for every" , it simply means variable '$x$' has to be true for all values of '$x$' upon a propositional function $P(x)$. So we could 'AND' all the values from domain of 'x' and find whether its true.
For example: $forall x[P(x)]$ is equivalent to : $P(x_1) land P(x_2) land dots land P(x_n)$
Similar case for "there exists", atleast one of them has to be true. So OR could be used
$exists x[P(x)]$ is equivalent to : $P(x_1) lor P(x_2) lor dots lor P(x_n)$
What I am asking is when it comes to proposition involving more than one quantifiers. How to express it in above form ?
For example, consider a proposition involving 2 variables $P(x,y)$.
Consider $exists x forall x[P(x,y)]$. How can I write it using 'AND' and 'OR'
logic first-order-logic predicate-logic quantifiers
edited Dec 24 '18 at 14:36
Bram28
63.3k44793
asked Dec 23 '18 at 7:53
Mathews GeorgeMathews George
194
$endgroup$
Consider the quantifier "for every" , it simply means variable '$x$' has to be true for all values of '$x$' upon a propositional function $P(x)$. So we could 'AND' all the values from domain of 'x' and find whether its true.
For example: $forall x[P(x)]$ is equivalent to : $P(x_1) land P(x_2) land dots land P(x_n)$
Similar case for "there exists", atleast one of them has to be true. So OR could be used
$exists x[P(x)]$ is equivalent to : $P(x_1) lor P(x_2) lor dots lor P(x_n)$
What I am asking is when it comes to proposition involving more than one quantifiers. How to express it in above form ?
For example, consider a proposition involving 2 variables $P(x,y)$.
Consider $exists x forall x[P(x,y)]$. How can I write it using 'AND' and 'OR'
logic first-order-logic predicate-logic quantifiers
logic first-order-logic predicate-logic quantifiers
edited Dec 24 '18 at 14:36
Bram28
63.3k44793
asked Dec 23 '18 at 7:53
Mathews GeorgeMathews George
194
edited Dec 24 '18 at 14:36
Bram28
63.3k44793
asked Dec 23 '18 at 7:53
Mathews GeorgeMathews George
194
edited Dec 24 '18 at 14:36
Bram28
63.3k44793
edited Dec 24 '18 at 14:36
Bram28
63.3k44793
edited Dec 24 '18 at 14:36
Bram28
63.3k44793
63.3k44793
asked Dec 23 '18 at 7:53
Mathews GeorgeMathews George
194
asked Dec 23 '18 at 7:53
Mathews GeorgeMathews George
194
asked Dec 23 '18 at 7:53
Mathews GeorgeMathews George
194
194
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
First of all, please know that these are not equivalences in the strict sense of logical equivalence ... with $n$ terms in $P(x_1) land ... land P(x_n)$ the best we can say is that that statement will have the same truth-value as $forall x P(x)$ for any domain with $n$ elements, and where $x_1$, $x_2$ ... are treated as constants that respectively denote each of those $n$ different objects. Indeed, to make that clear, I would use $c_i$'s rather than $x_i$'s
Still, as long as you are careful and understand this restriction, you can indeed usefully work with this 'equivalence' ... which I'll denote by $approx$
Now to your question. If you have multiple quantifiers you can just work them out step by step:
$$exists x forall y P(x,y)approx$$
$$forall y P(c_1,y) lor forall y P(c_2,y) lor .... lor forall y P(c_n,y) approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
You can also work this out inside out:
$$exists x forall y P(x,y)approx$$
$$exists x (P(x,c_1) land P(x,c_2)land ... land P(x,c_n)approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
answered Dec 24 '18 at 14:33
Bram28Bram28
63.3k44793
$endgroup$
$begingroup$
Thank you, I understood the method with multiple quantifiers, but I cannot understand why is it approximated. "these are not equivalences in the strict sense of logical equivalence", Can you explain or provide some links ?
$endgroup$
– Mathews George
Dec 25 '18 at 6:06
add a comment |
$begingroup$
$$bigl(P(x_1,y_1)land ldotsland P(x_1,y-n)bigr)lorbigl(P(x_2,y_1)landldotsland P(x_2,y_n)bigr)lorldotslorbigl(P(x_n,y-1)landldots P(x_n,y_n)bigr) $$
answered Dec 23 '18 at 8:14
Hagen von EitzenHagen von Eitzen
2843
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3050149%2fhow-to-express-propositional-functions-with-multiple-quantifiers-using-and-and%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First of all, please know that these are not equivalences in the strict sense of logical equivalence ... with $n$ terms in $P(x_1) land ... land P(x_n)$ the best we can say is that that statement will have the same truth-value as $forall x P(x)$ for any domain with $n$ elements, and where $x_1$, $x_2$ ... are treated as constants that respectively denote each of those $n$ different objects. Indeed, to make that clear, I would use $c_i$'s rather than $x_i$'s
Still, as long as you are careful and understand this restriction, you can indeed usefully work with this 'equivalence' ... which I'll denote by $approx$
Now to your question. If you have multiple quantifiers you can just work them out step by step:
$$exists x forall y P(x,y)approx$$
$$forall y P(c_1,y) lor forall y P(c_2,y) lor .... lor forall y P(c_n,y) approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
You can also work this out inside out:
$$exists x forall y P(x,y)approx$$
$$exists x (P(x,c_1) land P(x,c_2)land ... land P(x,c_n)approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
answered Dec 24 '18 at 14:33
Bram28Bram28
63.3k44793
$endgroup$
$begingroup$
Thank you, I understood the method with multiple quantifiers, but I cannot understand why is it approximated. "these are not equivalences in the strict sense of logical equivalence", Can you explain or provide some links ?
$endgroup$
– Mathews George
Dec 25 '18 at 6:06
add a comment |
$begingroup$
First of all, please know that these are not equivalences in the strict sense of logical equivalence ... with $n$ terms in $P(x_1) land ... land P(x_n)$ the best we can say is that that statement will have the same truth-value as $forall x P(x)$ for any domain with $n$ elements, and where $x_1$, $x_2$ ... are treated as constants that respectively denote each of those $n$ different objects. Indeed, to make that clear, I would use $c_i$'s rather than $x_i$'s
Still, as long as you are careful and understand this restriction, you can indeed usefully work with this 'equivalence' ... which I'll denote by $approx$
Now to your question. If you have multiple quantifiers you can just work them out step by step:
$$exists x forall y P(x,y)approx$$
$$forall y P(c_1,y) lor forall y P(c_2,y) lor .... lor forall y P(c_n,y) approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
You can also work this out inside out:
$$exists x forall y P(x,y)approx$$
$$exists x (P(x,c_1) land P(x,c_2)land ... land P(x,c_n)approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
answered Dec 24 '18 at 14:33
Bram28Bram28
63.3k44793
$endgroup$
$begingroup$
Thank you, I understood the method with multiple quantifiers, but I cannot understand why is it approximated. "these are not equivalences in the strict sense of logical equivalence", Can you explain or provide some links ?
$endgroup$
– Mathews George
Dec 25 '18 at 6:06
add a comment |
$begingroup$
First of all, please know that these are not equivalences in the strict sense of logical equivalence ... with $n$ terms in $P(x_1) land ... land P(x_n)$ the best we can say is that that statement will have the same truth-value as $forall x P(x)$ for any domain with $n$ elements, and where $x_1$, $x_2$ ... are treated as constants that respectively denote each of those $n$ different objects. Indeed, to make that clear, I would use $c_i$'s rather than $x_i$'s
Still, as long as you are careful and understand this restriction, you can indeed usefully work with this 'equivalence' ... which I'll denote by $approx$
Now to your question. If you have multiple quantifiers you can just work them out step by step:
$$exists x forall y P(x,y)approx$$
$$forall y P(c_1,y) lor forall y P(c_2,y) lor .... lor forall y P(c_n,y) approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
You can also work this out inside out:
$$exists x forall y P(x,y)approx$$
$$exists x (P(x,c_1) land P(x,c_2)land ... land P(x,c_n)approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
answered Dec 24 '18 at 14:33
Bram28Bram28
63.3k44793
$endgroup$
First of all, please know that these are not equivalences in the strict sense of logical equivalence ... with $n$ terms in $P(x_1) land ... land P(x_n)$ the best we can say is that that statement will have the same truth-value as $forall x P(x)$ for any domain with $n$ elements, and where $x_1$, $x_2$ ... are treated as constants that respectively denote each of those $n$ different objects. Indeed, to make that clear, I would use $c_i$'s rather than $x_i$'s
Still, as long as you are careful and understand this restriction, you can indeed usefully work with this 'equivalence' ... which I'll denote by $approx$
Now to your question. If you have multiple quantifiers you can just work them out step by step:
$$exists x forall y P(x,y)approx$$
$$forall y P(c_1,y) lor forall y P(c_2,y) lor .... lor forall y P(c_n,y) approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
You can also work this out inside out:
$$exists x forall y P(x,y)approx$$
$$exists x (P(x,c_1) land P(x,c_2)land ... land P(x,c_n)approx$$
$$(P(c_1,c_1) land P(c_1,c_2) land ...P(c_1,c_n)) lor (P(c_2,c_1) land P(c_2,c_2) land ...P(c_2,c_n)) land .... land (P(c_n,c_1) land P(c_n,c_2) land ...P(c_n,c_n))$$
answered Dec 24 '18 at 14:33
Bram28Bram28
63.3k44793
answered Dec 24 '18 at 14:33
Bram28Bram28
63.3k44793
answered Dec 24 '18 at 14:33
Bram28Bram28
63.3k44793
answered Dec 24 '18 at 14:33
Bram28Bram28
63.3k44793
63.3k44793
$begingroup$
Thank you, I understood the method with multiple quantifiers, but I cannot understand why is it approximated. "these are not equivalences in the strict sense of logical equivalence", Can you explain or provide some links ?
$endgroup$
– Mathews George
Dec 25 '18 at 6:06
add a comment |
$begingroup$
Thank you, I understood the method with multiple quantifiers, but I cannot understand why is it approximated. "these are not equivalences in the strict sense of logical equivalence", Can you explain or provide some links ?
$endgroup$
– Mathews George
Dec 25 '18 at 6:06
$begingroup$
Thank you, I understood the method with multiple quantifiers, but I cannot understand why is it approximated. "these are not equivalences in the strict sense of logical equivalence", Can you explain or provide some links ?
$endgroup$
– Mathews George
Dec 25 '18 at 6:06
$begingroup$
Thank you, I understood the method with multiple quantifiers, but I cannot understand why is it approximated. "these are not equivalences in the strict sense of logical equivalence", Can you explain or provide some links ?
$endgroup$
– Mathews George
Dec 25 '18 at 6:06
add a comment |
$begingroup$
$$bigl(P(x_1,y_1)land ldotsland P(x_1,y-n)bigr)lorbigl(P(x_2,y_1)landldotsland P(x_2,y_n)bigr)lorldotslorbigl(P(x_n,y-1)landldots P(x_n,y_n)bigr) $$
answered Dec 23 '18 at 8:14
Hagen von EitzenHagen von Eitzen
2843
$endgroup$
add a comment |
$begingroup$
$$bigl(P(x_1,y_1)land ldotsland P(x_1,y-n)bigr)lorbigl(P(x_2,y_1)landldotsland P(x_2,y_n)bigr)lorldotslorbigl(P(x_n,y-1)landldots P(x_n,y_n)bigr) $$
answered Dec 23 '18 at 8:14
Hagen von EitzenHagen von Eitzen
2843
$endgroup$
add a comment |
$begingroup$
$$bigl(P(x_1,y_1)land ldotsland P(x_1,y-n)bigr)lorbigl(P(x_2,y_1)landldotsland P(x_2,y_n)bigr)lorldotslorbigl(P(x_n,y-1)landldots P(x_n,y_n)bigr) $$
answered Dec 23 '18 at 8:14
Hagen von EitzenHagen von Eitzen
2843
$endgroup$
$$bigl(P(x_1,y_1)land ldotsland P(x_1,y-n)bigr)lorbigl(P(x_2,y_1)landldotsland P(x_2,y_n)bigr)lorldotslorbigl(P(x_n,y-1)landldots P(x_n,y_n)bigr) $$
answered Dec 23 '18 at 8:14
Hagen von EitzenHagen von Eitzen
2843
answered Dec 23 '18 at 8:14
Hagen von EitzenHagen von Eitzen
2843
answered Dec 23 '18 at 8:14
Hagen von EitzenHagen von Eitzen
2843
answered Dec 23 '18 at 8:14
Hagen von EitzenHagen von Eitzen
2843
2843
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3050149%2fhow-to-express-propositional-functions-with-multiple-quantifiers-using-and-and%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
