tableau calculus for system KValidity of LTL formulas in a given transition systemDecidability of normal modal logicsTruth Conditions for Modal LogicFinitary assignment functions and typed modal languagesConstructing a path of a fixed finite lengthPublic announcement logic - inclusion of the necessitation ruleI am looking for a soundness, completeness and consistency proof for this particular $S5$ calculus.A sequent calculus proofApplying the necessitation rule in semantic tableauxModal logic — eliminating modal operators in a tableau calculus by introducing a fresh world-splitting variable

How to read the value of this capacitor?

Can I use USB data pins as power source

Existence of subset with given Hausdorff dimension

Recruiter wants very extensive technical details about all of my previous work

How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?

how to write formula in word in latex

Is a party consisting of only a bard, a cleric, and a warlock functional long-term?

Why would a flight no longer considered airworthy be redirected like this?

Why Choose Less Effective Armour Types?

Why do passenger jet manufacturers design their planes with stall prevention systems?

In a future war, an old lady is trying to raise a boy but one of the weapons has made everyone deaf

Did Ender ever learn that he killed Stilson and/or Bonzo?

How Could an Airship Be Repaired Mid-Flight

Can someone explain to me where this proof goes wrong? (Twin Prime Conjecture)

How to create the Curved texte?

Dice rolling probability game

Why one should not leave fingerprints on bulbs and plugs?

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

How to use deus ex machina safely?

How do I hide Chekhov's Gun?

Do I need life insurance if I can cover my own funeral costs?

Are all passive ability checks floors for active ability checks?

Why doesn't using two cd commands in bash script execute the second command?

Time travel from stationary position?



tableau calculus for system K


Validity of LTL formulas in a given transition systemDecidability of normal modal logicsTruth Conditions for Modal LogicFinitary assignment functions and typed modal languagesConstructing a path of a fixed finite lengthPublic announcement logic - inclusion of the necessitation ruleI am looking for a soundness, completeness and consistency proof for this particular $S5$ calculus.A sequent calculus proofApplying the necessitation rule in semantic tableauxModal logic — eliminating modal operators in a tableau calculus by introducing a fresh world-splitting variable













0












$begingroup$


How do you decide whether a potential rule is allowed or not for a tableaux calculus for a given modal logic such as system K?



In particular, I'm curious whether this rule:



$$ fracsquare A_1; square A_2; dots; square A_n; lozenge BA_1; A_2; dots A_n; B tagK $$



Can be replaced with a different one that leaves all statements headed by a modal operator except for $D$ untouched.



$$ fraclozenge A_1cdotslozenge A_n ; square B_1 cdots square B_n; C_1 cdots C_n ; lozenge Dlozenge A_1 cdots lozenge A_n; square B_1 cdots square B_n; D tagFAKE-K $$



And, moreover, I'm curious if there's a way to think about the rules in this sort of proof calculus so that they fall directly out of the presentation of a given modal logic.




I'm trying to get a better understanding of set-labeled tableau calculi. Most of the diagrams in the Wikipedia article on the method of analytic tableaux show non-set-labelled calculi, which are more compact because nodes "above you" in the tree are accessible for forming contradictions.



Here's a proof of the consequentia mirabilis in propositional logic (101), written in a modified form of Polish notation with ! as negation instead of N.



Figure 101
Tableau for consequentia mirabilis

Goal: CC!aaa
Goal: A!A!!aaa
Goal: A!Aaaa
Goal: AK!a!aa
Negated Goal: KAaa!a

KAaa!a
|
Aaa,!a
/
a,!a a,!a
| |
⊥ ⊥


I then tried to create a tableau for the distribution axiom of system K (102).



I deliberately avoided using rule K to eliminate the possibility operator at (103) and instead retained the outermost connectives as is permitted by (FAKE-K). At 104 and 105, I used a statement headed by necessity to get a fact about the current world.



Figure 102
Tableau for distribution axiom in system K

Goal: CLCpqCLpLq
Goal: A!LA!pqA!LpLq
Goal: AMKp!qA!LpLq
Goal: AMKp!qAM!pLq
Negated Goal: KLA!pqKLpM!q

