Mūsdienu pasaulē mēs arvien vairāk izmantojam dažādas automašīnas un sīkrīkus. Un ne tikai tad, kad jāpieliek burtiski necilvēcīgi spēki: pārvietot kravu, pacelt augstumā, rakt garu un dziļu tranšeju u.tml. Automašīnas mūsdienās komplektē roboti, ēdienu gatavo multivarkas, un elementāri aritmētiskie aprēķini ir ko veic kalkulatori. Arvien biežāk mēs dzirdam izteicienu "Būla algebra". Varbūt ir pienācis laiks saprast cilvēka lomu robotu radīšanā un mašīnu spēju atrisināt ne tikai matemātiskas, bet arī loģiskas problēmas.
Loģika
Tulkojumā no grieķu valodas, loģika ir sakārtota domāšanas sistēma, kas rada attiecības starp dotajiem nosacījumiem un ļauj izdarīt secinājumus, pamatojoties uz premisām un pieņēmumiem. Diezgan bieži viens otram jautājam: "Vai tas ir loģiski?" Saņemtā atbilde apstiprina mūsu pieņēmumus vai kritizē domu gājienu. Bet process neapstājas: mēs turpinām spriest.
Dažreiz nosacījumu skaits (ievada) ir tik liels, un attiecības starp tiem ir tik sarežģītas un sarežģītas, ka cilvēka smadzenes nespēj "sagremot" visu uzreiz. Var paiet vairāk nekā viens mēnesis (nedēļa, gads), lai saprastu, kas notiek. Betmūsdienu dzīve mums nedod tādus laika intervālus lēmumu pieņemšanai. Un mēs ķeramies pie datoru palīdzības. Un šeit parādās loģikas algebra ar saviem likumiem un īpašībām. Lejupielādējot visus sākotnējos datus, mēs ļaujam datoram atpazīt visas attiecības, novērst pretrunas un atrast apmierinošu risinājumu.
Matemātika un loģika
Slavenais Gotfrīds Vilhelms Leibnics formulēja jēdzienu "matemātiskā loģika", kuras problēmas bija saprotamas tikai šauram zinātnieku lokam. Šis virziens īpašu interesi neizraisīja, un līdz 19. gadsimta vidum tikai daži cilvēki zināja par matemātisko loģiku.
Lielā interese zinātnieku aprindās izraisīja strīdu, kurā anglis Džordžs Būls paziņoja par nodomu izveidot matemātikas nozari, kurai praktiski nav pielietojuma. Kā atceramies no vēstures, tolaik aktīvi attīstījās rūpnieciskā ražošana, tika izstrādātas visādas palīgmašīnas un darbgaldi, tas ir, visiem zinātniskajiem atklājumiem bija praktiska ievirze.
Raugoties uz priekšu, pieņemsim, ka Būla algebra ir visvairāk izmantotā matemātikas daļa mūsdienu pasaulē. Tāpēc Buls zaudēja argumentus.
Džordžs Būls
Pati autora personība ir pelnījusi īpašu uzmanību. Pat ņemot vērā, ka agrāk cilvēki uzauga pirms mums, joprojām nav iespējams neievērot, ka 16 gadu vecumā J. Buhls mācīja ciema skolā un līdz 20 gadu vecumam Linkolnā atvēra savu skolu. Matemātiķis brīvi pārvaldīja piecas svešvalodas, un brīvajā laikā viņš lasīja darbusŅūtons un Lagrenžs. Un tas viss ir par vienkārša strādnieka dēlu!
1839. gadā Būls pirmo reizi iesniedza savus zinātniskos darbus Kembridžas Mathematical Journal. Zinātniekam ir 24 gadi. Būla darbs tik ļoti ieinteresēja Karaliskās biedrības locekļus, ka 1844. gadā viņš saņēma medaļu par ieguldījumu matemātiskās analīzes attīstībā. Vairāki publicēti darbi, kuros aprakstīti matemātiskās loģikas elementi, ļāva jaunajam matemātiķim ieņemt profesora amatu Korkas apgabala koledžā. Atcerieties, ka pašam Buhlam nebija izglītības.
Ideja
Principā Būla algebra ir ļoti vienkārša. Ir apgalvojumi (loģiski izteicieni), kurus no matemātikas viedokļa var definēt tikai ar diviem vārdiem: “patiess” vai “nepatiess”. Piemēram, pavasarī koki zied - tiesa, vasarā snieg - meli. Šīs matemātikas skaistums ir tāds, ka nav stingri jāizmanto tikai skaitļi. Jebkuri apgalvojumi ar nepārprotamu nozīmi ir diezgan piemēroti spriedumu algebrai.
Tādējādi loģikas algebru var izmantot burtiski visur: plānojot un rakstot instrukcijas, analizējot pretrunīgu informāciju par notikumiem un nosakot darbību secību. Vissvarīgākais ir saprast, ka ir pilnīgi mazsvarīgi, kā mēs nosakām apgalvojuma patiesumu vai nepatiesību. Šie "kā" un "kāpēc" ir jānoņem. Svarīgs ir tikai fakta paziņojums: patiess-nepatiess.
Protams, programmēšanai svarīgas ir loģikas algebras funkcijas, kuras raksta atbilstošāzīmes un simboli. Un apgūt tos nozīmē apgūt jaunu svešvalodu. Nekas nav neiespējams.
Pamatjēdzieni un definīcijas
Neiedziļinoties, tiksim galā ar terminoloģiju. Tātad Būla algebra pieņem:
- paziņojumi;
- loģiskās darbības;
- funkcijas un likumi.
Paziņojumi ir jebkādi apstiprinoši izteicieni, kurus nevar interpretēt neviennozīmīgi. Tie ir rakstīti kā skaitļi (5 > 3) vai formulēti pazīstamos vārdos (zilonis ir lielākais zīdītājs). Tajā pašā laikā frāzei “žirafei nav kakla” arī ir tiesības pastāvēt, tikai Būla algebra to definēs kā “nepatiesu”.
Visiem apgalvojumiem ir jābūt nepārprotamiem, taču tie var būt elementāri un salikti. Pēdējie izmanto loģiskos savienojumus. Tas ir, spriedumu algebrā saliktos apgalvojumus veido, elementārus apgalvojumus pievienojot ar loģisku darbību palīdzību.
Būla algebras darbības
Mēs jau atceramies, ka darbības spriedumu algebrā ir loģiskas. Tāpat kā skaitļu algebra izmanto aritmētiku, lai saskaitītu, atņemtu vai salīdzinātu skaitļus, matemātiskās loģikas elementi ļauj formulēt sarežģītus apgalvojumus, noliegt vai aprēķināt gala rezultātu.
Loģiskās darbības formalizēšanai un vienkāršībai raksta ar mums aritmētikā pazīstamām formulām. Būla algebras īpašības ļauj rakstīt vienādojumus un aprēķināt nezināmos. Loģiskās darbības parasti raksta, izmantojot patiesības tabulu. Tās kolonnasdefinē aprēķina elementus un ar tiem veicamo darbību, un līnijas parāda aprēķina rezultātu.
Pamata loģiskās darbības
Visizplatītākās Būla algebras darbības ir noliegšana (NOT) un loģiskā UN un VAI. Tādā veidā var aprakstīt gandrīz visas darbības spriedumu algebrā. Sīkāk izpētīsim katru no trim operācijām.
Negācija (nav) attiecas tikai uz vienu elementu (operandu). Tāpēc nolieguma operāciju sauc par unāru. Lai uzrakstītu jēdzienu "ne A", izmantojiet šādus simbolus: ¬A, A¯¯¯ vai !A. Tabulas formā tas izskatās šādi:
Nolieguma funkciju raksturo šāds apgalvojums: ja A ir patiess, tad B ir nepatiess. Piemēram, Mēness riņķo ap Zemi – taisnība; Zeme griežas ap Mēnesi - viltus.
Loģiskā reizināšana un saskaitīšana
Loģisko UN sauc par savienojuma darbību. Ko tas nozīmē? Pirmkārt, to var attiecināt uz diviem operandiem, t.i., un tā ir bināra darbība. Otrkārt, ka tikai abu operandu (gan A, gan B) patiesuma gadījumā pati izteiksme ir patiesa. Sakāmvārds "Pacietība un darbs visu sasmalcina" liek domāt, ka tikai abi faktori palīdzēs cilvēkam tikt galā ar grūtībām.
Rakstīšanai izmantotie simboli: A∧B, A⋅B vai A&&B.
Savienojums ir līdzīgs reizināšanai aritmētikā. Dažreiz viņi saka, ka - loģiskā reizināšana. Ja tabulas elementus reizinām pa rindiņām, iegūstam loģiskajam spriešanai līdzīgu rezultātu.
Disjunkcija ir loģiska VAI darbība. Tas aizņem patiesības vērtībuja vismaz viens no apgalvojumiem ir patiess (vai nu A, vai B). To raksta šādi: A∨B, A+B vai A||B. Šo darbību patiesības tabulas ir šādas:
Disjunkcija ir kā aritmētiskā saskaitīšana. Loģiskās pievienošanas darbībai ir tikai viens ierobežojums: 1+1=1. Bet mēs atceramies, ka digitālajā formātā matemātiskā loģika ir ierobežota līdz 0 un 1 (kur 1 ir patiess, 0 ir nepatiess). Piemēram, apgalvojums "muzejā jūs varat redzēt šedevru vai satikt interesantu sarunu biedru" nozīmē, ka jūs varat redzēt mākslas darbus vai jūs varat satikt interesantu cilvēku. Tajā pašā laikā nav izslēgta iespēja, ka abi notikumi varētu notikt vienlaikus.
Funkcijas un likumi
Tātad, mēs jau zinām, kādas loģiskās operācijas izmanto Būla algebra. Funkcijas apraksta visas matemātiskās loģikas elementu īpašības un ļauj vienkāršot sarežģītus saliktos uzdevumu nosacījumus. Šķiet, ka saprotamākā un vienkāršākā īpašība ir atvasinātu darbību noraidīšana. Atvasinājumi ir ekskluzīvas VAI, implikācijas un līdzvērtības. Tā kā esam izpētījuši tikai pamatoperācijas, ņemsim vērā arī tikai to īpašības.
Asociativitāte nozīmē, ka tādos priekšrakstos kā "un A, un B, un C" operandu secībai nav nozīmes. Formula ir uzrakstīta šādi:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Kā redzat, tas ir raksturīgs ne tikai konjunkcijai, bet arī disjunkcijai.
Komutativitāte norāda, ka rezultātskonjunkcija vai disjunkcija nav atkarīga no tā, kurš elements tika ņemts vērā pirmais:
A∧B=B∧A; A∨B=B∨A.
Izplatība ļauj paplašināt iekavas sarežģītās loģiskās izteiksmēs. Noteikumi ir līdzīgi kā iekavu atvēršana reizināšanā un saskaitīšanā algebrā:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Viens un nulles īpašības, kas var būt viens no operandiem, ir līdzīgas arī algebriskajai reizināšanai ar nulli vai vienu un saskaitīšanai ar vienu:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotence norāda, ka, ja attiecībā uz diviem vienādiem operandiem darbības rezultāts izrādās līdzīgs, tad mēs varam “izmest” liekos operandus, kas sarežģī spriešanas gaitu. Gan konjunkcija, gan disjunkcija ir idempotentas darbības.
B∧B=B; B∨B=B.
Absorbcija arī ļauj mums vienkāršot vienādojumus. Absorbcija norāda, ka, ja izteiksmei ar vienu operandu tiek piemērota cita darbība ar to pašu elementu, rezultāts ir absorbējošās darbības operands.
A∧B∨B=B; (A∨B)∧B=B.
Darbību secība
Darbību secībai nav maza nozīme. Faktiski, kas attiecas uz algebru, ir prioritāra funkcija, ko izmanto Būla algebra. Formulas var vienkāršot tikai tad, ja tiek ievērota darbību nozīme. Sarindojot no nozīmīgākā līdz mazākajam, mēs iegūstam šādu secību:
1. Atteikums.
2. Saikne.
3. Disjunkcija, ekskluzīvaVAI.
4. Implikācija, līdzvērtība.
Kā redzat, tikai noliegumam un savienojumam nav vienādas prioritātes. Un disjunkcijas un XOR prioritātes ir vienādas, kā arī implikācijas un ekvivalences prioritātes.
Iesaistes un līdzvērtības funkcijas
Kā jau teicām, matemātiskā loģika un algoritmu teorija papildus loģiskajām pamatoperācijām izmanto atvasinājumus. Visbiežāk lietotās ir implikācija un ekvivalence.
Implikācija jeb loģiskās sekas ir apgalvojums, kurā viena darbība ir nosacījums, bet otra ir tās īstenošanas sekas. Citiem vārdiem sakot, šis ir teikums ar prievārdiem "ja … tad." "Ja jums patīk braukt, patīk nēsāt ragavas." Tas ir, lai slēpotu, jāpievelk ragavas kalnā. Ja nav vēlēšanās doties lejā no kalna, tad ragavas nav jānēsā. Tas ir rakstīts šādi: A→B vai A⇒B.
Ekvivalence pieņem, ka iegūtā darbība notiek tikai tad, ja abi operandi ir patiesi. Piemēram, nakts pārvēršas dienā, kad (un tikai tad) saule uzlec pāri horizontam. Matemātiskās loģikas valodā šo apgalvojumu raksta šādi: A≡B, A⇔B, A==B.
Citi Būla algebras likumi
Spriedumu algebra attīstās, un daudzi ieinteresēti zinātnieki ir formulējuši jaunus likumus. Par slavenākajiem tiek uzskatīti skotu matemātiķa O. de Morgana postulāti. Viņš pamanīja un definēja tādas īpašības kā tuvu noliegums, papildinājums un dubultā noliegums.
Aizvērt noliegumu nozīmē, ka pirms iekavām nav noliegšanas:nav (A vai B)=nav A vai NAV B.
Kad operands tiek noliegts, neatkarīgi no tā vērtības, tiek runāts par papildinājumu:
B∧¬B=0; B∨¬B=1.
Un visbeidzot, dubultā noliegšana kompensē sevi. Tie. vai nu noliegums pazūd pirms operanda, vai arī paliek tikai viens.
Kā atrisināt testus
Matemātiskā loģika ietver doto vienādojumu vienkāršošanu. Tāpat kā algebrā, vispirms ir jāpadara nosacījums pēc iespējas vienkāršāks (atbrīvojieties no sarežģītām ievadēm un darbībām ar tām), un pēc tam sāciet meklēt pareizo atbildi.
Ko var darīt, lai vienkāršotu? Pārvērtiet visas atvasinātās darbības uz vienkāršām. Pēc tam atveriet visas iekavas (vai otrādi, izņemiet to no iekavām, lai saīsinātu šo elementu). Nākamajam solim vajadzētu būt Būla algebras īpašību pielietošanai praksē (absorbcija, nulles un viena īpašības utt.).
Galu galā vienādojumam jāsastāv no minimālā nezināmo skaita, kas apvienots ar vienkāršām darbībām. Vienkāršākais veids, kā atrast risinājumu, ir sasniegt lielu skaitu tuvu negatīvu. Tad atbilde parādīsies it kā pati no sevis.
