Hantar kerja baik anda di pangkalan pengetahuan adalah mudah. Gunakan borang di bawah
Pelajar, pelajar siswazah, saintis muda yang menggunakan asas pengetahuan dalam pengajian dan kerja mereka akan sangat berterima kasih kepada anda.
Masih belum ada versi HTML karya.
Anda boleh memuat turun arkib kerja dengan mengklik pada pautan di bawah.
Dokumen yang serupa
Takrif asas logik matematik, Boolean dan fungsi setara. Konsep umum Algebra Boolean. Algebra Zhegalkin: pernyataan dan predikat. Definisi teori formal. Elemen teori algoritma, fungsi rekursif, mesin Turing.
kursus kuliah, ditambah 08/08/2011
Bentuk asas pemikiran: konsep, pertimbangan, inferens. Sebuah esei oleh George Boole yang meneroka algebra logik secara terperinci. Nilai kebenaran (iaitu, kebenaran atau kepalsuan) sesuatu pernyataan. Operasi logik penyongsangan (negasi) dan kata hubung.
pembentangan, ditambah 14/12/2016
Tafsiran grafik set dan operasi padanya. Logik matematik, algebra Boolean. Bentuk normal konjungsi sempurna. Formula setara dan buktinya. Kesempurnaan sistem Fungsi Boolean. Logik predikat, teori graf.
kuliah, ditambah 12/01/2009
Sejarah kemunculan algebra Boolean, perkembangan sistem kalkulus proposisi. Kaedah untuk menetapkan kebenaran atau kepalsuan kompleks kenyataan logik dengan menggunakan kaedah algebra. Disjungsi, konjungsi dan penolakan, jadual kebenaran.
pembentangan, ditambah 02/22/2014
Matriks segi empat sama dan penentu. Selaraskan ruang linear. Penyelidikan Sistem persamaan linear. Algebra matriks: penambahan dan pendaraban mereka. Imej geometri nombor kompleks dan mereka bentuk trigonometri. Teorem dan asas Laplace.
manual latihan, ditambah 03/02/2009
Konsep asas teori nombor positif (semula jadi). Pembangunan trengkas untuk operasi aritmetik. Bahasa simbolik untuk pembahagian. Sifat dan algebra perbandingan. Meningkatkan perbandingan kepada kuasa. Petak dua semula. Teorem kecil Fermat.
pembentangan, ditambah 06/04/2014
Sistem pemprosesan digital maklumat. Konsep algebra Boole. Penetapan operasi logik: percabaran, konjungsi, penyongsangan, implikasi, kesetaraan. Undang-undang dan identiti algebra Boole. Asas Logik KOMPUTER. Penukaran formula struktur.
pembentangan, ditambah 10/11/2014
Universiti Volzhsky dinamakan sempena. Tatishcheva.
Kuliah pada logik matematik dan teori algoritma.
Disusun oleh: Profesor Madya S.V. Kaverin.
Bab I. Algebra Logik.
§1.1. Definisi fungsi Boolean.
Fungsi Boolean y=f(x 1 ,x 2 ,…,x n)daripada P pembolehubah x 1 , x 2 ,...,x n ialah sebarang fungsi di mana argumen dan fungsi boleh mengambil nilai sama ada 0 atau 1, i.e. fungsi Boolean ialah peraturan yang menggunakan set arbitrari sifar dan satu
(x 1 ,x 2 ,...,x n) diberikan kepada nilai 0 atau 1.
Fungsi Boolean juga dipanggil fungsi algebra logik, fungsi binari dan fungsi pensuisan.
Fungsi Boolean daripada n pembolehubah boleh ditentukan oleh jadual kebenaran di mana set nilai argumen disusun dalam tertib menaik nombornya : pada mulanya pengambilan sedang dijalankan, mewakili pengembangan binari 0 (set ini bernombor 0); kemudian datang set, iaitu pengembangan binari 1, kemudian 2, 3, dsb. Set terakhir terdiri daripada n unit dan merupakan pengembangan binari nombor 2 n-1 (urutan susunan set ini akan dipanggil susunan leksikografi ). Memandangkan kiraan bermula dari 0, dan nilai fungsi Boolean boleh sama ada 0 atau n
1, kami membuat kesimpulan bahawa terdapat hanya 22 fungsi Boolean yang berbeza bagi n pembolehubah. Oleh itu, terdapat, sebagai contoh, 16 fungsi Boolean bagi dua pembolehubah, 256 daripada tiga, dsb.
Contoh 1.1.1.(undi) . Mari kita pertimbangkan peranti yang merekodkan penggunaan resolusi tertentu oleh "jawatankuasa tiga". Setiap ahli jawatankuasa menekan butang sendiri apabila meluluskan resolusi. Jika majoriti ahli mengundi menyokong, resolusi itu diterima pakai. Ini dirakam oleh peranti rakaman. Oleh itu, peranti melaksanakan fungsi f(x,y,z ) , yang jadual kebenarannya mempunyai bentuk
| 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 |
Fungsi Boolean juga ditentukan secara unik dengan menyenaraikan semua tupel yang mana ia mengambil nilai 0, atau dengan menghitung semua tupel yang mana ia mengambil nilai 1. Fungsi yang diperolehi dalam contoh f juga boleh ditentukan oleh sistem kesamaan berikut: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
Vektor nilai fungsi Boolean y=f(x 1 ,x 2 ,…,x n) ialah set tertib semua nilai fungsi f, yang mana nilainya disusun mengikut susunan leksikografi. Sebagai contoh, biarkan fungsi tiga pembolehubah f ditentukan oleh vektor nilai (0000 0010) dan adalah perlu untuk mencari set di mana f mengambil nilai 1. Kerana 1 berada di tempat ke-7, dan penomboran dalam susunan leksikografi bermula dari 0, maka perlu mencari pengembangan binari 6. Oleh itu, fungsi f mengambil nilai 1 pada set (110).
§1.2. Fungsi Boolean asas.
Di antara fungsi Boolean, fungsi Boolean asas yang dipanggil menonjol, yang mana mana-mana fungsi Boolean bagi sebarang bilangan pembolehubah boleh diterangkan.
1. Fungsi Boolean f(x 1 ,x 2 ,…,x n) mengambil nilai 1 pada semua set sifar dan satu dipanggil malar 1, atau unit yang sama. Jawatan : 1 .
2. Fungsi Boolean f(x 1 ,x 2 ,…,x n) mengambil nilai 0 pada semua set sifar dan satu dipanggil malar 0, atau sifar yang sama. Jawatan : 0 .
3. Penafian ialah fungsi Boolean bagi satu pembolehubah yang ditakrifkan oleh jadual kebenaran berikut
Nama lain : pendaraban logik (produk); logik "dan".
Jawatan : x&y, xÿy, x⁄y, min(x,y).
5. Disjunction
Nama lain : akibat logik. Jawatan : xØy, xfly, xy.
7. Kesetaraan ialah fungsi Boolean bagi dua pembolehubah yang ditakrifkan oleh jadual kebenaran berikut
Nama lain : anti-kesetaraan. Jawatan : x∆y, x+y.
9. Strok Schaeffer adalah fungsi Boolean bagi dua pembolehubah yang ditakrifkan oleh jadual kebenaran berikut
Nama lain : penolakan disjungsi, logik "bukan-atau", fungsi Webb.
Jawatan : x∞y ; untuk fungsi Webb - x±y.
Komen. Simbol Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ terlibat dalam tatatanda fungsi asas kami akan memanggil mereka sambungan atau operasi.
§1.3. Menentukan fungsi Boolean menggunakan fungsi asas.
Jika anda menggantikan beberapa fungsi Boolean ke dalam fungsi logik dan bukannya pembolehubah, hasilnya ialah fungsi Boolean baharu yang dipanggil superposisi fungsi diganti (fungsi kompleks). Menggunakan superposisi, anda boleh mendapatkan fungsi yang lebih kompleks yang boleh bergantung pada sebarang bilangan pembolehubah. Kami akan memanggil menulis fungsi Boolean dari segi fungsi Boolean asas formula melaksanakan fungsi ini.
Contoh 1.3.1. Biarkan fungsi Boolean asas x¤y diberikan. Mari kita gantikan fungsi x 1 ∞x 2 dan bukannya x. Kami memperoleh fungsi tiga pembolehubah (x 1 ∞x 2)¤y. Jika bukannya pembolehubah y kita gantikan, sebagai contoh, x 3 ∆x 4, maka kita dapat ciri baharu daripada empat pembolehubah: (x 1 ∞x 2)¤(x 3 ∆x 4). Jelas sekali, dengan cara ini kita akan memperoleh fungsi Boolean, yang akan dinyatakan melalui fungsi Boolean asas.
Memandang ke hadapan, kami perhatikan itu mana-mana fungsi Boolean boleh diwakili sebagai superposisi fungsi asas.
Untuk rakaman yang lebih padat fungsi yang kompleks mari kita perkenalkan konvensyen berikut : 1) kurungan luar ditinggalkan; 2) operasi dalam kurungan dilakukan terlebih dahulu; 3) ia dianggap bahawa keutamaan penghubung berkurangan dalam susunan berikut : Ÿ, ⁄, ¤, Ø, ~. Untuk penghubung yang setara dan penghubung yang tinggal (∆,|,∞), anda harus meletakkan kurungan buat masa ini.
Contoh 1.3.2. Dalam formula x⁄y¤z kurungan diletakkan dengan cara berikut: ((x⁄y)¤z), kerana operasi ⁄ lebih kuat daripada operasi ¤ mengikut perjanjian kami.
1. Dalam formula x¤y~zØx kurungan diletakkan seperti berikut: ((x¤y)~(zØx))
2. Dalam formula (x∆y)~zØxy¤Ÿz kurungan diletakkan seperti berikut: ((x∆y)~(zØ((xy)¤(Ÿz)))).
3. Formula xØyØz, mengikut perjanjian kami, tidak ditulis dengan betul, kerana meletakkan kurungan menghasilkan dua fungsi yang berbeza: ((xØy)Øz) dan (xØ(yØz)).
§1.4. Pembolehubah bererti dan tidak bererti.
Fungsi Boolean y=f(x 1 ,x 2 ,…,x n) bergantung dengan ketara daripada pembolehubah x k jika set nilai sedemikian wujud a 1 ,a 2 ,…,a k - 1, a k+1, a k + 2 ,…, a n bahawa 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).
Dalam kes ini x k dipanggil pembolehubah penting , V sebaliknya x k dipanggil pembolehubah tidak ketara (dummy). . Dengan kata lain, pembolehubah tidak relevan jika mengubahnya tidak mengubah nilai fungsi.
Contoh 1.4.1. Biarkan fungsi Boolean f 1 (x 1 ,x 2) dan f 2 (x 1 ,x 2) ditakrifkan oleh jadual kebenaran berikut:
| 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 |
Untuk fungsi ini pembolehubah x 1 - adalah signifikan, dan pembolehubah x 2 adalah tidak signifikan.
Jelas sekali, fungsi Boolean tidak mengubah nilainya dengan memperkenalkan (atau mengalih keluar) pembolehubah yang tidak berkaitan. Oleh itu, dalam perkara berikut, fungsi Boolean dianggap sehingga pembolehubah tidak penting (dalam contoh kita boleh tulis: f 1 (x 1 , x 2) = x 1 , f 2 (x 1 , x 2) = Ÿx 1 ).
§1.5. Jadual kebenaran. Fungsi yang setara.
Mengetahui jadual kebenaran untuk fungsi asas, anda boleh mengira jadual kebenaran bagi fungsi yang formula ini laksanakan.
Contoh 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)
Oleh itu, formula F1 melaksanakan disjungsi. Contoh 1.5.2. F2=x 1 ⁄x 2 Øx 1
Oleh itu, formula F3 melaksanakan disjungsi.
Fungsi Boolean f1 dan f2 dipanggil bersamaan, jika pada setiap set ( a 1 ,a 2 ,…, a n) sifar dan satu, nilai fungsi bertepatan. Notasi untuk fungsi setara adalah seperti berikut : f1=f2.
Mengikut contoh 1-3 yang diberikan, kita boleh menulis
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. Kesetaraan asas.
Persamaan yang diberikan selalunya berguna apabila beroperasi dengan fungsi Boolean.
Di bawah H, H1, H2,... berdiri untuk beberapa fungsi Boolean.
1. Hukum penafian berganda: H = H.
2. Idempotensi
3. Komutatif:
H1*H2=H2*H1, di mana simbol * bermaksud salah satu daripada penghubung &, ¤, ∆,
4. pergaulan:
H1*(H2*H3)=(H1*H2)*H3, dengan simbol * bermaksud salah satu daripada penghubung &, ¤, ∆, ~.
5. Pengagihan:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. Undang-undang De Morgan:
H1& H2 = H1 ∨ H2 , H1∨ H2 = H1 & H2 .
7. Peraturan pengambilalihan:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Undang-undang pelekatan:
H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.
9. Undang-undang penyongsangan: H ∨ H = 1, H & H = 0.
10. Peraturan untuk operasi dengan pemalar:
H¤1=1, H&1=H, H¤0=H, H&0=0.
Untuk menyemak kebenaran kesetaraan di atas, sudah cukup untuk membina jadual kebenaran yang sepadan.
Ambil perhatian bahawa sifat persekutuan operasi membolehkan operasi ini dilanjutkan kepada sebarang bilangan pembolehubah. Jadi, sebagai contoh, notasi x¤у¤z¤w adalah betul, kerana sebarang susunan kurungan menghasilkan fungsi yang sama. Sifat komutatif operasi membolehkan anda menukar pembolehubah dalam formula. Contohnya, x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Kesempurnaan berfungsi.
Dalam digital moden yang tipikal komputer nombornya ialah 0 dan 1. Oleh itu, arahan yang pemproses laksanakan ialah fungsi Boolean. Di bawah ini kami akan menunjukkan bahawa sebarang fungsi Boolean dilaksanakan melalui konjungsi, disjungsi dan penolakan. Akibatnya, adalah mungkin untuk membina pemproses yang diperlukan, mempunyai unsur-unsur pelupusan yang melaksanakan konjungsi, disjungsi dan penolakan. Bahagian ini dikhaskan untuk menjawab soalan: adakah terdapat (dan jika ya, apakah) sistem lain bagi fungsi Boolean yang mempunyai sifat yang boleh digunakan untuk menyatakan semua fungsi lain.
Mari kita perkenalkan beberapa kelas fungsi.
1. Kelas fungsi yang mengekalkan pemalar 0, i.e. fungsi tersebut
2. Kelas fungsi yang mengekalkan pemalar 1, i.e. fungsi tersebut
3. Kelas fungsi dwi kendiri, i.e. fungsi sedemikian y=f(x 1 ,x 2 ,…,x n) supaya f(x 1 , x 2 ,… , x n) = f(x 1 , x 2 ,… , x n) .
darjah 4 fungsi linear, iaitu fungsi sedemikian y=f(x 1 ,x 2 ,…,x n), yang boleh diwakili sebagai f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ c n x n, di mana c 0, c 1, c 2 ...pekali yang boleh mengambil nilai 0 atau 1.
5. Kelas fungsi monotonik. Pada set set sifar dan satu Bn =((x 1 ,x 2 ,…,x n):x i œ(0,1),i=1,2,…,n) kami memperkenalkan susunan separa seperti berikut:
(a 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) jika dan hanya jika a 1 § b 1 , a 2 § b 2 ,…,a n § b n. Fungsi f(x 1, x 2,..., x n) dipanggil monotonik jika bagi mana-mana dua unsur daripada B n sedemikian
(a 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) ia berikutan bahawa f( a 1 ,a 2 ,...,a n)§f( b 1 ,b 2 ,...,b n).
Sistem S bagi fungsi Boolean, yang superposisinya boleh mewakili sebarang fungsi Boolean, dipanggil berfungsi lengkap . Mereka mengatakan ia berfungsi sistem lengkap S bentuk fungsi Boolean asas dalam ruang logik. Asas S dipanggil yang minimum , jika penyingkiran mana-mana fungsi daripadanya menjadikan sistem ini tidak lengkap.
Kriteria kesempurnaan (Teorem pasca) . Sistem S bagi fungsi Boolean lengkap jika dan hanya jika ia termasuk sekurang-kurangnya satu fungsi: pemalar tidak mengekalkan 0, pemalar tidak dipelihara 1, bukan dwi-diri, tidak linear dan tidak monotonik.
Jadual 1.7 menunjukkan sifat yang ada pada fungsi Boolean asas (simbol * menunjukkan sifat yang ada pada fungsi tertentu).
Menggunakan teorem Post dan jadual 1.7, anda boleh membina asas daripada fungsi asas mengikut peraturan seterusnya. Dengan memilih mana-mana fungsi Boolean asas dan menambahnya, jika perlu, dengan fungsi lain supaya kesemuanya bersama-sama memenuhi teorem kesempurnaan fungsi. Melalui fungsi asas ini kita boleh menyatakan Semua fungsi Boolean yang lain.
Mari bina beberapa pangkalan yang kerap digunakan dalam aplikasi.
Jadual 1.7
| Nama | Jawatan | Tidak boleh disimpan pemalar |
Tidak boleh disimpan pemalar |
Samodvoys kesahan |
||
| Const.0 | 0 | * | * | |||
| Const.1 | 1 | * | * | |||
| Negatif | Ÿ | * | * | * | ||
| Kongyun. | & | * | * | |||
| Disjunction. | ¤ | * | * | |||
| tersirat. | Ø | * | * | * | * | |
| Bersamaan. | ~ | * | * | * | ||
| Jumlahkan mengikut mod_2 | ∆ | * | * | * | ||
| | | * | * | * | * | * | |
| anak panah Pierce | ∞ | * | * | * | * | * |
1. Sistem fungsi S1=(Ÿ,⁄,¤) membentuk asas. Untuk mengurangkan fungsi Boolean kepada bentuk yang mengandungi hanya penghubung daripada asas S1, kesetaraan berikut boleh berguna: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , xy = x ∨ y , x ↓ y = x & y .
2. Sistem S2=(Ÿ,&) membentuk asas. Fungsi sewenang-wenangnya mula-mula boleh dikurangkan kepada bentuk yang mengandungi penghubung dari S1 dan kemudian
gunakan hubungan x ∨ y = x ⋅ y.
3. Sistem S3=(Ÿ,¤) membentuk asas. Fungsi arbitrari boleh mula-mula dikurangkan kepada bentuk yang mengandungi penghubung dari S1 dan kemudian
gunakan hubungan x ⋅ y = x ∨ y.
4. Sistem S4=(1,&,∆) membentuk asas. Fungsi arbitrari boleh mula-mula dikurangkan kepada bentuk yang mengandungi penghubung daripada S1 dan kemudian gunakan hubungan x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y.
5. Sistem S5=(|) membentuk asas. Fungsi arbitrari boleh mula-mula dikurangkan kepada bentuk yang mengandungi penghubung daripada S2 dan kemudian menggunakan hubungan x ⋅ y = x y, x = xx.
6. Sistem S6=(∞) membentuk asas. Fungsi arbitrari boleh mula-mula dikurangkan kepada bentuk yang mengandungi penghubung daripada S3 dan kemudian
gunakan hubungan x ∨ y = x ↓ y, x = x ↓ x.
7. Sistem S7=(Ø,0) membentuk asas.
Contoh 1.7.1. Tulis fungsi x¨(y∆z) dalam asas S1=(Ÿ,⁄,¤). x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∨ z) y
Bab II. Algebra Boolean.
Set semua boolean dalam asas S1=( ÿ, &, ⁄} bentuk Algebra Boolean. Oleh itu, dalam algebra Boolean, semua formula ditulis menggunakan tiga penghubung: Ÿ, &, ¤. Kami meneliti sebahagian sifat algebra ini dalam Bab I (lihat, sebagai contoh, kesetaraan asas). Bab ini membincangkan sifat khusus untuk algebra Boolean dan oleh itu sepanjang bab ini kita hanya akan berurusan dengan tiga fungsi: ÿ, &, ⁄.
§2.1. Bentuk biasa.
Bentuk biasa ialah cara yang tidak jelas secara sintaksis untuk menulis formula yang melaksanakan fungsi yang diberikan.
Jika x ialah pembolehubah logik, dan σœ(0,1) maka ungkapan x σ = x jika jika σσ == 10 atau x σ = 10 jika jika x x =≠σσ , x dipanggil huruf . Huruf x dan Ÿx dipanggil berlawanan. Konjungsi disjunct disebut penceraian huruf. Sebagai contoh, rumus x ⋅ y ⋅ z dan x ⋅ y ⋅ x ⋅ x ialah kata hubung, rumus x ∨ y ∨ z dan x ∨ y ∨ x ialah pecah, dan formula z ialah kedua-dua konjungsi dan pemecahan.
Bentuk normal disjungtif (DNF) dipanggil pemecahan bilangan kata hubung yang terhingga .
Bentuk normal bersambung (CNF) dipanggil kata hubung bagi bilangan klausa yang terhingga .
Lebih ringkas: DNF ialah jumlah produk, dan CNF ialah hasil jumlah logik.
1. xÿy¤yÿz¤x ialah DNF (jumlah produk).
2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z ialah CNF (hasil hasil tambah).
3. x ∨ y ∨ z ∨ w ialah DNF dan CNF (secara serentak).
4. x ⋅ y ⋅ z ⋅ w ialah DNF dan CNF (secara serentak).
5. (x¤x¤y)·(y¤z¤x)·z ialah CNF.
6. x⋅y⋅z dan x⋅y⋅x⋅x ialah DNF.
7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z bukan bentuk biasa (bukan DNF atau CNF).
Biarkan fungsi f ditulis dalam asas S1. Fungsi ini dikurangkan kepada bentuk normal seperti berikut:
1) kami menggunakan undang-undang De Morgan untuk mengubah formula kepada bentuk di mana tanda negatif hanya berkaitan dengan pembolehubah individu;
2) kami menggunakan peraturan untuk membuang negatif berganda: ŸŸx=x;
H1&(H2¤H3)=(H1&H2)¤(H1&H3) , dan undang-undang pengedaran kedua untuk pengurangan kepada CNF. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).
Sebarang fungsi Boolean boleh mempunyai bilangan perwakilan DNF dan CNF yang tidak terhingga. Sebagai contoh, dengan menggunakan tambahan undang-undang penyongsangan dan peraturan operasi dengan pemalar, adalah mungkin untuk memastikan bahawa dalam setiap individu bersambung atau putus sebarang pembolehubah muncul tidak lebih daripada sekali (sama ada dirinya atau penafiannya).
Contoh 2.1.1. Untuk mengurangkan kepada DNF kita menggunakan undang-undang 1 pengagihan.
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)= ialah CNF
= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = - ini CNF lain
X ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅ = y⋅
X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ialah DNF
Contoh 2.1.2. Untuk mengurangkan kepada CNF adalah perlu untuk menggunakan hukum pengagihan kedua.
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) ialah CNF
§2.2. Bentuk normal yang sempurna.
Jika dalam setiap sebutan bentuk normal semua pembolehubah diwakili (sama ada diri mereka sendiri atau penafiannya), dan dalam setiap konjungsi individu atau disjungsi mana-mana pembolehubah muncul tepat sekali (sama ada dirinya atau penafiannya), maka bentuk ini dipanggil bentuk normal sempurna (SDNF atau SCNF). Contoh: Biarkan fungsi tiga pembolehubah f(x,y,z) diberikan.
1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ialah DNF yang sempurna.
2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) ialah CNF yang sempurna.
3. (x ∨ y) ⋅ (x ∨ z) bukanlah CNF yang sempurna, kerana sebagai contoh, jumlah pertama tidak termasuk pembolehubah z.
4. xÿyÿz ialah DNF yang sempurna. Teorem 2.2.1.
1. Mana-mana fungsi Boolean yang tidak sama dengan sifar hanya mempunyai satu SDNF, sehingga lokasi istilah.
2. Mana-mana fungsi Boolean yang tidak sama dengan 1 hanya mempunyai satu SCNF, sehingga lokasi istilah.
Kami akan membuktikan teorem secara konstruktif, sebagai penyelesaian kepada masalah berikut: Menggunakan jadual kebenaran ini, bina SDNF.
Mari kita pertimbangkan penyelesaian menggunakan contoh fungsi f(x,y,z) yang diberikan dalam jadual (Jadual 2.2) untuk n=3.
Contoh 2.2.1. Menggunakan jadual kebenaran ini (Jadual 2.2), bina SDNF.
Jadual 2.2
| x | y | z | asas kata hubung |
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 |
Kata sendi asas (atau juzuk_1) termasuk dalam jadual sepadan dengan set sifar tertentu dan yang mengambil pembolehubah x,y,z. Juzuk sedang dibina_ 1 mengikut peraturan berikut: pembolehubah dimasukkan dalam produk itu sendiri jika ia mengambil nilai 1 pada set tertentu, jika tidak, penolakannya disertakan dalam produk. Jadi, sebagai contoh, pada set (0,0,1) pembolehubah x,y mengambil nilai 0 dan oleh itu penolakan mereka dimasukkan ke dalam produk, dan pembolehubah z mengambil nilai 1 dan oleh itu dimasukkan ke dalam produk itu sendiri . Untuk set tertentu (0,0,1), konstituen_1 adalah sama dengan x ⋅ y ⋅ z .
Jelas sekali, kata sendi x ⋅ y ⋅ z adalah sama dengan 1 sahaja pada set
(0,0,0), dan x ⋅ y ⋅ z ialah 1 pada set (0,0,1), dsb. (lihat jadual). Seterusnya, ambil perhatian bahawa penceraian dua kata hubung asas adalah sama dengan 1 pada dua set tepat yang sepadan dengan kata hubung asas ini. Sebagai contoh, fungsi x ⋅ y ⋅ z¤x ⋅ y ⋅ z adalah sama dengan 1 sahaja pada dua set - (0,0,0) dan (0,0,1), dan pada semua set lain ia adalah sama dengan 0. Begitu juga, pemecahan tiga kata hubung asas adalah sama dengan 1 pada tepat tiga set yang sepadan dengan kata hubung asas ini, dsb.
Itu. kita mendapatkan peraturan: untuk membina SDNF anda harus memilih baris di mana fungsinya adalah sama dengan 1, dan kemudian mengambil percabaran kata sendi utama yang sepadan, kami memperoleh SDNF yang dikehendaki. Jadi untuk contoh kita, kita mempunyai x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Tugasan. Menggunakan jadual kebenaran ini, bina SCNF.
Perlembagaan_0 untuk set sifar dan satu (yang mengambil pembolehubah x,y,z) dibina seperti berikut: pembolehubah dimasukkan dalam percanggahan itu sendiri jika ia mengambil nilai pada set ini 0 , jika tidak, kerja itu termasuk penolakannya.
Peraturan untuk membina SKNF: anda harus memilih baris yang fungsinya sama dengannya 0 , dan kemudian ambil kata hubung juzuk yang sepadan_0. Hasilnya ialah SCNF yang diingini. Jadi untuk contoh kita, kita mempunyai f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Komen. Untuk membina fungsi CNF yang sempurna f, sudah cukup untuk membina DNF yang sempurna untuk fungsi f, dan kemudian
Mari kita bina SCNF untuk contoh kita berdasarkan kenyataan itu. 1. Kami membina SDNF untuk penafian.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Kami menggunakan undang-undang 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 == y == y ) ⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .
Kaedah yang diterangkan untuk mencari SDNF (dan SCNF) menggunakan jadual kebenaran selalunya lebih intensif buruh daripada algoritma berikut.
1. Untuk mencari SDNF formula ini Kami mula-mula mengurangkan kepada DNF.
2. Jika beberapa kata sendi K (iaitu K ialah hasil darab beberapa pembolehubah tertentu atau penolakannya) tidak termasuk, katakan, pembolehubah y, maka kita menggantikan kata hubung ini dengan formula setara K&(y ∨ y) dan, menggunakan undang-undang pengagihan, kami membentangkan formula yang terhasil kepada DNF; jika terdapat beberapa pembolehubah yang hilang, maka bagi setiap pembolehubah itu kita tambahkan formula yang sepadan bagi bentuk (y ∨ y) kepada kata hubung.
3. Jika DNF yang terhasil mengandungi beberapa juzuk yang sama bagi unit, maka kami tinggalkan hanya satu daripadanya. Hasilnya ialah SDNF.
Komen: Untuk membina SCNF menjadi klausa yang tidak mengandungi, katakan, pembolehubah di kita menambah formula bentuk y⋅ y, i.e. Kami menggantikan disjung ini dengan formula setara D ∨ y⋅ y dan, menggunakan hukum ke-2 pengagihan.
Contoh 2. 2. 2. Bina SDNF untuk fungsi f menggunakan penjelmaan setara.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ z y ⋅ z ⋅ z y ⋅ ⋅ z ⋅ x y ⋅ z ⋅ x =
BERUndur.
Pengiraan SDNF bukan sahaja mempunyai teori, tetapi juga besar kepentingan praktikal. Sebagai contoh, dalam banyak program moden dengan antara muka grafik untuk mengarang kompleks keadaan logik bentuk visual dalam bentuk jadual digunakan: keadaan ditulis dalam sel, dan sel-sel satu lajur dianggap disambungkan oleh kata hubung, dan lajur dianggap disambungkan oleh percanggahan, iaitu, mereka membentuk DNF (atau sebaliknya, dalam kes ini, CNF diperolehi). Khususnya, ini adalah cara antara muka grafik QBE (Query-byExample) direka bentuk, digunakan untuk merumuskan keadaan logik apabila menanyakan DBMS.
Algoritma 2.2.1. Pembinaan SDNF
Pintu masuk: vektor X: tatasusunan rentetan - pengecam pembolehubah, matriks V: tatasusunan 0..1 daripada semua set nilai pembolehubah yang berbeza,
vektor F: tatasusunan 0..1 nilai fungsi yang sepadan.
Keluar: urutan simbol yang membentuk rekod formula SDNF untuk fungsi tertentu.
f:= salah(tanda kehadiran operan kiri disjunction) untuk i daripada 1kepada 2n buat
jika F[i] = 1 maka jika f kemudian
hasil"¤" (menambah tanda disjungsi pada formula; operator hasil m cetakan
simbol m) lain f:= benar
tamat jika g:= salah(tanda kehadiran operan kiri kata hubung) untuk j daripada 1kepada n lakukan jika g kemudian
hasil"⁄" (menambah tanda konjungsi pada formula)
lain g: = benar
tamat jika jika V (menambah pengecam pembolehubah pada formula
§2.3. Pengecilan DNF dengan kaedah Quine.
Setiap formula ada nombor akhir kejadian pembolehubah. Kejadian pembolehubah merujuk kepada tempat pembolehubah itu menduduki dalam formula. Tugasnya adalah untuk mencari, untuk fungsi Boolean f yang diberikan, DNF yang mewakili fungsi ini dan mempunyai nombor terkecil kejadian pembolehubah.
Jika x ialah pembolehubah logik, dan σœ(0,1) maka ungkapan x σ =xx jika jika σσ== 10 .
dipanggil surat . Konjungsi dipanggil kata hubung huruf. Sebagai contoh, formula x ⋅ y ⋅ z dan x ⋅ y ⋅ x ⋅ x ialah kata hubung . Produk asas ialah kata hubung di mana mana-mana pembolehubah muncul tidak lebih daripada sekali (sama ada dirinya sendiri atau penafiannya).
Formula f1 dipanggil tersirat formula f , jika f1 ialah hasil darab asas dan f 1 ⁄ f = f 1, i.e. iaitu, untuk fungsi yang sepadan dengan formula, ketaksamaan f 1 § f berlaku. F1 tersirat bagi formula f dipanggil ringkas , jika, selepas membuang mana-mana huruf daripada f1, formula tidak diperolehi yang merupakan implikan bagi formula f.
Contoh 2.3.1 . Mari cari semua implikasi dan implikasi mudah untuk formula f=xØy . Terdapat sejumlah 8 produk asas dengan pembolehubah X Dan u. Di bawah, untuk kejelasan, jadual kebenaran mereka diberikan:
| 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 | |||||||
Daripada jadual kebenaran kita membuat kesimpulan bahawa formula x ⋅ y , x ⋅ y , x ⋅ y , x ,y - semua tersirat formula xØy, dan daripada tersirat ini formula x dan y adalah mudah (rumus x ⋅ y, sebagai contoh, bukan tersirat mudah, kerana, dengan membuang huruf y, kita memperoleh tersirat x).
Disingkat DNF dipanggil disjungsi semua implikasi utama bagi formula (fungsi) tertentu .
Teorem 2.3.1. Mana-mana fungsi Boolean yang bukan pemalar 0 boleh diwakili sebagai DNF singkatan.
Dalam Contoh 2.3.1, fungsi yang sepadan dengan formula xØy diwakili oleh formula x ∨ y yang merupakan singkatan DNF.
DNF yang dikurangkan mungkin mengandungi implikasi tambahan, yang pengalihannya tidak mengubah jadual kebenaran. Jika kami mengalih keluar semua implikasi yang tidak diperlukan daripada DNF yang dikurangkan, kami memperoleh DNF yang dipanggil Jalan mati.
Ambil perhatian bahawa perwakilan fungsi sebagai DNF buntu dalam kes am samar-samar. Memilih daripada semua bentuk buntu, borang dengan bilangan kejadian pembolehubah yang paling sedikit memberikan DNF minimum (MDNF).
Pertimbangkan kaedahnya Quina, untuk mencari MDNF yang mewakili fungsi Boolean yang diberikan. Kami mentakrifkan tiga operasi berikut:
1. operasi ikatan penuh : f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;
2. operasi pelekatan separa:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3. operasi serapan asas f ⋅ x σ ∨ f = f , σ ∈ (0,1) .
Teorem 2.3.2(Teorem Quine). Jika, berdasarkan fungsi SDNF, kami melaksanakan semua kemungkinan operasi pelekatan tidak lengkap dan kemudian penyerapan asas, maka hasilnya akan menjadi DNF yang dikurangkan, iaitu, percanggahan semua implikasi mudah.
Contoh 2.3.2. Biarkan fungsi f(x,y,z) diberikan oleh DNF sempurna f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Kemudian, melakukan dalam dua peringkat semua kemungkinan operasi pelekatan yang tidak lengkap, dan kemudian penyerapan asas, kami mempunyai
f 
Oleh itu, DNF yang dipendekkan bagi fungsi f ialah formula y¤x·z.
Dalam amalan, apabila melakukan operasi gam yang tidak lengkap pada setiap peringkat, adalah mungkin untuk tidak menulis istilah yang terlibat dalam operasi ini, tetapi untuk menulis hanya hasil semua kemungkinan gluing dan konjungsi lengkap yang tidak terlibat dalam sebarang gam.
Contoh 2. 3. 3. Biarkan fungsi f(x,y,z) diberikan oleh DNF sempurna f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
Kemudian, melakukan operasi pelekatan dan kemudian penyerapan asas, kita ada
f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z
Untuk mendapatkan DNF minimum daripada DNF yang dikurangkan, matriks Quine digunakan , yang dibina seperti berikut. Tajuk lajur jadual mengandungi juzuk unit DNF yang sempurna, dan tajuk baris mengandungi implikasi mudah daripada DNF singkatan yang terhasil. Dalam jadual, asterisk menandakan persilangan baris dan lajur yang mana konjungsi dalam pengepala baris disertakan dalam konstituen unit, iaitu pengepala lajur.
Contohnya 2.3.3. Matriks Quine mempunyai bentuk
Dalam DNF buntu, bilangan minimum implikasi mudah dipilih, yang disjunksinya mengekalkan semua juzuk unit, iaitu, setiap lajur matriks Quine mengandungi asterisk di persimpangan dengan baris yang sepadan dengan salah satu daripada implikasi terpilih. DNF buntu yang mempunyai bilangan kejadian pembolehubah terkecil dipilih sebagai DNF minimum.
Dalam Contoh 2.3.3, menggunakan matriks Quine, kita dapati bahawa DNF minimum bagi fungsi tertentu ialah x ⋅ y ¤ x ⋅ z.
Komen.
gunakan f =f dan undang-undang De Morgan.
§ 2.4. Peta Carnot.
Satu lagi cara untuk mendapatkan formula implikan mudah dengan sebilangan kecil pembolehubah (dan, oleh itu, untuk mencari DNF minimum) adalah berdasarkan penggunaan peta Carnot yang dipanggil.
Peta Carnot ialah jenis khas jadual yang memudahkan proses mencari bentuk minimum dan berjaya digunakan apabila bilangan pembolehubah tidak melebihi enam. Peta Karnaugh untuk fungsi bergantung pada n pembolehubah ialah segi empat tepat dibahagikan kepada 2 n sel. Setiap sel rajah dikaitkan dengan set n-dimensi binari. Nilai fungsi tertentu f dari jadual kebenaran dimasukkan ke dalam petak yang diperlukan, tetapi jika sel sepadan dengan 0, maka ia biasanya kekal kosong.
Dalam jadual 2.4.1. menunjukkan contoh menanda peta Karnaugh untuk fungsi yang bergantung kepada tiga pembolehubah. Empat sel bawah peta sepadan dengan set binari di mana pembolehubah x mengambil nilai 1, empat sel teratas sepadan dengan set di mana pembolehubah x mengambil nilai 0. Empat sel yang membentuk separuh kanan peta sepadan dengan set di mana pembolehubah y; mengambil nilai 1, dsb. Dalam jadual 2.4.2. Penandaan peta Karnaugh untuk n=4 pembolehubah ditunjukkan.
Untuk membina DNF yang minimum, kami melakukan prosedur gluing "1". Nilai "1" yang melekat bersama sepadan dengan sel jiran, i.e. sel hanya berbeza dalam nilai satu pembolehubah (oleh perwakilan grafik dipisahkan secara menegak atau garis mendatar mengambil kira kedekatan sel ekstrem yang bertentangan).
Proses melekatkan "1" adalah untuk menggabungkan sel tunggal peta Karnaugh ke dalam kumpulan, dan peraturan berikut mesti dipatuhi;
1. Bilangan sel yang termasuk dalam satu kumpulan mesti dinyatakan sebagai gandaan 2, i.e. 2 m di mana m=0,1,2,...
2. Setiap sel yang termasuk dalam kumpulan 2 m sel mesti mempunyai m sel jiran dalam kumpulan itu.
3. Setiap sel mesti tergolong dalam sekurang-kurangnya satu kumpulan.
4. Setiap kumpulan hendaklah memasukkan bilangan maksimum sel, i.e. tiada kumpulan harus terkandung dalam kumpulan lain.
5. Bilangan kumpulan hendaklah minimum.
Fungsi baca f mengikut kumpulan gluing dijalankan seperti berikut: pembolehubah yang menjimatkan nilai yang sama dalam sel-sel kumpulan gluing, mereka masuk ke dalam konjungsi, dan nilai 1 sepadan dengan pembolehubah itu sendiri, dan nilai 0 sepadan dengan penafian mereka.
Kami membentangkan templat yang membantu membina liputan 1 (kami menganggap pembolehubah adalah sama, tetapi kami tidak akan menulisnya). Untuk memudahkan tatatanda, kami tidak akan menandakan pembolehubah, walaupun kami akan mengekalkan sebutannya seperti dalam jadual 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 |
Contoh 2.4.1. Bina MDNF.
Mula-mula kita lihat sama ada terdapat sebarang salutan_ 1 daripada 16 sel yang meliputi sekurang-kurangnya satu terbongkar 1. Tiada penutup sedemikian. Kami beralih kepada penutup 8 sel. Mari lihat jika terdapat penutup 1 daripada 8 sel yang meliputi sekurang-kurangnya satu 1 yang tidak bertutup. Tiada penutup sedemikian. Kami beralih kepada penutup 4 sel. Mari kita lihat jika terdapat penutup 1 daripada 4 sel yang meliputi sekurang-kurangnya satu 1 yang tidak bertutup. Terdapat dua penutup sedemikian. Kami beralih kepada penutup 2 sel. Hanya terdapat satu salutan sedemikian. Oleh itu, semua 1 telah dilindungi. Seterusnya, mari lihat sama ada kita boleh mengeluarkan beberapa penutup supaya semua unit kekal dilindungi. Pada akhirnya kita menulis MDNF: f =x⋅z∨y⋅w∨y⋅z⋅w.
Komen. Untuk membina CNF minimum bagi fungsi f, sudah cukup untuk membina DNF minimum untuk fungsi f, dan kemudian
gunakan f =f dan undang-undang De Morgan.
Bab III. Algebra Zhegalkin.
Set fungsi Boolean yang ditakrifkan dalam asas Zhegalkin S4=(∆,&,1) dipanggil algebra Zhegalkin.
Sifat asas.
1. komutatif
H1∆H2=H2∆H1, H1&H2=H2
2. pergaulan
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)
3. pengagihan
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. sifat pemalar H&1=H, H&0=0, H∆0=H;
5. H∆H=0, H&H=H.
Penyata 3.1.1. Semua fungsi Boolean lain boleh dinyatakan melalui operasi algebra 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.
Definisi. Polinomial Zhegalkin (modul polinomial 2) bagi n pembolehubah x 1 ,x 2 ,…,x n ialah ungkapan bentuk c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn, di mana pemalar dengan k boleh mengambil nilai 0 atau 1.
Jika polinomial Zhegalkin tidak mengandungi produk pembolehubah individu, maka ia dipanggil linear (fungsi linear).
Contohnya, f=x∆yz∆xyz dan f1=1∆x∆y∆z ialah polinomial, yang kedua ialah fungsi linear.
Teorem 3.1.1. Setiap fungsi Boolean diwakili dalam bentuk polinomial Zhegalkin dengan cara yang unik.
Mari kita kemukakan kaedah utama untuk membina polinomial Zhegalkin daripada fungsi tertentu.
1. Kaedah pekali tidak pasti. Biarkan P(x 1 ,x 2 ,…,x n) ialah polinomial Zhegalkin yang diingini yang melaksanakan fungsi yang diberi f(x 1 ,x 2 ,…,xn). Jom tulis dalam borang
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 .
Mari cari pekali dengan k Untuk melakukan ini, kita tetapkan pembolehubah x 1 , x 2 ,…, x n nilai secara berurutan daripada setiap baris jadual kebenaran. Hasilnya, kita memperoleh sistem 2 n persamaan dengan 2 n tidak diketahui, mempunyai keputusan sahaja. Setelah menyelesaikannya, kita dapati pekali polinomial P(x 1 ,x 2 ,…,xn).
2. Kaedah berdasarkan mengubah formula ke atas satu set penghubung ( ÿ,&}. Bina formula tertentu Ф di atas set penyambung (Ÿ,&), merealisasikan fungsi yang diberi f(x 1 ,x 2 ,…,x n). Kemudian gantikan di mana-mana subformula bentuk A dengan A∆1, buka kurungan menggunakan hukum pengagihan (lihat sifat 3), dan kemudian gunakan sifat 4 dan 5.
Contoh 3.1.1. Bina polinomial Zhegalkin untuk fungsi f(x,y)=xØy.
Penyelesaian. 1 . (kaedah pekali tidak ditentukan). Mari kita tulis polinomial yang diperlukan dalam bentuk
P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Menggunakan jadual kebenaran
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| xØy | 1 | 1 | 0 | 1 |
kita dapati bahawa 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
Dari mana kita secara konsisten dapati, c 0 =1, c 1 =1, c 2 =0, c 12 =1. Oleh itu xØy=1∆x∆xy (bandingkan dengan pernyataan 3.1).
2.(Kaedah penukaran formula.) Kami ada
x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
Ambil perhatian bahawa kelebihan algebra Zhegalkin (berbanding dengan algebra lain) ialah pengiraan logik, yang memungkinkan untuk melakukan transformasi fungsi Boolean dengan agak mudah. Kelemahannya berbanding dengan algebra Boolean ialah kerumitan formula.
Bab IV. Kenyataan. Predikat.
§4.1. Kenyataan.
Apabila membina algebra logik, kami menggunakan pendekatan berfungsi. Walau bagaimanapun, adalah mungkin untuk membina algebra ini secara konstruktif. Pertama, takrifkan objek kajian (penyataan), perkenalkan operasi pada objek ini dan kaji sifatnya. Mari kita berikan definisi formal.
Dengan berkata jom telefon ayat deklaratif mengenai yang mana seseorang boleh dengan jelas mengatakan sama ada ia benar (nilai I atau 1) atau palsu (nilai L atau 0) pada masa tertentu. Contohnya, "5 ialah nombor perdana", "Kekunci Esc ditekan", dsb. Menggunakan penghubung "tidak", "dan", "atau", "jika,... maka", "jika dan hanya jika" (ia sepadan dengan operasi "Ÿ", "&", "¤", "Ø" , “~” » sewajarnya), pernyataan (ayat) yang lebih kompleks boleh dibina. Beginilah cara algebra proposisi dibina.
Untuk memudahkan rakaman pernyataan kompleks, keutamaan penghubung diperkenalkan: “Ÿ”, “&”, “¤”, “Ø”, “~”, yang membantu untuk menghilangkan kurungan yang tidak perlu.
Kami memanggil penyataan mudah pembolehubah proposisi.
Mari kita perkenalkan konsep formula.
1. Pembolehubah usul ialah formula.
2. Jika A, B ialah formula, maka ungkapan ŸA, A⁄B, A¤B, AØB, A~B ialah formula.
3. Rumus hanyalah ungkapan yang dibina mengikut perenggan 1 dan 2.
Formula yang mengambil nilai DAN untuk semua nilai pembolehubah proposisi dipanggil tautologi (atau secara amnya sah), dan formula yang mengambil nilai A untuk semua nilai pembolehubah proposisi dipanggil bertentangan (atau mustahil)
Perihalan sifat algebra proposisi adalah serupa dengan perihalan fungsi yang sepadan dalam algebra Boolean, dan kami meninggalkannya.
§4.2. Predikat. Operasi logik pada predikat.
Subjek kajian dalam bab ini akan menjadi predikat - pemetaan set arbitrari ke dalam set pernyataan. Sebenarnya, kita sedang membuat peralihan kepada tahap baru abstraksi, peralihan jenis yang dibuat di sekolah - daripada aritmetik nombor nyata kepada algebra fungsi berangka.
Definisi 2.1 Biarkan x 1 ,x 2 ,…,xn menjadi simbol pembolehubah sifat arbitrari. Kami akan memanggil pembolehubah ini pembolehubah subjek. Biarkan set pembolehubah (x 1 ,x 2 ,…,x n) tergolong dalam set M=(M1,M2,…Mn), yang akan kita panggil kawasan subjek (iaitu x i œM i, di mana Mi dipanggil domain takrif pembolehubah xi). Predikat lokaliti n (predikat tempat n) ditakrifkan pada bidang subjek M, ialah fungsi logik yang mengambil sama ada nilai DAN atau nilai L.
Contoh 4.2.1. D(x1,x2) = “Nombor asli x1 dibahagikan (tanpa baki) dengan nombor asli x2.” - predikat dua tempat yang ditakrifkan pada set pasangan nombor asli M=NäN. Jelas sekali, D(4,2) = Dan, D(3,5) = 0.
Contoh 4.2.2. Q(x) ==“x 2<-1, хœR» - одноместный предикат, определенный на множестве nombor nyata M=R. Adalah jelas bahawa Q(1) = А, Q(5) = А, dan secara amnya predikat Q(x) adalah sama palsu, i.e.
Q(x) = А untuk semua xœR.
Contoh 4.2.3. B(x,y,z) = "x 2 +y 2 Predikat P yang ditakrifkan pada M dipanggil sama benar jika ia mengambil nilai DAN untuk sebarang nilai pembolehubah subjek; Predikat P dipanggil identik palsu jika ia mengambil nilai A untuk sebarang nilai pembolehubah subjek. Predikat Q daripada Contoh 4.2.2. adalah sama palsu. Oleh kerana predikat ialah fungsi dengan nilai dalam satu set pernyataan di mana operasi logik diperkenalkan, operasi ini ditakrifkan secara semula jadi untuk predikat. Biarkan P dan Q adalah predikat yang ditakrifkan pada M. Kemudian 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) Predikat P dan Q, ditakrifkan pada M dipanggil setara (tulis P=Q) jika P(x 1 ,x 2 ,…,xn)=Q(x 1 ,x 2 ,…,xn) untuk sebarang set (x 1 ,x 2 ,…, x n )
pembolehubah subjek daripada M .
Teorem 4.2.1 Set predikat n-ary yang ditakrifkan pada M membentuk algebra predikat Boolean. Oleh itu, kesetaraan asas adalah sah untuk mereka (lihat §1.6). Biarkan P(x 1 ,x 2 ,…,xn) menjadi predikat n-ary yang ditakrifkan pada M. Mari kita betulkan x i = a. Mari kita takrifkan predikat (n-1)-ary Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) seperti berikut: Q(x 1 ,x 2 ,…,xk-1,xk +1, xn)=P(x 1 ,x 2 ,…,xk1, a,xk+1,xn). Mereka mengatakan bahawa predikat Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) diperoleh daripada predikat P(x 1 ,x 2 ,…,xn) dengan menetapkan nilai i- pembolehubah ke: x i = a
. Definisi
4.3.1
. Biarkan P(x) ialah predikat unari. Marilah kita kaitkan dengannya satu pernyataan yang ditandakan “xP(x) (baca “untuk mana-mana x P(x)”), yang benar jika dan hanya jika P(x) ialah predikat yang sama benar Pernyataan “xP(x) dikatakan , bahawa ia diperoleh daripada predikat P dengan melampirkan pengkuantiti universal di atas pembolehubah x. Definisi 4.3.2. Biarkan P(x) ialah predikat unari. Mari kita kaitkan dengan pernyataan yang dilambangkan $xP(x) (baca "ada x P(x)"), yang palsu jika dan hanya jika P(x) ialah predikat palsu yang serupa. Pernyataan $xP(x) dikatakan diperoleh daripada predikat P dengan melampirkan pengkuantiti maujud pada pembolehubah x. Nota 1. Simbol " dan $ untuk pengkuantiti ialah huruf Latin terbalik A dan E, yang merupakan huruf pertama dalam perkataan Inggeris Semua- Semua, wujud- wujud. Nota 2. Pernyataan boleh dianggap sebagai predikat yang tidak mengandungi pembolehubah, iaitu predikat 0-tempat (atau predikat mana-mana lokaliti). Biarkan P(x 1 ,x 2 ,…,xn) menjadi predikat n-ary yang ditakrifkan pada M. Mari kita betulkan di dalamnya nilai-nilai pembolehubah x 1 ,x 2 ,…,x k-1 ,x k +1 ,x n . Kami melampirkan pengkuantiti universal (kewujudan) pada predikat unary Q(x k) yang terhasil dan mendapatkan pernyataan. Oleh itu, satu set tetap nilai pembolehubah x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n dikaitkan dengan pernyataan menggunakan pengkuantiti kesejagatan (kewujudan). Predikat (n-1)-ary bagi pembolehubah x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n dikatakan diperoleh daripada predikat asal P(x 1 ,x 2 ,…, x n) dengan menambah kesejagatan pengkuantiti (kewujudan) dalam pembolehubah kth. Predikat ini dilambangkan: “x kepada P(x 1 ,x 2 ,…,x n) ($x kepada P(x 1 ,x 2 ,…,x n) Mengenai pembolehubah ke-k (yang tidak wujud lagi)). mereka mengatakan bahawa ia terikat dengan pengkuantiti kesejagatan (kewujudan). Contoh 4.3.1. Biarkan D(x1,x2) = "Nombor asli x1 boleh dibahagikan (tanpa baki) dengan nombor asli x2." - predikat dua tempat. Mari kita berikan pengkuantiti berturut-turut kepada pembolehubahnya. Ia adalah jelas bahawa 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. Oleh itu (dengan membandingkan 7 dan 8 dalam contoh terakhir) kami membuktikan teorem: Lazimnya, penghubung dan pengkuantiti disusun mengikut keutamaan seperti berikut: Ÿ, ", $, &, ¤, Ø, ~. Teorem 4.3.1. Pengkuantiti bertentangan, secara amnya, jangan berulang-alik. Teorem 4.3.2.(kesetaraan asas yang mengandungi pengkuantiti) Kesetaraan berikut berlaku: 1. Undang-undang De Morgan ∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x) 2. Komutatif ∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y) 3. Pengagihan ∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x) 4. Had ke atas tindakan pengkuantiti ∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y) 5. Bagi mana-mana predikat dua tempat ∃y∀xP(x,y) →∀x∃yP(x,y) =1 Teori formal(atau kalkulus)
Y- Ini: 1 set A
watak membentuk abjad
;
1.
sekumpulan F
perkataan dalam abjad A, F
à A
yang dipanggil formula
;
3. subset B
formula, B
à F
,
yang dipanggil aksiom; 4. banyak perhubungan R
pada satu set formula yang dipanggil peraturan inferens. Banyak watak A
mungkin terhingga atau tidak terhingga. Biasanya, untuk membentuk simbol, set huruf terhingga digunakan, yang, jika perlu, nombor asli ditetapkan sebagai indeks. Banyak formula F
biasanya diberikan dengan definisi induktif, contohnya melalui tatabahasa formal. Sebagai peraturan, set ini tidak terhingga. set A
Dan F
tentukan secara kolektif bahasa
,
atau tandatangan
,
teori formal. Banyak aksiom B
mungkin terhingga atau tidak terhingga. Jika set aksiom adalah tak terhingga, maka, sebagai peraturan, ia ditentukan menggunakan set terhingga skema aksiom dan peraturan untuk menghasilkan aksiom tertentu daripada skema aksiom. Banyak peraturan inferens R
, sebagai peraturan, sudah tentu. Jadi, kalkulus Y ada empat (A, F, B, R)
. Dengan terbitan dalam kalkulus Y ialah jujukan formula F 1 ,F 2 ,…,Fn supaya bagi mana-mana k (1§k§n) formula Fk ialah sama ada aksiom bagi kalkulus Y atau akibat langsung daripada sebarang formula sebelumnya yang diperolehi oleh peraturan inferens . Formula G dipanggil teorem kalkulus Y (boleh terbit dalam Y atau boleh dibuktikan dalam Y) jika terdapat kesimpulan F 1 ,F 2 ,…,F n ,G yang dipanggil terbitan formula G atau bukti bagi teorem G. Ini ditulis seperti berikut: F 1,F 2,…,F n + G. Kalkulus Y dipanggil konsisten, jika tidak semua formulanya boleh dibuktikan. Takrif ketekalan lain boleh diberikan: Kalkulus dipanggil konsisten jika formula F dan ŸF (penafian F) tidak boleh ditolak secara serentak di dalamnya. Kalkulus Y dipanggil lengkap(atau memadai) jika setiap pernyataan benar M sepadan dengan teorem teori Y
. Teori formal Y dipanggil boleh diputuskan, jika terdapat algoritma yang, untuk sebarang formula teori, menentukan sama ada formula ini adalah teorem teori Y atau tidak. Menggunakan konsep kalkulus formal, kami mentakrifkan kalkulus proposisi (PS). Abjad IW terdiri daripada 1. surat A, B, Q, R, P dan lain-lain, mungkin dengan indeks (yang dipanggil pembolehubah proposisi), 2. simbol logik(ligamen) Ÿ, &, ¤, Ø, 3. bantu watak
(,). Banyak formula IV ditentukan secara induktif: 1. semua pembolehubah proposisi adalah formula IV; 2. jika A, B ialah formula IV ,
toŸA, A⁄B, A¤B, AØB - formulaIV ;
3. ungkapan ialah formula IV jika dan hanya jika ini boleh diwujudkan menggunakan titik "1" dan Oleh itu, sebarang formula IV dibina daripada pembolehubah proposisi menggunakan penghubung Ÿ, ⁄, ¤, Ø. Pada masa hadapan, apabila menulis formula, kami akan meninggalkan beberapa kurungan, menggunakan konvensyen yang sama seperti dalam bab sebelumnya. Aksiom IV ialah formula berikut (untuk sebarang formula 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); Formula ini dipanggil skema aksiom IV .
Apabila menggantikan formula khusus ke dalam mana-mana skema, kes khas skema aksiom diperolehi. Peraturan inferens dalam IE terdapat peraturan kesimpulan (modus ponens): jika A dan AØB adalah formula terbitan, maka B juga boleh terbitan Secara simbolik ia ditulis seperti ini: A, A B →
B
. Sebagai contoh, jika pernyataan A⁄B dan A⁄BØ(AØC) boleh ditolak, maka pernyataan AØC juga boleh ditolak mengikut peraturan inferens. Formula G dikatakan boleh ditolak daripada formula F 1 ,F 2 ,…,F n (ditandakan F 1 ,F 2 ,…,F n +G) jika terdapat urutan formula F 1 ,F 2 ,… ,F k ,G , di mana sebarang formula adalah sama ada aksiom, atau tergolong dalam senarai formula F 1,F 2,...,F n (dipanggil hipotesis), atau diperoleh daripada formula sebelumnya mengikut peraturan inferens. Kebolehterbitan formula G daripada “ (ditandakan dengan +G) adalah bersamaan dengan fakta bahawa G ialah teorem IV. Contoh 5.2.1. Mari kita tunjukkan bahawa formula AØA boleh diterbitkan dalam IV. Untuk melakukan ini, kami akan membina terbitan formula ini: 1) dalam aksiom 2, gantikan B dengan AØA, C dengan A. Kami mendapat aksiom (AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA)); 2) dalam aksiom 1 kita gantikan B dengan A. Kami memperoleh AØ(AØA); 3) dari 1 dan 2 mengikut modus ponens kita simpulkan (AØ((AØA)ØA))Ø(AØA); 4) dalam aksiom 1 kita gantikan B dengan AØA. Kami mendapat AØ((AØA)ØA); 5) daripada perenggan. 3 dan 4, mengikut peraturan inferens, + AØA adalah benar. Teorem 5.2.1. 1. Jika F 1 ,F 2 ,…,Fn,A,B ialah formula IV, Г=(F 1 ,F 2 ,…,Fn), Г+A, maka Г,B+A. (anda boleh menambah bilangan hipotesis). 2. Jika dan hanya jika F 1 ,F 2 ,…,F n +A, apabila F 1 ⁄F 2 ⁄…⁄F n +A (pengurangan banyak hipotesis kepada satu hipotesis). Teorem 5.3.1. (teorem potongan) Jika Г,B+A, maka Г+BØA, dengan Г ialah set beberapa formula Г=(F 1 ,F 2 ,…,F n ). Akibat 5.3.1. Jika dan hanya jika F 1 ,F 2 ,…,F n +A, bila Bukti. Biarkan F 1 ,F 2 ,…,F n +A. Kemudian, menggunakan teorem potongan, kita mempunyai F 1 ,F 2 ,…,F n-1 +F n ØA. Begitu juga F 1 ,F 2 ,…,F n-2 +F n 1Ø(F n ØA), dll. Meneruskan proses bilangan kali yang diperlukan, kita mendapat F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…) Untuk membuktikan kecukupan, andaikan bahawa +B, dengan B=F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Mari gunakan Teorem 5.2.1., item 1: F 1 +B .
Mengikut peraturan kesimpulan, kita memperoleh F 1 + (F 2 Ø…Ø(F n-1 Ø(F n ØA))…), Kemudian selepas n langkah kita mempunyai F 1 ,F 2 ,…,F n +A . Oleh itu, terima kasih kepada Corollary 5.3.1., menyemak kebolehtelapan formula A daripada formula F 1,F 2,…,F n, dikurangkan kepada menyemak kebolehbuktian formula F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Ingat bahawa formula A dipanggil identik benar (atau tautologi) jika nilai formula A adalah sama dengan satu untuk sebarang set nilai pembolehubah proposisi. Teorem berikut mengurangkan pengesahan kebolehbuktian formula kepada pengesahan kebenaran yang sama. Teorem 5.3.2. (tentang kesempurnaan). Formula A boleh dibuktikan jika dan hanya jika A adalah sama benar (tautologi): +A ‹ A-tautologi. Oleh itu, untuk menentukan sama ada formula boleh dibuktikan, cukup untuk menyusun jadual kebenarannya. Seperti yang diketahui, terdapat algoritma yang berkesan untuk membina jadual kebenaran, dan, oleh itu, IV boleh diselesaikan. Contoh 5.3.1. Mari kita buktikan bahawa P+P. Dengan teorem potongan, ini bersamaan dengan +(PØP). Sebaliknya, mengikut teorem kesempurnaan, sudah cukup untuk membuktikan bahawa (РØР) ialah tautologi. Menyusun jadual kebenaran untuk formula (РØР) ,
Kami yakin bahawa (РØР) adalah sama benar dan, oleh itu, boleh dibuktikan. Teorem 5.3.3. (mengenai konsistensi). Kalkulus IW adalah konsisten. Bukti. Mengikut teorem kesempurnaan, sebarang formula yang tidak sama benar tidak boleh dibuktikan dalam IW. Sebagai contoh, formula sedemikian ialah formula A⁄(ŸA). Set formula Г dipanggil kontroversi
,
jika Г+А⁄(ŸА) .
Jika Γ ialah set formula yang bercanggah, kita akan menandakan fakta ini dengan Γ+. Kenyataan
5.3.1.
Formula A boleh ditolak daripada set formula Г jika dan hanya jika set Г»(ŸA) adalah bercanggah. Pembuktian teorem automatik adalah asas pengaturcaraan logik, kecerdasan buatan dan trend moden lain dalam pengaturcaraan. Secara amnya, mungkin tidak ada algoritma yang, berdasarkan formula A sewenang-wenangnya, seseorang boleh menentukan, selepas beberapa langkah terhingga, sama ada A boleh disimpulkan dalam kalkulus Y atau tidak. Walau bagaimanapun, untuk beberapa teori formal ringkas (contohnya, kalkulus proposisi) dan beberapa kelas formula ringkas (contohnya, kalkulus predikat gunaan dengan satu predikat unari), algoritma untuk pembuktian teorem automatik diketahui. Di bawah, menggunakan contoh kalkulus proposisi, kami menggariskan asas kaedah resolusi - kaedah klasik dan pada masa yang sama popular untuk membuktikan teorem secara automatik. Ingat bahawa jika x ialah pembolehubah logik, dan σœ(0,1) maka ungkapan itu x σ = xx jika jika σσ == 10 atau x σ = 10 jika jika x x =≠σσ , dipanggil surat. Huruf x dan Ÿx dipanggil bertentangan.
Konjungsi dipanggil kata hubung huruf. disjunct disebut penceraian huruf. Biarkan D 1 = B 1 ∨ A, D 2 = B 2 ∨ A menjadi klausa. Klausa B 1 ¤B 2 dipanggil penyelesai klausa D 1 dan D 2 dengan huruf A dan dilambangkan dengan res A (D 1 ,D 2). Penyelesai bagi klausa D 1 dan D 2 ialah penyelesai oleh beberapa huruf dan dilambangkan dengan res(D 1 ,D 2). Jelas sekali res(A,ŸA)=0. Sesungguhnya, kerana A=A¤0 dan ŸA=ŸA¤0, kemudian res(A,ŸA)=0¤0=0. Jika klausa D 1 dan D 2 tidak mengandungi aksara yang berbeza, maka ia tidak mempunyai pelarut. Contoh 5.5.1. Jika D 1 =A¤B¤C, D 2 = A ∨ B ∨ Q, maka 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) tidak wujud. Penyata 5.5.1. Jika res(D 1 ,D 2) wujud, maka D 1 ,D 2 + res(D 1 ,D 2). Biarkan S=(D 1 ,D 2 ,…,Dn) ialah set klausa. Urutan formula F 1 ,F 2 ,…,F n dipanggil terbitan tetap daripada S jika bagi setiap formula F k satu daripada syarat dipenuhi: 2. terdapat j, k
Teorem 5.5.1.
(tentang kesempurnaan kaedah resolusi). Satu set klausa S adalah bercanggah jika dan hanya jika terdapat kesimpulan tegas daripada S yang berakhir dengan 0. Ambil perhatian bahawa kaedah peleraian boleh digunakan untuk menyemak kebolehterangan formula F daripada set formula F 1,F 2,…,F n yang diberikan. Sesungguhnya, keadaan F 1 ,F 2 ,…,F n +F adalah bersamaan dengan keadaan F 1 ,F 2 ,…,F n ,ŸF+ (banyak formula bercanggah), yang seterusnya bersamaan dengan keadaan Q+, di mana Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Mari kita kurangkan formula Q kepada CNF: Q=D 1 ⁄D 2 ⁄...⁄Dm, kemudian Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Oleh itu, tugas untuk menyemak kebolehtelapan bagi F 1 ,F 2 ,…,F n +F turun untuk menyemak ketidakkonsistenan set klausa S=(D 1 ,D 2 ,...,D m ), yang adalah bersamaan dengan kewujudan kesimpulan yang tegas 0 daripada S. Contoh 5.5.2. Semak nisbah AØ(BØC), CDØE, ŸFØD&(Ÿ)E + AØ(BØF) menggunakan kaedah resolusi. Mengikut pernyataan 5.3.1. perlu menyemak untuk ketidakkonsistenan banyak formula S = (AØ(BØC), CDØE, ŸFØD&(Ÿ)E, Ÿ(AØ(BØF))). Kami membentangkan semua formula dari. S kepada KNF: 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) . Oleh itu, kita memperoleh satu set klausa S = (A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F) Mari kita bina kesimpulan tegas dari S berakhir dengan 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 . Jadi, kami membuat kesimpulan bahawa formula AØ(BØF) boleh disimpulkan daripada set formula AØ(BØC), CDØE, ŸFØD&(Ÿ)E. Ambil perhatian bahawa kaedah penyelesaian adalah mencukupi untuk menemui kemungkinan kepuasan bagi set klausa S yang diberikan. Untuk melakukan ini, mari kita masukkan dalam set S semua klausa yang diperoleh oleh terbitan resolusi daripada S. Daripada teorem mengenai kesempurnaan kaedah resolusi ia mengikuti Akibat 5.5.1. Jika satu set klausa S mengandungi pelarut semua unsurnya, maka S adalah memuaskan jika dan hanya jika 0–S. Ciri ciri kemodenan ialah penggunaan komputer yang meluas dalam menyelesaikan masalah (tugas) dalam pelbagai bidang aktiviti manusia. Walau bagaimanapun, masalah itu mesti terlebih dahulu diselesaikan secara algoritma, i.e. preskripsi rasmi mesti diberikan, mengikut mana seseorang boleh mendapatkan keputusan akhir untuk menyelesaikan semua masalah jenis tertentu (ini adalah konsep algoritma yang intuitif, bukan ketat). Sebagai contoh, algoritma untuk mencari pembahagi sepunya terbesar bagi dua nombor asli a, b, seperti berikut: 1) mengembangkan bilangan a oleh faktor utama; 2) ulangi langkah 1 untuk b
Dan pergi ke langkah 3; 3) menyusun hasil darab faktor perdana sepunya daripada pengembangan A Dan b dengan indeks yang sama dengan yang terkecil daripada indeks kemasukan dalam pengembangan. Setelah menganalisis contoh ini, kami perhatikan ciri (sifat) algoritma yang paling penting: 1.
Watak jisim- kebolehgunaan algoritma bukan kepada satu masalah, tetapi kepada kelas masalah. 2.
Kebijaksanaan- pecahan yang jelas kepada peringkat individu (langkah) algoritma. 3.
Determinisme- seperti organisasi peringkat pelaksanaan di mana ia sentiasa jelas bagaimana untuk membuat peralihan dari satu peringkat ke yang lain. 4.
Anggota badan- untuk mendapatkan hasil apabila menggunakan algoritma untuk menyelesaikan masalah tertentu, urutan terhingga langkah algoritma dilakukan: Ambil perhatian bahawa jika kehadiran algoritma itu sendiri berfungsi sebagai bukti kewujudan algoritma, maka untuk membuktikan ketiadaannya adalah perlu untuk mempunyai definisi matematik yang ketat bagi algoritma. Percubaan untuk memformalkan konsep algoritma membawa kepada penciptaan Mesin Turing, sebagai beberapa peranti khayalan yang melaksanakan algoritma. Satu lagi langkah dalam menentukan konsep algoritma ialah penampilan fungsi rekursif ,
sebagai fungsi yang memformalkan konsep algoritma dan melaksanakan konsep intuitif kebolehkiraan. Tidak lama kemudian didapati bahawa set fungsi rekursif bertepatan dengan set fungsi yang boleh dikira pada mesin Turing. Konsep baru yang kemudiannya muncul, mendakwa menjelaskan konsep algoritma, ternyata bersamaan dengan fungsi yang boleh dikira pada mesin Turing, dan oleh itu dengan fungsi rekursif. Hasil perbincangan berterusan tentang apa itu algoritma ialah kenyataan yang kini dipanggil tesis Gereja. tesis gereja. Konsep algoritma, atau kebolehkiraan oleh beberapa peranti mekanikal, bertepatan dengan konsep kebolehkiraan pada mesin Turing (dan oleh itu dengan konsep fungsi rekursif). Dengan kata lain, algoritma ialah proses yang boleh diwakili oleh gambar rajah berfungsi dan dilaksanakan oleh beberapa mesin Turing. Mesin Turing ialah peranti (abstrak) yang terdiri daripada pita, peranti kawalan, dan kepala baca. Pita dibahagikan kepada sel. Setiap sel mengandungi tepat satu aksara daripada abjad luaran
A=(
a 0,
a 1 ,…,
a n). Beberapa simbol (kami akan menandakannya Ÿ
) abjad A dipanggil kosong, dan mana-mana sel pada masa ini mengandungi aksara kosong dipanggil sel kosong (pada masa itu). Pita itu diandaikan berpotensi tidak terhad dalam kedua-dua arah. Peranti kawalan pada setiap saat masa berada dalam beberapa keadaan q j kepunyaan set Q=(q 0 , q 1 ,..., q m )(m=l). Himpunan Q dipanggil abjad dalaman
.
Salah satu daripada syarat ini (biasanya q 0) dipanggil muktamad, dan beberapa yang lain (biasanya q 1) - permulaan. Kepala baca bergerak di sepanjang pita supaya pada bila-bila masa ia mengimbas tepat satu sel pita. Kepala boleh membaca kandungan sel yang diperhatikan dan menulis ke dalamnya dan bukannya simbol yang diperhatikan beberapa simbol baru dari abjad luaran A(mungkin yang sama). Semasa operasi, peranti kawalan, bergantung pada keadaan di mana ia berada dan simbol yang dilihat oleh kepala, mengubah keadaan dalamannya q. Kemudian ia mengeluarkan perintah untuk mencetak aksara tertentu daripada abjad luaran dalam sel yang dipantau A, dan kemudian mengarahkan kepala sama ada kekal di tempatnya, atau gerakkan satu sel ke kanan, atau gerakkan satu sel ke kiri. Apabila dalam keadaan akhir, mesin berhenti berfungsi. Konfigurasi pada pita (atau perkataan mesin) dipanggil himpunan yang dibentuk oleh: 1) urutan a
i (1)
, a
i (2)
,...,a
i(s) aksara daripada abjad luar A, direkodkan dalam sel pita, di mana a
i
(1)
.- simbol yang ditulis dalam sel pertama di sebelah kiri, dsb. (sebarang urutan sedemikian dipanggil dalam satu perkataan), 2) keadaan memori dalaman q r ; 3) nombor k sel yang dirasakan. Kami akan menulis konfigurasi mesin seperti berikut: a ,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) Di sini r- sel yang dilihat diserlahkan sebagai pecahan. Jika mesin, berada dalam keadaan dalaman q i, menerima sel dengan simbol a u, menulis simbol pada sel ini pada masa yang seterusnya a r, masuk ke keadaan dalaman qs dan bergerak di sepanjang pita, kemudian mereka mengatakan bahawa mesin sedang melaksanakan arahan q i a u
Æ
q s a r S, di mana simbol S boleh mengambil salah satu daripada nilai berikut: -1 – alihkan kepala ke kiri; +1 - anjakan kepala ke kanan; 0 - kepala kekal di tempatnya. Senarai semua arahan (quintuple) yang menentukan operasi mesin Turing dipanggil program kereta ini. Program mesin selalunya dinyatakan dalam bentuk jadual. Jadi untuk situasi yang diterangkan di atas dalam jadual di persimpangan garisan a
u dan lajur q i akan berdiri q s a r S(lihat jadual 6.2.1) Jadual 6.2.1. Jika program ini termasuk kereta untuk pasangan (
q i , a u
)
lima hilang, kemudian dalam jadual di persimpangan garisan a u, dan lajur q i sengkang ditambah. Jadi, Mesin Turing adalah, mengikut definisi, kit M=(A,Q,P), Di mana A- abjad luaran, Q- abjad negeri dalaman, P- program. Jika mesin, setelah mula bekerja dengan beberapa perkataan P yang ditulis pada pita, mencapai keadaan akhir, maka ia dipanggil terpakai pada perkataan ini. Hasil kerjanya ialah perkataan yang dirakam pada pita dalam keadaan terakhirnya. Jika tidak, mesin itu dikatakan tidak boleh digunakan untuk perkataan R. Contoh 6.2.1. Mari bina mesin Turing yang menambah nombor asli yang ditulis dalam sistem nombor unari (iaitu, ditulis menggunakan satu simbol |.
Contohnya 5=|||||.). Penyelesaian. Pertimbangkan abjad A
= {|, +, ⁄}. Mesin ditentukan oleh program berikut: Mari kita tuliskan konfigurasi yang timbul secara berurutan semasa pengendalian mesin ini pada perkataan awal ||+ ||| , iaitu 2+3. Di sini, apabila merakam konfigurasi, kami akan menggunakan konvensyen berikut: keadaan di mana mesin berada ditulis dalam kurungan di sebelah kanan di belakang huruf yang diperhatikan. Contoh 6.2.2. Bina mesin Turing yang menggandakan nombor asli yang ditulis dalam sistem nombor unari. Penyelesaian. Kami akan membina mesin yang diperlukan dalam abjad A=(|, α, ⁄). Program untuk mesin sedemikian mungkin kelihatan seperti ini: Mari gunakan mesin yang terhasil pada perkataan ||
. Pengenalan huruf baru α dan penggantian huruf asal |
pada α membolehkan seseorang membezakan yang asal |
dan baharu (ditugaskan) |
. negeri q 1 menyediakan pengganti |
pada α ,
negeri q 2 menyediakan carian untuk α ,
bertujuan untuk menggantikan |
, dan menghentikan mesin dalam kes apabila α tidak dikesan, q 3 memastikan siap |
dalam kes apabila α digantikan oleh |.
Marilah kita bersetuju bahawa dalam perenggan ini 1. set N nombor asli mengandungi 0 (sifar), i.e. N=(0,1,2,3,...); 2. fungsi yang dipertimbangkan f=f(x 1 ,x 2 ,…,x n) ditakrifkan hanya apabila pembolehubah mengambil nilai daripada N, i.e. xiœN; 3. julat nilai fungsi DŒN; 4. fungsi yang dipertimbangkan f=f(x 1 ,x 2 ,…,x n) boleh ditakrifkan sebahagiannya, i.e. tidak ditakrifkan untuk semua set nombor asli. Mari kita perkenalkan dalam pertimbangan fungsi mudah o(x)=0, s(x)=x+1,
Saya m n (x 1 ,..., x n)
=
x m Fungsi ini boleh dikira menggunakan peranti mekanikal yang sesuai (contohnya, mesin Turing). Mari kita tentukan operator yang membina fungsi baharu berdasarkan satu atau lebih fungsi yang diberikan. Operator superposisi. Biarkan fungsi f(x 1 ,x 2 ,…,x k) bagi k pembolehubah dan k fungsi f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n) menjadi diberi n pembolehubah. Superposisi bagi fungsi f,f 1 ,…,f k ialah fungsi j(x 1 ,x 2 ,…,x n)= f(f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n)) Kita katakan bahawa fungsi j diperoleh dengan menggunakan operator superposisi S k+1 pada fungsi f,f 1 ,…,f k , dan tulis j=S k+1 (f,f 1 ,…,f k) Contohnya, S 2 (s, o)=s(o(x)), i.e. fungsi yang sama dengan 1, dan S 2 (s,s)=s(s(x)) ialah fungsi y(x)=x+2. Pengendali rekursi primitif. Biarkan fungsi g(x 1 ,x 2 ,…,x n) dan h(x 1 ,x 2 ,…,x n+2) diberikan. Mari bina fungsi f(x 1 ,x 2 ,…,x n+1) Biarkan nilai x 1 ,x 2 ,…,x n dibetulkan. Kemudian kita andaikan: 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)) Kesamaan ini mentakrifkan fungsi f(x 1 ,x 2 ,…,x n+1) secara unik. Fungsi f dipanggil fungsi yang diperoleh menggunakan operator rekursi primitif R. Tatatanda f=R(g,h) digunakan. Takrifan induktif bagi fungsi (ditunjukkan dalam operator rekursi primitif) adalah perkara biasa dalam matematik. Sebagai contoh, 1) ijazah dengan eksponen semula jadi ditentukan secara induktif: a
0
=1, a n+ 1
=a n
ÿ a
; 2) faktorial: 0!=1, (n+1)!= n!ÿ(n+1), dsb. Definisi. Fungsi yang boleh diperolehi daripada o(x)=0 termudah, s(x)=x+1, I m n (x 1 ,..., x n) = x m dengan menggunakan operator superposisi dan rekursi primitif beberapa kali terhingga dipanggil secara primitif rekursif. Mari kita semak bahawa fungsi u(x,y)=x+y ialah rekursif primitif. Sesungguhnya, kita ada: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Ini ialah skema rekursi primitif, kerana x= I 1 1 (x), dan u(x,y)+1=s(u(x,y))=S 2 (s,u). Di sini g(x)= I 1 1 (x), dan h(x,y,u)=s(u)=S 2 (s, I 3 3). Begitu juga dibuktikan bahawa fungsi m(x,y)=xÿy, d(x,y)=x y (kita andaikan mengikut takrifan 0 0 =1), fakta(x)=x! dan banyak lagi adalah rekursif primitif. Catatan; bahawa fungsi rekursif primitif ditakrifkan di mana-mana (iaitu, ditakrifkan untuk semua nilai hujah mereka). Sesungguhnya, fungsi yang paling mudah o, s, Saya m n ditakrifkan di mana-mana, dan menggunakan superposisi dan pengendali rekursi primitif pada fungsi yang ditakrifkan di mana-mana juga memberikan fungsi yang ditakrifkan di mana-mana. Jadi fungsi seperti = x − y, jika x ≥ y< y f(x,y) tidak wujud jika x tidak boleh secara primitif rekursif. Kami tidak mempunyai hak untuk mempertimbangkan fungsi f(x,y)=x-y di sini, kerana nilai fungsi mestilah nombor asli (oleh itu bukan negatif). Walau bagaimanapun, seseorang boleh mempertimbangkan fungsinya ÷ y = 0x − y ifif x x<≥y.y Mari kita semak bahawa ia adalah rekursif primitif. Mari kita buktikan dahulu bahawa fungsi j(x)=xπ1 ialah rekursif primitif. Sesungguhnya, j(0)=0. j(y+1)=(y+1)π1=y, yang berfungsi sebagai skema rekursi primitif untuk fungsi xπ1. Akhir sekali, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) ialah skema rekursi primitif untuk xπy. Kelas fungsi yang lebih luas daripada fungsi rekursif primitif ialah kelas fungsi rekursif (lihat definisi di bawah). Dalam kesusasteraan fungsi ini juga dipanggil separa rekursif .
Untuk menentukannya, kami memperkenalkan satu lagi pengendali. Operator pengecilan. Biarkan fungsi f(x 1 ,x 2 ,… ,x n ,x n+1) diberikan. Mari betulkan beberapa nilai x 1 ,x 2 ,… ,x n daripada n pembolehubah pertama dan hitung f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1 ), f(x 1 ,x 2 ,… ,x n ,2) dsb. Jika y ialah nombor asli terkecil yang f(x 1 ,x 2 ,… X n ,y)=x n+1 (iaitu nilai 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) semuanya wujud dan tidak sama dengan xn +1), maka kita letakkan g(x 1 ,x 2 ,… X n ,x n+1)=y. Oleh itu, g(x 1 ,x 2 ,… ,x n ,x n+1)=min(y|f(x 1 ,x 2 ,…,x n ,y)=x n+1). Jika demikian y tidak, maka kami menganggap bahawa f(x 1 ,x 2 ,… ,x n ,x n+1) tidak ditakrifkan. Jadi, tiga kes mungkin: 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) wujud dan tidak sama dengan xn +1, dan 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) wujud dan tidak sama dengan xn +1, tetapi f(x 1 ,x 2 ,…,x n ,y) tidak wujud; 3. f(x 1 ,x 2 ,… ,x n ,i) wujud untuk semua iœN dan berbeza daripada xn +1. Jika kes pertama berlaku, maka g(x 1 ,x 2 ,… ,x n ,x n+1)=y, dan jika kes ke-2 atau ke-3, maka g(x 1 ,x 2 ,… ,x n , x n +1) tidak ditakrifkan. Fungsi g yang diperoleh dengan cara ini dikatakan diperoleh daripada f menggunakan operator pengecilan M. Kami menulis g= Mf. Operator pengecilan ialah generalisasi jelas bagi operator fungsi songsang. Generalisasi agak mendalam, kerana fungsi f tidak diperlukan untuk menjadi satu-satu (dalam pembolehubah x n+1) Definisi. Fungsi yang boleh diperolehi daripada yang paling mudah o(x)=0, s(x)=x+1,
Saya m n (x 1 ,..., x n)
= x m menggunakan operator superposisi, rekursi primitif dan operator pengecilan beberapa kali terhingga dipanggil rekursif. Kelas fungsi rekursif adalah lebih luas daripada kelas fungsi rekursif primitif, jika hanya kerana ia mengandungi bukan sahaja fungsi yang ditakrifkan di mana-mana. Mari kita buktikan, sebagai contoh, bahawa fungsi = x − y, jika x ≥ y< y f(x,y) tidak wujud jika x adalah rekursif. Sesungguhnya, f(x,y)=min(z| y+z=x), dan sebelum ini telah ditetapkan bahawa fungsi u(x,y)=x+y adalah rekursif primitif. Fungsi rekursif mencerminkan pemahaman intuitif kami tentang fungsi yang boleh dikira oleh sesetengah peranti mekanikal. Khususnya, ia boleh dikira pada mesin Turing (lihat perenggan sebelumnya). Sebaliknya, setiap fungsi yang boleh dikira pada mesin Turing adalah rekursif. Kami tidak akan menyemak fakta ini, kerana ia akan mengambil terlalu banyak masa dan ruang. Bukti lengkap boleh didapati, sebagai contoh, dalam buku A.I. Maltsev "Algoritma dan Fungsi Rekursif". Ambil perhatian bahawa bukan setiap fungsi hujah semula jadi adalah rekursif, malah bukan setiap fungsi hujah tunggal. Kewujudan fungsi bukan rekursif adalah "sebab matematik" untuk kehadiran masalah yang tidak dapat diselesaikan secara algoritma. Dalam pelbagai cabang matematik terdapat masalah yang tidak dapat diselesaikan secara algoritma, i.e. masalah yang tidak ada algoritma penyelesaian, dan bukan kerana ia belum dicipta, tetapi kerana ia adalah mustahil pada dasarnya. Sudah tentu, algoritma mesti difahami dalam erti kata mesin Turing dan fungsi rekursif. Mari kita rumuskan salah satu masalah ini Masalah berhenti mesin Turing. Mesin Turing ialah objek yang ditakrifkan oleh bilangan parameter yang terhingga. Semua pemetaan separa dari satu set terhingga kepada set yang lain boleh dinomborkan semula dengan cekap. Oleh itu, setiap mesin Turing boleh diberikan nombor (nombor asli). Biarkan T(n) ialah mesin Turing dengan nombor n. Sesetengah mesin yang mula berjalan pada tali pinggang kosong akhirnya berhenti, dan beberapa mesin berjalan selama-lamanya. Masalah timbul: diberi nombor asli n, tentukan sama ada mesin Turing T(n) yang dilancarkan pada pita kosong akan berhenti atau tidak. tugasan ini tidak dapat ditentukan secara algoritma. Iaitu, tiada prosedur automatik ,
bagi setiap n menentukan sama ada mesin T(n) berhenti atau tidak. Ini tidak menghalang kami daripada menentukan untuk mana-mana mesin tertentu sama ada ia berhenti atau tidak. Tiada kaedah yang menyelesaikan masalah ini untuk semua mesin sekaligus .
Memandangkan masalah, bagaimana untuk mencari algoritma yang cekap untuk menyelesaikannya? Dan jika algoritma ditemui, bagaimanakah ia boleh dibandingkan dengan algoritma lain yang menyelesaikan masalah yang sama? Bagaimana untuk menilai kualitinya? Soalan seperti ini menarik minat pengaturcara dan mereka yang terlibat dalam kajian teori pengkomputeran. Terdapat banyak kriteria untuk menilai algoritma. Selalunya, kami akan berminat dengan susunan pertumbuhan masa dan kapasiti memori yang diperlukan untuk menyelesaikan masalah apabila data input meningkat. Kami ingin mengaitkan nombor dengan setiap tugas tertentu, dipanggil saiznya ,
yang akan menyatakan ukuran jumlah data input. Sebagai contoh, saiz masalah pendaraban matriks mungkin saiz terbesar bagi matriks faktor. Masa yang diambil oleh algoritma sebagai fungsi saiz masalah dipanggil kerumitan masa algoritma ini. Tingkah laku kerumitan ini dalam had apabila saiz masalah meningkat dipanggil kerumitan masa asimptotik
.
Begitu juga kita boleh menentukan kerumitan kapasitif dan kerumitan kapasitif asimptotik. Ia adalah kerumitan asimptotik algoritma yang akhirnya menentukan saiz masalah yang boleh diselesaikan oleh algoritma ini. Jika algoritma memproses input saiz n dalam masa cÿn 2 , di mana c -
beberapa pemalar, maka mereka mengatakan bahawa kerumitan masa algoritma ini ialah O(n 2) (baca “of order en square”). Orang akan berfikir bahawa peningkatan besar dalam kelajuan pengkomputeran yang dibawa oleh generasi semasa mesin pengkomputeran digital akan mengurangkan kepentingan algoritma yang cekap. Namun, sebaliknya berlaku. Memandangkan mesin pengkomputeran semakin pantas dan pantas dan kita boleh menyelesaikan masalah yang lebih besar, kerumitan algoritmalah yang menentukan peningkatan saiz masalah yang boleh dicapai apabila kelajuan mesin meningkat. Katakan kita mempunyai lima algoritma A1,A2,…,A5 dengan kerumitan masa berikut: Di sini, kerumitan masa ialah bilangan unit masa yang diperlukan untuk memproses input bersaiz n. Biarkan unit masa menjadi satu milisaat (1sec=1000 milisaat). Kemudian algoritma A1 boleh memproses input bersaiz 1000 dalam satu saat, manakala A5 boleh memproses input bersaiz tidak lebih daripada 9. Dalam jadual. 6.5.1. Saiz masalah yang boleh diselesaikan dalam satu saat, satu minit dan satu jam oleh setiap lima algoritma ini diberikan. Jadual 6.5.3. Mari kita andaikan bahawa komputer generasi akan datang akan menjadi 10 kali lebih pantas daripada komputer sekarang. Dalam jadual 6.5.2. menunjukkan bagaimana saiz masalah yang boleh kita selesaikan disebabkan peningkatan kelajuan ini akan meningkat. Ambil perhatian bahawa untuk algoritma A5, peningkatan sepuluh kali ganda dalam kelajuan meningkatkan saiz masalah yang boleh diselesaikan dengan hanya tiga unit (lihat baris terakhir dalam Jadual 6.5.2.), manakala untuk algoritma A3 saiz masalah lebih daripada tiga kali ganda. . Jadual 6.5.4. Daripada kesan peningkatan kelajuan, mari kita pertimbangkan kesan penggunaan algoritma yang lebih cekap. Mari kembali ke jadual 6.5.1. Jika kita mengambil masa 1 minit sebagai asas untuk perbandingan, maka dengan menggantikan algoritma A4 dengan algoritma A3, kita boleh menyelesaikan masalah 6 kali lebih besar, dan dengan menggantikan A4 dengan A2 ,
anda boleh menyelesaikan masalah 125 kali lebih besar. Keputusan ini jauh lebih mengagumkan daripada peningkatan 2x yang dicapai dengan 10x kelajuan. Jika kita mengambil masa 1 jam sebagai asas perbandingan, perbezaannya ternyata lebih ketara. Daripada ini, kami menyimpulkan bahawa kerumitan asimptotik algoritma berfungsi sebagai ukuran penting bagi kualiti algoritma, dan ukuran yang menjanjikan untuk menjadi lebih penting dengan peningkatan seterusnya dalam kelajuan pengiraan. Walaupun fakta bahawa perhatian utama di sini diberikan kepada susunan pertumbuhan kuantiti, seseorang mesti memahami bahawa susunan pertumbuhan yang besar dalam kerumitan algoritma mungkin mempunyai pemalar darab yang lebih kecil (malar c dalam takrifan O(f(x))), daripada susunan kecil peningkatan dalam kerumitan algoritma lain. Dalam kes ini, algoritma dengan kerumitan yang semakin meningkat dengan cepat mungkin lebih baik untuk masalah kecil - mungkin juga untuk semua masalah yang kami minati. Sebagai contoh, katakan bahawa kerumitan masa algoritma A1, A2, A3, A4, A5 sebenarnya masing-masing 1000n, 100nÿlog(n), 10n2, n3 dan 2. n Kemudian A5 akan menjadi yang terbaik untuk masalah saiz 2§n§9, A2 - untuk masalah saiz 10§n§58, A1 - pada 59§n§1024, dan A1- dengan n>1024.- 1. F.A. Novikov. Matematik diskret untuk pengaturcara./ St. Petersburg: Peter, 2001, 304С. 2. S.V. Sudoplatov, E.V. Elemen Matematik Diskret./ M., INFRA-M, Novosibirsk, NSTU Publishing House, 3. Y.M.Erusalimsky. Matematik diskret / M., "Buku Universiti", 2001, 279 pp. 4. A. Aho, J. Hopcroft, J. Ullman. Pembinaan dan analisis algoritma pengiraan. / M., Mir, 1979, 536С. 5. V.N.Nefedov, V.A.Osipova Kursus dalam matematik diskret./ M., Rumah Penerbitan MAI, 1992, 264P.§4.3. Pengkuantiti dan sifatnya.
Bab V. Teori formal.
§5.1. Definisi teori formal.
§5.2. Kalkulus cadangan.
§5.3. Teorem potongan. Kelengkapan IV.
§5.4. Bukti automatik teorem.
§5.5. Kaedah penyelesaian dalam IW.
Bab VI. Unsur-unsur teori algoritma.
§6.1. Definisi algoritma.
§6.2. Mesin Turing.
q 0
…
q i
…
q m
…
a u
q
s
a
rS
…
§6.3. Fungsi rekursif
§6.4. Masalah yang tidak dapat diselesaikan secara algoritma.
§6.5. Algoritma dan kerumitannya.
KESUSASTERAAN.
pengenalan.
Tujuan.
Bahagian baharu kursus matematik diskret, walaupun dilaksanakan dalam bentuk program pendidikan dan siri kuliah, masih belum wujud dalam bentuk monograf, sekurang-kurangnya dalam bahasa Rusia, kerana kursus matematik diskret untuk universiti teknikal tertumpu kepada masalah gunaan lama yang jurutera terpaksa menyelesaikannya. Khususnya, dalam logik matematik ia adalah pengecilan litar logik, yang telah kehilangan kaitannya hari ini.
Adalah menarik untuk diperhatikan bahawa teori sintesis litar logik, setelah melalui "kitaran biologi" yang hampir lengkap di hadapan mata satu generasi penyelidik, adalah contoh yang sangat instruktif tentang bagaimana cabang sains teknikal yang kurang berkaitan dengan asas. sains sangat terdedah kepada keusangan. Hanya 10 tahun yang lalu, semua jurnal teknikal telah diisi dengan artikel mengenai pengecilan dan sintesis litar logik. Kebanyakan kaedah meminimumkan yang dibangunkan oleh saintis kini dilupakan dan tidak dalam permintaan dalam amalan. Dan idea-idea yang dianggap sebagai teori semata-mata pada masa itu telah menemui aplikasi praktikal dalam teknologi moden. Contohnya, logik kabur, jaring Petri, dan teori algoritma telah bertahan dalam ujian masa dan digunakan secara meluas dalam pelbagai bidang sibernetik dan pengaturcaraan seperti pengaturcaraan sistem, kerumitan pengiraan dan kecerdasan buatan.
Dan teori algoritma menjadi bahagian tengah matematik diskret. Walau bagaimanapun, tidak seperti kebanyakan monograf dalam bahasa Rusia, semasa kuliah, isu-isu ini dibentangkan sebagai cara untuk menyelesaikan masalah kejuruteraan yang praktikal.
Seperti yang anda ketahui, selepas setiap dekad, komponen perkakasan komputer, sistem pengendalian, alat capaian dan program itu sendiri berubah secara radikal. Walau bagaimanapun, struktur dan algoritma yang mendasarinya kekal tidak berubah untuk lebih lama. Asas ini mula diletakkan beribu-ribu tahun dahulu, apabila logik formal dibangunkan dan algoritma pertama dibangunkan.
Logik matematik dan teori algoritma secara tradisinya tergolong dalam sains asas dan dianggap mempunyai sedikit kaitan dengan amalan dan sukar untuk difahami. Sesungguhnya, apabila J. Boole mencipta radas matematik algebra Boolean, ia tidak menemui aplikasi praktikal untuk masa yang lama, tetapi pada abad ke-20, radas matematik inilah yang memungkinkan untuk mereka bentuk semua komponen komputer. Akibatnya, prasangka pertama ini berjaya disangkal oleh perkembangan teknologi komputer.
Bagi prasangka tentang kesukaran memahami disiplin ini, sebahagian besarnya berpunca daripada fakta bahawa buku tentang logik matematik dan teori algoritma telah ditulis oleh ahli matematik untuk ahli matematik.
Kini, apabila keupayaan teknologi pengkomputeran telah meningkat berkali-kali ganda, dan terdapat lebih banyak komputer peribadi itu sendiri daripada orang yang tahu cara menggunakannya dengan berkesan, memahami apa yang boleh dan tidak boleh dilakukan dengan bantuan teknologi pengkomputeran moden adalah kepentingan yang luar biasa.
Teori umum algoritma yang menunjukkan bahawa terdapat masalah yang tidak dapat diselesaikan tidak kira betapa kuatnya kuasa pengkomputeran, dan cabangnya yang pesat membangun - teori kerumitan pengiraan - secara beransur-ansur membawa kepada pemahaman bahawa terdapat masalah yang boleh diselesaikan, tetapi kompleks secara objektif, dan kerumitannya mungkin menjadi agak dalam erti kata mutlak, i.e. boleh dikatakan tidak boleh diakses oleh komputer moden.
Kursus ini menetapkan objektif berikut:
1. Kemukakan semua isu yang sedang dipertimbangkan semudah mungkin, tetapi tidak lebih mudah daripada yang diperlukan untuk pakar yang berkelayakan tinggi.
2. Masalah praktikal reka bentuk dan analisis sistem maklumat adalah titik permulaan, dan radas formal adalah cara untuk menyelesaikan masalah ini secara sistematik. Adalah menjadi keyakinan kami yang mendalam bahawa seorang pelajar bukanlah wadah yang perlu diisi, tetapi obor yang perlu dinyalakan.
3. Setiap bahagian kursus mengandungi soalan ujian kendiri. Untuk menguasai kursus ini, pelajar mesti menjawab semua soalan ini.
Hasil daripada menguasai kursus ini, pelajar, berdasarkan pemahaman yang jelas tentang bahagian teori yang berkaitan, seharusnya dapat:
Melaksanakan jenis transformasi logik maklumat yang paling mudah dalam asas fungsi logik yang sewenang-wenangnya;
Kenal pasti struktur logik dalam penaakulan bukti dalam bahasa semula jadi, bina skema bukti formal dan semak ketepatannya.
1.2 Perwakilan logik
Perwakilan logik - penerangan tentang sistem, proses, fenomena yang dikaji dalam bentuk set pernyataan yang kompleks terdiri daripada pernyataan mudah (asas). Dan penghubung logik antara mereka. Perwakilan logik dan komponennya dicirikan oleh sifat tertentu dan satu set transformasi yang dibenarkan ke atasnya (operasi, peraturan inferens, dll.), melaksanakan yang dibangunkan secara formal (matematik) Dalam logik, kaedah penaakulan yang betul ialah hukum logik.
Kaedah (peraturan) pembentangan rasmi pernyataan, pembinaan pernyataan baharu daripada yang sedia ada menggunakan transformasi yang betul secara logik, serta kaedah (kaedah) untuk menentukan kebenaran atau kepalsuan pernyataan dikaji dalam logik matematik. Logik matematik moden merangkumi dua bahagian utama: logik kenyataan dan menutupinya logik predikat(Rajah 1.1), untuk pembinaannya terdapat dua pendekatan (bahasa), membentuk dua varian logik formal: algebra logik Dan kalkulus logik. Terdapat korespondensi satu dengan satu antara konsep asas bahasa logik formal ini. Isomorfisme mereka akhirnya dipastikan oleh kesatuan transformasi yang boleh diterima.
nasi. 1.1
Objek utama cabang logik tradisional ialah pernyataan.
Kenyataan - ayat deklaratif (kenyataan, penghakiman), o yang masuk akal untuk mengatakan bahawa ia benar atau salah. Semua pengetahuan saintifik (undang-undang dan fenomena fizik, kimia, biologi, dll., Teorem matematik, dll.), Peristiwa kehidupan seharian, situasi yang timbul dalam ekonomi dan proses pengurusan dirumuskan dalam bentuk pernyataan. Ayat imperatif dan ayat tanya bukan penyataan.
Contoh pernyataan: "Dua kali dua ialah empat", "Kita hidup pada abad ke-21", "Ruble ialah mata wang Rusia", "Alyosha ialah abang Oleg", "Operasi kesatuan, persimpangan dan penambahan ialah operasi Boolean pada set. ”, “Manusia adalah fana” , “Menyusun semula tempat istilah tidak mengubah jumlahnya,” “Hari ini adalah hari Isnin,” “Jika hujan, anda harus mengambil payung.”
Untuk terus beroperasi dengan ayat-ayat ini sebagai pernyataan, kita mesti mengetahui bagi setiap daripada mereka sama ada ia benar atau salah, i.e. mengenali mereka nilai kebenaran (truth). Ambil perhatian bahawa dalam beberapa kes kebenaran atau kepalsuan pernyataan bergantung pada realiti tertentu (sistem, proses, fenomena) yang kami cuba huraikan dengan bantuannya. Dalam kes ini, pernyataan yang diberikan dikatakan benar (atau palsu) dalam tafsiran (konteks) yang diberikan. Kami selanjutnya menganggap bahawa konteks diberikan dan pernyataan itu mempunyai nilai kebenaran tertentu.
1.3 Sejarah logik matematik yang dibangunkan
Logik sebagai sains telah terbentuk pada abad ke-4. BC. Ia dicipta oleh saintis Yunani Aristotle.Perkataan "logik" berasal dari bahasa Yunani "logos", yang di satu pihak bermaksud "perkataan" atau "eksposisi", dan di sisi lain, berfikir. Dalam kamus penjelasan Ozhegov S.I. Dikatakan: "Logik ialah ilmu tentang hukum-hukum pemikiran dan bentuk-bentuknya." Pada abad ke-17 Saintis Jerman Leibniz merancang untuk mencipta sains baharu, yang akan menjadi "seni mengira kebenaran" . Dalam logik ini, menurut Leibniz, setiap pernyataan akan mempunyai simbol yang sepadan, dan penaakulan akan mempunyai bentuk pengiraan. Idea Leibniz ini, setelah tidak memenuhi pemahaman sezamannya, tidak disebarkan atau dikembangkan dan kekal sebagai tekaan yang cemerlang.
Hanya pada pertengahan abad ke-19. Ahli matematik Ireland George Boole menjelmakan idea Leibniz Pada tahun 1854, beliau menulis karya "Penyiasatan hukum pemikiran," yang meletakkan asas untuk algebra logik, di mana undang-undang yang serupa dengan undang-undang algebra biasa digunakan, tetapi huruf itu berlaku. bukan menunjukkan nombor, tetapi pernyataan. Dalam bahasa algebra Boolean, seseorang boleh menerangkan penaakulan dan "mengira" keputusannya. Walau bagaimanapun, ia tidak merangkumi semua penaakulan, tetapi hanya jenis tertentu sahaja. , Oleh itu, algebra Boole dianggap sebagai kalkulus proposisi.
Algebra logik Boole adalah embrio sains baharu - logik matematik. Sebaliknya, logik Aristotle dipanggil logik formal tradisional. Nama "logik matematik" mencerminkan dua ciri sains ini: pertama, logik matematik ialah logik yang menggunakan bahasa dan kaedah matematik; kedua, logik matematik dihidupkan oleh keperluan matematik.
Pada akhir abad ke-19. Teori set yang dicipta oleh Georg Cantor nampaknya merupakan asas yang boleh dipercayai untuk semua matematik, termasuk logik matematik, sekurang-kurangnya untuk kalkulus proposisi (algebra Boole), kerana Ternyata algebra Cantor (teori set) adalah isomorfik kepada algebra Boole.
Logik matematik itu sendiri menjadi cabang matematik yang pada mulanya kelihatan sangat abstrak dan jauh dari aplikasi praktikal. Walau bagaimanapun, kawasan ini tidak kekal sebagai domain ahli matematik "tulen" untuk masa yang lama. Pada awal abad ke-20. (1910) Saintis Rusia Ehrenfest P.S. menunjukkan kemungkinan menggunakan radas algebra Boolean dalam komunikasi telefon untuk menerangkan litar pensuisan. Pada tahun 1938-1940, hampir serentak, karya saintis Soviet V.I Shestakov, saintis Amerika Shannon dan saintis Jepun Nakashima dan Hakazawa muncul pada aplikasi logik matematik dalam teknologi digital. Monograf pertama yang dikhaskan untuk penggunaan logik matematik dalam reka bentuk peralatan digital diterbitkan di USSR oleh saintis Soviet M.A. Gavrilov. pada tahun 1950. Peranan logik matematik dalam pembangunan teknologi mikropemproses moden sangat penting: ia digunakan dalam reka bentuk perkakasan komputer, dalam pembangunan semua bahasa pengaturcaraan dan dalam reka bentuk peranti automasi diskret.
Para saintis dari negara yang berbeza membuat sumbangan besar kepada pembangunan logik matematik: profesor Universiti Kazan Poretsky P.S., de-Morgan, Peirce, Turing, Kolmogorov A.N., Heidel K. dan lain-lain.
1.4 Soalan untuk ujian kendiri.
1. Merumus objektif kursus