Simplify [p∧ (¬(¬p v q)) ] v (p ∧ q) so that it become p, q, ¬p, or ¬q
$begingroup$
Had a question on a test that asked for us to simplify (using rules of inference) the following proposition: [p∧ (¬(¬p v q)) ] v (p ∧ q)
to p, q, or their negation (¬p, ¬q). Here is what I did:
1) [p∧ (¬(¬p v q)) ] v (p ∧ q)
2) [p∧ (p ∧ ¬q)) ] v (p ∧ q) DeMorgan's Law
3) [(p∧ p) ∧ ¬q] v (p∧ q) Associative law
4) [p ∧ ¬q] v (p∧ q) Idempotent law
Step 4 is where I got stuck. I didn't know what to do afterwards. So I substituted S= (p∧ q) and did distributive law
5) [p ∧ ¬q] v S
6) (S v p) ∧ (S v ¬q) Distributive law
7) [ (p∧q) v p ] ∧ [ (p∧q) v ¬q] Substitute S=(p∧q) back in
8) [ (pvp) ∧ (pvq) ] ∧ [ (¬q v p) ∧ (¬q v q) ] Distributive law
9) [ p ∧ (pvq) ] ∧ [ (¬q v p) ∧ T ] Idempotent law and Domination law
10) p ∧ (¬q v p) Absorption and Identity law
I stopped there. I didn't know how to further simplify step 10 into p, q, ¬p, or ¬q. I was thinking maybe absorption law? But p ∧ (¬q v p) is not the same as p ∧ (q v p), so I couldn't simplify it to p, correct? Can someone help me further simplify it? Do you think I will get most the marks for this question or was my approach completely wrong?
discrete-mathematics logic propositional-calculus boolean-algebra
edited 1 min ago
Bram28
62.6k44793
asked 5 hours ago
NevNev
254
$endgroup$
add a comment |
$begingroup$
Had a question on a test that asked for us to simplify (using rules of inference) the following proposition: [p∧ (¬(¬p v q)) ] v (p ∧ q)
to p, q, or their negation (¬p, ¬q). Here is what I did:
1) [p∧ (¬(¬p v q)) ] v (p ∧ q)
2) [p∧ (p ∧ ¬q)) ] v (p ∧ q) DeMorgan's Law
3) [(p∧ p) ∧ ¬q] v (p∧ q) Associative law
4) [p ∧ ¬q] v (p∧ q) Idempotent law
Step 4 is where I got stuck. I didn't know what to do afterwards. So I substituted S= (p∧ q) and did distributive law
5) [p ∧ ¬q] v S
6) (S v p) ∧ (S v ¬q) Distributive law
7) [ (p∧q) v p ] ∧ [ (p∧q) v ¬q] Substitute S=(p∧q) back in
8) [ (pvp) ∧ (pvq) ] ∧ [ (¬q v p) ∧ (¬q v q) ] Distributive law
9) [ p ∧ (pvq) ] ∧ [ (¬q v p) ∧ T ] Idempotent law and Domination law
10) p ∧ (¬q v p) Absorption and Identity law
I stopped there. I didn't know how to further simplify step 10 into p, q, ¬p, or ¬q. I was thinking maybe absorption law? But p ∧ (¬q v p) is not the same as p ∧ (q v p), so I couldn't simplify it to p, correct? Can someone help me further simplify it? Do you think I will get most the marks for this question or was my approach completely wrong?
discrete-mathematics logic propositional-calculus boolean-algebra
edited 1 min ago
Bram28
62.6k44793
asked 5 hours ago
NevNev
254
$endgroup$
$begingroup$
By the way, $pland (neg q lor p)$ can be immediately simplified to $p$ by what is known as the absorption law. See for example math.stackexchange.com/questions/2421690/… for some further reading.
$endgroup$
– Minus One-Twelfth
2 hours ago
add a comment |
$begingroup$
Had a question on a test that asked for us to simplify (using rules of inference) the following proposition: [p∧ (¬(¬p v q)) ] v (p ∧ q)
to p, q, or their negation (¬p, ¬q). Here is what I did:
1) [p∧ (¬(¬p v q)) ] v (p ∧ q)
2) [p∧ (p ∧ ¬q)) ] v (p ∧ q) DeMorgan's Law
3) [(p∧ p) ∧ ¬q] v (p∧ q) Associative law
4) [p ∧ ¬q] v (p∧ q) Idempotent law
Step 4 is where I got stuck. I didn't know what to do afterwards. So I substituted S= (p∧ q) and did distributive law
5) [p ∧ ¬q] v S
6) (S v p) ∧ (S v ¬q) Distributive law
7) [ (p∧q) v p ] ∧ [ (p∧q) v ¬q] Substitute S=(p∧q) back in
8) [ (pvp) ∧ (pvq) ] ∧ [ (¬q v p) ∧ (¬q v q) ] Distributive law
9) [ p ∧ (pvq) ] ∧ [ (¬q v p) ∧ T ] Idempotent law and Domination law
10) p ∧ (¬q v p) Absorption and Identity law
I stopped there. I didn't know how to further simplify step 10 into p, q, ¬p, or ¬q. I was thinking maybe absorption law? But p ∧ (¬q v p) is not the same as p ∧ (q v p), so I couldn't simplify it to p, correct? Can someone help me further simplify it? Do you think I will get most the marks for this question or was my approach completely wrong?
discrete-mathematics logic propositional-calculus boolean-algebra
edited 1 min ago
Bram28
62.6k44793
asked 5 hours ago
NevNev
254
$endgroup$
Had a question on a test that asked for us to simplify (using rules of inference) the following proposition: [p∧ (¬(¬p v q)) ] v (p ∧ q)
to p, q, or their negation (¬p, ¬q). Here is what I did:
1) [p∧ (¬(¬p v q)) ] v (p ∧ q)
2) [p∧ (p ∧ ¬q)) ] v (p ∧ q) DeMorgan's Law
3) [(p∧ p) ∧ ¬q] v (p∧ q) Associative law
4) [p ∧ ¬q] v (p∧ q) Idempotent law
Step 4 is where I got stuck. I didn't know what to do afterwards. So I substituted S= (p∧ q) and did distributive law
5) [p ∧ ¬q] v S
6) (S v p) ∧ (S v ¬q) Distributive law
7) [ (p∧q) v p ] ∧ [ (p∧q) v ¬q] Substitute S=(p∧q) back in
8) [ (pvp) ∧ (pvq) ] ∧ [ (¬q v p) ∧ (¬q v q) ] Distributive law
9) [ p ∧ (pvq) ] ∧ [ (¬q v p) ∧ T ] Idempotent law and Domination law
10) p ∧ (¬q v p) Absorption and Identity law
I stopped there. I didn't know how to further simplify step 10 into p, q, ¬p, or ¬q. I was thinking maybe absorption law? But p ∧ (¬q v p) is not the same as p ∧ (q v p), so I couldn't simplify it to p, correct? Can someone help me further simplify it? Do you think I will get most the marks for this question or was my approach completely wrong?
discrete-mathematics logic propositional-calculus boolean-algebra
discrete-mathematics logic propositional-calculus boolean-algebra
edited 1 min ago
Bram28
62.6k44793
asked 5 hours ago
NevNev
254
edited 1 min ago
Bram28
62.6k44793
asked 5 hours ago
NevNev
254
edited 1 min ago
Bram28
62.6k44793
edited 1 min ago
Bram28
62.6k44793
edited 1 min ago
Bram28
62.6k44793
62.6k44793
asked 5 hours ago
NevNev
254
asked 5 hours ago
NevNev
254
asked 5 hours ago
NevNev
254
254
$begingroup$
By the way, $pland (neg q lor p)$ can be immediately simplified to $p$ by what is known as the absorption law. See for example math.stackexchange.com/questions/2421690/… for some further reading.
$endgroup$
– Minus One-Twelfth
2 hours ago
add a comment |
$begingroup$
By the way, $pland (neg q lor p)$ can be immediately simplified to $p$ by what is known as the absorption law. See for example math.stackexchange.com/questions/2421690/… for some further reading.
$endgroup$
– Minus One-Twelfth
2 hours ago
$begingroup$
By the way, $pland (neg q lor p)$ can be immediately simplified to $p$ by what is known as the absorption law. See for example math.stackexchange.com/questions/2421690/… for some further reading.
$endgroup$
– Minus One-Twelfth
2 hours ago
$begingroup$
By the way, $pland (neg q lor p)$ can be immediately simplified to $p$ by what is known as the absorption law. See for example math.stackexchange.com/questions/2421690/… for some further reading.
$endgroup$
– Minus One-Twelfth
2 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
This is a common 'mistake': to Distribute when you should really 'Un-Distribute'. That is, you can see:
$(p land neg q) lor (p land q)$
as the result of applying Distribution to:
$p land (neg q lor q)$
But given that this is an equivalence, that means you can go the other way around as well (i.e. 'un-distribute' ... sometimes I call this 'reverse distribution' or 'factoring')
Note that from your last line we can do this as well:
$p land (neg q lor p) = (bot lor p) land (neg q lor p) = (bot land neg q) lor p = bot lor p =p$
Finally, the fact that $(p land q) lor (p land neg q)$ works out to just $p$ is such a common and handy equivalence that it has been given its own name:
Adjacency
$(p land q) lor (p land neg q) =p$
(and its dual form:) $(p lor q) land (p lor neg q)=p$
So, definitely put that one in your boolean algebra toolbox!
answered 5 hours ago
Bram28Bram28
62.6k44793
$endgroup$
$begingroup$
Ohhhh you're totally right, that went right over my head. Judging by what I did for this question, do you think I'll lose all the marks?
$endgroup$
– Nev
4 hours ago
1
$begingroup$
@nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :)
$endgroup$
– Bram28
4 hours ago
add a comment |
$begingroup$
I'm going to use some shorthand notation: $pq$ for $p land q$, and $p + q$ for $p lor q$. Your proposition is $$p(neg(neg p + q)) + pq.$$ Distributing the negation on the left, we obtain $$p (neg (neg p + q)) + pq equiv pp(neg q) + pq.$$ Note that $pp equiv p$. This now gives us $$p(neg q) + pq.$$
We can "factor out" that $p$ to obtain $$p (neg q) + pq equiv p(neg q + q) equiv p,$$ and we're done.
answered 4 hours ago
rwboglrwbogl
1,007617
$endgroup$
$begingroup$
Yes I totally see that now, thanks! I really hope I get at least some partial marks. I was supposed to "undo" the distribution rather than distribute again
$endgroup$
– Nev
4 hours ago
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%2f3114498%2fsimplify-p%25e2%2588%25a7-%25c2%25ac%25c2%25acp-v-q-v-p-%25e2%2588%25a7-q-so-that-it-become-p-q-%25c2%25acp-or-%25c2%25acq%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$
This is a common 'mistake': to Distribute when you should really 'Un-Distribute'. That is, you can see:
$(p land neg q) lor (p land q)$
as the result of applying Distribution to:
$p land (neg q lor q)$
But given that this is an equivalence, that means you can go the other way around as well (i.e. 'un-distribute' ... sometimes I call this 'reverse distribution' or 'factoring')
Note that from your last line we can do this as well:
$p land (neg q lor p) = (bot lor p) land (neg q lor p) = (bot land neg q) lor p = bot lor p =p$
Finally, the fact that $(p land q) lor (p land neg q)$ works out to just $p$ is such a common and handy equivalence that it has been given its own name:
Adjacency
$(p land q) lor (p land neg q) =p$
(and its dual form:) $(p lor q) land (p lor neg q)=p$
So, definitely put that one in your boolean algebra toolbox!
answered 5 hours ago
Bram28Bram28
62.6k44793
$endgroup$
$begingroup$
Ohhhh you're totally right, that went right over my head. Judging by what I did for this question, do you think I'll lose all the marks?
$endgroup$
– Nev
4 hours ago
1
$begingroup$
@nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :)
$endgroup$
– Bram28
4 hours ago
add a comment |
$begingroup$
This is a common 'mistake': to Distribute when you should really 'Un-Distribute'. That is, you can see:
$(p land neg q) lor (p land q)$
as the result of applying Distribution to:
$p land (neg q lor q)$
But given that this is an equivalence, that means you can go the other way around as well (i.e. 'un-distribute' ... sometimes I call this 'reverse distribution' or 'factoring')
Note that from your last line we can do this as well:
$p land (neg q lor p) = (bot lor p) land (neg q lor p) = (bot land neg q) lor p = bot lor p =p$
Finally, the fact that $(p land q) lor (p land neg q)$ works out to just $p$ is such a common and handy equivalence that it has been given its own name:
Adjacency
$(p land q) lor (p land neg q) =p$
(and its dual form:) $(p lor q) land (p lor neg q)=p$
So, definitely put that one in your boolean algebra toolbox!
answered 5 hours ago
Bram28Bram28
62.6k44793
$endgroup$
$begingroup$
Ohhhh you're totally right, that went right over my head. Judging by what I did for this question, do you think I'll lose all the marks?
$endgroup$
– Nev
4 hours ago
1
$begingroup$
@nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :)
$endgroup$
– Bram28
4 hours ago
add a comment |
$begingroup$
This is a common 'mistake': to Distribute when you should really 'Un-Distribute'. That is, you can see:
$(p land neg q) lor (p land q)$
as the result of applying Distribution to:
$p land (neg q lor q)$
But given that this is an equivalence, that means you can go the other way around as well (i.e. 'un-distribute' ... sometimes I call this 'reverse distribution' or 'factoring')
Note that from your last line we can do this as well:
$p land (neg q lor p) = (bot lor p) land (neg q lor p) = (bot land neg q) lor p = bot lor p =p$
Finally, the fact that $(p land q) lor (p land neg q)$ works out to just $p$ is such a common and handy equivalence that it has been given its own name:
Adjacency
$(p land q) lor (p land neg q) =p$
(and its dual form:) $(p lor q) land (p lor neg q)=p$
So, definitely put that one in your boolean algebra toolbox!
answered 5 hours ago
Bram28Bram28
62.6k44793
$endgroup$
This is a common 'mistake': to Distribute when you should really 'Un-Distribute'. That is, you can see:
$(p land neg q) lor (p land q)$
as the result of applying Distribution to:
$p land (neg q lor q)$
But given that this is an equivalence, that means you can go the other way around as well (i.e. 'un-distribute' ... sometimes I call this 'reverse distribution' or 'factoring')
Note that from your last line we can do this as well:
$p land (neg q lor p) = (bot lor p) land (neg q lor p) = (bot land neg q) lor p = bot lor p =p$
Finally, the fact that $(p land q) lor (p land neg q)$ works out to just $p$ is such a common and handy equivalence that it has been given its own name:
Adjacency
$(p land q) lor (p land neg q) =p$
(and its dual form:) $(p lor q) land (p lor neg q)=p$
So, definitely put that one in your boolean algebra toolbox!
answered 5 hours ago
Bram28Bram28
62.6k44793
edited 4 hours ago
answered 5 hours ago
Bram28Bram28
62.6k44793
answered 5 hours ago
Bram28Bram28
62.6k44793
answered 5 hours ago
Bram28Bram28
62.6k44793
62.6k44793
$begingroup$
Ohhhh you're totally right, that went right over my head. Judging by what I did for this question, do you think I'll lose all the marks?
$endgroup$
– Nev
4 hours ago
1
$begingroup$
@nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :)
$endgroup$
– Bram28
4 hours ago
add a comment |
$begingroup$
Ohhhh you're totally right, that went right over my head. Judging by what I did for this question, do you think I'll lose all the marks?
$endgroup$
– Nev
4 hours ago
1
$begingroup$
@nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :)
$endgroup$
– Bram28
4 hours ago
$begingroup$
Ohhhh you're totally right, that went right over my head. Judging by what I did for this question, do you think I'll lose all the marks?
$endgroup$
– Nev
4 hours ago
$begingroup$
Ohhhh you're totally right, that went right over my head. Judging by what I did for this question, do you think I'll lose all the marks?
$endgroup$
– Nev
4 hours ago
1
1
$begingroup$
@nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :)
$endgroup$
– Bram28
4 hours ago
$begingroup$
@nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :)
$endgroup$
– Bram28
4 hours ago
add a comment |
$begingroup$
I'm going to use some shorthand notation: $pq$ for $p land q$, and $p + q$ for $p lor q$. Your proposition is $$p(neg(neg p + q)) + pq.$$ Distributing the negation on the left, we obtain $$p (neg (neg p + q)) + pq equiv pp(neg q) + pq.$$ Note that $pp equiv p$. This now gives us $$p(neg q) + pq.$$
We can "factor out" that $p$ to obtain $$p (neg q) + pq equiv p(neg q + q) equiv p,$$ and we're done.
answered 4 hours ago
rwboglrwbogl
1,007617
$endgroup$
$begingroup$
Yes I totally see that now, thanks! I really hope I get at least some partial marks. I was supposed to "undo" the distribution rather than distribute again
$endgroup$
– Nev
4 hours ago
add a comment |
$begingroup$
I'm going to use some shorthand notation: $pq$ for $p land q$, and $p + q$ for $p lor q$. Your proposition is $$p(neg(neg p + q)) + pq.$$ Distributing the negation on the left, we obtain $$p (neg (neg p + q)) + pq equiv pp(neg q) + pq.$$ Note that $pp equiv p$. This now gives us $$p(neg q) + pq.$$
We can "factor out" that $p$ to obtain $$p (neg q) + pq equiv p(neg q + q) equiv p,$$ and we're done.
answered 4 hours ago
rwboglrwbogl
1,007617
$endgroup$
$begingroup$
Yes I totally see that now, thanks! I really hope I get at least some partial marks. I was supposed to "undo" the distribution rather than distribute again
$endgroup$
– Nev
4 hours ago
add a comment |
$begingroup$
I'm going to use some shorthand notation: $pq$ for $p land q$, and $p + q$ for $p lor q$. Your proposition is $$p(neg(neg p + q)) + pq.$$ Distributing the negation on the left, we obtain $$p (neg (neg p + q)) + pq equiv pp(neg q) + pq.$$ Note that $pp equiv p$. This now gives us $$p(neg q) + pq.$$
We can "factor out" that $p$ to obtain $$p (neg q) + pq equiv p(neg q + q) equiv p,$$ and we're done.
answered 4 hours ago
rwboglrwbogl
1,007617
$endgroup$
I'm going to use some shorthand notation: $pq$ for $p land q$, and $p + q$ for $p lor q$. Your proposition is $$p(neg(neg p + q)) + pq.$$ Distributing the negation on the left, we obtain $$p (neg (neg p + q)) + pq equiv pp(neg q) + pq.$$ Note that $pp equiv p$. This now gives us $$p(neg q) + pq.$$
We can "factor out" that $p$ to obtain $$p (neg q) + pq equiv p(neg q + q) equiv p,$$ and we're done.
answered 4 hours ago
rwboglrwbogl
1,007617
answered 4 hours ago
rwboglrwbogl
1,007617
answered 4 hours ago
rwboglrwbogl
1,007617
answered 4 hours ago
rwboglrwbogl
1,007617
1,007617
$begingroup$
Yes I totally see that now, thanks! I really hope I get at least some partial marks. I was supposed to "undo" the distribution rather than distribute again
$endgroup$
– Nev
4 hours ago
add a comment |
$begingroup$
Yes I totally see that now, thanks! I really hope I get at least some partial marks. I was supposed to "undo" the distribution rather than distribute again
$endgroup$
– Nev
4 hours ago
$begingroup$
Yes I totally see that now, thanks! I really hope I get at least some partial marks. I was supposed to "undo" the distribution rather than distribute again
$endgroup$
– Nev
4 hours ago
$begingroup$
Yes I totally see that now, thanks! I really hope I get at least some partial marks. I was supposed to "undo" the distribution rather than distribute again
$endgroup$
– Nev
4 hours ago
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%2f3114498%2fsimplify-p%25e2%2588%25a7-%25c2%25ac%25c2%25acp-v-q-v-p-%25e2%2588%25a7-q-so-that-it-become-p-q-%25c2%25acp-or-%25c2%25acq%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
$begingroup$
By the way, $pland (neg q lor p)$ can be immediately simplified to $p$ by what is known as the absorption law. See for example math.stackexchange.com/questions/2421690/… for some further reading.
$endgroup$
– Minus One-Twelfth
2 hours ago