Výrokový kalkul - Propositional calculus

Výrokový počet je větev logiky . Říká se mu také výroková logika , logika výroků , větný kalkul , větná logika nebo někdy logika nulového řádu . Zabývá se tvrzeními (která mohou být pravdivá i nepravdivá) a vztahy mezi tvrzeními, včetně konstrukce argumentů na jejich základě. Složené věty jsou tvořeny spojováním výroků logickými spojkami . Propozice, které neobsahují žádná logická spojení, se nazývají atomické propozice.

Na rozdíl od logiky prvního řádu se výroková logika nezabývá nelogickými objekty, predikáty o nich nebo kvantifikátory . Celá logika výrokové logiky je však zahrnuta v logice prvního řádu a logikách vyššího řádu. V tomto smyslu je výroková logika základem logiky prvního řádu a logiky vyššího řádu.

Vysvětlení

Logická spojení se nacházejí v přirozených jazycích. V angličtině jsou například některé příklady „a“ ​​( spojka ), „nebo“ ( disjunkce ), „ne“ ( negace ) a „pokud“ (ale pouze pokud jsou použity k označení podmíněnosti materiálu ).

Následuje příklad velmi jednoduchého odvození v rámci výrokové logiky:

Předpoklad 1: Pokud prší, je zataženo.
Předpoklad 2: Prší.
Závěr: Je zataženo.

Oba premisy a závěr jsou propozice. Prostory jsou považovány za samozřejmost a s použitím modus ponens ( odvozovací pravidlo ) následuje závěr.

Jelikož výroková logika se nezabývá strukturou výroků za bodem, kde je již nelze rozložit pomocí logických spojek, lze tento závěr přepsat nahrazením těchto atomových příkazů písmeny výroků, které jsou interpretovány jako proměnné představující příkazy:

Předpoklad 1:
Předpoklad 2:
Závěr:

Totéž lze stručně říci následujícím způsobem:

Když je P interpretováno jako „prší“ a Q jako „je zataženo“, je vidět, že výše uvedené symbolické výrazy přesně odpovídají původnímu výrazu v přirozeném jazyce. Nejen to, ale budou také korespondovat s jakýmkoli jiným odvozením tohoto formuláře , které bude platné na stejném základě, jako je toto odvození.

Výrokové logiky lze studovat pomocí formálního systému , ve kterém formule příslušníky formálního jazyka může být interpretována reprezentovat návrhy . Systém z axiomů a odvozovacích pravidel umožňuje určité vzorce, které mají být odvozeny. Tyto odvozené vzorce se nazývají věty a lze je interpretovat jako pravdivé výroky. Sestrojená posloupnost takovýchto vzorců je známá jako odvození nebo důkaz a poslední vzorec posloupnosti je věta. Odvození lze interpretovat jako důkaz tvrzení reprezentovaného větou.

Je-li formální systém používá pro reprezentaci formální logiku, tak prohlášení dopisy (obvykle velké římské písmena jako například , a ) jsou zastoupeny přímo. Propozice přirozeného jazyka, které vznikají při jejich interpretaci, jsou mimo rozsah systému a vztah mezi formálním systémem a jeho interpretací je rovněž mimo samotný formální systém.

V klasické výrokové logice s funkční pravdou jsou vzorce interpretovány tak, že mají přesně jednu ze dvou možných hodnot pravdy , pravdivostní hodnotu pravdy nebo pravdivostní hodnotu nepravdy . Booleova logika a právo vyloučeného středa byly dodržovány. Pravdově funkční výroková logika definovaná jako taková a systémy s ní izomorfní jsou považovány za logiku nulového řádu . Jsou však také možné alternativní výrokové logiky. Více viz Další logické kameny níže.

Dějiny

Ačkoli propoziční logika (která je zaměnitelná s propozičním kalkulem) byla naznačována dřívějšími filozofy, byla ve 3. století př. N. L. Chrysippem rozvinuta do formální logiky ( stoická logika ) a rozšířena jeho nástupcem Stoicsem . Logika byla zaměřena na věty . Tento pokrok se lišil od tradiční sylogistické logiky , která byla zaměřena na termíny . Většina původních spisů však byla ztracena a výroková logika vyvinutá stoiky již nebyla ve starověku chápána. V důsledku toho byl systém v podstatě znovu objeven Peterem Abelardem ve 12. století.

Výroková logika byla nakonec upřesněna pomocí symbolické logiky . Matematik 17./18. století Gottfried Leibniz byl připočítán jako zakladatel symbolické logiky pro svou práci s poměrovým poměrem počtu . Ačkoli jeho práce byla první svého druhu, byla širší logické komunitě neznámá. V důsledku toho mnoho pokroků dosažených Leibnizem bylo obnoveno logiky jako George Boole a Augustus De Morgan - zcela nezávislí na Leibnizovi.

Stejně jako výrokovou logiku lze považovat za pokrok z dřívější syllogistické logiky, za predikát z dřívější výrokové logiky lze považovat také predikátovou logiku Gottlob Frege . Jeden autor popisuje predikátovou logiku jako kombinaci „charakteristických rysů sylogistické logiky a výrokové logiky“. V důsledku toho predikátová logika zahájila novou éru v historii logiky; po Fregeovi však bylo dosaženo pokroku v propoziční logice, včetně přirozené dedukce , stromů pravdy a pravdivostních tabulek . Přirozenou dedukci vymysleli Gerhard Gentzen a Jan Łukasiewicz . Stromy pravdy vynalezl Evert Willem Beth . Vynález pravdivostních tabulek má však nejistou atribuci.

V dílech Frege a Bertranda Russella jsou myšlenky, které mají vliv na vynález tabulek pravdy. Vlastní tabulková struktura (formátovaná jako tabulka) je obecně připisována buď Ludwigu Wittgensteinovi nebo Emilu Postovi (nebo oběma nezávisle). Kromě Fregeho a Russella patří k dalším, kterým se připisují myšlenky předcházející pravdivé tabulky, Philo, Boole, Charles Sanders Peirce a Ernst Schröder . Mezi další zásluhy o tabulkovou strukturu patří Jan Łukasiewicz , Alfred North Whitehead , William Stanley Jevons , John Venn a Clarence Irving Lewis . Nakonec někteří dospěli k závěru, jako John Shosky, že „Není zdaleka jasné, že by někdo měl dostat titul„ vynálezce “tabulek pravdy.“.

Terminologie

Obecně řečeno, kalkul je formální systém, který se skládá ze sady syntaktických výrazů ( dobře formulované formule ), význačné podmnožiny těchto výrazů (axiomů) a souboru formálních pravidel, která definují konkrétní binární vztah , určený být interpretován jako logická ekvivalence na prostoru výrazů.

Když je formálním systémem zamýšlen logický systém , výrazy mají být interpretovány jako prohlášení a pravidla, známá jako odvozovací pravidla , jsou obvykle zamýšlena tak, aby zachovávala pravdu. V tomto nastavení lze pravidla, která mohou zahrnovat axiomy , použít k odvození („odvození“) vzorců představujících pravdivá tvrzení - z daných vzorců představujících pravdivá tvrzení.

Sada axiomů může být prázdná, neprázdná konečná množina nebo spočitatelně nekonečná množina (viz schéma axiomu ). Formální gramatika rekurzivně definuje výrazy a dobře vytvořených formulí na jazyku . Kromě toho může být poskytnuta sémantika, která definuje pravdu a ocenění (nebo interpretace ).

Jazyk z výrokové logiky se skládá z

  1. sada primitivních symbolů, různě označovaných jako atomové vzorce , zástupné symboly , propozice nebo proměnné , a
  2. sada symbolů operátorů, různě interpretovaných jako logické operátory nebo logická spojiva .

