Utangulizi.
Kusudi.
Sehemu mpya za kozi ya hisabati ya kipekee, ingawa inatekelezwa kwa njia ya programu za kielimu na safu ya mihadhara, bado haipo katika mfumo wa monographs, angalau kwa Kirusi, kwani kozi ya hesabu ya vyuo vikuu vya ufundi inazingatia shida za zamani zilizotumika ambazo. wahandisi walilazimika kusuluhisha. Hasa, katika mantiki ya hisabati ilikuwa kupunguza mizunguko ya mantiki, ambayo imepoteza umuhimu wake leo.
Inafurahisha kutambua kwamba nadharia ya usanisi wa mizunguko ya kimantiki, baada ya kupitia "mzunguko kamili wa kibaolojia" mbele ya macho ya kizazi kimoja cha watafiti, ni mfano mzuri sana wa jinsi matawi ya sayansi ya kiufundi ambayo hayajaunganishwa vibaya na msingi. sayansi ni rahisi kuathiriwa na kupitwa na wakati. Miaka 10 iliyopita kila kitu magazeti ya kiufundi zilijazwa na makala juu ya kupunguza na usanisi wa saketi za mantiki. Njia nyingi za kupunguza zilizotengenezwa na wanasayansi sasa zimesahaulika na hazihitajiki katika mazoezi. Na maoni hayo ambayo yalizingatiwa kuwa ya kinadharia wakati huo yalipata matumizi ya vitendo ndani teknolojia ya kisasa. Kwa mfano, mantiki ya fuzzy, Petri nets, na nadharia ya algoriti zimestahimili mtihani wa wakati na hutumiwa sana katika nyanja mbalimbali za cybernetics na upangaji programu kama vile upangaji wa mifumo, uchangamano wa hesabu na akili bandia.
Na nadharia ya algorithms ikawa sehemu kuu ya hisabati ya kipekee. Walakini, tofauti na monographs nyingi katika Kirusi, wakati wa mihadhara maswala haya yanawasilishwa kama njia ya kutatua shida za uhandisi za vitendo.
Kama unavyojua, baada ya kila muongo, vifaa vya kompyuta, mifumo ya uendeshaji, zana za ufikiaji na programu zenyewe hubadilika sana. Walakini, miundo na algoriti zinazozisimamia zinabaki bila kubadilika kwa muda mrefu zaidi. Misingi hii ilianza kuwekwa maelfu ya miaka iliyopita, wakati mantiki rasmi ilitengenezwa na algorithms ya kwanza ilitengenezwa.
Mantiki ya hisabati na nadharia ya algoriti kwa kawaida ni ya sayansi ya kimsingi na inachukuliwa kuwa na uhusiano mdogo na mazoezi na ni ngumu kuelewa. Hakika, wakati J. Boole aliunda vifaa vya hisabati vya algebra ya Boolean, haikupata matumizi ya vitendo kwa muda mrefu, lakini katika karne ya 20 ilikuwa ni kifaa hiki cha hisabati ambacho kilifanya iwezekanavyo kuunda vipengele vyote vya kompyuta. Kwa hivyo, ya kwanza ya chuki hizi inakanushwa kwa mafanikio na maendeleo ya teknolojia ya kompyuta.
Ama chuki juu ya ugumu wa kuelewa taaluma hii, kwa kiasi kikubwa inatokana na ukweli kwamba vitabu vya mantiki ya hisabati na nadharia ya algoriti viliandikwa na wanahisabati kwa wanahisabati.
Sasa, wakati uwezo wa teknolojia ya kompyuta umeongezeka mara nyingi zaidi, na kuna kompyuta nyingi zaidi za kibinafsi kuliko kuna watu ambao wanajua jinsi ya kuzitumia kwa ufanisi, kuelewa ni nini kinachoweza na kisichoweza kufanywa kwa msaada wa teknolojia ya kisasa ya kompyuta. umuhimu wa kipekee.
Ilikuwa nadharia ya jumla ya algorithms ambayo ilionyesha kuwa kuna shida ambazo haziwezi kusuluhishwa bila kujali nguvu ya kompyuta ina nguvu gani, na tawi lake linalokua haraka - nadharia ya ugumu wa hesabu - hatua kwa hatua husababisha kuelewa kuwa kuna shida ambazo zinaweza kutatuliwa. lakini utata wa kimalengo, na utata wao unaweza kugeuka kuwa kiasi fulani kwa maana kabisa, i.e. kivitendo haipatikani kwa kompyuta za kisasa.
Kozi hii iliweka malengo yafuatayo:
1. Wasilisha masuala yote yanayozingatiwa kwa urahisi iwezekanavyo, lakini si rahisi kuliko inavyohitajika kwa mtaalamu aliyehitimu sana.
2. Matatizo ya vitendo muundo na uchambuzi wa mifumo ya habari ndio mahali pa kuanzia, na vifaa rasmi ndio njia ufumbuzi wa utaratibu matatizo haya. Ni imani yetu kubwa kwamba mwanafunzi si chombo kinachohitaji kujazwa, bali ni tochi inayohitaji kuwashwa.
3. Kila sehemu ya kozi ina maswali ya kujipima. Kwa assimilation kozi hii mwanafunzi anatakiwa kujibu maswali haya yote.
Kama matokeo ya kusimamia kozi hii, mwanafunzi, kwa kuzingatia ufahamu wazi wa sehemu husika za kinadharia, anapaswa kuwa na uwezo wa:
Tekeleza aina rahisi zaidi ya mabadiliko ya kimantiki ya habari kwa misingi ya kiholela ya kazi za kimantiki;
Angazia katika hoja za ushahidi lugha ya asili muundo wa kimantiki, jenga miradi rasmi ya uthibitisho na uangalie usahihi wake.
1.2 Uwakilishi wa kimantiki
Uwakilishi wa kimantiki - maelezo ya mfumo, mchakato, jambo chini ya utafiti katika mfumo wa kuweka kauli tata imeundwa na kauli rahisi (za msingi). Na viunganishi vya kimantiki
kati yao. Uwasilishaji wa kimantiki na vifaa vyao vinaonyeshwa na mali fulani na seti ya mabadiliko yanayoruhusiwa juu yao (operesheni, sheria za uelekezaji, n.k.), kutekeleza zile zilizotengenezwa rasmi (hisabati) mantiki mbinu sahihi hoja - sheria za mantiki.
Mbinu (kanuni) za uwasilishaji rasmi wa taarifa, ujenzi wa taarifa mpya kutoka kwa zilizopo kwa kutumia mabadiliko sahihi ya kimantiki, na pia njia (mbinu) za kubaini ukweli au uwongo wa taarifa zinasomwa katika mantiki ya hisabati. Mantiki ya kisasa ya hisabati inajumuisha sehemu kuu mbili: mantiki ya kauli na kuifunika mantiki ya kitabiri(Mchoro 1.1), kwa ajili ya ujenzi ambao kuna mbinu mbili (lugha), na kutengeneza lahaja mbili za mantiki rasmi: algebra ya mantiki Na hesabu ya kimantiki. Kuna mawasiliano ya moja kwa moja kati ya dhana za kimsingi za lugha hizi za mantiki rasmi. Isomorphism yao hatimaye inahakikishwa na umoja wa mabadiliko yanayokubalika.
Mchele. 1.1
Vitu kuu vya matawi ya jadi ya mantiki ni taarifa.
Kauli - sentensi ya kutangaza (kauli, hukumu), o ambayo ina mantiki kusema hivyo kweli au uongo. Wote maarifa ya kisayansi(sheria na matukio ya fizikia, kemia, biolojia, n.k., nadharia za hisabati, n.k.), matukio ya maisha ya kila siku, hali zinazotokea katika michakato ya uchumi na usimamizi huundwa kwa namna ya taarifa. Sentensi za lazima na za kuuliza sio kauli.
Mifano ya taarifa: "Mara mbili ni nne", "Tunaishi katika karne ya 21", "Ruble ni sarafu ya Urusi", "Alyosha ni kaka wa Oleg", "Shughuli za umoja, makutano na nyongeza ni shughuli za Boolean kwenye seti. ”, “Mwanadamu ni wa kufa” , “Kupanga upya maeneo ya istilahi hakubadilishi jumla,” “Leo ni Jumatatu,” “Mvua ikinyesha, unapaswa kuchukua mwavuli.”
Ili kufanya kazi zaidi na sentensi hizi kama taarifa, lazima tujue kwa kila moja ikiwa ni kweli au si kweli, i.e. kuwajua thamani ya ukweli (ukweli). Kumbuka kwamba katika idadi ya matukio ukweli au uwongo wa taarifa inategemea ukweli gani maalum (mfumo, mchakato, jambo) tunajaribu kuelezea kwa msaada wake. Katika hali hii, taarifa iliyotolewa inasemekana kuwa ya kweli (au uongo) katika tafsiri fulani (muktadha). Tunazidi kuchukulia kuwa muktadha umetolewa na taarifa ina thamani fulani ya ukweli.
1.3 Historia ya mantiki ya hisabati iliyoendelezwa
Mantiki kama sayansi iliundwa katika karne ya 4. BC. Iliundwa na mwanasayansi wa Kigiriki Aristotle.Neno "mantiki" linatokana na neno la Kigiriki "logos", ambalo kwa upande mmoja linamaanisha "neno" au "ufafanuzi", na kwa upande mwingine, kufikiri. KATIKA kamusi ya ufafanuzi Ozhegova S.I. Inasemwa: “Mantiki ni sayansi ya sheria za kufikiri na namna zake.” Katika karne ya 17 Mwanasayansi wa Ujerumani Leibniz alipanga kuunda sayansi mpya, ambayo itakuwa "sanaa ya kuhesabu ukweli" . Katika mantiki hii, kulingana na Leibniz, kila kauli ingekuwa na ishara inayolingana, na hoja ingekuwa na namna ya hesabu. Wazo hili la Leibniz, akiwa hajakutana na uelewa wa watu wa wakati wake, halikuenezwa au kukuzwa na kubaki kuwa nadhani nzuri.
Tu katikati ya karne ya 19. Mwanahisabati wa Ireland George Boole aliunga mkono wazo la Leibniz.” Mnamo 1854, aliandika kitabu “Uchunguzi wa sheria za mawazo,” ambacho kiliweka msingi wa aljebra ya mantiki, ambamo sheria zinazofanana na za algebra ya kawaida hutumika, lakini herufi hizo zinatumika. sio kuashiria nambari, lakini taarifa. Katika lugha ya algebra ya Boolean, mtu anaweza kuelezea hoja na "kuhesabu" matokeo yake. Walakini, haijumuishi hoja zote, lakini aina fulani tu yake. , Kwa hivyo, algebra ya Boole inachukuliwa kuwa hesabu ya pendekezo.
Aljebra ya mantiki ya Boole ilikuwa kiinitete cha sayansi mpya - mantiki ya hisabati. Kinyume chake, mantiki ya Aristotle inaitwa mantiki rasmi ya kimapokeo. Jina “mantiki ya hisabati” linaonyesha sifa mbili za sayansi hii: kwanza, mantiki ya hisabati ni mantiki inayotumia lugha na mbinu za hisabati; pili, mantiki ya hisabati huletwa hai na mahitaji ya hisabati.
Mwishoni mwa karne ya 19. Nadharia iliyowekwa iliyoundwa na Georg Cantor ilionekana kuwa msingi wa kutegemewa kwa hisabati zote, pamoja na mantiki ya hisabati, angalau kwa calculus propositional (Boole algebra), kwa sababu. Ilibadilika kuwa Cantor algebra (nadharia iliyowekwa) ni isomorphic kwa algebra ya Boole.
Mantiki ya hisabati yenyewe ikawa tawi la hisabati, ambalo mwanzoni lilionekana shahada ya juu dhahania na mbali kabisa na matumizi ya vitendo. Walakini, eneo hili halikubaki kikoa cha wanahisabati "safi" kwa muda mrefu. Mwanzoni mwa karne ya 20. (1910) Mwanasayansi wa Kirusi Ehrenfest P.S. ilionyesha uwezekano wa kutumia vifaa vya algebra ya Boolean katika mawasiliano ya simu kuelezea kubadili saketi. Mnamo 1938-1940, karibu wakati huo huo, kazi za mwanasayansi wa Soviet V.I. Shestakov, mwanasayansi wa Amerika Shannon na wanasayansi wa Kijapani Nakashima na Hakazawa walionekana juu ya matumizi ya mantiki ya hisabati katika teknolojia ya dijiti. Monograph ya kwanza iliyotolewa kwa matumizi ya mantiki ya hisabati katika muundo wa vifaa vya dijiti ilichapishwa huko USSR na mwanasayansi wa Soviet M. A. Gavrilov. mnamo 1950. Jukumu la mantiki ya hisabati katika maendeleo ya teknolojia ya kisasa ya microprocessor ni muhimu sana: inatumika katika muundo wa vifaa vya kompyuta, katika ukuzaji wa lugha zote za programu na katika muundo wa vifaa vya kiotomatiki.
Wanasayansi walitoa mchango mkubwa katika maendeleo ya mantiki ya hisabati nchi mbalimbali: Profesa wa Chuo Kikuu cha Kazan Poretsky P.S., de-Morgan, Pierce, Turing, Kolmogorov A.N., Heidel K. et al.
1.4 Maswali ya kujipima.
1. Tengeneza malengo ya kozi
Chuo Kikuu cha Volzhsky kilichoitwa baada. Tatishcheva.
Mihadhara juu ya mantiki ya hisabati na nadharia ya algorithms.
Imetungwa na: Profesa Mshiriki S.V. Kaverin.
Sura ya I. Aljebra ya Mantiki.
§1.1. Ufafanuzi wa kazi ya Boolean.
Kazi ya Boolean y=f(x 1 ,x 2 ,…,x n)kutoka P vigezo x 1 , x 2 ,...,x n ni chaguo la kukokotoa ambalo hoja na chaguo za kukokotoa zinaweza kuchukua thamani ama 0 au 1, i.e. kazi ya Boolean ni sheria ambayo seti ya kiholela ya zero na ndio
(x 1 ,x 2 ,...,x n) imetolewa kwa thamani 0 au 1.
Kazi za Boolean pia inaitwa mantiki kazi za aljebra, kazi za binary na vitendaji vya kubadili.
Kitendaji cha Boolean kutoka n Vigezo vinaweza kubainishwa na jedwali la ukweli ambalo seti za maadili ya hoja hupangwa kwa mpangilio wa kupanda wa nambari zao. : mwanzoni uajiri unaendelea, inayowakilisha upanuzi wa binary wa 0 (seti hii imehesabiwa 0); kisha inakuja seti, ambayo ni upanuzi wa binary wa 1, kisha 2, 3, nk. Seti ya mwisho inajumuisha n vitengo na ni upanuzi wa binary wa nambari 2 n-1 (utaratibu huu wa mpangilio wa seti utaitwa mpangilio wa leksikografia) Ikizingatiwa kuwa hesabu huanza kutoka 0, na thamani ya chaguo za kukokotoa za Boolean inaweza kuwa 0 au n
1, tunahitimisha kuwa kuna kazi 22 tofauti za Boolean za n vigezo. Kwa hivyo, kuna, kwa mfano, kazi 16 za Boolean za vigezo viwili, 256 kati ya tatu, nk.
Mfano 1.1.1.(kura) . Hebu tuchunguze kifaa ambacho kinarekodi kupitishwa kwa azimio fulani na "kamati ya watatu". Kila mwanachama wa kamati anabofya kitufe chake anapoidhinisha azimio. Ikiwa wajumbe wengi watapiga kura ya ndiyo, azimio hilo litapitishwa. Hii inarekodiwa na kifaa cha kurekodi. Kwa hivyo, kifaa hutekeleza kazi ya f(x,y,z ) , ambaye jedwali la ukweli lina umbo
| x | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Chaguo za kukokotoa za Boolean pia hubainishwa kwa njia ya kipekee kwa kuorodhesha nakala zote ambazo huchukua thamani ya 0, au kwa kuorodhesha nakala zote ambazo huchukua thamani ya 1. Chaguo za kukokotoa zilizopatikana katika mfano. f pia inaweza kubainishwa na mfumo ufuatao wa usawa: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
Vekta ya thamani za utendakazi za Boolean y=f(x 1 ,x 2 ,…,x n) ni seti iliyopangwa ya thamani zote za chaguo za kukokotoa f, ambapo thamani hupangwa kwa mpangilio wa leksikografia. Kwa mfano, acha kazi ya vigeu vitatu f ibainishwe na vekta ya thamani (0000 0010) na ni muhimu kupata seti ambayo f inachukua thamani 1. Kwa sababu 1 iko katika nafasi ya 7, na inaingia mpangilio wa kileksikografia huanza saa 0, basi tunahitaji kupata upanuzi wa binary wa 6. Kwa hivyo, kazi f inachukua thamani 1 kwenye seti (110).
§1.2. Vipengele vya msingi vya Boolean.
Miongoni mwa vitendaji vya Boolean, kinachojulikana kama vitendaji vya msingi vya Boolean vinajitokeza, kwa njia ambayo kazi yoyote ya Boolean ya idadi yoyote ya vigeu inaweza kuelezewa.
1. Kitendakazi cha Boolean f(x 1 ,x 2 ,…,x n) kuchukua thamani 1 kwenye seti zote za sufuri na zile huitwa. mara kwa mara 1, au kitengo kinachofanana. Uteuzi : 1 .
2. Kitendakazi cha Boolean f(x 1 ,x 2 ,…,x n) kuchukua thamani 0 kwenye seti zote za sufuri na zile huitwa. mara kwa mara 0, au sufuri sawa. Uteuzi : 0 .
3. Kukataa ni kazi ya Boolean ya kigezo kimoja ambacho kinafafanuliwa na jedwali lifuatalo la ukweli
Majina mengine : kuzidisha mantiki (bidhaa); mantiki "na".
Uteuzi : x&y, xÿy, x⁄y, dakika(x,y).
5. Utengano
Jina lingine : matokeo ya kimantiki. Uteuzi : xØy, xfly, xy.
7. Usawa ni kazi ya Boolean ya vigeu viwili ambavyo vinafafanuliwa na jedwali lifuatalo la ukweli
Jina lingine : kupinga usawa. Uteuzi : x∆y, x+y.
9. Kiharusi cha Schaeffer ni kazi ya Boolean ya vigeu viwili ambavyo vinafafanuliwa na jedwali lifuatalo la ukweli
Jina lingine : kukanusha kwa kutenganisha, kimantiki "si-au", kazi ya Webb.
Uteuzi : x∞y ; kwa kazi ya Webb - x±y.
Maoni. Alama Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ zinazohusika katika nukuu kazi za msingi tutaziita viunganishi au uendeshaji.
§1.3. Inabainisha vitendaji vya Boolean kwa kutumia za msingi.
Ukibadilisha baadhi ya vitendakazi vya Boolean katika kitendakazi cha kimantiki badala ya vigeu, matokeo yake ni kitendakazi kipya cha Boolean kinachoitwa. nafasi ya juu kazi zilizobadilishwa (kazi ngumu). Kwa kutumia superposition, unaweza kupata kazi ngumu zaidi ambazo zinaweza kutegemea idadi yoyote ya vigezo. Tutaita uandishi wa vitendaji vya Boolean kulingana na vitendaji vya msingi vya Boolean fomula kutekeleza kazi hii.
Mfano 1.3.1. Acha kitendakazi cha msingi cha Boolean x¤y itolewe. Wacha tubadilishe chaguo za kukokotoa x 1 ∞x 2 badala ya x. Tunapata kitendakazi cha vigeu vitatu (x 1 ∞x 2)¤y. Ikiwa badala ya kutofautiana y tunabadilisha, kwa mfano, x 3 ∆x 4, basi tunapata kazi mpya ya vigezo vinne: (x 1 ∞x 2)¤(x 3 ∆x 4). Ni wazi, kwa njia hii tutapata vitendaji vya Boolean, ambavyo vitaonyeshwa kupitia vitendaji vya msingi vya Boolean.
Kuangalia mbele, tunaona kwamba yoyote kitendakazi cha Boolean kinaweza kuwakilishwa kama nafasi kuu ya vitendaji vya msingi.
Ili kuandika kazi ngumu kwa ushikamanifu zaidi, tunatanguliza kanuni zifuatazo: : 1) mabano ya nje yameachwa; 2) shughuli katika mabano hufanyika kwanza; 3) inachukuliwa kuwa kipaumbele cha viunganisho hupungua kwa utaratibu ufuatao : Ÿ, ⁄, ¤, Ø, ~. Kwa viunganishi sawa na viunganishi vilivyosalia (∆,|,∞), unapaswa kuweka mabano kwa sasa.
Mifano 1.3.2. Katika fomula x⁄y¤z, mabano yamewekwa kama ifuatavyo: ((x⁄y)¤z), kwa sababu operesheni ⁄ ina nguvu zaidi kuliko operesheni ¤ kulingana na makubaliano yetu.
1. Katika fomula x¤y~zØx mabano yamewekwa kama ifuatavyo: ((x¤y)~(zØx))
2. Katika fomula (x∆y)~zØxy¤Ÿz mabano yamewekwa kama ifuatavyo: ((x∆y)~(zØ((xy)¤(Ÿz))))).
3. Formula xØyØz, kufuatia makubaliano yetu, haijaandikwa kwa usahihi, kwa sababu kuweka mabano matokeo katika mbili kazi tofauti: ((xØy)Øz) na (xØ(yØz)).
§1.4. Vigezo muhimu na visivyo vya maana.
Kitendaji cha Boolean y=f(x 1 ,x 2 ,…,x n) inategemea kwa kiasi kikubwa kutoka kwa kutofautiana x k ikiwa seti kama hiyo ya maadili ipo a 1 ,a 2 ,…,a k - 1, a k+1, a k + 2 ,…, a n hiyo f (a 1, a 2,…,a k-1 , 0 ,a k+1,a k+2,...,a n) π f (a 1, a 2,…,a k-1 , 1 ,a k+1,a k+2,...,a n).
Kwa kesi hii x k inaitwa kigezo muhimu , vinginevyo x k inaitwa tofauti isiyo na maana (dummy). . Kwa maneno mengine, kutofautisha sio muhimu ikiwa kuibadilisha hakubadilishi thamani ya chaguo la kukokotoa.
Mfano 1.4.1. Acha utendakazi wa Boolean f 1 (x 1 ,x 2) na f 2 (x 1 ,x 2) ubainishwe na jedwali lifuatalo la ukweli:
| x 1 | x 2 | f 1 (x 1 ,x 2) | f 2 (x 1 ,x 2) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
Kwa kazi hizi tofauti x 1 - ni muhimu, na tofauti x 2 sio muhimu.
Ni wazi, chaguo za kukokotoa za Boolean hazibadilishi thamani zao kwa kuanzisha (au kuondoa) viambajengo visivyo na umuhimu. Kwa hiyo, katika kile kinachofuata, kazi za Boolean zinazingatiwa hadi vigezo visivyo muhimu (katika mfano tunaweza kuandika: f 1 (x 1, x 2) = x 1, f 2 (x 1, x 2) = Ÿx 1).
§1.5. Meza za ukweli. Kazi zinazolingana.
Kujua majedwali ya ukweli kwa vipengele vya msingi, unaweza kuhesabu jedwali la ukweli la chaguo za kukokotoa ambalo fomula hii inatekeleza.
Mfano 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)
Kwa hivyo, formula F1 hutekelezea mtengano. Mfano 1.5.2. F2=x 1 ⁄x 2 Øx 1
Kwa hivyo, formula F3 hutekelezea mtengano.
Kazi za Boolean f1 na f2 zinaitwa sawa, ikiwa kwenye kila seti ( a 1 ,a 2 ,…, n) zero na zile, maadili ya kazi yanaambatana. Dokezo la vitendaji sawa ni kama ifuatavyo : f1=f2.
Kulingana na mifano iliyotolewa 1-3, tunaweza kuandika
X 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)=x 1 ¤x 2;
X 1 ⁄x 2 Øx 1 =1;
((x 1 ⁄x 2)∆x 1)∆x 2 =x 1 ¤x 2.
§1.6. Usawa wa kimsingi.
Usawa uliotolewa mara nyingi ni muhimu wakati wa kufanya kazi na vitendaji vya Boolean.
Chini ya H, H1, H2,... simamia baadhi ya vitendaji vya Boolean.
1. Sheria ya kukanusha mara mbili: H = H.
2. Upungufu wa nguvu za kiume
3. Mawasiliano:
H1*H2=H2*H1, ambapo ishara * inamaanisha mojawapo ya viunganishi &, ¤, ∆,
4. Ushirikiano:
H1*(H2*H3)=(H1*H2)*H3, ambapo ishara * inamaanisha mojawapo ya viunganishi &, ¤, ∆, ~.
5. Usambazaji:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. Sheria za De Morgan:
H1& H2 = H1 ∨ H2, H1∨ H2 = H1 & H2.
7. Kanuni za kuchukua:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Sheria za kuunganisha:
H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.
9. Sheria za ubadilishaji: H ∨ H = 1, H & H = 0.
10. Kanuni za uendeshaji na viunga:
H¤1=1, H&1=H, H¤0=H, H&0=0.
Ili kuangalia ukweli wa usawa hapo juu, inatosha kuunda majedwali ya ukweli yanayolingana.
Kumbuka kuwa sifa ya ushirika ya operesheni inaruhusu operesheni hii kuongezwa kwa idadi yoyote ya vigeu. Kwa hivyo, kwa mfano, nukuu x¤у¤z¤w ni sahihi, kwa sababu mpangilio wowote wa mabano husababisha kazi sawa. Asili ya mabadiliko ya operesheni hukuruhusu kubadilisha vigeu katika fomula. Kwa mfano, x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Ukamilifu wa kiutendaji.
Katika kompyuta ya kisasa ya kisasa ya kisasa, nambari ni 0 na 1. Kwa hiyo, maagizo ambayo processor hufanya ni kazi za Boolean. Hapo chini tutaonyesha kwamba kipengele chochote cha kukokotoa cha Boolean kinatekelezwa kupitia muunganisho, mtengano na ukanushaji. Kwa hivyo, inawezekana kujenga processor inayohitajika, ikiwa na vitu vyake vya ovyo vinavyotekelezea kiunganishi, mgawanyiko na kukanusha. Sehemu hii imejitolea kujibu swali: je, kuna (na ikiwa ni hivyo, nini) mifumo mingine ya utendaji wa Boolean ambayo ina sifa ambayo inaweza kutumika kueleza vipengele vingine vyote.
Wacha tuanzishe idadi ya madarasa ya kazi.
1. Darasa la kazi zinazohifadhi mara kwa mara 0, i.e. kazi kama hizo
2. Darasa la kazi zinazohifadhi mara kwa mara 1, i.e. kazi kama hizo
3. Darasa la kazi za kujitegemea mbili, i.e. vitendaji hivyo y=f(x 1 ,x 2 ,…,x n) ili f(x 1 , x 2 ,… , x n) = f(x 1 , x 2 ,… , x n) .
4. Darasa la kazi za mstari, i.e. vitendaji hivyo y=f(x 1 ,x 2 ,…,x n), ambavyo vinaweza kuwakilishwa kama f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ c n x n, ambapo c 0, c 1, c 2 ...migawo ambayo inaweza kuchukua thamani 0 au 1.
5. Darasa la kazi za monotonic. Kwenye seti ya sufuri na zile Bn =((x 1 ,x 2 ,…,x n):x i œ(0,1),i=1,2,…,n) tunatanguliza mpangilio wa sehemu kama ifuatavyo:
(a 1 ,a 2,...,a n)§( b 1 ,b 2 ,...,b n) ikiwa na tu ikiwa a 1 § b 1 ,a 2 § b 2,…,a n § b n. Kitendakazi f(x 1, x 2,..., x n) kinaitwa monotonic ikiwa kwa vipengele vyovyote viwili kutoka kwa B n hivyo
(a 1 ,a 2,...,a n)§( b 1 ,b 2 ,...,b n) inafuata kwamba f ( a 1 ,a 2,...,a n)§f( b 1 ,b 2 ,...,b n).
Mfumo wa S wa utendakazi wa Boolean, nafasi ya juu ambayo inaweza kuwakilisha kazi yoyote ya Boolean, inaitwa imekamilika kiutendaji . Inasemekana kuwa mfumo kamili wa utendaji wa S wa fomu za utendaji wa Boolean msingi katika nafasi ya kimantiki. Msingi wa S unaitwa Ndogo , ikiwa kuondolewa kwa kazi yoyote kutoka kwake hugeuza mfumo huu kuwa haujakamilika.
Kigezo cha ukamilifu (Nadharia ya chapisho) . Mfumo wa S wa vitendaji vya Boolean hukamilika ikiwa na tu ikiwa unajumuisha angalau chaguo la kukokotoa: 0 isiyo ya kuhifadhi, isiyo ya kawaida 1, isiyo ya kibinafsi, isiyo ya mstari na isiyo ya monotoniki.
Jedwali 1.7 linaonyesha sifa ambazo kipengele cha msingi cha kukokotoa cha Boolean (alama * inaonyesha sifa ambayo kipengele fulani cha kukokotoa kina).
Kwa kutumia nadharia ya Chapisho na Jedwali 1.7, unaweza kuunda misingi kutoka kwa vipengele vya msingi kulingana na sheria ifuatayo. Kwa kuchagua kazi yoyote ya msingi ya Boolean na kuiongezea, ikiwa ni lazima, na kazi zingine ili zote kwa pamoja zikidhi nadharia kuhusu. ukamilifu wa utendaji. Kupitia kazi za msingi huu tunaweza kueleza Wote kazi zingine za Boolean.
Wacha tuunda besi kadhaa zinazotumiwa mara kwa mara katika programu.
Jedwali 1.7
| Jina | Uteuzi | Kutoweza kuhimilika mara kwa mara |
Kutoweza kuhimilika mara kwa mara |
Samodvoys uhalali |
||
| Const.0 | 0 | * | * | |||
| Const.1 | 1 | * | * | |||
| Hasi | Ÿ | * | * | * | ||
| Kongyun. | & | * | * | |||
| Utengano. | ¤ | * | * | |||
| Implic. | Ø | * | * | * | * | |
| Sawa. | ~ | * | * | * | ||
| Jumla kwa mod_2 | ∆ | * | * | * | ||
| | | * | * | * | * | * | |
| Mshale wa Pierce | ∞ | * | * | * | * | * |
1. Mfumo wa vitendakazi S1=(Ÿ,⁄,¤) huunda msingi. Ili kupunguza kitendakazi cha Boolean hadi fomu iliyo na viunganishi pekee kutoka kwa msingi S1, usawa ufuatao unaweza kuwa muhimu: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , xy = x ∨ y , x ↓ y = x & y .
2. Mfumo S2=(Ÿ,&) huunda msingi. Kazi ya kiholela inaweza kwanza kupunguzwa kwa fomu iliyo na viunganishi kutoka S1 na kisha
tumia uhusiano x ∨ y = x ⋅ y.
3. Mfumo S3=(Ÿ,¤) huunda msingi. Kitendaji kiholela kinaweza kwanza kupunguzwa hadi fomu iliyo na viunganishi kutoka S1 na kisha
tumia uhusiano x ⋅ y = x ∨ y.
4. Mfumo S4=(1,&,∆) huunda msingi. Kitendaji kiholela kinaweza kwanza kupunguzwa hadi fomu iliyo na viunganishi kutoka S1 na kisha kutumia mahusiano x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y.
5. Mfumo S5=(|) huunda msingi. Chaguo za kukokotoa kiholela zinaweza kwanza kupunguzwa hadi fomu iliyo na viunganishi kutoka S2 na kisha kutumia mahusiano x ⋅ y = x y , x = xx .
6. Mfumo S6=(∞) huunda msingi. Kazi ya kiholela inaweza kwanza kupunguzwa hadi fomu iliyo na viunganishi kutoka S3 na kisha
tumia mahusiano x ∨ y = x ↓ y, x = x ↓ x.
7. Mfumo S7=(Ø,0) huunda msingi.
Mfano 1.7.1. Andika chaguo za kukokotoa x¨(y∆z) katika msingi S1=(Ÿ,⁄,¤). x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅ (x ∨ y ∨ z z)
Sura ya II. algebra ya Boolean.
Seti ya booleans zote katika msingi S1=( ÿ, &, ⁄} fomu algebra ya Boolean. Kwa hivyo, katika aljebra ya Boolean, fomula zote zimeandikwa kwa kutumia viunganishi vitatu: Ÿ, &, ¤. Tulichunguza kwa kiasi sifa za aljebra hii katika Sura ya I (tazama, kwa mfano, usawa wa kimsingi). Sura hii inahusu sifa mahususi kwa algebra ya Boolean na kwa hivyo katika sura hii yote tutashughulikia tu kazi tatu: ÿ, &, ⁄.
§2.1. Fomu za kawaida.
Miundo ya kawaida ni njia isiyo na utata ya kuandika fomula inayotekeleza kitendakazi fulani.
Ikiwa x ni kigezo cha kimantiki, na σœ(0,1) basi usemi x σ = x ikiwa σσ == 10 au x σ = 10 ikiwa x x =≠σσ , x inaitwa herufi. . Herufi x na Ÿx huitwa contraries. Kiunganishi tenganisha inayoitwa disjunction ya barua. Kwa mfano, fomula x ⋅ y ⋅ z na x ⋅ y ⋅ x ⋅ x ni viunganishi, fomula x ∨ y ∨ z na x ∨ y ∨ x ni viunganishi, na fomula z ni kiunganishi na kitenganishi.
Fomu ya kawaida ya kutenganisha (DNF) inaitwa mtengano wa idadi kamilifu ya viunganishi .
Fomu ya kawaida ya kiunganishi (CNF) inaitwa kiunganishi cha idadi bainifu ya vifungu .
Kwa urahisi zaidi: DNF ni jumla ya bidhaa, na CNF ni zao la hesabu za kimantiki.
1. xÿy¤yÿz¤x ni DNF (jumla ya bidhaa).
2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z ni CNF (bidhaa ya jumla).
3. x ∨ y ∨ z ∨ w ni DNF na CNF (kwa wakati mmoja).
4. x ⋅ y ⋅ z ⋅ w ni DNF na CNF (kwa wakati mmoja).
5. (x¤x¤y)·(y¤z¤x)·z ni CNF.
6. x⋅y⋅z na x⋅y⋅x⋅x ni DNF.
7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z si aina ya kawaida (si DNF au CNF).
Acha kazi f iandikwe katika msingi S1. Kitendaji hiki kimepunguzwa hadi fomu ya kawaida kama ifuatavyo:
1) tunatumia sheria za De Morgan kubadilisha fomula kwa fomu ambayo ishara mbaya zinahusiana tu na vigezo vya mtu binafsi;
2) tunatumia sheria ya kuondoa hasi mbili: ŸŸx=x;
H1&(H2¤H3)=(H1&H2)¤(H1&H3) , na sheria ya pili ya ugawaji ya kupunguzwa kwa CNF. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).
Chaguo lolote la kukokotoa la Boolean linaweza kuwa na idadi isiyo na kikomo ya uwakilishi wa DNF na CNF. Kwa mfano, kwa kutumia zaidi ya sheria za inversions na sheria za uendeshaji na constants, inawezekana kuhakikisha kwamba katika kila mtu kwa pamoja au disjunct kutofautiana yoyote inaonekana si zaidi ya mara moja (yenyewe au kukanusha yake).
Mfano 2.1.1. Ili kupunguza hadi DNF tunatumia sheria ya 1 ya usambazaji.
x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y ⋅z)⋅(y∨z)= ni CNF
= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = - hii ni CNF nyingine
X ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⅋z = y
X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ni DNF
Mfano 2.1.2. Ili kupunguza kwa CNF ni muhimu kutumia sheria ya pili ya usambazaji.
x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =
X∨y⋅z⋅(x∨y)=(x∨y⋅z)⋅(x∨x∨y)=(x∨y)⋅(x∨z)⋅(1∨y)=
= (x ∨ y) ⋅ (x ∨ z) ni CNF
§2.2. Fomu za kawaida kabisa.
Ikiwa katika kila neno la fomu ya kawaida vigezo vyote vinawakilishwa (yenyewe au kukanusha kwao), na katika kila muunganisho wa mtu binafsi au mtengano tofauti yoyote inaonekana mara moja (ama yenyewe au ukanushaji wake), basi fomu hii inaitwa. fomu kamili ya kawaida (SDNF au SCNF). Mifano: Acha kazi ya vigeu vitatu f(x,y,z) itolewe.
1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ni DNF kamili.
2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) ni CNF kamili.
3. (x ∨ y) ⋅ (x ∨ z) si CNF kamili, kwa sababu kwa mfano, jumla ya kwanza haijumuishi mabadiliko z.
4. xÿyÿz ni DNF kamili. Nadharia 2.2.1.
1. Chaguo lolote la kukokotoa la Boolean ambalo si sifuri sawa lina SDNF moja tu, hadi eneo la masharti.
2. Chaguo lolote la kukokotoa la Boolean ambalo halifanani na 1 lina SCNF moja tu, hadi eneo la sheria na masharti.
Tutathibitisha nadharia hiyo kwa njia nzuri, kama suluhisho la shida ifuatayo: Kwa kutumia jedwali hili la ukweli, tengeneza SDNF.
Wacha tuchunguze suluhisho kwa kutumia mfano wa kazi f(x,y,z) iliyotolewa kwenye jedwali (Jedwali 2.2) kwa n=3.
Mfano 2.2.1. Kwa kutumia jedwali hili la ukweli (Jedwali 2.2), tengeneza SDNF.
Jedwali 2.2
| x | y | z | msingi viunganishi |
f(x,y,z) |
| 0 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 0 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 1 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 1 | x ⋅ y ⋅ z | 1 |
Viunganishi vya msingi (au washiriki_1) iliyojumuishwa kwenye jedwali inalingana na seti maalum ya sufuri na zile ambazo viambishi x,y,z huchukua. Majimbo yanajengwa_ 1 kwa mujibu wa kanuni ifuatayo: kutofautiana kunajumuishwa katika bidhaa yenyewe ikiwa inachukua thamani 1 kwenye seti fulani, vinginevyo kukataa kwake kunajumuishwa katika bidhaa. Kwa hivyo, kwa mfano, kwenye seti (0,0,1) vigezo x,y huchukua thamani 0 na kwa hivyo kanusho zao zinajumuishwa kwenye bidhaa, na kutofautisha z huchukua thamani 1 na kwa hivyo imejumuishwa katika bidhaa yenyewe. . Kwa seti fulani (0,0,1), kipengele_1 ni sawa na x ⋅ y ⋅ z .
Ni wazi, kiunganishi x ⋅ y ⋅ z ni sawa na 1 pekee kwenye seti.
(0,0,0), na x ⋅ y ⋅ z ni 1 kwenye seti (0,0,1), nk. (tazama jedwali). Ifuatayo, kumbuka kuwa muunganisho wa viunganishi viwili vya msingi ni sawa na 1 kwenye seti mbili haswa zinazolingana na viunganishi hivi vya msingi. Kwa mfano, chaguo za kukokotoa x ⋅ y ⋅ z¤x ⋅ y ⋅ z ni sawa na 1 pekee kwenye seti mbili - (0,0,0) na (0,0,1), na kwenye seti nyingine zote ni sawa na 0. Vile vile, mtengano wa viunganishi vitatu vya msingi ni sawa na 1 kwenye seti tatu hasa zinazolingana na viunganishi hivi vya msingi, nk.
Hiyo. tunapata kanuni: kwa ajili ya kujenga SDNF unapaswa kuchagua safu ambazo kazi ni sawa na 1, na kisha kuchukua mgawanyiko wa viunganishi kuu vinavyolingana, tunapata SDNF inayotaka. Kwa hivyo kwa mfano wetu, tunayo x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Kazi. Kwa kutumia jedwali hili la ukweli, tengeneza SCNF.
Katiba_0 kwa seti ya sufuri na zile (ambazo huchukua vigeu x,y,z) imeundwa kama ifuatavyo: kutofautisha kunajumuishwa kwenye mgawanyiko yenyewe ikiwa inachukua thamani kwenye seti hii. 0 , vinginevyo kazi inajumuisha kukanusha kwake.
Sheria za kuunda SKNF: unapaswa kuchagua mistari ambayo kazi ni sawa na 0 , na kisha chukua kiunganishi cha viambajengo vinavyolingana_0. Matokeo yake yatakuwa SCNF inayotakiwa. Kwa hivyo kwa mfano wetu, tunayo f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Maoni. Ili kuunda kitendakazi kamili cha CNF f, inatosha kuunda DNF kamili kwa chaguo la kukokotoa f, na kisha
Wacha tuunde SCNF kwa mfano wetu kulingana na maoni. 1. Tunaunda SDNF kwa kukanusha.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Tunatumia sheria za de Morgan f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ y⋅ z == ) ⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .
Mbinu iliyofafanuliwa ya kupata SDNF (na SCNF) kwa kutumia jedwali la ukweli mara nyingi ni ya nguvu kazi zaidi kuliko algorithm ifuatayo.
1. Ili kupata SDNF Kwanza tunapunguza fomula hii kuwa DNF.
2. Ikiwa kiunganishi fulani K (yaani K ni bidhaa ya idadi fulani ya vigeu au ukanushaji wao) hakijumuishi, tuseme, kigezo y, basi tunabadilisha kiunganishi hiki na fomula sawa K&(y ∨ y) na, tukitumia. sheria ya usambazaji, tunawasilisha fomula inayotokana na DNF; ikiwa kuna vigezo kadhaa vinavyokosekana, basi kwa kila mmoja wao tunaongeza formula inayofanana ya fomu (y ∨ y) kwa kuunganishwa.
3. Ikiwa DNF inayotokana ina vipengele kadhaa vinavyofanana vya kitengo, basi tunaacha moja tu yao. Matokeo yake ni SDNF.
Maoni: Kuunda SCNF kuwa kifungu kisicho na, tuseme, kigezo katika tunaongeza fomula ya fomu y⋅ y, i.e. Tunabadilisha mtengano huu na fomula sawa D ∨ y⋅ y na, kwa kutumia sheria ya 2 ya usambazaji.
Mfano 2. 2. 2. Unda SDNF kwa chaguo za kukokotoa f kwa kutumia mageuzi sawa.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z ⋅ z x y ⋅ z ⋅ z ⋅ z ⋅ z ⋅ z ⋅ x y ⋅ z ⋅ x =
KURUDI.
Hesabu ya SDNF sio tu ya kinadharia, lakini pia ya umuhimu mkubwa wa vitendo. Kwa mfano, katika nyingi programu za kisasa na kiolesura cha kielelezo, ili kuunda hali ngumu za kimantiki, fomu ya kuona katika mfumo wa jedwali hutumiwa: hali zimeandikwa katika seli, na seli za safu moja huchukuliwa kuwa zimeunganishwa na kiunganishi, na nguzo zinachukuliwa kuwa zimeunganishwa. kwa kutengana, yaani, huunda DNF (au kinyume chake, katika kesi hii, CNF inapatikana). Hasa, hivi ndivyo kiolesura cha picha cha QBE (Query-byExample) kimeundwa, kinachotumiwa kuunda hali za kimantiki wakati wa kuuliza DBMS.
Algorithm 2.2.1. Ujenzi wa SDNF
Ingång: vekta X: safu ya kamba - vitambulishi vinavyobadilika, matrix V: safu ya 0..1 ya seti zote tofauti za maadili tofauti,
vekta F: safu ya 0..1 thamani zinazolingana za utendakazi.
Utgång: mlolongo wa alama zinazounda rekodi ya fomula ya SDNF kwa kipengele fulani cha kukokotoa.
f:= uongo(ishara ya uwepo wa operesheni ya kushoto ya mgawanyiko) kwa i kutoka 1kwa 2 n fanya
kama F[i] = 1 basi ikiwa f basi
mavuno"¤" (kuongeza ishara ya mtengano kwenye fomula; mwendeshaji mavuno m prints
ishara m) mwingine f:= kweli
mwisho kama g:= uongo(ishara ya uwepo wa operesheni ya kushoto ya kiunganishi) kwa j kutoka 1kwa n fanya kama g basi
mavuno"⁄" (kuongeza ishara ya kiunganishi kwenye fomula)
mwingine g: = kweli
mwisho kama V ( kuongeza kitambulisho tofauti kwenye fomula
§2.3. Kupunguza DNF kwa mbinu ya Quine.
Kila formula ina nambari ya mwisho matukio ya vigezo. Kutokea kwa kigezo hurejelea mahali ambapo kigezo kinachukua katika fomula. Kazi ni kupata, kwa kitendakazi fulani cha Boolean f, DNF ambayo inawakilisha chaguo hili la kukokotoa na ina idadi ndogo zaidi ya matukio ya vigeu.
Ikiwa x ni kigezo cha kimantiki, na σœ(0,1) basi usemi x σ =xx ikiwa σσ== 10 .
kuitwa barua . Kiunganishi inayoitwa muunganisho wa barua. Kwa mfano, fomula x ⋅ y ⋅ z na x ⋅ y ⋅ x ⋅ x ni viunganishi . Bidhaa ya msingi ni kiunganishi ambacho kigeuzo chochote hakionekani zaidi ya mara moja (yenyewe au kukanusha kwake).
Formula f1 inaitwa muhimu fomula f , ikiwa f1 ni bidhaa ya msingi na f 1 ⁄ f = f 1, i.e. yaani, kwa kazi zinazolingana na fomula, ukosefu wa usawa f 1 § f unashikilia. F1 muhimu ya fomula f inaitwa rahisi , ikiwa, baada ya kutupa herufi yoyote kutoka kwa f1, fomula haipatikani ambayo ni kiambatisho cha fomula f.
Mfano 2.3.1 . Hebu tutafute viambishi vyote na viambishi rahisi vya fomula f=xØy . Kuna jumla ya bidhaa 8 za msingi zilizo na anuwai X Na u. Ifuatayo, kwa uwazi, meza zao za ukweli zimepewa:
| x | y | xØy | x ⋅ y | x ⋅ y | x ⋅ y | x ⋅ y | x | y | x | y | |||||||
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |||||||
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |||||||
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |||||||
Kutoka kwa majedwali ya ukweli tunahitimisha kuwa fomula x ⋅ y , x ⋅ y , x ⋅ y , x ,y - viambajengo vyote vya fomula xØy, na kati ya viambajengo hivi fomula x na y ni rahisi (formula x ⋅ y, kwa mfano, si kidokezo rahisi, kwa kuwa, tukitupilia mbali herufi y, tunapata kiambatisho x).
DNF iliyofupishwa inaitwa mtengano wa viambajengo vyote vya msingi vya fomula (kazi) iliyotolewa .
Nadharia 2.3.1. Chaguo lolote la kukokotoa la Boolean ambalo si 0 thabiti linaweza kuwakilishwa kama DNF ya mkato.
Katika Mfano 2.3.1, fomula ya kukokotoa inayolingana na fomula xØy inawakilishwa na fomula x ∨ y ambayo ni DNF yake iliyofupishwa.
DNF iliyopunguzwa inaweza kuwa na viashiria vya ziada, ambavyo kuondolewa kwake habadilishi jedwali la ukweli. Ikiwa tutaondoa viashiria vyote visivyo vya lazima kutoka kwa DNF iliyopunguzwa, tunapata DNF inayoitwa mwisho wa kufa.
Kumbuka kuwa uwakilishi wa chaguo la kukokotoa kama DNF isiyoisha ni katika hali ya utata. Kuchagua kutoka kwa aina zote za mwisho-mwisho, fomu yenye idadi ndogo ya matukio ya vigeu inatoa Kiwango cha chini cha DNF (MDNF).
Fikiria mbinu Quina, kupata MDNF inayowakilisha kazi fulani ya Boolean. Tunafafanua shughuli tatu zifuatazo:
1. operesheni kamili ya kuunganisha : f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;
2. operesheni ya gluing ya sehemu:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3. uendeshaji wa ngozi ya msingi f ⋅ x σ ∨ f = f , σ ∈ (0,1) .
Nadharia 2.3.2(Nadharia ya Quinine). Ikiwa, kwa kuzingatia kazi ya SDNF, tunafanya shughuli zote zinazowezekana za gluing isiyo kamili na kisha ngozi ya msingi, basi matokeo yatakuwa DNF iliyopunguzwa, yaani, kutengana kwa vipengele vyote rahisi.
Mfano 2.3.2. Acha chaguo la kukokotoa f(x,y,z) itolewe na DNF f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Halafu, tukifanya katika hatua mbili shughuli zote zinazowezekana za gluing isiyo kamili, na kisha kunyonya kwa msingi, tunayo.
f 
Kwa hivyo, DNF iliyofupishwa ya fomula f ni fomula y¤x·z.
Katika mazoezi, wakati wa kufanya shughuli zisizo kamili za gluing katika kila hatua, inawezekana si kuandika maneno yanayohusika katika shughuli hizi, lakini kuandika tu matokeo ya gluings yote iwezekanavyo kamili na viunganisho ambavyo havihusiani na gluing yoyote.
Mfano 2. 3. 3. Acha fomula f(x,y,z) itolewe na DNF f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
Kisha, kufanya shughuli za gluing na kisha ngozi ya msingi, tunayo
f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨z x ⋅ z ∨z x
Ili kupata kiwango cha chini cha DNF kutoka kwa DNF iliyopunguzwa, matrix ya Quine inatumika , ambayo imeundwa kama ifuatavyo. Vichwa vya safu wima vya jedwali vina viambajengo vya kitengo kamili cha DNF, na vichwa vya safu mlalo vina viambishi rahisi kutoka kwa DNF iliyofupishwa. Katika jedwali, nyota huashiria makutano ya safu na nguzo ambazo kiunganishi kwenye kichwa cha safu kinajumuishwa katika sehemu ya kitengo, ambayo ni kichwa cha safu.
Kwa mfano 2.3.3. Matrix ya Quine ina fomu
Katika DNF iliyokufa, idadi ya chini ya viambajengo rahisi huchaguliwa, mgawanyiko ambao huhifadhi sehemu zote za kitengo, i.e., kila safu ya matrix ya Quine ina nyota kwenye makutano na safu inayolingana na moja ya safu. wahusika waliochaguliwa. DNF-mwisho ambayo ina idadi ndogo zaidi ya matukio ya vigeu inachaguliwa kama kiwango cha chini cha DNF.
Katika Mfano 2.3.3, kwa kutumia matrix ya Quine, tunapata kwamba kiwango cha chini cha DNF cha chaguo za kukokotoa ni x ⋅ y ¤ x ⋅ z.
Maoni.
tumia f =f na sheria za De Morgan.
§ 2.4. Ramani za Carnot.
Njia nyingine ya kupata fomula rahisi zilizo na idadi ndogo ya vigeu (na, kwa hivyo, kupata kiwango cha chini cha DNF) inategemea utumiaji wa kinachojulikana kama ramani za Carnot.
Ramani ya Carnot ni aina maalum jedwali ambalo hurahisisha mchakato wa kupata fomu ndogo na hutumiwa kwa mafanikio wakati idadi ya vigeu haizidi sita. Ramani za Karnaugh za vitendaji kulingana na vigeu vya n ni mstatili uliogawanywa katika seli 2 n. Kila seli ya mchoro inahusishwa na seti ya n-dimensional ya binary. Thamani za chaguo za kukokotoa f kutoka kwa jedwali la ukweli huingizwa kwenye miraba inayohitajika, lakini ikiwa seli inalingana na 0, basi kawaida hubaki tupu.
Katika jedwali 2.4.1. inaonyesha mfano wa kuweka alama kwenye ramani ya Karnaugh kwa kazi ambayo inategemea vigezo vitatu. Seli nne za chini za ramani zinalingana na seti za jozi ambamo kigezo x inachukua thamani 1, seli nne za juu zinahusiana na seti ambazo kutofautiana x inachukua thamani 0. Seli nne zinazounda nusu ya kulia ya ramani zinalingana na seti ambazo mabadiliko y; inachukua thamani 1, nk. Katika jedwali 2.4.2. Kuweka alama kwa ramani ya Karnaugh kwa vigeu vya n=4 kunaonyeshwa.
Ili kuunda DNF ndogo, tunafanya utaratibu wa gluing "1". Thamani "1" ambazo hushikamana zinalingana na seli za jirani, i.e. seli zinazotofautiana tu katika thamani ya kigezo kimoja (katika picha ya mchoro, ikitenganishwa na mstari wima au mlalo, kwa kuzingatia ukaribu wa seli zilizo kinyume).
Mchakato wa kuunganisha "1" unakuja kwa kuchanganya seli moja za ramani ya Karnaugh katika vikundi, na sheria zifuatazo lazima zifuatwe;
1. Idadi ya seli zilizojumuishwa katika kundi moja lazima zionyeshwe kuwa nyingi ya 2, i.e. mita 2 ambapo m=0,1,2,...
2. Kila seli iliyojumuishwa katika kundi la seli za m 2 lazima iwe na seli za m jirani kwenye kikundi.
3. Kila seli lazima iwe ya angalau kundi moja.
4. Kila kikundi kinapaswa kuwa na idadi kubwa ya seli, i.e. hakuna kikundi kinachopaswa kuwa ndani ya kikundi kingine.
5. Idadi ya vikundi inapaswa kuwa ndogo.
Kusoma kipengele f kulingana na kikundi cha gluing hufanyika kama ifuatavyo: vigezo vinavyohifadhi maadili sawa katika seli za kikundi cha gluing, huingia kwenye kiunganishi, na maadili 1 yanahusiana na vigezo wenyewe, na maadili 0 yanahusiana na makataa yao.
Tunawasilisha templates zinazosaidia kujenga vifuniko 1 (tunazingatia vigezo kuwa sawa, lakini hatutaziandika). Ili kurahisisha nukuu, hatutaweka alama kwenye viambajengo, ingawa tutahifadhi majina yao kama ilivyo kwenye jedwali 2.4.1, 2.4.2.
| 1 | 1 |
| 1 | 1 |
| F=Ÿy&x | |
| 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 |
| 1 | 1 | 1 |
| 1 |
F=Ÿz&Ÿy f=Ÿx&y
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
F=Ÿx&z f=y&w F=Ÿx&Ÿy
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||
| 1 | 1 |
F=Ÿy&Ÿw f=Ÿy&Ÿz F=Ÿz&Ÿx
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | ||||
| 1 | 1 | 1 | 1 |
F=y&z&w f=Ÿy&Ÿz&Ÿw F=x&y&Ÿz
| 1 | ||
| 1 | ||
| 1 | 1 | 1 |
| 1 |
Mfano 2.4.1. Kujenga MDNF.
Kwanza tunaangalia kuona kama kuna mipako_ 1 kati ya seli 16 zinazofunika angalau moja isiyofunikwa 1. Hakuna vifuniko kama hivyo. Tunasonga kwenye vifuniko vya seli 8. Hebu tuone kama kuna vifuniko vya seli 1 kati ya 8 vinavyofunika angalau moja ambayo haijafunikwa 1. Hakuna vifuniko kama hivyo. Tunasonga kwenye vifuniko vya seli 4. Hebu tuone kama kuna vifuniko vya seli 1 kati ya 4 vinavyofunika angalau moja ambayo haijafunikwa 1. Kuna vifuniko viwili kama hivyo. Tunahamia kwenye vifuniko vya seli 2. Kuna mipako moja tu kama hiyo. Kwa hivyo, zote 1 zilifunikwa. Ifuatayo, hebu tuone ikiwa tunaweza kuondoa baadhi ya vifuniko ili vitengo vyote vibaki vimefunikwa. Mwishoni tunaandika MDNF: f =x⋅z∨y⋅w∨y⋅z⋅w.
Maoni. Ili kuunda CNF ndogo ya kazi f, inatosha kuunda DNF ndogo kwa kazi f, na kisha.
tumia f =f na sheria za De Morgan.
Sura ya III. algebra ya Zhegalkin.
Seti ya vitendaji vya Boolean iliyofafanuliwa katika msingi wa Zhegalkin S4=(∆,&,1) inaitwa aljebra ya Zhegalkin.
Mali ya msingi.
1. mawasiliano
H1∆H2=H2∆H1, H1&H2=H2
2. ushirika
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)
3. usambazaji
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. sifa za viasili H&1=H, H&0=0, H∆0=H;
5. H∆H=0, H&H=H.
Taarifa 3.1.1. Kazi zingine zote za Boolean zinaweza kuonyeshwa kupitia shughuli za algebra ya Zhegalkin:
Ÿx=1∆x, x¤y=x∆y∆xy, x~y=1∆x∆y, xØy=1∆x∆xy, x∞y=1∆x∆y∆xy, x|y= 1∆xy.
Ufafanuzi. Zhegalkin polynomial (modulo 2) ya vigeu vya n x 1 ,x 2 ,…,x n ni usemi wa umbo c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2… inaweza kuchukua maadili 0 au 1.
Ikiwa Zhegalkin polynomial haina bidhaa za vigezo vya mtu binafsi, basi inaitwa linear (kazi ya mstari).
Kwa mfano, f=x∆yz∆xyz na f1=1∆x∆y∆z ni polynomia, ya pili ikiwa ni kazi ya mstari.
Nadharia 3.1.1. Kila kazi ya Boolean inawakilishwa kwa namna ya polynomial ya Zhegalkin kwa njia ya kipekee.
Wacha tuonyeshe njia kuu za kuunda polynomials za Zhegalkin kutoka kwa kazi fulani.
1. Mbinu isiyo na uhakika ya mgawo . Acha P(x 1 ,x 2 ,…,x n) iwe Zhegalkin polynomial inayotaka inayotekeleza chaguo za kukokotoa f(x 1 ,x 2 ,…,xn). Hebu tuandike kwa fomu
P= c 0 ∆c 1 x 1 ∆c 2 x 2 ∆…∆c n x n ∆c 12 x 1 x 2 ∆…∆c12… n x 1 x 2 …x n .
Wacha tutafute coefficients kwa k. Ili kufanya hivyo, tunagawa kwa mpangilio vigezo x 1 , x 2 ,…, x n maadili kutoka kwa kila safu ya jedwali la ukweli. Matokeo yake, tunapata mfumo wa 2 n equations na 2 n haijulikani, ambayo ina ufumbuzi wa pekee. Baada ya kusuluhisha, tunapata coefficients ya polynomial P(x 1 ,x 2 ,…,xn).
2. Njia ya msingi ya kubadilisha fomula juu ya seti ya viunganishi ( ÿ,&}. Tengeneza fomula fulani Ф juu ya seti ya viunganishi (Ÿ,&), kwa kutambua chaguo la kukokotoa f(x 1 ,x 2 ,…,x n). Kisha badilisha fomula ndogo za fomu A kila mahali na A∆1, fungua mabano kwa kutumia sheria ya ugawaji (angalia kipengele 3), kisha utumie sifa 4 na 5.
Mfano 3.1.1. Unda polynomial ya Zhegalkin kwa chaguo za kukokotoa f(x,y)=xØy.
Suluhisho. 1 . (njia ya coefficients isiyojulikana). Hebu tuandike polynomial inayohitajika katika fomu
P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Kutumia jedwali la ukweli
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| xØy | 1 | 1 | 0 | 1 |
tunapata kwamba f(0,0)=P(0,0)= c 0 =1, f(0,1)=P(0,1)= c 0 ∆ c 2 =1, f(1,0) =P(1,0)= c 0 ∆c 1 =0, f(1,1)=P(1,1)= c 0 ∆c 1 ∆c 2 ∆c 12 =1
Kutoka ambapo tunapata mara kwa mara, c 0 =1, c 1 =1, c 2 =0, c 12 =1. Kwa hivyo xØy=1∆x∆xy (linganisha na taarifa 3.1).
2.(Mbinu ya ubadilishaji wa fomula.) Tuna
x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
Kumbuka kwamba faida ya Zhegalkin algebra (ikilinganishwa na algebra nyingine) ni hesabu ya mantiki, ambayo inafanya uwezekano wa kufanya mabadiliko ya kazi za Boolean kwa urahisi kabisa. Ubaya wake ikilinganishwa na aljebra ya Boolean ni ugumu wa fomula.
Sura ya IV. Taarifa. Vibashiri.
§4.1. Taarifa.
Wakati wa kuunda algebra ya mantiki, tulitumia mbinu ya kazi. Walakini, ingewezekana kuunda aljebra hii kwa njia ya kujenga. Kwanza, fafanua vitu vya utafiti (kauli), anzisha shughuli kwenye vitu hivi na usome mali zao. Wacha tutoe ufafanuzi rasmi.
Kwa kusema Wacha tuite sentensi ya kutangaza ambayo mtu anaweza kusema bila utata ikiwa ni kweli (thamani ya I au 1) au si kweli (thamani L au 0) kwa wakati maalum. Kwa mfano, "5 ni nambari kuu", "Ufunguo wa Esc umebonyezwa", nk. Kutumia viunganishi "si", "na", "au", "ikiwa,... basi", "ikiwa na tu ikiwa" (zinalingana na operesheni "Ÿ", "&", "¤", "Ø" , “~” » ipasavyo), kauli ngumu zaidi (sentensi) zinaweza kutengenezwa. Hivi ndivyo aljebra ya pendekezo inavyoundwa.
Ili kurahisisha kurekodi taarifa changamano, utangulizi wa viunganishi huletwa: "Ÿ", "&", "¤", "Ø", "~", ambayo husaidia kuacha mabano yasiyo ya lazima.
Tunaziita kauli rahisi vigezo vya pendekezo.
Hebu tuanzishe dhana ya fomula.
1. Vigezo vya pendekezo ni fomula.
2. Ikiwa A, B ni fomula, basi semi ŸA, A⁄B, A¤B, AØB, A~B ni fomula.
3. Fomula ni semi tu zilizoundwa kwa mujibu wa aya ya 1 na 2.
Fomula inayochukua thamani NA kwa thamani zote za viambishi vya pendekezo inaitwa tautology (au kwa ujumla halali), na fomula inayochukua thamani A kwa thamani zote za viambishi vya pendekezo inaitwa kupingana (au haiwezekani)
Maelezo ya sifa za aljebra ya pendekezo ni sawa na maelezo ya kazi zinazolingana katika aljebra ya Boolean, na tunaziacha.
§4.2. Vibashiri. Uendeshaji wa kimantiki kwenye vihusishi.
Somo la utafiti katika sura hii litakuwa vihusishi - michoro ya seti za kiholela katika seti ya taarifa. Kwa kweli, tunafanya mpito kwa kiwango kipya cha uondoaji, mpito wa aina sawa na ulifanywa shuleni - kutoka kwa hesabu ya nambari halisi hadi algebra ya kazi za nambari.
Ufafanuzi 2.1 Acha x 1 ,x 2 ,…,xn ziwe ishara za viambajengo vya asili ya kiholela. Vigezo hivi tutaviita vigeu vya somo. Acha seti za vigeu (x 1 ,x 2 ,…,x n) ziwe za seti M=(M1,M2,…Mn), ambayo tutaiita eneo la mada (yaani x i œM i, ambapo Mi huitwa kikoa. ya ufafanuzi wa kutofautiana xi). Kivumishi cha eneo n (kiasi cha mahali-n), kinachofafanuliwa kwenye eneo la somo M, ni chaguo la kukokotoa kimantiki ambalo huchukua thamani NA au thamani L.
Mfano 4.2.1. D(x1,x2) = "Nambari asilia x1 imegawanywa (bila salio) na nambari asilia x2." - kihusishi cha mahali-mbili kinafafanuliwa kwenye seti ya jozi nambari za asili M=NäN. Ni wazi, D(4,2) = Na, D(3,5) = 0.
Mfano 4.2.2. Q(x) ==“x 2<-1, хœR» - одноместный предикат, определенный на множестве nambari za kweli M=R. Ni wazi kwamba Q(1) = А, Q(5) = А, na kwa ujumla kiima Q(x) ni sawa na uongo, i.e.
Q(x) = А kwa xœR zote.
Mfano 4.2.3. B(x,y,z) = “x 2 +y 2 Kiambishi P kinachofafanuliwa kwenye M kinaitwa ukweli sawa ikiwa inachukua thamani NA kwa maadili yoyote ya vigezo vya mada; Kiambishi P kinaitwa uwongo sawa ikiwa kitachukua thamani A kwa thamani zozote za vigeu vya mada. Predicate Q kutoka kwa Mfano 4.2.2. ni sawa na uongo. Kwa kuwa vihusishi ni vitendaji vilivyo na maadili katika seti ya taarifa ambapo utendakazi wa kimantiki huletwa, shughuli hizi kwa kawaida hufafanuliwa kwa vihusishi. Acha P na Q zifafanuliwe kwenye M. Kisha 1. ¬P(x, x,…, x n) = P(x, x,…, x) ∧ 1 2 n 1 2 n ∧ 1 2 n 3. (P ∨ Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,…,x n) ∨ Q(x 1 ,x 2 ,…,x n) 4. (P → Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,…,x n) → Q(x 1 ,x 2 ,…,x n) Vibashiri P na Q, vinavyofafanuliwa kwenye M huitwa sawa (andika P=Q) ikiwa P(x 1 ,x 2 ,…,xn)=Q(x 1 ,x 2 ,…,xn) kwa seti yoyote (x 1 ,x 2 ,…, x n )
Vigezo vya mada kutoka kwa M .
Nadharia 4.2.1 Seti ya vihusishi vya n-ary vilivyofafanuliwa kwenye M huunda aljebra ya Kiboole. Kwa hivyo, usawa wa kimsingi ni halali kwao (tazama §1.6). Acha P(x 1 ,x 2 ,…,xn) iwe kiima cha n-ary kinachofafanuliwa kwenye M. Hebu turekebishe x i = a. Hebu tufafanue kihusishi (n-1)-ary Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) kama ifuatavyo: Q(x 1 ,x 2 ,…,xk-1,xk) +1, xn)=P(x 1 ,x 2 ,…,xk1, a,xk+1,xn). Wanasema kwamba kiima Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) hupatikana kutoka kwa kiima P(x 1 ,x 2 ,…,xn) kwa kuweka thamani ya i- th tofauti: x i = a
. Ufafanuzi
4.3.1
. Acha P(x) iwe kihusishi kisicho cha kawaida. Hebu tuhusishe nayo kauli inayoashiria “xP(x) (soma “kwa x P(x) yoyote”), ambayo ni kweli ikiwa tu ikiwa P(x) ni kiima sawa sawa. Taarifa “xP(x) inasemekana kuwa , kwamba hupatikana kutoka kwa kihusishi P kwa kuambatanisha kibainishi cha jumla juu ya mabadiliko x. Ufafanuzi 4.3.2. Acha P(x) iwe kihusishi kisicho cha kawaida. Hebu tuihusishe na taarifa inayoashiria $xP(x) (soma "kuna x P(x)"), ambayo si kweli ikiwa tu P(x) ni kivumishi cha uwongo sawa. Taarifa $xP(x) inasemekana kupatikana kutoka kwa kihusishi P kwa kuambatanisha kibainishi kinachokuwepo kwenye kigezo x. Kumbuka 1. Alama " na $ kwa quantifiers ni herufi za Kilatini A na E, mtawaliwa, ambazo ni herufi za kwanza kwa maneno ya Kiingereza. Wote- Wote, Zipo- kuwepo. Kumbuka 2. Kauli zinaweza kuchukuliwa kuwa vihusishi ambavyo havina viambishi, yaani, vihusishi vya mahali 0 (au vihusishi vya eneo lolote). Acha P(x 1 ,x 2 ,…,xn) iwe kiima cha n-ary kinachofafanuliwa kwenye M. Wacha turekebishe ndani yake maadili ya viambishi x 1 ,x 2 ,…,x k-1 ,x k +1 ,x n . Tunaambatisha kitambulisho cha jumla (uwepo) kwa kihusishi kisicho cha kawaida Q(x k) na kupata taarifa. Kwa hivyo, seti maalum ya maadili ya vigezo x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n inahusishwa na taarifa inayotumia kibainishi cha ulimwengu (uwepo). Kiambishi hiki (n-1)-ary cha viambajengo x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n kinasemekana kupatikana kutoka kwa kiima asili P(x 1 ,x 2 ,…, x n) kwa kuongeza quantifier universality (kuwepo) katika variable kth. Kiima hiki kinaashiria: “x hadi P(x 1 ,x 2 ,…,x n) ($x hadi P(x 1 ,x 2 ,…,x n)). Kuhusu kigezo cha k-th (ambacho hakipo tena) wanasema kwamba inafungwa na kikadiriaji cha universality (uwepo). Mfano 4.3.1. Acha D(x1,x2) = "Nambari asilia x1 inaweza kugawanywa (bila salio) kwa nambari asilia x2." - kihusishi cha nafasi mbili. Wacha tuwagawie vibainishi mfululizo kwa vigeu vyake. Ni wazi kwamba 1) "x1"x2D(x1,x2)=0 2) "x2"x1D(x1,x2)=0 3) $x1$x2D(x1,x2)=1 4) $x2$x1D(x1,x2)=1 5) "x1$x2D(x1,x2)=1 6) $x2"x1D(x1,x2)=1 7) $x1"x2D(x1,x2) =0 8) "x1$x2D(x1,x2)=1. Kwa hivyo (kwa kulinganisha 7 na 8 katika mfano wa mwisho) tulithibitisha nadharia: Kwa kawaida, viunganishi na vibainishi hupangwa kwa kipaumbele kama ifuatavyo: Ÿ, ", $, &, ¤, Ø, ~. Nadharia 4.3.1. Vipimo vilivyo kinyume, kwa ujumla, usisafiri. Nadharia 4.3.2.(sawa za kimsingi zilizo na vidhibiti) Usawa ufuatao hufanyika: 1. Sheria za De Morgan ∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x) 2. Ushirikiano ∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y) 3. Usambazaji ∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x) 4. Mapungufu juu ya hatua ya quantifiers ∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y) 5. Kwa kihusishi chochote cha sehemu mbili ∃y∀xP(x,y) →∀x∃yP(x,y) =1 Nadharia rasmi(au hesabu)
Y-Hii: 1. kuweka A
wahusika kutengeneza alfabeti
;
1.
kundi la F
maneno katika alfabeti A, F
à A
ambazo zinaitwa fomula
;
3. kikundi kidogo B
fomula, B
à F
,
ambazo zinaitwa axioms; 4. mahusiano mengi R
kwenye seti ya fomula zinazoitwa kanuni za ufahamu. Alama nyingi A
inaweza kuwa na mwisho au isiyo na mwisho. Kawaida, kuunda alama, seti ndogo ya herufi hutumiwa, ambayo, ikiwa ni lazima, nambari za asili hupewa kama fahirisi. Fomula nyingi F
kwa kawaida hutolewa kwa ufafanuzi wa kufata neno, kwa mfano kwa njia ya sarufi rasmi. Kama sheria, seti hii haina mwisho. Seti A
Na F
kuamua kwa pamoja lugha
,
au Sahihi
,
nadharia rasmi. Axioms nyingi B
inaweza kuwa na mwisho au isiyo na mwisho. Ikiwa seti ya axioms haina ukomo, basi, kama sheria, imeainishwa kwa kutumia seti ya mwisho ya mipango ya axiom na sheria za kuzalisha axioms maalum kutoka kwa mpango wa axiom. Sheria nyingi za utambuzi R
, kama sheria, bila shaka. Kwa hivyo, hesabu Y kuna nne (A, F, B, R)
. Kwa kutolewa kwa calculus Y ni mfuatano wa fomula F 1 ,F 2 ,…,Fn kiasi kwamba kwa k yoyote (1§k§n) fomula Fk ama ni axiom ya calculus Y au tokeo la moja kwa moja la fomula zozote za awali zilizopatikana kwa kanuni ya makisio. . Fomula G inaitwa nadharia ya calculus Y (inayotokana na Y au inayoweza kuthibitishwa katika Y) ikiwa kuna hitimisho F 1 ,F 2 ,…,F n ,G inayoitwa kutokezwa kwa fomula G au uthibitisho wa nadharia G. Hii imeandikwa kama ifuatavyo: F 1,F 2,…,F n + G. Calculus Y kuitwa thabiti, ikiwa sio fomula zake zote zinaweza kuthibitishwa. Ufafanuzi mwingine wa uthabiti unaweza kutolewa: Kalkulasi inaitwa thabiti ikiwa fomula F na ŸF (ukanuzi wa F) hazipunguki ndani yake kwa wakati mmoja. Calculus Y kuitwa kamili(au inatosha) ikiwa kila kauli ya kweli M inalingana na nadharia ya nadharia Y
. Nadharia rasmi Y kuitwa kuamuliwa, ikiwa kuna algorithm ambayo, kwa fomula yoyote ya nadharia, huamua ikiwa fomula hii ni nadharia ya nadharia. Y au siyo. Kwa kutumia dhana ya calculus rasmi, tunafafanua calculus propositional (PS). Alfabeti IW inajumuisha 1. barua A, B, Q, R, P na wengine, ikiwezekana na faharasa (ambazo huitwa vigezo vya pendekezo), 2. alama za kimantiki(mishipa) Ÿ, &, ¤, Ø, 3. msaidizi wahusika
(,). Fomula nyingi IV imedhamiriwa kwa kufata: 1. vigezo vyote vya pendekezo ni fomula za IV; 2. ikiwa A, B ni fomula IV ,
toŸA, A⁄B, A¤B, AØB - fomulaIV ;
3. usemi ni fomula ya IV ikiwa na tu ikiwa hii inaweza kuanzishwa kwa kutumia alama "1" na Kwa hivyo, fomula yoyote ya IV inaundwa kutokana na viambajengo vya pendekezo kwa kutumia viunganishi Ÿ, ⁄, ¤, Ø. Katika siku zijazo, tunapoandika fomula, tutaacha baadhi ya mabano, kwa kutumia kanuni sawa na katika sura iliyotangulia. Axioms IV ni fomula zifuatazo (kwa fomula zozote A,B,C) 2. (AØB)Ø((AØ(BØC))Ø(AØC)); 5. (AØB)Ø((AØC)Ø(AØ(B⁄C))); 8. (AØC)Ø((BØC)Ø((A¤B)ØC)); 9. (AØB)Ø((AØŸB)ØŸA); Fomula zilizoonyeshwa zinaitwa IV axiom schemes .
Wakati wa kubadilisha fomula maalum katika mpango wowote, kesi maalum ya mpango wa axiom hupatikana. Kanuni ya ufahamu katika IE kuna sheria ya hitimisho (modus ponens): ikiwa A na AØB ni fomula zinazoweza kutolewa, basi B pia inaweza kutolewa. Kiishara imeandikwa hivi: A, A B →
B
. Kwa mfano, ikiwa kauli A⁄B na A⁄BØ(AØC) zinaweza kukatwa, basi kauli AØC pia inaweza kutolewa kulingana na kanuni ya makisio. Fomula G inasemekana inaweza kukatwa kutoka kwa fomula F 1 ,F 2 ,…,F n (iliyoashiria F 1 ,F 2 ,…,F n +G) ikiwa kuna mfuatano wa fomula F 1 ,F 2 ,… ,F k ,G , ambamo fomula yoyote ni aksiom, au ni ya orodha ya fomula F 1,F 2,...,F n (inayoitwa hypotheses), au inapatikana kutoka kwa fomula zilizopita kulingana na kanuni ya makisio. Utokezi wa fomula G kutoka “ (inayoonyeshwa na +G) ni sawa na ukweli kwamba G ni nadharia ya IV. Mfano 5.2.1. Hebu tuonyeshe kwamba fomula AØA inapatikana katika IV. Ili kufanya hivyo, tutaunda muundo wa fomula hii: 1) katika axiom 2, badilisha B na AØA, C na A. Tunapata axiom (AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA)); 2) katika axiom 1 tunabadilisha B na A. Tunapata AØ(AØA); 3) kutoka 1 na 2 kulingana na modus ponens tunahitimisha (AØ((AØA)ØA))Ø(AØA); 4) katika axiom 1 tunabadilisha B na AØA. Tunapata AØ((AØA)ØA); 5) kutoka kwa aya. 3 na 4, kulingana na kanuni ya kukisia, + AØA ni kweli. Nadharia 5.2.1. 1. Ikiwa F 1 ,F 2 ,…,Fn,A,B ni fomula za IV, Г=(F 1 ,F 2 ,…,Fn), Г+A, kisha Г,B+A. (unaweza kuongeza idadi ya hypotheses). 2. Iwapo tu ikiwa F 1 ,F 2 ,…,F n +A, wakati F 1 ⁄F 2 ⁄…⁄F n +A (kupunguzwa kwa dhana nyingi hadi dhana moja). Nadharia 5.3.1. (nadharia ya kupunguzwa) Ikiwa Г,B+A, basi Г+BØA, ambapo Г ni seti ya baadhi ya fomula Г=(F 1 ,F 2 ,…,F n ). Muhimu 5.3.1. Kisha na ikiwa F 1 ,F 2 ,…,F n +A, lini Ushahidi. Acha F 1 ,F 2 ,…,F n +A. Kisha, kwa kutumia nadharia ya kukatwa, tuna F 1 ,F 2 ,…,F n-1 +F n ØA. Vile vile F 1 ,F 2 ,…,F n-2 +F n 1Ø(F n ØA), n.k. Kuendeleza mchakato idadi inayohitajika ya nyakati, tunapata F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…) Ili kuthibitisha utoshelevu, chukulia kwamba +B, ambapo B=F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Wacha tutumie Theorem 5.2.1., kipengee cha 1: F 1 +B .
Kulingana na kanuni ya hitimisho, tunapata F 1 + (F 2 Ø…Ø(F n-1 Ø(F n ØA))…), Kisha baada ya n hatua tuna F 1 ,F 2 ,…,F n +A . Kwa hivyo, kutokana na Mfuatano wa 5.3.1., kuangalia kupunguzwa kwa fomula A kutoka kwa fomula F 1,F 2,…,F n, kunapunguzwa ili kuangalia uwezekano wa fomula. F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Kumbuka kwamba fomula A inaitwa sawa sawa (au tautology) ikiwa thamani ya fomula A ni sawa na moja kwa seti yoyote ya maadili ya viambishi vya pendekezo. Nadharia ifuatayo inapunguza uthibitishaji wa uwezekano wa fomula kwa uthibitishaji wa ukweli wake sawa. Nadharia 5.3.2. (kuhusu ukamilifu). Mfumo A unaweza kuthibitishwa ikiwa tu A ni kweli sawa (tautology): +A ‹A-tautology. Kwa hivyo, ili kuamua ikiwa fomula inaweza kuthibitishwa, inatosha kuunda jedwali lake la ukweli. Kama inavyojulikana, kuna algorithm inayofaa ya kuunda jedwali la ukweli, na, kwa hivyo, IV inayoweza kutengenezea. Mfano 5.3.1. Hebu tuthibitishe kuwa P+P. Kwa nadharia ya kukatwa, hii ni sawa na +(PØP). Kwa upande wake, kwa mujibu wa nadharia ya ukamilifu, inatosha kuthibitisha kwamba (РØР) ni tautology. Kukusanya jedwali la ukweli la fomula (РØР) ,
Tuna hakika kwamba (РØР) ni kweli sawa na, kwa hivyo, inaweza kuthibitishwa. Nadharia 5.3.3. (kuhusu uthabiti). Hesabu ya IW ni thabiti. Ushahidi. Kulingana na nadharia ya ukamilifu, fomula yoyote ambayo si kweli sawa haiwezi kuthibitishwa katika IW. Kwa mfano, fomula kama hiyo ni fomula A⁄(ŸA). Seti ya fomula Г inaitwa utata
,
ikiwa Г+А⁄(ŸА) .
Ikiwa Г ni seti kinzani ya fomula, tutaashiria ukweli huu kwa Г+. Kauli
5.3.1.
Fomula A inaweza kukatwa kutoka kwa seti ya fomula Г ikiwa na ikiwa tu seti Г»(ŸA) inakinzana. Uthibitishaji wa nadharia ya kiotomatiki ndio msingi wa upangaji programu wa mantiki, akili bandia na mitindo mingine ya kisasa katika upangaji programu. Kwa ujumla, kunaweza kusiwe na algorithm ambayo, kwa kuzingatia fomula ya kiholela, mtu anaweza kuamua, baada ya idadi maalum ya hatua, ikiwa A inaweza kupunguzwa katika calculus Y au la. Hata hivyo, kwa baadhi ya nadharia rahisi rasmi (kwa mfano, calculus propositional) na baadhi ya madarasa rahisi ya fomula (kwa mfano, calculus prediketo inayotumika yenye kiima kimoja), algoriti za uthibitishaji wa nadharia otomatiki zinajulikana. Chini, kwa kutumia mfano wa calculus propositional, sisi muhtasari wa misingi ya njia ya azimio - classic na wakati huo huo maarufu mbinu ya moja kwa moja kuthibitisha theorems. Kumbuka kwamba ikiwa x ni kigezo cha kimantiki, na σœ(0,1) basi usemi x σ = xx ikiwa σσ == 10 au x σ = 10 ikiwa x x =≠σσ , inaitwa barua. Herufi x na Ÿx zinaitwa kinyume.
Kiunganishi inayoitwa muunganisho wa barua. tenganisha inayoitwa disjunction ya barua. Acha D 1 = B 1 ∨ A, D 2 = B 2 ∨ A viwe vifungu. Kifungu B 1 ¤B 2 kinaitwa suluhisho vifungu D 1 na D 2 kwa herufi A na inaonyeshwa na res A (D 1 ,D 2). Azimio la vifungu D 1 na D 2 ni kiazimio kwa baadhi ya herufi na huonyeshwa kwa res(D 1 ,D 2). Ni wazi res(A,ŸA)=0. Kweli, kwa sababu A=A¤0 na ŸA=ŸA¤0, kisha res(A,ŸA)=0¤0=0. Ikiwa vifungu D 1 na D 2 havina vibambo tofauti, basi havina visuluhishi. Mfano 5.5.1. Kama D 1 =A¤B¤C, D 2 = A ∨ B ∨ Q, kisha res A (D 1 ,D 2)=B¤C¤ B ¤Q, res B (D 1 ,D 2)=A¤C¤A¤Q, resC(D 1 ,D 2) haipo. Taarifa 5.5.1. Ikiwa res(D 1 ,D 2) ipo, basi D 1 ,D 2 + res(D 1 ,D 2). Acha S=(D 1 ,D 2 ,…,Dn) iwe seti ya vifungu. Mfuatano wa fomula F 1 ,F 2 ,…,F n inaitwa utohozi thabiti kutoka S ikiwa kwa kila fomula F k mojawapo ya masharti yametimizwa: 2. kuna j, k
Nadharia 5.5.1.
(kuhusu ukamilifu wa njia ya azimio). Seti ya vifungu S inakinzana ikiwa na tu ikiwa kuna hitimisho suluhu kutoka kwa S ambalo linaisha kwa 0. Kumbuka kuwa mbinu ya utatuzi inaweza kutumika kuangalia upunguzo wa fomula F kutoka kwa seti fulani ya fomula F 1,F 2,…,F n. Hakika, hali F 1 ,F 2 ,…,F n +F ni sawa na hali F 1 ,F 2 ,…,F n ,ŸF+ (formula nyingi zinakinzana), ambayo nayo ni sawa na hali Q+, ambapo Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Hebu tupunguze fomula Q hadi CNF: Q=D 1 ⁄D 2 ⁄...⁄Dm, kisha Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Kwa hivyo, kazi ya kukagua upunguzo wa F 1 ,F 2 ,…,F n +F inakuja kwa kuangalia kutokubaliana kwa seti ya vifungu S=(D 1 ,D 2 ,...,D m ), ambayo ni sawa na kuwepo kwa hitimisho thabiti 0 kutoka kwa S. Mfano 5.5.2. Angalia uwiano AØ(BØC), CDØE, ŸFØD&(Ÿ)E + AØ(BØF) kwa kutumia mbinu ya utatuzi. Kwa mujibu wa taarifa 5.3.1. haja ya kuangalia kwa kutokwenda formula nyingi S = (AØ(BØC), CDØE, ŸFØD&(Ÿ)E, Ÿ(AØ(BØF))). Tunawasilisha fomula zote kutoka. S kwa KNF ni: S = (A ∨ B ∨ C,C ⋅ D ∨ E, F ∨ D ⋅ E, A ∨ B ∨ F) == (A ∨ B ∨ C, C ∨ D ∨ E, (F ∨ D) ⋅ (F ∨ E), A ⋅ B ⋅ F) . Kwa hivyo, tunapata seti ya vifungu S = (A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F) Wacha tuunda hitimisho dhabiti kutoka kwa S kumalizia na 0: 1. res A (A ∨ B ∨ C,A) = B ∨ C ; 2. res B (B ∨ C,B) = C; 3. res D (C ∨ D ∨ E,F ∨ D) = C ∨ E ∨ F ; 4. res E (C ∨ E ∨ F,F ∨ E) = C ∨ F; 5. res C (C, C ∨ F) = F; 6. res(F, F) = 0 . Kwa hivyo, tunahitimisha kuwa fomula AØ(BØF) inaweza kukatwa kutoka kwa seti ya fomula AØ(BØC), CDØE, ŸFØD&(Ÿ)E. Kumbuka kuwa njia ya azimio inatosha kugundua kutosheka iwezekanavyo kwa seti fulani ya vifungu S. Ili kufanya hivyo, hebu tujumuishe katika seti S vifungu vyote vilivyopatikana kwa kupunguzwa kwa usuluhishi kutoka kwa S. Kutoka kwa nadharia juu ya ukamilifu wa njia ya azimio. inafuata Muhimu 5.5.1. Iwapo seti ya vifungu S ina viasili vya vipengele vyake vyote, basi S inaweza kuridhika ikiwa tu 0-S. Kipengele cha tabia ya kisasa ni matumizi makubwa ya kompyuta katika kutatua matatizo (kazi) katika nyanja mbalimbali za shughuli za binadamu. Hata hivyo, tatizo lazima kwanza kutatuliwa algorithmically, i.e. agizo rasmi lazima litolewe, kufuatia ambayo mtu anaweza kupata matokeo ya mwisho ya kutatua shida zote za aina fulani (hii ni dhana ya angavu, sio kali ya algorithm). Kwa mfano, algorithm ya kupata kigawanyaji kikubwa zaidi cha nambari mbili asilia a, b, kama ifuatavyo: 1) kupanua idadi a kwa sababu kuu; 2) kurudia hatua ya 1 kwa b
Na nenda kwa hatua ya 3; 3) kutunga bidhaa ya mambo ya kawaida ya msingi kutoka kwa upanuzi A Na b na fahirisi zinazolingana na fahirisi ndogo kabisa za kujumuishwa katika upanuzi. Baada ya kuchambua mfano huu, tunaona sifa muhimu zaidi (sifa) za algorithm: 1.
Tabia ya wingi- utumiaji wa algorithm sio kwa shida moja, lakini kwa darasa la shida. 2.
Uadilifu- mgawanyiko wazi katika hatua za mtu binafsi (hatua) za algorithm. 3.
Uamuzi- shirika kama hilo la hatua za utekelezaji ambalo huwa wazi kila wakati jinsi ya kufanya mabadiliko kutoka hatua moja hadi nyingine. 4.
Kiungo- kupata matokeo wakati wa kutumia algorithm kutatua shida fulani, mlolongo mzuri wa hatua za algorithm hufanywa: Kumbuka kwamba ikiwa uwepo wa algorithm yenyewe hutumika kama uthibitisho wa kuwepo kwa algorithm, basi kuthibitisha kutokuwepo kwake ni muhimu kuwa na ufafanuzi mkali wa hisabati wa algorithm. Majaribio ya kurasimisha dhana ya algoriti ilisababisha kuundwa Mashine ya kusaga, kama kifaa fulani cha kufikiria kinachotekelezea algorithm. Hatua nyingine katika kufafanua dhana ya algorithm ilikuwa kuonekana kazi za kujirudia ,
kama kazi zinazorasimisha dhana ya algoriti na kutekeleza dhana angavu ya utangamano. Hivi karibuni iligunduliwa kuwa seti ya kazi za kujirudia ziliambatana na seti ya vitendaji vinavyoweza kuunganishwa kwenye mashine za Turing. Dhana mpya ambazo zilionekana, zikidai kuelezea dhana ya algorithm, ziligeuka kuwa sawa na kazi zinazoweza kuunganishwa kwenye mashine za Turing, na kwa hiyo kwa kazi za kujirudia. Matokeo ya mjadala unaoendelea kuhusu algoriti ni nini ilikuwa taarifa ambayo sasa inaitwa thesis ya Kanisa. Thesis ya kanisa. Wazo la algoriti, au utengamano wa kifaa fulani cha mitambo, sanjari na dhana ya utengamano kwenye mashine za Turing (na kwa hivyo na dhana ya utendakazi wa kujirudia). Kwa maneno mengine, algorithm ni mchakato ambao unaweza kuwakilishwa na mchoro wa kazi na kutekelezwa na mashine fulani ya Turing. Mashine ya Turing ni kifaa (kidhahiri) kinachojumuisha mkanda, kifaa cha kudhibiti, na kichwa cha kusoma. Tape imegawanywa katika seli. Kila seli ina herufi moja kutoka alfabeti ya nje
A=(
a 0,
a 1,…,
a n). Ishara fulani (tutaiashiria Ÿ
) ya alfabeti A inaitwa tupu, na seli yoyote iliyo na herufi tupu kwa sasa inaitwa seli tupu (wakati huo). Tape inadhaniwa kuwa na uwezekano wa kutokuwa na kikomo katika pande zote mbili. Kifaa cha kudhibiti kwa kila wakati wa wakati iko katika hali fulani q j inayomilikiwa na seti Q=(q 0 , q 1 ,..., q m )(m=l). Seti ya Q inaitwa alfabeti ya ndani
.
Moja ya masharti haya (kawaida q 0) inaitwa mwisho, na nyingine (kawaida q 1) - awali. Kichwa kilichosomwa kinasogea kando ya mkanda ili wakati wowote inachanganua seli moja ya tepi. Kichwa kinaweza kusoma yaliyomo kwenye seli inayoangaliwa na kuandika ndani yake badala ya alama inayoonekana alama fulani mpya kutoka kwa alfabeti ya nje. A(labda ni sawa). Wakati wa operesheni, kifaa cha kudhibiti, kulingana na hali ambayo iko na ishara inayotazamwa na kichwa, hubadilisha hali yake ya ndani. q. Kisha hutoa agizo kwa kichwa cha kuchapisha herufi fulani kutoka kwa alfabeti ya nje katika kisanduku kinachofuatiliwa A, na kisha kuamuru kichwa ama kukaa mahali, au kusogeza seli moja kulia, au kusogeza seli moja upande wa kushoto. Mara moja katika hali ya mwisho, mashine huacha kufanya kazi. Usanidi kwenye mkanda (au neno la mashine) inaitwa seti iliyoundwa na: 1) mlolongo a
i(1)
, a
mimi (2)
,...,a
i(s) herufi kutoka kwa alfabeti ya nje A, iliyorekodiwa katika seli za tepi, wapi a
i
(1)
.- ishara iliyoandikwa katika seli ya kwanza upande wa kushoto, nk. (mlolongo wowote kama huo unaitwa kwa neno moja), 2) hali ya kumbukumbu ya ndani q r; 3) nambari k seli inayotambuliwa. Tutaandika usanidi wa mashine kama ifuatavyo: a ,a ,..., a i(r) a ,a ,..., a i(1) i(2) i(r-1) q r i(r+1) i(r+2) i(s) Hapa r- seli inayotambuliwa inaangaziwa kama sehemu. Ikiwa mashine, kuwa katika hali ya ndani qi, inakubali seli iliyo na ishara u, huandika ishara kwa seli hii wakati unaofuata kwa wakati r, huenda katika hali ya ndani qs na kusonga kando ya mkanda, kisha wanasema kwamba mashine inatekeleza amri q i u
Æ
q s a r S, ambapo ishara S inaweza kuchukua mojawapo ya maadili yafuatayo: -1 - kuhamisha kichwa upande wa kushoto; +1 - mabadiliko ya kichwa kwenda kulia; 0 - kichwa kinabaki mahali. Orodha ya amri zote (quints) zinazoamua uendeshaji wa mashine ya Turing inaitwa programu gari hili. Mpango wa mashine mara nyingi huelezwa kwa namna ya meza. Kwa hivyo kwa hali iliyoelezewa hapo juu kwenye jedwali kwenye makutano mistari a
u na safu qi itasimama q s a r S(tazama jedwali 6.2.1) Jedwali 6.2.1. Ikiwa mpango unajumuisha magari kwa wanandoa (
q i, u
)
tano haipo, kisha kwenye meza kwenye makutano ya mstari u, na safu qi dashi imeongezwa. Kwa hiyo, Mashine ya Turing ni, kwa ufafanuzi, vifaa M=(A,Q,P), Wapi A- alfabeti ya nje, Q- alfabeti ya majimbo ya ndani; P- programu. Ikiwa mashine, baada ya kuanza kufanya kazi na neno fulani P iliyoandikwa kwenye mkanda, inafikia hali ya mwisho, basi inaitwa inayotumika kwa neno hili. Matokeo ya kazi yake ni neno lililorekodiwa kwenye kanda katika hali yake ya mwisho. Vinginevyo, mashine inasemekana haitumiki kwa neno R. Mfano 6.2.1. Wacha tutengeneze mashine ya Turing inayoongeza nambari asilia zilizoandikwa katika mfumo wa nambari zisizo za kawaida (yaani, iliyoandikwa kwa kutumia alama moja. |.
Kwa mfano 5=|||||.). Suluhisho. Fikiria alfabeti A
= {|, +, ⁄}. Mashine imedhamiriwa na programu ifuatayo: Hebu tuandike usanidi unaojitokeza kwa kufuatana wakati wa uendeshaji wa mashine hii kwenye neno la awali ||+ ||| , i.e. 2+3. Hapa, wakati wa kurekodi usanidi, tutatumia mkataba wafuatayo: hali ambayo mashine iko imeandikwa kwa mabano kwa haki nyuma ya barua inayozingatiwa. Mfano 6.2.2. Tengeneza mashine ya Turing ambayo huongeza maradufu nambari asilia zilizoandikwa katika mfumo wa nambari zisizo za kawaida. Suluhisho. Tutaunda mashine inayohitajika katika alfabeti A=(|, α, ⁄). Mpango wa mashine kama hiyo inaweza kuonekana kama hii: Wacha tutumie mashine inayosababisha kwa neno ||
. Utangulizi wa herufi mpya α na uingizwaji wa zile za asili |
kwenye α inaruhusu mtu kutofautisha asili |
na mpya (iliyokabidhiwa) |
. Jimbo q 1 hutoa uingizwaji |
juu ya α ,
jimbo q 2 hutoa utafutaji wa α ,
iliyokusudiwa kuchukua nafasi |
, na kusimamisha mashine katika kesi wakati α haijagunduliwa, q 3 inahakikisha kukamilika |
katika kesi wakati α ilibadilishwa na |.
Tukubaliane katika aya hii 1. seti N ya nambari za asili ina 0 (sifuri), i.e. N=(0,1,2,3,...); 2. kazi zinazozingatiwa f=f(x 1 ,x 2 ,…,x n) hufafanuliwa tu wakati viambajengo vinachukua maadili kutoka N, i.e. xiœN; 3. anuwai ya maadili ya kazi DŒN; 4. kazi zinazozingatiwa f=f(x 1 ,x 2 ,…,x n) zinaweza kufafanuliwa kwa kiasi, i.e. haijafafanuliwa kwa seti zote za nambari asilia. Hebu tujulishe kwa kuzingatia kazi rahisi o(x)=0, s(x)=x+1,
Mimi m n (x 1 ,..., x n)
=
x m Kazi hizi zinaweza kuhesabiwa kwa kutumia kifaa sahihi cha mitambo (kwa mfano, mashine ya Turing). Hebu tufafanue waendeshaji ambao huunda kazi mpya kulingana na kazi moja au zaidi zilizopewa. Opereta wa nafasi ya juu. Acha chaguo za kukokotoa f(x 1 ,x 2 ,…,x k) za vigeu vya k na vitendakazi k f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n) ziwe kupewa n vigeu. Nafasi kuu ya chaguo za kukokotoa f,f 1 ,…,f k ni chaguo za kukokotoa j(x 1 ,x 2 ,…,x n)= f(f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1) ,x 2 ,…,x n)) Tunasema kwamba chaguo la kukokotoa j linapatikana kwa kutumia opereta wa nafasi ya juu S k+1 kwa vitendakazi f,f 1 ,…,f k , na kuandika j=S k+1 (f,f 1 ,…,f k) Kwa mfano, S 2 (s, o)=s(o(x)), i.e. chaguo za kukokotoa sawa na 1, na S 2 (s,s)=s(s(x)) ni chaguo za kukokotoa y(x)=x+2. Opereta primitive recursion. Acha vitendakazi g(x 1 ,x 2 ,…,x n) na h(x 1 ,x 2 ,…,x n+2) itolewe. Hebu tuunde chaguo za kukokotoa f(x 1 ,x 2 ,…,x n+1) Acha thamani x 1 ,x 2 ,…,x n zirekebishwe. Kisha tunadhania: f(x 1 ,x 2 ,…,x n ,0)= g(x 1 ,x 2 ,…,x n) f 1 (x 1 ,x 2 ,…,x n ,y+1)= h(x 1 ,x 2 ,…,x n ,y, f(x 1 ,x 2 ,…,x n ,y)) Usawa huu hufafanua chaguo za kukokotoa f(x 1 ,x 2 ,…,x n+1) kipekee. Chaguo za kukokotoa f huitwa chaguo za kukokotoa zilizopatikana kwa kutumia opereta primitive recursion R. Nukuu f=R(g,h) imetumika. Ufafanuzi kwa kufata neno wa chaguo za kukokotoa (zilizoonyeshwa katika opereta ya urejeshaji wa awali) si kawaida katika hisabati. Kwa mfano, 1) digrii iliyo na kipeo asilia huamuliwa kwa kufata neno: a
0
=1, a n+ 1
= n
ÿ a
; 2) factorial: 0!=1, (n+1)!= n!ÿ(n+1), nk. Ufafanuzi. Kazi zinazoweza kupatikana kutoka kwa rahisi zaidi o(x)=0, s(x)=x+1, I m n (x 1 ,..., x n) = x m kwa kutumia waendeshaji wa nafasi za juu na urejeshaji wa primitive idadi ya nyakati. zinaitwa primitively kujirudia. Wacha tuangalie ikiwa chaguo za kukokotoa u(x,y)=x+y ni za awali za kujirudia. Hakika, tuna: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Huu ni mpango wa awali wa kujirudia, kwani x= I 1 1 (x), na u(x,y)+1=s(u(x,y))=S 2 (s,u). Hapa g(x)= I 1 1 (x), na h(x,y,u)=s(u)=S 2 (s, I 3 3). Vile vile imethibitishwa kuwa kazi m(x,y)=xÿy, d(x,y)=x y (tunadhani kwa ufafanuzi 0 0 =1), ukweli(x)=x! na wengine wengi ni wa kujirudia rudia. Kumbuka; kwamba vitendaji vya awali vya kujirudia vinafafanuliwa kila mahali (yaani, hufafanuliwa kwa maadili yote ya hoja zao). Hakika, kazi rahisi zaidi o, s, I m n hufafanuliwa kila mahali, na kutumia nafasi za juu zaidi na viendeshaji vya urejeshaji vya zamani kwa vitendakazi vilivyofafanuliwa kila mahali pia hutoa kazi zilizobainishwa kila mahali. Hivyo kazi kama = x − y, ikiwa x ≥ y< y f(x,y) haipo ikiwa x haiwezi kujirudia primitively. Hatuna haki ya kuzingatia chaguo za kukokotoa f(x,y)=x-y hapa, kwani thamani za chaguo za kukokotoa lazima ziwe nambari asilia (kwa hivyo zisiwe hasi). Hata hivyo, mtu anaweza kuzingatia kazi ÷ y = 0x − y ifif x x<≥y.y Wacha tuangalie ikiwa inajirudia primitively. Hebu kwanza tuthibitishe kwamba chaguo za kukokotoa j(x)=xπ1 ni za awali za kujirudia. Hakika, j(0)=0. j(y+1)=(y+1)π1=y, ambayo hutumika kama mpango wa urejeshaji wa awali wa chaguo za kukokotoa xπ1. Hatimaye, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) ni mpango wa urejeshaji wa awali wa xπy. Darasa pana zaidi la vitendakazi kuliko vitendakazi vya awali vya kujirudishia ni darasa la vitendakazi rudishi (tazama ufafanuzi hapa chini). Katika fasihi kazi hizi pia huitwa kujirudia kwa sehemu .
Ili kuwaamua, tunaanzisha mwendeshaji mmoja zaidi. Opereta wa kupunguza. Acha kitendakazi f(x 1 ,x 2 ,… ,x n ,x n+1) itolewe. Hebu turekebishe baadhi ya thamani x 1 ,x 2 ,… ,x n ya vigezo vya kwanza vya n na tuhesabu f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1) ), f(x 1 ,x 2 ,… ,x n ,2) n.k. Ikiwa y ndio nambari asilia ndogo zaidi ambayo f(x 1 ,x 2 ,… X n ,y)=x n+1 (yaani thamani f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f( x 1, x 2 ,... X n ,y-1) zote zipo na si sawa na xn +1), kisha tunaweka g(x 1 ,x 2 ,… X n ,x n+1)=y. Kwa hivyo, g(x 1 ,x 2 ,… ,x n ,x n+1)=min(y|f(x 1 ,x 2 ,…,x n ,y)=x n+1). Kama vile y hapana, basi tunazingatia kwamba f(x 1 ,x 2 ,… ,x n ,x n+1) haijafafanuliwa. Kwa hivyo, kesi tatu zinawezekana: 1. f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) zipo na hazilingani na xn +1, na f(x 1 ,x 2 ,…,x n ,y)=x n+1 ; 2. f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) zipo na hazilingani na xn +1, lakini f(x 1 ,x 2 ,…,x n ,y) haipo; 3. f(x 1 ,x 2 ,… ,x n ,i) zipo kwa iœN zote na ni tofauti na xn +1. Ikiwa kesi ya 1 itatokea, basi g(x 1 ,x 2 ,… ,x n ,x n+1)=y, na ikiwa kesi ya 2 au ya 3, basi g(x 1 ,x 2 ,… ,x n , x n) +1) haijafafanuliwa. Chaguo za kukokotoa g zilizopatikana kwa njia hii inasemekana kupatikana kutoka kwa f kwa kutumia kiendeshaji cha kupunguza M. Tunaandika g= Mf. Opereta ya kupunguza ni ujanibishaji dhahiri wa opereta ya kitendakazi kinyume. Ujumla ni wa kina kabisa, kwani kazi f haihitajiki kuwa moja-kwa-moja (katika kutofautisha x n+1) Ufafanuzi. Kazi ambazo zinaweza kupatikana kutoka kwa rahisi zaidi o(x)=0, s(x)=x+1,
Mimi m n (x 1 ,..., x n)
= x m kutumia waendeshaji wa nafasi za juu, urejeshaji wa primitive, na waendeshaji kupunguza idadi ya nyakati huitwa kujirudia. Darasa la vitendaji vya kujirudi ni pana zaidi kuliko darasa la vitendaji vya awali vya kujirudia, ikiwa tu kwa sababu lina si tu vitendaji ambavyo vimefafanuliwa kila mahali. Hebu tuthibitishe, kwa mfano, kwamba kazi = x − y, ikiwa x ≥ y< y f(x,y) haipo ikiwa x inajirudia. Kwa hakika, f(x,y)=min(z| y+z=x), na ilianzishwa hapo awali kuwa chaguo za kukokotoa u(x,y)=x+y awali zinajirudia. Vitendaji vya kujirudi huakisi uelewa wetu angavu wa vitendakazi ambavyo baadhi ya kifaa cha kimitambo kinaweza kukokotoa. Hasa, zinaweza kuunganishwa kwenye mashine za Turing (tazama aya iliyotangulia). Kinyume chake, kila kazi inayoweza kutekelezeka kwenye mashine ya Turing inajirudia. Hatutaangalia ukweli huu, kwani itachukua muda mwingi na nafasi. Uthibitisho kamili unaweza kupatikana, kwa mfano, katika kitabu cha A.I. Maltsev "Algorithms na kazi za kujirudia". Kumbuka kuwa si kila kazi ya hoja asilia inajirudia, hata sio kila kazi ya hoja moja. Uwepo wa kazi zisizo za kujirudia ni "sababu ya hisabati" ya kuwepo kwa matatizo ya algorithmically yasiyoweza kutatuliwa. Katika matawi mbalimbali ya hisabati kuna matatizo ya algorithmically yasiyoweza kutatuliwa, i.e. matatizo ambayo hakuna algorithm ya ufumbuzi, na si kwa sababu bado haijazuliwa, lakini kwa sababu haiwezekani kwa kanuni. Bila shaka, algorithm lazima ieleweke kwa maana ya mashine za Turing na kazi za kujirudia. Wacha tutengeneze moja ya shida hizi Tatizo la kusimamisha mashine ya kuwasha. Mashine ya Turing ni kitu kinachofafanuliwa kwa idadi maalum ya vigezo. Mipangilio yote isiyo kamili kutoka kwa seti moja hadi nyingine inaweza kuhesabiwa upya kwa ufanisi. Kwa hivyo, kila mashine ya Turing inaweza kupewa nambari (nambari ya asili). Acha T(n) iwe mashine ya Turing yenye nambari n. Mashine zingine zinazoanza kufanya kazi kwenye ukanda usio na kitu hatimaye huacha, na zingine huendesha kwa muda usiojulikana. Tatizo linatokea: ukipewa nambari ya asili n, tambua ikiwa mashine ya Turing T(n) iliyozinduliwa kwenye mkanda tupu itaacha au la. Jukumu hili haiwezi kuamua kwa algorithmically. Hiyo ni, hakuna utaratibu wa moja kwa moja ,
kwa kila n huamua ikiwa mashine T(n) itasimama au la. Hii haituzuii sisi kuamua kwa mashine yoyote ikiwa itasimama au la. Hakuna njia ambayo hutatua hii kwa mashine zote mara moja .
Kwa kuzingatia shida, jinsi ya kupata algorithm bora ya kuisuluhisha? Na ikiwa algorithm inapatikana, inawezaje kulinganishwa na algorithms zingine zinazosuluhisha shida sawa? Jinsi ya kutathmini ubora wake? Maswali ya aina hii ni ya kupendeza kwa waandaaji wa programu na wale wanaohusika katika utafiti wa kinadharia wa kompyuta. Kuna vigezo vingi vya kutathmini algorithms. Mara nyingi, tutavutiwa na mpangilio wa ukuaji wa wakati na uwezo wa kumbukumbu unaohitajika kutatua tatizo data ya uingizaji inapoongezeka. Tungependa kuhusisha nambari na kila kazi mahususi, inayoitwa ukubwa wake ,
ambayo inaweza kuonyesha kipimo cha kiasi cha data ya pembejeo. Kwa mfano, saizi ya tatizo la kuzidisha matrix inaweza kuwa saizi kubwa zaidi ya matrices ya sababu. Wakati unaochukuliwa na algorithm kama kazi ya saizi ya shida inaitwa utata wa wakati algorithm hii. Tabia ya ugumu huu katika kikomo kadiri saizi ya shida inavyoongezeka inaitwa ugumu wa wakati wa asymptotic
.
Vile vile tunaweza kufafanua ugumu wa capacitive na uchangamano wa capacitive usio na dalili. Ni utata wa asymptotic wa algorithm ambayo hatimaye huamua ukubwa wa matatizo ambayo yanaweza kutatuliwa na algorithm hii. Ikiwa algorithm itachakata maingizo ya saizi n kwa wakati cÿn 2 , ambapo c -
baadhi ya mara kwa mara, basi wanasema kwamba ugumu wa wakati wa algorithm hii ni O (n 2) (soma "of order en square"). Mtu anaweza kufikiria kwamba ongezeko kubwa la kasi ya kompyuta inayoletwa na kizazi cha sasa cha dijiti kompyuta, itapunguza umuhimu wa algorithms bora. Hata hivyo, kinyume hutokea. Kadiri mashine za kompyuta zinavyokua kwa kasi na kasi zaidi na tunaweza kutatua matatizo makubwa zaidi, ni utata wa algoriti ambayo huamua ongezeko la ukubwa wa tatizo ambalo linaweza kupatikana kadri kasi ya mashine inavyoongezeka. Wacha tuseme tuna algoriti tano A1, A2,…,A5 na ugumu ufuatao wa wakati: Hapa, utata wa wakati ni idadi ya vitengo vya wakati vinavyohitajika kuchakata ingizo la saizi n. Acha kitengo cha muda kiwe milisekunde moja (1sec=1000 milisekunde). Kisha algorithm A1 inaweza kusindika pembejeo ya ukubwa wa 1000 kwa sekunde moja, wakati A5 inaweza kusindika pembejeo la ukubwa si zaidi ya 9. Katika jedwali. 6.5.1. Ukubwa wa matatizo ambayo yanaweza kutatuliwa kwa sekunde moja, dakika moja na saa moja kwa kila algorithms hizi tano hutolewa. Jedwali 6.5.3. Hebu tufikiri kwamba kizazi kijacho cha kompyuta kitakuwa mara 10 kwa kasi zaidi kuliko sasa. Katika jedwali 6.5.2. inaonyesha jinsi ukubwa wa matatizo tunayoweza kutatua kutokana na ongezeko hili la kasi itaongezeka. Kumbuka kwamba kwa algorithm A5, ongezeko la kasi la mara kumi huongeza ukubwa wa tatizo ambalo linaweza kutatuliwa na vitengo vitatu tu (tazama mstari wa mwisho katika Jedwali 6.5.2.), wakati kwa algorithm A3 ukubwa wa tatizo zaidi ya mara tatu. . Jedwali 6.5.4. Badala ya athari ya kuongeza kasi, hebu sasa fikiria athari ya kutumia algorithm yenye ufanisi zaidi. Hebu turudi kwenye jedwali 6.5.1. Ikiwa tutachukua dakika 1 kama msingi wa kulinganisha, basi kwa kubadilisha algorithm A4 na algoriti A3, tunaweza kutatua tatizo mara 6 zaidi, na kwa kubadilisha A4 na A2. ,
unaweza kutatua tatizo mara 125 kubwa. Matokeo haya ni ya kuvutia zaidi kuliko uboreshaji wa 2x uliopatikana kwa kasi ya 10x. Ikiwa tutachukua saa 1 kama msingi wa kulinganisha, tofauti itageuka kuwa muhimu zaidi. Kutokana na hili tunahitimisha kuwa uchangamano usio na dalili wa algoriti hutumika kama kipimo muhimu cha ubora wa kanuni, na kipimo ambacho kinaahidi kuwa muhimu zaidi na ongezeko la baadae la kasi ya kukokotoa. Licha ya ukweli kwamba tahadhari kuu hapa hulipwa kwa utaratibu wa ukuaji wa kiasi, mtu lazima aelewe kwamba utaratibu mkubwa wa ukuaji katika utata wa algorithm inaweza kuwa na mara kwa mara ndogo ya kuzidisha (mara kwa mara). c katika ufafanuzi wa O(f(x))), kuliko utaratibu mdogo wa ongezeko la utata wa algorithm nyingine. Katika kesi hii, algorithm yenye utata unaoongezeka kwa kasi inaweza kuwa bora kwa matatizo madogo - labda hata kwa matatizo yote tunayopendezwa nayo. Kwa mfano, tuseme kwamba uchangamano wa wakati wa algoriti A1, A2, A3, A4, A5 ni 1000n, 100nÿlog(n), 10n2, n3, na 2, mtawalia. n Kisha A5 itakuwa bora zaidi kwa matatizo ya ukubwa 2§n§9, A2 - kwa matatizo ya ukubwa 10§n§58, A1 - saa 59§n§1024, na A1- na n>1024.- 1. F.A. Novikov. Hisabati ya kipekee kwa watengeneza programu./ St. Petersburg: Peter, 2001, 304С. 2. S.V. Sudoplatov, E.V. Ovchinnikova. Vipengele vya Hisabati Tofauti./ M., INFRA-M, Novosibirsk, Nyumba ya Uchapishaji ya NSTU, 3. Y.M.Erusalimsky. Hisabati ya kipekee / M., "Kitabu cha Chuo Kikuu", 2001, 279 pp. 4. A. Aho, J. Hopcroft, J. Ullman. Ujenzi na uchambuzi wa algorithms ya hesabu. / M., Mir, 1979, 536С. 5. V.N.Nefedov, V.A.Osipova Kozi katika hisabati Diskret./ M., Nyumba ya Uchapishaji ya MAI, 1992, 264P.§4.3. Quantifiers na mali zao.
Sura ya V. Nadharia rasmi.
§5.1. Ufafanuzi wa nadharia rasmi.
§5.2. Hesabu ya pendekezo.
§5.3. Nadharia ya kupunguzwa. Ukamilifu wa IV.
§5.4. Uthibitisho otomatiki wa nadharia.
§5.5. Njia ya azimio katika IW.
Sura ya VI. Vipengele vya nadharia ya algorithms.
§6.1. Ufafanuzi wa algorithm.
§6.2. Mashine ya kusaga.
q 0
…
qi
…
q m
…
u
q
s
a
rS
…
§6.3. Vitendaji vya kujirudia
§6.4. Matatizo ya algorithmically yasiyotatulika.
§6.5. Algorithms na ugumu wao.
FASIHI.