Logiikan algebra

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7.11.2021 tarkistetusta versiosta . tarkastukset vaativat 26 muokkausta .

Logiikkaalgebra ( propositionalgebra ) on matemaattisen logiikan osa, joka tutkii lauseiden loogisia operaatioita [ 1] . Useimmiten oletetaan, että väitteet voivat olla vain tosi tai epätosi, eli käytetään ns. binaari- tai binaarilogiikkaa , toisin kuin esimerkiksi kolmiosainen logiikka .

Sen perustaja on J. Boole , englantilainen matemaatikko ja logiikka , joka perusti loogisen oppinsa algebran ja logiikan väliseen analogiaan. Logiikkaalgebrasta tuli ensimmäinen matemaattisen logiikan järjestelmä, jossa algebrallista symboliikkaa alettiin soveltaa loogisiin johtopäätöksiin operaatioissa, joissa käsitteitä tarkastellaan niiden tilavuuden puolelta. Boole asetti itselleen tehtäväksi ratkaista loogisia ongelmia algebran menetelmillä . Hän yritti ilmaista tuomion yhtälöiden muodossa symboleilla, joissa loogiset lait toimivat, samoin kuin algebran lait.

Myöhemmin logiikan algebran parannukset suorittivat W. .Ch,S. PoretskyP.,SchroederE.,JevonsS. B. Russell osallistui ja antoi yhdessä A. Whiteheadin kanssa matemaattiselle logiikalle modernin ilmeen; I. I. Zhegalkin , jonka ansiona oli luokkalaskennan edelleen kehittäminen ja loogisen summauksen operaatioteorian merkittävä yksinkertaistaminen; VI Glivenko vei logiikan algebran aiheen paljon pidemmälle kuin käsitteillä tehtyjen tilavuusoperaatioiden tutkiminen.

Logiikkaalgebra nykyaikaisessa esityksessään käsittelee operaatioiden tutkimusta lauseilla, eli lauseilla, joille on ominaista vain yksi ominaisuus - totuusarvo (tosi, epätosi). Klassisessa logiikan algebrassa väitteellä voi olla samanaikaisesti vain toinen kahdesta totuusarvosta: "tosi" tai "epätosi". Logiikkaalgebra tutkii myös lauseita - funktioita, jotka voivat saada arvot "tosi" ja "epätosi" riippuen siitä, mikä arvo annetaan lausekkeeseen sisältyvälle muuttujalle - funktio.

Määritelmä

Peruselementit, joilla logiikan algebra toimii, ovat propositiot .

Lausekkeet muodostetaan joukolle { , , , , , }, jossa on ei-tyhjä joukko, jonka elementeille määritellään kolme operaatiota : $B$ $\lei$ $\maa$ $\lor$ $0$ $yksi$ $B$

\lei

negaatio ( unaarinen operaatio ),

\maa

konjunktio ( binääri ),

\lor

disjunktio ( binääri ),

ja looginen nolla 0 ja looginen yksikkö 1 ovat vakioita .

Käytetyt nimet myös:

Disjunkti on lausekaava , joka on yhden tai useamman literaalin disjunktio (esimerkiksi , ). $x_{1}\tai \neg x_{2}\tai x_{4}$
Konjunkti on lausekaava , joka on yhden tai useamman literaalin (esim . ) konjunktio . $x_{1}\land \neg x_{2}\land x_{4}$

Kaavojen tekstin unaarinen negaatiooperaattori on joko kuvakkeen muodossa ennen operandia ( ) tai viivana operandin yläpuolella ( ), joka on kompaktimpi, mutta yleensä vähemmän havaittavissa. $\lei x$ ${\bar {x}}$

Aksioomit

${\bar {\bar {x))}=x$ , negaation involutiivisuus , kaksoisnegaation poiston laki
$x\lor {\bar {x}}=1$
$\x\lor 1=1$
$\x\tai x=x$
$\x\tai 0=x$
$\ x\land {\bar {x}}=0$
$\x\maa x=x$
$\x\land 0=0$
$\x\maa 1=x$

Loogiset operaatiot

Yksinkertaisin ja laajimmin käytetty esimerkki tällaisesta algebrallisesta järjestelmästä on rakennettu käyttämällä joukkoa B, joka koostuu vain kahdesta elementistä:

B

= { Väärin, totta }

Matemaattisissa lausekkeissa False identifioidaan pääsääntöisesti loogisella nollalla ja Totuus loogisella yksiköllä, ja negaation (NOT), konjunktion (AND) ja disjunktion (OR) operaatiot määritellään tavallisessa merkityksessä. On helppo osoittaa, että annetulla joukolla B voidaan määrittää neljä unaarista ja kuusitoista binäärirelaatiota, ja ne kaikki voidaan saada kolmen valitun operaation superpositiolla.

Tämän matemaattisen työkalupakin perusteella propositionaalinen logiikka tutkii väitteitä ja predikaatteja . Myös lisäoperaatioita esitellään, kuten ekvivalenssi ("jos ja vain jos"), implikaatio ("täten"), modulo two -lisäys (" eksklusiivinen tai "), Schaefferin veto , Piercen nuoli ja muut. $\vasen oikea nuoli$ $\nuoli oikealle$ $\oplus$ $\mid$ $\alaspäin$

Propositiologiikka on toiminut pääasiallisena matemaattisena työkaluna tietokoneiden luomisessa. Se on helppo muuntaa bittilogiikaksi : lauseen totuus ilmaistaan yhdellä bitillä (0 - EPÄTOSI, 1 - TOSI); silloin operaatio saa yksiköstä vähentämisen merkityksen; - ei-modulaarinen lisäys; & - kertolaskuja; - tasa-arvo; - kirjaimellisessa lisäyksen merkityksessä modulo 2 (yksinomainen Or - XOR); - ei summan paremmuus kuin 1 (eli = ). $\neg$ $\lor$ $\vasen oikea nuoli$ $\oplus$ $\mid$ $A$ $\mid$ $B$ ${\näyttötyyli (A+B)<=1}$

