Mnohocenná logika - Many-valued logic

v logika, a mnohocenná logika (taky multi- nebo logika s více hodnotami) je výrokový kalkul ve kterých jsou více než dva pravdivostní hodnoty. Tradičně v Aristoteles je logický počet, pro libovolnou existovaly pouze dvě možné hodnoty (tj. „true“ a „false“) tvrzení. Klasický dvouhodnotová logika lze rozšířit na n-hodnotová logika pro n větší než 2. Ty nejoblíbenější v literatuře jsou tři (např., Łukasiewicz a Kleene, které přijímají hodnoty "true", "false" a "unknown"), konečná hodnota (konečně mnoho oceněných) s více než třemi hodnotami a nekonečně cenné (nekonečně mnoho oceněných), jako je fuzzy logika a logika pravděpodobnosti.

Dějiny

První známý klasický logik, který plně nepřijal zákon vyloučeného prostředku byl Aristoteles (který je paradoxně také obecně považován za prvního klasického logika a „otce logiky“)^[1]). Aristoteles připustil, že všechny jeho zákony se nevztahovaly na budoucí události (De Interpretatione, ch. IX), ale nevytvořil systém vícehodnotové logiky, aby vysvětlil tuto izolovanou poznámku. Až do příchodu 20. století následovali pozdější logici Aristotelská logika, který zahrnuje nebo předpokládá zákon vyloučeného středu.

20. století přineslo myšlenku vícehodnotové logiky. Polský logik a filozof Jan Łukasiewicz začal vytvářet systémy mnohohodnotné logiky v roce 1920 s využitím třetí hodnoty, „možné“, pro řešení Aristotelovy paradox námořní bitvy. Mezitím americký matematik, Emil L. Post (1921), také představili formulaci dalších stupňů pravdy pomocí n ≥ 2, kde n jsou hodnoty pravdy. Později Jan Łukasiewicz a Alfred Tarski společně formulovali logiku n pravdivostní hodnoty kde n ≥ 2. V roce 1932 Hans Reichenbach formuloval logiku mnoha hodnot pravdy, kde n→∞. Kurt Gödel v roce 1932 to ukázal intuicionistická logika není konečně mnoho logiky, a definoval systém Gödelova logika mezi klasický a intuicionistická logika; takové logiky jsou známé jako mezilehlé logiky.

Příklady

Kleene (silný) K.₃ a Priest logika P₃

Kleene „(silná) logika neurčitosti“ K.₃ (někdy ${displaystyle K_ {3} ^ {S}}$) a Kněz „Logika paradoxu“ přidává třetí „nedefinovanou“ nebo „neurčitou“ hodnotu pravdy Já. Pravda funguje pro negace (¬), spojení (∧), disjunkce (∨), implikace (→K.), a dvojpodmínečné (↔K.) jsou dány:^[2]

Rozdíl mezi těmito dvěma logikami spočívá v tom, jak tautologie jsou definovány. v K.₃ pouze T je určená pravdivostní hodnota, zatímco v P₃ oba T a Já jsou (logický vzorec se považuje za tautologii, pokud se vyhodnotí na určenou hodnotu pravdy). Podle Kleeneovy logiky Já lze interpretovat jako „nedeterminovaný“, přičemž není pravdivý ani falešný, zatímco je v Priestově logice Já lze interpretovat jako „předurčené“, přičemž jsou pravdivé i nepravdivé. K.₃ nemá žádné tautologie P₃ má stejné tautologie jako klasická dvouhodnotová logika.^[3]

Bochvarova vnitřní logika se třemi hodnotami

Další logikou je Bochvarova „interní“ logika se třemi hodnotami ${displaystyle B_ {3} ^ {I}}$, nazývaný také Kleeneova slabá logika se třemi hodnotami. S výjimkou negace a dvojpodmínečnosti se její pravdivostní tabulky liší od výše uvedených.^[4]

Mezilehlou hodnotu pravdy v Bochvarově „vnitřní“ logice lze popsat jako „nakažlivou“, protože se šíří ve vzorci bez ohledu na hodnotu jakékoli jiné proměnné.^[4]

Logika Belnap (B₄)

Belnapova logika B₄ kombinuje K.₃ a P₃. Nadměrně stanovená hodnota pravdy je zde označena jako B a podurčená hodnota pravdy jako N.

Gödelova logika G_k a G_∞

