Mixing
How to convert formula to disjunctive normal form?
$begingroup$
Convert
$$((p wedge q) → r) wedge (¬(p wedge q) → r)$$
to DNF.
This is what I've already done:
$$((p wedge q) → r) wedge (¬(p wedge q) → r)$$
$$(¬(p wedge q) vee r) wedge ((p wedge q) vee r)$$
$$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$$
And from this point I'm not sure how to proceed. Help would be appreciated.
Sorry, but the last line was written badly (I think). It's fixed now.
discrete-mathematics propositional-calculus disjunctive-normal-form
edited Oct 19 '16 at 10:51
Rodrigo de Azevedo
13.1k41960
asked Nov 4 '12 at 16:49
user1242967user1242967
7452719
$endgroup$
add a comment |
$begingroup$
Convert
$$((p wedge q) → r) wedge (¬(p wedge q) → r)$$
to DNF.
This is what I've already done:
$$((p wedge q) → r) wedge (¬(p wedge q) → r)$$
$$(¬(p wedge q) vee r) wedge ((p wedge q) vee r)$$
$$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$$
And from this point I'm not sure how to proceed. Help would be appreciated.
Sorry, but the last line was written badly (I think). It's fixed now.
discrete-mathematics propositional-calculus disjunctive-normal-form
edited Oct 19 '16 at 10:51
Rodrigo de Azevedo
13.1k41960
asked Nov 4 '12 at 16:49
user1242967user1242967
7452719
$endgroup$
$begingroup$
It's really great you got as far as you did; thanks for showing what you've done.
$endgroup$
– Namaste
Nov 4 '12 at 17:10
add a comment |
$begingroup$
Convert
$$((p wedge q) → r) wedge (¬(p wedge q) → r)$$
to DNF.
This is what I've already done:
$$((p wedge q) → r) wedge (¬(p wedge q) → r)$$
$$(¬(p wedge q) vee r) wedge ((p wedge q) vee r)$$
$$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$$
And from this point I'm not sure how to proceed. Help would be appreciated.
Sorry, but the last line was written badly (I think). It's fixed now.
discrete-mathematics propositional-calculus disjunctive-normal-form
edited Oct 19 '16 at 10:51
Rodrigo de Azevedo
13.1k41960
asked Nov 4 '12 at 16:49
user1242967user1242967
7452719
$endgroup$
Convert
$$((p wedge q) → r) wedge (¬(p wedge q) → r)$$
to DNF.
This is what I've already done:
$$((p wedge q) → r) wedge (¬(p wedge q) → r)$$
$$(¬(p wedge q) vee r) wedge ((p wedge q) vee r)$$
$$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$$
And from this point I'm not sure how to proceed. Help would be appreciated.
Sorry, but the last line was written badly (I think). It's fixed now.
discrete-mathematics propositional-calculus disjunctive-normal-form
discrete-mathematics propositional-calculus disjunctive-normal-form
edited Oct 19 '16 at 10:51
Rodrigo de Azevedo
13.1k41960
asked Nov 4 '12 at 16:49
user1242967user1242967
7452719
edited Oct 19 '16 at 10:51
Rodrigo de Azevedo
13.1k41960
asked Nov 4 '12 at 16:49
user1242967user1242967
7452719
edited Oct 19 '16 at 10:51
Rodrigo de Azevedo
13.1k41960
edited Oct 19 '16 at 10:51
Rodrigo de Azevedo
13.1k41960
edited Oct 19 '16 at 10:51
Rodrigo de Azevedo
13.1k41960
13.1k41960
asked Nov 4 '12 at 16:49
user1242967user1242967
7452719
asked Nov 4 '12 at 16:49
user1242967user1242967
7452719
asked Nov 4 '12 at 16:49
user1242967user1242967
7452719
7452719
$begingroup$
It's really great you got as far as you did; thanks for showing what you've done.
$endgroup$
– Namaste
Nov 4 '12 at 17:10
add a comment |
$begingroup$
It's really great you got as far as you did; thanks for showing what you've done.
$endgroup$
– Namaste
Nov 4 '12 at 17:10
$begingroup$
It's really great you got as far as you did; thanks for showing what you've done.
$endgroup$
– Namaste
Nov 4 '12 at 17:10
$begingroup$
It's really great you got as far as you did; thanks for showing what you've done.
$endgroup$
– Namaste
Nov 4 '12 at 17:10
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You can continue by using Distributivity of the boolean algebra:
$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$
$ Leftrightarrow (¬p vee ¬q vee r) wedge ((p wedge q) vee r)$
Here we apply distributivity:
$ Leftrightarrow (¬p wedge p wedge q) vee (¬q wedge p wedge q) vee (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee (r wedge r)$
Formally, this is in disjunctive normal form now.
We could further simplify:
$ Leftrightarrow (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee r$
answered Nov 6 '12 at 17:44
user48415user48415
11613
$endgroup$
$begingroup$
Sorry for asking, but how did you use distributivity law to get the third line? All I can think of is to use this identity: a∧(b∨c)=(a∧b)∨(a∧c) to get this: ((¬p∨¬q∨r)∧(p∧q))∨((¬p∨¬q∨r)∧r)
$endgroup$
– user1242967
Nov 6 '12 at 18:39
$begingroup$
Here you use: (a∨b∨c)∧(d∨e)=(a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 18:59
3
$begingroup$
The above can be seen as follows: (a∨b∨c)∧(d∨e) = ((a∨b∨c)∧d) ∨ ((a∨b∨c)∧e) = (a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 19:06
$begingroup$
brother, how did you simplified further the last statement using disjunctive normal form
$endgroup$
– Humoyun
Jun 23 '16 at 4:07
add a comment |
$begingroup$
$$((p land q) to r) land (neg(p land q)to r) equiv (neg(p land q) lor r) land ((p land q) lor r)$$
using the distributive law
$$r lor (neg (p land q) land (p land q)) equiv r lor text{False} equiv r$$
because $s land neg s equiv text{False}$.
edited Oct 19 '16 at 11:53
Rodrigo de Azevedo
13.1k41960
answered Nov 10 '15 at 10:07
Renuka PiyumalRenuka Piyumal
112
$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%2f228969%2fhow-to-convert-formula-to-disjunctive-normal-form%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$
You can continue by using Distributivity of the boolean algebra:
$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$
$ Leftrightarrow (¬p vee ¬q vee r) wedge ((p wedge q) vee r)$
Here we apply distributivity:
$ Leftrightarrow (¬p wedge p wedge q) vee (¬q wedge p wedge q) vee (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee (r wedge r)$
Formally, this is in disjunctive normal form now.
We could further simplify:
$ Leftrightarrow (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee r$
answered Nov 6 '12 at 17:44
user48415user48415
11613
$endgroup$
$begingroup$
Sorry for asking, but how did you use distributivity law to get the third line? All I can think of is to use this identity: a∧(b∨c)=(a∧b)∨(a∧c) to get this: ((¬p∨¬q∨r)∧(p∧q))∨((¬p∨¬q∨r)∧r)
$endgroup$
– user1242967
Nov 6 '12 at 18:39
$begingroup$
Here you use: (a∨b∨c)∧(d∨e)=(a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 18:59
3
$begingroup$
The above can be seen as follows: (a∨b∨c)∧(d∨e) = ((a∨b∨c)∧d) ∨ ((a∨b∨c)∧e) = (a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 19:06
$begingroup$
brother, how did you simplified further the last statement using disjunctive normal form
$endgroup$
– Humoyun
Jun 23 '16 at 4:07
add a comment |
$begingroup$
You can continue by using Distributivity of the boolean algebra:
$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$
$ Leftrightarrow (¬p vee ¬q vee r) wedge ((p wedge q) vee r)$
Here we apply distributivity:
$ Leftrightarrow (¬p wedge p wedge q) vee (¬q wedge p wedge q) vee (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee (r wedge r)$
Formally, this is in disjunctive normal form now.
We could further simplify:
$ Leftrightarrow (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee r$
answered Nov 6 '12 at 17:44
user48415user48415
11613
$endgroup$
$begingroup$
Sorry for asking, but how did you use distributivity law to get the third line? All I can think of is to use this identity: a∧(b∨c)=(a∧b)∨(a∧c) to get this: ((¬p∨¬q∨r)∧(p∧q))∨((¬p∨¬q∨r)∧r)
$endgroup$
– user1242967
Nov 6 '12 at 18:39
$begingroup$
Here you use: (a∨b∨c)∧(d∨e)=(a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 18:59
3
$begingroup$
The above can be seen as follows: (a∨b∨c)∧(d∨e) = ((a∨b∨c)∧d) ∨ ((a∨b∨c)∧e) = (a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 19:06
$begingroup$
brother, how did you simplified further the last statement using disjunctive normal form
$endgroup$
– Humoyun
Jun 23 '16 at 4:07
add a comment |
$begingroup$
You can continue by using Distributivity of the boolean algebra:
$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$
$ Leftrightarrow (¬p vee ¬q vee r) wedge ((p wedge q) vee r)$
Here we apply distributivity:
$ Leftrightarrow (¬p wedge p wedge q) vee (¬q wedge p wedge q) vee (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee (r wedge r)$
Formally, this is in disjunctive normal form now.
We could further simplify:
$ Leftrightarrow (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee r$
answered Nov 6 '12 at 17:44
user48415user48415
11613
$endgroup$
You can continue by using Distributivity of the boolean algebra:
$((¬p vee ¬q) vee r) wedge ((p wedge q) vee r)$
$ Leftrightarrow (¬p vee ¬q vee r) wedge ((p wedge q) vee r)$
Here we apply distributivity:
$ Leftrightarrow (¬p wedge p wedge q) vee (¬q wedge p wedge q) vee (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee (r wedge r)$
Formally, this is in disjunctive normal form now.
We could further simplify:
$ Leftrightarrow (r wedge p wedge q) vee (¬p wedge r) vee (¬q wedge r) vee r$
answered Nov 6 '12 at 17:44
user48415user48415
11613
answered Nov 6 '12 at 17:44
user48415user48415
11613
answered Nov 6 '12 at 17:44
user48415user48415
11613
answered Nov 6 '12 at 17:44
user48415user48415
11613
11613
$begingroup$
Sorry for asking, but how did you use distributivity law to get the third line? All I can think of is to use this identity: a∧(b∨c)=(a∧b)∨(a∧c) to get this: ((¬p∨¬q∨r)∧(p∧q))∨((¬p∨¬q∨r)∧r)
$endgroup$
– user1242967
Nov 6 '12 at 18:39
$begingroup$
Here you use: (a∨b∨c)∧(d∨e)=(a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 18:59
3
$begingroup$
The above can be seen as follows: (a∨b∨c)∧(d∨e) = ((a∨b∨c)∧d) ∨ ((a∨b∨c)∧e) = (a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 19:06
$begingroup$
brother, how did you simplified further the last statement using disjunctive normal form
$endgroup$
– Humoyun
Jun 23 '16 at 4:07
add a comment |
$begingroup$
Sorry for asking, but how did you use distributivity law to get the third line? All I can think of is to use this identity: a∧(b∨c)=(a∧b)∨(a∧c) to get this: ((¬p∨¬q∨r)∧(p∧q))∨((¬p∨¬q∨r)∧r)
$endgroup$
– user1242967
Nov 6 '12 at 18:39
$begingroup$
Here you use: (a∨b∨c)∧(d∨e)=(a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 18:59
3
$begingroup$
The above can be seen as follows: (a∨b∨c)∧(d∨e) = ((a∨b∨c)∧d) ∨ ((a∨b∨c)∧e) = (a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 19:06
$begingroup$
brother, how did you simplified further the last statement using disjunctive normal form
$endgroup$
– Humoyun
Jun 23 '16 at 4:07
$begingroup$
Sorry for asking, but how did you use distributivity law to get the third line? All I can think of is to use this identity: a∧(b∨c)=(a∧b)∨(a∧c) to get this: ((¬p∨¬q∨r)∧(p∧q))∨((¬p∨¬q∨r)∧r)
$endgroup$
– user1242967
Nov 6 '12 at 18:39
$begingroup$
Sorry for asking, but how did you use distributivity law to get the third line? All I can think of is to use this identity: a∧(b∨c)=(a∧b)∨(a∧c) to get this: ((¬p∨¬q∨r)∧(p∧q))∨((¬p∨¬q∨r)∧r)
$endgroup$
– user1242967
Nov 6 '12 at 18:39
$begingroup$
Here you use: (a∨b∨c)∧(d∨e)=(a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 18:59
$begingroup$
Here you use: (a∨b∨c)∧(d∨e)=(a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 18:59
3
3
$begingroup$
The above can be seen as follows: (a∨b∨c)∧(d∨e) = ((a∨b∨c)∧d) ∨ ((a∨b∨c)∧e) = (a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 19:06
$begingroup$
The above can be seen as follows: (a∨b∨c)∧(d∨e) = ((a∨b∨c)∧d) ∨ ((a∨b∨c)∧e) = (a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e)
$endgroup$
– user48415
Nov 6 '12 at 19:06
$begingroup$
brother, how did you simplified further the last statement using disjunctive normal form
$endgroup$
– Humoyun
Jun 23 '16 at 4:07
$begingroup$
brother, how did you simplified further the last statement using disjunctive normal form
$endgroup$
– Humoyun
Jun 23 '16 at 4:07
add a comment |
$begingroup$
$$((p land q) to r) land (neg(p land q)to r) equiv (neg(p land q) lor r) land ((p land q) lor r)$$
using the distributive law
$$r lor (neg (p land q) land (p land q)) equiv r lor text{False} equiv r$$
because $s land neg s equiv text{False}$.
edited Oct 19 '16 at 11:53
Rodrigo de Azevedo
13.1k41960
answered Nov 10 '15 at 10:07
Renuka PiyumalRenuka Piyumal
112
$endgroup$
add a comment |
$begingroup$
$$((p land q) to r) land (neg(p land q)to r) equiv (neg(p land q) lor r) land ((p land q) lor r)$$
using the distributive law
$$r lor (neg (p land q) land (p land q)) equiv r lor text{False} equiv r$$
because $s land neg s equiv text{False}$.
edited Oct 19 '16 at 11:53
Rodrigo de Azevedo
13.1k41960
answered Nov 10 '15 at 10:07
Renuka PiyumalRenuka Piyumal
112
$endgroup$
add a comment |
$begingroup$
$$((p land q) to r) land (neg(p land q)to r) equiv (neg(p land q) lor r) land ((p land q) lor r)$$
using the distributive law
$$r lor (neg (p land q) land (p land q)) equiv r lor text{False} equiv r$$
because $s land neg s equiv text{False}$.
edited Oct 19 '16 at 11:53
Rodrigo de Azevedo
13.1k41960
answered Nov 10 '15 at 10:07
Renuka PiyumalRenuka Piyumal
112
$endgroup$
$$((p land q) to r) land (neg(p land q)to r) equiv (neg(p land q) lor r) land ((p land q) lor r)$$
using the distributive law
$$r lor (neg (p land q) land (p land q)) equiv r lor text{False} equiv r$$
because $s land neg s equiv text{False}$.
edited Oct 19 '16 at 11:53
Rodrigo de Azevedo
13.1k41960
answered Nov 10 '15 at 10:07
Renuka PiyumalRenuka Piyumal
112
edited Oct 19 '16 at 11:53
Rodrigo de Azevedo
13.1k41960
edited Oct 19 '16 at 11:53
Rodrigo de Azevedo
13.1k41960
edited Oct 19 '16 at 11:53
Rodrigo de Azevedo
13.1k41960
13.1k41960
answered Nov 10 '15 at 10:07
Renuka PiyumalRenuka Piyumal
112
answered Nov 10 '15 at 10:07
Renuka PiyumalRenuka Piyumal
112
answered Nov 10 '15 at 10:07
Renuka PiyumalRenuka Piyumal
112
112
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%2f228969%2fhow-to-convert-formula-to-disjunctive-normal-form%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$
It's really great you got as far as you did; thanks for showing what you've done.
$endgroup$
– Namaste
Nov 4 '12 at 17:10