Dobře tvarované vzorec je jakýkoliv atomové vzorec nebo jakýkoli vzorec, který může být vytvořen z atomických formulí pomocí symbolů provozovatele podle pravidel gramatiky.

Matematici někdy rozlišují mezi výrokovými konstantami, výrokovými proměnnými a schématy. Výrokové konstanty představují nějaký konkrétní výrok, zatímco výrokové proměnné se pohybují nad množinou všech atomových výroků. Schémata však přesahuje všechny výroky. Je běžné reprezentovat výrokové konstanty pomocí A , B a C , výrokové proměnné podle P , Q a R a schematická písmena jsou často řecká písmena, nejčastěji φ , ψ a χ .

Základní pojmy

Následující text nastiňuje standardní propoziční kalkul. Existuje mnoho různých formulací, které jsou víceméně ekvivalentní, ale liší se v detailech:

  1. jejich jazyk (tj. konkrétní sbírka primitivních symbolů a symbolů operátorů),
  2. množina axiomů nebo rozlišovaných vzorců a
  3. soubor odvozovacích pravidel.

Jakýkoli daný návrh může být reprezentován písmenem nazývaným „propoziční konstanta“, analogicky k reprezentaci čísla písmenem v matematice (např. A = 5 ). Všechny věty vyžadují přesně jednu ze dvou hodnot pravdy: pravdivé nebo nepravdivé. Například nechť P je návrh, že venku prší. To bude pravdivé ( P ), pokud venku prší, a nepravdivé jinak ( ¬ P ).

  • Poté definujeme pravdivě funkční operátory, počínaje negací. ¬ P představuje negaci P , která může být považována za odepření P . Ve výše uvedeném příkladu ¬ P vyjadřuje, že venku neprší, nebo standardnějším čtením: „Není pravda, že venku prší.“ Když P je pravda, ¬ P je nepravda; a když P je falešný, ¬ P je pravdivý. Jako výsledek, ¬ ¬ P má vždy stejnou pravdivostní hodnotu jako P .
  • Spojení je pravda funkční spojovací který tvoří návrh ze dvou jednodušších výroků, například, P a Q . Spojka P a Q je napsána PQ a vyjadřuje, že každá z nich je pravdivá. PQ čteme jako „ P a Q “. Pro jakákoli dvě tvrzení existují čtyři možná přiřazení hodnot pravdy:
    1. P je pravda a Q je pravda
    2. P je pravda a Q je nepravda
    3. P je nepravda a Q je pravda
    4. P je falešný a Q je falešný
Spojka P a Q je pravdivá v případě 1 a je nepravdivá. Kde P je tvrzení, že venku prší a Q je tvrzení, že nad Kansasem je studená fronta, PQ platí, když venku prší a nad Kansasem je studená fronta. Pokud venku neprší, pak P ∧ Q je falešné; a pokud nad Kansasem není studená fronta, pak PQ je také falešná.
  • Disjunkce připomíná konjunkci v tom, že tvoří výrok ze dvou jednodušších výroků. Napíšeme to PQ a čte se to „ P nebo Q “. Vyjadřuje, že buď P nebo Q je pravda. Ve výše uvedených případech je tedy disjunkce P s Q pravdivá ve všech případech - kromě případu 4. Pomocí výše uvedeného příkladu disjunkce vyjadřuje, že venku buď prší, nebo je nad Kansasem studená fronta. (Všimněte si, že toto použití disjunkce má připomínat použití anglického slova „nebo“. Nejvíce se však podobá angličtině zahrnující „nebo“, které lze použít k vyjádření pravdy alespoň jednoho ze dvou tvrzení. Není to jako anglické exkluzivní "nebo", což vyjadřuje pravdu přesně o jednom ze dvou tvrzení. Jinými slovy, exkluzivní "nebo" je nepravdivé, když platí P i Q (případ 1). Příklad exkluzivního nebo je: Můžete mít rohlík nebo pečivo, ale ne obojí. Často v přirozeném jazyce, vzhledem k příslušnému kontextu, je dodatek „ale ne obojí“ vynechán - ale implikován. V matematice je však „nebo“ vždy zahrnuto nebo; pokud je exkluzivní nebo je míněno, bude specifikováno, případně „xor“.)
  • Materiálově podmíněné také spojuje dvě jednodušší tvrzení a píšeme PQ , které se čte „když P, pak Q “. Tvrzení nalevo od šipky se nazývá předchůdce a tvrzení napravo se nazývá důsledek. (Neexistuje žádné takové označení pro konjunkci nebo disjunkci, protože se jedná o komutativní operace.) Vyjadřuje, že Q je pravdivé, kdykoli P je pravdivé. Tak PQ platí v každém případě výše, s výjimkou případu 2, protože je to jediný případ, kdy P je pravda, ale Q není. Na příkladu, pokud P pak Q vyjadřuje, že pokud venku prší, pak je nad Kansasem studená fronta. Hmotná podmíněnost je často zaměňována s fyzickou příčinnou souvislostí. Hmotné podmíněné však vztahují pouze dvě tvrzení podle jejich pravdivostních hodnot-což není vztah příčiny a následku. V literatuře je sporné, zda materiální implikace představuje logickou příčinnou souvislost.
  • Biconditional spojuje dvě jednodušší tvrzení a píšeme PQ , které se čte „ P právě tehdy, když Q “. Vyjadřuje, že P a Q mají stejnou pravdivostní hodnotu, a v případech 1 a 4. „ P je pravdivé tehdy a jen tehdy, je-li Q “ pravdivé, a jinak je nepravdivé.

Je velmi užitečné podívat se na pravdivostní tabulky pro tyto různé operátory a také na metodu analytických tableaux .

Uzavření za provozu

Výroková logika je pod pravdivými funkčními spojkami uzavřena. To znamená, že pro jakýkoli návrh φ je ¬ φ také návrh. Podobně pro jakékoli výroky φ a ψ je φψ propozice a podobně pro disjunkce, podmíněné a bikondicionální. To znamená, že například φψ je výrok, a proto jej lze spojit s jiným výrokem. Abychom to mohli znázornit, musíme použít závorky k označení, které tvrzení je spojeno s kterým. Například PQR není dobře vytvořený vzorec, protože neví, budeme-li vzájemné spojení PQ s R nebo pokud jsou vzájemné spojení P s QR . Musíme tedy napsat buď ( PQ ) ∧ R, abychom reprezentovali první, nebo P ∧ ( QR ), abychom reprezentovali druhé. Vyhodnocením pravdivostních podmínek vidíme, že oba výrazy mají stejné pravdivostní podmínky (budou platit ve stejných případech), a navíc, že ​​jakýkoli výrok tvořený libovolnými spojkami bude mít stejné pravdivostní podmínky, bez ohledu na umístění závorek. To znamená, že spojka je asociativní, ale neměli bychom předpokládat, že závorky nikdy neslouží účelu. Například věta P ∧ ( QR ) nemá stejné pravdivostní podmínky jako ( PQ ) ∨ R , jedná se tedy o různé věty rozlišené pouze v závorkách. Lze to ověřit výše uvedenou metodou tabulky pravdivosti.