V roce 1932 Gödel definována^[5] rodina ${displaystyle G_ {k}}$ mnoha hodnotných logik s konečně mnoha hodnotami pravdy ${displaystyle 0, {frac {1} {k-1}}, {frac {2} {k-1}}, ldots {frac {k-2} {k-1}}, 1}$, například ${displaystyle G_ {3}}$ má pravdivostní hodnoty ${displaystyle 0, {frac {1} {2}}, 1}$ a ${displaystyle G_ {4}}$ má ${displaystyle 0, {frac {1} {3}}, {frac {2} {3}}, 1}$. Podobným způsobem definoval logiku s nekonečně mnoha hodnotami pravdy, ${displaystyle G_ {infty}}$, ve kterém jsou pravdivé hodnoty všechny reálná čísla v intervalu ${displaystyle [0,1]}$. Určená hodnota pravdy v těchto logikách je 1.

Spojení ${displaystyle wedge}$ a disjunkce ${displaystyle vee}$ jsou definovány jako minimální a maximum operandů:

• ${displaystyle uwedge v: = min {u, v}}$
• ${displaystyle uvee v: = max {u, v}}$

Negace ${displaystyle eg _ {G}}$ a implikace ${displaystyle {xrightarrow [{G}] {}}}$ jsou definovány takto:

• ${displaystyle {egin {aligned} eg _ {G} u & = {egin {cases} 1, & {ext {if}} u = 0 0, & {ext {if}} u> 0end {cases}} u {xrightarrow [{G}] {}} v & = {egin {cases} 1, & {ext {if}} uleq v v, & {ext {if}} u> vend {cases}} end {aligned}} }$

Gödelovy logiky jsou zcela axiomatizovatelné, to znamená, že je možné definovat logický počet, ve kterém jsou dokázatelné všechny tautologie.

Logika Łukasiewicz L_proti a L_∞

Implikace ${displaystyle {xrightarrow [{L}] {}}}$ a negace ${displaystyle {underset {L} {eg}}}$ byly definovány Jan Łukasiewicz prostřednictvím následujících funkcí:

• ${displaystyle {underset {L} {eg}} u: = 1-u}$
• ${displaystyle u {xrightarrow [{L}] {}} v: = min {1,1-u + v}}$

Nejprve Łukasiewicz použil tuto definici v roce 1920 pro svou tříhodnotovou logiku ${displaystyle L_ {3}}$, s hodnotami pravdy ${displaystyle 0, {frac {1} {2}}, 1}$. V roce 1922 vytvořil logiku s nekonečně mnoha hodnotami ${displaystyle L_ {infty}}$, ve kterém hodnoty pravdy pokrývaly reálná čísla v intervalu ${displaystyle [0,1]}$. V obou případech byla určená pravdivostní hodnota 1.^[6]

Přijetím pravdivostních hodnot definovaných stejným způsobem jako u logiky Gödel ${displaystyle 0, {frac {1} {v-1}}, {frac {2} {v-1}}, ldots, {frac {v-2} {v-1}}, 1}$, je možné vytvořit rodinu logik s konečnou hodnotou ${displaystyle L_ {v}}$, výše uvedené ${displaystyle L_ {infty}}$ a logika ${displaystyle L_ {aleph _ {0}}}$, ve kterém jsou pravdivostní hodnoty dány racionální čísla v intervalu ${displaystyle [0,1]}$. Soubor tautologií v ${displaystyle L_ {infty}}$ a ${displaystyle L_ {aleph _ {0}}}$ je identický.

Logika produktu Π

V logice produktu máme pravdivostní hodnoty v intervalu ${displaystyle [0,1]}$, spojení ${displaystyle odot}$ a implikace ${displaystyle {xrightarrow [{Pi}] {}}}$, definováno následovně^[7]

• ${displaystyle uodot v: = uv}$
• ${displaystyle u {xrightarrow [{Pi}] {}} v: = {egin {cases} 1, & {ext {if}} uleq v {frac {v} {u}}, a {ext {if}} u> vend {cases}}}$

Dále je zde záporná určená hodnota ${displaystyle {overline {0}}}$ který označuje koncept Nepravdivé. Prostřednictvím této hodnoty je možné definovat negaci ${displaystyle {underset {Pi} {eg}}}$ a další spojení ${displaystyle {underset {Pi} {wedge}}}$ jak následuje:

• ${displaystyle {underset {Pi} {eg}} u: = u {xrightarrow [{Pi}] {}} {overline {0}}}$
• ${displaystyle u {underset {Pi} {wedge}} v: = uodot (u {xrightarrow [{Pi}] {}} v)}$

