Mixing
How do I prove that $[¬P ∧ (P ∨ Q)] → Q$ is tautology without using truth tables?
$begingroup$
How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$
I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left of the implication operator is, the statement will be a tautology. But if we assume that $Q ≡ F$ then there could be two possibilities of the outcome of the statement: If $;[¬P ∧ (P ∨ Q)] ≡ T,;$ then the statement is false, and if $;[¬P ∧ (P ∨ Q)] ≡ F,;$ then the statement is true (according to the truth table of implication statements: $;T → F = F;text{ and };F → F = T.)$
Is there a way of proving $;[¬P ∧ (P ∨ Q)]rightarrow Q;$ is always true without using any truth tables, instead can it be solely proven by words/logic? Or am I just being dumb?
logic propositional-calculus
edited Jan 27 at 5:50
Martin Sleziak
44.9k10122275
asked Nov 6 '13 at 17:45
KrisKris
66117
$endgroup$
|
show 2 more comments
$begingroup$
How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$
I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left of the implication operator is, the statement will be a tautology. But if we assume that $Q ≡ F$ then there could be two possibilities of the outcome of the statement: If $;[¬P ∧ (P ∨ Q)] ≡ T,;$ then the statement is false, and if $;[¬P ∧ (P ∨ Q)] ≡ F,;$ then the statement is true (according to the truth table of implication statements: $;T → F = F;text{ and };F → F = T.)$
Is there a way of proving $;[¬P ∧ (P ∨ Q)]rightarrow Q;$ is always true without using any truth tables, instead can it be solely proven by words/logic? Or am I just being dumb?
logic propositional-calculus
edited Jan 27 at 5:50
Martin Sleziak
44.9k10122275
asked Nov 6 '13 at 17:45
KrisKris
66117
$endgroup$
$begingroup$
You should be able to use distributive property.
$endgroup$
– MasterOfBinary
Nov 6 '13 at 17:48
$begingroup$
In the final paragraph, I think you meant to ask if there is a way of proving the full statement is always true, not just the portion before the arrow.
$endgroup$
– Barry Cipra
Nov 6 '13 at 18:25
$begingroup$
@MasterOfBinary Why bother with the distributive property for this question?
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:26
$begingroup$
@MasterOfBinary Because it involves properties of two operations. So, you have to understand how logical operations interact to some extent. Consequently, using the distributive property may well require more understanding than you need for solving this problem, and perhaps we should try to solve such problems from a position of as little knowledge as possible. If you're doing things from "the ground-up" you'd have to prove the relevant distributive property first. That may well require more work than other sorts of solutions.
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:49
$begingroup$
@DougSpoonwood You can simplify the left side to get $neg P wedge Q$, which implies $Q$.
$endgroup$
– MasterOfBinary
Nov 8 '13 at 16:54
|
show 2 more comments
$begingroup$
How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$
I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left of the implication operator is, the statement will be a tautology. But if we assume that $Q ≡ F$ then there could be two possibilities of the outcome of the statement: If $;[¬P ∧ (P ∨ Q)] ≡ T,;$ then the statement is false, and if $;[¬P ∧ (P ∨ Q)] ≡ F,;$ then the statement is true (according to the truth table of implication statements: $;T → F = F;text{ and };F → F = T.)$
Is there a way of proving $;[¬P ∧ (P ∨ Q)]rightarrow Q;$ is always true without using any truth tables, instead can it be solely proven by words/logic? Or am I just being dumb?
logic propositional-calculus
edited Jan 27 at 5:50
Martin Sleziak
44.9k10122275
asked Nov 6 '13 at 17:45
KrisKris
66117
$endgroup$
How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$
I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left of the implication operator is, the statement will be a tautology. But if we assume that $Q ≡ F$ then there could be two possibilities of the outcome of the statement: If $;[¬P ∧ (P ∨ Q)] ≡ T,;$ then the statement is false, and if $;[¬P ∧ (P ∨ Q)] ≡ F,;$ then the statement is true (according to the truth table of implication statements: $;T → F = F;text{ and };F → F = T.)$
Is there a way of proving $;[¬P ∧ (P ∨ Q)]rightarrow Q;$ is always true without using any truth tables, instead can it be solely proven by words/logic? Or am I just being dumb?
logic propositional-calculus
logic propositional-calculus
edited Jan 27 at 5:50
Martin Sleziak
44.9k10122275
asked Nov 6 '13 at 17:45
KrisKris
66117
edited Jan 27 at 5:50
Martin Sleziak
44.9k10122275
asked Nov 6 '13 at 17:45
KrisKris
66117
edited Jan 27 at 5:50
Martin Sleziak
44.9k10122275
edited Jan 27 at 5:50
Martin Sleziak
44.9k10122275
edited Jan 27 at 5:50
Martin Sleziak
44.9k10122275
44.9k10122275
asked Nov 6 '13 at 17:45
KrisKris
66117
asked Nov 6 '13 at 17:45
KrisKris
66117
asked Nov 6 '13 at 17:45
KrisKris
66117
66117
$begingroup$
You should be able to use distributive property.
$endgroup$
– MasterOfBinary
Nov 6 '13 at 17:48
$begingroup$
In the final paragraph, I think you meant to ask if there is a way of proving the full statement is always true, not just the portion before the arrow.
$endgroup$
– Barry Cipra
Nov 6 '13 at 18:25
$begingroup$
@MasterOfBinary Why bother with the distributive property for this question?
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:26
$begingroup$
@MasterOfBinary Because it involves properties of two operations. So, you have to understand how logical operations interact to some extent. Consequently, using the distributive property may well require more understanding than you need for solving this problem, and perhaps we should try to solve such problems from a position of as little knowledge as possible. If you're doing things from "the ground-up" you'd have to prove the relevant distributive property first. That may well require more work than other sorts of solutions.
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:49
$begingroup$
@DougSpoonwood You can simplify the left side to get $neg P wedge Q$, which implies $Q$.
$endgroup$
– MasterOfBinary
Nov 8 '13 at 16:54
|
show 2 more comments
$begingroup$
You should be able to use distributive property.
$endgroup$
– MasterOfBinary
Nov 6 '13 at 17:48
$begingroup$
In the final paragraph, I think you meant to ask if there is a way of proving the full statement is always true, not just the portion before the arrow.
$endgroup$
– Barry Cipra
Nov 6 '13 at 18:25
$begingroup$
@MasterOfBinary Why bother with the distributive property for this question?
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:26
$begingroup$
@MasterOfBinary Because it involves properties of two operations. So, you have to understand how logical operations interact to some extent. Consequently, using the distributive property may well require more understanding than you need for solving this problem, and perhaps we should try to solve such problems from a position of as little knowledge as possible. If you're doing things from "the ground-up" you'd have to prove the relevant distributive property first. That may well require more work than other sorts of solutions.
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:49
$begingroup$
@DougSpoonwood You can simplify the left side to get $neg P wedge Q$, which implies $Q$.
$endgroup$
– MasterOfBinary
Nov 8 '13 at 16:54
$begingroup$
You should be able to use distributive property.
$endgroup$
– MasterOfBinary
Nov 6 '13 at 17:48
$begingroup$
You should be able to use distributive property.
$endgroup$
– MasterOfBinary
Nov 6 '13 at 17:48
$begingroup$
In the final paragraph, I think you meant to ask if there is a way of proving the full statement is always true, not just the portion before the arrow.
$endgroup$
– Barry Cipra
Nov 6 '13 at 18:25
$begingroup$
In the final paragraph, I think you meant to ask if there is a way of proving the full statement is always true, not just the portion before the arrow.
$endgroup$
– Barry Cipra
Nov 6 '13 at 18:25
$begingroup$
@MasterOfBinary Why bother with the distributive property for this question?
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:26
$begingroup$
@MasterOfBinary Why bother with the distributive property for this question?
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:26
$begingroup$
@MasterOfBinary Because it involves properties of two operations. So, you have to understand how logical operations interact to some extent. Consequently, using the distributive property may well require more understanding than you need for solving this problem, and perhaps we should try to solve such problems from a position of as little knowledge as possible. If you're doing things from "the ground-up" you'd have to prove the relevant distributive property first. That may well require more work than other sorts of solutions.
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:49
$begingroup$
@MasterOfBinary Because it involves properties of two operations. So, you have to understand how logical operations interact to some extent. Consequently, using the distributive property may well require more understanding than you need for solving this problem, and perhaps we should try to solve such problems from a position of as little knowledge as possible. If you're doing things from "the ground-up" you'd have to prove the relevant distributive property first. That may well require more work than other sorts of solutions.
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:49
$begingroup$
@DougSpoonwood You can simplify the left side to get $neg P wedge Q$, which implies $Q$.
$endgroup$
– MasterOfBinary
Nov 8 '13 at 16:54
$begingroup$
@DougSpoonwood You can simplify the left side to get $neg P wedge Q$, which implies $Q$.
$endgroup$
– MasterOfBinary
Nov 8 '13 at 16:54
|
show 2 more comments
10 Answers
10
active
oldest
votes
$begingroup$
As you note, if $Q$ is true, then the implication is true.
And if $Q$ is false, we have that $lnot P land (P lor Q) equiv underbrace{underbrace{(lnot P land P)}_{F} lor underbrace{(lnot P land underbrace{Q}_{F})}_{F}}_{F}$ and any implication with a false premise is true.
Hence, the implication is a tautology.
answered Nov 6 '13 at 17:49
NamasteNamaste
1
$endgroup$
add a comment |
$begingroup$
So, this is probably a silly approach to this sort of thing, but I hate truth tables and take a slightly more circuitous route through what Quine referred to as "alternational normal form". @amWhy cast the antecedent of the conditional in alternational normal form above, but casting the entire sentence into that form gives a pretty clear test of tautology. The drawback is that alternational form can get very long.
So the original formula is $(neg Pwedge(Pvee Q))to Q$. First thing is to eliminate the conditionals by writing this as $(Pvee(neg Pwedgeneg Q))vee Q$.
On a more complicated sentence we would make use of the distributive properties of alternation and conjunction to make sure we have a chain of alternations of conjunctions. In this case, we have it in a single step above: $Pvee(neg Pwedgeneg Q)vee Q$. By changing the order of our alternated elements and adding back in parentheses, we see we have $(Pvee Q)vee(neg Pwedgeneg Q)$ or $(Pvee Q)veeneg(Pvee Q)$, an obvious tautology.
The thing I like about alternational normal form is A) the resulting sentence is clear, if cumbersome and B) can show a tautology or inconsistency by an extremely syntax-focused method of evaluation.
answered Nov 6 '13 at 19:10
Malice VidrineMalice Vidrine
6,22421123
$endgroup$
add a comment |
$begingroup$
To prove the implication $neg P wedge (P vee Q) to Q$, we assume
$neg P wedge (P vee Q)$ and then prove $Q$ from this assumption.
From the conjunction $neg P wedge (P vee Q)$ we can infer $neg P$ and we can also infer $P vee Q$. Consider two cases according to the two disjuncts of $P vee Q$.
$P$ holds. Then from $neg P$ we get a contradiction, and from a contradiction we can infer $Q$.
$Q$ holds.
In either case we have shown that $Q$ holds.
answered Nov 8 '13 at 23:01
Trevor WilsonTrevor Wilson
14.8k2456
$endgroup$
add a comment |
$begingroup$
I agree with Malice Vidrine's answer, and would write it down in the following format:
begin{align}
& lnot P land (P lor Q) ;Rightarrow; Q \
equiv & ;;;;;text{"expand $;Rightarrow;$ -- that usually simplifies formulas"} \
& lnot(lnot P land (P lor Q)) lor Q \
equiv & ;;;;;text{"DeMorgan -- that seems the only way to make progress"} \
& P lor lnot(P lor Q) lor Q \
equiv & ;;;;;text{"reorder disjuncts -- since this introduces more symmetry"} \
& (P lor Q) lor lnot(P lor Q) \
equiv & ;;;;;text{"excluded middle"} \
& text{true}
end{align}
Alternatively, we can start with the antecedent, and try to simplify:
begin{align}
& lnot P land (P lor Q) \
equiv & ;;;;;text{"distribute $;land;$ over $;lor;$"} \
& (lnot P land P) lor (lnot P land Q) \
equiv & ;;;;;text{"contradiction"} \
& text{false} lor (lnot P land Q) \
equiv & ;;;;;text{"simplify"} \
& lnot P land Q \
Rightarrow & ;;;;;text{"weaken -- to achieve our goal"} \
& Q \
end{align}
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 6 '13 at 19:28
Marnix KloosterMarnix Klooster
4,23122149
$endgroup$
add a comment |
$begingroup$
*Using the algorithm tautology test*
[P'∧(P∨Q)]→Q
Assume: [P'∧(P∨Q)] is true and Q is false
Assume that [P'∧(P∨Q)] is true and Q is false.
-If [P'∧(P∨Q)] is true, then P' is true and (P∨Q) is true.
-If P' is true, then P is false.
-If P is false in (P∨Q), then Q is true in order for (P∨Q) to be true.
So Q contradicts, it says that is false and at the same time is says that is true. Because of this, we know that this WFF(well formed formula) is a tautology!
answered Jan 22 '14 at 21:15
GabrielGabriel
112
$endgroup$
add a comment |
$begingroup$
Using a Fitch style proof, this tautology can be proved by contradiction. Assume the statement is false, show that this assumption entails a contradiction, then negate the assumption.
answered May 30 '14 at 21:52
pseudologoipseudologoi
10510
$endgroup$
2
$begingroup$
which program did you use for this?
$endgroup$
– ndrizza
Oct 12 '14 at 22:09
add a comment |
$begingroup$
The only way for ¬P ∧ (P ∨ Q) to be true is for P to be false and Q to be true. So the full statement [¬P ∧ (P ∨ Q)] → Q cannot be false. Hence it is a tautology.
answered Nov 6 '13 at 17:54
Barry CipraBarry Cipra
60.4k654128
$endgroup$
add a comment |
$begingroup$
"But if we assume that Q≡F then there could be two possibilities of the outcome of the statement"
That's not correct. If you assume Q≡F (I'm not assuming ≡ as a logical operator here), then it follows that
[¬p∧(p∨q)]≡[¬p∧(p∨F)] where F indicates the constant false proposition.
(p∨F)≡p, since (T∨F)≡T, and (T∨T)≡T. Or in more algebraic terminology we can say that "F" is the neutral or identity element for ∨.
Thus,
[¬p∧(p∨F)]≡(¬p∧p). From here I think you can complete this sort of proof.
Additionally, I'll add that you could have considered the cases where P holds false, and P holds true. In which case you'll similarly end up using "F" as the neutral element for ∨. In this way, the truth value of a disjunction of two propositions behaves like the maximum of two natural numbers (and in general this holds also).
answered Nov 8 '13 at 16:34
Doug SpoonwoodDoug Spoonwood
8,14212244
$endgroup$
add a comment |
$begingroup$
Assume [¬P∧(P∨Q)]. From "both x and y" as true, we may infer x as true. We may also infer y as true. So, we can infer ¬P as true, as well as (P∨Q) as true. Assume P true. Assume ¬Q true. Then since we have ¬P and P true, we may discharge the negation and infer Q. So, (P→Q) holds true. Suppose Q true. Then Q holds true. So, we can infer (Q→Q) holds true. Since (P∨Q), (P→Q), and (Q→Q) hold true, it follows that Q holds true. Since [¬P∧(P∨Q)] comes as the only assumption still in place, we may infer {[¬P∧(P∨Q)]→Q} as true as desired.
Via Polish notation, (P∨Q) can get rewritten as Apq, [¬P∧(P∨Q)] can get rewritten as KNpApq, and {[¬P∧(P∨Q)]→Q} can get rewritten as CKNpApqq. We can then use the following axioms to prove CKNpApqq as a theorem. By a relevant soundness meta-theorem, we'll have CKNpApqq as a tautology also.
A1 CpCqp - recursive variable prefixing - RVP
A2 CCpCqrCCpqCpr - self-distribution - SD
A3 CCNpKqNqp - negation out - No
A4 CKpqp - conjunction out left - Kol
A5 CKpqq - conjunction out right - Kor
A6 CpCqKpq - conjunction in - Ki
A7 CCpqCCrqCAprq - disjunction out - Ao
Via the relevant deduction meta-theorem which SD and RVP enable, we have conditional introduction as a derivable rule of inference, which I'll denote as Ci. The only other rule of inference I'll use is C-detachment or C-d
{C$alpha$$beta$, $alpha$} $vdash$ $beta$.
1 hypothesis | KNpApq
2 Kol | CKNpApqNp
3 C-d 2, 1 | Np
4 Kor | CKNpApqApq
5 C-d 4, 1 | Apq
6 hypothesis || p
7 hypothesis ||| Nq
8 Ki ||| CpCNpKpNp
9 C-d 8, 6 ||| CNpKpNp
10 C-d 9, 3 ||| KpNp
11 Ci 7-10 || CNqKpNp
12 No || CCNqKpNpq
13 C-d 12, 11 || q
14 Ci 6-13 | Cpq
15 hypothesis || q
16 Ci 15-15 | Cqq
17 Ao | CCpqCCqqCApqq
18 C-d 17, 14 | CCqqCApqq
19 C-d 18, 16 | CApqq
20 C-d 19, 5 | q
21 Ci 1-20 CKNpApqq.
answered Nov 8 '13 at 17:36
Doug SpoonwoodDoug Spoonwood
8,14212244
$endgroup$
add a comment |
$begingroup$
[~p^(pvq)]->q
[pv(~p^~q)]vq
[(pv~p)^(pv~q)]vq
[T^(pv~q)]vq
(pv~q)vq
pvT
T
======================
Therefore its a tautology^^
answered Jul 5 '15 at 13:01
Romeo Bantugan Jr.Romeo Bantugan Jr.
1
$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%2f554593%2fhow-do-i-prove-that-%25c2%25acp-%25e2%2588%25a7-p-%25e2%2588%25a8-q-%25e2%2586%2592-q-is-tautology-without-using-truth-tables%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As you note, if $Q$ is true, then the implication is true.
And if $Q$ is false, we have that $lnot P land (P lor Q) equiv underbrace{underbrace{(lnot P land P)}_{F} lor underbrace{(lnot P land underbrace{Q}_{F})}_{F}}_{F}$ and any implication with a false premise is true.
Hence, the implication is a tautology.
answered Nov 6 '13 at 17:49
NamasteNamaste
1
$endgroup$
add a comment |
$begingroup$
As you note, if $Q$ is true, then the implication is true.
And if $Q$ is false, we have that $lnot P land (P lor Q) equiv underbrace{underbrace{(lnot P land P)}_{F} lor underbrace{(lnot P land underbrace{Q}_{F})}_{F}}_{F}$ and any implication with a false premise is true.
Hence, the implication is a tautology.
answered Nov 6 '13 at 17:49
NamasteNamaste
1
$endgroup$
add a comment |
$begingroup$
As you note, if $Q$ is true, then the implication is true.
And if $Q$ is false, we have that $lnot P land (P lor Q) equiv underbrace{underbrace{(lnot P land P)}_{F} lor underbrace{(lnot P land underbrace{Q}_{F})}_{F}}_{F}$ and any implication with a false premise is true.
Hence, the implication is a tautology.
answered Nov 6 '13 at 17:49
NamasteNamaste
1
$endgroup$
As you note, if $Q$ is true, then the implication is true.
And if $Q$ is false, we have that $lnot P land (P lor Q) equiv underbrace{underbrace{(lnot P land P)}_{F} lor underbrace{(lnot P land underbrace{Q}_{F})}_{F}}_{F}$ and any implication with a false premise is true.
Hence, the implication is a tautology.
answered Nov 6 '13 at 17:49
NamasteNamaste
1
edited Nov 6 '13 at 17:55
answered Nov 6 '13 at 17:49
NamasteNamaste
1
answered Nov 6 '13 at 17:49
NamasteNamaste
1
answered Nov 6 '13 at 17:49
NamasteNamaste
1
1
add a comment |
add a comment |
$begingroup$
So, this is probably a silly approach to this sort of thing, but I hate truth tables and take a slightly more circuitous route through what Quine referred to as "alternational normal form". @amWhy cast the antecedent of the conditional in alternational normal form above, but casting the entire sentence into that form gives a pretty clear test of tautology. The drawback is that alternational form can get very long.
So the original formula is $(neg Pwedge(Pvee Q))to Q$. First thing is to eliminate the conditionals by writing this as $(Pvee(neg Pwedgeneg Q))vee Q$.
On a more complicated sentence we would make use of the distributive properties of alternation and conjunction to make sure we have a chain of alternations of conjunctions. In this case, we have it in a single step above: $Pvee(neg Pwedgeneg Q)vee Q$. By changing the order of our alternated elements and adding back in parentheses, we see we have $(Pvee Q)vee(neg Pwedgeneg Q)$ or $(Pvee Q)veeneg(Pvee Q)$, an obvious tautology.
The thing I like about alternational normal form is A) the resulting sentence is clear, if cumbersome and B) can show a tautology or inconsistency by an extremely syntax-focused method of evaluation.
answered Nov 6 '13 at 19:10
Malice VidrineMalice Vidrine
6,22421123
$endgroup$
add a comment |
$begingroup$
So, this is probably a silly approach to this sort of thing, but I hate truth tables and take a slightly more circuitous route through what Quine referred to as "alternational normal form". @amWhy cast the antecedent of the conditional in alternational normal form above, but casting the entire sentence into that form gives a pretty clear test of tautology. The drawback is that alternational form can get very long.
So the original formula is $(neg Pwedge(Pvee Q))to Q$. First thing is to eliminate the conditionals by writing this as $(Pvee(neg Pwedgeneg Q))vee Q$.
On a more complicated sentence we would make use of the distributive properties of alternation and conjunction to make sure we have a chain of alternations of conjunctions. In this case, we have it in a single step above: $Pvee(neg Pwedgeneg Q)vee Q$. By changing the order of our alternated elements and adding back in parentheses, we see we have $(Pvee Q)vee(neg Pwedgeneg Q)$ or $(Pvee Q)veeneg(Pvee Q)$, an obvious tautology.
The thing I like about alternational normal form is A) the resulting sentence is clear, if cumbersome and B) can show a tautology or inconsistency by an extremely syntax-focused method of evaluation.
answered Nov 6 '13 at 19:10
Malice VidrineMalice Vidrine
6,22421123
$endgroup$
add a comment |
$begingroup$
So, this is probably a silly approach to this sort of thing, but I hate truth tables and take a slightly more circuitous route through what Quine referred to as "alternational normal form". @amWhy cast the antecedent of the conditional in alternational normal form above, but casting the entire sentence into that form gives a pretty clear test of tautology. The drawback is that alternational form can get very long.
So the original formula is $(neg Pwedge(Pvee Q))to Q$. First thing is to eliminate the conditionals by writing this as $(Pvee(neg Pwedgeneg Q))vee Q$.
On a more complicated sentence we would make use of the distributive properties of alternation and conjunction to make sure we have a chain of alternations of conjunctions. In this case, we have it in a single step above: $Pvee(neg Pwedgeneg Q)vee Q$. By changing the order of our alternated elements and adding back in parentheses, we see we have $(Pvee Q)vee(neg Pwedgeneg Q)$ or $(Pvee Q)veeneg(Pvee Q)$, an obvious tautology.
The thing I like about alternational normal form is A) the resulting sentence is clear, if cumbersome and B) can show a tautology or inconsistency by an extremely syntax-focused method of evaluation.
answered Nov 6 '13 at 19:10
Malice VidrineMalice Vidrine
6,22421123
$endgroup$
So, this is probably a silly approach to this sort of thing, but I hate truth tables and take a slightly more circuitous route through what Quine referred to as "alternational normal form". @amWhy cast the antecedent of the conditional in alternational normal form above, but casting the entire sentence into that form gives a pretty clear test of tautology. The drawback is that alternational form can get very long.
So the original formula is $(neg Pwedge(Pvee Q))to Q$. First thing is to eliminate the conditionals by writing this as $(Pvee(neg Pwedgeneg Q))vee Q$.
On a more complicated sentence we would make use of the distributive properties of alternation and conjunction to make sure we have a chain of alternations of conjunctions. In this case, we have it in a single step above: $Pvee(neg Pwedgeneg Q)vee Q$. By changing the order of our alternated elements and adding back in parentheses, we see we have $(Pvee Q)vee(neg Pwedgeneg Q)$ or $(Pvee Q)veeneg(Pvee Q)$, an obvious tautology.
The thing I like about alternational normal form is A) the resulting sentence is clear, if cumbersome and B) can show a tautology or inconsistency by an extremely syntax-focused method of evaluation.
answered Nov 6 '13 at 19:10
Malice VidrineMalice Vidrine
6,22421123
answered Nov 6 '13 at 19:10
Malice VidrineMalice Vidrine
6,22421123
answered Nov 6 '13 at 19:10
Malice VidrineMalice Vidrine
6,22421123
answered Nov 6 '13 at 19:10
Malice VidrineMalice Vidrine
6,22421123
6,22421123
add a comment |
add a comment |
$begingroup$
To prove the implication $neg P wedge (P vee Q) to Q$, we assume
$neg P wedge (P vee Q)$ and then prove $Q$ from this assumption.
From the conjunction $neg P wedge (P vee Q)$ we can infer $neg P$ and we can also infer $P vee Q$. Consider two cases according to the two disjuncts of $P vee Q$.
$P$ holds. Then from $neg P$ we get a contradiction, and from a contradiction we can infer $Q$.
$Q$ holds.
In either case we have shown that $Q$ holds.
answered Nov 8 '13 at 23:01
Trevor WilsonTrevor Wilson
14.8k2456
$endgroup$
add a comment |
$begingroup$
To prove the implication $neg P wedge (P vee Q) to Q$, we assume
$neg P wedge (P vee Q)$ and then prove $Q$ from this assumption.
From the conjunction $neg P wedge (P vee Q)$ we can infer $neg P$ and we can also infer $P vee Q$. Consider two cases according to the two disjuncts of $P vee Q$.
$P$ holds. Then from $neg P$ we get a contradiction, and from a contradiction we can infer $Q$.
$Q$ holds.
In either case we have shown that $Q$ holds.
answered Nov 8 '13 at 23:01
Trevor WilsonTrevor Wilson
14.8k2456
$endgroup$
add a comment |
$begingroup$
To prove the implication $neg P wedge (P vee Q) to Q$, we assume
$neg P wedge (P vee Q)$ and then prove $Q$ from this assumption.
From the conjunction $neg P wedge (P vee Q)$ we can infer $neg P$ and we can also infer $P vee Q$. Consider two cases according to the two disjuncts of $P vee Q$.
$P$ holds. Then from $neg P$ we get a contradiction, and from a contradiction we can infer $Q$.
$Q$ holds.
In either case we have shown that $Q$ holds.
answered Nov 8 '13 at 23:01
Trevor WilsonTrevor Wilson
14.8k2456
$endgroup$
To prove the implication $neg P wedge (P vee Q) to Q$, we assume
$neg P wedge (P vee Q)$ and then prove $Q$ from this assumption.
From the conjunction $neg P wedge (P vee Q)$ we can infer $neg P$ and we can also infer $P vee Q$. Consider two cases according to the two disjuncts of $P vee Q$.
$P$ holds. Then from $neg P$ we get a contradiction, and from a contradiction we can infer $Q$.
$Q$ holds.
In either case we have shown that $Q$ holds.
answered Nov 8 '13 at 23:01
Trevor WilsonTrevor Wilson
14.8k2456
answered Nov 8 '13 at 23:01
Trevor WilsonTrevor Wilson
14.8k2456
answered Nov 8 '13 at 23:01
Trevor WilsonTrevor Wilson
14.8k2456
answered Nov 8 '13 at 23:01
Trevor WilsonTrevor Wilson
14.8k2456
14.8k2456
add a comment |
add a comment |
$begingroup$
I agree with Malice Vidrine's answer, and would write it down in the following format:
begin{align}
& lnot P land (P lor Q) ;Rightarrow; Q \
equiv & ;;;;;text{"expand $;Rightarrow;$ -- that usually simplifies formulas"} \
& lnot(lnot P land (P lor Q)) lor Q \
equiv & ;;;;;text{"DeMorgan -- that seems the only way to make progress"} \
& P lor lnot(P lor Q) lor Q \
equiv & ;;;;;text{"reorder disjuncts -- since this introduces more symmetry"} \
& (P lor Q) lor lnot(P lor Q) \
equiv & ;;;;;text{"excluded middle"} \
& text{true}
end{align}
Alternatively, we can start with the antecedent, and try to simplify:
begin{align}
& lnot P land (P lor Q) \
equiv & ;;;;;text{"distribute $;land;$ over $;lor;$"} \
& (lnot P land P) lor (lnot P land Q) \
equiv & ;;;;;text{"contradiction"} \
& text{false} lor (lnot P land Q) \
equiv & ;;;;;text{"simplify"} \
& lnot P land Q \
Rightarrow & ;;;;;text{"weaken -- to achieve our goal"} \
& Q \
end{align}
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 6 '13 at 19:28
Marnix KloosterMarnix Klooster
4,23122149
$endgroup$
add a comment |
$begingroup$
I agree with Malice Vidrine's answer, and would write it down in the following format:
begin{align}
& lnot P land (P lor Q) ;Rightarrow; Q \
equiv & ;;;;;text{"expand $;Rightarrow;$ -- that usually simplifies formulas"} \
& lnot(lnot P land (P lor Q)) lor Q \
equiv & ;;;;;text{"DeMorgan -- that seems the only way to make progress"} \
& P lor lnot(P lor Q) lor Q \
equiv & ;;;;;text{"reorder disjuncts -- since this introduces more symmetry"} \
& (P lor Q) lor lnot(P lor Q) \
equiv & ;;;;;text{"excluded middle"} \
& text{true}
end{align}
Alternatively, we can start with the antecedent, and try to simplify:
begin{align}
& lnot P land (P lor Q) \
equiv & ;;;;;text{"distribute $;land;$ over $;lor;$"} \
& (lnot P land P) lor (lnot P land Q) \
equiv & ;;;;;text{"contradiction"} \
& text{false} lor (lnot P land Q) \
equiv & ;;;;;text{"simplify"} \
& lnot P land Q \
Rightarrow & ;;;;;text{"weaken -- to achieve our goal"} \
& Q \
end{align}
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 6 '13 at 19:28
Marnix KloosterMarnix Klooster
4,23122149
$endgroup$
add a comment |
$begingroup$
I agree with Malice Vidrine's answer, and would write it down in the following format:
begin{align}
& lnot P land (P lor Q) ;Rightarrow; Q \
equiv & ;;;;;text{"expand $;Rightarrow;$ -- that usually simplifies formulas"} \
& lnot(lnot P land (P lor Q)) lor Q \
equiv & ;;;;;text{"DeMorgan -- that seems the only way to make progress"} \
& P lor lnot(P lor Q) lor Q \
equiv & ;;;;;text{"reorder disjuncts -- since this introduces more symmetry"} \
& (P lor Q) lor lnot(P lor Q) \
equiv & ;;;;;text{"excluded middle"} \
& text{true}
end{align}
Alternatively, we can start with the antecedent, and try to simplify:
begin{align}
& lnot P land (P lor Q) \
equiv & ;;;;;text{"distribute $;land;$ over $;lor;$"} \
& (lnot P land P) lor (lnot P land Q) \
equiv & ;;;;;text{"contradiction"} \
& text{false} lor (lnot P land Q) \
equiv & ;;;;;text{"simplify"} \
& lnot P land Q \
Rightarrow & ;;;;;text{"weaken -- to achieve our goal"} \
& Q \
end{align}
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 6 '13 at 19:28
Marnix KloosterMarnix Klooster
4,23122149
$endgroup$
I agree with Malice Vidrine's answer, and would write it down in the following format:
begin{align}
& lnot P land (P lor Q) ;Rightarrow; Q \
equiv & ;;;;;text{"expand $;Rightarrow;$ -- that usually simplifies formulas"} \
& lnot(lnot P land (P lor Q)) lor Q \
equiv & ;;;;;text{"DeMorgan -- that seems the only way to make progress"} \
& P lor lnot(P lor Q) lor Q \
equiv & ;;;;;text{"reorder disjuncts -- since this introduces more symmetry"} \
& (P lor Q) lor lnot(P lor Q) \
equiv & ;;;;;text{"excluded middle"} \
& text{true}
end{align}
Alternatively, we can start with the antecedent, and try to simplify:
begin{align}
& lnot P land (P lor Q) \
equiv & ;;;;;text{"distribute $;land;$ over $;lor;$"} \
& (lnot P land P) lor (lnot P land Q) \
equiv & ;;;;;text{"contradiction"} \
& text{false} lor (lnot P land Q) \
equiv & ;;;;;text{"simplify"} \
& lnot P land Q \
Rightarrow & ;;;;;text{"weaken -- to achieve our goal"} \
& Q \
end{align}
edited Apr 13 '17 at 12:20
Community♦
1
answered Nov 6 '13 at 19:28
Marnix KloosterMarnix Klooster
4,23122149
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Nov 6 '13 at 19:28
Marnix KloosterMarnix Klooster
4,23122149
answered Nov 6 '13 at 19:28
Marnix KloosterMarnix Klooster
4,23122149
answered Nov 6 '13 at 19:28
Marnix KloosterMarnix Klooster
4,23122149
4,23122149
add a comment |
add a comment |
$begingroup$
*Using the algorithm tautology test*
[P'∧(P∨Q)]→Q
Assume: [P'∧(P∨Q)] is true and Q is false
Assume that [P'∧(P∨Q)] is true and Q is false.
-If [P'∧(P∨Q)] is true, then P' is true and (P∨Q) is true.
-If P' is true, then P is false.
-If P is false in (P∨Q), then Q is true in order for (P∨Q) to be true.
So Q contradicts, it says that is false and at the same time is says that is true. Because of this, we know that this WFF(well formed formula) is a tautology!
answered Jan 22 '14 at 21:15
GabrielGabriel
112
$endgroup$
add a comment |
$begingroup$
*Using the algorithm tautology test*
[P'∧(P∨Q)]→Q
Assume: [P'∧(P∨Q)] is true and Q is false
Assume that [P'∧(P∨Q)] is true and Q is false.
-If [P'∧(P∨Q)] is true, then P' is true and (P∨Q) is true.
-If P' is true, then P is false.
-If P is false in (P∨Q), then Q is true in order for (P∨Q) to be true.
So Q contradicts, it says that is false and at the same time is says that is true. Because of this, we know that this WFF(well formed formula) is a tautology!
answered Jan 22 '14 at 21:15
GabrielGabriel
112
$endgroup$
add a comment |
$begingroup$
*Using the algorithm tautology test*
[P'∧(P∨Q)]→Q
Assume: [P'∧(P∨Q)] is true and Q is false
Assume that [P'∧(P∨Q)] is true and Q is false.
-If [P'∧(P∨Q)] is true, then P' is true and (P∨Q) is true.
-If P' is true, then P is false.
-If P is false in (P∨Q), then Q is true in order for (P∨Q) to be true.
So Q contradicts, it says that is false and at the same time is says that is true. Because of this, we know that this WFF(well formed formula) is a tautology!
answered Jan 22 '14 at 21:15
GabrielGabriel
112
$endgroup$
*Using the algorithm tautology test*
[P'∧(P∨Q)]→Q
Assume: [P'∧(P∨Q)] is true and Q is false
Assume that [P'∧(P∨Q)] is true and Q is false.
-If [P'∧(P∨Q)] is true, then P' is true and (P∨Q) is true.
-If P' is true, then P is false.
-If P is false in (P∨Q), then Q is true in order for (P∨Q) to be true.
So Q contradicts, it says that is false and at the same time is says that is true. Because of this, we know that this WFF(well formed formula) is a tautology!
answered Jan 22 '14 at 21:15
GabrielGabriel
112
edited Jan 22 '14 at 21:20
answered Jan 22 '14 at 21:15
GabrielGabriel
112
answered Jan 22 '14 at 21:15
GabrielGabriel
112
answered Jan 22 '14 at 21:15
GabrielGabriel
112
112
add a comment |
add a comment |
$begingroup$
Using a Fitch style proof, this tautology can be proved by contradiction. Assume the statement is false, show that this assumption entails a contradiction, then negate the assumption.
answered May 30 '14 at 21:52
pseudologoipseudologoi
10510
$endgroup$
2
$begingroup$
which program did you use for this?
$endgroup$
– ndrizza
Oct 12 '14 at 22:09
add a comment |
$begingroup$
Using a Fitch style proof, this tautology can be proved by contradiction. Assume the statement is false, show that this assumption entails a contradiction, then negate the assumption.
answered May 30 '14 at 21:52
pseudologoipseudologoi
10510
$endgroup$
2
$begingroup$
which program did you use for this?
$endgroup$
– ndrizza
Oct 12 '14 at 22:09
add a comment |
$begingroup$
Using a Fitch style proof, this tautology can be proved by contradiction. Assume the statement is false, show that this assumption entails a contradiction, then negate the assumption.
answered May 30 '14 at 21:52
pseudologoipseudologoi
10510
$endgroup$
Using a Fitch style proof, this tautology can be proved by contradiction. Assume the statement is false, show that this assumption entails a contradiction, then negate the assumption.
answered May 30 '14 at 21:52
pseudologoipseudologoi
10510
answered May 30 '14 at 21:52
pseudologoipseudologoi
10510
answered May 30 '14 at 21:52
pseudologoipseudologoi
10510
answered May 30 '14 at 21:52
pseudologoipseudologoi
10510
10510
2
$begingroup$
which program did you use for this?
$endgroup$
– ndrizza
Oct 12 '14 at 22:09
add a comment |
2
$begingroup$
which program did you use for this?
$endgroup$
– ndrizza
Oct 12 '14 at 22:09
2
2
$begingroup$
which program did you use for this?
$endgroup$
– ndrizza
Oct 12 '14 at 22:09
$begingroup$
which program did you use for this?
$endgroup$
– ndrizza
Oct 12 '14 at 22:09
add a comment |
$begingroup$
The only way for ¬P ∧ (P ∨ Q) to be true is for P to be false and Q to be true. So the full statement [¬P ∧ (P ∨ Q)] → Q cannot be false. Hence it is a tautology.
answered Nov 6 '13 at 17:54
Barry CipraBarry Cipra
60.4k654128
$endgroup$
add a comment |
$begingroup$
The only way for ¬P ∧ (P ∨ Q) to be true is for P to be false and Q to be true. So the full statement [¬P ∧ (P ∨ Q)] → Q cannot be false. Hence it is a tautology.
answered Nov 6 '13 at 17:54
Barry CipraBarry Cipra
60.4k654128
$endgroup$
add a comment |
$begingroup$
The only way for ¬P ∧ (P ∨ Q) to be true is for P to be false and Q to be true. So the full statement [¬P ∧ (P ∨ Q)] → Q cannot be false. Hence it is a tautology.
answered Nov 6 '13 at 17:54
Barry CipraBarry Cipra
60.4k654128
$endgroup$
The only way for ¬P ∧ (P ∨ Q) to be true is for P to be false and Q to be true. So the full statement [¬P ∧ (P ∨ Q)] → Q cannot be false. Hence it is a tautology.
answered Nov 6 '13 at 17:54
Barry CipraBarry Cipra
60.4k654128
answered Nov 6 '13 at 17:54
Barry CipraBarry Cipra
60.4k654128
answered Nov 6 '13 at 17:54
Barry CipraBarry Cipra
60.4k654128
answered Nov 6 '13 at 17:54
Barry CipraBarry Cipra
60.4k654128
60.4k654128
add a comment |
add a comment |
$begingroup$
"But if we assume that Q≡F then there could be two possibilities of the outcome of the statement"
That's not correct. If you assume Q≡F (I'm not assuming ≡ as a logical operator here), then it follows that
[¬p∧(p∨q)]≡[¬p∧(p∨F)] where F indicates the constant false proposition.
(p∨F)≡p, since (T∨F)≡T, and (T∨T)≡T. Or in more algebraic terminology we can say that "F" is the neutral or identity element for ∨.
Thus,
[¬p∧(p∨F)]≡(¬p∧p). From here I think you can complete this sort of proof.
Additionally, I'll add that you could have considered the cases where P holds false, and P holds true. In which case you'll similarly end up using "F" as the neutral element for ∨. In this way, the truth value of a disjunction of two propositions behaves like the maximum of two natural numbers (and in general this holds also).
answered Nov 8 '13 at 16:34
Doug SpoonwoodDoug Spoonwood
8,14212244
$endgroup$
add a comment |
$begingroup$
"But if we assume that Q≡F then there could be two possibilities of the outcome of the statement"
That's not correct. If you assume Q≡F (I'm not assuming ≡ as a logical operator here), then it follows that
[¬p∧(p∨q)]≡[¬p∧(p∨F)] where F indicates the constant false proposition.
(p∨F)≡p, since (T∨F)≡T, and (T∨T)≡T. Or in more algebraic terminology we can say that "F" is the neutral or identity element for ∨.
Thus,
[¬p∧(p∨F)]≡(¬p∧p). From here I think you can complete this sort of proof.
Additionally, I'll add that you could have considered the cases where P holds false, and P holds true. In which case you'll similarly end up using "F" as the neutral element for ∨. In this way, the truth value of a disjunction of two propositions behaves like the maximum of two natural numbers (and in general this holds also).
answered Nov 8 '13 at 16:34
Doug SpoonwoodDoug Spoonwood
8,14212244
$endgroup$
add a comment |
$begingroup$
"But if we assume that Q≡F then there could be two possibilities of the outcome of the statement"
That's not correct. If you assume Q≡F (I'm not assuming ≡ as a logical operator here), then it follows that
[¬p∧(p∨q)]≡[¬p∧(p∨F)] where F indicates the constant false proposition.
(p∨F)≡p, since (T∨F)≡T, and (T∨T)≡T. Or in more algebraic terminology we can say that "F" is the neutral or identity element for ∨.
Thus,
[¬p∧(p∨F)]≡(¬p∧p). From here I think you can complete this sort of proof.
Additionally, I'll add that you could have considered the cases where P holds false, and P holds true. In which case you'll similarly end up using "F" as the neutral element for ∨. In this way, the truth value of a disjunction of two propositions behaves like the maximum of two natural numbers (and in general this holds also).
answered Nov 8 '13 at 16:34
Doug SpoonwoodDoug Spoonwood
8,14212244
$endgroup$
"But if we assume that Q≡F then there could be two possibilities of the outcome of the statement"
That's not correct. If you assume Q≡F (I'm not assuming ≡ as a logical operator here), then it follows that
[¬p∧(p∨q)]≡[¬p∧(p∨F)] where F indicates the constant false proposition.
(p∨F)≡p, since (T∨F)≡T, and (T∨T)≡T. Or in more algebraic terminology we can say that "F" is the neutral or identity element for ∨.
Thus,
[¬p∧(p∨F)]≡(¬p∧p). From here I think you can complete this sort of proof.
Additionally, I'll add that you could have considered the cases where P holds false, and P holds true. In which case you'll similarly end up using "F" as the neutral element for ∨. In this way, the truth value of a disjunction of two propositions behaves like the maximum of two natural numbers (and in general this holds also).
answered Nov 8 '13 at 16:34
Doug SpoonwoodDoug Spoonwood
8,14212244
edited Nov 8 '13 at 16:39
answered Nov 8 '13 at 16:34
Doug SpoonwoodDoug Spoonwood
8,14212244
answered Nov 8 '13 at 16:34
Doug SpoonwoodDoug Spoonwood
8,14212244
answered Nov 8 '13 at 16:34
Doug SpoonwoodDoug Spoonwood
8,14212244
8,14212244
add a comment |
add a comment |
$begingroup$
Assume [¬P∧(P∨Q)]. From "both x and y" as true, we may infer x as true. We may also infer y as true. So, we can infer ¬P as true, as well as (P∨Q) as true. Assume P true. Assume ¬Q true. Then since we have ¬P and P true, we may discharge the negation and infer Q. So, (P→Q) holds true. Suppose Q true. Then Q holds true. So, we can infer (Q→Q) holds true. Since (P∨Q), (P→Q), and (Q→Q) hold true, it follows that Q holds true. Since [¬P∧(P∨Q)] comes as the only assumption still in place, we may infer {[¬P∧(P∨Q)]→Q} as true as desired.
Via Polish notation, (P∨Q) can get rewritten as Apq, [¬P∧(P∨Q)] can get rewritten as KNpApq, and {[¬P∧(P∨Q)]→Q} can get rewritten as CKNpApqq. We can then use the following axioms to prove CKNpApqq as a theorem. By a relevant soundness meta-theorem, we'll have CKNpApqq as a tautology also.
A1 CpCqp - recursive variable prefixing - RVP
A2 CCpCqrCCpqCpr - self-distribution - SD
A3 CCNpKqNqp - negation out - No
A4 CKpqp - conjunction out left - Kol
A5 CKpqq - conjunction out right - Kor
A6 CpCqKpq - conjunction in - Ki
A7 CCpqCCrqCAprq - disjunction out - Ao
Via the relevant deduction meta-theorem which SD and RVP enable, we have conditional introduction as a derivable rule of inference, which I'll denote as Ci. The only other rule of inference I'll use is C-detachment or C-d
{C$alpha$$beta$, $alpha$} $vdash$ $beta$.
1 hypothesis | KNpApq
2 Kol | CKNpApqNp
3 C-d 2, 1 | Np
4 Kor | CKNpApqApq
5 C-d 4, 1 | Apq
6 hypothesis || p
7 hypothesis ||| Nq
8 Ki ||| CpCNpKpNp
9 C-d 8, 6 ||| CNpKpNp
10 C-d 9, 3 ||| KpNp
11 Ci 7-10 || CNqKpNp
12 No || CCNqKpNpq
13 C-d 12, 11 || q
14 Ci 6-13 | Cpq
15 hypothesis || q
16 Ci 15-15 | Cqq
17 Ao | CCpqCCqqCApqq
18 C-d 17, 14 | CCqqCApqq
19 C-d 18, 16 | CApqq
20 C-d 19, 5 | q
21 Ci 1-20 CKNpApqq.
answered Nov 8 '13 at 17:36
Doug SpoonwoodDoug Spoonwood
8,14212244
$endgroup$
add a comment |
$begingroup$
Assume [¬P∧(P∨Q)]. From "both x and y" as true, we may infer x as true. We may also infer y as true. So, we can infer ¬P as true, as well as (P∨Q) as true. Assume P true. Assume ¬Q true. Then since we have ¬P and P true, we may discharge the negation and infer Q. So, (P→Q) holds true. Suppose Q true. Then Q holds true. So, we can infer (Q→Q) holds true. Since (P∨Q), (P→Q), and (Q→Q) hold true, it follows that Q holds true. Since [¬P∧(P∨Q)] comes as the only assumption still in place, we may infer {[¬P∧(P∨Q)]→Q} as true as desired.
Via Polish notation, (P∨Q) can get rewritten as Apq, [¬P∧(P∨Q)] can get rewritten as KNpApq, and {[¬P∧(P∨Q)]→Q} can get rewritten as CKNpApqq. We can then use the following axioms to prove CKNpApqq as a theorem. By a relevant soundness meta-theorem, we'll have CKNpApqq as a tautology also.
A1 CpCqp - recursive variable prefixing - RVP
A2 CCpCqrCCpqCpr - self-distribution - SD
A3 CCNpKqNqp - negation out - No
A4 CKpqp - conjunction out left - Kol
A5 CKpqq - conjunction out right - Kor
A6 CpCqKpq - conjunction in - Ki
A7 CCpqCCrqCAprq - disjunction out - Ao
Via the relevant deduction meta-theorem which SD and RVP enable, we have conditional introduction as a derivable rule of inference, which I'll denote as Ci. The only other rule of inference I'll use is C-detachment or C-d
{C$alpha$$beta$, $alpha$} $vdash$ $beta$.
1 hypothesis | KNpApq
2 Kol | CKNpApqNp
3 C-d 2, 1 | Np
4 Kor | CKNpApqApq
5 C-d 4, 1 | Apq
6 hypothesis || p
7 hypothesis ||| Nq
8 Ki ||| CpCNpKpNp
9 C-d 8, 6 ||| CNpKpNp
10 C-d 9, 3 ||| KpNp
11 Ci 7-10 || CNqKpNp
12 No || CCNqKpNpq
13 C-d 12, 11 || q
14 Ci 6-13 | Cpq
15 hypothesis || q
16 Ci 15-15 | Cqq
17 Ao | CCpqCCqqCApqq
18 C-d 17, 14 | CCqqCApqq
19 C-d 18, 16 | CApqq
20 C-d 19, 5 | q
21 Ci 1-20 CKNpApqq.
answered Nov 8 '13 at 17:36
Doug SpoonwoodDoug Spoonwood
8,14212244
$endgroup$
add a comment |
$begingroup$
Assume [¬P∧(P∨Q)]. From "both x and y" as true, we may infer x as true. We may also infer y as true. So, we can infer ¬P as true, as well as (P∨Q) as true. Assume P true. Assume ¬Q true. Then since we have ¬P and P true, we may discharge the negation and infer Q. So, (P→Q) holds true. Suppose Q true. Then Q holds true. So, we can infer (Q→Q) holds true. Since (P∨Q), (P→Q), and (Q→Q) hold true, it follows that Q holds true. Since [¬P∧(P∨Q)] comes as the only assumption still in place, we may infer {[¬P∧(P∨Q)]→Q} as true as desired.
Via Polish notation, (P∨Q) can get rewritten as Apq, [¬P∧(P∨Q)] can get rewritten as KNpApq, and {[¬P∧(P∨Q)]→Q} can get rewritten as CKNpApqq. We can then use the following axioms to prove CKNpApqq as a theorem. By a relevant soundness meta-theorem, we'll have CKNpApqq as a tautology also.
A1 CpCqp - recursive variable prefixing - RVP
A2 CCpCqrCCpqCpr - self-distribution - SD
A3 CCNpKqNqp - negation out - No
A4 CKpqp - conjunction out left - Kol
A5 CKpqq - conjunction out right - Kor
A6 CpCqKpq - conjunction in - Ki
A7 CCpqCCrqCAprq - disjunction out - Ao
Via the relevant deduction meta-theorem which SD and RVP enable, we have conditional introduction as a derivable rule of inference, which I'll denote as Ci. The only other rule of inference I'll use is C-detachment or C-d
{C$alpha$$beta$, $alpha$} $vdash$ $beta$.
1 hypothesis | KNpApq
2 Kol | CKNpApqNp
3 C-d 2, 1 | Np
4 Kor | CKNpApqApq
5 C-d 4, 1 | Apq
6 hypothesis || p
7 hypothesis ||| Nq
8 Ki ||| CpCNpKpNp
9 C-d 8, 6 ||| CNpKpNp
10 C-d 9, 3 ||| KpNp
11 Ci 7-10 || CNqKpNp
12 No || CCNqKpNpq
13 C-d 12, 11 || q
14 Ci 6-13 | Cpq
15 hypothesis || q
16 Ci 15-15 | Cqq
17 Ao | CCpqCCqqCApqq
18 C-d 17, 14 | CCqqCApqq
19 C-d 18, 16 | CApqq
20 C-d 19, 5 | q
21 Ci 1-20 CKNpApqq.
answered Nov 8 '13 at 17:36
Doug SpoonwoodDoug Spoonwood
8,14212244
$endgroup$
Assume [¬P∧(P∨Q)]. From "both x and y" as true, we may infer x as true. We may also infer y as true. So, we can infer ¬P as true, as well as (P∨Q) as true. Assume P true. Assume ¬Q true. Then since we have ¬P and P true, we may discharge the negation and infer Q. So, (P→Q) holds true. Suppose Q true. Then Q holds true. So, we can infer (Q→Q) holds true. Since (P∨Q), (P→Q), and (Q→Q) hold true, it follows that Q holds true. Since [¬P∧(P∨Q)] comes as the only assumption still in place, we may infer {[¬P∧(P∨Q)]→Q} as true as desired.
Via Polish notation, (P∨Q) can get rewritten as Apq, [¬P∧(P∨Q)] can get rewritten as KNpApq, and {[¬P∧(P∨Q)]→Q} can get rewritten as CKNpApqq. We can then use the following axioms to prove CKNpApqq as a theorem. By a relevant soundness meta-theorem, we'll have CKNpApqq as a tautology also.
A1 CpCqp - recursive variable prefixing - RVP
A2 CCpCqrCCpqCpr - self-distribution - SD
A3 CCNpKqNqp - negation out - No
A4 CKpqp - conjunction out left - Kol
A5 CKpqq - conjunction out right - Kor
A6 CpCqKpq - conjunction in - Ki
A7 CCpqCCrqCAprq - disjunction out - Ao
Via the relevant deduction meta-theorem which SD and RVP enable, we have conditional introduction as a derivable rule of inference, which I'll denote as Ci. The only other rule of inference I'll use is C-detachment or C-d
{C$alpha$$beta$, $alpha$} $vdash$ $beta$.
1 hypothesis | KNpApq
2 Kol | CKNpApqNp
3 C-d 2, 1 | Np
4 Kor | CKNpApqApq
5 C-d 4, 1 | Apq
6 hypothesis || p
7 hypothesis ||| Nq
8 Ki ||| CpCNpKpNp
9 C-d 8, 6 ||| CNpKpNp
10 C-d 9, 3 ||| KpNp
11 Ci 7-10 || CNqKpNp
12 No || CCNqKpNpq
13 C-d 12, 11 || q
14 Ci 6-13 | Cpq
15 hypothesis || q
16 Ci 15-15 | Cqq
17 Ao | CCpqCCqqCApqq
18 C-d 17, 14 | CCqqCApqq
19 C-d 18, 16 | CApqq
20 C-d 19, 5 | q
21 Ci 1-20 CKNpApqq.
answered Nov 8 '13 at 17:36
Doug SpoonwoodDoug Spoonwood
8,14212244
answered Nov 8 '13 at 17:36
Doug SpoonwoodDoug Spoonwood
8,14212244
answered Nov 8 '13 at 17:36
Doug SpoonwoodDoug Spoonwood
8,14212244
answered Nov 8 '13 at 17:36
Doug SpoonwoodDoug Spoonwood
8,14212244
8,14212244
add a comment |
add a comment |
$begingroup$
[~p^(pvq)]->q
[pv(~p^~q)]vq
[(pv~p)^(pv~q)]vq
[T^(pv~q)]vq
(pv~q)vq
pvT
T
======================
Therefore its a tautology^^
answered Jul 5 '15 at 13:01
Romeo Bantugan Jr.Romeo Bantugan Jr.
1
$endgroup$
add a comment |
$begingroup$
[~p^(pvq)]->q
[pv(~p^~q)]vq
[(pv~p)^(pv~q)]vq
[T^(pv~q)]vq
(pv~q)vq
pvT
T
======================
Therefore its a tautology^^
answered Jul 5 '15 at 13:01
Romeo Bantugan Jr.Romeo Bantugan Jr.
1
$endgroup$
add a comment |
$begingroup$
[~p^(pvq)]->q
[pv(~p^~q)]vq
[(pv~p)^(pv~q)]vq
[T^(pv~q)]vq
(pv~q)vq
pvT
T
======================
Therefore its a tautology^^
answered Jul 5 '15 at 13:01
Romeo Bantugan Jr.Romeo Bantugan Jr.
1
$endgroup$
[~p^(pvq)]->q
[pv(~p^~q)]vq
[(pv~p)^(pv~q)]vq
[T^(pv~q)]vq
(pv~q)vq
pvT
T
======================
Therefore its a tautology^^
answered Jul 5 '15 at 13:01
Romeo Bantugan Jr.Romeo Bantugan Jr.
1
answered Jul 5 '15 at 13:01
Romeo Bantugan Jr.Romeo Bantugan Jr.
1
answered Jul 5 '15 at 13:01
Romeo Bantugan Jr.Romeo Bantugan Jr.
1
answered Jul 5 '15 at 13:01
Romeo Bantugan Jr.Romeo Bantugan Jr.
1
1
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%2f554593%2fhow-do-i-prove-that-%25c2%25acp-%25e2%2588%25a7-p-%25e2%2588%25a8-q-%25e2%2586%2592-q-is-tautology-without-using-truth-tables%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$
You should be able to use distributive property.
$endgroup$
– MasterOfBinary
Nov 6 '13 at 17:48
$begingroup$
In the final paragraph, I think you meant to ask if there is a way of proving the full statement is always true, not just the portion before the arrow.
$endgroup$
– Barry Cipra
Nov 6 '13 at 18:25
$begingroup$
@MasterOfBinary Why bother with the distributive property for this question?
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:26
$begingroup$
@MasterOfBinary Because it involves properties of two operations. So, you have to understand how logical operations interact to some extent. Consequently, using the distributive property may well require more understanding than you need for solving this problem, and perhaps we should try to solve such problems from a position of as little knowledge as possible. If you're doing things from "the ground-up" you'd have to prove the relevant distributive property first. That may well require more work than other sorts of solutions.
$endgroup$
– Doug Spoonwood
Nov 8 '13 at 16:49
$begingroup$
@DougSpoonwood You can simplify the left side to get $neg P wedge Q$, which implies $Q$.
$endgroup$
– MasterOfBinary
Nov 8 '13 at 16:54