Poznámka: Pro libovolný počet výrokových konstant můžeme vytvořit konečný počet případů, které uvádějí jejich možné pravdivostní hodnoty. Jednoduchý způsob, jak to generovat, je pomocí pravdivostních tabulek, do kterých se zapisuje P , Q , ..., Z pro jakýkoli seznam k propozičních konstant-to znamená jakýkoli seznam propozičních konstant s k vstupy. Pod tento seznam se zapisují 2 k řádky a pod P se zapisuje do první poloviny řádků true (nebo T) a do druhé poloviny false (nebo F). Pod Q se vyplní jedna čtvrtina řádků s T, pak jedna čtvrtina s F, pak jedna čtvrtina s T a poslední čtvrtina s F. Další sloupec přepíná mezi true a false pro každou osminu řádků, poté šestnáctiny a tak dále, dokud se poslední výroková konstanta pro každou řadu pohybuje mezi T a F. To poskytne úplný seznam případů nebo přiřazení pravdivostních hodnot možných pro tyto výrokové konstanty.

Argument

Výrokový kalkul pak definuje argument jako seznam tvrzení. Platným argumentem je seznam tvrzení, z nichž poslední vyplývá ze zbytku - nebo z něj vyplývá. Všechny ostatní argumenty jsou neplatné. Nejjednodušším platným argumentem je modus ponens , jehož jednou instancí je následující seznam tvrzení:

Toto je seznam tří propozic, každý řádek je propozicí a poslední vyplývá ze zbytku. První dva řádky se nazývají prostory a poslední řádek závěr. Říkáme, že jakýkoli návrh C vyplývá z jakékoli sady propozic , pokud C musí být pravdivé, kdykoli je pravdivý každý člen množiny . Ve výše uvedeném argumentu platí, že pro všechna P a Q , kdykoli PQ a P platí, nutně Q platí. Všimněte si, že když P je pravda, nemůžeme uvažovat případy 3 a 4 (z tabulky pravdy). Je -li PQ pravdivá, nemůžeme uvažovat případ 2. Ponechává se tedy pouze případ 1, ve kterém Q platí také. Prostor tedy implikuje Q.

To schematicky zobecňuje. Kde tedy φ a ψ mohou být nějaké návrhy,

Jiné formy argumentů jsou pohodlné, ale nejsou nutné. Vzhledem k úplné sadě axiomů (viz jeden takový soubor níže) postačuje modus ponens k prokázání všech ostatních forem argumentů v propoziční logice, takže je lze považovat za derivát. Všimněte si toho, že to neplatí pro rozšíření výrokové logiky na jiné logiky, jako je logika prvního řádu . Aby logika prvního řádu získala úplnost, vyžaduje alespoň jedno další pravidlo odvození .

Význam argumentu ve formální logice spočívá v tom, že lze získat nové pravdy ze zavedených pravd. V prvním příkladu výše, vzhledem k těmto dvěma předpokladům, pravda Q ještě není známa ani uvedena. Po provedení argumentu se odvodí Q. Tímto způsobem definujeme systém odpočtu jako soubor všech propozic, které lze odvodit z jiné sady propozic. Například vzhledem k tomu, množina výroků , můžeme definovat odpočet systém, y , což je množina všech výroků, které vyplývají z A . Opakování se vždy předpokládá, takže . Také z prvního prvku A , posledního prvku, stejně jako modus ponens, R je důsledek, a tak . Protože jsme nezahrnuli dostatečně úplné axiomy, nelze odvodit nic jiného. I když je tedy většina dedukčních systémů studovaných v propoziční logice schopna dedukovat , tento je příliš slabý na to, aby dokázal takové tvrzení.

Obecný popis výrokového počtu

Výrokové kalkul je formální systém , pokud:

  • Sada alfa je countably nekonečná množina prvků nazývaných ProPosition symboly nebo výrokové proměnné . Syntakticky vzato se jedná o nejzákladnější prvky formálního jazyka , jinak označované jako atomové vzorce nebo koncové prvky . V následujících příkladech jsou prvky obvykle písmena p , q , r atd.
  • Omega sada Ω je konečná množina prvků nazývaných symboly operátorů nebo logické spojky . Sada Ω je rozdělena do disjunktních podmnožin následovně:

    V tomto oddílu je sada symbolů operátorů arity j .

    V známějších výrokových kalkulích je Ω obvykle rozděleno takto:

    Často přijímaná konvence považuje konstantní logické hodnoty za operátory nulové arity, tedy:

    Někteří spisovatelé používají místo ¬ ; vlnovku (~) nebo N ; a některá použití v místo , stejně jako ampersand (a) se před označením K, nebo místo . Zápis se pro sadu logických hodnot liší ještě více, přičemž symboly jako {false, true}, {F, T} nebo {0, 1} jsou místo toho viděny v různých kontextech .
  • Sada zeta je konečná sada transformačních pravidel, která se při získávání logických aplikací nazývají odvozovací pravidla .
  • Sada iota je počitatelná sada počátečních bodů, které se nazývají axiomy, když dostávají logické interpretace.

Language of , také známý jako jeho soubor vzorců , dobře vytvořených formulí , je indukčně definována podle následujících pravidel:

  1. Základ: Jakýkoli prvek alfa sady je vzorec .
  2. Pokud jsou vzorce a je in , pak je vzorec.
  3. Zavřeno: Nic jiného není vzorec .

Opakované aplikace těchto pravidel umožňují konstrukci složitých vzorců. Například:

  • Podle pravidla 1 je p vzorec.
  • Podle pravidla 2 je vzorec.
  • Podle pravidla 1 je q vzorec.
  • Podle pravidla 2 je vzorec.

Příklad 1. Jednoduchý systém axiomu

Nech , kde , , , jsou definovány takto:

  • Alfa sada je spočítatelně nekonečná sada symbolů, například:
  • Ze tří spojek pro konjunkci, disjunkci a implikaci ( , a ) lze jeden brát jako primitivní a další dva lze definovat z hlediska jeho a negace ( ¬ ). Všechny logické spojky lze definovat pomocí jediného dostatečného operátora . Dvoupodmínečné ( ) lze samozřejmě definovat z hlediska konjunkce a implikace, přičemž je definováno jako .
    Přijetí negace a implikace jako dvou primitivních operací propozičního počtu se rovná rozdělení omega množiny takto:
  • Axiomový systém navržený Janem Łukasiewiczem a používaný jako propoziční-kalkulní část Hilbertova systému formuluje propoziční kalkul v tomto jazyce následovně. Axiomy jsou všechny substituční instance :
  • Pravidlo odvození je modus ponens (tj. Z p a , usoudit q ). Potom je definován jako a je definován jako . Tento systém se používá v Metamath set.mm formální databáze důkaz.

Příklad 2. Systém přirozeného odpočtu

Nech , kde , , , jsou definovány takto:

  • Alfa sada je spočítatelně nekonečná sada symbolů, například:
  • Omega nastavte oddíly následovně:

V následujícím příkladu výrokového počtu mají být transformační pravidla interpretována jako odvozovací pravidla takzvaného systému přirozené dedukce . Zde představený konkrétní systém nemá žádné počáteční body, což znamená, že jeho interpretace pro logické aplikace odvozuje své věty z prázdné sady axiomů.

  • Sada počátečních bodů je prázdná, tj .
  • Soubor pravidel transformace,, je popsán následovně:

Náš propoziční kalkul má jedenáct odvozovacích pravidel. Tato pravidla nám umožňují odvodit další pravdivé vzorce dané sadou vzorců, o nichž se předpokládá, že jsou pravdivé. Prvních deset jednoduše uvádí, že určité dobře formulované vzorce můžeme odvodit z jiných dobře formulovaných formulí. Poslední pravidlo však používá hypotetické uvažování v tom smyslu, že v premise pravidla dočasně předpokládáme (neprokázanou) hypotézu, která je součástí souboru odvozených vzorců, abychom zjistili, zda můžeme odvodit určitý jiný vzorec. Protože prvních deset pravidel to nedělá, jsou obvykle popisována jako nehypotetická pravidla a poslední jako hypotetické pravidlo.

