Help with logical equivalence/proving not a contradiction
$begingroup$
The question is this:
Demonstrate using logical equivalences that $(p → q) ∧ (p → ¬q)$ is not
a contradiction. Identify all logical equivalences by name.
So far, I have
$(p → q) land (p → ¬q)$
a. $(¬plor q) land (¬plor¬q)$
b. $¬(¬plor q) lor(¬(¬plor¬q)$
c. $( pland¬q) lor (p lor q)$
I can't figure out where to go from here. Any help would be appreciated.
discrete-mathematics logic propositional-calculus
edited Jan 14 at 9:58
Mostafa Ayaz
17.1k31039
asked Jan 14 at 1:05
Keith ReynoldsKeith Reynolds
62
$endgroup$
add a comment |
$begingroup$
The question is this:
Demonstrate using logical equivalences that $(p → q) ∧ (p → ¬q)$ is not
a contradiction. Identify all logical equivalences by name.
So far, I have
$(p → q) land (p → ¬q)$
a. $(¬plor q) land (¬plor¬q)$
b. $¬(¬plor q) lor(¬(¬plor¬q)$
c. $( pland¬q) lor (p lor q)$
I can't figure out where to go from here. Any help would be appreciated.
discrete-mathematics logic propositional-calculus
edited Jan 14 at 9:58
Mostafa Ayaz
17.1k31039
asked Jan 14 at 1:05
Keith ReynoldsKeith Reynolds
62
$endgroup$
add a comment |
$begingroup$
The question is this:
Demonstrate using logical equivalences that $(p → q) ∧ (p → ¬q)$ is not
a contradiction. Identify all logical equivalences by name.
So far, I have
$(p → q) land (p → ¬q)$
a. $(¬plor q) land (¬plor¬q)$
b. $¬(¬plor q) lor(¬(¬plor¬q)$
c. $( pland¬q) lor (p lor q)$
I can't figure out where to go from here. Any help would be appreciated.
discrete-mathematics logic propositional-calculus
edited Jan 14 at 9:58
Mostafa Ayaz
17.1k31039
asked Jan 14 at 1:05
Keith ReynoldsKeith Reynolds
62
$endgroup$
The question is this:
Demonstrate using logical equivalences that $(p → q) ∧ (p → ¬q)$ is not
a contradiction. Identify all logical equivalences by name.
So far, I have
$(p → q) land (p → ¬q)$
a. $(¬plor q) land (¬plor¬q)$
b. $¬(¬plor q) lor(¬(¬plor¬q)$
c. $( pland¬q) lor (p lor q)$
I can't figure out where to go from here. Any help would be appreciated.
discrete-mathematics logic propositional-calculus
discrete-mathematics logic propositional-calculus
edited Jan 14 at 9:58
Mostafa Ayaz
17.1k31039
asked Jan 14 at 1:05
Keith ReynoldsKeith Reynolds
62
edited Jan 14 at 9:58
Mostafa Ayaz
17.1k31039
asked Jan 14 at 1:05
Keith ReynoldsKeith Reynolds
62
edited Jan 14 at 9:58
Mostafa Ayaz
17.1k31039
edited Jan 14 at 9:58
Mostafa Ayaz
17.1k31039
edited Jan 14 at 9:58
Mostafa Ayaz
17.1k31039
17.1k31039
asked Jan 14 at 1:05
Keith ReynoldsKeith Reynolds
62
asked Jan 14 at 1:05
Keith ReynoldsKeith Reynolds
62
asked Jan 14 at 1:05
Keith ReynoldsKeith Reynolds
62
62
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
It is not a contradiction becauss it is true when p is false.
Truth tables show this quickly.
a. perhaps is the best for showing that.
a. is equivalent to: (not p) or (q and not q);
which in turn is equivalent to; not p.
So there's the answer - to show the orginal statement is
equivalent to: not p.
Little surprise, as the orginal statement is basically
proof by contradiction.
answered Jan 14 at 3:14
William ElliotWilliam Elliot
8,7552820
$endgroup$
add a comment |
$begingroup$
From :
a) $(¬p lor q) land (¬p lor ¬q)$
we have to apply the Distributive law to get :
b) $lnot p lor (q land lnot q)$.
Now we use the equivalence (often called : Negation law) : $(alpha land lnot alpha) equiv text F$ to get :
c) $lnot p lor text F$.
Finally, we use the equivalence (often called : Identity law) : $alpha lor text F equiv alpha$ to conclude with :
d) $lnot p$
that is not a contradiction.
answered Jan 14 at 7:10
Mauro ALLEGRANZAMauro ALLEGRANZA
67.3k449115
$endgroup$
add a comment |
$begingroup$
An easy way to say that is: since $p$ concludes $q$ and $lnot q$, if it holds true then two controversy statements hold true which is a contradiction, but if $lnot p$ is true, the contradiction is removed.
In a more formal way $$(pto q)land (pto lnot q)iff pto (qland lnot q)iff pto 0iff lnot pto 1$$which means that $lnot p$ is true.
answered Jan 14 at 10:03
Mostafa AyazMostafa Ayaz
17.1k31039
$endgroup$
$begingroup$
Are you missing a $p$ here?
$endgroup$
– Max Herrmann
Jan 14 at 11:19
$begingroup$
Where do you mean I'm missing?
$endgroup$
– Mostafa Ayaz
Jan 14 at 14:35
$begingroup$
(...), but if $neg$ is true, (...)
$endgroup$
– Max Herrmann
Jan 14 at 15:37
$begingroup$
Thank you. Nice look through my answer :)
$endgroup$
– Mostafa Ayaz
Jan 14 at 15:40
add a comment |
$begingroup$
Just an add-on to William Elliot's answer:
$$
begin{array}{c|c|c|c|c}
p & q & p rightarrow q & p rightarrow neg q & (p rightarrow q) wedge (p rightarrow neg q) \ hline
0 & 0 & 1 & 1 & 1 \
0 & 1 & 1 & 1 & 1 \
1 & 0 & 0 & 1 & 0 \
1 & 1 & 1 & 0 & 0
end{array}
$$
answered Jan 14 at 7:30
Max HerrmannMax Herrmann
724419
$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%2f3072740%2fhelp-with-logical-equivalence-proving-not-a-contradiction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It is not a contradiction becauss it is true when p is false.
Truth tables show this quickly.
a. perhaps is the best for showing that.
a. is equivalent to: (not p) or (q and not q);
which in turn is equivalent to; not p.
So there's the answer - to show the orginal statement is
equivalent to: not p.
Little surprise, as the orginal statement is basically
proof by contradiction.
answered Jan 14 at 3:14
William ElliotWilliam Elliot
8,7552820
$endgroup$
add a comment |
$begingroup$
It is not a contradiction becauss it is true when p is false.
Truth tables show this quickly.
a. perhaps is the best for showing that.
a. is equivalent to: (not p) or (q and not q);
which in turn is equivalent to; not p.
So there's the answer - to show the orginal statement is
equivalent to: not p.
Little surprise, as the orginal statement is basically
proof by contradiction.
answered Jan 14 at 3:14
William ElliotWilliam Elliot
8,7552820
$endgroup$
add a comment |
$begingroup$
It is not a contradiction becauss it is true when p is false.
Truth tables show this quickly.
a. perhaps is the best for showing that.
a. is equivalent to: (not p) or (q and not q);
which in turn is equivalent to; not p.
So there's the answer - to show the orginal statement is
equivalent to: not p.
Little surprise, as the orginal statement is basically
proof by contradiction.
answered Jan 14 at 3:14
William ElliotWilliam Elliot
8,7552820
$endgroup$
It is not a contradiction becauss it is true when p is false.
Truth tables show this quickly.
a. perhaps is the best for showing that.
a. is equivalent to: (not p) or (q and not q);
which in turn is equivalent to; not p.
So there's the answer - to show the orginal statement is
equivalent to: not p.
Little surprise, as the orginal statement is basically
proof by contradiction.
answered Jan 14 at 3:14
William ElliotWilliam Elliot
8,7552820
answered Jan 14 at 3:14
William ElliotWilliam Elliot
8,7552820
answered Jan 14 at 3:14
William ElliotWilliam Elliot
8,7552820
answered Jan 14 at 3:14
William ElliotWilliam Elliot
8,7552820
8,7552820
add a comment |
add a comment |
$begingroup$
From :
a) $(¬p lor q) land (¬p lor ¬q)$
we have to apply the Distributive law to get :
b) $lnot p lor (q land lnot q)$.
Now we use the equivalence (often called : Negation law) : $(alpha land lnot alpha) equiv text F$ to get :
c) $lnot p lor text F$.
Finally, we use the equivalence (often called : Identity law) : $alpha lor text F equiv alpha$ to conclude with :
d) $lnot p$
that is not a contradiction.
answered Jan 14 at 7:10
Mauro ALLEGRANZAMauro ALLEGRANZA
67.3k449115
$endgroup$
add a comment |
$begingroup$
From :
a) $(¬p lor q) land (¬p lor ¬q)$
we have to apply the Distributive law to get :
b) $lnot p lor (q land lnot q)$.
Now we use the equivalence (often called : Negation law) : $(alpha land lnot alpha) equiv text F$ to get :
c) $lnot p lor text F$.
Finally, we use the equivalence (often called : Identity law) : $alpha lor text F equiv alpha$ to conclude with :
d) $lnot p$
that is not a contradiction.
answered Jan 14 at 7:10
Mauro ALLEGRANZAMauro ALLEGRANZA
67.3k449115
$endgroup$
add a comment |
$begingroup$
From :
a) $(¬p lor q) land (¬p lor ¬q)$
we have to apply the Distributive law to get :
b) $lnot p lor (q land lnot q)$.
Now we use the equivalence (often called : Negation law) : $(alpha land lnot alpha) equiv text F$ to get :
c) $lnot p lor text F$.
Finally, we use the equivalence (often called : Identity law) : $alpha lor text F equiv alpha$ to conclude with :
d) $lnot p$
that is not a contradiction.
answered Jan 14 at 7:10
Mauro ALLEGRANZAMauro ALLEGRANZA
67.3k449115
$endgroup$
From :
a) $(¬p lor q) land (¬p lor ¬q)$
we have to apply the Distributive law to get :
b) $lnot p lor (q land lnot q)$.
Now we use the equivalence (often called : Negation law) : $(alpha land lnot alpha) equiv text F$ to get :
c) $lnot p lor text F$.
Finally, we use the equivalence (often called : Identity law) : $alpha lor text F equiv alpha$ to conclude with :
d) $lnot p$
that is not a contradiction.
answered Jan 14 at 7:10
Mauro ALLEGRANZAMauro ALLEGRANZA
67.3k449115
edited Jan 14 at 8:51
answered Jan 14 at 7:10
Mauro ALLEGRANZAMauro ALLEGRANZA
67.3k449115
answered Jan 14 at 7:10
Mauro ALLEGRANZAMauro ALLEGRANZA
67.3k449115
answered Jan 14 at 7:10
Mauro ALLEGRANZAMauro ALLEGRANZA
67.3k449115
67.3k449115
add a comment |
add a comment |
$begingroup$
An easy way to say that is: since $p$ concludes $q$ and $lnot q$, if it holds true then two controversy statements hold true which is a contradiction, but if $lnot p$ is true, the contradiction is removed.
In a more formal way $$(pto q)land (pto lnot q)iff pto (qland lnot q)iff pto 0iff lnot pto 1$$which means that $lnot p$ is true.
answered Jan 14 at 10:03
Mostafa AyazMostafa Ayaz
17.1k31039
$endgroup$
$begingroup$
Are you missing a $p$ here?
$endgroup$
– Max Herrmann
Jan 14 at 11:19
$begingroup$
Where do you mean I'm missing?
$endgroup$
– Mostafa Ayaz
Jan 14 at 14:35
$begingroup$
(...), but if $neg$ is true, (...)
$endgroup$
– Max Herrmann
Jan 14 at 15:37
$begingroup$
Thank you. Nice look through my answer :)
$endgroup$
– Mostafa Ayaz
Jan 14 at 15:40
add a comment |
$begingroup$
An easy way to say that is: since $p$ concludes $q$ and $lnot q$, if it holds true then two controversy statements hold true which is a contradiction, but if $lnot p$ is true, the contradiction is removed.
In a more formal way $$(pto q)land (pto lnot q)iff pto (qland lnot q)iff pto 0iff lnot pto 1$$which means that $lnot p$ is true.
answered Jan 14 at 10:03
Mostafa AyazMostafa Ayaz
17.1k31039
$endgroup$
$begingroup$
Are you missing a $p$ here?
$endgroup$
– Max Herrmann
Jan 14 at 11:19
$begingroup$
Where do you mean I'm missing?
$endgroup$
– Mostafa Ayaz
Jan 14 at 14:35
$begingroup$
(...), but if $neg$ is true, (...)
$endgroup$
– Max Herrmann
Jan 14 at 15:37
$begingroup$
Thank you. Nice look through my answer :)
$endgroup$
– Mostafa Ayaz
Jan 14 at 15:40
add a comment |
$begingroup$
An easy way to say that is: since $p$ concludes $q$ and $lnot q$, if it holds true then two controversy statements hold true which is a contradiction, but if $lnot p$ is true, the contradiction is removed.
In a more formal way $$(pto q)land (pto lnot q)iff pto (qland lnot q)iff pto 0iff lnot pto 1$$which means that $lnot p$ is true.
answered Jan 14 at 10:03
Mostafa AyazMostafa Ayaz
17.1k31039
$endgroup$
An easy way to say that is: since $p$ concludes $q$ and $lnot q$, if it holds true then two controversy statements hold true which is a contradiction, but if $lnot p$ is true, the contradiction is removed.
In a more formal way $$(pto q)land (pto lnot q)iff pto (qland lnot q)iff pto 0iff lnot pto 1$$which means that $lnot p$ is true.
answered Jan 14 at 10:03
Mostafa AyazMostafa Ayaz
17.1k31039
edited Jan 14 at 15:39
answered Jan 14 at 10:03
Mostafa AyazMostafa Ayaz
17.1k31039
answered Jan 14 at 10:03
Mostafa AyazMostafa Ayaz
17.1k31039
answered Jan 14 at 10:03
Mostafa AyazMostafa Ayaz
17.1k31039
17.1k31039
$begingroup$
Are you missing a $p$ here?
$endgroup$
– Max Herrmann
Jan 14 at 11:19
$begingroup$
Where do you mean I'm missing?
$endgroup$
– Mostafa Ayaz
Jan 14 at 14:35
$begingroup$
(...), but if $neg$ is true, (...)
$endgroup$
– Max Herrmann
Jan 14 at 15:37
$begingroup$
Thank you. Nice look through my answer :)
$endgroup$
– Mostafa Ayaz
Jan 14 at 15:40
add a comment |
$begingroup$
Are you missing a $p$ here?
$endgroup$
– Max Herrmann
Jan 14 at 11:19
$begingroup$
Where do you mean I'm missing?
$endgroup$
– Mostafa Ayaz
Jan 14 at 14:35
$begingroup$
(...), but if $neg$ is true, (...)
$endgroup$
– Max Herrmann
Jan 14 at 15:37
$begingroup$
Thank you. Nice look through my answer :)
$endgroup$
– Mostafa Ayaz
Jan 14 at 15:40
$begingroup$
Are you missing a $p$ here?
$endgroup$
– Max Herrmann
Jan 14 at 11:19
$begingroup$
Are you missing a $p$ here?
$endgroup$
– Max Herrmann
Jan 14 at 11:19
$begingroup$
Where do you mean I'm missing?
$endgroup$
– Mostafa Ayaz
Jan 14 at 14:35
$begingroup$
Where do you mean I'm missing?
$endgroup$
– Mostafa Ayaz
Jan 14 at 14:35
$begingroup$
(...), but if $neg$ is true, (...)
$endgroup$
– Max Herrmann
Jan 14 at 15:37
$begingroup$
(...), but if $neg$ is true, (...)
$endgroup$
– Max Herrmann
Jan 14 at 15:37
$begingroup$
Thank you. Nice look through my answer :)
$endgroup$
– Mostafa Ayaz
Jan 14 at 15:40
$begingroup$
Thank you. Nice look through my answer :)
$endgroup$
– Mostafa Ayaz
Jan 14 at 15:40
add a comment |
$begingroup$
Just an add-on to William Elliot's answer:
$$
begin{array}{c|c|c|c|c}
p & q & p rightarrow q & p rightarrow neg q & (p rightarrow q) wedge (p rightarrow neg q) \ hline
0 & 0 & 1 & 1 & 1 \
0 & 1 & 1 & 1 & 1 \
1 & 0 & 0 & 1 & 0 \
1 & 1 & 1 & 0 & 0
end{array}
$$
answered Jan 14 at 7:30
Max HerrmannMax Herrmann
724419
$endgroup$
add a comment |
$begingroup$
Just an add-on to William Elliot's answer:
$$
begin{array}{c|c|c|c|c}
p & q & p rightarrow q & p rightarrow neg q & (p rightarrow q) wedge (p rightarrow neg q) \ hline
0 & 0 & 1 & 1 & 1 \
0 & 1 & 1 & 1 & 1 \
1 & 0 & 0 & 1 & 0 \
1 & 1 & 1 & 0 & 0
end{array}
$$
answered Jan 14 at 7:30
Max HerrmannMax Herrmann
724419
$endgroup$
add a comment |
$begingroup$
Just an add-on to William Elliot's answer:
$$
begin{array}{c|c|c|c|c}
p & q & p rightarrow q & p rightarrow neg q & (p rightarrow q) wedge (p rightarrow neg q) \ hline
0 & 0 & 1 & 1 & 1 \
0 & 1 & 1 & 1 & 1 \
1 & 0 & 0 & 1 & 0 \
1 & 1 & 1 & 0 & 0
end{array}
$$
answered Jan 14 at 7:30
Max HerrmannMax Herrmann
724419
$endgroup$
Just an add-on to William Elliot's answer:
$$
begin{array}{c|c|c|c|c}
p & q & p rightarrow q & p rightarrow neg q & (p rightarrow q) wedge (p rightarrow neg q) \ hline
0 & 0 & 1 & 1 & 1 \
0 & 1 & 1 & 1 & 1 \
1 & 0 & 0 & 1 & 0 \
1 & 1 & 1 & 0 & 0
end{array}
$$
answered Jan 14 at 7:30
Max HerrmannMax Herrmann
724419
answered Jan 14 at 7:30
Max HerrmannMax Herrmann
724419
answered Jan 14 at 7:30
Max HerrmannMax Herrmann
724419
answered Jan 14 at 7:30
Max HerrmannMax Herrmann
724419
724419
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%2f3072740%2fhelp-with-logical-equivalence-proving-not-a-contradiction%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