KLA!pqKLpM!q
|
LA!pq,KLpM!q
|
LA!pq,Lp,M!q
|
LA!pq,Lp,q (103)
|
LA!pq,A!pq,Lp,q (104)
|
LA!pq,A!pq,Lp,p,q (105)
/
LA!pq,!p,Lp,p,q LA!pq,q,Lp,p,q
| |
⊥ ⊥


There's a helpful rule for dealing with the possibly operator (M) written schematically in the section of the same article on set-labeling tableau for modal logic. Even though the article calls this kind of tableau set-labeling and the verbose kind of tableau for propositional logic set-labeled, I think it's reasonable to consider them the same kind of proof calculus.



The rule K looks like this (K). It's immediately clear what the rule means intuitively: you're entering a possible world. You are allowed to strip away one possibility operator ... for a price. The other conditions in your set must all have $square$/L as their top-level connective, this connective is then removed when entering the possible world.



$$ fracsquare A_1; square A_2; dots; square A_n; lozenge BA_1; A_2; dots A_n; B tagK $$



However, there's an alternative way to formulate this rule (FAKE-K). In FAKE-K, you get to remove one possibility operator when entering a possible world, but you don't impose any preconditions on the other elements of the set. Instead, you drop any expressions that are not headed by a modal operator. Expressions headed by a modal operator are retained regardless of whether that modal operator is $lozenge$ or $square$.



$$ fraclozenge A_1cdotslozenge A_n ; square B_1 cdots square B_n; C_1 cdots C_n ; lozenge Dlozenge A_1 cdots lozenge A_n; square B_1 cdots square B_n; D tagFAKE-K $$



I'm curious whether (FAKE-K) results in a more powerful system and therefore results in something that isn't a proof calculus for system K. The intuition behind it is that resolving a possibility operator removes all of the statements that refer to the currently focused world, but all of the statements that do not make reference to the currently focused world untouched except for $D$. Since $D$'s possibility operator is removed, repeatedly applying rule (FAKE-K) does not allow us to enter a world where multiple expressions governed by possibility are satisfied simultaneously.










share|cite|improve this question