Při popisu pravidel transformace můžeme zavést metajazykový symbol . Je to v podstatě praktická zkratka pro vyslovení „odvodit to“. Formát je , ve kterém Γ je (možná prázdná) sada vzorců nazývaných prostory a ψ je vzorec nazývaný závěr. Transformační pravidlo znamená, že je -li každý výrok v Γ větou (nebo má stejnou pravdivostní hodnotu jako axiomy), pak ψ je také věta. Všimněte si toho, že vzhledem k následujícímu pravidlu Úvod konjunkce budeme vědět, kdykoli má Γ více než jeden vzorec, můžeme jej vždy bezpečně zredukovat na jeden vzorec pomocí spojky. Stručně řečeno, od té doby můžeme místo množiny reprezentovat Γ jako jeden vzorec. Další opomenutí pro pohodlí je, když Γ je prázdná sada, v takovém případě se Γ nemusí objevit.

Úvod do negace
Od a , usuzovat .
To je , .
Eliminace negace
Od , usoudit .
To je , .
Eliminace dvojité negace
Od , usoudit p .
To je , .
Úvod do spojení
Z p a q odvodit .
To je , .
Odstranění spojky
Od , usoudit p .
Od , usoudit q .
To je, a .
Úvod do disjunkce
Od p , usoudit .
Od q , usuzovat .
To je, a .
Odstranění disjunkce
Od a a , usuzovat r .
To je , .
Dvoupodmínečný úvod
Od a , usuzovat .
To je , .
Dvoupodmínečná eliminace
Od , usoudit .
Od , usoudit .
To je, a .
Modus ponens (podmíněné odstranění)
Z p a usoudit q .
To je , .
Podmíněný důkaz (podmíněné zavedení)
Od [přijetí p umožňuje důkaz q ], usoudit .
To je , .

Základní a odvozené formy argumentů

název Následující Popis
Modus Ponens Pokud p, pak q ; p ; proto q
Modus Tollens Pokud p, pak q ; ne q ; proto ne p
Hypotetický sylogismus Pokud p, pak q ; pokud q, pak r ; pokud tedy p pak r
Disjunktivní sylogismus Buď p nebo q , nebo obojí; ne p ; proto q
Konstruktivní dilema Pokud p, pak q ; a pokud r, pak s ; ale p nebo r ; proto q nebo s
Destruktivní dilema Pokud p, pak q ; a pokud r, pak s ; ale ne q nebo ne s ; tedy ne p nebo ne r
Obousměrné dilema Pokud p, pak q ; a pokud r, pak s ; ale p nebo ne s ; proto q nebo ne r
Zjednodušení p a q jsou pravdivé; proto p je pravda
Spojení p a q platí samostatně; proto jsou pravdivé souběžně
Přidání p je pravda; proto je disjunkce ( p nebo q ) pravdivá
Složení Pokud p, pak q ; a pokud p, pak r ; proto pokud p je pravdivé, pak q a r jsou pravdivé
De Morganova věta (1) Negace ( p a q ) je ekviv. do (ne p nebo ne q )
De Morganova věta (2) Negace ( p nebo q ) je ekviv. do (ne p a ne q )
Komutace (1) ( p nebo q ) je ekviv. do ( q nebo p )
Komutace (2) ( p a q ) je ekviv. na ( q a p )
Komutace (3) ( p je ekviv. až q ) je ekviv. do ( q je ekvivalent k p )
Asociace (1) p nebo ( q nebo r ) je ekviv. na ( p nebo q ) nebo r
Asociace (2) p a ( q a r ) je ekviv. na ( p a q ) a r
Distribuce (1) p a ( q nebo r ) je ekviv. na ( p a q ) nebo ( p a r )
Distribuce (2) p nebo ( q a r ) je ekviv. do ( p nebo q ) a ( p nebo r )
Dvojitá negace a p je ekvivalentní negaci ne p
Transpozice Pokud p, pak q je ekviv. pokud ne q, tak ne p
Význam materiálu Pokud p, pak q je ekviv. ne p nebo q
Materiální ekvivalence (1) ( p iff q ) je ekviv. do (je -li p pravdivé, pak q je pravdivé) a (je -li q pravdivé, pak p je pravdivé)
Materiální ekvivalence (2) ( p iff q ) je ekviv. buď ( p a q jsou pravdivé) nebo (oba p a q jsou nepravdivé)
Materiální ekvivalence (3) ( p iff q ) se rovná., oba ( p nebo ne q je pravda) a (ne p nebo q je pravda)
Vývoz z (pokud p a q jsou pravdivé, pak r je pravda) můžeme dokázat (pokud q je pravdivé, pak r je pravdivé, pokud p je pravdivé)
Dovoz Pokud p pak (pokud q, pak r ) je ekvivalentní if p a q pak r
Tautologie (1) p je pravda je ekviv. to p is true or p is true
Tautologie (2) p je pravda je ekviv. to p is true and p is true
Tertium non datur (zákon vyloučeného středu) p nebo ne p je pravda
Zákon o rozporu p and not p is false, is a true statement

Důkazy v propozičním počtu

Jedním z hlavních použití výrokového počtu při jeho interpretaci pro logické aplikace je určení vztahů logické ekvivalence mezi výrokovými vzorci. Tyto vztahy jsou určeny pomocí dostupných transformačních pravidel, jejichž posloupnosti se nazývají derivace nebo důkazy .

V následující diskusi je důkaz předložen jako posloupnost očíslovaných řádků, přičemž každý řádek se skládá z jednoho vzorce, za kterým následuje důvod nebo odůvodnění zavedení tohoto vzorce. Každý předpoklad argumentu, tj. Předpoklad zavedený jako hypotéza argumentu, je uveden na začátku sekvence a je označen jako „předpoklad“ namísto jiného ospravedlnění. Závěr je uveden na posledním řádku. Důkaz je úplný, pokud každý řádek vyplývá z předchozích řádků správnou aplikací transformačního pravidla. (Kontrastní přístup najdete na stromech důkazů ).

Příklad důkazu v systému přirozeného odpočtu

  • Aby se ukázalo, že AA .
  • Jeden možný důkaz toho (který, i když je platný, obsahuje více kroků, než je nutné), může být uspořádán následovně:
Příklad důkazu
Číslo Vzorec Důvod
1 předpoklad
2 Od ( 1 ) úvodem disjunkce
3 Od ( 1 ) a ( 2 ) spojkovým úvodem
4 Od ( 3 ) odstraněním spojky
5 Shrnutí ( 1 ) až ( 4 )
6 Od ( 5 ) podmíněným důkazem

Interpretujte jako „Za předpokladu A , odvodit A “. Čtěte jako „Za předpokladu, že nic znamená, že A znamená A “ nebo „Je to tautologie, že A znamená A “ nebo „Vždy platí, že A znamená A “.

Příklad důkazu v klasickém systému propozičních kalkulů

Nyní dokážeme tutéž větu v axiomatickém systému od Jana Łukasiewicze popsaného výše, což je příklad klasických propozičních kalkulárních systémů nebo dedukčních systémů pro propoziční kalkul Hilbertova stylu .

Axiomy jsou:

(A1)
(A2)
(A3)

A důkaz je následující:

  1.       (instance (A1))
  2.       (instance (A2))
  3.       (od (1) a (2) od modus ponens )
  4.       (instance (A1))
  5.       (od (4) a (3) od modus ponens)

Správnost a úplnost pravidel

Klíčovými vlastnostmi této sady pravidel je, že jsou správná a úplná . Neformálně to znamená, že pravidla jsou správná a nejsou vyžadována žádná další pravidla. Tyto nároky mohou být formálnější následovně. Všimněte si, že důkazy o správnosti a úplnosti výrokové logiky nejsou samy o sobě důkazy v propoziční logice; toto jsou věty v ZFC používané jako metateorie k prokázání vlastností výrokové logiky.