Post logiky P_m

V roce 1921 Pošta definoval rodinu logiky ${displaystyle P_ {m}}$ s (jako v ${displaystyle L_ {v}}$ a ${displaystyle G_ {k}}$) hodnoty pravdy ${displaystyle 0, {frac {1} {m-1}}, {frac {2} {m-1}}, ldots, {frac {m-2} {m-1}}, 1}$. Negace ${displaystyle {underset {P} {eg}}}$ a spojení ${displaystyle {underset {P} {wedge}}}$ a disjunkce ${displaystyle {underset {P} {vee}}}$ jsou definovány takto:

• ${displaystyle {underset {P} {eg}} u: = {egin {cases} 1, & {ext {if}} u = 0 u- {frac {1} {m-1}}, & {ext { if}} uot = 0end {případů}}}$

• ${displaystyle u {underset {P} {wedge}} v: = min {u, v}}$
• ${displaystyle u {underset {P} {vee}} v: = max {u, v}}$

Logika růží

V roce 1951 Alan Rose definoval další rodinu logiky pro systémy, jejichž pravdivostní hodnoty tvoří mřížky. („Logické systémy, jejichž pravdivostní hodnoty tvoří mřížky", Math. Annalen, sv. 123, prosinec 1951, s. 152–165; zdroj ).

Sémantika

Maticová sémantika (logické matice)

Vidět Logická matice

Vztah ke klasické logice

Logiky jsou obvykle systémy určené ke kodifikaci pravidel pro zachování některých sémantický vlastnost propozic napříč transformacemi. V klasickém logika, tato vlastnost je „pravda“. V platném argumentu je pravdivost odvozené nabídky zaručena, pokud jsou prostory společně pravdivé, protože aplikace platných kroků zachovává vlastnost. Tato vlastnost však nemusí být „pravdou“; místo toho to může být nějaký jiný koncept.

Logika s více hodnotami jsou určeny k zachování vlastnosti značení (nebo označení). Vzhledem k tomu, že existují více než dvě hodnoty pravdy, je možné uvažovat o pravidlech závěru tak, aby byla zachována více než ta, která odpovídá (v příslušném smyslu) pravdě. Například v logice se třemi hodnotami jsou někdy označeny dvě největší pravdivostní hodnoty (pokud jsou reprezentovány jako např. Kladná celá čísla) a pravidla odvození tyto hodnoty zachovají. Platný argument bude přesně takový, že hodnota společně převzatých prostor bude vždy menší nebo stejná jako závěr.

Zachovaná vlastnost může být například odůvodnění, základní koncept intuicionistická logika. Tvrzení tedy není pravdivé nebo nepravdivé; místo toho je to oprávněné nebo chybné. Klíčovým rozdílem mezi ospravedlněním a pravdou je v tomto případě to, že zákon vyloučeného prostředku neplatí: návrh, který nemá chybu, nemusí být nutně oprávněný; místo toho se pouze neprokazuje, že je vadný. Klíčovým rozdílem je rozhodnost zachované vlastnosti: Lze to dokázat P je to oprávněné P je vadný nebo není schopen prokázat ani jeden. Platný argument zachovává ospravedlnění napříč transformacemi, takže věta odvozená z oprávněných vět je stále oprávněná. V klasické logice však existují důkazy, které závisí na zákoně vyloučeného středu; protože tento zákon není v tomto režimu použitelný, existují návrhy, které takto nelze prokázat.

Suszkova teze

Funkční úplnost mnoha hodnotných logik

Funkční úplnost je termín používaný k popisu speciální vlastnosti konečné logiky a algebry. Logická sada spojek je považována za funkčně kompletní nebo přiměřené právě když lze jeho sadu spojek použít ke konstrukci vzorce odpovídající všem možným funkce pravdy^[8]. Adekvátní algebra je taková, ve které každé konečné mapování proměnných může být vyjádřeno složením jejích operací^[9].

Klasická logika: CL = ({0,1}, ¬, →, ∨, ∧, ↔) je funkčně kompletní, zatímco č Łukasiewiczova logika nebo nekonečně mnohocenná logika má tuto vlastnost^[9][10].

Můžeme definovat konečně mnohocennou logiku jako L_n ({1, 2, ..., n} ƒ₁, ..., ƒ_m) kde n ≥ 2 je dané přirozené číslo. Pošta (1921) dokazuje, že za předpokladu, že logika je schopna produkovat funkci libovolného m^th objednávkový model, existuje nějaká odpovídající kombinace spojek v adekvátní logice L_n který může vytvořit model objednávky m + 1 ^[11].

Aplikace

Známé aplikace mnohohodnotové logiky lze zhruba rozdělit do dvou skupin.^[12] První skupina používá logickou doménu s mnoha hodnotami k efektivnějšímu řešení binárních problémů. Například dobře známým přístupem k reprezentaci booleovské funkce s více výstupy je zacházet s jeho výstupní částí jako s jednou proměnnou s mnoha hodnotami a převést ji na jeden výstup. charakteristická funkce (konkrétně funkce indikátoru ). Mezi další aplikace logiky s mnoha hodnotami patří návrh programovatelná logická pole (PLA) se vstupními dekodéry, optimalizace strojů s konečným stavem, testování a ověřování.

Druhá skupina se zaměřuje na návrh elektronických obvodů, které používají více než dvě diskrétní úrovně signálů, jako jsou paměti s velkou hodnotou, aritmetické obvody a polní programovatelná hradlová pole (FPGA). Mnohocenné obvody mají oproti standardním binárním obvodům řadu teoretických výhod. Například čip pro zapnutí a vypnutí propojení lze snížit, pokud signály v obvodu nabývají spíše čtyř nebo více úrovní než pouze dvou. V designu paměti se při uložení dvou namísto jednoho bitu informací na paměťovou buňku zdvojnásobí hustota paměti ve stejné velikosti matrice. Aplikace využívající aritmetické obvody často těží z používání alternativ k binárním číselným systémům. Například, zbytek a redundantní číselné systémy^[13] může snížit nebo vyloučit zvlnění nese které se podílejí na normálním binárním sčítání nebo odčítání, což má za následek vysokorychlostní aritmetické operace. Tyto číselné systémy mají přirozenou implementaci využívající mnohocenné obvody. Praktičnost těchto potenciálních výhod však silně závisí na dostupnosti realizací obvodů, které musí být kompatibilní nebo konkurenceschopné se současnými standardními technologiemi. Kromě pomoci při navrhování elektronických obvodů se k testování obvodů na poruchy a vady používá rozsáhlá logika. V podstatě vše známé automatické generování testovacích vzorů Algoritmy (ATG) používané pro testování digitálních obvodů vyžadují simulátor, který dokáže vyřešit logiku s 5 hodnotami (0, 1, x, D, D ').^[14] Další hodnoty - x, D a D '- představují (1) neznámé / neinicializované, (2) 0 místo 1 a (3) 1 místo 0.

Místa výzkumu

An IEEE Mezinárodní sympozium o vícehodnotové logice (ISMVL) se koná každoročně od roku 1970. Většinou se zaměřuje na aplikace v digitálním designu a ověřování.^[15] Je tam také Journal of Multiple-Valued Logic and Soft Computing.^[16]

Viz také

Matematická logika

• Stupně pravdy
• Fuzzy logika
• Gödelova logika
• Logika Jainy se sedmi hodnotami
• Kleene logika
• Kleene algebra (s involucí)
• Łukasiewiczova logika
• MV-algebra
• Post logika
• Princip bivalence
• A. N. Prior
• Logika relevance

Filozofická logika

• Falešné dilema
• Mu

Digitální logika

• MVCML, logika aktuálního režimu s více hodnotami
• IEEE 1164 standard s devíti hodnotami pro VHDL
• IEEE 1364 čtyřhodnotový standard pro Verilog
• Logika tří stavů
• Logika založená na šumu

Reference

Další čtení

Všeobecné

• Augusto, Luis M. (2017). Mnohocenná logika: Matematický a výpočetní úvod. London: College Publications. 340 stránek. ISBN  978-1-84890-250-3. Webová stránka
• Béziau J.-Y. (1997), Co je to mnohocenná logika? Sborník 27. mezinárodního sympozia o vícehodnotové logice, IEEE Computer Society, Los Alamitos, str. 117–121.
• Malinowski, Gregorz, (2001), Logika s mnoha hodnotami, v Goble, Lou, ed., Blackwell Guide to Philosophical Logic. Blackwell.
• Bergmann, Merrie (2008), Úvod do mnohocenné a fuzzy logiky: sémantika, algebry a derivační systémy, Cambridge University Press, ISBN  978-0-521-88128-9CS1 maint: ref = harv (odkaz)
• Cignoli, R. L. O., D'Ottaviano, I, M. L., Mundici, D., (2000). Algebraické základy mnohonásobného uvažování. Kluwer.
• Malinowski, Grzegorz (1993). Mnohocenné logiky. Clarendon Press. ISBN  978-0-19-853787-8.
• S. Gottwald, Pojednání o mnohocenné logice. Studies in Logic and Computation, sv. 9, Research Studies Press: Baldock, Hertfordshire, England, 2001.
• Gottwald, Siegfried (2005). „Mnohohodnotná logika“ (PDF). Archivovány od originálu dne 2016-03-03. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: ref = harv (odkaz) CS1 maint: BOT: stav původní adresy URL neznámý (odkaz)
• Miller, D. Michael; Thornton, Mitchell A. (2008). Logika s více hodnotami: koncepty a reprezentace. Syntetické přednášky o číslicových obvodech a systémech. 12. Vydavatelé Morgan & Claypool. ISBN  978-1-59829-190-2.
• Hájek P., (1998), Matematika fuzzy logiky. Kluwer. (Fuzzy logika chápána jako logika s mnoha hodnotami sui generis.)

Charakteristický

• Alexandre Zinovjev, Filozofické problémy mnohocenné logiky, D. Reidel Publishing Company, 169s., 1963.
• Předchozí A. 1957, Čas a modalita. Oxford University Press, založený na jeho 1956 John Locke přednášky
• Goguen J.A. 1968/69, Logika nepřesných konceptů, Synthese, 19, 325–373.
• Chang C.C. a Keisler H. J. 1966. Teorie spojitého modelu, Princeton, Princeton University Press.
• Gerla G. 2001, Fuzzy logika: Matematické nástroje pro přibližné uvažování, Kluwer Academic Publishers, Dordrecht.
• Pavelka J. 1979, Na fuzzy logice I: Mnohocenná pravidla odvození, Zeitschr. F. matematika. Logik und Grundlagen d. Math., 25, 45–52.
• Metcalfe, George; Olivetti, Nicola; Dov M. Gabbay (2008). Teorie důkazu pro fuzzy logiku. Springer. ISBN  978-1-4020-9408-8. Pokrývá teorii důkazů mnoha cenných logik, v tradici Hájek.
• Hähnle, Reiner (1993). Automatický odpočet v logice s více hodnotami. Clarendon Press. ISBN  978-0-19-853989-6.
• Azevedo, Francisco (2003). Řešení omezení přes vícehodnotovou logiku: aplikace na digitální obvody. IOS Press. ISBN  978-1-58603-304-0.
• Bolc, Leonard; Borowik, Piotr (2003). Mnohocenná Logics 2: Automatizované uvažování a praktické aplikace. Springer. ISBN  978-3-540-64507-8.
• Stanković, Radomir S .; Astola, Jaakko T .; Moraga, Claudio (2012). Reprezentace vícehodnotových logických funkcí. Vydavatelé Morgan & Claypool. doi:10.2200 / S00420ED1V01Y201205DCS037. ISBN  978-1-60845-942-1.
• Abramovici, Miron; Breuer, Melvin A .; Friedman, Arthur D. (1994). Testování digitálních systémů a testovatelný design. New York: Computer Science Press. ISBN  978-0-7803-1062-9.

externí odkazy

• Gottwald, Siegfried (2009). „Mnohohodnotná logika“. Stanfordská encyklopedie filozofie. Výzkumná laboratoř metafyziky, Stanford University.CS1 maint: ref = harv (odkaz)
• Stanfordská encyklopedie filozofie: "Pravdivé hodnoty „- Yaroslav Shramko a Heinrich Wansing.
• IEEE Computer Society je Technický výbor pro vícehodnotovou logiku
• Zdroje pro mnohocennou logiku autor: Reiner Hähnle, Chalmers University
• Server Logics W3 s mnoha hodnotami (archivováno)
• Yaroslav Shramko a Heinrich Wansing (2014). „Suszkova práce“. Stanfordská encyklopedie filozofie.CS1 maint: používá parametr autoři (odkaz)
• Carlos Caleiro, Walter Carnielli, Marcelo E. Coniglio a João Marcos, Společnost dvou: „Humbug mnoha logických hodnot“ v Jean-Yves Beziau, ed. (2007). Logica Universalis: Směrem k obecné teorii logiky (2. vyd.). Springer Science & Business Media. 174–194. ISBN  978-3-7643-8354-1.