$endgroup$
















    0












    $begingroup$


    How do you decide whether a potential rule is allowed or not for a tableaux calculus for a given modal logic such as system K?



    In particular, I'm curious whether this rule:



    $$ fracsquare A_1; square A_2; dots; square A_n; lozenge BA_1; A_2; dots A_n; B tagK $$



    Can be replaced with a different one that leaves all statements headed by a modal operator except for $D$ untouched.



    $$ fraclozenge A_1cdotslozenge A_n ; square B_1 cdots square B_n; C_1 cdots C_n ; lozenge Dlozenge A_1 cdots lozenge A_n; square B_1 cdots square B_n; D tagFAKE-K $$



    And, moreover, I'm curious if there's a way to think about the rules in this sort of proof calculus so that they fall directly out of the presentation of a given modal logic.




    I'm trying to get a better understanding of set-labeled tableau calculi. Most of the diagrams in the Wikipedia article on the method of analytic tableaux show non-set-labelled calculi, which are more compact because nodes "above you" in the tree are accessible for forming contradictions.



    Here's a proof of the consequentia mirabilis in propositional logic (101), written in a modified form of Polish notation with ! as negation instead of N.



    Figure 101
    Tableau for consequentia mirabilis

    Goal: CC!aaa
    Goal: A!A!!aaa
    Goal: A!Aaaa
    Goal: AK!a!aa
    Negated Goal: KAaa!a

    KAaa!a
    |
    Aaa,!a
    /
    a,!a a,!a
    | |
    ⊥ ⊥


    I then tried to create a tableau for the distribution axiom of system K (102).



    I deliberately avoided using rule K to eliminate the possibility operator at (103) and instead retained the outermost connectives as is permitted by (FAKE-K). At 104 and 105, I used a statement headed by necessity to get a fact about the current world.



    Figure 102
    Tableau for distribution axiom in system K

    Goal: CLCpqCLpLq
    Goal: A!LA!pqA!LpLq
    Goal: AMKp!qA!LpLq
    Goal: AMKp!qAM!pLq
    Negated Goal: KLA!pqKLpM!q

    KLA!pqKLpM!q
    |
    LA!pq,KLpM!q
    |
    LA!pq,Lp,M!q
    |
    LA!pq,Lp,q (103)
    |
    LA!pq,A!pq,Lp,q (104)
    |
    LA!pq,A!pq,Lp,p,q (105)
    /
    LA!pq,!p,Lp,p,q LA!pq,q,Lp,p,q
    | |
    ⊥ ⊥


    There's a helpful rule for dealing with the possibly operator (M) written schematically in the section of the same article on set-labeling tableau for modal logic. Even though the article calls this kind of tableau set-labeling and the verbose kind of tableau for propositional logic set-labeled, I think it's reasonable to consider them the same kind of proof calculus.



    The rule K looks like this (K). It's immediately clear what the rule means intuitively: you're entering a possible world. You are allowed to strip away one possibility operator ... for a price. The other conditions in your set must all have $square$/L as their top-level connective, this connective is then removed when entering the possible world.



    $$ fracsquare A_1; square A_2; dots; square A_n; lozenge BA_1; A_2; dots A_n; B tagK $$



    However, there's an alternative way to formulate this rule (FAKE-K). In FAKE-K, you get to remove one possibility operator when entering a possible world, but you don't impose any preconditions on the other elements of the set. Instead, you drop any expressions that are not headed by a modal operator. Expressions headed by a modal operator are retained regardless of whether that modal operator is $lozenge$ or $square$.



    $$ fraclozenge A_1cdotslozenge A_n ; square B_1 cdots square B_n; C_1 cdots C_n ; lozenge Dlozenge A_1 cdots lozenge A_n; square B_1 cdots square B_n; D tagFAKE-K $$



    I'm curious whether (FAKE-K) results in a more powerful system and therefore results in something that isn't a proof calculus for system K. The intuition behind it is that resolving a possibility operator removes all of the statements that refer to the currently focused world, but all of the statements that do not make reference to the currently focused world untouched except for $D$. Since $D$'s possibility operator is removed, repeatedly applying rule (FAKE-K) does not allow us to enter a world where multiple expressions governed by possibility are satisfied simultaneously.










    share|cite|improve this question









    $endgroup$














      0












      0








      0





      $begingroup$


      How do you decide whether a potential rule is allowed or not for a tableaux calculus for a given modal logic such as system K?



      In particular, I'm curious whether this rule:



      $$ fracsquare A_1; square A_2; dots; square A_n; lozenge BA_1; A_2; dots A_n; B tagK $$



      Can be replaced with a different one that leaves all statements headed by a modal operator except for $D$ untouched.



      $$ fraclozenge A_1cdotslozenge A_n ; square B_1 cdots square B_n; C_1 cdots C_n ; lozenge Dlozenge A_1 cdots lozenge A_n; square B_1 cdots square B_n; D tagFAKE-K $$



      And, moreover, I'm curious if there's a way to think about the rules in this sort of proof calculus so that they fall directly out of the presentation of a given modal logic.




      I'm trying to get a better understanding of set-labeled tableau calculi. Most of the diagrams in the Wikipedia article on the method of analytic tableaux show non-set-labelled calculi, which are more compact because nodes "above you" in the tree are accessible for forming contradictions.



      Here's a proof of the consequentia mirabilis in propositional logic (101), written in a modified form of Polish notation with ! as negation instead of N.



      Figure 101
      Tableau for consequentia mirabilis

      Goal: CC!aaa
      Goal: A!A!!aaa
      Goal: A!Aaaa
      Goal: AK!a!aa
      Negated Goal: KAaa!a

      KAaa!a
      |
      Aaa,!a
      /
      a,!a a,!a
      | |
      ⊥ ⊥


      I then tried to create a tableau for the distribution axiom of system K (102).



      I deliberately avoided using rule K to eliminate the possibility operator at (103) and instead retained the outermost connectives as is permitted by (FAKE-K). At 104 and 105, I used a statement headed by necessity to get a fact about the current world.



      Figure 102
      Tableau for distribution axiom in system K

      Goal: CLCpqCLpLq
      Goal: A!LA!pqA!LpLq
      Goal: AMKp!qA!LpLq
      Goal: AMKp!qAM!pLq
      Negated Goal: KLA!pqKLpM!q

      KLA!pqKLpM!q
      |
      LA!pq,KLpM!q
      |
      LA!pq,Lp,M!q
      |
      LA!pq,Lp,q (103)
      |
      LA!pq,A!pq,Lp,q (104)
      |
      LA!pq,A!pq,Lp,p,q (105)
      /
      LA!pq,!p,Lp,p,q LA!pq,q,Lp,p,q
      | |
      ⊥ ⊥


      There's a helpful rule for dealing with the possibly operator (M) written schematically in the section of the same article on set-labeling tableau for modal logic. Even though the article calls this kind of tableau set-labeling and the verbose kind of tableau for propositional logic set-labeled, I think it's reasonable to consider them the same kind of proof calculus.



      The rule K looks like this (K). It's immediately clear what the rule means intuitively: you're entering a possible world. You are allowed to strip away one possibility operator ... for a price. The other conditions in your set must all have $square$/L as their top-level connective, this connective is then removed when entering the possible world.



      $$ fracsquare A_1; square A_2; dots; square A_n; lozenge BA_1; A_2; dots A_n; B tagK $$



      However, there's an alternative way to formulate this rule (FAKE-K). In FAKE-K, you get to remove one possibility operator when entering a possible world, but you don't impose any preconditions on the other elements of the set. Instead, you drop any expressions that are not headed by a modal operator. Expressions headed by a modal operator are retained regardless of whether that modal operator is $lozenge$ or $square$.



      $$ fraclozenge A_1cdotslozenge A_n ; square B_1 cdots square B_n; C_1 cdots C_n ; lozenge Dlozenge A_1 cdots lozenge A_n; square B_1 cdots square B_n; D tagFAKE-K $$



      I'm curious whether (FAKE-K) results in a more powerful system and therefore results in something that isn't a proof calculus for system K. The intuition behind it is that resolving a possibility operator removes all of the statements that refer to the currently focused world, but all of the statements that do not make reference to the currently focused world untouched except for $D$. Since $D$'s possibility operator is removed, repeatedly applying rule (FAKE-K) does not allow us to enter a world where multiple expressions governed by possibility are satisfied simultaneously.










      share|cite|improve this question









      $endgroup$




      How do you decide whether a potential rule is allowed or not for a tableaux calculus for a given modal logic such as system K?



      In particular, I'm curious whether this rule:



      $$ fracsquare A_1; square A_2; dots; square A_n; lozenge BA_1; A_2; dots A_n; B tagK $$



      Can be replaced with a different one that leaves all statements headed by a modal operator except for $D$ untouched.



      $$ fraclozenge A_1cdotslozenge A_n ; square B_1 cdots square B_n; C_1 cdots C_n ; lozenge Dlozenge A_1 cdots lozenge A_n; square B_1 cdots square B_n; D tagFAKE-K $$



      And, moreover, I'm curious if there's a way to think about the rules in this sort of proof calculus so that they fall directly out of the presentation of a given modal logic.




      I'm trying to get a better understanding of set-labeled tableau calculi. Most of the diagrams in the Wikipedia article on the method of analytic tableaux show non-set-labelled calculi, which are more compact because nodes "above you" in the tree are accessible for forming contradictions.



      Here's a proof of the consequentia mirabilis in propositional logic (101), written in a modified form of Polish notation with ! as negation instead of N.



      Figure 101
      Tableau for consequentia mirabilis

      Goal: CC!aaa
      Goal: A!A!!aaa
      Goal: A!Aaaa
      Goal: AK!a!aa
      Negated Goal: KAaa!a

      KAaa!a
      |
      Aaa,!a
      /
      a,!a a,!a
      | |
      ⊥ ⊥


      I then tried to create a tableau for the distribution axiom of system K (102).



      I deliberately avoided using rule K to eliminate the possibility operator at (103) and instead retained the outermost connectives as is permitted by (FAKE-K). At 104 and 105, I used a statement headed by necessity to get a fact about the current world.



      Figure 102
      Tableau for distribution axiom in system K

      Goal: CLCpqCLpLq
      Goal: A!LA!pqA!LpLq
      Goal: AMKp!qA!LpLq
      Goal: AMKp!qAM!pLq
      Negated Goal: KLA!pqKLpM!q

      KLA!pqKLpM!q
      |
      LA!pq,KLpM!q
      |
      LA!pq,Lp,M!q
      |
      LA!pq,Lp,q (103)
      |
      LA!pq,A!pq,Lp,q (104)
      |
      LA!pq,A!pq,Lp,p,q (105)
      /
      LA!pq,!p,Lp,p,q LA!pq,q,Lp,p,q
      | |
      ⊥ ⊥


      There's a helpful rule for dealing with the possibly operator (M) written schematically in the section of the same article on set-labeling tableau for modal logic. Even though the article calls this kind of tableau set-labeling and the verbose kind of tableau for propositional logic set-labeled, I think it's reasonable to consider them the same kind of proof calculus.



      The rule K looks like this (K). It's immediately clear what the rule means intuitively: you're entering a possible world. You are allowed to strip away one possibility operator ... for a price. The other conditions in your set must all have $square$/L as their top-level connective, this connective is then removed when entering the possible world.



      $$ fracsquare A_1; square A_2; dots; square A_n; lozenge BA_1; A_2; dots A_n; B tagK $$



      However, there's an alternative way to formulate this rule (FAKE-K). In FAKE-K, you get to remove one possibility operator when entering a possible world, but you don't impose any preconditions on the other elements of the set. Instead, you drop any expressions that are not headed by a modal operator. Expressions headed by a modal operator are retained regardless of whether that modal operator is $lozenge$ or $square$.



      $$ fraclozenge A_1cdotslozenge A_n ; square B_1 cdots square B_n; C_1 cdots C_n ; lozenge Dlozenge A_1 cdots lozenge A_n; square B_1 cdots square B_n; D tagFAKE-K $$



      I'm curious whether (FAKE-K) results in a more powerful system and therefore results in something that isn't a proof calculus for system K. The intuition behind it is that resolving a possibility operator removes all of the statements that refer to the currently focused world, but all of the statements that do not make reference to the currently focused world untouched except for $D$. Since $D$'s possibility operator is removed, repeatedly applying rule (FAKE-K) does not allow us to enter a world where multiple expressions governed by possibility are satisfied simultaneously.







      modal-logic






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Mar 11 at 20:41









      Gregory NisbetGregory Nisbet

      756612




      756612




















          0






          active

          oldest

          votes











          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%2f3144213%2ftableau-calculus-for-system-k%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          0






          active

          oldest

          votes








          0






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes















          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.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3144213%2ftableau-calculus-for-system-k%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

          How should I support this large drywall patch? Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How do I cover large gaps in drywall?How do I keep drywall around a patch from crumbling?Can I glue a second layer of drywall?How to patch long strip on drywall?Large drywall patch: how to avoid bulging seams?Drywall Mesh Patch vs. Bulge? To remove or not to remove?How to fix this drywall job?Prep drywall before backsplashWhat's the best way to fix this horrible drywall patch job?Drywall patching using 3M Patch Plus Primer

          random experiment with two different functions on unit interval Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Random variable and probability space notionsRandom Walk with EdgesFinding functions where the increase over a random interval is Poisson distributedNumber of days until dayCan an observed event in fact be of zero probability?Unit random processmodels of coins and uniform distributionHow to get the number of successes given $n$ trials , probability $P$ and a random variable $X$Absorbing Markov chain in a computer. Is “almost every” turned into always convergence in computer executions?Stopped random walk is not uniformly integrable

          Lowndes Grove History Architecture References Navigation menu32°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661132°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661178002500"National Register Information System"Historic houses of South Carolina"Lowndes Grove""+32° 48' 6.00", −79° 57' 58.00""Lowndes Grove, Charleston County (260 St. Margaret St., Charleston)""Lowndes Grove"The Charleston ExpositionIt Happened in South Carolina"Lowndes Grove (House), Saint Margaret Street & Sixth Avenue, Charleston, Charleston County, SC(Photographs)"Plantations of the Carolina Low Countrye