Myöhemmin Boolen algebra yleistettiin lauselogiikasta ottamalla käyttöön lauselogiikalle ominaisia aksioomia. Tämä mahdollisti esimerkiksi kubittien logiikan , kolmiosaisen logiikan (kun lausunnon totuudenmukaisuuden vaihtoehtoja on kolme: "tosi", "epätosi" ja "määrittämätön"), monimutkaisen logiikan jne.

Loogisten operaatioiden ominaisuudet

Kommutatiivisuus : . $x\circ y=y\circ x,\circ \in \{\land ,\lor ,\oplus ,\sim ,\mid ,\downarrow \}$
Idempotenssi : . $x\circ x=x,\circ \in \{\land ,\lor \}$
Assosiatiivisuus : . $(x\circ y)\circ z=x\circ (y\circ z),\circ \in \{\land ,\lor ,\oplus ,\sim \}$
Konjunktioiden ja disjunktioiden jakautuminen suhteessa disjunktioon, konjunktiin ja summaan modulo kaksi:
- $x\land (y\lor z)=(x\land y)\lor (x\land z)$ ,
- $x\lor (y\land z)=(x\lor y)\land (x\lor z)$ ,
- $x\land (y\oplus z)=(x\land y)\oplus (x\land z)$ .
De Morganin lait :
- ${\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$ ,
- ${\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$ .
Absorptiolainsäädäntö:
- $x\land (x\tai y)=x$ ,
- $x\lor (x\maa y)=x$ .
Muut (1):
- $x\land {\bar {x}}=x\land 0=x\oplus x=0$ .
- $x\lor {\bar {x}}=x\lor 1=x\sim x=x\rightarrow x=1$ .
- $x\lor x=x\maa x=x\maa 1=x\tai 0=x\oplus 0=x$ .
- $x\oplus 1=x\rightarrow 0=x\sim 0=x\mid x=x\downarrow x={\bar {x))$ .
- ${\bar {\bar {x))}=x$ , negaation involutiivisuus , kaksoisnegaation poiston laki .
Muut (2):
- $x\oplus y=x\land {\bar {y}}\lor {\bar {x}}\land y=(x\lor y)\land ({\bar {x}}\lor {\bar { y)))$ .
- $x\sim y={\overline {x\oplus y}}=1\oplus x\oplus y=x\land y\lor {\bar {x}}\land {\bar {y}}=(x\ lor {\bar {y)))\land ({\bar {x))\lor y)$ .
- $x\rightarrow y={\bar {x}}\lor y=x\land y\oplus x\oplus 1$ .
- $x\lor y=x\oplus y\oplus x\land y$ .
Muut (3) (Lisäys de Morganin lakeihin ):
- $x\mid y={\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$ .
- $x\downarrow y={\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$ .

On olemassa menetelmiä logiikkafunktion yksinkertaistamiseksi: esim. Carnot-kartta , Quine-McCluskey-menetelmä

Historia

Tieteen "logiikan algebran" olemassaolo on velkaa englantilaiselle matemaatikolle George Boolelle , joka opiskeli propositionaalista logiikkaa . Ensimmäisen venäläisen logiikan algebran kurssin piti PS Poretsky Kazanin osavaltion yliopistossa .

Katso myös

Muistiinpanot

↑ Logiikkaalgebra // Suuri Neuvostoliiton Encyclopedia : [30 nidettä] / ch. toim. A. M. Prokhorov . - 3. painos - M . : Neuvostoliiton tietosanakirja, 1969-1978.

Sanakirjat ja tietosanakirjat

Bibliografisissa luetteloissa
BNE : XX4576349 BNF : 119793249 GND : 4146280-4 J9U : 987007293933005171 LCCN : sh85003429 NDL : 00560863

Logiikka

Filosofia • Semantiikka • Syntaksi • Historia

Logiikkaryhmät

klassista logiikkaa	Aristoteelinen logiikka propositionaalinen logiikka Ensimmäisen asteen logiikka Toisen asteen logiikka korkeamman asteen logiikkaa
matemaattinen logiikka	joukko teoria Mallin teoria Lasketettavuuden teoria Todistusteoria ja konstruktiivinen matematiikka Lineaarinen logiikka muodollinen järjestelmä luonnollinen johtopäätös Sekvenssilaskenta Logiikan algebra Asiaankuuluva logiikka Deonttinen logiikka intuitionistinen logiikka Lambek-laskenta
Ei-klassinen logiikka	intuitionismi sumea logiikka Alirakennelogiikka logiikka Kuvauslogiikka Moniarvoinen logiikka Logiikka synteesi Sidontalogiikka Temporaalinen logiikka Modaalinen logiikka ( Hybridilogiikka ) episteeminen logiikka
Filosofinen logiikka	Kriittinen ajattelu epävirallista logiikkaa deduktiivinen päättely

Komponentit

Sieppaus (logiikka)
Todennäköisyys
lausunto
Vähennys / Induktio / Traduction
Todellisuus
induktiivinen päättely
päättely
boolen vakio
Totta
loogista seuraamista
Looginen muoto
Tarpeelliset ja riittävät olosuhteet
Kuvaus
Määritelmä
Korvaus
Paketti
Kiista ( Antinomia )
Synteettinen arviointi / Analyyttinen arviointi
Linkki

Luettelo loogisista symboleista