Mixing
Showing a conditional statement is a tautology without using a truth table.
$begingroup$
I wanted to show that [(p→q)∧(q→r)]→(p→r) is a tautology without using a truth table. This is what I got so far:
[(p→q)∧(q→r)] → (p→r)
=> ¬[(¬p v q) ∧ (¬q v r)] v (¬pvr) (logical equivalence)
=> [¬(¬p v q) v ¬(¬qvr)] v (¬pvr) (demorgan's law)
=> [(p ∧ ¬q) v (q∧¬r)] v (¬pvr) (demogran's law)
I can't seem to figure out what comes after this step. Can someone help me?
discrete-mathematics proof-verification logic
asked Jan 24 at 23:10
NevNev
305
$endgroup$
add a comment |
$begingroup$
I wanted to show that [(p→q)∧(q→r)]→(p→r) is a tautology without using a truth table. This is what I got so far:
[(p→q)∧(q→r)] → (p→r)
=> ¬[(¬p v q) ∧ (¬q v r)] v (¬pvr) (logical equivalence)
=> [¬(¬p v q) v ¬(¬qvr)] v (¬pvr) (demorgan's law)
=> [(p ∧ ¬q) v (q∧¬r)] v (¬pvr) (demogran's law)
I can't seem to figure out what comes after this step. Can someone help me?
discrete-mathematics proof-verification logic
asked Jan 24 at 23:10
NevNev
305
$endgroup$
add a comment |
$begingroup$
I wanted to show that [(p→q)∧(q→r)]→(p→r) is a tautology without using a truth table. This is what I got so far:
[(p→q)∧(q→r)] → (p→r)
=> ¬[(¬p v q) ∧ (¬q v r)] v (¬pvr) (logical equivalence)
=> [¬(¬p v q) v ¬(¬qvr)] v (¬pvr) (demorgan's law)
=> [(p ∧ ¬q) v (q∧¬r)] v (¬pvr) (demogran's law)
I can't seem to figure out what comes after this step. Can someone help me?
discrete-mathematics proof-verification logic
asked Jan 24 at 23:10
NevNev
305
$endgroup$
I wanted to show that [(p→q)∧(q→r)]→(p→r) is a tautology without using a truth table. This is what I got so far:
[(p→q)∧(q→r)] → (p→r)
=> ¬[(¬p v q) ∧ (¬q v r)] v (¬pvr) (logical equivalence)
=> [¬(¬p v q) v ¬(¬qvr)] v (¬pvr) (demorgan's law)
=> [(p ∧ ¬q) v (q∧¬r)] v (¬pvr) (demogran's law)
I can't seem to figure out what comes after this step. Can someone help me?
discrete-mathematics proof-verification logic
discrete-mathematics proof-verification logic
asked Jan 24 at 23:10
NevNev
305
asked Jan 24 at 23:10
NevNev
305
asked Jan 24 at 23:10
NevNev
305
asked Jan 24 at 23:10
NevNev
305
asked Jan 24 at 23:10
NevNev
305
305
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Notice that
$ [(p land neg q) lor (qland neg r)] lor (neg plor r)$
is one big disjunction, so you can drop parentheses:
$ (p land neg q) lor (qland neg r) lor neg plor r$
Now, if you have:
Reduction
$p lor (neg p land q) equiv p lor q$
then you can apply that:
$ (p land neg q) lor (qland neg r) lor neg plor r equiv$
$neg q lor q lor neg p lor r equiv$
$top lor neg p lor r equiv$
$top$
But if you don't have Reduction:
$ (p land neg q) lor (qland neg r) lor neg p lor r equiv$
$((p lor neg p) land (neg q lor neg p)) lor ((q lor r) land (neg r lor r)) equiv$
$(top land (neg q lor neg p)) lor ((q lor r) land top) equiv$
$neg q lor neg p lor q lor r$
$top lor neg p lor r equiv$
$top$
answered Jan 25 at 1:23
Bram28Bram28
63.8k44793
$endgroup$
$begingroup$
Thank you so much, makes a lot of sense now
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
@nev you're welcome!
$endgroup$
– Bram28
Jan 25 at 2:13
add a comment |
$begingroup$
Expand the expression $(p wedge neg q) vee (q wedge neg r)$ by distributing the $vee$ over the $wedge$:
begin{align*}
&(p wedge neg q) vee (q wedge neg r)\
&[(p wedge neg q) vee q] wedge [(p wedge neg q) vee neg r]\
&[(p vee q ) wedge (neg q vee q)] wedge [(p vee neg r ) wedge (neg q vee neg r)]\
&[(p vee q) wedge top ] wedge[(p vee neg r) wedge (neg q vee neg r)]\
&(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)].
end{align*}
Now overall we have ${(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)]}vee (neg p vee r)$. If we distribute the $vee$ over the $wedge$, we get $[(p vee q) vee ( neg p vee r)]wedge{[(p vee neg r) wedge (neg q vee neg r)]vee(neg p vee r)}$. Focusing on the first half, you can manipulate $(p vee q) vee ( neg p vee r)$ to get $top$ by shuffling parentheses around to get $(p vee neg p) vee (q vee r)$ (I'll leave that to you).
So we are left with $[(p vee neg r) wedge (neg q vee neg r)] vee (neg p vee r)$. Again let's distribute the $vee$ over the $wedge$:
begin{align*}
&[(p vee neg r) vee (neg p vee r)] wedge [(neg q vee neg r) vee (neg p vee r)].
end{align*}
Again both halves of this can be manipulated to get $top$.
answered Jan 24 at 23:41
kccukccu
10.6k11229
$endgroup$
add a comment |
$begingroup$
I can't seem to figure out what comes after this step. Can someone help me?
Yes.
$$begin{align}vdotsquad\iff&~big((p land lnot q) lor (qlandlnot r)big) lor (lnot plor r)
\[1ex]iff &~big(lnot plor (pland lnot q)big)lor big(rlor (lnot rland q)big)&quadtextsf{(Commutation and Association)}\vdotsquadend{align}$$
answered Jan 25 at 0:05
Graham KempGraham Kemp
86.8k43579
$endgroup$
add a comment |
$begingroup$
You can use Double Distribution to get
$$[(p lor q)land(q lor lnot q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
$q lor lnot q$ is a Tautology so this becomes
$$[(p lor q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
which by distribution is
$$[(p lor q)land[lnot rland(p lor lnot q)]]lor (lnot p lor r)$$
Association gives
$$[lnot r land [(p lor q)land(p lor lnot q)]]lor (lnot p lor r)$$
Distribution again gives
$$[lnot r land [p lor(q land lnot q)]]lor (lnot p lor r)$$
$q land lnot q$ is a contradiction so this becomes
$$(lnot r land p)lor (lnot p lor r)$$
Which by DeMorgan's Law is
$$(lnot r land p)lor lnot(lnot r land p)$$
Which is a tautology.
answered Jan 25 at 1:03
Erik ParkinsonErik Parkinson
1,17519
$endgroup$
$begingroup$
Thanks for the help!!
$endgroup$
– Nev
Jan 25 at 2:02
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%2f3086499%2fshowing-a-conditional-statement-is-a-tautology-without-using-a-truth-table%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$
Notice that
$ [(p land neg q) lor (qland neg r)] lor (neg plor r)$
is one big disjunction, so you can drop parentheses:
$ (p land neg q) lor (qland neg r) lor neg plor r$
Now, if you have:
Reduction
$p lor (neg p land q) equiv p lor q$
then you can apply that:
$ (p land neg q) lor (qland neg r) lor neg plor r equiv$
$neg q lor q lor neg p lor r equiv$
$top lor neg p lor r equiv$
$top$
But if you don't have Reduction:
$ (p land neg q) lor (qland neg r) lor neg p lor r equiv$
$((p lor neg p) land (neg q lor neg p)) lor ((q lor r) land (neg r lor r)) equiv$
$(top land (neg q lor neg p)) lor ((q lor r) land top) equiv$
$neg q lor neg p lor q lor r$
$top lor neg p lor r equiv$
$top$
answered Jan 25 at 1:23
Bram28Bram28
63.8k44793
$endgroup$
$begingroup$
Thank you so much, makes a lot of sense now
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
@nev you're welcome!
$endgroup$
– Bram28
Jan 25 at 2:13
add a comment |
$begingroup$
Notice that
$ [(p land neg q) lor (qland neg r)] lor (neg plor r)$
is one big disjunction, so you can drop parentheses:
$ (p land neg q) lor (qland neg r) lor neg plor r$
Now, if you have:
Reduction
$p lor (neg p land q) equiv p lor q$
then you can apply that:
$ (p land neg q) lor (qland neg r) lor neg plor r equiv$
$neg q lor q lor neg p lor r equiv$
$top lor neg p lor r equiv$
$top$
But if you don't have Reduction:
$ (p land neg q) lor (qland neg r) lor neg p lor r equiv$
$((p lor neg p) land (neg q lor neg p)) lor ((q lor r) land (neg r lor r)) equiv$
$(top land (neg q lor neg p)) lor ((q lor r) land top) equiv$
$neg q lor neg p lor q lor r$
$top lor neg p lor r equiv$
$top$
answered Jan 25 at 1:23
Bram28Bram28
63.8k44793
$endgroup$
$begingroup$
Thank you so much, makes a lot of sense now
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
@nev you're welcome!
$endgroup$
– Bram28
Jan 25 at 2:13
add a comment |
$begingroup$
Notice that
$ [(p land neg q) lor (qland neg r)] lor (neg plor r)$
is one big disjunction, so you can drop parentheses:
$ (p land neg q) lor (qland neg r) lor neg plor r$
Now, if you have:
Reduction
$p lor (neg p land q) equiv p lor q$
then you can apply that:
$ (p land neg q) lor (qland neg r) lor neg plor r equiv$
$neg q lor q lor neg p lor r equiv$
$top lor neg p lor r equiv$
$top$
But if you don't have Reduction:
$ (p land neg q) lor (qland neg r) lor neg p lor r equiv$
$((p lor neg p) land (neg q lor neg p)) lor ((q lor r) land (neg r lor r)) equiv$
$(top land (neg q lor neg p)) lor ((q lor r) land top) equiv$
$neg q lor neg p lor q lor r$
$top lor neg p lor r equiv$
$top$
answered Jan 25 at 1:23
Bram28Bram28
63.8k44793
$endgroup$
Notice that
$ [(p land neg q) lor (qland neg r)] lor (neg plor r)$
is one big disjunction, so you can drop parentheses:
$ (p land neg q) lor (qland neg r) lor neg plor r$
Now, if you have:
Reduction
$p lor (neg p land q) equiv p lor q$
then you can apply that:
$ (p land neg q) lor (qland neg r) lor neg plor r equiv$
$neg q lor q lor neg p lor r equiv$
$top lor neg p lor r equiv$
$top$
But if you don't have Reduction:
$ (p land neg q) lor (qland neg r) lor neg p lor r equiv$
$((p lor neg p) land (neg q lor neg p)) lor ((q lor r) land (neg r lor r)) equiv$
$(top land (neg q lor neg p)) lor ((q lor r) land top) equiv$
$neg q lor neg p lor q lor r$
$top lor neg p lor r equiv$
$top$
answered Jan 25 at 1:23
Bram28Bram28
63.8k44793
answered Jan 25 at 1:23
Bram28Bram28
63.8k44793
answered Jan 25 at 1:23
Bram28Bram28
63.8k44793
answered Jan 25 at 1:23
Bram28Bram28
63.8k44793
63.8k44793
$begingroup$
Thank you so much, makes a lot of sense now
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
@nev you're welcome!
$endgroup$
– Bram28
Jan 25 at 2:13
add a comment |
$begingroup$
Thank you so much, makes a lot of sense now
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
@nev you're welcome!
$endgroup$
– Bram28
Jan 25 at 2:13
$begingroup$
Thank you so much, makes a lot of sense now
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
Thank you so much, makes a lot of sense now
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
@nev you're welcome!
$endgroup$
– Bram28
Jan 25 at 2:13
$begingroup$
@nev you're welcome!
$endgroup$
– Bram28
Jan 25 at 2:13
add a comment |
$begingroup$
Expand the expression $(p wedge neg q) vee (q wedge neg r)$ by distributing the $vee$ over the $wedge$:
begin{align*}
&(p wedge neg q) vee (q wedge neg r)\
&[(p wedge neg q) vee q] wedge [(p wedge neg q) vee neg r]\
&[(p vee q ) wedge (neg q vee q)] wedge [(p vee neg r ) wedge (neg q vee neg r)]\
&[(p vee q) wedge top ] wedge[(p vee neg r) wedge (neg q vee neg r)]\
&(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)].
end{align*}
Now overall we have ${(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)]}vee (neg p vee r)$. If we distribute the $vee$ over the $wedge$, we get $[(p vee q) vee ( neg p vee r)]wedge{[(p vee neg r) wedge (neg q vee neg r)]vee(neg p vee r)}$. Focusing on the first half, you can manipulate $(p vee q) vee ( neg p vee r)$ to get $top$ by shuffling parentheses around to get $(p vee neg p) vee (q vee r)$ (I'll leave that to you).
So we are left with $[(p vee neg r) wedge (neg q vee neg r)] vee (neg p vee r)$. Again let's distribute the $vee$ over the $wedge$:
begin{align*}
&[(p vee neg r) vee (neg p vee r)] wedge [(neg q vee neg r) vee (neg p vee r)].
end{align*}
Again both halves of this can be manipulated to get $top$.
answered Jan 24 at 23:41
kccukccu
10.6k11229
$endgroup$
add a comment |
$begingroup$
Expand the expression $(p wedge neg q) vee (q wedge neg r)$ by distributing the $vee$ over the $wedge$:
begin{align*}
&(p wedge neg q) vee (q wedge neg r)\
&[(p wedge neg q) vee q] wedge [(p wedge neg q) vee neg r]\
&[(p vee q ) wedge (neg q vee q)] wedge [(p vee neg r ) wedge (neg q vee neg r)]\
&[(p vee q) wedge top ] wedge[(p vee neg r) wedge (neg q vee neg r)]\
&(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)].
end{align*}
Now overall we have ${(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)]}vee (neg p vee r)$. If we distribute the $vee$ over the $wedge$, we get $[(p vee q) vee ( neg p vee r)]wedge{[(p vee neg r) wedge (neg q vee neg r)]vee(neg p vee r)}$. Focusing on the first half, you can manipulate $(p vee q) vee ( neg p vee r)$ to get $top$ by shuffling parentheses around to get $(p vee neg p) vee (q vee r)$ (I'll leave that to you).
So we are left with $[(p vee neg r) wedge (neg q vee neg r)] vee (neg p vee r)$. Again let's distribute the $vee$ over the $wedge$:
begin{align*}
&[(p vee neg r) vee (neg p vee r)] wedge [(neg q vee neg r) vee (neg p vee r)].
end{align*}
Again both halves of this can be manipulated to get $top$.
answered Jan 24 at 23:41
kccukccu
10.6k11229
$endgroup$
add a comment |
$begingroup$
Expand the expression $(p wedge neg q) vee (q wedge neg r)$ by distributing the $vee$ over the $wedge$:
begin{align*}
&(p wedge neg q) vee (q wedge neg r)\
&[(p wedge neg q) vee q] wedge [(p wedge neg q) vee neg r]\
&[(p vee q ) wedge (neg q vee q)] wedge [(p vee neg r ) wedge (neg q vee neg r)]\
&[(p vee q) wedge top ] wedge[(p vee neg r) wedge (neg q vee neg r)]\
&(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)].
end{align*}
Now overall we have ${(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)]}vee (neg p vee r)$. If we distribute the $vee$ over the $wedge$, we get $[(p vee q) vee ( neg p vee r)]wedge{[(p vee neg r) wedge (neg q vee neg r)]vee(neg p vee r)}$. Focusing on the first half, you can manipulate $(p vee q) vee ( neg p vee r)$ to get $top$ by shuffling parentheses around to get $(p vee neg p) vee (q vee r)$ (I'll leave that to you).
So we are left with $[(p vee neg r) wedge (neg q vee neg r)] vee (neg p vee r)$. Again let's distribute the $vee$ over the $wedge$:
begin{align*}
&[(p vee neg r) vee (neg p vee r)] wedge [(neg q vee neg r) vee (neg p vee r)].
end{align*}
Again both halves of this can be manipulated to get $top$.
answered Jan 24 at 23:41
kccukccu
10.6k11229
$endgroup$
Expand the expression $(p wedge neg q) vee (q wedge neg r)$ by distributing the $vee$ over the $wedge$:
begin{align*}
&(p wedge neg q) vee (q wedge neg r)\
&[(p wedge neg q) vee q] wedge [(p wedge neg q) vee neg r]\
&[(p vee q ) wedge (neg q vee q)] wedge [(p vee neg r ) wedge (neg q vee neg r)]\
&[(p vee q) wedge top ] wedge[(p vee neg r) wedge (neg q vee neg r)]\
&(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)].
end{align*}
Now overall we have ${(p vee q) wedge [(p vee neg r) wedge (neg q vee neg r)]}vee (neg p vee r)$. If we distribute the $vee$ over the $wedge$, we get $[(p vee q) vee ( neg p vee r)]wedge{[(p vee neg r) wedge (neg q vee neg r)]vee(neg p vee r)}$. Focusing on the first half, you can manipulate $(p vee q) vee ( neg p vee r)$ to get $top$ by shuffling parentheses around to get $(p vee neg p) vee (q vee r)$ (I'll leave that to you).
So we are left with $[(p vee neg r) wedge (neg q vee neg r)] vee (neg p vee r)$. Again let's distribute the $vee$ over the $wedge$:
begin{align*}
&[(p vee neg r) vee (neg p vee r)] wedge [(neg q vee neg r) vee (neg p vee r)].
end{align*}
Again both halves of this can be manipulated to get $top$.
answered Jan 24 at 23:41
kccukccu
10.6k11229
answered Jan 24 at 23:41
kccukccu
10.6k11229
answered Jan 24 at 23:41
kccukccu
10.6k11229
answered Jan 24 at 23:41
kccukccu
10.6k11229
10.6k11229
add a comment |
add a comment |
$begingroup$
I can't seem to figure out what comes after this step. Can someone help me?
Yes.
$$begin{align}vdotsquad\iff&~big((p land lnot q) lor (qlandlnot r)big) lor (lnot plor r)
\[1ex]iff &~big(lnot plor (pland lnot q)big)lor big(rlor (lnot rland q)big)&quadtextsf{(Commutation and Association)}\vdotsquadend{align}$$
answered Jan 25 at 0:05
Graham KempGraham Kemp
86.8k43579
$endgroup$
add a comment |
$begingroup$
I can't seem to figure out what comes after this step. Can someone help me?
Yes.
$$begin{align}vdotsquad\iff&~big((p land lnot q) lor (qlandlnot r)big) lor (lnot plor r)
\[1ex]iff &~big(lnot plor (pland lnot q)big)lor big(rlor (lnot rland q)big)&quadtextsf{(Commutation and Association)}\vdotsquadend{align}$$
answered Jan 25 at 0:05
Graham KempGraham Kemp
86.8k43579
$endgroup$
add a comment |
$begingroup$
I can't seem to figure out what comes after this step. Can someone help me?
Yes.
$$begin{align}vdotsquad\iff&~big((p land lnot q) lor (qlandlnot r)big) lor (lnot plor r)
\[1ex]iff &~big(lnot plor (pland lnot q)big)lor big(rlor (lnot rland q)big)&quadtextsf{(Commutation and Association)}\vdotsquadend{align}$$
answered Jan 25 at 0:05
Graham KempGraham Kemp
86.8k43579
$endgroup$
I can't seem to figure out what comes after this step. Can someone help me?
Yes.
$$begin{align}vdotsquad\iff&~big((p land lnot q) lor (qlandlnot r)big) lor (lnot plor r)
\[1ex]iff &~big(lnot plor (pland lnot q)big)lor big(rlor (lnot rland q)big)&quadtextsf{(Commutation and Association)}\vdotsquadend{align}$$
answered Jan 25 at 0:05
Graham KempGraham Kemp
86.8k43579
answered Jan 25 at 0:05
Graham KempGraham Kemp
86.8k43579
answered Jan 25 at 0:05
Graham KempGraham Kemp
86.8k43579
answered Jan 25 at 0:05
Graham KempGraham Kemp
86.8k43579
86.8k43579
add a comment |
add a comment |
$begingroup$
You can use Double Distribution to get
$$[(p lor q)land(q lor lnot q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
$q lor lnot q$ is a Tautology so this becomes
$$[(p lor q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
which by distribution is
$$[(p lor q)land[lnot rland(p lor lnot q)]]lor (lnot p lor r)$$
Association gives
$$[lnot r land [(p lor q)land(p lor lnot q)]]lor (lnot p lor r)$$
Distribution again gives
$$[lnot r land [p lor(q land lnot q)]]lor (lnot p lor r)$$
$q land lnot q$ is a contradiction so this becomes
$$(lnot r land p)lor (lnot p lor r)$$
Which by DeMorgan's Law is
$$(lnot r land p)lor lnot(lnot r land p)$$
Which is a tautology.
answered Jan 25 at 1:03
Erik ParkinsonErik Parkinson
1,17519
$endgroup$
$begingroup$
Thanks for the help!!
$endgroup$
– Nev
Jan 25 at 2:02
add a comment |
$begingroup$
You can use Double Distribution to get
$$[(p lor q)land(q lor lnot q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
$q lor lnot q$ is a Tautology so this becomes
$$[(p lor q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
which by distribution is
$$[(p lor q)land[lnot rland(p lor lnot q)]]lor (lnot p lor r)$$
Association gives
$$[lnot r land [(p lor q)land(p lor lnot q)]]lor (lnot p lor r)$$
Distribution again gives
$$[lnot r land [p lor(q land lnot q)]]lor (lnot p lor r)$$
$q land lnot q$ is a contradiction so this becomes
$$(lnot r land p)lor (lnot p lor r)$$
Which by DeMorgan's Law is
$$(lnot r land p)lor lnot(lnot r land p)$$
Which is a tautology.
answered Jan 25 at 1:03
Erik ParkinsonErik Parkinson
1,17519
$endgroup$
$begingroup$
Thanks for the help!!
$endgroup$
– Nev
Jan 25 at 2:02
add a comment |
$begingroup$
You can use Double Distribution to get
$$[(p lor q)land(q lor lnot q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
$q lor lnot q$ is a Tautology so this becomes
$$[(p lor q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
which by distribution is
$$[(p lor q)land[lnot rland(p lor lnot q)]]lor (lnot p lor r)$$
Association gives
$$[lnot r land [(p lor q)land(p lor lnot q)]]lor (lnot p lor r)$$
Distribution again gives
$$[lnot r land [p lor(q land lnot q)]]lor (lnot p lor r)$$
$q land lnot q$ is a contradiction so this becomes
$$(lnot r land p)lor (lnot p lor r)$$
Which by DeMorgan's Law is
$$(lnot r land p)lor lnot(lnot r land p)$$
Which is a tautology.
answered Jan 25 at 1:03
Erik ParkinsonErik Parkinson
1,17519
$endgroup$
You can use Double Distribution to get
$$[(p lor q)land(q lor lnot q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
$q lor lnot q$ is a Tautology so this becomes
$$[(p lor q)land(lnot q lor lnot r)land(p lor lnot r)]lor (lnot p lor r)$$
which by distribution is
$$[(p lor q)land[lnot rland(p lor lnot q)]]lor (lnot p lor r)$$
Association gives
$$[lnot r land [(p lor q)land(p lor lnot q)]]lor (lnot p lor r)$$
Distribution again gives
$$[lnot r land [p lor(q land lnot q)]]lor (lnot p lor r)$$
$q land lnot q$ is a contradiction so this becomes
$$(lnot r land p)lor (lnot p lor r)$$
Which by DeMorgan's Law is
$$(lnot r land p)lor lnot(lnot r land p)$$
Which is a tautology.
answered Jan 25 at 1:03
Erik ParkinsonErik Parkinson
1,17519
answered Jan 25 at 1:03
Erik ParkinsonErik Parkinson
1,17519
answered Jan 25 at 1:03
Erik ParkinsonErik Parkinson
1,17519
answered Jan 25 at 1:03
Erik ParkinsonErik Parkinson
1,17519
1,17519
$begingroup$
Thanks for the help!!
$endgroup$
– Nev
Jan 25 at 2:02
add a comment |
$begingroup$
Thanks for the help!!
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
Thanks for the help!!
$endgroup$
– Nev
Jan 25 at 2:02
$begingroup$
Thanks for the help!!
$endgroup$
– Nev
Jan 25 at 2:02
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%2f3086499%2fshowing-a-conditional-statement-is-a-tautology-without-using-a-truth-table%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