Přiřazení pravdy definujeme jako funkci, která mapuje výrokové proměnné na true nebo false . Neformálně lze takové přiřazení pravdy chápat jako popis možného stavu věcí (nebo možného světa ), kde jsou určitá tvrzení pravdivá a jiná nikoli. Sémantika vzorců pak může být formalizována definováním, pro který „stav věcí“ jsou považovány za pravdivé, což se děje následující definicí.

Definujeme, kdy takové přiřazení pravdy A splňuje určitý dobře formulovaný vzorec s následujícími pravidly:

  • A splňuje výrokovou proměnnou P právě tehdy, když A ( P ) = true
  • A splňuje ¬ φ právě tehdy, když A nesplňuje φ
  • A splňuje ( φψ ) právě tehdy, pokud A splňuje φ i ψ
  • A splňuje ( φψ ) právě tehdy, pokud A splňuje alespoň jeden z φ nebo ψ
  • A splňuje ( φψ ) tehdy a jen tehdy, pokud to není tak, že A splňuje φ, ale ne ψ
  • A splňuje ( φψ ) právě tehdy, pokud A splňuje φ i ψ nebo nesplňuje ani jeden z nich

S touto definicí můžeme nyní formalizovat, co to znamená, že vzorec φ je implikován určitou sadou S vzorců. Neformálně to platí, pokud ve všech světech, které jsou možné vzhledem k množině vzorců S, také platí formule φ . To vede k následující formální definici: Říkáme, že množina S dobře formulovaných formulí sémanticky zahrnuje (nebo implikuje ) určitý dobře formulovaný vzorec φ, pokud všechna přiřazení pravdy, která splňují všechny vzorce v S, také splňují φ .

Nakonec definujeme syntaktické zahrnutí tak, že φ je syntakticky zahrnuto S právě tehdy, pokud jej můžeme odvodit pomocí odvozovacích pravidel, která byla uvedena výše v konečném počtu kroků. To nám umožňuje přesně formulovat, co to znamená, že sada odvozovacích pravidel je správná a úplná:

Správnost: Pokud sada dobře formulovaných formulí S syntakticky zahrnuje dobře formulovanou formuli φ, pak S sémanticky zahrnuje φ .

Úplnost: Pokud soubor dobře formulovaných formulí S sémanticky zahrnuje dobře formulovaný vzorec φ, pak S syntakticky zahrnuje φ .

U výše uvedeného souboru pravidel tomu tak skutečně je.

Náčrt důkazu spolehlivosti

(Pro většinu logických systémů je to poměrně „jednoduchý“ směr dokazování)

Notační konvence: Nechť G je proměnná v rozsahu sad vět. Nechť A, B a C přesahují věty. Pro „ G syntakticky zahrnuje A “ píšeme „ G dokazuje A “. Pro „ G sémanticky znamená A “ píšeme „ G znamená A “.

Chceme ukázat: ( A ) ( G ) (pokud G dokazuje A , pak G znamená A ).

Poznamenáváme, že „ G dokazuje A “ má induktivní definici, a to nám dává okamžité zdroje pro demonstraci tvrzení ve tvaru „Pokud G prokáže A , pak ...“. Náš důkaz tedy probíhá indukcí.

  1. Základ. Ukazují: Pokud je členem skupiny G , pak G znamená, A .
  2. Základ. Ukazují: Pokud je axiom, pak G znamená, A .
  3. Indukční krok (indukce na n , délka důkazu):
    1. Předpokládejme, že pro libovolné G a A, že pokud G prokáže A v N nebo méně kroků, potom G znamená .
    2. Pro každou možnou aplikaci pravidla závěru v kroku n + 1 , což vede k nové teorému B , ukazují, že G znamená B .

Všimněte si, že základní krok II lze u systémů přirozené dedukce vynechat, protože nemají žádné axiomy. Krok II zahrnuje ukázání, že každý z axiomů je (sémantickou) logickou pravdou .

