A fogkő a kijelentések vagy propozicionális kalkulus része matematikai logika . Célja a "propozíciók" közötti logikai kapcsolatok tanulmányozása, és meghatározza azokat a formális törvényeket, amelyek szerint az egyszerű állítások logikai összekötők segítségével történő összeállításával összetett javaslatok jönnek létre, és ezek érvényes érveléshez vannak láncolva. Ez a matematikai logika egyik formális rendszere , pillére , amelynek a fogalmak megfogalmazásában segít. A sztoikus logika modern formájának számít .
A propozíció fogalma számos vita tárgyát képezte a logika történetében ; a konszenzus szerint az állítás egy szintaktikai konstrukció, amely állítólag igazságról beszél. A matematikai logikában a propozíciók kiszámítása az első lépés a logika és az érvelés meghatározásában. Meghatározza a levonás szabályait, amelyek összekapcsolják a javaslatokat, anélkül, hogy megvizsgálnák azok tartalmát; ez tehát az állítmányok számításának felépítésének első lépése , amelyet a javaslatok tartalma érdekel, és amely a matematikai érvelés befejezett formalizálása . A fogkő vagy ítéletlogika neve még most is propozicionális logika , propozicionális logika vagy számítási nyilatkozatok .
Bár a javaslatok kiszámítása nem a javaslatok tartalmára vonatkozik, hanem csak a kapcsolataikra, érdekes lehet megvitatni, mi lehet ez a tartalom. Egy javaslat információt ad a helyzet állapotáról. Így a „2 + 2 = 4” vagy „a könyv nyitva” két állítás.
A klasszikus logikában ( kétértékű logika ) egy tétel csak igaz vagy hamis értékeket vehet fel . Választható mondat (amely olyan kívánságot fejez ki, mint „Isten óvjon meg minket!”), Kötelező mondat („gyere!”, „Fogd be!”) Vagy egy kérdés nem állítás. "Isten óvjon meg minket! Nem lehet sem igaz, sem hamis: csak a beszélő kívánságát fejezi ki.
Másrészt egy olyan mondat, mint "Ebben a számításban az összes számítógépes változó mindig szigorúan pozitív ", egy olyan javaslat, amelynek tartalmát a kvantor minden esetben módosította, és az időbeli modalitást mindig, és amelynek állítólag időtartamnak kell bizonyulnia .. Ez a fajta javaslat a modális logika és pontosabban az időbeli logika alá tartozik . Valójában a modalitás mindig érvényesíti tartósságát az idő múlásával, és ezért mindig igaz lesz, míg a kvantor mind azt állítja, hogy az állítás mindig pozitív , minden adatfeldolgozási változóra vonatkozik, amely ráadásul kívül esik a javaslatok kiszámításán.
Ha egy állítás igazságértékű állítás, akkor az állítmány olyan kifejezés, amelynek igazságértéke a benne szereplő változóktól függ. A "Hazám Európában található" állítmány igaz, hamis vagy határozatlan, a "Saját ország" változó értékétől függően. Ha az olvasó svájci, akkor megkapjuk a „Svájc Európában található” javaslatot , ami igaz; ha az olvasó kanadai, megkapjuk a „Kanada Európában található” felvetést , amely hamis; ha az olvasó orosz, akkor megkapjuk az "Oroszország Európában található" felvetést, amely határozatlan, mert, mint tudjuk, Oroszország Európában és Ázsiában terül el.
A számítás vagy a deduktív rendszer logikailag olyan szabályhalmaz, amely véges számú lépésben és kifejezett szabályok szerint meg tudja erősíteni, hogy egy állítás igaz-e. Az ilyen folyamatot demonstrációnak nevezzük . A javaslatokhoz társítunk egy matematikai struktúrát is, amely lehetővé teszi, hogy garantáljuk, hogy ezeknek az érveléseknek vagy demonstrációknak jelentése van, azt mondjuk, hogy szemantikát adtunk neki. A klasszikus propositiószámításnál ez a szemantika csak két értéket használ, igaz és hamis (gyakran megjegyezzük, hogy 1 és 0). Egy teljesen meghatározott tétel (vagyis az egyik meghatározza az elemi alkotóelemek értékeit) e két érték közül csak egyet vesz fel.
A matematikai logika elméleteiben tehát két úgynevezett szintaktikai és szemantikai szempontot veszünk figyelembe , ez a helyzet a propozíciók számításánál.
Egy adott logika esetében a figyelembe vett levonási szabályok helyesek a szemantika szempontjából, abban az értelemben, hogy az igaz állításokból csak igaz állításokat lehet levezetni. Ha a dedukció tökéletesen megfelel a szemantikának, akkor azt mondják, hogy a rendszer teljes.
Az alábbiakban kitett rendszer a klasszikus logika keretei közé tartozik , amely a matematikai logika ága a matematikában. A nem klasszikus logika bemutatása később található . A melléknév „klasszikus” nem kell figyelembe venni abban az értelemben, a „normalitás”, de mint attribútum által adott a történelem logikája , lehetett volna akár az úgynevezett „logikai”.
A propozíciószámítás szintaxisának alapjain a propozíciós változók vagy atomi propozíciók találhatók , p , q stb., Amelyek általában megszámlálhatatlan végtelen halmazt alkotnak .
A propozíciószámítás nyelvének második alapvető alkotóeleme az operátor vagy összekötő . Ezek olyan szimbólumok, amelyek lehetővé teszik számunkra bonyolultabb javaslatok elkészítését. Ezen logikai csatlakozók közül a leggyakoribbak:
és | |
vagy | |
nem | |
magában foglal | |
egyenlő |
Gyakran figyelembe vesszük az állandó jelölt ⊥-t is, amelyet a „hegynek a teteje felé”, az „ üres típus ”, az „ alja ” vagy a „bot” kifejezésnek nevezünk , és amelynek célja a hamis ábrázolása .
E szimbólumok mellett zárójeleket használunk a képletek kétértelműségének (az alábbiakban elfogadott választás) eltávolítására, vagy olyan jelölésre, mint a lengyel jelölés , amelyet Jan Łukasiewicz lengyel logikus talált ki . Fontos, hogy a képletek meghatározása egyszerű és egyértelmű legyen, különösen a képletek szerkezetére vonatkozó induktív meghatározások lehetővé tétele érdekében, de a gyakorlatban lehetőség van a zárójelek mentésére, akár bizonyos egyezmények elfogadásával a kétértelműségek eltávolítására. , vagy azért, mert a kontextus lényegtelenné teszi ezeket a kétértelműségeket.
TételképletekA propozíciók kiszámítása ezen felül a formálási szabályokon nyugszik, amelyek azt mutatják, hogyan lehet összetett javaslatokat felépíteni az elemi propozíciókból vagy atomokból kiindulva, amelyek a propozíciós változók, és a lehetséges konstansokból, például ⊥. Ezek a szabályok meghatározzák, hogy a jelek mely csoportjai, mely szavak vannak jól kialakítva, és kijelölik a javaslatokat. A meghatározás a csatlakozók és az atomok megválasztásától függ.
Adunk magunknak egy tételes változót. Az (on ) vagy egyszerűen a propozíciók kiszámításához szükséges képletek halmazát az indukció határozza meg, vagyis ez a legkisebb halmaz, például:
Példák : Ha P , Q és R propozíciók,
( P → Q ) → (¬ Q → ¬ P ) egy tétel. ( P → ⊥) → ⊥ propozíció. P ∧ ¬ P egy tétel. ( P ∧ Q ) ∨ R propozíció. P ∧ Q ∨ nem tétel. Néhány szintaktikai konvencióA kifejezések bemutatásának megkönnyítése érdekében, a kétértelműség hiányának veszélyeztetése nélkül, a fenti definíciótól való bizonyos eltéréseket szintaktikai egyezmények engedélyezik.
Az olvashatóság érdekében a zárójelek több formáját is használják (méret, zárójeles helyettesítés stb.)
Továbbá bebizonyosodott, hogy csak a nyitó zárójelekre van szükség a képletek egyértelmű olvasásához, amelyeket ezért "" "periódus vált fel. egyes jelölésekben.
Deduktív rendszerekA propozíciók számítása lehetővé teszi a három leghíresebb deduktív rendszer bemutatását. Erre csak azokra a javaslatokra korlátozódunk, amelyek a propozíciós változók mellett csak implikációkat, disjunkciókat és hamis előfordulásokat tartalmaznak , más szóval of. Elismerjük, hogy ¬ P a P → ⊥ rövidítése . Ha P egy tétel, hogy egy javaslatot, hogy van egy bemutató, azt látjuk, hogy a ⊢ P .
A deduktív rendszerek a dedukció szabályait (más néven következtetési szabályokat ) alkalmazzák, amelyek a következők :
A nevezik helyiségek és az úgynevezett következtetést .
Hilbert-dedukcióCsak egy olyan szabály létezik, amelyet modus ponensnek hívnak .
Ezt a következőképpen lehet megérteni: ha tétel és tétel, akkor tétel . Ehhez hozzátehetjük:
három axióma implikációra és hamisságra :Míg a Hilbert-dedukció manipulálja és igazolja a tételeket, addig a természetes dedukció a hipotézisek szerinti állításokat bizonyítja, és ha nincs (több) hipotézis, akkor azok tételek. Ha azt mondjuk, hogy a javaslat a következménye egy sor hipotézisek, írunk . Míg a Hilbert-dedukcióban csak egy szabály és több axióma létezik, addig a természetes dedukcióban csak egy axióma és több szabály létezik. Minden csatlakozóhoz egy osztály szabályokat vezet be a szabályok bevezetésében és eltávolításában .
Ezenkívül létezik az abszurdra való redukció szabálya, amely a klasszikus logikában szükséges:
Ne feledje, hogy az implikáció kiküszöbölésének szabálya nagyon közel áll a modus ponenokhoz , ráadásul modus ponennek is nevezik . Meg kell jegyezni, hogy nincs szabály bevezetésére a hamis , és hogy a szabály megszüntetése hamis annyit jelent, hogy ha egy sor hipotézisek levezetni a hamis (vagy az abszurd), akkor ebből még együtt tudok következtetni semmit. Észre fogjuk venni, hogy az abszurdra redukció az a szabály, amely megfelel az abszurd érvelésének: a demonstráláshoz hozzáadjuk a hipotéziseket, és ha megszerezzük az abszurdot, akkor megvan .
A szekvenciák kiszámításaAz egyik ötlet ami a számítás a sequents az, hogy csak a bevezető szabályok mellett a szabály az úgynevezett vágási és strukturális szabályokat . Az, hogy az általunk használt képletek nevezünk sequents és amelyek a forma , ahol és amelyek multihalmazok a javaslatokat. A szekvenciát úgy értelmezzük, hogy a konjunkció állításaként levezetjük a disszjunkcióját . A nevezik előzményei és az úgynevezett következmény van . Ha az előzménylista üres, akkor írunk , ha a következõ lista üres, akkor írunk . A tétel továbbra is előzmények nélküli szekvencia, és csak egy következménye van.
A vágás a matematikus hozzáállását tükrözi, aki bizonyít egy lemmát (a tételt ), amelyet máshol használ a tétel bizonyításában. Ez a lemma kifejezhet valamit, aminek semmi köze a fő tételhez, ennélfogva az a vágy, hogy kiküszöböljük azokat a lemmákat, amelyek olyanok, mint a kitérők a fő eredmény felé haladásban. A gyengülés felesleges javaslat hozzáadásának felel meg, akár előzményként, akár következményként.
Példák tételekreAz alábbiakban felsoroljuk a fenti szabályok segítségével kimutatható tételek listáját, valamint a hagyomány által nekik adott közönséges nevet.
identitás | |
kizárt harmadik fél | |
kettős tagadás | |
klasszikus kettős tagadás | |
Peirce törvénye | |
nincs ellentmondás | |
De Morgan törvényei | |
ellentétbe helyezés | |
modus ponens (propozicionális) | |
modus tollens (propozicionális) | |
modus barbara (tételes) | |
modus barbara (implikatív) | |
disztribúció | |
Mindhárom rendszer ugyanazt a szimbólumot használja , de ez a jelölés következetes. A természetes dedukcióhoz használt formátum valójában egy olyan szekvencia, amelyben csak egy következtetés van, akkor természetes szekvenciáról beszélünk. A Hilbert-stílusú rendszerek tételeihez használt formátum megfelel egy természetes sorozatnak, ahol nincs hipotézis.
Megmutathatjuk, hogy ez a három rendszer ekvivalens abban az értelemben, hogy pontosan ugyanazok a tételek vannak.
A tételek állításának „klasszikus” aspektusát a Hilbert-stílusú rendszerben az ellentétek axiómája adja meg, az abszurdra redukció révén a természetes dedukcióban jelenik meg. A szekvenciák kiszámítása klasszikus, de ha egyetlen következménnyel rendelkező szekvenciákra szorítkozunk, az intuícióvá válik.
A szemantika határozza meg a javaslatok értelmezésének szabályait. Ha az állításban beavatkozó elemi állításokhoz igazságértékeket tulajdonítunk, az ennek a tételnek a modelljét választja .
Pontosabban, ha a klasszikus logikát nézzük, akkor az A tétel értelmezése az a tény, hogy igazságértéket (0 vagy 1) tulajdonítunk a propozíciós változóknak, és elmagyarázzuk, hogy a csatlakozók hogyan viselkednek az értékekkel szemben. Az igazság. Ezt a viselkedést egy igazságtáblázat adja meg. Ily módon minden tételhez 0 vagy 1 értéket adhatunk, amely az igazságtáblák által vett értékektől függ. Három értelmezési eset van:
Megmagyarázzuk a viselkedést, majd megadjuk a hozzá tartozó igazságtáblázatot
P | Q | |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
P | Q | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
P | Q | |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
P | |
0 | 1 |
1 | 0 |
P | Q | |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
1. példa :
(¬ A → A ) → A tautológia.Valóban, ha tulajdonítunk A értéke 0, akkor ¬ A veszi az 1 értéket, (¬ A → A ) értéket veszi fel 0, és (¬ A → A ) → A értékét veszi 1. Hasonlóképpen, ha rendel A az 1 értéket, majd ¬ A veszi a 0 értéket, (¬ A → A ) az 1 értéket, és (¬ A → A ) → A az 1 értéket veszi fel.
2. példa :
A → ( A → ¬ A ) nem tautológia.Valóban, ha tulajdonítunk A értéke 1, akkor a ¬ A értékét veszi fel 0, ( A → ¬ A ) értéket vesz fel 0 és A → ( A → ¬ A ) értéket veszi 0.
Komplett csatlakozó rendszerekAz n- belépési igazságtábla meghatároz egy n- csatlakozót . A propozíciós csatlakozók halmaza teljesnek mondható, ha bármelyik csatlakozó meghatározható a készlet csatlakozóival. Bármely igazságtáblát a disszjunkciók és a tagadás kötőszóival írunk le. Például a fenti ekvivalencia igazságtáblázatát teljes egészében leírjuk: " p ↔ q akkor és akkor veszi az igaz értéket, ha p és q hamis értéket vesznek fel, vagy p és q a érték igaz ”, azaz p ↔ q ≡ (¬ p ∧ ¬ q ) ∨ ( p ∧ q ). Ez a módszer általános, és lehetővé teszi annak bemutatását, hogy a {¬, ∧, ∨} rendszer egy teljes csatlakozási rendszer. Arra következtettünk, hogy a {¬, ∧}, {¬, ∨} is teljes rendszerek (Morgan törvényei miatt A ∨ B ≡ ¬ (¬ A ∧ ¬ B ), A ∧ B ≡ ¬ (¬ A ∨ ¬ B )) . A készlet {¬, →} befejeződött: A ∨ B ≡ ¬ A → B .
A készlet áll az egyetlen NAND csatlakozó (jelöljük „|” által Henry Sheffer , és ezért az úgynevezett Sheffer bárban ) Is teljes, ¬ P egyenértékűnek P | P és P ∨ Q - ( P | P ) | ( Q | Q ). Ezt a funkciót használják a logikai áramkörök felépítéséhez, ekkor egyetlen kapu elegendő az összes létező áramkör megtervezéséhez.
A propozíciós számításnak ezért többféle eszköze van a javaslatok „érvényesítéséhez”: a tételek bizonyító dedukciós rendszerei és a tautológiákat meghatározó szemantikai módszerek . Felmerül a kérdés, hogy ezek a módszerek egybeesnek-e.
Az a tény, hogy bármely állítás bizonyítható, ha tautológia, kifejezi a propozíciós számítás azon tulajdonságát, amelyet teljességnek nevezünk , ez azt jelenti, hogy a propozíciós számítás deduktív bemutatása egyenértékű a szemantikus prezentációval. A teljesség a következő megjegyzéseken alapul.
A javaslatok kiszámításának teljességéről szóló cikk- tétel újabb részletesebb bizonyítékot kínál.
A javaslatok kiszámításának teljességéből az következik, hogy:
Tegyük fel, hogy végtelen számú javaslatot kapott. Meg tudjuk egyidejűleg kielégíteni ezeket a javaslatokat? Más szavakkal, vannak-e olyan igazságértékek a propozíciós változók számára, amelyek az 1-et adják igazságértéknek minden állításnak? Ha a válasz bármelyik véges részhalmazra pozitív, akkor az összes állításra vonatkozik. Ezt a tulajdonságot, amely biztosítja, hogy az összes véges részhalmazból átkerüljünk a teljes végtelen halmazba, tömörségnek nevezzük .
Láttuk, hogy annak eldöntéséhez, hogy egy állítás klasszikusan bizonyítható-e, elegendő ellenőrizni, hogy tautológia-e, vagyis annak igazolására, hogy az igazság értékét veszi-e bármi is, a propozíciós változóinak igazságértéke.
Ez a brutális megközelítés azonban szembeszáll a szükséges számítási idővel. Valójában, ha az állításnak n propozíciós változója van, akkor 2 n lehetséges értékkombinációt kell kiszámítani a propozíciós változók számára, ami n nagy nagy esetén gyorsan megvalósíthatatlanná válik . Tehát, ha n = 30, akkor több mint egymilliárd értékkombinációt kell felsorolni.
Minden bizonnyal vannak fejlesztések. Például, ha a 0 igazságértéket hozzárendeljük egy p propozíciós változóhoz , akkor a 0 értéket közvetlenül rendelhetjük a q-hoz rendelt későbbi értéktől függetlenül , ami csökkenti az elvégzendő számítások számát.
Megvizsgálhatjuk azt is, hogy érvényteleníteni lehet-e a következményeket. Vegyük például az állítást:
Rész pedig egy vonzata, hogy ez érvénytelen, akkor elegendő, ha azt a következtetést lehet az értéke 0 (és így az 1-es érték), és hogy a hipotézis vehet az értéke 1 (és ezért , valamint az 1-es érték). De ekkor felveszi a 0 értéket, és csak a 0. értéket veheti fel. Ezért lehetetlen érvényteleníteni az implikációt, és ez tautológia.
De a korábbi fejlesztések nem változtatják meg alapvetően a probléma nehézségét. Ezért a következő helyzettel állunk szemben. Ha egy f tételt állítunk fel, feltesszük magunknak a kérdést, hogy f tautológia-e vagy sem, ezért arra kíváncsiak vagyunk, hogy vannak-e olyan igazságértékek, amelyek az f propozíciós változóinak tulajdoníthatók, amelyek érvénytelenné tennék f-t .
Az f érvénytelenségének kérdését , valamint az összes problémát, amelyet az imént felvázolt módszer szerint oldunk meg, NP-nek nevezzük (nem determinisztikus polinomnak). Az f érvénytelenségének tesztelése nagyon egyszerű számításokkal (polinomi időben) egyenértékű negációjának kielégítőségével. A propozíció kielégíthetőségének problémáját, nevezetesen egy olyan konfiguráció megtalálását, amely 1-et ad meg a propozíció igazságértékeként, SAT-problémának nevezzük (az angol logikai SAT- féle isfiabilitási problémából ). Alapvető szerepet játszik a komplexitáselméletben , mivel kimutatható, hogy egy determinista algoritmus polinomiális időben történő felfedezése erre a problémára lehetővé tenné a determinista algoritmusok polinomiális időben történő levezetését az összes NP-típusú probléma esetén ( Cook-tétel ). Azt mondjuk, hogy a SAT (és ennélfogva a propozíció bizonyíthatatlanságának problémája is) NP-teljes probléma . A propozíció bizonyíthatóságának problémája állítólag co-NP (az NP komplementere szempontjából).
A SAT probléma leggyakrabban a tagmondatok együttesének kielégíthetőségét jelöli meg (egy konkrét eset a állítások között), de a hozzá adott javaslat kielégíthetőségének problémáját egy polinomiális redukcióval csökkentjük (egy záradékos formába tett egyenlőtlenség, a logikai egyenértékűség szerint nem működnek).
Legyen E a propozíciós változók halmaza fölötti állításhalmaz. Megjegyezzük az E-n két állítás (klasszikus) ekvivalenciája által meghatározott bináris relációt ≡. Ez ekvivalencia-reláció az E-n, kompatibilis a kötőszóval (amely két elem alsó határát adja), a diszjunkcióval (amely két elem felső határát adja) és a tagadással (amely a kiegészítést adja). A propozíciós számítás E / ≡ hányadosa .
Amint a propozíciós változók halmaza végtelen, a propozíciós képletek Lindenbaum algebrájában nincsenek atomok, vagyis nincs minimális nulla nélküli elem (minden olyan képlet esetében, amely nem antilógia, szigorúan alacsonyabb elemet kapunk egy propozíciós változóval együtt. nincs a képletben). Ez megkülönbözteti a halmaz összes részének logikai algebrájától, amelynek szingulettjei atomként szerepelnek.
A Heyting algebrát Arend Heyting határozta meg, értelmezve az intuíciós logikát.
A diszjunkció a forma és a kötőszó a forma javaslata . A tagmondat konjunktív normál alakban (FNC) van, ha diszjunkciók kötőszavaiból áll . A záradék diszjunktív normál formában (FND) van, ha kötőszavak diszjunkcióiból áll .
Példák:
Amikor egy FND minden egyes disszjunktív blokkjának ugyanazok a propozíciós változók egyetlen és egyetlen előfordulása van, akkor megkülönböztetett FND-ről beszélünk .
Amikor egy FNC minden egyes összekötő blokkjának ugyanazok a propozíciós változók egyetlen és egyetlen előfordulása van, akkor megkülönböztetett FNC-ről beszélünk .
Példák:
Megmutathatjuk, hogy bármely állítás ekvivalens egy FND-vel (feltételezve, hogy ez egy üres állításhalmaz disszjunkciója), és egyenértékű egy FNC-vel (feltételezve, hogy T egy üres állításhalmaz együttese). Más szóval, minden állítás létezik egy ajánlatom a diszjunktív normál forma, mint például , és egy ajánlatom konjunktív normál formában, például .
A propozíciós számítás axiómái és szabályai, amelyeket bemutattunk, a klasszikus logikáéi . Indukálják a kizárt harmadik elvnek nevezett p ∨ ¬p állítást, a kettős tagadás kiküszöbölésének nevezett ¬¬ p → p állítást és Peirce-törvénynek nevezett állítást ((p → q) → p) → p . Ez a logika azon az elven alapul, hogy a P tulajdonság szükségszerűen igaz vagy hamis. Hilbert és mások által elfogadott úgynevezett formalista álláspont egyik pillére . Ezt az álláspontot, amely azt sugallja, hogy vannak olyan demonstrációk, amelyek nem a bizonyított javaslatot kielégítő objektumot konstruálják, több matematikus megkérdőjelezte, amelyek közül a legismertebb Brouwer, amely az intuíciós logika megalkotásához vezet .
Vannak eltérések a unclassical logika, nevezetesen a minimális logika a Ingebrigt Johansson (1936), valamint a matematikai intuicionizmus a Heyting (1930). A primitív csatlakozók →, ∧, ∨ és ¬. Ezek a variánsok az általuk használt axiómák megválasztásában különböznek egymástól.
Az abszolút logika a következõ axiómákat használja az implikációra, a konjunkcióra és a diszjunkcióra. Nem foglalkozik a tagadással.
A implikáció axiómái (ezek a klasszikus logika első két axiómája):
ax.1: ax.2:A kötőszó axiómái :
ax.3: ax.4: ax.5:Axiómái diszjunkció ( duals a korábbiak):
ax.8: ax.9: ax.10:Ennek a logikának a tételeit szigorúan a klasszikus logika tételei tartalmazzák, amelyek nem használnak tagadásokat. Például lehetetlen bizonyítani a Peirce képletét vagy törvényét .
Ha az axiómákhoz ax.1-től ax.8-ig hozzáadjuk a következő axiómát:
ax.9:pozitív logikát kapunk. Ennek a logikának a tételei megegyeznek a klasszikus logika tételeinek azon halmazával, amelyek nem használnak tagadásokat.
Ha az axiómákhoz ax.1-től ax.8-ig hozzáadjuk a negatívumra vonatkozó következő két axiómát:
ax.10: ¬ p → ( p → ¬ q ) ax.11: ( p → ¬ p ) → ¬ pmegkapjuk a minimális logikát . Az első axióma meghatározza a logika viselkedését egy ellentmondással szemben. A második axióma kifejezi, hogy ha p magában hordozza a saját tagadását, akkor p érvénytelen.
Az egyetlen különbség az intuitionista logika és a minimális logika között az axióma ax10-re vonatkozik, amelyet a következő vált fel:
ax.12: ¬ p → ( p → q )Tétel és negációjának jelenlétében a három logika, a klasszikus, az intuíció és a minimális, mindhárom ellentmondásban következik ⊥. De a különbség az ellentmondás használatával kapcsolatos:
A minimális logikának és az intuíciós logikának egyaránt van tétele a ¬ (p ∧ ¬p) tétel. Másrészt a p ∨ ¬p nem ezeknek a logikáknak a tétele.
Hasonlóképpen lehetővé teszik számunkra a p → ¬¬p bizonyítását, de nem fordítva. Másrészt lehetővé teszik a ¬p és ¬¬p ekvivalencia bemutatását. Végül a (¬p ∨ q) → (p → q) állítás az intuitionista logika tétele, de nem a minimális logika tétele.
Glivenko (en) 1929-ben bebizonyította, hogy p a klasszikus propozíciós számítás tétele csak akkor, ha a ¬¬ az intuitionista propozíciós számítás tétele. Ez az eredmény nem terjed ki, ha az „intuicionistát” a „minimálisra” cseréljük. Nem vonatkozik a predikátumok kiszámítására sem ; fordítás azonban lehetséges, de a képletek felépítésétől függ.
Végül, hogy rendelkezzünk p ∨ q igazolásával az intuíciós logikában, vagy p, vagy q igazolásra van szükségünk , míg a klasszikus logikában elegendő a ¬ (¬p ∧ ¬q) igazolása .
Bevezethetjük az if (van) és a ∀ (bármi) kvantorokat a propozíciók számszerűsítésére (ezt meg kell különböztetni a predikátumok kiszámításának kvantálásától ). Így például a kvantifikált propozíciós számítás érvényes képletei lesznek, amelyet másodrendű propozíciós számításnak is nevezünk :