Is the following formula a tautology?
$begingroup$
In order to find out whether this formula is a tautology, I'm creating a semantic tree for its negation. If all of the branches are a contradiction then the formula is a tautology.
Formula: !(A => B) <=> (!B => !A).
This is how I do it: !(!(A => B) <=> (!B => !A))
|=|
!(( (A ∧ !B) => (B ∨ !A) ) ∧ ( (B ∨ !A) => (A ∧ !B) ))
|=|
(A ∧ !B) ∨ (!A ∨ B).
This is how my semantic tree looks like:
A
/ |
!A B !B
Which in the semantic tree is a contradiction, so the formula is a tautology. I was drawing the tree the wrong way, now I clearly see it.
logic
asked Jan 1 at 12:53
ponikoliponikoli
466
$endgroup$
add a comment |
$begingroup$
In order to find out whether this formula is a tautology, I'm creating a semantic tree for its negation. If all of the branches are a contradiction then the formula is a tautology.
Formula: !(A => B) <=> (!B => !A).
This is how I do it: !(!(A => B) <=> (!B => !A))
|=|
!(( (A ∧ !B) => (B ∨ !A) ) ∧ ( (B ∨ !A) => (A ∧ !B) ))
|=|
(A ∧ !B) ∨ (!A ∨ B).
This is how my semantic tree looks like:
A
/ |
!A B !B
Which in the semantic tree is a contradiction, so the formula is a tautology. I was drawing the tree the wrong way, now I clearly see it.
logic
asked Jan 1 at 12:53
ponikoliponikoli
466
$endgroup$
2
$begingroup$
The formula is never true. The statement on the right is equivalent to $Aimplies B$ which is the negation of the statement on the left.
$endgroup$
– John Douma
Jan 1 at 12:57
3
$begingroup$
The formula is not a tautology, because $(A to B) equiv (lnot B to lnot A)$.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 12:57
$begingroup$
But the last step in your tree is not a contradicition : with a valuation $v$ such that $v(A)=$ t and $v(B)=$ f the formula is satisfied. Thus, the tree does not close and this proves that the formula is not taut.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:05
$begingroup$
@MauroALLEGRANZA hello, I've added how I thought the semantic tree should look like and better explanation. I still don't see how this semantic tree is not a contradiction (and therefore the formula tautology)? Now I see that I draw it the wrong way...
$endgroup$
– ponikoli
Jan 1 at 13:17
$begingroup$
You have a disjunction; thus, two branches : the left one for $(A land lnot B)$ and the right one for $(lnot A lor B)$. No way to find a contradiction...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:20
add a comment |
$begingroup$
In order to find out whether this formula is a tautology, I'm creating a semantic tree for its negation. If all of the branches are a contradiction then the formula is a tautology.
Formula: !(A => B) <=> (!B => !A).
This is how I do it: !(!(A => B) <=> (!B => !A))
|=|
!(( (A ∧ !B) => (B ∨ !A) ) ∧ ( (B ∨ !A) => (A ∧ !B) ))
|=|
(A ∧ !B) ∨ (!A ∨ B).
This is how my semantic tree looks like:
A
/ |
!A B !B
Which in the semantic tree is a contradiction, so the formula is a tautology. I was drawing the tree the wrong way, now I clearly see it.
logic
asked Jan 1 at 12:53
ponikoliponikoli
466
$endgroup$
In order to find out whether this formula is a tautology, I'm creating a semantic tree for its negation. If all of the branches are a contradiction then the formula is a tautology.
Formula: !(A => B) <=> (!B => !A).
This is how I do it: !(!(A => B) <=> (!B => !A))
|=|
!(( (A ∧ !B) => (B ∨ !A) ) ∧ ( (B ∨ !A) => (A ∧ !B) ))
|=|
(A ∧ !B) ∨ (!A ∨ B).
This is how my semantic tree looks like:
A
/ |
!A B !B
Which in the semantic tree is a contradiction, so the formula is a tautology. I was drawing the tree the wrong way, now I clearly see it.
logic
logic
asked Jan 1 at 12:53
ponikoliponikoli
466
asked Jan 1 at 12:53
ponikoliponikoli
466
edited Jan 1 at 13:19
ponikoli
asked Jan 1 at 12:53
ponikoliponikoli
466
asked Jan 1 at 12:53
ponikoliponikoli
466
asked Jan 1 at 12:53
ponikoliponikoli
466
466
2
$begingroup$
The formula is never true. The statement on the right is equivalent to $Aimplies B$ which is the negation of the statement on the left.
$endgroup$
– John Douma
Jan 1 at 12:57
3
$begingroup$
The formula is not a tautology, because $(A to B) equiv (lnot B to lnot A)$.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 12:57
$begingroup$
But the last step in your tree is not a contradicition : with a valuation $v$ such that $v(A)=$ t and $v(B)=$ f the formula is satisfied. Thus, the tree does not close and this proves that the formula is not taut.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:05
$begingroup$
@MauroALLEGRANZA hello, I've added how I thought the semantic tree should look like and better explanation. I still don't see how this semantic tree is not a contradiction (and therefore the formula tautology)? Now I see that I draw it the wrong way...
$endgroup$
– ponikoli
Jan 1 at 13:17
$begingroup$
You have a disjunction; thus, two branches : the left one for $(A land lnot B)$ and the right one for $(lnot A lor B)$. No way to find a contradiction...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:20
add a comment |
2
$begingroup$
The formula is never true. The statement on the right is equivalent to $Aimplies B$ which is the negation of the statement on the left.
$endgroup$
– John Douma
Jan 1 at 12:57
3
$begingroup$
The formula is not a tautology, because $(A to B) equiv (lnot B to lnot A)$.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 12:57
$begingroup$
But the last step in your tree is not a contradicition : with a valuation $v$ such that $v(A)=$ t and $v(B)=$ f the formula is satisfied. Thus, the tree does not close and this proves that the formula is not taut.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:05
$begingroup$
@MauroALLEGRANZA hello, I've added how I thought the semantic tree should look like and better explanation. I still don't see how this semantic tree is not a contradiction (and therefore the formula tautology)? Now I see that I draw it the wrong way...
$endgroup$
– ponikoli
Jan 1 at 13:17
$begingroup$
You have a disjunction; thus, two branches : the left one for $(A land lnot B)$ and the right one for $(lnot A lor B)$. No way to find a contradiction...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:20
2
2
$begingroup$
The formula is never true. The statement on the right is equivalent to $Aimplies B$ which is the negation of the statement on the left.
$endgroup$
– John Douma
Jan 1 at 12:57
$begingroup$
The formula is never true. The statement on the right is equivalent to $Aimplies B$ which is the negation of the statement on the left.
$endgroup$
– John Douma
Jan 1 at 12:57
3
3
$begingroup$
The formula is not a tautology, because $(A to B) equiv (lnot B to lnot A)$.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 12:57
$begingroup$
The formula is not a tautology, because $(A to B) equiv (lnot B to lnot A)$.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 12:57
$begingroup$
But the last step in your tree is not a contradicition : with a valuation $v$ such that $v(A)=$ t and $v(B)=$ f the formula is satisfied. Thus, the tree does not close and this proves that the formula is not taut.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:05
$begingroup$
But the last step in your tree is not a contradicition : with a valuation $v$ such that $v(A)=$ t and $v(B)=$ f the formula is satisfied. Thus, the tree does not close and this proves that the formula is not taut.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:05
$begingroup$
@MauroALLEGRANZA hello, I've added how I thought the semantic tree should look like and better explanation. I still don't see how this semantic tree is not a contradiction (and therefore the formula tautology)? Now I see that I draw it the wrong way...
$endgroup$
– ponikoli
Jan 1 at 13:17
$begingroup$
@MauroALLEGRANZA hello, I've added how I thought the semantic tree should look like and better explanation. I still don't see how this semantic tree is not a contradiction (and therefore the formula tautology)? Now I see that I draw it the wrong way...
$endgroup$
– ponikoli
Jan 1 at 13:17
$begingroup$
You have a disjunction; thus, two branches : the left one for $(A land lnot B)$ and the right one for $(lnot A lor B)$. No way to find a contradiction...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:20
$begingroup$
You have a disjunction; thus, two branches : the left one for $(A land lnot B)$ and the right one for $(lnot A lor B)$. No way to find a contradiction...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:20
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I was drawing the tree the wrong way, the semantic three is neither contradiction nor tautology, so the formula is neither.
answered Jan 1 at 13:20
ponikoliponikoli
466
$endgroup$
$begingroup$
This is not an answer...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 16:49
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%2f3058460%2fis-the-following-formula-a-tautology%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I was drawing the tree the wrong way, the semantic three is neither contradiction nor tautology, so the formula is neither.
answered Jan 1 at 13:20
ponikoliponikoli
466
$endgroup$
$begingroup$
This is not an answer...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 16:49
add a comment |
$begingroup$
I was drawing the tree the wrong way, the semantic three is neither contradiction nor tautology, so the formula is neither.
answered Jan 1 at 13:20
ponikoliponikoli
466
$endgroup$
$begingroup$
This is not an answer...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 16:49
add a comment |
$begingroup$
I was drawing the tree the wrong way, the semantic three is neither contradiction nor tautology, so the formula is neither.
answered Jan 1 at 13:20
ponikoliponikoli
466
$endgroup$
I was drawing the tree the wrong way, the semantic three is neither contradiction nor tautology, so the formula is neither.
answered Jan 1 at 13:20
ponikoliponikoli
466
answered Jan 1 at 13:20
ponikoliponikoli
466
answered Jan 1 at 13:20
ponikoliponikoli
466
answered Jan 1 at 13:20
ponikoliponikoli
466
466
$begingroup$
This is not an answer...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 16:49
add a comment |
$begingroup$
This is not an answer...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 16:49
$begingroup$
This is not an answer...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 16:49
$begingroup$
This is not an answer...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 16:49
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%2f3058460%2fis-the-following-formula-a-tautology%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
2
$begingroup$
The formula is never true. The statement on the right is equivalent to $Aimplies B$ which is the negation of the statement on the left.
$endgroup$
– John Douma
Jan 1 at 12:57
3
$begingroup$
The formula is not a tautology, because $(A to B) equiv (lnot B to lnot A)$.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 12:57
$begingroup$
But the last step in your tree is not a contradicition : with a valuation $v$ such that $v(A)=$ t and $v(B)=$ f the formula is satisfied. Thus, the tree does not close and this proves that the formula is not taut.
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:05
$begingroup$
@MauroALLEGRANZA hello, I've added how I thought the semantic tree should look like and better explanation. I still don't see how this semantic tree is not a contradiction (and therefore the formula tautology)? Now I see that I draw it the wrong way...
$endgroup$
– ponikoli
Jan 1 at 13:17
$begingroup$
You have a disjunction; thus, two branches : the left one for $(A land lnot B)$ and the right one for $(lnot A lor B)$. No way to find a contradiction...
$endgroup$
– Mauro ALLEGRANZA
Jan 1 at 13:20