Základem kroky ukazují, že nejjednodušší prokazatelné věty z G jsou rovněž vyplývá z G , pro každou G . (Důkaz je jednoduchý, protože sémantický fakt, že množina zahrnuje některého z jejích členů, je také triviální.) Indukční krok bude systematicky pokrývat všechny další věty, které by mohly být prokazatelné - zvážením každého případu, kde bychom mohli dojít k logickému závěru pomocí odvozovacího pravidla - a ukazuje, že pokud je nová věta prokazatelná, je také logicky implikovaná. (Například můžeme mít pravidlo, které nám říká, že z „ A “ můžeme odvodit „ A nebo B “. V III.a předpokládáme, že pokud je A prokazatelné, je implikováno. Víme také, že pokud A je prokazatelné, pak “ nebo B „je prokazatelný. Musíme ukázat, že potom“ a nebo B ", příliš se mlčky. Činíme tak tím, že odvolání k sémantické vymezení a za předpokladu, jsme právě udělal. je prokazatelné z G , budeme předpokládat. proto je také implikované G. Takže každé sémantické ocenění, které dělá všechno G pravdivé, dělá A true. Ale každé ocenění, které dělá A true, dělá „ A nebo B “ pravdivým, podle definované sémantiky pro „nebo“. Tedy jakékoli ocenění, které dělá všechno G pravdivým dělá „ A nebo B “ pravdivým. Takže „ A nebo B “ je implikováno.) Obecně bude indukční krok sestávat z dlouhé, ale jednoduché analýzy všech pravidel odvozování případ od případu , která ukazuje, že každý „zachovává“ sémantiku implikace.

Podle definice prokazatelnosti neexistují žádné prokazatelné věty kromě toho, že jsou členy G , axiomu nebo se řídí pravidlem; takže pokud jsou všechny tyto sémanticky implikované, dedukční kalkul je zdravý.

Náčrt důkazu úplnosti

(Toto je obvykle mnohem těžší směr dokazování.)

Přijímáme stejné notační konvence jako výše.

Chceme ukázat: pokud G znamená, A , pak G dokazuje A . Postupujeme podle kontrapozici : Ukázali jsme, namísto, že pokud G není ani dokázat A pak G však nebude znamenat A . Budeme-li ukázat, že existuje model, kde nedrží přes G je pravda, pak samozřejmě G neznamená A . Hlavní myšlenkou je vytvořit takový model z naší samého předpokladu, že G nedokazuje A .

  1. G nedokazuje A . (Předpoklad)
  2. Pokud G nedokazuje A , pak můžeme zkonstruovat (nekonečné) Maximální sada , G * , který je podmnožinou G a která také neprokazuje A .
    1. Umístěte uspořádání (s pořadím typu ω) na všechny věty v jazyce (např. Nejkratší první a stejně dlouhé v rozšířeném abecedním řazení) a očíslujte je ( E 1 , E 2 , ...)
    2. Definujte řadu G n množin ( G 0 , G 1 , ...) indukčně:
      1. Dokáže -li A , pak
      2. Pokud to není dokázat A , potom
    3. Definujte G jako spojení všech G n . (To znamená, že G je množina všech vět, které jsou v jakékoli G n .)
    4. Lze to snadno ukázat
      1. G obsahuje (je nadmnožinou) G (o (bi));
      2. G nedokazuje A (protože důkaz by obsahoval jen konečný počet vět a když je poslední z nich uvedena v nějakém G n , že G n by dokázalo A v rozporu s definicí G n ); a
      3. G * je maximální nastavení s ohledem na A : Je-li nějaké další věty, co byly přidány do G * , bylo by to dokázat A . (Protože kdyby bylo možné přidat další věty, měly by být přidány, když na ně při stavbě G n došlo , opět podle definice)
  3. Pokud je G maximální množinou s ohledem na A , pak je pravdivá . To znamená, že obsahuje C v případě, a pouze tehdy, pokud nebude obsahovat ¬C ; Pokud obsahuje C a obsahuje „If C then B “, pak také obsahuje B ; a tak dále. Abychom to ukázali, musíme ukázat, že axiomatický systém je dostatečně silný pro následující:
    • Pro jakékoliv vzorcích C a D , pokud se ukáže, jak C a ¬C , pak se ukáže, D . Z toho vyplývá, že maximální Set ve vztahu k A nemůže prokázat, jak C a ¬C , protože jinak by to dokázat A .
    • Pro jakékoliv vzorcích C a D , pokud se ukáže, jak CD a ¬CD , pak se ukáže, D . Toto se používá společně s dedukční větou k ukázce, že pro jakýkoli vzorec je buďto jeho nebo jeho negace v G : Nechť B je vzorec, který není v G ; pak G * s přídavkem B dokazuje . Tak z odpočtu věty vyplývá, že G * dokazuje BA . Předpokládejme však, že ¬B také nebyly v G , pak stejnou logikou G také dokazuje ¬BA ; ale pak G prokáže A , což jsme již ukázali jako falešné.
    • Pro jakékoliv vzorcích C a D , pokud se ukáže, C a D , pak se ukáže, CD .
    • Pro jakékoli vzorce C a D platí , že pokud prokáže C a ¬D , pak prokáže ¬ ( CD ).
    • Pro jakékoliv vzorcích C a D , pokud se ukáže, ¬C , pak se ukáže, CD .
    Pokud jsou součástí slovníku také další logické operace (například spojka a/nebo disjunkce), pak jsou na axiomatický systém kladeny další požadavky (např. Že pokud prokáže C a D , prokáže také jejich konjunkci).
  4. Je -li G pravdivé, existuje G -kanonické ocenění jazyka: takové, které činí každou větu v G pravdivou a vše mimo G falešnými, přičemž stále dodržuje zákony sémantického složení v jazyce. Všimněte si toho, že požadavek, aby byl pravdivý, je potřebný k tomu, aby bylo zaručeno, že tímto sdělením pravdy budou splněny zákony sémantické kompozice v jazyce.
  5. A G -kanonické ocenění způsobí, že naše původní sada G bude všechna pravdivá a A nepravdivá.
  6. Pokud je hodnota, na kterém G jsou pravdivé a je nepravdivé, pak G není (sémanticky) vyplývá, A .

Každý systém, který má jako odvozovací pravidlo modus ponens a dokazuje následující věty (včetně jejich nahrazení), je tedy úplný:

  • p → (¬p → q)
  • (p → q) → ((¬p → q) → q)
  • p → (q → (p → q))
  • p → (¬q → ¬ (p → q))
  • ¬p → (p → q)
  • p → p
  • p → (q → p)
  • (p → (q → r)) → ((p → q) → (p → r))

Prvních pět slouží ke splnění pěti podmínek ve výše uvedeném stupni III a poslední tři k prokázání věty o srážce.

Příklad

Jako příklad lze ukázat, že jako každou jinou tautologii lze tři výše popsané axiomy klasického systému propozičních kalkulů prokázat v jakémkoli systému, který splňuje výše uvedené, konkrétně ten, který má modus ponens jako odvozovací pravidlo a dokazuje výše uvedené. osm vět (včetně jejich substitucí). Z osmi vět jsou poslední dva dva ze tří axiomů; třetí axiom,, lze také dokázat, jak nyní ukážeme.

Jako důkaz můžeme použít hypotetickou syllogistickou větu (ve formě relevantní pro tento axiomatický systém), protože se spoléhá pouze na dva axiomy, které již jsou ve výše uvedené sadě osmi vět. Důkaz je pak následující:

  1.       (instance of the 7th theorem)
  2.       (instance of the 7th theorem)
  3.       (od (1) a (2) od modus ponens)
  4.       (instance of the hypotetical syllogism theorem)
  5.       (příklad 5. věty)
  6.       (od (5) a (4) od modus ponens)
  7.       (instance 2. věty)
  8.       (instance of the 7th theorem)
  9.       (od (7) a (8) od modus ponens)
  10.       (příklad 8. věty)
  11.       (od (9) a (10) od modus ponens)
  12.       (od (3) a (11) od modus ponens)
  13.       (příklad 8. věty)
  14.       (od (12) a (13) od modus ponens)
  15.       (od (6) a (14) od modus ponens)

Ověření úplnosti pro klasický výrokový početní systém

Nyní ověřujeme, že klasický systém výrokových kalkulů popsaný výše může skutečně dokázat požadovaných osm vět uvedených výše. Používáme několik osvědčených lemmat zde :

(DN1) - dvojitá negace (jeden směr)
(DN2) - dvojitá negace (jiný směr)
(HS1) - jedna forma hypotetického sylogismu
(HS2) - další forma hypotetického sylogismu
(TR1) - Transpozice
(TR2) - další forma transpozice.
(L1)
(L3)

Metodu hypotetického sylogismu metatheorem používáme také jako zkratku pro několik důkazních kroků.

  • p → (¬p → q) - důkaz:
    1.       (instance (A1))
    2.       (instance (TR1))
    3.       (od (1) a (2) pomocí hypotetického sylogismu metatheorem)
    4.       (instance (DN1))
    5.       (instance (HS1))
    6.       (od (4) a (5) pomocí modus ponens)
    7.       (od (3) a (6) pomocí hypotetického sylogismu metatheorem)
  • (p → q) → ((¬p → q) → q) - důkaz:
    1.       (instance (HS1))
    2.       (instance (L3))
    3.       (instance (HS1))
    4.       (od (2) a (3) od modus ponens)
    5.       (od (1) a (4) pomocí hypotetického sylogismu metatheorem)
    6.       (instance (TR2))
    7.       (instance (HS2))
    8.       (od (6) a (7) pomocí modus ponens)
    9.       (od (5) a (8) pomocí hypotetického sylogismu metatheorem)
  • p → (q → (p → q)) - důkaz:
    1.       (instance (A1))
    2.       (instance (A1))
    3.       (od (1) a (2) pomocí modus ponens)
  • p → (¬q → ¬ (p → q)) - důkaz:
    1.       (instance (L1))
    2.       (instance (TR1))
    3.       (od (1) a (2) pomocí hypotetického sylogismu metatheorem)
  • ¬p → (p → q) - důkaz:
    1.       (instance (A1))
    2.       (instance (A3))
    3.       (od (1) a (2) pomocí hypotetického sylogismu metatheorem)
  • p → p - důkaz uvedený v příkladu důkazu výše
  • p → (q → p) - axiom (A1)
  • (p → (q → r)) → ((p → q) → (p → r)) - axiom (A2)

Další obrys pro důkaz úplnosti

Pokud je vzorec tautologie , pak pro něj existuje tabulka pravd , která ukazuje, že každé ocenění přináší hodnotu pravdivou pro vzorec. Zvažte takové ocenění. Matematickou indukcí na délce podformulí ukažte, že pravda nebo nepravdivost podformulí vyplývá z pravdy nebo nepravdy (podle vhodnosti pro ocenění) každé výrokové proměnné v podformuli. Poté spojte řádky tabulky pravdy dohromady po dvou pomocí „( P je pravda znamená S ) znamená (( P je nepravda znamená S ) znamená S )“. Opakujte to, dokud nebudou odstraněny všechny závislosti na výrokových proměnných. Výsledkem je, že jsme prokázali danou tautologii. Protože každá tautologie je prokazatelná, logika je úplná.

Interpretace pravdivostně funkčního výrokového počtu

Interpretace výrokové logiky pravda-funkční je přiřazení ke každé výrokové symbol z jedné nebo druhé (ale ne oba) v pravdivostní hodnoty pravda ( T ) a falše ( F ), a přiřazení k pojivové symbolů z z jejich obvyklé pravdivě funkční významy. Interpretace pravdivostně funkčního výrokového počtu může být také vyjádřena pomocí pravdivostních tabulek .

Pro odlišné výrokové symboly existují různé možné interpretace. Například pro jakýkoli konkrétní symbol existují možné interpretace:

  1. je přiřazeno T , popř
  2. je přiřazen F .

Pro dvojici , jsou možné výklady:

  1. oběma je přiřazeno T ,
  2. oběma je přiřazeno F ,
  3. je přiřazeno T a je přiřazeno F , popř
  4. je přiřazen F a je přiřazen T .

Vzhledem k tomu , že má , tj. Početně mnoho výrokových symbolů, existuje , a proto je nespočetně mnoho různých možných interpretací .

Interpretace věty pravdivě funkční výrokové logiky

-Li φ a ψ jsou formule z a je výklad pak platí následující definice:

  • Věta výrokové logiky je při interpretaci pravdivá, pokud této větě přiřadí pravdivostní hodnotu T. Pokud je věta pravdivá při interpretaci, pak se této interpretaci říká model této věty.
  • φ je při interpretaci nepravdivé, pokud φ není pravdivé pod .
  • Věta výrokové logiky je logicky platná, pokud je pravdivá při každé interpretaci.
    φ znamená, že φ je logicky platné.
  • Věta ψ výrokové logiky je sémantickým důsledkem věty φ, pokud neexistuje interpretace, podle které φ je pravdivé a ψ nepravdivé.
  • Věta výrokové logiky je konzistentní, pokud je pravdivá alespoň pod jednou interpretací. Je nekonzistentní, pokud není konzistentní.

Některé důsledky těchto definic:

  • Pro jakýkoli daný výklad je daný vzorec pravdivý nebo nepravdivý.
  • Žádný vzorec není podle stejné interpretace pravdivý ani nepravdivý.
  • φ je pro danou interpretaci nepravdivé, pokud pro tuto interpretaci platí; a φ je při interpretaci pravdivé, pokud je při této interpretaci nepravdivé.
  • Pokud φ a obě jsou při dané interpretaci pravdivé , pak ψ platí při této interpretaci.
  • Pokud a pak .
  • platí pod iff φ není pravdivé pod .
  • platí, pokud buď φ není pravdivé pod nebo ψ je pravdivé pod .
  • Věta ψ výrokové logiky je sémantický důsledek větě φ právě tehdy, když je logicky platný , tedy právě tehdy .

Alternativní počet

Je možné definovat jinou verzi výrokového počtu, který definuje většinu syntaxe logických operátorů pomocí axiomů a který používá pouze jedno odvozovací pravidlo.

Axiomy

Nechť φ , χ a ψ znamená dobře formulované vzorce. (Samotné dobře formulované vzorce by neobsahovaly žádná řecká písmena, ale pouze velká římská písmena, spojovací operátory a závorky.) Pak jsou axiomy následující:

Axiomy
název Schéma Axiom Popis
PAK-1 Přidejte hypotézu χ , implikační úvod
PAK-2 Rozdělte hypotézu nad implikaci
A-1 Odstraňte konjunkci
A-2  
A-3 Zavést spojení
NEBO 1 Zaveďte disjunkci
NEBO-2  
NEBO 3 Odstranit disjunkci
NE-1 Zaveďte negaci
NE-2 Odstraňte negaci
NE-3 Vyloučená střední, klasická logika
IFF-1 Odstraňte ekvivalenci
IFF-2  
IFF-3 Zavést rovnocennost
  • Axiom THEN-2 lze považovat za „distribuční vlastnost implikace s ohledem na implikaci“.
  • Axiomy AND-1 a AND-2 odpovídají „eliminaci spojky“. Vztah mezi AND-1 a AND-2 odráží komutativitu operátoru spojky.
  • Axiom AND-3 odpovídá „zavedení spojky“.
  • Axiomy OR-1 a OR-2 odpovídají „zavedení disjunkce“. Vztah mezi OR-1 a OR-2 odráží komutativitu operátora disjunkce.
  • Axiom NOT-1 odpovídá „reductio ad absurdum“.
  • Axiom NOT-2 říká, že „z rozporu lze odvodit cokoli“.
  • Axiom NOT-3 se nazývá „ tertium non-datur “ ( latinsky : „třetina není uvedena“) a odráží sémantické ocenění výrokových formulí: vzorec může mít pravdivostní hodnotu buď pravdivou, nebo nepravdivou. Neexistuje žádná třetí hodnota pravdy, alespoň ne v klasické logice. Intuicionalističtí logici neakceptují axiom NOT-3 .

Inferenční pravidlo

Inferenční pravidlo je modus ponens :

.

Meta-odvozovací pravidlo

Nechte ukázku reprezentovat posloupnost s hypotézami nalevo od turniketu a závěrem napravo od turniketu. Potom lze větu o odpočtu uvést takto:

Pokud sekvence
byla prokázána, pak je také možné demonstrovat sekvenci
.

Tato dedukční věta (DT) sama o sobě není formulována s propozičním kalkulem: není to věta propozičního počtu, ale věta o propozičním počtu. V tomto smyslu je to meta-věta , srovnatelná s větami o správnosti nebo úplnosti výrokového počtu.

Na druhé straně je DT tak užitečný pro zjednodušení syntaktického důkazního procesu, že jej lze považovat a použít jako další odvozovací pravidlo, doprovázející modus ponens. V tomto smyslu DT odpovídá přirozenému odvozovacímu pravidlu podmíněného důkazu, které je součástí první verze propozičního počtu představené v tomto článku.

Konverzace DT je ​​také platná:

Pokud sekvence
byla prokázána, pak je také možné demonstrovat sekvenci

ve skutečnosti je platnost obrácení DT ve srovnání s DT téměř triviální:

Li
pak
1:
2:
a z (1) a (2) lze odvodit
3:
prostřednictvím modus ponens, QED

Konverzace DT má silné důsledky: lze ji použít k převodu axiomu na odvozovací pravidlo. Například axiom AND-1,

lze transformovat pomocí převodu věty o srážce na odvozovací pravidlo

což je eliminace spojky , jedno z deseti odvozovacích pravidel použitých v první verzi (v tomto článku) výrokového počtu.

Příklad důkazu

Následuje příklad (syntaktické) demonstrace zahrnující pouze axiomy THEN-1 a THEN-2 :

Dokázat: (Reflexivita implikace).

Důkaz:

  1. Axiom THEN-2 s
  2. Axiom THEN-1 s
  3. Od (1) a (2) od modus ponens.
  4. Axiom THEN-1 s
  5. Od (3) a (4) od modus ponens.

Ekvivalence k rovníkové logice

Předchozí alternativní počet je příkladem systému dedukce ve stylu Hilberta . V případě výrokových systémů jsou axiomy termíny postavené na logických spojkách a jediným odvozovacím pravidlem je modus ponens. Ekvatorní logika, jak se standardně používá neformálně ve středoškolské algebře, je jiný druh kalkulu od Hilbertových systémů. Jeho věty jsou rovnice a její odvozovací pravidla vyjadřují vlastnosti rovnosti, totiž že jde o shodu na podmínkách, které připouští substituci.

Klasický výrokový počet, jak je popsán výše, je ekvivalentní booleovské algebře , zatímco intuicionistický propoziční počet je ekvivalentní Heytingově algebře . Ekvivalence je ukázána překladem v každém směru vět vět příslušných systémů. Věty klasického nebo intuicionistického výrokového počtu se překládají jako rovnice booleovské nebo Heytingovy algebry. Naopak věty booleovské nebo Heytingovy algebry se překládají jako věty klasického nebo intuicionistického počtu, což je standardní zkratka. V případě booleovské algebry lze také přeložit jako , ale tento překlad je nesprávný z hlediska intuice.

V booleovské i Heytingově algebře lze místo rovnosti použít nerovnost . Rovnost je vyjádřitelná jako dvojice nerovností a . Naopak nerovnost je vyjádřitelná jako rovnost nebo . Význam nerovnosti pro systémy ve stylu Hilberta spočívá v tom, že odpovídá jejímu symbolu dedukce nebo implikace . Obtěžování

je přeloženo ve verzi nerovnice algebraického rámce jako

Naopak algebraická nerovnost se překládá jako entalment

.

Rozdíl mezi implikace a nerovnosti nebo entailment nebo je to, že první z nich je vnitřní logiky, zatímco druhá je vnější. Interní implikace mezi dvěma termíny je další termín stejného druhu. Entailment jako externí implikace mezi dvěma termíny vyjadřuje metatruth mimo jazyk logiky a je považován za součást metajazyka . I když je zkoumaná logika intuicionistická, obnášení je obvykle chápáno klasicky jako dvojí hodnota: buď levá strana znamená, nebo je menší nebo rovná pravé straně, nebo není.

Podobné, ale složitější překlady do az algebraických logik jsou možné pro systémy přirozené dedukce popsané výše a pro sekvenční počet . Důsledky toho posledního lze interpretovat jako dvě hodnoty, ale podrobnější výklad je jako soubor, jehož prvky lze chápat jako abstraktní důkazy organizované jako morfismy kategorie . V této interpretaci pravidlo řezu sekvenčního počtu odpovídá složení v kategorii. Booleovské a Heytingovy algebry vstupují do tohoto obrázku jako speciální kategorie, které mají maximálně jeden morfismus na sadu domů, tj. Jeden důkaz na entalment, což odpovídá myšlence, že existence důkazů je vše, na čem záleží: jakýkoli důkaz udělá a nemá smysl je rozlišovat .

Grafické kameny

Je možné zobecnit definici formálního jazyka ze sady konečných sekvencí na konečném základě tak, aby zahrnovala mnoho dalších sad matematických struktur, pokud jsou vytvořeny konečnými prostředky z konečných materiálů. A co víc, mnoho z těchto rodin formálních struktur je obzvláště vhodných pro použití v logice.

Například existuje mnoho rodin grafů, které jsou si natolik blízké analogy formálních jazyků, že se na ně koncept počtu celkem snadno a přirozeně rozšiřuje. Mnoho druhů grafů vzniknout rozebrat grafů v syntaktické analýze příslušných rodin textových struktur. Náležitosti praktického výpočtu ve formálních jazycích často vyžadují, aby byly textové řetězce převedeny na ztvárnění struktury ukazatelů parsovaných grafů, jednoduše jako kontrola, zda řetězce jsou dobře formulované vzorce nebo ne. Jakmile je toto hotové, existuje mnoho výhod, které lze získat z vývoje grafického analogu počtu na řetězcích. Mapování od řetězců k analýze grafů se nazývá analýza a inverzního mapování od analýzy grafů k řetězcům je dosaženo operací, která se nazývá procházení grafu.

Další logické kameny

Výrokový počet je o nejjednodušším druhu logického počtu v současném používání. Lze ji rozšířit několika způsoby. ( Aristotelský „syllogistický“ počet , který je v moderní logice z velké části nahrazen, je v některých ohledech jednodušší - ale v jiných ohledech složitější - než propoziční kalkul.) Nejpřímějším způsobem, jak vyvinout složitější logický počet, je zavést pravidla, která jsou citlivé na jemnější detaily použitých vět.

Logika prvního řádu (aka predikátová logika prvního řádu) vzniká, když jsou „atomové věty“ propoziční logiky rozděleny na termíny , proměnné , predikáty a kvantifikátory , přičemž všechna pravidla propoziční logiky jsou dodržována, přičemž jsou zavedeny některé nové. (Například z „Všichni psi jsou savci“ můžeme usuzovat „Pokud je Rover pes, pak je Rover savec“.) Pomocí nástrojů logiky prvního řádu je možné formulovat řadu teorií, buď s explicitními axiomy nebo podle odvozovacích pravidel, která mohou být sama o sobě považována za logická kalkula. Aritmetika je z nich nejznámější; další zahrnují teorii množin a pouhou teologii . Logika druhého řádu a další logiky vyššího řádu jsou formálním rozšířením logiky prvního řádu. Při porovnávání s těmito logikami má tedy smysl odkazovat na výrokovou logiku jako na logiku nulového řádu“ .

Modální logika také nabízí řadu závěrů, které nelze zachytit v propozičním počtu. Například z „Nezbytně p “ můžeme usoudit, že p . Z p můžeme usoudit „Je možné, že p “. Překlad mezi modální logikou a algebraickou logikou se týká klasické a intuitivní logiky, ale se zavedením unárního operátoru na booleovské nebo Heytingově algebře, odlišného od booleovských operací, interpretace modality možností a v případě Heytingovy algebry nutnost interpretace druhého operátora (pro booleovskou algebru je to nadbytečné, protože nutnost je De Morganův duál možností). První operátor zachovává 0 a disjunkce, zatímco druhý zachovává 1 a spojku.

Mnohohodnotné logiky jsou ty, které umožňují větám mít jiné hodnoty než true a false . (Například, ani a oba jsou standardní „extra hodnoty“, „kontinuum logika“ umožňuje každá věta na některý z nekonečného počtu „stupňů pravda“ mezi pravda a FALSE ). Tyto logiky často vyžadují výpočtových zařízení zcela odlišné od výrokové počet. Když hodnoty tvoří booleovskou algebru (která může mít více než dvě nebo dokonce nekonečně mnoho hodnot), logika s mnoha hodnotami se redukuje na klasickou logiku; logiky s mnoha hodnotami jsou tedy pouze nezávislého zájmu, když hodnoty tvoří algebru, která není booleovská.

Řešitelé

Hledání řešení výrokových logických vzorců je NP-úplný problém. Existují však praktické metody (např DPLL algoritmus , 1962; plev algoritmus , 2001), které jsou velmi rychlé mnoho užitečných případech. Nedávná práce rozšířila algoritmy SAT solveru o práci s výroky obsahujícími aritmetické výrazy ; to jsou řešitelé SMT .

Viz také

Vyšší logické úrovně

související témata

Reference

Další čtení

  • Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations , 1. vydání, Kluwer Academic Publishers, Norwell, MA. 2. vydání, Dover Publications, Mineola, NY.
  • Chang, CC a Keisler, HJ (1973), Model Theory , North-Holland, Amsterdam, Nizozemsko.
  • Kohavi, Zvi (1978), The Switching and Finite Automata Theory , 1. vydání, McGraw – Hill, 1970. 2. vydání, McGraw – Hill, 1978.
  • Korfhage, Robert R. (1974), Discrete Computational Structures , Academic Press, New York, NY.
  • Lambek, J. a Scott, PJ (1986), Úvod do kategorické logiky vyššího řádu , Cambridge University Press, Cambridge, Velká Británie.
  • Mendelson, Elliot (1964), Úvod do matematické logiky , D. Van Nostrand Company.

Související práce

externí odkazy