how to use Shannon-expansion to rewrite Logic to Normal if-then-else Form (INF)
$begingroup$
I'm taking a (online) course in logic, one goal of the course is to rewrite logic expressions to if-then-else form, using shannon-expansion, the following is a text-book example:
we got:
(p ∨ ¬r) → p
this can be rewriten using a Shannon-expansion to Normal if-then-else form (INF)
and the solution looks like this when done so:
(p ∨ ¬r) → p
p → ((⊺ ∨ ¬r) → ⊺); ((┴ ∨ ¬r) → ┴)
p → (r → ((⊺ ∨ ¬⊺) → ⊺); ((⊺ ∨ ¬┴) → ⊺));
(r → ((┴ ∨ ¬⊺) → ┴); ((┴ ∨ ¬┴) → ┴)))
p → (r → (⊺ → ⊺); (⊺ → ⊺)); (r → (┴ → ┴); (⊺ → ┴))
p → (r → ⊺; ⊺); (r → ⊺;┴ )
p → ⊺; (r → ⊺;┴ )
I'm having a hard time understanding exactly what is happening here and can't rly find any other examples or good explanations of this, so if there is some one that could explain this answer to me that would be great!
logic propositional-calculus boolean-algebra
asked Dec 9 '18 at 20:48
user10483669user10483669
83
$endgroup$
add a comment |
$begingroup$
I'm taking a (online) course in logic, one goal of the course is to rewrite logic expressions to if-then-else form, using shannon-expansion, the following is a text-book example:
we got:
(p ∨ ¬r) → p
this can be rewriten using a Shannon-expansion to Normal if-then-else form (INF)
and the solution looks like this when done so:
(p ∨ ¬r) → p
p → ((⊺ ∨ ¬r) → ⊺); ((┴ ∨ ¬r) → ┴)
p → (r → ((⊺ ∨ ¬⊺) → ⊺); ((⊺ ∨ ¬┴) → ⊺));
(r → ((┴ ∨ ¬⊺) → ┴); ((┴ ∨ ¬┴) → ┴)))
p → (r → (⊺ → ⊺); (⊺ → ⊺)); (r → (┴ → ┴); (⊺ → ┴))
p → (r → ⊺; ⊺); (r → ⊺;┴ )
p → ⊺; (r → ⊺;┴ )
I'm having a hard time understanding exactly what is happening here and can't rly find any other examples or good explanations of this, so if there is some one that could explain this answer to me that would be great!
logic propositional-calculus boolean-algebra
asked Dec 9 '18 at 20:48
user10483669user10483669
83
$endgroup$
$begingroup$
It seems that some of the characters from your unspecified source did not survive your cutting and pasting. For instance, what missing character precedes the last close parenthesis on the second line of your large display?
$endgroup$
– Eric Towers
Dec 9 '18 at 20:56
$begingroup$
@EricTowers thats correct!, fixed it!
$endgroup$
– user10483669
Dec 9 '18 at 21:05
add a comment |
$begingroup$
I'm taking a (online) course in logic, one goal of the course is to rewrite logic expressions to if-then-else form, using shannon-expansion, the following is a text-book example:
we got:
(p ∨ ¬r) → p
this can be rewriten using a Shannon-expansion to Normal if-then-else form (INF)
and the solution looks like this when done so:
(p ∨ ¬r) → p
p → ((⊺ ∨ ¬r) → ⊺); ((┴ ∨ ¬r) → ┴)
p → (r → ((⊺ ∨ ¬⊺) → ⊺); ((⊺ ∨ ¬┴) → ⊺));
(r → ((┴ ∨ ¬⊺) → ┴); ((┴ ∨ ¬┴) → ┴)))
p → (r → (⊺ → ⊺); (⊺ → ⊺)); (r → (┴ → ┴); (⊺ → ┴))
p → (r → ⊺; ⊺); (r → ⊺;┴ )
p → ⊺; (r → ⊺;┴ )
I'm having a hard time understanding exactly what is happening here and can't rly find any other examples or good explanations of this, so if there is some one that could explain this answer to me that would be great!
logic propositional-calculus boolean-algebra
asked Dec 9 '18 at 20:48
user10483669user10483669
83
$endgroup$
I'm taking a (online) course in logic, one goal of the course is to rewrite logic expressions to if-then-else form, using shannon-expansion, the following is a text-book example:
we got:
(p ∨ ¬r) → p
this can be rewriten using a Shannon-expansion to Normal if-then-else form (INF)
and the solution looks like this when done so:
(p ∨ ¬r) → p
p → ((⊺ ∨ ¬r) → ⊺); ((┴ ∨ ¬r) → ┴)
p → (r → ((⊺ ∨ ¬⊺) → ⊺); ((⊺ ∨ ¬┴) → ⊺));
(r → ((┴ ∨ ¬⊺) → ┴); ((┴ ∨ ¬┴) → ┴)))
p → (r → (⊺ → ⊺); (⊺ → ⊺)); (r → (┴ → ┴); (⊺ → ┴))
p → (r → ⊺; ⊺); (r → ⊺;┴ )
p → ⊺; (r → ⊺;┴ )
I'm having a hard time understanding exactly what is happening here and can't rly find any other examples or good explanations of this, so if there is some one that could explain this answer to me that would be great!
logic propositional-calculus boolean-algebra
logic propositional-calculus boolean-algebra
asked Dec 9 '18 at 20:48
user10483669user10483669
83
asked Dec 9 '18 at 20:48
user10483669user10483669
83
edited Dec 9 '18 at 21:04
user10483669
asked Dec 9 '18 at 20:48
user10483669user10483669
83
asked Dec 9 '18 at 20:48
user10483669user10483669
83
asked Dec 9 '18 at 20:48
user10483669user10483669
83
83
$begingroup$
It seems that some of the characters from your unspecified source did not survive your cutting and pasting. For instance, what missing character precedes the last close parenthesis on the second line of your large display?
$endgroup$
– Eric Towers
Dec 9 '18 at 20:56
$begingroup$
@EricTowers thats correct!, fixed it!
$endgroup$
– user10483669
Dec 9 '18 at 21:05
add a comment |
$begingroup$
It seems that some of the characters from your unspecified source did not survive your cutting and pasting. For instance, what missing character precedes the last close parenthesis on the second line of your large display?
$endgroup$
– Eric Towers
Dec 9 '18 at 20:56
$begingroup$
@EricTowers thats correct!, fixed it!
$endgroup$
– user10483669
Dec 9 '18 at 21:05
$begingroup$
It seems that some of the characters from your unspecified source did not survive your cutting and pasting. For instance, what missing character precedes the last close parenthesis on the second line of your large display?
$endgroup$
– Eric Towers
Dec 9 '18 at 20:56
$begingroup$
It seems that some of the characters from your unspecified source did not survive your cutting and pasting. For instance, what missing character precedes the last close parenthesis on the second line of your large display?
$endgroup$
– Eric Towers
Dec 9 '18 at 20:56
$begingroup$
@EricTowers thats correct!, fixed it!
$endgroup$
– user10483669
Dec 9 '18 at 21:05
$begingroup$
@EricTowers thats correct!, fixed it!
$endgroup$
– user10483669
Dec 9 '18 at 21:05
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
In general, the expression
$$prightarrow (expression_1;expression_2)$$
is understood as:
'if $p$ is true, then $expression_1$ holds, otherwise $expression_2$ holds'
So, for example, given the initial expression
$$(p lor neg r) rightarrow p$$
we can say that if $p$ is true, then the expression evaluates to
$$(top lor neg r) rightarrow top$$
while if $p$ is false, then it evaluates to:
$$(bot lor neg r) rightarrow bot$$
and therefore the original expression can be written as:
$$p rightarrow ((top lor neg r) rightarrow top ; (bot lor neg r) rightarrow bot)$$
and this is what you see on the second line.
And now just do the same for $r$
That is, if we expand the first half
$$(top lor neg r)rightarrow top $$, we get
$$(top lor neg top)rightarrow top $$
if $r$ is true, and:
$$(top lor neg bot)rightarrow top $$
if $r$ is false, and so this becomes:
$$r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) $$
while the second half becomes:
$$r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot) $$
meaning that we get:
$$p rightarrow (r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) ; r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot))$$
on line 3
And form this point on, it's just a matter of evaluating the 4 expressions you end up with. For example, the first expression
$$(top lor neg top)rightarrow top$$
works out to:
$$top rightarrow top$$
(this you see as the first expression on line 4) which itself works out to :
$$top$$
(and this you see as the first expression on line 5)
Finally, the expression $r rightarrow (top ; top)$ that is part of line 6 is being replaced by $top$ on line 7 since apparently it does not matter what $r$'s truth-value is.
answered Dec 9 '18 at 21:10
Bram28Bram28
61.6k44793
$endgroup$
$begingroup$
amazing answer!, if only the the book where this good.. Thank you sir!, making this an accepted answer!
$endgroup$
– user10483669
Dec 10 '18 at 0:04
$begingroup$
@user10483669 Glad I could help!
$endgroup$
– Bram28
Dec 10 '18 at 2:28
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%2f3032987%2fhow-to-use-shannon-expansion-to-rewrite-logic-to-normal-if-then-else-form-inf%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In general, the expression
$$prightarrow (expression_1;expression_2)$$
is understood as:
'if $p$ is true, then $expression_1$ holds, otherwise $expression_2$ holds'
So, for example, given the initial expression
$$(p lor neg r) rightarrow p$$
we can say that if $p$ is true, then the expression evaluates to
$$(top lor neg r) rightarrow top$$
while if $p$ is false, then it evaluates to:
$$(bot lor neg r) rightarrow bot$$
and therefore the original expression can be written as:
$$p rightarrow ((top lor neg r) rightarrow top ; (bot lor neg r) rightarrow bot)$$
and this is what you see on the second line.
And now just do the same for $r$
That is, if we expand the first half
$$(top lor neg r)rightarrow top $$, we get
$$(top lor neg top)rightarrow top $$
if $r$ is true, and:
$$(top lor neg bot)rightarrow top $$
if $r$ is false, and so this becomes:
$$r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) $$
while the second half becomes:
$$r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot) $$
meaning that we get:
$$p rightarrow (r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) ; r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot))$$
on line 3
And form this point on, it's just a matter of evaluating the 4 expressions you end up with. For example, the first expression
$$(top lor neg top)rightarrow top$$
works out to:
$$top rightarrow top$$
(this you see as the first expression on line 4) which itself works out to :
$$top$$
(and this you see as the first expression on line 5)
Finally, the expression $r rightarrow (top ; top)$ that is part of line 6 is being replaced by $top$ on line 7 since apparently it does not matter what $r$'s truth-value is.
answered Dec 9 '18 at 21:10
Bram28Bram28
61.6k44793
$endgroup$
$begingroup$
amazing answer!, if only the the book where this good.. Thank you sir!, making this an accepted answer!
$endgroup$
– user10483669
Dec 10 '18 at 0:04
$begingroup$
@user10483669 Glad I could help!
$endgroup$
– Bram28
Dec 10 '18 at 2:28
add a comment |
$begingroup$
In general, the expression
$$prightarrow (expression_1;expression_2)$$
is understood as:
'if $p$ is true, then $expression_1$ holds, otherwise $expression_2$ holds'
So, for example, given the initial expression
$$(p lor neg r) rightarrow p$$
we can say that if $p$ is true, then the expression evaluates to
$$(top lor neg r) rightarrow top$$
while if $p$ is false, then it evaluates to:
$$(bot lor neg r) rightarrow bot$$
and therefore the original expression can be written as:
$$p rightarrow ((top lor neg r) rightarrow top ; (bot lor neg r) rightarrow bot)$$
and this is what you see on the second line.
And now just do the same for $r$
That is, if we expand the first half
$$(top lor neg r)rightarrow top $$, we get
$$(top lor neg top)rightarrow top $$
if $r$ is true, and:
$$(top lor neg bot)rightarrow top $$
if $r$ is false, and so this becomes:
$$r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) $$
while the second half becomes:
$$r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot) $$
meaning that we get:
$$p rightarrow (r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) ; r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot))$$
on line 3
And form this point on, it's just a matter of evaluating the 4 expressions you end up with. For example, the first expression
$$(top lor neg top)rightarrow top$$
works out to:
$$top rightarrow top$$
(this you see as the first expression on line 4) which itself works out to :
$$top$$
(and this you see as the first expression on line 5)
Finally, the expression $r rightarrow (top ; top)$ that is part of line 6 is being replaced by $top$ on line 7 since apparently it does not matter what $r$'s truth-value is.
answered Dec 9 '18 at 21:10
Bram28Bram28
61.6k44793
$endgroup$
$begingroup$
amazing answer!, if only the the book where this good.. Thank you sir!, making this an accepted answer!
$endgroup$
– user10483669
Dec 10 '18 at 0:04
$begingroup$
@user10483669 Glad I could help!
$endgroup$
– Bram28
Dec 10 '18 at 2:28
add a comment |
$begingroup$
In general, the expression
$$prightarrow (expression_1;expression_2)$$
is understood as:
'if $p$ is true, then $expression_1$ holds, otherwise $expression_2$ holds'
So, for example, given the initial expression
$$(p lor neg r) rightarrow p$$
we can say that if $p$ is true, then the expression evaluates to
$$(top lor neg r) rightarrow top$$
while if $p$ is false, then it evaluates to:
$$(bot lor neg r) rightarrow bot$$
and therefore the original expression can be written as:
$$p rightarrow ((top lor neg r) rightarrow top ; (bot lor neg r) rightarrow bot)$$
and this is what you see on the second line.
And now just do the same for $r$
That is, if we expand the first half
$$(top lor neg r)rightarrow top $$, we get
$$(top lor neg top)rightarrow top $$
if $r$ is true, and:
$$(top lor neg bot)rightarrow top $$
if $r$ is false, and so this becomes:
$$r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) $$
while the second half becomes:
$$r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot) $$
meaning that we get:
$$p rightarrow (r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) ; r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot))$$
on line 3
And form this point on, it's just a matter of evaluating the 4 expressions you end up with. For example, the first expression
$$(top lor neg top)rightarrow top$$
works out to:
$$top rightarrow top$$
(this you see as the first expression on line 4) which itself works out to :
$$top$$
(and this you see as the first expression on line 5)
Finally, the expression $r rightarrow (top ; top)$ that is part of line 6 is being replaced by $top$ on line 7 since apparently it does not matter what $r$'s truth-value is.
answered Dec 9 '18 at 21:10
Bram28Bram28
61.6k44793
$endgroup$
In general, the expression
$$prightarrow (expression_1;expression_2)$$
is understood as:
'if $p$ is true, then $expression_1$ holds, otherwise $expression_2$ holds'
So, for example, given the initial expression
$$(p lor neg r) rightarrow p$$
we can say that if $p$ is true, then the expression evaluates to
$$(top lor neg r) rightarrow top$$
while if $p$ is false, then it evaluates to:
$$(bot lor neg r) rightarrow bot$$
and therefore the original expression can be written as:
$$p rightarrow ((top lor neg r) rightarrow top ; (bot lor neg r) rightarrow bot)$$
and this is what you see on the second line.
And now just do the same for $r$
That is, if we expand the first half
$$(top lor neg r)rightarrow top $$, we get
$$(top lor neg top)rightarrow top $$
if $r$ is true, and:
$$(top lor neg bot)rightarrow top $$
if $r$ is false, and so this becomes:
$$r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) $$
while the second half becomes:
$$r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot) $$
meaning that we get:
$$p rightarrow (r rightarrow ((top lor neg top)rightarrow top ; (top lor neg bot)rightarrow top) ; r rightarrow ((bot lor neg top)rightarrow bot ; (bot lor neg bot)rightarrow bot))$$
on line 3
And form this point on, it's just a matter of evaluating the 4 expressions you end up with. For example, the first expression
$$(top lor neg top)rightarrow top$$
works out to:
$$top rightarrow top$$
(this you see as the first expression on line 4) which itself works out to :
$$top$$
(and this you see as the first expression on line 5)
Finally, the expression $r rightarrow (top ; top)$ that is part of line 6 is being replaced by $top$ on line 7 since apparently it does not matter what $r$'s truth-value is.
answered Dec 9 '18 at 21:10
Bram28Bram28
61.6k44793
edited Dec 9 '18 at 21:20
answered Dec 9 '18 at 21:10
Bram28Bram28
61.6k44793
answered Dec 9 '18 at 21:10
Bram28Bram28
61.6k44793
answered Dec 9 '18 at 21:10
Bram28Bram28
61.6k44793
61.6k44793
$begingroup$
amazing answer!, if only the the book where this good.. Thank you sir!, making this an accepted answer!
$endgroup$
– user10483669
Dec 10 '18 at 0:04
$begingroup$
@user10483669 Glad I could help!
$endgroup$
– Bram28
Dec 10 '18 at 2:28
add a comment |
$begingroup$
amazing answer!, if only the the book where this good.. Thank you sir!, making this an accepted answer!
$endgroup$
– user10483669
Dec 10 '18 at 0:04
$begingroup$
@user10483669 Glad I could help!
$endgroup$
– Bram28
Dec 10 '18 at 2:28
$begingroup$
amazing answer!, if only the the book where this good.. Thank you sir!, making this an accepted answer!
$endgroup$
– user10483669
Dec 10 '18 at 0:04
$begingroup$
amazing answer!, if only the the book where this good.. Thank you sir!, making this an accepted answer!
$endgroup$
– user10483669
Dec 10 '18 at 0:04
$begingroup$
@user10483669 Glad I could help!
$endgroup$
– Bram28
Dec 10 '18 at 2:28
$begingroup$
@user10483669 Glad I could help!
$endgroup$
– Bram28
Dec 10 '18 at 2:28
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%2f3032987%2fhow-to-use-shannon-expansion-to-rewrite-logic-to-normal-if-then-else-form-inf%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 seems that some of the characters from your unspecified source did not survive your cutting and pasting. For instance, what missing character precedes the last close parenthesis on the second line of your large display?
$endgroup$
– Eric Towers
Dec 9 '18 at 20:56
$begingroup$
@EricTowers thats correct!, fixed it!
$endgroup$
– user10483669
Dec 9 '18 at 21:05