Show that the conditional statement is a tautology without using a truth table












2














I have been attempting to use identities to get to the answer but I am unable to get anywhere.
Here is the equation I am trying to prove tautological without using truth tables:



$[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$



And here is my attempt at using identities to work my way up. (a link to a page with a table of logical equivalence identities: http://en.wikipedia.org/wiki/Logical_equivalence)



$lnot [(p rightarrow q) land (q rightarrow r)] lor (p rightarrow r)$



$lnot [(lnot p lor q) land (q rightarrow r)] lor (p rightarrow r)$



$[lnot (lnot p lor q) land lnot (q rightarrow r)] lor (p rightarrow r)$



$[(pland lnot q) land (q land lnot r)] lor (p rightarrow r)$



I don't know where to go from there.










share|cite|improve this question
























  • In fourth step you did not apply the nagasion properly due to nagasion sign the AND operator will change into OR operator and then the whole question will solve very easily.
    – user620344
    Nov 27 '18 at 18:55
















2














I have been attempting to use identities to get to the answer but I am unable to get anywhere.
Here is the equation I am trying to prove tautological without using truth tables:



$[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$



And here is my attempt at using identities to work my way up. (a link to a page with a table of logical equivalence identities: http://en.wikipedia.org/wiki/Logical_equivalence)



$lnot [(p rightarrow q) land (q rightarrow r)] lor (p rightarrow r)$



$lnot [(lnot p lor q) land (q rightarrow r)] lor (p rightarrow r)$



$[lnot (lnot p lor q) land lnot (q rightarrow r)] lor (p rightarrow r)$



$[(pland lnot q) land (q land lnot r)] lor (p rightarrow r)$



I don't know where to go from there.










share|cite|improve this question
























  • In fourth step you did not apply the nagasion properly due to nagasion sign the AND operator will change into OR operator and then the whole question will solve very easily.
    – user620344
    Nov 27 '18 at 18:55














2












2








2


1





I have been attempting to use identities to get to the answer but I am unable to get anywhere.
Here is the equation I am trying to prove tautological without using truth tables:



$[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$



And here is my attempt at using identities to work my way up. (a link to a page with a table of logical equivalence identities: http://en.wikipedia.org/wiki/Logical_equivalence)



$lnot [(p rightarrow q) land (q rightarrow r)] lor (p rightarrow r)$



$lnot [(lnot p lor q) land (q rightarrow r)] lor (p rightarrow r)$



$[lnot (lnot p lor q) land lnot (q rightarrow r)] lor (p rightarrow r)$



$[(pland lnot q) land (q land lnot r)] lor (p rightarrow r)$



I don't know where to go from there.










share|cite|improve this question















I have been attempting to use identities to get to the answer but I am unable to get anywhere.
Here is the equation I am trying to prove tautological without using truth tables:



$[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$



And here is my attempt at using identities to work my way up. (a link to a page with a table of logical equivalence identities: http://en.wikipedia.org/wiki/Logical_equivalence)



$lnot [(p rightarrow q) land (q rightarrow r)] lor (p rightarrow r)$



$lnot [(lnot p lor q) land (q rightarrow r)] lor (p rightarrow r)$



$[lnot (lnot p lor q) land lnot (q rightarrow r)] lor (p rightarrow r)$



$[(pland lnot q) land (q land lnot r)] lor (p rightarrow r)$



I don't know where to go from there.







logic propositional-calculus






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 24 '15 at 21:29









Git Gud

28.7k1049100




28.7k1049100










asked Jan 24 '15 at 21:26









user11892

9828




9828












  • In fourth step you did not apply the nagasion properly due to nagasion sign the AND operator will change into OR operator and then the whole question will solve very easily.
    – user620344
    Nov 27 '18 at 18:55


















  • In fourth step you did not apply the nagasion properly due to nagasion sign the AND operator will change into OR operator and then the whole question will solve very easily.
    – user620344
    Nov 27 '18 at 18:55
















In fourth step you did not apply the nagasion properly due to nagasion sign the AND operator will change into OR operator and then the whole question will solve very easily.
– user620344
Nov 27 '18 at 18:55




In fourth step you did not apply the nagasion properly due to nagasion sign the AND operator will change into OR operator and then the whole question will solve very easily.
– user620344
Nov 27 '18 at 18:55










1 Answer
1






active

oldest

votes


















1














In your approach, you made a mistake in the derivation on the third line, it should be:
$$[lnot (lnot p lor q) lor lnot (q rightarrow r)] lor (p rightarrow r)$$



so that your fourth line becomes:



$$[(pland lnot q) lor (q land lnot r)] lor (p rightarrow r)$$



At this point, there isn't really much to be done except for a tedious case-by-case argument ("Suppose $p$ is true. [...] Now suppose $p$ is false [...].").





Let us take a step back. When proving a tautology (which is not easily seen to be so by virtue of known theorems), it is often a more productive technique to try and prove that its negation is a contradiction. The idea behind this is that if the original $phi$ is to be a tautology, then by investigating its negation $neg phi$, we will obtain stricter and stricter conditions on $p, q, r$ to allow $neg phi$ to be true, until we get to the conclusion that there are no possibilities left, i.e. that $phi$ is a tautology.



Essentially, one converts a universal check ("All interpretations yield true") to a search for an example ("Some interpretation does not yield true") -- keeping in mind that we want the latter search to be fruitless. Basically, it's easier to find the black sheep in a flock than to count the white ones. For a more detailed account of this approach, you can search for terms like semantic tableaux or analytic tableaux.





Returning to our concrete example, let us see how this approach works out. We use repeatedly the equivalences $p to q iff neg p lor q$ and $neg (p to q) iff p land neg q$:



begin{align*}
& negbig([(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )big)\
iff& (pto q)land (qto r) land neg(p to r) \
iff& (neg p lor q) land (neg q lor r) land p land neg r
end{align*}



From the last two clauses, we see that $p$ must be true and $r$ must be false. But then for $neg p lor q$ to be true, $q$ must be true as well. Similarly, $neg q$ must be true in order for $neg q lor r$ to be true as well. Hence we need $q$ to be both true and false at the same time, a contradiction.



We conclude that $[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$ is a tautology, as desired.






share|cite|improve this answer





















    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
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1118152%2fshow-that-the-conditional-statement-is-a-tautology-without-using-a-truth-table%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









    1














    In your approach, you made a mistake in the derivation on the third line, it should be:
    $$[lnot (lnot p lor q) lor lnot (q rightarrow r)] lor (p rightarrow r)$$



    so that your fourth line becomes:



    $$[(pland lnot q) lor (q land lnot r)] lor (p rightarrow r)$$



    At this point, there isn't really much to be done except for a tedious case-by-case argument ("Suppose $p$ is true. [...] Now suppose $p$ is false [...].").





    Let us take a step back. When proving a tautology (which is not easily seen to be so by virtue of known theorems), it is often a more productive technique to try and prove that its negation is a contradiction. The idea behind this is that if the original $phi$ is to be a tautology, then by investigating its negation $neg phi$, we will obtain stricter and stricter conditions on $p, q, r$ to allow $neg phi$ to be true, until we get to the conclusion that there are no possibilities left, i.e. that $phi$ is a tautology.



    Essentially, one converts a universal check ("All interpretations yield true") to a search for an example ("Some interpretation does not yield true") -- keeping in mind that we want the latter search to be fruitless. Basically, it's easier to find the black sheep in a flock than to count the white ones. For a more detailed account of this approach, you can search for terms like semantic tableaux or analytic tableaux.





    Returning to our concrete example, let us see how this approach works out. We use repeatedly the equivalences $p to q iff neg p lor q$ and $neg (p to q) iff p land neg q$:



    begin{align*}
    & negbig([(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )big)\
    iff& (pto q)land (qto r) land neg(p to r) \
    iff& (neg p lor q) land (neg q lor r) land p land neg r
    end{align*}



    From the last two clauses, we see that $p$ must be true and $r$ must be false. But then for $neg p lor q$ to be true, $q$ must be true as well. Similarly, $neg q$ must be true in order for $neg q lor r$ to be true as well. Hence we need $q$ to be both true and false at the same time, a contradiction.



    We conclude that $[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$ is a tautology, as desired.






    share|cite|improve this answer


























      1














      In your approach, you made a mistake in the derivation on the third line, it should be:
      $$[lnot (lnot p lor q) lor lnot (q rightarrow r)] lor (p rightarrow r)$$



      so that your fourth line becomes:



      $$[(pland lnot q) lor (q land lnot r)] lor (p rightarrow r)$$



      At this point, there isn't really much to be done except for a tedious case-by-case argument ("Suppose $p$ is true. [...] Now suppose $p$ is false [...].").





      Let us take a step back. When proving a tautology (which is not easily seen to be so by virtue of known theorems), it is often a more productive technique to try and prove that its negation is a contradiction. The idea behind this is that if the original $phi$ is to be a tautology, then by investigating its negation $neg phi$, we will obtain stricter and stricter conditions on $p, q, r$ to allow $neg phi$ to be true, until we get to the conclusion that there are no possibilities left, i.e. that $phi$ is a tautology.



      Essentially, one converts a universal check ("All interpretations yield true") to a search for an example ("Some interpretation does not yield true") -- keeping in mind that we want the latter search to be fruitless. Basically, it's easier to find the black sheep in a flock than to count the white ones. For a more detailed account of this approach, you can search for terms like semantic tableaux or analytic tableaux.





      Returning to our concrete example, let us see how this approach works out. We use repeatedly the equivalences $p to q iff neg p lor q$ and $neg (p to q) iff p land neg q$:



      begin{align*}
      & negbig([(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )big)\
      iff& (pto q)land (qto r) land neg(p to r) \
      iff& (neg p lor q) land (neg q lor r) land p land neg r
      end{align*}



      From the last two clauses, we see that $p$ must be true and $r$ must be false. But then for $neg p lor q$ to be true, $q$ must be true as well. Similarly, $neg q$ must be true in order for $neg q lor r$ to be true as well. Hence we need $q$ to be both true and false at the same time, a contradiction.



      We conclude that $[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$ is a tautology, as desired.






      share|cite|improve this answer
























        1












        1








        1






        In your approach, you made a mistake in the derivation on the third line, it should be:
        $$[lnot (lnot p lor q) lor lnot (q rightarrow r)] lor (p rightarrow r)$$



        so that your fourth line becomes:



        $$[(pland lnot q) lor (q land lnot r)] lor (p rightarrow r)$$



        At this point, there isn't really much to be done except for a tedious case-by-case argument ("Suppose $p$ is true. [...] Now suppose $p$ is false [...].").





        Let us take a step back. When proving a tautology (which is not easily seen to be so by virtue of known theorems), it is often a more productive technique to try and prove that its negation is a contradiction. The idea behind this is that if the original $phi$ is to be a tautology, then by investigating its negation $neg phi$, we will obtain stricter and stricter conditions on $p, q, r$ to allow $neg phi$ to be true, until we get to the conclusion that there are no possibilities left, i.e. that $phi$ is a tautology.



        Essentially, one converts a universal check ("All interpretations yield true") to a search for an example ("Some interpretation does not yield true") -- keeping in mind that we want the latter search to be fruitless. Basically, it's easier to find the black sheep in a flock than to count the white ones. For a more detailed account of this approach, you can search for terms like semantic tableaux or analytic tableaux.





        Returning to our concrete example, let us see how this approach works out. We use repeatedly the equivalences $p to q iff neg p lor q$ and $neg (p to q) iff p land neg q$:



        begin{align*}
        & negbig([(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )big)\
        iff& (pto q)land (qto r) land neg(p to r) \
        iff& (neg p lor q) land (neg q lor r) land p land neg r
        end{align*}



        From the last two clauses, we see that $p$ must be true and $r$ must be false. But then for $neg p lor q$ to be true, $q$ must be true as well. Similarly, $neg q$ must be true in order for $neg q lor r$ to be true as well. Hence we need $q$ to be both true and false at the same time, a contradiction.



        We conclude that $[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$ is a tautology, as desired.






        share|cite|improve this answer












        In your approach, you made a mistake in the derivation on the third line, it should be:
        $$[lnot (lnot p lor q) lor lnot (q rightarrow r)] lor (p rightarrow r)$$



        so that your fourth line becomes:



        $$[(pland lnot q) lor (q land lnot r)] lor (p rightarrow r)$$



        At this point, there isn't really much to be done except for a tedious case-by-case argument ("Suppose $p$ is true. [...] Now suppose $p$ is false [...].").





        Let us take a step back. When proving a tautology (which is not easily seen to be so by virtue of known theorems), it is often a more productive technique to try and prove that its negation is a contradiction. The idea behind this is that if the original $phi$ is to be a tautology, then by investigating its negation $neg phi$, we will obtain stricter and stricter conditions on $p, q, r$ to allow $neg phi$ to be true, until we get to the conclusion that there are no possibilities left, i.e. that $phi$ is a tautology.



        Essentially, one converts a universal check ("All interpretations yield true") to a search for an example ("Some interpretation does not yield true") -- keeping in mind that we want the latter search to be fruitless. Basically, it's easier to find the black sheep in a flock than to count the white ones. For a more detailed account of this approach, you can search for terms like semantic tableaux or analytic tableaux.





        Returning to our concrete example, let us see how this approach works out. We use repeatedly the equivalences $p to q iff neg p lor q$ and $neg (p to q) iff p land neg q$:



        begin{align*}
        & negbig([(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )big)\
        iff& (pto q)land (qto r) land neg(p to r) \
        iff& (neg p lor q) land (neg q lor r) land p land neg r
        end{align*}



        From the last two clauses, we see that $p$ must be true and $r$ must be false. But then for $neg p lor q$ to be true, $q$ must be true as well. Similarly, $neg q$ must be true in order for $neg q lor r$ to be true as well. Hence we need $q$ to be both true and false at the same time, a contradiction.



        We conclude that $[(prightarrow q) land (q rightarrow r)] rightarrow (p rightarrow r )$ is a tautology, as desired.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Jan 24 '15 at 22:56









        Lord_Farin

        15.5k636108




        15.5k636108






























            draft saved

            draft discarded




















































            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.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • 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.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1118152%2fshow-that-the-conditional-statement-is-a-tautology-without-using-a-truth-table%23new-answer', 'question_page');
            }
            );

            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







            Popular posts from this blog

            Aardman Animations

            Are they similar matrix

            “minimization” problem in Euclidean space related to orthonormal basis