Matematiksel mantık ve algoritma teorisi üzerine dersler. Matematiğin inşası

Bölüm I. Mantığın Cebiri.

Bölüm II. Boole cebiri.

Bölüm III. Zhegalkin cebiri.

Bölüm IV. İfadeler. Tahminler.

Bölüm V. Biçimsel teoriler.

§1.1. Boole fonksiyonunun tanımı.

§1.2. Temel Boole fonksiyonları.

§1.3. Temel olanları kullanarak Boolean işlevlerini belirtme.

§1.4. Anlamlı ve anlamlı olmayan değişkenler.

§1.5. Doğruluk tabloları. Eşdeğer fonksiyonlar.

§1.6. Temel eşdeğerlikler.

§1.7. İşlevsel bütünlük.

§2.1. Normal formlar.

§2.2. Mükemmel normal formlar.

§2.3. Quine yöntemiyle DNF minimizasyonu.

§ 2.4. Carnot haritaları.

§4.1. İfadeler.

§4.2. Tahminler. Yüklemler üzerinde mantıksal işlemler.

§4.3. Niceleyiciler ve özellikleri.

§5.1. Biçimsel teorinin tanımı.

§5.2. Önerme hesabı.

§5.3. Tümdengelim teoremi. IV'ün tamlığı.

§5.4. Teoremlerin otomatik ispatı.

§5.5. IW'de çözünürlük yöntemi.

İyi çalışmanızı bilgi tabanına göndermek kolaydır. Aşağıdaki formu kullanın

Benzer belgeler

Bilgi tabanını çalışmalarında ve çalışmalarında kullanan öğrenciler, lisansüstü öğrenciler, genç bilim insanları size çok minnettar olacaklardır.

Eserin henüz HTML versiyonu bulunmamaktadır.
Eserin arşivini aşağıdaki linke tıklayarak indirebilirsiniz.

Matematiksel mantığın temel tanımları, Boolean ve eşdeğer fonksiyonlar. Genel kavramlar Boole cebiri. Zhegalkin cebiri: ifadeler ve yüklemler. Tanım biçimsel teori. Algoritma teorisinin unsurları, özyinelemeli fonksiyonlar, Turing makinesi.

ders kursu, eklendi 08/08/2011

Temel düşünme biçimleri: kavramlar, yargılar, çıkarımlar. George Boole'un mantıksal cebiri ayrıntılı olarak araştıran bir makalesi. Bir ifadenin doğruluk değeri (yani doğruluk veya yanlışlık). Mantıksal işlemler ters çevirme (olumsuzlama) ve bağlaç.

sunum, 14.12.2016 eklendi

Kümelerin grafiksel yorumu ve üzerlerinde yapılan işlemler. Matematiksel mantık, Boole cebiri. Mükemmel konjonktif normal form. Eşdeğer formüller ve kanıtları. Sistemin eksiksizliği Boole işlevleri. Yüklem mantığı, çizge teorisi.

ders, 12/01/2009 eklendi

Boole cebirinin ortaya çıkış tarihi, önermeli hesap sisteminin gelişimi. Karmaşıklığın doğruluğunu veya yanlışlığını belirleme yöntemleri mantıksal ifadeler kullanarak cebirsel yöntemler. Ayrıklık, bağlaç ve olumsuzluk, doğruluk tabloları.

sunum, 22.02.2014 eklendi

Kare matrisler ve belirleyiciler. Doğrusal uzayı koordine edin. Sistem Araştırması doğrusal denklemler. Matrislerin cebiri: toplama ve çarpma. Geometrik resim karmaşık sayılar ve onlar trigonometrik form. Laplace teoremi ve temeli.

eğitim kılavuzu, eklendi 03/02/2009

Pozitif (doğal) sayılar teorisinin temel kavramı. Aritmetik işlemler için kısayolun geliştirilmesi. Bölünebilirlik için sembolik bir dil. Karşılaştırmaların özellikleri ve cebiri. Güçlerle karşılaştırmaları arttırmak. Yeniden kare alma. Fermat'ın küçük teoremi.

sunum, 06/04/2014 eklendi

Sistemler dijital işleme bilgi. Boole cebiri kavramı. Mantıksal işlemlerin tanımları: ayrılma, bağlaç, ters çevirme, ima, eşdeğerlik. Boole cebirinin yasaları ve kimlikleri. Mantıksal Temeller BİLGİSAYAR. Yapısal formüllerin dönüştürülmesi.

sunum, 10/11/2014 eklendi

Volzhsky Üniversitesi adını almıştır. Tatishcheva.

Dersler matematiksel mantık ve algoritma teorisi.

Derleyen: Doçent S.V. Kaverin.

Boole işlevi y=f(x 1 ,x 2 ,…,x n)den N değişkenler x 1 , x 2 ,...,x n, argümanların ve fonksiyonun 0 veya 1 değerini alabileceği herhangi bir fonksiyondur; Boolean işlevi, rastgele sıfırlar ve birler kümesinin

(x 1 ,x 2 ,...,x n) 0 veya 1 değerine atanır.

Boole işlevleri ayrıca denir lojik cebir fonksiyonları, ikili fonksiyonlar ve anahtarlama fonksiyonları.

Boolean işlevi N değişkenler, argüman değerleri kümelerinin sayılarına göre artan sırada düzenlendiği bir doğruluk tablosuyla belirtilebilir : Başta işe alım sürüyor 0'ın ikili açılımını temsil eden (bu küme 0 olarak numaralandırılmıştır); sonra 1'in, ardından 2, 3'ün vb. ikili açılımı olan küme gelir. Son set şunlardan oluşur: N birimler ve 2 sayısının ikili açılımıdır N-1 (kümelerin bu düzenlenme sırasına sözlükbilimsel sıralama ). Sayımın 0'dan başladığını ve Boolean fonksiyonunun değerinin 0 veya olabileceğini düşünürsek N

Şekil 1'den yalnızca 22 farklı Boole fonksiyonunun olduğu sonucuna varıyoruz. N değişkenler. Dolayısıyla, örneğin iki değişkenli 16 Boole fonksiyonu, üç değişkenli 256'sı vb. vardır.

Örnek 1.1.1.(oy) . “Üçlü komite”nin aldığı belirli bir kararı kaydeden bir cihazı düşünelim. Her komite üyesi bir kararı onaylarken kendi düğmesine basar. Üyelerin çoğunluğunun olumlu oy kullanması halinde karar kabul edilir. Bu bir kayıt cihazı tarafından kaydedilir. Böylece cihaz f(x,y,z) fonksiyonunu uygular. ) doğruluk tablosu şu şekle sahip olan

X	0	0	0	0	1	1	1
sen	0	1	1	1	0	0	1
z	1	0	0	1	0	1	1
f(x,y,z)	0	0	0	1	0	1	1

Bir Boolean işlevi ayrıca, 0 değerini aldığı tüm demetleri numaralandırarak veya 1 değerini aldığı tüm demetleri numaralandırarak benzersiz bir şekilde belirtilir. Örnekte elde edilen fonksiyon F aşağıdaki eşitlik sistemiyle de belirtilebilir: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.

Boolean fonksiyon değerlerinin bir vektörü y=f(x 1 ,x 2 ,…,x n), değerlerin sözlüksel sıraya göre sıralandığı f fonksiyonunun tüm değerlerinin sıralı bir kümesidir. Örneğin, üç değişkenli f fonksiyonu, değerlerin vektörü (0000 0010) ile belirtilsin ve f'nin 1 değerini alacağı bir küme bulmak gerekir. Çünkü 1 7. sırada yer alıyor ve sözlüksel sıralamada numaralandırma 0'dan başlıyor, bu durumda 6'nın ikili açılımını bulmak gerekiyor. Böylece f fonksiyonu (110) kümesinde 1 değerini alıyor.

Boolean fonksiyonları arasında, herhangi bir sayıda değişkenin herhangi bir Boolean fonksiyonunun tanımlanabildiği temel Boolean fonksiyonları öne çıkmaktadır.

1. Tüm sıfır ve birlerden oluşan kümelerde 1 değerini alan f(x 1 ,x 2 ,…,x n) Boolean fonksiyonuna denir sabit 1 veya aynı birim. Tanım : 1 .

2. Tüm sıfır ve birlerden oluşan kümelerde 0 değerini alan f(x 1 ,x 2 ,…,x n) Boolean fonksiyonuna denir sabit 0 veya aynı sıfır. Tanım : 0 .

3. İnkar aşağıdaki doğruluk tablosuyla tanımlanan bir değişkenin Boolean fonksiyonudur

Diğer isimler : mantıksal çarpma (çarpım); mantıksal "ve".

Tanımlar : x&y, xÿy, x⁄y, min(x,y).

5. Ayrılık

Diğer isim : mantıksal sonuç. Tanımlar : xØy, xfly, xy.

7. Denklik aşağıdaki doğruluk tablosuyla tanımlanan iki değişkenin bir Boole fonksiyonudur

Diğer isim : anti-eşdeğerlik. Tanımlar : x∆y, x+y.

9. Schaeffer'in felç geçirmesi aşağıdaki doğruluk tablosuyla tanımlanan iki değişkenli bir Boole fonksiyonu

Diğer isim : ayrılığın olumsuzlanması, mantıksal “ya da değil”, Webb işlevi.

Tanım : x∞y ; Webb işlevi için - x±y.

Yorum. Gösterimde yer alan Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ sembolleri temel işlevler bunlara bağlantılar veya operasyonlar diyeceğiz.

Bazı Boolean fonksiyonlarını değişkenler yerine mantıksal bir fonksiyonla değiştirirseniz sonuç, adı verilen yeni bir Boolean fonksiyonu olur. süperpozisyon ikame edilmiş fonksiyonlar (karmaşık fonksiyon). Süperpozisyon kullanarak herhangi bir sayıda değişkene bağlı olabilecek daha karmaşık fonksiyonlar elde edebilirsiniz. Boolean fonksiyonlarını temel Boolean fonksiyonlara göre yazmaya çağıracağız. formül uygulamak bu fonksiyon.

Örnek 1.3.1. Bir temel Boole fonksiyonu x¤y verilsin. X yerine x 1 ∞x 2 fonksiyonunu yazalım. Üç değişkenli (x 1 ∞x 2)¤y fonksiyonunu elde ederiz. Eğer y değişkeni yerine örneğin x 3 ∆x 4 koyarsak, şunu elde ederiz: yeni özellik dört değişkenden: (x 1 ∞x 2)¤(x 3 ∆x 4). Açıkçası, bu şekilde temel Boolean fonksiyonlarıyla ifade edilecek olan Boolean fonksiyonlarını elde edeceğiz.

İleriye baktığımızda şunu not ediyoruz: herhangi Bir Boole fonksiyonu, temel fonksiyonların süperpozisyonu olarak temsil edilebilir.

Daha kompakt bir kayıt için karmaşık işlevler aşağıdaki kuralları tanıtalım : 1) dış parantezler çıkarılmıştır; 2) önce parantez içindeki işlemler gerçekleştirilir; 3) Bağlaçların önceliğinin aşağıdaki sırayla azaldığı düşünülmektedir. : Ÿ, ⁄, ¤, Ø, ~. Eşdeğer bağlaçlar ve geri kalan (∆,|,∞) bağlaçlar için şimdilik parantez koymalısınız.

Örnekler 1.3.2. x⁄y¤z formülünde parantezler yerleştirilmiştir aşağıdaki gibi: ((x⁄y)¤z), çünkü anlaşmamıza göre ⁄ operasyonu ¤ operasyonundan daha güçlüdür.

1. x¤y~zØx formülünde parantezler şu şekilde yerleştirilir: ((x¤y)~(zØx))

2. (x∆y)~zØxy¤Ÿz formülünde parantezler şu şekilde yerleştirilir: ((x∆y)~(zØ((xy)¤(Ÿz))))).

3. Anlaşmamıza uygun olarak xØyØz formülü doğru yazılmamıştır çünkü parantezlerin yerleştirilmesi iki sonuçla sonuçlanır farklı işlevler: ((xØy)Øz) ve (xØ(yØz)).

Boolean işlevi y=f(x 1 ,x 2 ,…,x n) önemli ölçüde bağlıdır değişkenden X k eğer böyle bir değer kümesi mevcutsa A 1 ,A 2 ,…,A k-1, A k+1, A k + 2 ,…, A N bu f (A 1,a 2,…,bir k-1 , 0 ,A k+1,a k+2,…,a N) π F (A 1,a 2,…,bir k-1 , 1 ,A k+1,a k+2,…,a N).

Bu durumda X k'ya temel değişken denir , V aksi takdirde X k'ya önemsiz (kukla) bir değişken denir . Başka bir deyişle, bir değişkenin değiştirilmesi fonksiyonun değerini değiştirmiyorsa konuyla ilgisizdir.

Örnek 1.4.1. Boolean fonksiyonları f 1 (x 1 ,x 2) ve f 2 (x 1 ,x 2) aşağıdaki doğruluk tablosuyla tanımlansın:

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

Bu işlevler için x 1 değişkeni - anlamlıdır ve x 2 değişkeni anlamlı değildir.

Açıkçası Boolean fonksiyonları, alakasız değişkenleri ekleyerek (veya kaldırarak) değerlerini değiştirmez. Bu nedenle, aşağıda Boolean fonksiyonları önemsiz değişkenlere kadar dikkate alınır (örnekte şunu yazabiliriz: f 1 (x 1 , x 2) = x 1 , f 2 (x 1 , x 2) = Ÿx 1 ).

Temel fonksiyonların doğruluk tablolarını bildiğinizden, bu formülün uyguladığı fonksiyonun doğruluk tablosunu hesaplayabilirsiniz.

Örnek 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)

Böylece F1 formülü ayırmayı uygular. Örnek 1.5.2. F2=x 1 ⁄x 2 Øx 1

Böylece formül F3 ayırmayı uygular.

Boolean fonksiyonları f1 ve f2 çağrılır eş değer, eğer her sette ( A 1 ,A 2 ,…, BİR) sıfırlar ve birler, fonksiyonların değerleri çakışıyor. Eşdeğer fonksiyonların gösterimi aşağıdaki gibidir : f1=f2.

Verilen 1-3 örneklerine göre şunu yazabiliriz:

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.

Verilen eşdeğerlikler genellikle Boolean fonksiyonlarıyla çalışırken faydalıdır.

H, H1, H2,...'nin altında bazı Boole fonksiyonları yer alır.

1. Çift olumsuzlama yasası: H = H.

2. İktidarsızlık

3. Değişebilirlik:

H1*H2=H2*H1, burada * sembolü &, ¤, ∆, bağlaçlarından biri anlamına gelir

4. İlişkisellik:

H1*(H2*H3)=(H1*H2)*H3, burada * sembolü &, ¤, ∆, ~ bağlaçlarından biri anlamına gelir.

5. Dağıtıcılık:

H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).

6. De Morgan'ın yasaları:

H1& H2 = H1 ∨ H2, H1∨ H2 = H1 & H2.

7. Devralma kuralları:

H1¤(H2&H3)=H1, H1&(H2¤H3)=H1

8. Yapıştırma kanunları:

H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.

9. Ters çevirme yasaları: H ∨ H = 1, H & H = 0.

10. Sabitlerle işlemler için kurallar:

H¤1=1, H&1=H, H¤0=H, H&0=0.

Yukarıdaki eşdeğerliklerin doğruluğunu kontrol etmek için ilgili doğruluk tablolarını oluşturmak yeterlidir.

Bir işlemin ilişkilendirilebilirlik özelliğinin, bu işlemin herhangi bir sayıda değişkene genişletilmesine izin verdiğini unutmayın. Yani örneğin x¤у¤z¤w gösterimi doğrudur çünkü parantezlerin herhangi bir düzenlemesi aynı işlevle sonuçlanır. Bir işlemin değişmeli doğası, bir formüldeki değişkenleri değiştirmenize olanak tanır. Örneğin, x⁄y⁄z⁄w=w⁄y⁄x⁄z.

Tipik bir modern dijital ortamda bilgisayar sayılar 0 ve 1'dir. Bu nedenle işlemcinin yürüttüğü talimatlar Boolean işlevleridir. Aşağıda herhangi bir Boole fonksiyonunun bağlaç, ayırma ve olumsuzlama yoluyla uygulandığını göstereceğiz. Sonuç olarak, birleştirme, ayırma ve olumsuzlamayı uygulayan unsurları emrinde bulundurarak gerekli işlemciyi oluşturmak mümkündür. Bu bölüm şu soruyu yanıtlamaya ayrılmıştır: diğer tüm işlevleri ifade etmek için kullanılabilecek özelliğe sahip başka Boole işlevleri sistemleri var mı (ve varsa ne).

Birkaç fonksiyon sınıfını tanıtalım.

1. 0 sabitini koruyan işlevler sınıfı; bu tür işlevler

2. Sabit 1'i koruyan işlevler sınıfı, yani. bu tür işlevler

3. Kendi kendine ikili fonksiyonlar sınıfı, yani. y=f(x 1 ,x 2 ,…,x n) gibi fonksiyonlar, f(x 1 , x 2 ,… , x n) = f(x 1 , x 2 ,… , x n) .

4. Sınıf doğrusal fonksiyonlar yani f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ şeklinde temsil edilebilen y=f(x 1 ,x 2 ,…,x n) fonksiyonları c n x n, burada c 0, c 1, c 2 ...0 veya 1 değerini alabilen katsayılardır.

5. Sınıf monoton fonksiyonlar. Sıfırlar ve birlerden oluşan kümeler kümesinde Bn =((x 1 ,x 2 ,…,x n):x i œ(0,1),i=1,2,…,n) aşağıdaki gibi kısmi bir sıralama uygularız:

(A 1 ,a 2 ,...,a n)§( B 1 ,b 2 ,...,b n) ancak ve ancak A 1 § B 1 , bir 2 § b 2 ,…,a N § B N. Bir f(x 1, x 2,..., x n) fonksiyonu, B n'den gelen herhangi iki eleman için monoton olarak adlandırılır;

(A 1 ,a 2 ,...,a n)§( B 1 ,b 2 ,...,b n) bundan şu sonuç çıkar: f( A 1 ,a 2 ,...,a n)§F( B 1 ,b 2 ,...,b n).

Süperpozisyonu herhangi bir Boole fonksiyonunu temsil edebilen Boole fonksiyonlarından oluşan bir S sistemine denir. işlevsel olarak tamamlanmış . İşlevsel olduğunu söylüyorlar komple sistem S Boolean fonksiyonları formu temel mantıksal uzayda. S tabanı denir asgari , herhangi bir fonksiyonun kaldırılması bu sistemi eksik hale getirirse.

Tamlık kriteri (Post'un teoremi) . Boole fonksiyonlarından oluşan bir S sistemi ancak ve ancak en az bir fonksiyon içeriyorsa tamamlanır: korunmayan sabit 0, korunmayan sabit 1, kendi kendine ikili olmayan, doğrusal olmayan ve monoton olmayan.

Tablo 1.7, temel Boolean fonksiyonlarının sahip olduğu özellikleri göstermektedir (* sembolü, belirli bir fonksiyonun sahip olduğu bir özelliği belirtir).

Post'un teoremini ve tablo 1.7'yi kullanarak temel işlevlerden aşağıdakilere göre temeller oluşturabilirsiniz: sonraki kural. Herhangi bir temel Boole fonksiyonunu seçerek ve gerekirse diğer fonksiyonlarla tamamlayarak, hepsinin birlikte fonksiyonel tamlık teoremini karşılamasını sağlayın. Bu bazın işlevleri aracılığıyla şunu ifade edebiliriz: Tüm diğer Boole fonksiyonları.

Uygulamalarda sık kullanılan bazı temelleri oluşturalım.

Tablo 1.7

İsim	Tanım	Depolanamazlık sabitler	Depolanamazlık sabitler	Samodvoylar geçerlilik
Sabit0	0	*	*
İnşaat1	1	*	*
Negatif	Ÿ	*	*	*
Kongyun.	&	*	*
Ayrılık.	¤	*	*
Örtülü.	Ø	*	*	*	*
Eş değer.	~	*	*	*
mod_2'ye göre topla	∆	*	*	*
	\|	*	*	*	*	*
Pierce'ın oku	∞	*	*	*	*	*

1. S1=(Ÿ,⁄,¤) fonksiyon sistemi bir temel oluşturur. Bir Boole fonksiyonunu yalnızca S1 tabanındaki bağlaçları içeren bir forma indirmek için aşağıdaki eşdeğerlikler yararlı olabilir: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , xy = x ∨ y , x ↓ y = x ve y .

2. S2=(Ÿ,&) sistemi bir temel oluşturur. Keyfi işlevönce S1'den gelen bağlaçları içeren bir forma indirgenebilir ve daha sonra

x ∨ y = x ⋅ y ilişkisini kullanın.

3. S3=(Ÿ,¤) sistemi bir temel oluşturur. Rastgele bir fonksiyon ilk olarak S1'den gelen bağlaçları içeren bir forma indirgenebilir ve daha sonra

x ⋅ y = x ∨ y ilişkisini kullanın.

4. S4=(1,&,∆) sistemi bir temel oluşturur. Rastgele bir fonksiyon ilk olarak S1'den gelen bağlaçları içeren bir forma indirgenebilir ve ardından x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y ilişkileri kullanılabilir.

5. S5=(|) sistemi bir temel oluşturur. Rastgele bir fonksiyon ilk olarak S2'den gelen bağlaçları içeren bir forma indirgenebilir ve daha sonra x ⋅ y = x y, x = xx ilişkileri kullanılabilir.

6. S6=(∞) sistemi bir temel oluşturur. Rastgele bir işlev ilk olarak S3'ten gelen bağlaçları içeren bir forma indirgenebilir ve daha sonra

x ∨ y = x ↓ y, x = x ↓ x ilişkilerini kullanın.

7. S7=(Ø,0) sistemi temel oluşturur.

Örnek 1.7.1. x¨(y∆z) fonksiyonunu S1=(Ÿ,⁄,¤) bazında yazın. x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∨ y ⋅ z)

Temeldeki tüm booleanların kümesi S1=( ÿ, &, ⁄} biçim Boole cebiri. Dolayısıyla Boolean cebirinde tüm formüller üç bağlaç kullanılarak yazılır: Ÿ, &, ¤. Bu cebirin özelliklerini Bölüm I'de kısmen inceledik (örneğin temel eşdeğerliklere bakınız). Bu bölümde Boole cebirine özgü özellikler ele alınmaktadır ve bu nedenle bu bölüm boyunca yalnızca üç fonksiyonla ilgileneceğiz: ÿ, &, ⁄.

Normal formlar, uygulayan bir formül yazmanın sözdizimsel olarak açık bir yoludur. Verilen fonksiyon.

Eğer x mantıksal bir değişkense ve σœ(0,1) ise x σ = x if σσ == 10 veya x σ = 10 ise x x =≠σσ , x ifadesine bir harf denir . X ve Ÿx harflerine karşıt harfler denir. kavuşum ayrık harflerin ayrılması denir. Örneğin, x ⋅ y ⋅ z ve x ⋅ y ⋅ x ⋅ x formülleri bağlaçtır, x ∨ y ∨ z ve x ∨ y ∨ x formülleri ayrıklardır ve z formülü hem bağlaç hem de ayrıktır.

Ayırıcı normal form (DNF) sonlu sayıda bağlacın ayrılmasına denir .

Konjonktif normal form (CNF) sonlu sayıda cümleciğin birleşimine denir .

Daha basit bir şekilde: DNF, ürünlerin toplamıdır ve CNF, mantıksal toplamların ürünüdür.

1. xÿy¤yÿz¤x, DNF'dir (ürünlerin toplamı).

2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z, CNF'dir (toplamların çarpımı).

3. x ∨ y ∨ z ∨ w, DNF ve CNF'dir (aynı anda).

4. x ⋅ y ⋅ z ⋅ w, DNF ve CNF'dir (aynı anda).

5. (x¤x¤y)·(y¤z¤x)·z, CNF'dir.

6. x⋅y⋅z ve x⋅y⋅x⋅x, DNF'lerdir.

7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z normal bir form değildir (DNF veya CNF değil).

F fonksiyonu S1 bazında yazılsın. Bu fonksiyon aşağıdaki gibi normal forma indirgenir:

1) formülü, negatif işaretlerin yalnızca bireysel değişkenlerle ilgili olduğu bir forma dönüştürmek için De Morgan yasalarını kullanırız;

2) çift negatifleri kaldırmak için kuralı uyguluyoruz: ŸŸx=x;

H1&(H2¤H3)=(H1&H2)¤(H1&H3) ve CNF'ye indirgeme için ikinci dağıtım yasası. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).

Herhangi bir Boolean işlevi sonsuz sayıda DNF ve CNF temsiline sahip olabilir. Örneğin, ters çevirme yasalarını ve sabitlerle işlem kurallarını ek olarak kullanarak, her bir bireysel birleşik veya ayrık durumda herhangi bir değişkenin (kendisi veya olumsuzu) birden fazla görünmemesini sağlamak mümkündür.

Örnek 2.1.1. DNF'ye indirgemek için 1. dağıtım yasasını kullanıyoruz.

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)= CNF'dir

= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = - bu başka bir CNF'dir

X ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅ y⋅z =

X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z bir DNF'dir

Örnek 2.1.2. CNF'ye indirgemek için ikinci dağıtım yasasını kullanmak gerekir.

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) CNF'dir

Normal bir formun her teriminde tüm değişkenler temsil ediliyorsa (kendileri veya olumsuzları) ve her bir bağlaç veya ayrıklıkta herhangi bir değişken tam olarak bir kez görünüyorsa (kendisi veya olumsuzu), o zaman bu forma denir. mükemmel normal form (SDNF veya SCNF). Örnekler:Üç değişkenli f(x,y,z) fonksiyonu verilsin.

1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z mükemmel bir DNF'dir.

2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) mükemmel bir CNF'dir.

3. (x ∨ y) ⋅ (x ∨ z) mükemmel bir CNF değildir, çünkü örneğin ilk toplam z değişkenini içermez.

4. xÿyÿz mükemmel bir DNF'dir. Teorem 2.2.1.

1. Aynı şekilde sıfır olmayan herhangi bir Boolean işlevi, terimlerin konumuna kadar yalnızca bir SDNF'ye sahiptir.

2. 1 ile aynı olmayan herhangi bir Boolean işlevi, terimlerin konumuna kadar yalnızca bir SCNF'ye sahiptir.

Aşağıdaki problemin çözümü olarak teoremi yapıcı olarak kanıtlayacağız: Bu doğruluk tablosunu kullanarak bir SDNF oluşturun.

n=3 için bir tabloda (Tablo 2.2) verilen f(x,y,z) fonksiyonu örneğini kullanarak çözümü düşünelim.

Örnek 2.2.1. Bu doğruluk tablosunu (Tablo 2.2) kullanarak bir SDNF oluşturun.

Tablo 2.2

X	sen	z	temel bağlaçlar	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

Temel bağlaçlar (veya bileşenler_1) tabloda yer alan belirli bir sıfırlar ve birler kümesine karşılık gelir. değişkenler x,y,z. Bileşenler oluşturuluyor_ 1 Aşağıdaki kurala göre: Bir değişken belirli bir kümede 1 değerini alıyorsa çarpımın kendisine dahil edilir, aksi halde olumsuzluğu çarpıma dahil edilir. Yani örneğin (0,0,1) kümesinde x,y değişkenleri 0 değerini alır ve bu nedenle bunların olumsuzları çarpıma dahil edilir ve z değişkeni 1 değerini alır ve dolayısıyla çarpımın kendisine dahil edilir . Belirli bir (0,0,1) kümesi için bileşen_1, x ⋅ y ⋅ z'ye eşittir.

Açıkçası, x ⋅ y ⋅ z bağlacı yalnızca kümede 1'e eşittir

(0,0,0) ve x ⋅ y ⋅ z, (0,0,1) kümesinde 1'dir, vb. (tabloya bakınız). Daha sonra, iki temel bağlacın ayrıklığının, bu temel bağlaçlara karşılık gelen tam olarak iki kümede 1'e eşit olduğuna dikkat edin. Örneğin, x ⋅ y ⋅ z¤x ⋅ y ⋅ z fonksiyonu yalnızca iki kümede (0,0,0) ve (0,0,1) 1'e eşittir ve diğer tüm kümelerde şuna eşittir: 0. Benzer şekilde, temel bağlaçlardan üçünün ayrıklığı, bu temel bağlaçlara vb. karşılık gelen tam olarak üç kümede 1'e eşittir.

O. aldık kural: SDNF oluşturmak için fonksiyonun 1'e eşit olduğu satırları seçmeli ve ardından karşılık gelen ana bağlaçların ayrımını yapmalısınız, istenen SDNF'yi elde ederiz. Örneğimizde x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z var.

Görev. Bu doğruluk tablosunu kullanarak SCNF'yi oluşturun.

Anayasa_0 sıfırlar ve birlerden oluşan bir küme için (x,y,z değişkenlerini alan) şu şekilde oluşturulur: değişken bu kümedeki değeri alıyorsa ayrışımın kendisine dahil edilir 0 aksi takdirde çalışma onun olumsuzlanmasını içerir.

SKNF oluşturma kuralı: fonksiyonun eşit olduğu satırları seçmelisiniz 0 ve ardından karşılık gelen bileşenlerin_0 birleşimini alın. Sonuç istenen SCNF olacaktır. Örneğimizde f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) var.

Yorum. Mükemmel bir CNF fonksiyonu f oluşturmak için, f fonksiyonu için mükemmel bir DNF oluşturmak yeterlidir ve sonra

Örneğimiz için SCNF'yi açıklamalara dayanarak oluşturalım. 1. Olumsuzlama için bir SDNF oluşturuyoruz.

x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z

2. De Morgan yasalarını kullanıyoruz 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)⋅(x ∨ y ∨ z) .

Doğruluk tablosunu kullanarak SDNF'yi (ve SCNF'yi) bulmanın açıklanan yöntemi genellikle aşağıdaki algoritmadan daha fazla emek gerektirir.

1. SDNF'yi bulmak için bu formülİlk önce DNF'ye indiriyoruz.

2. Eğer bir K bağlacı (yani K, belirli sayıda değişkenin veya bunların olumsuzlamalarının çarpımıdır) örneğin y değişkenini içermiyorsa, o zaman bu bağlacı eşdeğer K&(y ∨ y) formülüyle değiştiririz ve dağıtım kanunu, ortaya çıkan formülü DNF'ye sunuyoruz; birkaç eksik değişken varsa, bunların her biri için (y ∨ y) formunun karşılık gelen formülünü bağlaca ekleriz.

3. Ortaya çıkan DNF, birimin birkaç özdeş bileşenini içeriyorsa, bunlardan yalnızca birini bırakıyoruz. Sonuç SDNF'dir.

Yorum: Bir SCNF'yi örneğin bir değişken içermeyen bir cümlecikte oluşturmak için en y⋅ y formunda bir formül ekliyoruz, yani Bu ayrıklığı eşdeğer D ∨ y⋅ y formülüyle değiştiriyoruz ve 2. dağılım yasasını uyguluyoruz.

Örnek 2. 2. 2. Eşdeğer dönüşümleri kullanarak f fonksiyonu için bir SDNF oluşturun.

f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z y ⋅ z ⋅ x y ⋅ z ⋅ x =

GERİ ÇEKİL.

SDNF'nin hesaplanması sadece teorik değil aynı zamanda büyük pratik önemi. Örneğin, birçok durumda modern programlar karmaşık kompozisyonlar oluşturmak için grafiksel bir arayüze sahip mantıksal koşullar tablo şeklinde görsel bir form kullanılır: hücrelere koşullar yazılır ve bir sütunun hücrelerinin bir bağlaçla bağlı olduğu, sütunların ise bir ayrımla bağlı olduğu kabul edilir, yani bir DNF oluşturur (veya tam tersi, bu durumda bir CNF elde edilir). Özellikle, bir DBMS'yi sorgularken mantıksal koşulları formüle etmek için kullanılan QBE (Örnekle Sorgulama) grafik arayüzü bu şekilde tasarlanmıştır.

Algoritma 2.2.1. SDNF'nin inşaatı

Giriş: vektör X: dize - değişken tanımlayıcıların dizisi, matris V: tüm farklı değişken değer kümelerinin 0..1'inden oluşan dizi,

vektör F: 0..1 karşılık gelen fonksiyon değerlerinden oluşan dizi.

Çıkış: belirli bir işlev için SDNF formülünün bir kaydını oluşturan bir sembol dizisi.

f:= YANLIŞ(ayırmanın sol işleneninin varlığının işareti) için Ben itibaren 1ile 2 saat Yapmak

eğer F[i] = 1 o zaman eğer F Daha sonra

teslim olmak"¤" (formüle ayırma işareti ekleme; operatör teslim olmak m baskılar

sembol m) başka f:= doğru

eğer biterse g:= YANLIŞ(bağlacın sol işleneninin varlığının işareti) için J itibaren 1ile N eğer yap G Daha sonra

teslim olmak"⁄" (formüle bir bağlaç işareti ekleme)

başka g: =doğru

eğer biterse V ( formüle değişken tanımlayıcı ekleme

Her formül vardır son sayı değişkenlerin ortaya çıkışı. Bir değişkenin ortaya çıkışı, değişkenin formülde kapladığı yeri ifade eder. Görev, belirli bir Boole fonksiyonu f için, bu fonksiyonu temsil eden ve sahip olan bir DNF'yi bulmaktır. en küçük sayı değişkenlerin ortaya çıkışı.

Eğer x mantıksal bir değişkense ve σœ(0,1) ise x ifadesi σ =xx if if σσ== 10 .

isminde mektup . kavuşum harf birleşimi denir. Örneğin, x ⋅ y ⋅ z ve x ⋅ y ⋅ x ⋅ x formülleri bağlaçlardır . Temel bir çarpım, herhangi bir değişkenin birden fazla kez görünmediği (kendisi veya olumsuzu) bir bağlaçtır.

Formül f1 denir imalı formüller f , f1 bir temel çarpım ise ve f 1 ⁄ f = f 1 ise, yani yani formüllere karşılık gelen işlevler için f 1 § f eşitsizliği geçerlidir. f formülünün kapsayıcı f1'ine denir basit , f1'den herhangi bir harf atıldıktan sonra f formülünün bir sonucu olan bir formül elde edilmezse.

Örnek 2.3.1 . f=xØy formülü için tüm kapsamları ve basit çıkarımları bulalım . Değişkenlere sahip toplam 8 temel ürün var X Ve sen. Aşağıda, açıklık amacıyla doğruluk tabloları verilmiştir:

X	sen	xØy			x ⋅ y	x ⋅ y	x ⋅ y			x ⋅ y	X	sen		X		sen
							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

Doğruluk tablolarından x ⋅ y , x ⋅ y , x ⋅ y , x ,y formüllerinin olduğu sonucuna varıyoruz. - xØy formülünün tüm kapsamları ve bu kapsamların x ve y formülleri basittir (örneğin, x ⋅ y formülü basit bir kapsam değildir, çünkü y harfini atarak, kapsayıcı x'i elde ederiz).

Kısaltılmış DNF belirli bir formülün (fonksiyonun) tüm asal içeriklerinin ayrılması denir .

Teorem 2.3.1. 0 sabiti olmayan herhangi bir Boolean işlevi, kısa yollu DNF olarak temsil edilebilir.

Örnek 2.3.1'de xØy formülüne karşılık gelen fonksiyon, onun kısaltılmış DNF'si olan x ∨ y formülü ile temsil edilmektedir.

Azaltılmış bir DNF, ekstra implikasyonlar içerebilir ve bunların kaldırılması doğruluk tablosunu değiştirmez. İndirgenmiş bir DNF'den tüm gereksiz etkileri çıkarırsak, adı verilen bir DNF elde ederiz. çıkmaz sokak.

Bir işlevin çıkmaz DNF olarak temsilinin genel durum belirsiz. Tüm çıkmaz formlar arasından seçim yaparak, değişkenlerin en az sayıda görüldüğü form şunu verir: minimum DNF (MDNF).

Yöntemi düşünün Quina, Belirli bir Boolean işlevini temsil eden MDNF'yi bulmak için. Aşağıdaki üç işlemi tanımlıyoruz:

1. tam yapıştırma işlemi : f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;

2. kısmi yapıştırma işlemi:

f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;

3. temel absorpsiyonun çalışması f ⋅ x σ ∨ f = f , σ ∈ (0,1) .

Teorem 2.3.2(Quine'in teoremi). SDNF fonksiyonuna dayalı olarak, eksik yapıştırma ve ardından temel emilim gibi tüm olası işlemleri gerçekleştirirsek, sonuç, azaltılmış bir DNF, yani tüm basit içeriklerin ayrılması olacaktır.

Örnek 2.3.2. f(x,y,z) fonksiyonu mükemmel bir DNF ile verilsin f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Daha sonra, eksik yapıştırma ve ardından temel emilim gibi tüm olası işlemleri iki aşamada gerçekleştirerek, şunu elde ederiz:

Dolayısıyla, f fonksiyonunun kısaltılmış DNF'si y¤x·z formülüdür.

Uygulamada, her aşamada eksik yapıştırma işlemleri yapılırken, bu işlemlere ilişkin terimlerin yazılması değil, yalnızca olası tüm tam yapıştırmaların ve herhangi bir yapıştırma işlemine dahil olmayan bağlaçların sonuçlarının yazılması mümkündür.

Örnek 2. 3. 3. f(x,y,z) fonksiyonu mükemmel bir DNF ile verilsin f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .

Daha sonra yapıştırma ve ardından temel absorpsiyon işlemlerini gerçekleştirerek, elimizdeki

f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z

İndirgenmiş DNF'den minimum DNF'yi elde etmek için Quine matrisi kullanılır , aşağıdaki gibi inşa edilmiştir. Tablonun sütun başlıkları mükemmel DNF biriminin bileşenlerini içerir ve satır başlıkları, sonuçta ortaya çıkan kısaltılmış DNF'nin basit sonuçlarını içerir. Tabloda yıldız işaretleri, satır başlığındaki birleşimin sütun başlığı olan birimin bileşenine dahil edildiği satır ve sütunların kesişimlerini işaretler.

Örneğin 2.3.3. Quine matrisi şu şekle sahiptir:

Çıkmaz uçlu bir DNF'de, ayrılması birimin tüm bileşenlerini koruyan minimum sayıda basit kapsam seçilir, yani Quine matrisinin her sütunu, aşağıdaki matrislerden birine karşılık gelen satırla kesişme noktasında bir yıldız işareti içerir. seçilmiş etkiler. Değişkenlerin en az sayıda tekrarına sahip olan çıkmaz DNF, minimum DNF olarak seçilir.

Örnek 2.3.3'te Quine matrisini kullanarak belirli bir fonksiyonun minimum DNF'sinin x ⋅ y ¤ x ⋅ z olduğunu buluyoruz.

Yorum.

f =f ve De Morgan yasalarını kullanın.

Az sayıda değişkenle basit kapsamlı formüller elde etmenin (ve dolayısıyla minimum DNF'yi bulmanın) başka bir yolu Carnot haritalarının kullanımına dayanmaktadır.

Carnot haritası özel tip minimal form bulma sürecini kolaylaştıran ve değişken sayısı altıyı geçmediğinde başarıyla kullanılan bir tablo. N değişkene bağlı fonksiyonlar için bir Karnaugh haritası, 2 n hücreye bölünmüş bir dikdörtgendir. Diyagramın her hücresi bir ikili n boyutlu kümeyle ilişkilidir. Doğruluk tablosundan belirli bir f fonksiyonunun değerleri gerekli karelere girilir, ancak hücre 0'a karşılık gelirse genellikle boş kalır.

Tablo 2.4.1'de. üç değişkene bağlı bir fonksiyon için Karnaugh haritasını işaretleme örneğini gösterir. Haritanın alttaki dört hücresi, değişkenin bulunduğu ikili kümelere karşılık gelir. X 1 değerini alırsa, ilk dört hücre değişkenin bulunduğu kümelere karşılık gelir. X 0 değerini alır. Haritanın sağ yarısını oluşturan dört hücre, y; 1 vb. değerini alır. Tablo 2.4.2'de. Karnaugh haritasının n=4 değişken için işaretlenmesi gösterilmiştir.

Minimal bir DNF oluşturmak için şunları gerçekleştiriyoruz: yapıştırma prosedürü "1". Birbirine yapışan "1" değerleri komşu hücrelere karşılık gelir, yani. yalnızca bir değişkenin değerinde farklılık gösteren hücreler ( grafik gösterimi dikey olarak ayrılmış veya yatay çizgi zıt uç hücrelerin yakınlığı dikkate alınarak).

“1”in yapıştırılması işlemi, Karnaugh haritasının tek hücrelerinin gruplar halinde birleştirilmesine indirgenir ve aşağıdaki kurallara uyulması gerekir;

1. Bir grupta yer alan hücre sayısı 2'nin katı olarak ifade edilmelidir; 2 m burada m=0,1,2,...

2. 2 m'lik bir hücre grubuna dahil olan her hücre, grupta m adet komşu hücreye sahip olmalıdır.

3. Her hücre en az bir gruba ait olmalıdır.

4. Her grup şunları içermelidir: maksimum sayı hücreler, yani hiçbir grup başka bir grubun içinde yer almamalıdır.

5. Grup sayısı minimum düzeyde olmalıdır.

Okuma fonksiyonu f yapıştırma grubuna göre şu şekilde gerçekleştirilir: tasarruf sağlayan değişkenler aynı değerler yapıştırma grubunun hücrelerinde birleşime girerler ve 1 değerleri değişkenlerin kendilerine karşılık gelir ve 0 değerleri onların olumsuzluklarına karşılık gelir.

Kapsam 1'i oluşturmaya yardımcı olan şablonlar sunuyoruz (değişkenlerin aynı olduğunu düşünüyoruz ancak bunları yazmayacağız). Gösterimi basitleştirmek için değişkenleri işaretlemeyeceğiz, ancak gösterimlerini tablo 2.4.1 ve 2.4.2'deki gibi tutacağız.

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

Örnek 2.4.1. MDNF'yi oluşturun.

Öncelikle herhangi bir kaplama olup olmadığına bakıyoruz_ 1 16 hücreden en az biri açıkta kalıyor 1. Böyle bir örtü yok. 8 hücreli kaplamalara geçiyoruz. Bakalım 8 hücreden 1'inde en az bir açık 1'i kaplayan kapak var mı. Böyle bir kapak yok. 4 hücreli kaplamalara geçiyoruz. Bakalım 4 hücreden 1 tanesinin örtüsü var mı, en az bir tanesi açıkta 1'i kaplıyor. Böyle iki tane örtü var. 2 hücreli kaplamalara geçiyoruz. Böyle bir kaplama var. Böylece 1'in tamamı kapsandı. Daha sonra, tüm birimlerin kapalı kalması için bazı kaplamaları kaldırabilir miyiz bir bakalım. Sonunda MDNF'yi yazıyoruz: f =x⋅z∨y⋅w∨y⋅z⋅w.

Yorum. Bir f fonksiyonunun minimum CNF'sini oluşturmak için, f fonksiyonu için minimum DNF'yi oluşturmak yeterlidir ve sonra

f =f ve De Morgan yasalarını kullanın.

Zhegalkin temeli S4=(∆,&,1)'de tanımlanan Boole fonksiyonları kümesine Zhegalkin cebiri denir.

Temel özellikler.

1. değişebilirlik

H1∆H2=H2∆H1, H1&H2=H2

2. çağrışımsallık

H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)

3. dağıtıcılık

H1&(H2∆H3)=(H1&H2)∆(H1&H3);

4. H&1=H, H&0=0, H∆0=H sabitlerinin özellikleri;

5. H∆H=0, H&H=H.

Açıklama 3.1.1. Diğer tüm Boole fonksiyonları Zhegalkin cebiri işlemleriyle ifade edilebilir:

Ÿ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.

Tanım. N değişkenli x 1 ,x 2 ,…,x n'nin Zhegalkin polinomu (polinom modulo 2), c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn formunun bir ifadesidir; burada k ile sabitler 0 veya 1 değerlerini alabilir.

Zhegalkin polinomu bireysel değişkenlerin ürünlerini içermiyorsa buna doğrusal (doğrusal fonksiyon) denir.

Örneğin, f=x∆yz∆xyz ve f1=1∆x∆y∆z polinomlardır, ikincisi doğrusal bir fonksiyondur.

Teorem 3.1.1. Her Boolean fonksiyonu, Zhegalkin polinomu biçiminde benzersiz bir şekilde temsil edilir.

Belirli bir fonksiyondan Zhegalkin polinomlarını oluşturmanın ana yöntemlerini sunalım.

1. Yöntem belirsiz katsayılar. Verilen f(x 1 ,x 2 ,…,xn) fonksiyonunu uygulayan istenen Zhegalkin polinomu P(x 1 ,x 2 ,…,x n) olsun. Bunu formda yazalım.

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 .

Bunu yapmak için doğruluk tablosunun her satırından sırasıyla x 1 , x 2 ,…, x n değerlerini atadık. Sonuç olarak, 2 n bilinmeyenli 2 n denklemden oluşan bir sistem elde ederiz. tek çözüm. Çözdükten sonra P(x 1 ,x 2 ,…,xn) polinomunun katsayılarını buluyoruz.

2. Formüllerin bir dizi bağlayıcı üzerinden dönüştürülmesine dayanan bir yöntem ( ÿ,&}. Verilen f(x 1 ,x 2 ,…,x n) fonksiyonunu gerçekleştirerek, (Ÿ,&) bağlaçları kümesi üzerinde bir F formülü oluşturun. Daha sonra A formunun alt formüllerini her yerde A∆1 ile değiştirin, dağıtım yasasını kullanarak parantezleri açın (bkz. özellik 3) ve ardından 4 ve 5 özelliklerini uygulayın.

Örnek 3.1.1. f(x,y)=xØy fonksiyonu için bir Zhegalkin polinomu oluşturun.

Çözüm. 1 . (belirlenemeyen katsayılar yöntemi). Gerekli polinomu formda yazalım.

P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Doğruluk tablosunu kullanma

X	0	0	1	1
sen	0	1	0	1
xØy	1	1	0	1

f(0,0)=P(0,0)= c 0 =1, f(0,1)=P(0,1)= c 0 ∆ c 2 =1, f(1,0) olduğunu buluruz =P(1,0)= c 0 ∆ c 1 =0, f(1,1)=P(1,1)= c 0 ∆c 1 ∆c 2 ∆c 12 =1

Sürekli olarak c 0 =1, c 1 =1, c 2 =0, c 12 =1'i bulduğumuz yerden. Bu nedenle xØy=1∆x∆xy (ifade 3.1 ile karşılaştırın).

2.(Formül dönüştürme yöntemi.) Sahibiz

x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .

Zhegalkin cebirinin (diğer cebirlerle karşılaştırıldığında) avantajının, Boole fonksiyonlarının dönüşümlerini oldukça basit bir şekilde gerçekleştirmeyi mümkün kılan mantığın aritmetizasyonu olduğuna dikkat edin. Boolean cebirine göre dezavantajı formüllerin hantallığıdır.

Mantık cebirini oluştururken şunu kullandık: işlevsel yaklaşım. Ancak bu cebiri yapıcı bir şekilde oluşturmak mümkün olacaktır. Öncelikle çalışma nesnelerini (ifadeleri) tanımlayın, bu nesneler üzerindeki işlemleri tanıtın ve özelliklerini inceleyin. Resmi tanımları verelim.

Söyleyerek hadi arayalım bildirim cümlesi Zamanın belirli bir noktasında bunun doğru (değer I veya 1) veya yanlış (değer L veya 0) olup olmadığı açıkça söylenebilir. Örneğin, "5 bir asal sayıdır", "Esc tuşuna basıldı" vb. “not”, “and”, “or”, “if,...then”, “if and only if” bağlaçlarının kullanımı (bunlar “Ÿ”, “&”, “¤”, “Ø” işlemlerine karşılık gelir) , “~” » buna göre), daha karmaşık ifadeler (cümleler) oluşturulabilir. Önermesel cebir bu şekilde oluşturulur.

Karmaşık ifadelerin kaydını kolaylaştırmak için bağlaçların önceliği getirilmiştir: “Ÿ”, “&”, “¤”, “Ø”, “~”, bu da gereksiz parantezlerin atlanmasına yardımcı olur.

Basit ifadelere önermesel değişkenler diyoruz.

Formül kavramını tanıtalım.

1. Önerme değişkenleri formüllerdir.

2. A, B formül ise ŸA, A⁄B, A¤B, AØB, A~B ifadeleri formüldür.

3. Formüller yalnızca 1. ve 2. paragraflara uygun olarak oluşturulan ifadelerdir.

Önerme değişkenlerinin tüm değerleri için VE değerini alan formüle denir totoloji (veya genel olarak geçerli), ve önermesel değişkenlerin tüm değerleri için A değerini alan bir formüle denir çelişkili (veya imkansız)

Önermesel cebirin özelliklerinin açıklaması Boolean cebirindeki karşılık gelen fonksiyonların tanımına benzer ve bunları atladık.

Bu bölümdeki çalışmanın konusu yüklemler (rastgele kümelerin bir dizi ifade halinde eşleştirilmesi) olacaktır. Aslında geçiş yapıyoruz yeni seviye soyutlamalar, okulda yapılan türden bir geçiş - gerçek sayıların aritmetiğinden sayısal fonksiyonların cebirine.

Tanım 2.1 x 1 ,x 2 ,…,xn keyfi nitelikteki değişkenlerin sembolleri olsun. Bu değişkenlere konu değişkenleri adını vereceğiz. Değişken kümeleri (x 1 ,x 2 ,…,x n), konu alanı adını vereceğimiz M=(M1,M2,…Mn) kümesine ait olsun (yani x i œM i, burada Mi, etki alanı olarak adlandırılır) değişkenin tanımı xi). Yerellik yüklemi n (n-yer yüklemi) üzerinde tanımlandı konu alanı M, ya AND değerini ya da L değerini alan mantıksal bir fonksiyondur.

Örnek 4.2.1. D(x1,x2) = “X1 doğal sayısı, x2 doğal sayısına (kalansız olarak) bölünür.” - bir çift kümesinde tanımlanan iki basamaklı bir yüklem doğal sayılar M=NäN. Açıkçası, D(4,2) = Ve, D(3,5) = 0.

Örnek 4.2.2. Q(x) ==“x 2<-1, хœR» - одноместный предикат, определенный на множестве gerçek sayılar M=R. Q(1) = А, Q(5) = А olduğu açıktır ve genel olarak Q(x) yüklemi aynı şekilde yanlıştır, yani

Tüm xœR için Q(x) = А.

Örnek 4.2.3. B(x,y,z) = “x 2 +y 2

M üzerinde tanımlanan bir P yüklemi, konu değişkenlerinin herhangi bir değeri için VE değerini alırsa aynı şekilde doğru olarak adlandırılır; Konu değişkenlerinin herhangi bir değeri için A değerini alırsa, P yüklemi aynı şekilde yanlış olarak adlandırılır. Örnek 4.2.2'deki Q yüklemini. aynı şekilde yanlıştır.

Yüklemler, mantıksal işlemlerin tanıtıldığı bir dizi ifadedeki değerleri olan işlevler olduğundan, bu işlemler doğal olarak yüklemler için tanımlanır. P ve Q, M üzerinde tanımlanan yüklemler olsun. Daha sonra

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) P ve Q yüklemleri, tanımlı Herhangi bir (x 1 ,x 2 ,…, x n) kümesi için P(x 1 ,x 2 ,…,xn)=Q(x 1 ,x 2 ,…,xn) ise M üzerindeki eşdeğer denir (P=Q yazın) ) M'den konu değişkenleri .

Teorem 4.2.1 M üzerinde tanımlanan n-ary yüklemler kümesi bir Boolean yüklem cebiri oluşturur. Dolayısıyla temel eşdeğerlikler onlar için geçerlidir (bkz. §1.6).

P(x 1 ,x 2 ,…,xn) M üzerinde tanımlı n'li bir yüklem olsun. x i ='yi sabitleyelim. A. (n-1)-ary yüklemini Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) şu şekilde tanımlayalım: Q(x 1 ,x 2 ,…,xk-1,xk +1, xn)=P(x 1 ,x 2 ,…,xk1, A,xk+1,xn). Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) yükleminin P(x 1 ,x 2 ,…,xn) yükleminden i- değerinin sabitlenmesiyle elde edildiğini söylüyorlar. inci değişken: x i = A .

Tanım 4.3.1 . P(x) tekli bir yüklem olsun. Bununla "xP(x) ("herhangi bir x P(x) için" şeklinde okuyun) şeklinde bir ifadeyi ilişkilendirelim; bu ancak ve ancak P(x)'in aynı şekilde doğru bir yüklem olması durumunda doğrudur. x değişkenine evrensel bir niceleyici eklenerek P yükleminden elde edildiği söylenir.

Tanım 4.3.2. P(x) tekli bir yüklem olsun. Bunu $xP(x) ("x P(x) var" şeklinde okuyun) şeklinde bir ifadeyle ilişkilendirelim; bu ifade ancak ve ancak P(x)'in aynı şekilde yanlış bir yüklem olması durumunda yanlıştır. $xP(x) ifadesinin, x değişkenine varoluşsal bir niceleyicinin eklenmesiyle P yükleminden elde edildiği söylenir.

Not 1. Nicelik belirteçleri için " ve $ simgeleri, İngilizce kelimelerin ilk harfleri olan sırasıyla ters çevrilmiş Latin A ve E harfleridir. Tüm- Tüm, Var olmak- var olmak.

Not 2.İfadeler, değişken içermeyen, yani 0 basamaklı yüklemler (veya herhangi bir yerelliğin yüklemleri) olarak kabul edilebilir.

P(x 1 ,x 2 ,…,xn) M üzerinde tanımlı bir n-ary yüklemi olsun. İçinde x 1 ,x 2 ,…,x k-1 ,x k değişkenlerinin değerlerini sabitleyelim. +1 ,xn . Ortaya çıkan tekli Q(x k) yüklemine evrensel (varlık) bir niceleyici ekleriz ve bir ifade elde ederiz. Böylece, x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n değişkenlerinin sabit bir değer kümesi, evrensellik (varlık) niceleyicisini kullanan bir ifadeyle ilişkilendirilir. x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n değişkenlerinin bu (n-1)-ary yükleminin orijinal P(x 1 ,x 2 ,…, yükleminden elde edildiği söylenir) x n) k'inci değişkene bir niceleyici evrenselliği (varlığı) ekleyerek. Bu yüklem şu şekilde gösterilir: “x'den P(x 1 ,x 2 ,…,x n)'ye ($x'den P(x 1 ,x 2 ,…,x n)) k'inci değişken hakkında (artık mevcut değil) evrenselliğin (varoluşun) niceleyicisine bağlı olduğunu söylüyorlar.

Örnek 4.3.1. D(x1,x2) = “X1 doğal sayısı x2 doğal sayısına (kalansız) bölünebilir.” - iki basamaklı yüklem.

Değişkenlerine art arda niceleyiciler atayalım. Açık ki

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.

Böylece (son örnekte 7 ve 8'i karşılaştırarak) teoremi kanıtladık:

Tipik olarak bağlayıcılar ve niceleyiciler öncelik sırasına göre şu şekilde sıralanır: Ÿ, ", $, &, ¤, Ø, ~.

Teorem 4.3.1. Genel olarak konuşursak, karşıt nicelik belirleyiciler gidip gelmez.

Teorem 4.3.2.(Nicelik belirteçleri içeren temel eşdeğerlikler) Aşağıdaki eşdeğerlikler gerçekleşir:

1. De Morgan'ın yasaları

∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x)

2. Değişebilirlik

∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y)

3. Dağıtıcılık

∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x)

4. Niceleyicilerin etkisine ilişkin sınırlamalar

∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y)

5. İki basamaklı herhangi bir yüklem için

∃y∀xP(x,y) →∀x∃yP(x,y) =1

Biçimsel teori(veya hesap) e- Bu:

1. set A karakterler oluşturan alfabe ;

1. birçok F alfabedeki kelimeler A, F Ã A bunlara denir formüller ;

3. alt küme B formüller, B Ã F , bunlara denir aksiyomlar;

4. birçok ilişki R adı verilen bir dizi formül üzerinde çıkarım kuralları.

Çok sayıda karakter A sonlu veya sonsuz olabilir. Genellikle semboller oluşturmak için, gerektiğinde doğal sayıların endeks olarak atandığı sonlu bir harf kümesi kullanılır.

Çok sayıda formül F genellikle tümevarımsal tanımla, örneğin resmi bir dilbilgisi aracılığıyla verilir. Kural olarak bu küme sonsuzdur. Setler A Ve F toplu olarak belirlemek dil , veya imza , biçimsel teori.

Birçok aksiyom B sonlu veya sonsuz olabilir. Aksiyomlar kümesi sonsuzsa, kural olarak, aksiyom şemasından belirli aksiyomlar oluşturmak için sonlu bir aksiyom şemaları ve kurallar seti kullanılarak belirtilir.

Çok sayıda çıkarım kuralı R kural olarak elbette. Yani, hesap e dört tane var (A, F, B, R) .

Matematikte türetme yoluyla e herhangi bir k (1§k§n) için Fk formülü ya Y hesabının bir aksiyomu ya da çıkarım kuralıyla elde edilen önceki herhangi bir formülün doğrudan sonucu olacak şekilde F 1 , F 2 ,…, Fn formüllerinin bir dizisidir .

G formülünün bir türevi veya ispatı olarak adlandırılan bir F 1 ,F 2 ,…,Fn ,G sonucu varsa, bir G formülüne Y hesabının teoremi denir (Y'de türetilebilir veya Y'de kanıtlanabilir). teorem G.

Bu şu şekilde yazılır: F 1,F 2,…,F n + G.

Matematik e isminde tutarlı formüllerinin tümü kanıtlanabilir olmasa da. Tutarlılığın başka bir tanımı verilebilir: Bir analizde F ve ŸF formülleri (F'nin olumsuzu) aynı anda çıkarsanamıyorsa tutarlı olarak adlandırılır.

Matematik e isminde tamamlamak(veya yeterli) eğer her doğru M ifadesi teorinin bir teoremine karşılık geliyorsa e .

Biçimsel teori e isminde karar verilebilir Teorinin herhangi bir formülü için bu formülün teorinin teoremi olup olmadığını belirleyen bir algoritma varsa e ya da değil.

Biçimsel hesap kavramını kullanarak önermeli hesabı (PS) tanımlarız.

Alfabe IW şunlardan oluşur:

1. edebiyat A, B, Q, R, P ve diğerleri, muhtemelen indekslerle birlikte

(bunlara önermesel değişkenler denir),

2. mantıksal semboller(bağlar) Ÿ, &, ¤, Ø, 3. yardımcı karakterler (,).

Çok sayıda formül IV endüktif olarak belirlenir:

1. tüm önerme değişkenleri IV formülleridir;

2. A, B formül IV ise , toŸA, A⁄B, A¤B, AØB - formüllerIV ;

3. Bir ifade ancak ve ancak “1” ve noktaları kullanılarak belirlenebiliyorsa IV formülüdür.

Böylece herhangi bir IV formülü, Ÿ, ⁄, ¤, Ø bağlaçları kullanılarak önerme değişkenlerinden oluşturulur.

Gelecekte formül yazarken, önceki bölümdeki kuralların aynısını kullanarak bazı parantezleri atlayacağız.

Aksiyomlar IV aşağıdaki formüllerdir (herhangi bir A,B,C formülü için)

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);

Belirtilen formüllere IV aksiyom şemaları denir . Belirli formülleri herhangi bir şemaya yerleştirirken, aksiyom şemasının özel bir durumu elde edilir.

Çıkarım kuralı IE'de bir sonuç kuralı vardır (modus ponens): A ve AØB türetilebilir formüllerse, o zaman B de türetilebilir

Sembolik olarak şöyle yazılır: bir, bir B → B .

Örneğin A⁄B ve A⁄BØ(AØC) ifadeleri türetilebilirse, o zaman AØC ifadesi de çıkarım kuralına göre türetilebilir.

Bir G formülünün, F 1 ,F 2 ,...,Fn formüllerinden (F 1 ,F 2 ,...,F n +G olarak gösterilir) F 1 ,F 2 ,... formüllerinden oluşan bir dizi varsa çıkarılabileceği söylenir. ,F k ,G , burada herhangi bir formül ya bir aksiyomdur ya da F 1,F 2,...,Fn formülleri listesine aittir (hipotezler olarak adlandırılır) veya kuralına göre önceki formüllerden elde edilir çıkarım. G formülünün “(+G ile gösterilir)'den türetilebilirliği, G'nin bir IV teoremi olduğu gerçeğine eşdeğerdir.

Örnek 5.2.1. AØA formülünün IV'te türetilebildiğini gösterelim. Bunu yapmak için bu formülün türetilmesini oluşturacağız:

1) aksiyom 2'de B'yi AØA ile, C'yi A ile değiştirin.

Aksiyomu anlıyoruz

(AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA));

2) aksiyom 1'de B'yi A ile değiştiririz. AØ(AØA) elde ederiz;

3) modus ponens'e göre 1 ve 2'den şu sonuca varıyoruz

(AØ((AØA)ØA))Ø(AØA);

4) aksiyom 1'de B'yi AØA ile değiştiririz. AØ((AØA)ØA);

5) paragraflardan. 3 ve 4 çıkarım kuralına göre +AØA doğrudur.

Teorem 5.2.1.

1. F 1 ,F 2 ,…,Fn,A,B IV formülleri ise, Г=(F 1 ,F 2 ,…,Fn), Г+A, sonra Г,B+A. (hipotez sayısını artırabilirsiniz).

2. Ancak ve ancak F 1 ,F 2 ,…,F n +A ise, F 1 ⁄F 2 ⁄…⁄F n +A (birçok hipotezin tek bir hipoteze indirgenmesi).

Teorem 5.3.1. (kesinti teoremi)

Г,B+A ise Г+BØA, burada Г bazı formüllerden oluşan Г=(F 1 ,F 2 ,…,F n ) kümesidir.

Sonuç 5.3.1. O zaman ve yalnızca F 1 ,F 2 ,…,F n +A ise, ne zaman

Kanıt. F 1 ,F 2 ,…,F n +A olsun. Daha sonra tümdengelim teoremini uygulayarak F 1 ,F 2 ,…,F n-1 +F n ØA elde ederiz. Benzer şekilde F 1 ,F 2 ,…,F n-2 +F n 1Ø(F n ØA), vb. İşlemi istenilen sayıda sürdürerek şunu elde ederiz:

F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…)

Yeterliliği kanıtlamak için +B olduğunu varsayalım; burada B=F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Teorem 5.2.1., madde 1'i kullanalım:

F 1 +B . Sonuç kuralına göre F 1 + (F 2 Ø…Ø(F n-1 Ø(F n ØA))…), n adımdan sonra F 1 ,F 2 ,…,F n +A elde ederiz. .

Böylece, Sonuç 5.3.1. sayesinde, formül A'nın F 1,F 2,…,F n formüllerinden çıkarılabilirliğinin kontrol edilmesi, formülün kanıtlanabilirliğinin kontrol edilmesine indirgenmiştir.

F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…).

A formülünün değeri, önerme değişkenlerinin herhangi bir değer kümesi için bire eşitse, A formülünün aynı şekilde doğru (veya totoloji) olarak adlandırıldığını hatırlayın. Aşağıdaki teorem, bir formülün kanıtlanabilirliğinin doğrulanmasını, onun özdeş doğruluğunun doğrulanmasına indirgemektedir.

Teorem 5.3.2. (tamlık hakkında). A formülü ancak ve ancak A'nın tamamen doğru olması durumunda kanıtlanabilir (totoloji): +A ‹ A-totoloji.

Dolayısıyla bir formülün kanıtlanabilir olup olmadığını belirlemek için doğruluk tablosunu derlemek yeterlidir. Bilindiği gibi doğruluk tablosu oluşturmak için etkili bir algoritma vardır ve dolayısıyla IV çözülebilir.

Örnek 5.3.1. P+P olduğunu kanıtlayalım. Tümdengelim teoremine göre bu +(PØP)'ye eşdeğerdir. Tamlık teoremine göre (РØР)'nin totoloji olduğunu kanıtlamak yeterlidir. (РØР) formülü için doğruluk tablosunun derlenmesi , (РØР) ifadesinin tamamen doğru olduğuna ve dolayısıyla kanıtlanabilir olduğuna inanıyoruz.

Teorem 5.3.3. (tutarlılık hakkında). IW hesabı tutarlıdır.

Kanıt. Tamlık teoremine göre, aynı şekilde doğru olmayan herhangi bir formül IV'te kanıtlanamaz. Örneğin böyle bir formül A⁄(ŸA) formülüdür.

Г formülleri kümesine denir tartışmalı , eğer Г+А⁄(ŸА) . Eğer Г çelişkili bir formüller dizisi ise, bu gerçeği Г+ ile göstereceğiz.

İfade 5.3.1. Formül A, ancak ve ancak Г»(ŸA) kümesinin çelişkili olması durumunda Г formüller kümesinden çıkarılabilir.

Otomatik teorem kanıtlama, mantıksal programlamanın, yapay zekanın ve programlamadaki diğer modern eğilimlerin temel taşıdır. Genel olarak konuşursak, keyfi bir A formülü verildiğinde, sonlu sayıda adımdan sonra A'nın Y hesabında çıkarılabilir olup olmadığının belirlenebileceği bir algoritma olmayabilir. Bununla birlikte, bazı basit biçimsel teoriler (örneğin, önermeler hesabı) ve bazı basit formül sınıfları (örneğin, tekli yüklemli uygulamalı yüklem hesabı) için, otomatik teorem kanıtlamaya yönelik algoritmalar bilinmektedir. Aşağıda, önermeler hesabı örneğini kullanarak, teoremleri otomatik olarak kanıtlamanın klasik ve aynı zamanda popüler bir yöntemi olan çözümleme yönteminin temellerini özetliyoruz.

Argüman
İşlev Numarası

X mantıksal bir değişkense ve σœ(0,1) ise ifadenin

x σ = xx if σσ == 10 veya x σ = 10 eğer x x =≠σσ ise denir mektup. x ve Ÿx harflerine denir aykırı. kavuşum harf birleşimi denir. ayrık harflerin ayrılması denir.

D 1 = B 1 ∨ A, D 2 = B 2 ∨ A cümle olsun. B 1 ¤B 2 cümleciği denir çözücü D 1 ve D 2 maddeleri A harfiyle gösterilir ve res A (D 1,D 2) ile gösterilir. D 1 ve D 2 cümleciklerinin çözücüsü bir harfle çözücüdür ve res(D 1 ,D 2) ile gösterilir. Açıkçası res(A,ŸA)=0. Gerçekten, çünkü A=A¤0 ve ŸA=ŸA¤0, ardından res(A,ŸA)=0¤0=0. D 1 ve D 2 cümleleri zıt harfler içermiyorsa, çözücüleri yoktur.

Örnek 5.5.1. Eğer

D 1 =A¤B¤C, D 2 = A ∨ B ∨ Q, o zaman

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) mevcut değil.

Bildirim 5.5.1. Res(D 1 ,D 2) mevcutsa, D 1 ,D 2 + res(D 1 ,D 2).

S=(D 1 ,D 2 ,…,Dn) cümleciklerin kümesi olsun.

F 1 , F 2 ,…, F n formüllerinden oluşan bir diziye, eğer her F k formülü için koşullardan biri karşılanıyorsa, S'den kararlı türetme denir:

2. j, k var

Teorem 5.5.1. (çözüm yönteminin bütünlüğü hakkında). Bir S cümlecikleri dizisi ancak ve ancak S'den 0 ile biten kesin bir sonuç varsa çelişkilidir.

Çözünürlük yönteminin, bir F formülünün belirli bir F 1,F 2,…,Fn formülleri kümesinden çıkarılabilirliğini kontrol etmek için kullanılabileceğini unutmayın. Aslında F 1 ,F 2 ,…,F n +F koşulu F 1 ,F 2 ,…,F n ,ŸF+ koşuluna eşdeğerdir (birçok formül çelişkilidir), bu da Q+ koşuluna eşdeğerdir, burada Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Q formülünü CNF'ye indirgeyelim: Q=D 1 ⁄D 2 ⁄...⁄Dm, sonra Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Dolayısıyla, F 1 ,F 2 ,...,F n +F'nin çıkarsanabilirliğini kontrol etme görevi, S=(D 1 ,D 2 ,...,D m ) cümlecikleri kümesinin tutarsızlığını kontrol etmeye gelir. Bu, S'den kesin bir 0 sonucunun varlığına eşdeğerdir.

Örnek 5.5.2.Çözünürlük yöntemini kullanarak AØ(BØC), CDØE, ŸFØD&(Ÿ)E + AØ(BØF) oranını kontrol edin.

Açıklama 5.3.1'e göre. kontrol etmem gerekiyor

birçok formülün tutarsızlığı

S = (AØ(BØC), CDØE, ŸFØD&(Ÿ)E, Ÿ(AØ(BØF))).

Tüm formülleri sunuyoruz. S'den KNF'ye:

S = (A ∨ B ∨ C,C ⋅ D ∨ E, F ∨ D ⋅ E, A ∨ B ∨ F) == (A ∨ B ∨ C, C ∨ D ∨ E, (F ∨ D) ⋅ (F ∨ E), Bir ⋅ B ⋅ F) .

Böylece, S = (A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F) cümlecikleri kümesi elde ederiz.

0 ile biten S'den kesin bir sonuç çıkaralım:

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 .

Dolayısıyla, AØ(BØF) formülünün AØ(BØC), CDØE, ŸFØD&(Ÿ)E formülleri kümesinden çıkarılabileceği sonucuna varıyoruz.

Çözümleme yönteminin, belirli bir S cümleleri kümesinin olası karşılanabilirliğini keşfetmek için yeterli olduğuna dikkat edin. Bunu yapmak için, S kümesinden kesin çıkarımlarla elde edilen tüm cümleleri S kümesine dahil edelim. Çözümleme yönteminin tamlığı hakkındaki teoremden takip ediyor

Sonuç 5.5.1. Eğer bir S cümleleri kümesi tüm elemanlarının çözümleyicilerini içeriyorsa, o zaman S ancak ve ancak 0-S ise karşılanabilir.

Bölüm VI. Algoritma teorisinin unsurları.

§6.1. Algoritma tanımı.

Modernitenin karakteristik bir özelliği, insan faaliyetinin çeşitli alanlarındaki sorunların (görevlerin) çözümünde bilgisayarların yaygın olarak kullanılmasıdır. Ancak problemin öncelikle algoritmik olarak çözülmesi gerekiyor. belirli bir türdeki tüm problemlerin çözümü için nihai sonucun elde edilebileceği resmi bir reçete verilmelidir (bu, bir algoritmanın katı olmayan, sezgisel bir kavramıdır). Örneğin, iki doğal sayının en büyük ortak bölenini bulmaya yönelik bir algoritma a, b, şuna benziyor:

1) sayıyı genişlet A asal faktörlere göre;

2) 1. adımı tekrarlayın B Ve 3. adıma gidin;

3) açılımlardan ortak asal faktörlerin çarpımını oluşturun A Ve B genişletmelere dahil edilme endekslerinin en küçüğüne eşit endekslerle.

Bu örneği analiz ettikten sonra algoritmanın en önemli özelliklerine (özelliklerine) dikkat çekiyoruz:

1. Kütle karakteri- Algoritmanın tek bir probleme değil, bir problem sınıfına uygulanabilirliği.

2. Ayrıklık- algoritmanın bireysel aşamalarına (adımlarına) açık bir döküm.

3. Determinizm- Bir aşamadan diğerine geçişin her zaman açık olduğu, yürütme aşamalarının böyle bir organizasyonu.

4. Uzuv- Belirli bir sorunu çözmek için bir algoritma uygularken bir sonuç elde etmek için, algoritmanın sonlu bir adım dizisi gerçekleştirilir:

Bir algoritmanın varlığı tek başına bir algoritmanın varlığının kanıtı olarak hizmet ediyorsa, yokluğunu kanıtlamak için bir algoritmanın kesin bir matematiksel tanımına sahip olmanın gerekli olduğunu unutmayın.

Algoritma kavramını resmileştirme girişimleri yaratılışına yol açtı Turing makineleri Algoritmayı uygulayan hayali bir cihaz gibi. Algoritma kavramını tanımlamanın bir diğer adımı da algoritmanın görünümüydü. özyinelemeli işlevler , algoritma kavramını resmileştiren ve sezgisel hesaplanabilirlik kavramını uygulayan işlevler olarak. Kısa süre sonra özyinelemeli işlevler kümesinin Turing makinelerinde hesaplanabilen işlevler kümesiyle çakıştığı keşfedildi. Daha sonra ortaya çıkan ve algoritma kavramını açıkladığını iddia eden yeni kavramların, Turing makinelerinde hesaplanabilen işlevlere, dolayısıyla özyinelemeli işlevlere eşdeğer olduğu ortaya çıktı. Algoritmanın ne olduğuna dair devam eden tartışmanın sonucu, artık Church'ün tezi olarak adlandırılan bir açıklamaydı.

Church'ün tezi. Algoritma kavramı veya bazı mekanik aygıtlarla hesaplanabilirlik, Turing makinelerindeki hesaplanabilirlik kavramıyla (ve dolayısıyla özyinelemeli fonksiyon kavramıyla) örtüşür. Başka bir deyişle algoritma, işlevsel bir diyagramla temsil edilebilen ve bazı Turing makineleri tarafından uygulanabilen bir süreçtir.

§6.2. Turing makinesi.

Turing makinesi, bir bant, bir kontrol cihazı ve bir okuma kafasından oluşan (soyut) bir cihazdır.

Bant hücrelere bölünmüştür. Her hücre tam olarak bir karakter içerir harici alfabe bir=( bir 0, bir 1 ,…, BİR ). Bazı semboller (bunu göstereceğiz) Ÿ A alfabesinin ) harfi boş olarak adlandırılır ve şu anda boş bir karakter içeren herhangi bir hücreye (o anda) boş hücre adı verilir. Bandın her iki yönde de potansiyel olarak sınırsız olduğu varsayılmaktadır.

Kontrol cihazı zamanın her anında kümeye ait bir q j durumundadır Q=(q 0 , q 1 ,..., q m )(m=l). Q kümesi denir iç alfabe . Bu koşullardan biri (genellikle q 0) final olarak adlandırılır ve bazıları (genellikle q 1) - ilk.

Okuma kafası bant boyunca hareket ederek herhangi bir zamanda bandın tam olarak bir hücresini tarar. Baş, gözlenen hücrenin içeriğini okuyabilir ve gözlenen sembolün yerine dış alfabeden bazı yeni sembolleri içine yazabilir. A(muhtemelen aynısı).

Çalışma sırasında kontrol cihazı, bulunduğu duruma ve kafa tarafından görüntülenen sembole bağlı olarak dahili durumunu değiştirir. Q. Daha sonra başa, izlenen hücredeki harici alfabeden belirli bir karakterin yazdırılması emrini verir. A, ve sonra başa ya yerinde kalmasını ya da bir hücreyi sağa kaydırmasını ya da bir hücreyi sola taşımasını emreder. Son duruma gelindiğinde makine çalışmayı durdurur.

Banttaki yapılandırma (veya makine sözcüğü) aşağıdakilerin oluşturduğu kümeye denir:

1) sıra A ben (1) , A ben (2) ,...,A ben(ler) harici alfabedeki karakterler A teyp hücrelerine kaydedildi, burada A Ben (1) .- soldaki ilk hücrede yazılan sembol vb. (bu tür herhangi bir diziye denir tek kelimeyle), 2) dahili belleğin durumu qr;

3) sayı k algılanan hücre

Makine konfigürasyonunu şu şekilde yazacağız:

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)

Burada R- algılanan hücre kesirli olarak vurgulanır.

Makine dahili durumda ise ben, simgesi olan bir hücreyi kabul eder sen, bu hücreye bir sonraki anda bir sembol yazar bir r, iç duruma geçer qs ve bant boyunca hareket ediyor, ardından makinenin komutu yürüttüğünü söylüyorlar q ben a sen Æ q s a r S, burada S sembolü aşağıdaki değerlerden birini alabilir: -1 – kafayı sola kaydırın; +1 - başın sağa kayması; 0 – kafa yerinde kalır. Bir Turing makinesinin çalışmasını belirleyen tüm komutların (beşlilerin) listesine denir programı bu araba. Makine programı genellikle bir tablo biçiminde belirtilir. Yani yukarıda kavşaktaki tabloda açıklanan durum için

çizgiler A sen ve sütun ben ayakta kalacak q s a r S(bkz. tablo 6.2.1)

Tablo 6.2.1.

q 0 … ben … qm
…
sen Q S A RS
…
Program bir çift için araba içeriyorsa ( q ben, sen ) beşi eksik, o zaman çizginin kesişimindeki tabloda sen ve sütun ben bir tire eklenir.

Bu yüzden, Bir Turing makinesi tanımı gereği, kit M=(A,Q,P), Nerede A- harici alfabe, Q- iç durumların alfabesi, P- program.

Kasete yazılan P kelimesiyle çalışmaya başlayan bir makine son duruma ulaşırsa, o zaman çağrılır. bu kelimeye uygulanabilir. Çalışmasının sonucu, kasete son haliyle kaydedilen kelimedir. Aksi takdirde makinenin R kelimesine uygulanamayacağı söylenir.

Örnek 6.2.1. Tekli sayı sisteminde yazılan (yani tek sembol kullanılarak yazılan) doğal sayıları toplayan bir Turing makinesi oluşturalım. |. Örneğin 5=|||||.).

Çözüm. Alfabeyi düşünün A = {|, +, ⁄}.

Makine aşağıdaki program tarafından belirlenir:

Bu makinenin çalışması sırasında sırasıyla ortaya çıkan konfigürasyonları orijinal ||+ ||| kelimesi üzerine yazalım. yani 2+3. Burada konfigürasyonu kaydederken şu kuralı kullanacağız: Makinenin bulunduğu durum, gözlenen harfin hemen arkasına parantez içinde yazılır.

Örnek 6.2.2. Tekli sayı sisteminde yazılan doğal sayıları ikiye katlayan bir Turing makinesi oluşturun.

Çözüm. Gerekli makineyi A=(|, α, ⁄) alfabesiyle oluşturacağız. Böyle bir makinenin programı şöyle görünebilir:

Ortaya çıkan makineyi kelimeye uygulayalım || .

Yeni bir α harfinin tanıtılması ve orijinallerinin değiştirilmesi | α üzerinde orijinalin ayırt edilmesini sağlar | ve yeni (atanmış) | . Durum q 1 değiştirme sağlar | α'da , durum q 2α için arama sağlar , değiştirilmesi amaçlanıyor | ve α'nın algılanmaması durumunda makinenin durdurulması, 3. soru tamamlanmasını sağlar | α'nın yerini alması durumunda |.

§6.3. Özyinelemeli işlevler

Bu paragrafta anlaşalım

1. N doğal sayılar kümesi 0 (sıfır) içerir, yani. N=(0,1,2,3,...);

2. dikkate alınan işlevler f=f(x 1 ,x 2 ,…,x n) yalnızca değişkenler N'den değer aldığında tanımlanır, yani. xiœN;

3. DŒN fonksiyonlarının değer aralığı;

4. Söz konusu fonksiyonlar f=f(x 1 ,x 2 ,…,x n) kısmen tanımlanabilir, yani. tüm doğal sayı kümeleri için tanımlanmamıştır.

Göz önünde bulundurarak tanıtalım basit işlevler

o(x)=0, s(x)=x+1, ben m n (x 1 ,..., x n) = xm

Bu işlevler uygun bir mekanik cihaz (örneğin Turing makinesi) kullanılarak hesaplanabilir. Verilen bir veya daha fazla fonksiyona dayalı olarak yeni fonksiyonlar oluşturan operatörleri tanımlayalım.

Süperpozisyon operatörü. K değişkenin f(x 1 ,x 2 ,…,x k) fonksiyonu ve k fonksiyonu f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n) olsun n değişken verilmiştir. f,f 1 ,…,f k fonksiyonlarının süperpozisyonu j(x 1 ,x 2 ,…,x n)= f(f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1) fonksiyonudur. ,x 2 ,…,x n))

f,f 1 ,…,f k fonksiyonlarına S k+1 süperpozisyon operatörünü uygulayarak j fonksiyonunun elde edildiğini söyleriz ve j=S k+1 (f,f 1 ,…,f k) yazarız. Örneğin, S 2 (s, o)=s(o(x)) yani özdeş olarak 1'e eşit bir fonksiyon ve S 2 (s,s)=s(s(x)) bir y(x)=x+2 fonksiyonudur.

İlkel özyineleme operatörü. g(x 1 ,x 2 ,…,x n) ve h(x 1 ,x 2 ,…,x n+2) fonksiyonları verilsin. f(x 1 ,x 2 ,…,x n+1) fonksiyonunu oluşturalım. x 1 ,x 2 ,…,x n değerleri sabit olsun. O zaman şunu varsayıyoruz: 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))

Bu eşitlikler f(x 1 ,x 2 ,…,x n+1) fonksiyonunu benzersiz bir şekilde tanımlar. Bir f fonksiyonuna, ilkel yineleme operatörü R kullanılarak elde edilen bir fonksiyon denir. f=R(g,h) gösterimi kullanılır.

Bir fonksiyonun tümevarımsal tanımı (ilkel özyineleme operatöründe gösterilmiştir) matematikte alışılmadık bir durum değildir. Örneğin, 1) doğal üslü bir derece tümevarımsal olarak belirlenir: A 0 =1, A n+ 1 =bir n ÿ A ;

2) faktöriyel: 0!=1, (n+1)!= n!ÿ(n+1), vb.

Tanım. En basit o(x)=0, s(x)=x+1, I m n (x 1 ,..., x n) = x m'den süperpozisyon operatörleri ve ilkel özyinelemeyi sonlu sayıda uygulayarak elde edilebilecek fonksiyonlar denir ilkel olarak özyinelemeli.

u(x,y)=x+y fonksiyonunun ilkel yinelemeli olup olmadığını kontrol edelim. Aslında elimizde: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Bu bir ilkel yineleme şemasıdır, çünkü x= I 1 1 (x) ve u(x,y)+1=s(u(x,y))=S 2 (s,u). Burada g(x)= I 1 1 (x) ve h(x,y,u)=s(u)=S 2 (s, I 3 3).

Benzer şekilde m(x,y)=xÿy, d(x,y)=x y (tanım gereği 0 0 =1 olduğunu varsayıyoruz), fact(x)=x fonksiyonlarının da kanıtlanmış olduğu kanıtlanmıştır! ve diğerleri ilkel olarak özyinelemelidir.

Not; ilkel olarak özyinelemeli fonksiyonların her yerde tanımlandığı (yani argümanlarının tüm değerleri için tanımlandığı). Aslında en basit işlevler o, s, Her yerde tanımlıyım ve üst üste binme ve ilkel özyineleme işleçlerini her yerde tanımlanmış işlevlere uygulamak aynı zamanda her yerde tanımlanmış işlevler verir. Yani şöyle bir fonksiyon

=   x − y, eğer x ≥ y ise< y

x ise f(x,y) mevcut değildir

ilkel olarak özyinelemeli olamaz. Fonksiyon değerlerinin doğal sayılar olması (dolayısıyla negatif olmaması) gerektiğinden burada f(x,y)=x-y fonksiyonunu dikkate alma hakkımız yok. Ancak, işlevi göz önünde bulundurulabilir

÷ y = 0x − y eğer x x<≥y.y

İlkel olarak özyinelemeli olup olmadığını kontrol edelim. Öncelikle j(x)=xπ1 fonksiyonunun ilkel yinelemeli olduğunu kanıtlayalım. Aslında j(0)=0. j(y+1)=(y+1)π1=y, xπ1 fonksiyonu için ilkel bir yineleme şeması görevi görür. Son olarak, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy), xπy için ilkel bir yineleme şemasıdır.

İlkel özyinelemeli işlevlerden önemli ölçüde daha geniş bir işlev sınıfı, özyinelemeli işlevler sınıfıdır (aşağıdaki tanıma bakın). Literatürde bu işlevlere aynı zamanda denir. kısmen yinelenen . Bunları belirlemek için bir operatör daha tanıtıyoruz.

Minimizasyon operatörü. f(x 1 ,x 2 ,… ,x n ,x n+1) fonksiyonu verilsin. İlk n değişkenin bazı x 1 ,x 2 ,… ,x n değerlerini sabitleyelim ve f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1) hesaplayalım ), f(x 1 ,x 2 ,… ,x n ,2) vb. Eğer y, f(x 1 ,x 2 ,…) ifadesinin geçerli olduğu en küçük doğal sayı ise

X n ,y)=x n+1 (yani değerler f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f( x 1,x2,…

X n ,y-1) hepsi mevcut ve xn +1'e eşit değil), o zaman g(x 1 ,x 2 ,…

X n ,x n+1)=y. Böylece, g(x 1 ,x 2 ,… ,x n ,x n+1)=min(y|f(x 1 ,x 2 ,…,x n ,y)=x n+1).

eğer öyleyse sen hayır, o zaman f(x 1 ,x 2 ,… ,x n ,x n+1)'in tanımlı olmadığını düşünüyoruz. Yani üç durum mümkündür:

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) vardır ve xn +1'e eşit değildir ve 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) vardır ve xn +1'e eşit değildir, ancak f(x 1 ,x 2 ,…,x n ,y) yoktur;

3. f(x 1 ,x 2 ,… ,x n ,i) tüm iœN için mevcuttur ve xn +1'den farklıdır.

1. durum gerçekleşirse g(x 1 ,x 2 ,… ,x n ,x n+1)=y olur ve 2. veya 3. durum oluşursa g(x 1 ,x 2 ,… ,x n , x n +1) tanımlı değil. Bu şekilde elde edilen bir g fonksiyonuna minimizasyon operatörü kullanılarak f'den elde edildiği söylenir. M. g=Mf yazıyoruz.

Minimizasyon operatörü, ters fonksiyon operatörünün açık bir genellemesidir. Genelleme oldukça derindir, çünkü f fonksiyonunun bire bir olması gerekmemektedir (x n+1 değişkeninde)

Tanım. En basitinden türetilebilen işlevler o(x)=0, s(x)=x+1, ben m n (x 1 ,..., x n) = xm süperpozisyon operatörleri uygulanarak, ilkel özyineleme ve minimizasyon operatörleri sonlu sayıda çağrılır yinelemeli.

Özyinelemeli işlevler sınıfı, yalnızca her yerde tanımlanan işlevleri içermediği için, ilkel özyinelemeli işlevler sınıfından daha geniştir. Örneğin, fonksiyonun olduğunu kanıtlayalım.

=   x − y, eğer x ≥ y ise< y

x ise f(x,y) mevcut değildir

yinelemelidir. Aslında f(x,y)=min(z| y+z=x)'tir ve u(x,y)=x+y fonksiyonunun ilkel olarak özyinelemeli olduğu önceden belirlenmişti.

Özyinelemeli işlevler, bazı mekanik cihazların hesaplayabileceği işlevlere ilişkin sezgisel anlayışımızı yansıtır. Özellikle Turing makinelerinde hesaplanabilirler (önceki paragrafa bakınız). Tam tersine, Turing makinesinde hesaplanabilen her fonksiyon özyinelemelidir. Çok fazla zaman ve yer gerektireceğinden bu gerçeği kontrol etmeyeceğiz. Tam bir kanıt, örneğin A.I. Maltsev'in "Algoritmalar ve Özyinelemeli İşlevler" kitabında bulunabilir.

Doğal argümanların her fonksiyonunun, hatta tek bir argümanın her fonksiyonunun bile yinelemeli olmadığını unutmayın. Özyinelemeli olmayan fonksiyonların varlığı, algoritmik olarak çözülemeyen problemlerin varlığının “matematiksel nedenidir”.

§6.4. Algoritmik olarak çözülemeyen problemler.

Matematiğin çeşitli dallarında algoritmik olarak çözülemeyen problemler vardır; Henüz icat edilmediği için değil, prensipte imkansız olduğu için çözüm algoritması olmayan problemler. Elbette algoritmanın Turing makineleri ve özyinelemeli işlevler anlamında anlaşılması gerekir.

Bu problemlerden birini formüle edelim.

Turing makinesinin durma sorunu. Turing makinesi, sınırlı sayıda parametreyle tanımlanan bir nesnedir. Bir sonlu kümeden diğerine tüm kısmi eşlemeler verimli bir şekilde yeniden numaralandırılabilir. Bu nedenle her Turing makinesine bir sayı (doğal sayı) atanabilir. T(n), n numaralı bir Turing makinesi olsun. Boş bantla çalışmaya başlayan bazı makineler sonunda durur, bazıları ise süresiz olarak çalışır. Sorun ortaya çıkıyor: Bir n doğal sayısı verildiğinde, boş bir bantta başlatılan bir Turing makinesi T(n)'nin durup durmayacağını belirleyin. Bu görev

algoritmik olarak karar verilemez. Yani otomatik bir prosedür yoktur , her n için T(n) makinesinin durup durmayacağını belirler. Bu, herhangi bir makinenin durup durmadığını belirlememizi engellemez. Bunu tüm makineler için aynı anda çözecek bir yöntem yoktur. .

§6.5. Algoritmalar ve karmaşıklıkları.

Bir problem göz önüne alındığında, onu çözecek etkili bir algoritma nasıl bulunur? Ve eğer bir algoritma bulunursa, aynı sorunu çözen diğer algoritmalarla nasıl karşılaştırılabilir? Kalitesi nasıl değerlendirilir? Bu tür sorular hem programcıların hem de hesaplamanın teorik çalışmalarına katılanların ilgisini çekmektedir.

Algoritmaların değerlendirilmesinde birçok kriter vardır. Çoğu zaman, girdi verileri arttıkça bir sorunu çözmek için gereken zaman ve bellek kapasitesinin büyüme sırası ile ilgileneceğiz. Her bir görevle, boyutu adı verilen bir sayıyı ilişkilendirmek istiyoruz. , bu, giriş verilerinin miktarının bir ölçüsünü ifade eder. Örneğin bir matris çarpım probleminin boyutu, faktör matrislerinin en büyük boyutu olabilir.

Bir algoritmanın problem boyutunun bir fonksiyonu olarak harcadığı zamana denir. zaman karmaşıklığı bu algoritma. Problem boyutu arttıkça bu karmaşıklığın limitteki davranışına denir. asimptotik zaman karmaşıklığı . Benzer şekilde tanımlayabiliriz kapasitif karmaşıklık ve asimptotik kapasitif karmaşıklık.

Bu algoritma tarafından çözülebilecek problemlerin boyutunu nihai olarak belirleyen, algoritmanın asimptotik karmaşıklığıdır. Bir algoritma n boyutundaki girdileri cÿn 2 zamanında işlerse, burada c - bir sabit, o zaman bu algoritmanın zaman karmaşıklığının O(n 2) olduğunu söylüyorlar (“karesel düzende” şeklinde okunur).

Mevcut nesil dijital bilgi işlem makinelerinin bilgi işlem hızındaki muazzam artışın, verimli algoritmaların önemini azaltacağı düşünülebilir. Ancak tam tersi olur. Bilgi işlem makineleri gittikçe daha hızlı hale geldikçe ve biz daha büyük sorunları çözebilir hale geldikçe, makine hızı arttıkça elde edilebilecek sorun boyutundaki artışı belirleyen şey algoritmanın karmaşıklığıdır.

Diyelim ki aşağıdaki zaman karmaşıklıklarına sahip beş A1,A2,…,A5 algoritmamız var:

Burada zaman karmaşıklığı, n boyutunda bir girdiyi işlemek için gereken zaman birimlerinin sayısıdır. Zamanın birimi bir milisaniye (1sn=1000 milisaniye) olsun. Daha sonra A1 algoritması 1000 büyüklüğündeki bir girişi bir saniyede işleyebilirken A5, 9'dan büyük olmayan bir girişi işleyebilir. Tabloda. 6.5.1. Bu beş algoritmanın her birinin bir saniye, bir dakika ve bir saatte çözebileceği problemlerin boyutları verilmiştir.

Tablo 6.5.3.

Yeni nesil bilgisayarların mevcut bilgisayarlardan 10 kat daha hızlı olacağını varsayalım. Tablo 6.5.2'de. Hızdaki bu artış nedeniyle çözebileceğimiz sorunların boyutunun ne kadar artacağını gösteriyor. A5 algoritması için hızdaki on kat artışın, yalnızca üç birim ile çözülebilecek problemin boyutunu artırdığını (Tablo 6.5.2'deki son satıra bakın), A3 algoritması için ise problemin boyutunun üç kattan fazla arttığını unutmayın. .

Tablo 6.5.4.

Şimdi hızı artırmanın etkisi yerine daha verimli bir algoritma kullanmanın etkisini ele alalım. Tablo 6.5.1'e dönelim. Karşılaştırma için 1 dakikayı baz alırsak, A4 algoritmasını A3 algoritmasıyla değiştirerek 6 kat daha büyük bir sorunu, A4'ü A2 ile değiştirerek çözebiliriz. , 125 kat daha büyük bir sorunu çözebilirsiniz. Bu sonuçlar, 10 kat hız ile elde edilen 2 kat iyileşmeden çok daha etkileyicidir. Karşılaştırma için 1 saati baz alırsak aradaki fark daha da belirgin oluyor. Bundan, bir algoritmanın asimptotik karmaşıklığının, algoritmanın kalitesinin önemli bir ölçüsü olarak hizmet ettiği ve hesaplama hızındaki müteakip artışlarla daha da önemli hale gelmeyi vaat eden bir ölçü olduğu sonucuna varıyoruz.

Burada asıl dikkatin niceliklerin büyüme sırasına verilmesine rağmen, algoritmanın karmaşıklığında büyük bir büyüme sırasının daha küçük bir çarpımsal sabite (sabit) sahip olabileceği anlaşılmalıdır. C O(f(x))), tanımında başka bir algoritmanın karmaşıklığında küçük bir artıştan daha fazladır. Bu durumda karmaşıklığı hızla artan bir algoritma küçük problemler için, hatta belki de ilgilendiğimiz tüm problemler için tercih edilebilir. Örneğin, A1, A2, A3, A4, A5 algoritmalarının zaman karmaşıklıklarının gerçekte sırasıyla 1000n, 100nÿlog(n), 10n2, n3 ve 2 olduğunu varsayalım. n O zaman A5, 2§n§9 boyutundaki problemler için, A2 boyutundaki problemler için en iyisi olacaktır.

10§n§58, A1 - 59§n§1024'te ve A1- n>1024.- ile

EDEBİYAT.

1. F.A. Novikov. Programcılar için ayrık matematik./ St. Petersburg: Peter, 2001, 304С.

2.S.V.Sudoplatov, E.V. Ayrık Matematiğin Elemanları./ M., INFRA-M, Novosibirsk, NSTU Yayınevi,

3. Y.M.Erusalimsky. Ayrık matematik / M., “Üniversite kitabı”, 2001, 279 s.

4. A. Aho, J. Hopcroft, J. Ullman. Hesaplamalı algoritmaların oluşturulması ve analizi. / M., Mir, 1979, 536С.

5. V.N.Nefedov, V.A.Osipova Ayrık matematik kursu./ M., MAI Yayınevi, 1992, 264P.
Matematiksel mantık ve algoritma teorisi – Ders dersi
Giriiş.

Amaç.

Bu ders, bilgisayar bilimleri alanındaki problemlerin kurulması ve çözülmesi için gerekli teorik temeli oluşturan bilgi ve becerilerin geliştirilmesine, hesaplama yapıları, algoritmalar ve bilgi işleme programları oluşturulurken ortaya çıkan sınırlamaların doğru anlaşılmasına yöneliktir.
Ayrık matematik dersinin yeni bölümleri, eğitim programları ve ders dizileri şeklinde uygulanmasına rağmen, teknik üniversiteler için ayrık matematik dersi eski uygulamalı problemlere odaklandığından, en azından Rusça'da henüz monografi şeklinde mevcut değildir. Mühendislerin çözmesi gerekiyordu. Özellikle matematiksel mantıkta, bugün geçerliliğini kaybeden mantıksal devrelerin minimizasyonu oldu.
Bir nesil araştırmacının gözleri önünde neredeyse tamamlanmış bir "biyolojik döngüden" geçen mantıksal devrelerin sentezi teorisinin, temel bilimlerle zayıf bir şekilde bağlantısı olan teknik bilim dallarının nasıl olduğuna dair çok öğretici bir örnek olduğunu belirtmek ilginçtir. Bilim eskimeye oldukça duyarlıdır. Sadece 10 yıl önce tüm teknik dergiler mantık devrelerinin minimizasyonu ve sentezi üzerine makalelerle doluydu. Bilim adamlarının geliştirdiği minimizasyon yöntemlerinin çoğu artık unutulmuş ve pratikte talep görmemektedir. Ve o zamanlar tamamen teorik olarak kabul edilen fikirler, modern teknolojide pratik uygulama buldu. Örneğin, bulanık mantık, Petri ağları ve algoritma teorisi zaman testinden geçmiştir ve sistem programlama, hesaplama karmaşıklığı ve yapay zeka gibi sibernetik ve programlamanın çeşitli alanlarında yaygın olarak kullanılmaktadır.
Ve algoritma teorisi ayrık matematiğin merkezi bölümü haline geldi. Bununla birlikte, Rusça'daki çoğu monografinin aksine, dersler sırasında bu konular pratik mühendislik problemlerini çözmenin bir yolu olarak sunulmaktadır.
Bildiğiniz gibi her on yılda bir bilgisayarların donanım bileşenleri, işletim sistemleri, erişim araçları ve programların kendisi kökten değişiyor. Ancak bunların altında yatan yapılar ve algoritmalar çok daha uzun süre değişmeden kalır. Bu temeller binlerce yıl önce biçimsel mantığın geliştirildiği ve ilk algoritmaların geliştirildiği zaman atılmaya başlandı.
Matematiksel mantık ve algoritma teorisi geleneksel olarak temel bilime aittir ve pratikle çok az bağlantısı olduğu ve anlaşılmasının zor olduğu düşünülmektedir. Nitekim J. Boole, Boole cebirinin matematiksel aparatını yarattığında uzun süre pratik uygulama bulamadı, ancak 20. yüzyılda tüm bilgisayar bileşenlerinin tasarlanmasını mümkün kılan bu matematiksel aparattı. Sonuç olarak, bu önyargılardan ilki bilgisayar teknolojisinin gelişmesiyle başarıyla çürütülmüştür.
Bu disiplini anlamanın zorluğuna ilişkin önyargı ise büyük ölçüde matematiksel mantık ve algoritmalar teorisi üzerine kitapların matematikçiler tarafından matematikçiler için yazılmış olmasından kaynaklanmaktadır.
Şimdi, bilgi işlem teknolojisinin yetenekleri kat kat arttığında ve kişisel bilgisayarların sayısı, onları nasıl etkili bir şekilde kullanacağını bilen insanlardan çok daha fazla olduğunda, modern bilgi işlem teknolojisinin yardımıyla nelerin yapılabileceğini ve yapılamayacağını anlamak önemlidir. olağanüstü önem.
Bilgi işlem gücü ne kadar güçlü olursa olsun çözülemeyen sorunların olduğunu gösteren genel algoritma teorisiydi ve onun hızla gelişen dalı - hesaplama karmaşıklığı teorisi - yavaş yavaş çözülebilir sorunların olduğunun anlaşılmasına yol açtı. ancak nesnel olarak karmaşıktır ve bunların karmaşıklığı bir bakıma mutlak anlamda ortaya çıkabilir, yani. modern bilgisayarlara pratik olarak erişilemez.
Bu kurs aşağıdaki hedefleri belirlemektedir:
1. İncelenen tüm konuları mümkün olduğu kadar basit bir şekilde sunun, ancak yüksek vasıflı bir uzmanın gerektirdiğinden daha basit değil.
2. Bilgi sistemlerinin tasarımı ve analizine ilişkin pratik sorunlar başlangıç noktasıdır ve resmi aygıt bu sorunları sistematik olarak çözmenin bir yoludur. Öğrencinin doldurulması gereken bir kap değil, yakılması gereken bir meşale olduğuna olan inancımız tamdır.
3. Kursun her bölümü kendi kendine test soruları içerir. Bu dersi tamamlamak için öğrencinin tüm bu soruları yanıtlaması gerekir.
Bu derste uzmanlaşmanın bir sonucu olarak öğrenci, ilgili teorik bölümleri net bir şekilde anlayarak şunları yapabilmelidir:
Bilginin en basit mantıksal dönüşüm türünü keyfi bir mantıksal işlevler temelinde uygulayın;
Doğal dilde kanıta dayalı akıl yürütmenin mantıksal yapısını belirleyin, resmi kanıt şemaları oluşturun ve bunların doğruluğunu kontrol edin.
1.2 Mantıksal gösterimler
Mantıksal gösterimler - sistemin, sürecin, incelenen olgunun bir dizi şeklinde tanımlanması karmaşık ifadeler oluşan basit (temel) ifadeler Ve mantıksal bağlaçlar aralarında. Mantıksal temsiller ve bileşenleri, belirli özellikler ve bunlar üzerinde izin verilen bir dizi dönüşüm (işlemler, çıkarım kuralları vb.) ile karakterize edilir ve resmi (matematiksel) olarak geliştirilenleri uygular. Mantıkta doğru akıl yürütme yöntemleri mantık yasalarıdır.
İfadelerin resmi sunum yöntemleri (kuralları), mantıksal olarak doğru dönüşümler kullanılarak mevcut ifadelerden yeni ifadelerin oluşturulması ve ayrıca ifadelerin doğruluğunu veya yanlışlığını belirleme yöntemleri (yöntemleri) incelenmektedir. matematiksel mantık. Modern matematiksel mantık iki ana bölümden oluşur: ifadelerin mantığı ve onu kapsayan yüklem mantığı(Şekil 1.1), yapımı için iki yaklaşımın (dillerin) bulunduğu, iki biçimsel mantık çeşidi oluşturan: mantık cebiri Ve mantıksal hesap. Bu biçimsel mantık dillerinin temel kavramları arasında birebir bir örtüşme vardır. İzomorfizmleri sonuçta temeldeki kabul edilebilir dönüşümlerin birliği ile sağlanır.
Pirinç. 1.1
Geleneksel mantık dallarının ana nesneleri ifadelerdir.
İfade - bildirim cümlesi (ifade, karar), o bunu söylemek mantıklı doğru veya YANLIŞ. Tüm bilimsel bilgiler (fizik, kimya, biyoloji vb. yasalar ve olgular, matematik teoremleri vb.), günlük yaşamdaki olaylar, ekonomi ve yönetim süreçlerinde ortaya çıkan durumlar ifadeler şeklinde formüle edilir. Emir ve soru cümleleri ifade değildir.
İfade örnekleri: “İki kere iki dört eder”, “21. yüzyılda yaşıyoruz”, “Ruble Rus para birimidir”, “Alyosha Oleg'in kardeşidir”, “Birleştirme, kesişme ve toplama işlemleri setlerdeki Boole işlemleridir ”, “İnsan ölümlüdür”, “Terimlerin yerlerinin değişmesi toplamı değiştirmez”, “Bugün Pazartesi”, “Yağmur yağarsa şemsiye almalısın.”
Bu cümlelerle ifade olarak daha fazla işlem yapabilmek için her birinin doğru mu yanlış mı olduğunu bilmemiz gerekir; onları tanı doğruluk değeri (gerçek). Bazı durumlarda bir ifadenin doğruluğunun veya yanlışlığının, onun yardımıyla tanımlamaya çalıştığımız belirli gerçekliğe (sistem, süreç, olgu) bağlı olduğunu unutmayın. Bu durumda, verilen ifadenin belirli bir yorumda (bağlamda) doğru (veya yanlış) olduğu söylenir. Ayrıca bağlamın verildiğini ve ifadenin belirli bir doğruluk değerine sahip olduğunu varsayıyoruz.
1.3 Gelişmiş matematiksel mantığın tarihi
Bir bilim olarak mantık 4. yüzyılda kuruldu. M.Ö. Yunan bilim adamı Aristoteles tarafından yaratıldı.
"Mantık" kelimesi, bir yandan "kelime" veya "açıklama", diğer yandan düşünme anlamına gelen Yunanca "logos" kelimesinden gelir. Ozhegov S.I.'nin açıklayıcı sözlüğünde. Şöyle denir: "Mantık, düşünme yasalarının ve biçimlerinin bilimidir." 17. yüzyılda Alman bilim adamı Leibniz, "gerçeği hesaplama sanatı" olacak yeni bir bilim yaratmayı planladı . Leibniz'e göre bu mantıkta her ifadenin karşılık gelen bir sembolü olacak ve akıl yürütme hesaplamalar biçiminde olacaktır. Çağdaşlarının anlayışını karşılayamayan Leibniz'in bu fikri yayılmadı, gelişmedi ve parlak bir tahmin olarak kaldı.
Sadece 19. yüzyılın ortalarında. İrlandalı matematikçi George Boole, Leibniz'in fikrini somutlaştırdı. 1854'te, sıradan cebir yasalarına benzer yasaların geçerli olduğu, ancak harflerin geçerli olduğu mantık cebirinin temellerini atan "Düşünce yasalarının araştırılması" adlı eseri yazdı. sayıları değil, ifadeleri belirtir. Boolean cebiri dilinde, akıl yürütme açıklanabilir ve sonuçları "hesaplanabilir". Ancak akıl yürütmenin tamamını kapsamaz, yalnızca belirli bir türünü kapsar. , Bu nedenle Boole cebiri önermeli bir hesap olarak kabul edilir.
Boole'un mantık cebiri yeni bir bilimin, matematiksel mantığın embriyosuydu. Bunun tersine, Aristoteles'in mantığına geleneksel biçimsel mantık denir. “Matematiksel mantık” adı bu bilimin iki özelliğini yansıtmaktadır: Birincisi, matematiksel mantık, matematiğin dilini ve yöntemlerini kullanan mantıktır; ikincisi, matematiksel mantık matematiğin ihtiyaçları tarafından hayata geçirilir.
19. yüzyılın sonunda. Georg Cantor tarafından oluşturulan küme teorisi, matematiksel mantık da dahil olmak üzere tüm matematik için, en azından önermeli hesap (Boole cebiri) için güvenilir bir temel gibi görünüyordu, çünkü Cantor cebirinin (küme teorisi) Boole cebirine izomorfik olduğu ortaya çıktı.
Matematiksel mantığın kendisi, ilk başta oldukça soyut görünen ve pratik uygulamalardan son derece uzak görünen bir matematik dalı haline geldi. Ancak bu alan uzun süre "saf" matematikçilerin alanı olarak kalmadı. 20. yüzyılın başında. (1910) Rus bilim adamı Ehrenfest P.S. anahtarlama devrelerini tanımlamak için telefon iletişiminde Boole cebiri aparatının kullanılma olasılığına dikkat çekti. 1938-1940'ta, neredeyse aynı anda, Sovyet bilim adamı V.I. Shestakov, Amerikalı bilim adamı Shannon ve Japon bilim adamları Nakashima ve Hakazawa'nın dijital teknolojide matematiksel mantığın uygulanmasına ilişkin çalışmaları ortaya çıktı. Dijital ekipmanın tasarımında matematiksel mantığın kullanımına ayrılan ilk monografi, Sovyet bilim adamı M.A. Gavrilov tarafından SSCB'de yayınlandı. Modern mikroişlemci teknolojisinin gelişiminde matematiksel mantığın rolü son derece önemlidir: bilgisayar donanımının tasarımında, tüm programlama dillerinin geliştirilmesinde ve ayrık otomasyon cihazlarının tasarımında kullanılır.
Farklı ülkelerden bilim adamları matematiksel mantığın gelişimine büyük katkı sağladılar: Kazan Üniversitesi profesörü Poretsky P.S., de-Morgan, Peirce, Turing, Kolmogorov A.N., Heidel K. ve diğerleri.
1.4 Kendi kendine test için sorular.
1. Dersin hedeflerini formüle edin
Matematiksel mantık ve algoritma teorisi
Konuşmacı: A. L. Semenov

Ders 1

Giriş 1
Matematiksel mantık problemi ve algoritma teorisi 1

Matematiksel mantığın matematiksel sonuçları ve algoritma teorisi 2

Modern uygarlık ve MLiTA 2'nin rolü

Matematiğin inşası. Küme teorisi 5

programı matematiksel araştırma matematiksel aktivite- Gilbert 9

Genel fikir 9

Hilbert Programının Sonuçları 12

Küme teorisinin dili ve aksiyomları. I. Örnekler 12

Mantıksal semboller ve anlamları (anlambilim) 12

Kümelerin varlığına ilişkin aksiyom örnekleri 13

giriiş

Matematiksel mantık sorunu ve algoritma teorisi
Matematiksel mantık ve algoritma teorisi tarafından çözülen problem, aşağıdaki insan faaliyeti türlerinin matematiksel olarak tanımlanmasına ve incelenmesine olanak tanıyan bir matematiksel tanımlar ve teoremler sistemi oluşturmaktır:

Teoremlerin kanıtlanması ve matematiksel kavramların tanımlanması

Matematiksel nesneler arasındaki ilişkilerin açıklaması

Deneysel olarak oluşturulmuş ifadelerden, hipotezlerden vb. sonuçların elde edilmesi.

Belirtilen özellik ve işlevlere sahip cihazların (mekanik, elektronik vb.) tasarımı.

Resmi talimatların oluşturulması ve uygulanması (algoritmaların ve programların tanımlanması ve uygulanması)

Gerekli sonucun açıklaması ile bu sonuca ulaşmak için tasarlanan algoritma arasında bir yazışmanın kurulması (doğruluğun kanıtı)

Matematiksel mantık ve algoritma teorisi, listelenen faaliyetlerin doğruluğu için (matematiksel, kesin) kriterler sağlar.
Matematiksel mantığın matematiksel sonuçları ve algoritma teorisi
Bu araştırmayı yaparak aşağıdakilerle ilgili sonuçlar elde edeceğiz:

Belirli bir dilde tanımlanabilecek kümeler ve ilişkiler

Kanıtlanabilir formül setleri

Gerçek formül kümeleri (2. maddeyle temel bir fark vardır)

Belirli bir kümedeki formüllerin doğru olduğu matematiksel yapı kümeleri

Algoritmalar tarafından hesaplanan fonksiyon sınıfları

Formüllerin doğruluğunu veya kanıtlanabilirliğini belirleyen bir algoritmanın varlığı

Hesaplamalı Karmaşıklık

Nesnelerin karmaşıklığı

vesaire.
Modern uygarlık ve MLiTA'nın rolü
İnsanlığın gelişimindeki önemli ilerleme, maddi nesnelerin işlenmesi, enerjinin alınması ve iletilmesi (bu makineler tarafından kullanılır), ulaşım araçları, aydınlatma vb. için makinelerin yaratılmasıyla ilişkilidir.
Yüzyıllardır insanlar madde ve enerjiyle değil, bilgi nesneleriyle çalışacak makineler yaratma fikrini akıllarına getirdiler. Üstelik bu tür makineler oluşturuldu ve hatta başarıyla çalıştırıldı, örneğin aritmetik işlemleri yapmanıza izin veren bir makine - bir toplama makinesi (B. Pascal).

20. yüzyılın ilk yarısında, bilginin insanlar tarafından resmi olarak işlenmesinin olası yöntemlerinin genel bir açıklaması yapıldı. 20. yüzyılın ortalarına gelindiğinde, çok fazla bilgiyi depolayabilen ve çok hızlı bir şekilde işleyebilen cihazların yaratılmasını mümkün kılan fiziksel prensipler keşfedildi. Evrensel cihazlar oluşturuldu - bir kişinin resmi olarak yapabileceği her şeyi yapabilen, ancak bir insandan çok daha hızlı olan bilgisayarlar.

Çok genel bir bakış açısıyla matematiksel mantığın teorik matematiğin temelini oluşturduğunu, algoritma teorisinin ise hesaplamalı pratiğin (bilgisayar kullanımının) temelini oluşturduğunu söyleyebiliriz. Ancak daha ayrıntılı bir inceleme, matematiksel mantığın pek çok başarısının bilgi teknolojilerinin geliştirilmesinde ve uygulanmasında uygulama bulduğunu ve algoritmik düşüncelerin saf matematiğin çeşitli bölümlerinde de önemli olduğunu gösterir.

Tarihin kilometre taşları
Alman matematikçilerin başarıları, matematiksel kanıtların ve hesaplamaların ne olduğuna dair modern fikirlerin geliştirilmesinde önemli anlar oldu. XIX sonu- 20. yüzyılın başı
David Hilbert'in (01/23/1862 - 01/14/1943) II. Uluslararası Matematikçiler Kongresi'nde (Paris, 1900) yaptığı konuşma özellikle önemliydi. Orada 23 sözde formüle etti. Hilbert'in problemleri o zamanın matematiği ve 20. yüzyılda matematiğin gelişimi için en önemli problemlerdi. Hilbert'in sorunlarından bazıları belirli bir matematiksel ifadenin doğruluğunu belirleme meselesiydi, diğerleri ise daha çok bir tür araştırma programını yürütme önerisi olarak adlandırılabilirdi.

Hilbert'in listesindeki Problem I, II, X matematiksel mantık konusu ve algoritma teorisi ile ilgilidir.

Milenyumun yedi matematik probleminden ilki konumuzla da ilgilidir (Hilbert'in Problemleri arasında yoktu).

Derste matematiksel mantık ve algoritma teorisi alanında yukarıda belirtilen problemler ve bunlara modern bakış açısı tartışılacaktır.
Organizasyon notları
Kursun yazarları matematiği öğrenmenin ve matematikçi olmanın en iyi yolunun matematiği kendi başınıza yapmak olduğuna inanıyor. Matematikçiler derken, mesleki faaliyetlerinin önemli bir kısmını (ve birçoğu için tüm yaşamlarını) matematiksel faaliyet yöntemlerini kullanarak matematiksel nesnelerle çalışmak olan herkesi kastediyoruz. Örneğin bilgi teknolojisi alanındaki faaliyetlerin önemli bir kısmı bu şekilde yapılandırılmıştır. "Matematik yapmak" derken problemleri çözmeyi kastediyoruz ve her şeyden önce, okulda en sık çözülenleri veya üniversitenin ilk yılında matematiksel analiz sırasında çözülenleri kastetmiyoruz. Yeni bir şey bulmanız gereken görevleri kastediyoruz. Elbette, matematiğin yeni bir alanında ustalaşırken, bu problemlerin çoğunun basit ve uzun zaman önce çözülmüş olması gerekir, ancak bunlar, profesyonel bir matematikçinin ve programcının çözmek zorunda olduğu problemlerden temelde farklı değildir.
Şu anda bahsettiğimiz türden problemler hem derslerde hem de ders alıştırmalarında formüle edilecektir. Formüle edilmiş görevlerin tümü tamamen basit olmayacaktır. Üstelik bazıları matematikte çok yakın zamanda çözüldü, bazıları henüz çözülmemiş olacak, bazıları ise hiç çözümü olmayan (ancak çözülmesi yararlı olan) olacaktır.

Kurs boyunca problem çözmeye katılmanızı ve bunları eğitmeninizle (ve tabii ki birbirinizle) tartışmanızı öneririz. Bu:

Derslerin içeriğini ve dersin ilgili olduğu tüm matematik alanını daha iyi anlamanıza yardımcı olacaktır.

Sınava hazırlanmak ve kısmen "geçmek" daha iyidir (kurs sırasındaki problemlerin çözümü sınavda size "kredilendirilecektir", öğretmenleriniz size bu konuda daha fazla bilgi verecektir)

Kendinizi gelecek vaat eden bir matematik alanında deneyin ve belki de üniversitedeki uzmanlığınız için bunu seçin; bu, üniversiteden sonraki çalışmanız için yararlı olabilir.

Problemlerin çözüldüğü ve çözümlerinin tartışıldığı bir diğer yer ise üçüncü sınıf öğrencilerine yönelik Matematiksel Mantık ve Bilgisayar Bilimleri Prosemineridir. Orada, konunun özünü anlamanıza olanak tanıyan basit görevlerin yanı sıra, size hem karmaşık hem de henüz çözülmemiş görevler hemen sunulacak.
Bir sonraki dersin materyalleri internette web sitesinde yayınlanacaktır. http://lpcs.math.msu.su/vml2013/

Bunlara ek olarak kitaplardan ders içeriği hakkında bilgi edinebilirsiniz:

N.K. Vereshchagin, A. Shen, Matematiksel mantık ve algoritma teorisi üzerine dersler, ed. MCCME (mccme.ru)

I. A. Lavrov, L. L. Maksimova, Küme teorisi, matematiksel mantık ve algoritma teorisindeki problemler,

bunlar internette de mevcuttur.
Son olarak son şey. Matematiksel mantığın ve algoritma teorisinin uygulanan sonuçlarından biri, matematiksel aktivitenin çeşitli bileşenlerinin otomasyonudur. Özellikle belirli türdeki matematiksel kanıtların doğrulanması otomatikleştirilebilir. Bu tür otomasyon alanı, doğal olarak, otomasyon algoritmalarının geliştirilmesi, matematikçilerin bu algoritmaların nasıl uygulanacağı konusunda daha iyi anlaşılması, deneyim birikimi ve bilgi işlem yeteneklerinin büyümesi nedeniyle sürekli genişliyor. Bugün kanıt doğrulamayı otomatikleştirmek için en popüler ve etkili bilgi işlem çerçevesi Coq'dur. Departmanımız Coq üzerinde bu ortamı nasıl kullanacağınızı öğrenebileceğiniz, yeteneklerini ve sınırlamalarını hayal edebileceğiniz bir atölye çalışması yürütüyor.

Matematiğin inşası. Küme teorisi
Matematiğin modern yapısı, özellikle de üniversitelerde öğretilme şekli küme teorisine dayanmaktadır. Şimdi bu teorinin bazı temel kavramlarını hatırlayacağız.
Kümeleri tanımlamak için genellikle küme parantezleri kullanılır. Bunların içine, verilen kümenin tüm elemanlarını yerleştirebilirsiniz: (2, 14, 5.4) veya onu özel bir şekilde tanımlayabilirsiniz: (x|x bir gerçek sayıdır ve sin(x)>0).

Küme işlemleri için aşağıdaki gösterimi kullanırız: Bir öğenin kümeye üyeliği ∊, ⊂, birleşim ∪, kesişim ∩, fark \ kümelerinin dahil edilmesi.

İki nesnemiz olsun X,sen. Sıralı çift x; sen> benzersiz bir şekilde geri yüklenen nesneyi çağırdı X, sen başka bir deyişle: X; sen> = x'; sen′> → ( X = X′ sen = sen′).

iş X X sen iki takım X Ve sen tüm sıralı çiftlerin kümesidir sen; v>, nerede sen ∊ X Ve v ∊ sen.

Benzer şekilde sipariş edilen N-ki nesneleri ve N derece X N setleri X. Bu konuda anlaşmaya varılabilir X 1: X.

Kümeler arasındaki ilişki X, sen çarpımlarının herhangi bir alt kümesine denir X X sen.
N-setteki yerel ilişki X herhangi bir alt kümeye denir N Bu kümenin -inci derecesi.

Davranış F arasında X Ve sen fonksiyonu denir X V sen ilişkinin herhangi iki öğesinin ilk bileşenlerinin çakışmasından kaynaklanıyorsa F ikincisinin tesadüfü takip ediyor.

Bir fonksiyonun etki alanı, onun ilk bileşenlerinin kümesidir.

Bir fonksiyonun etki alanı nereden geliyorsa X V sen ile çakışıyor X, daha sonra fonksiyonun görüntüleneceği söylenir X V sen ve yaz F : X → sen. Tüm işlevlerin birçoğu görüntüleniyor X V sen, ile gösterilir sen X .

İşlev F : X → sen arasında eşleştirme denir X Ve sen, veya çıkarma X V sen veya izomorfizm X Ve sen, eğer elementlerin ikinci bileşenlerinin tesadüfünden kaynaklanıyorsa F bundan ilk unsurların çakıştığı ve buna ek olarak ikinci unsurların çakıştığı sonucu çıkar F tüm seti oluştur sen. İzomorfik kümelere eşdeğer kümeler de denir.

Bir küme doğal seriye eşdeğerse sayılabilir kümeye sayılabilir denir.

Görev. Bir doğal serinin her alt kümesinin ya başlangıç segmentine (bazı elemanlarıyla aynıdır) ya da doğal serinin tamamına eşdeğer olduğunu kanıtlayın.

Son problemde formüle edildi temel gözlem Bir parçanın bütüne eşbiçimli olabileceği ikinci sınıf öğrencilerine muhtemelen önemsiz gelebilir. Ancak bu, küme teorisinin ilk keşiflerinden biriydi.

Sonlu kümeler boyuta göre karşılaştırılabilir. Eğer biri diğerinin alt kümesine izomorf ise o zaman daha az elemanı vardır. Durumunda sonsuz kümeler bu yanlış. Bu durum Galileo Galilei tarafından kısaltmasıyla sunduğumuz aşağıdaki diyalogda anlatılmıştır:
Konuşmalar Vematematikselkanıt, iki yeni ile ilgilibilim dalları,ilgili İlemekanikVeyerel hareket
senyora Galileo Galilei Lyncheo, Filozof ve ilk matematikçi Majesteleri Toskana Büyük Dükü

Salviati. ...tüm sayıların (kareler ve kare olmayanlar) sayısı tek başına karelerin sayısından daha fazladır; değil mi?

Simplicio. Buna karşı çıkamam.

Salviati. Her karenin kendi kökü ve her kökün kendi karesi olduğundan, kök sayısı kadar kare vardır; Hiçbir karenin birden fazla kökü olamaz ve hiçbir kökün birden fazla karesi olamaz.

Sagredo. Bu durumdan bir çıkış yolu bulmak için ne yapılması gerekiyor?

Salviati. Sonsuzlukla uğraştığımızda eşitlik özelliklerinin yanı sıra daha büyük ve daha küçük büyüklüklerin mevcut olmadığını ve yalnızca sonlu niceliklere uygulanabileceğini kabul etmekten başka bir çözüm olasılığını görmüyorum. Bu nedenle, Sinyor Simplicio bana eşit olmayan çizgiler sunduğunda ve büyük olanın içermemesinin nasıl mümkün olduğunu sorduğunda Daha Daha az sayıda puan varsa, o zaman ona ne daha fazla ne de daha az olduğunu ve aynı sayıda olmadığını, her birinde sonsuz sayıda olduğunu söylerim.

Bununla birlikte, sonsuz kümeler arasında bile, aşağıdaki teoremin gösterdiği gibi, yine Cantor tarafından kanıtlanmadan açıklanan ve kısa süre sonra diğer Alman matematikçiler tarafından kanıtlanan bir düzen vardır.

Cantor-Bernstein teoremi. Kümeler arasında bir eşleşme olsun A ve kümenin bir alt kümesi B, ayrıca küme arasında bir eşleşme B ve kümenin bir alt kümesi A. Daha sonra setler A Ve B– güç bakımından eşit.

Görev. Cantor-Bernstein Teoremini kanıtlayın.

Görev. Herhangi bir kümeyi önem açısından karşılaştırmak mümkün müdür, yani herhangi bir küme için bu doğru mudur? A Ve B, veya A eşit derecede güçlü alt küme B, veya B eşit derecede güçlü alt küme A?

Vurguladığımız işlevler arasında özellikler– yalnızca 0 ve 1 değerlerini alan işlevler. Her özellik bir ilişkiyi, yani değerinin 1 olduğu bir öğeler kümesini belirtir. Herhangi bir işlev F : X → B denir karakteristik(Açık X). Gösterim ve kurallarımızda B=(0,1)=2 olduğuna dikkat edin. Böylece, tüm karakteristik fonksiyonların kümesi X B unvanını alır X veya 2 X .

Görev. Karakteristik fonksiyonlar kümesi arasında bir izomorfizm oluşturun. X ve setin birçok alt kümesi X.

Görev. Herhangi bir kümenin alt kümelerinin kümesinin kendisine izomorf olmadığını kanıtlayın.

Çözüm fikri [Cantor Diagonal]. İzomorfizm olsun G : X → 2 X var. Her öğe için düşünelim sençoğumuzdan X karşılık gelen alt kümesi G(sen). Elementlerden yapabilir miyiz? X bir alt küme topla C, setten farklı olacak G(sen) "öğe üzerinde sen» ? Veya aynı şey nedir, bir karakteristik fonksiyonun nasıl oluşturulacağı F C kümenin karakteristik fonksiyonundan farklı olacak G (sen) "bu noktada sen» her halükârda sen?

Eğer X bir doğal sayılar kümesi ise kanıt netleşir grafik formu. Numarayı arayacağız sen karakteristik fonksiyonuna giren F, fonksiyon numarası F.

Argüman
İşlev Numarası

0

1

2

3

4

…

0

1

0

0

1

0

1

1

1

0

1

0

2

1

0

0

1

1

3

0

0

0

1

0

4

0

1

0

1

0

………
Bu tabloda sayı satırında N taburcu karakteristik fonksiyon numara ile N. Tablonun köşegeninden 1'in 0'a ve 0'ın 1'e değiştirilmesiyle (olumsuzlama işlemi) elde edilen bir fonksiyon bulunmamaktadır.

Görev. Gerçel sayılar kümesinin doğal serinin alt kümeleri kümesine eşdeğer olduğunu kanıtlayın.
Matematiksel Etkinlik Araştırma Programı - Hilbert

Genel fikir
David Hilbert, matematiğin matematiksel olarak tanımlanmış bir aktivite alanı olduğu fikrine, matematiğin kendisi aracılığıyla matematiksel aktiviteye yönelik araştırmanın önemine dair farkındalığa ve bu tür araştırmalar için bir programın (Hilbert Programı) sunumuna sahiptir.
Hilbert'in matematik çalışmalarına yönelik programları şu şekilde temsil edilebilir:

Matematik bir sistem olarak temsil edilebilir

aksiyomlar - doğru olarak kabul ettiğimiz ifadeler ve

kanıt kuralları - yeni ifadelerin elde edilmesi.

Matematiksel aktivitenin uygulanması, seçilen sistemin gerekli tüm kanıtları oluşturmamıza izin verdiğine bizi ikna etmelidir. İdeal olarak, her matematiksel ifadenin bu sistem kullanılarak kanıtlanması veya çürütülmesi mümkündür. (Bu özelliğe denir bütünlük.)

Bazı matematiksel kanıtlar "özellikle sağlam ve ilgi çekicidir." Bunlar arasında örneğin şunlar yer alır: aritmetik hesaplamalar. Yalnızca bunları kullanarak matematik için seçilen sistemin çelişkiler elde etmenize izin vermediğinden emin olabilirsiniz. (Bu özelliğe denir tutarlılık.) Üstelik matematiğin tamlığının basit, anlaşılır ve ikna edici akıl yürütmelerle de kanıtlanabileceği ortaya çıkabilir.

Tamlık özelliğinin kullanışlılığı açıktır. Kural olarak, matematiksel bir ifadeyi kanıtlamaya çalışırken aynı zamanda onun çürütülmesini de ararız. Bu tür faaliyetlerin eninde sonunda sonuçlara yol açacağından ve bunun "sadece" yeteneklerimize ve zamanımıza bağlı olduğundan emin olmak isterim. Hilbert şuna inanıyordu: "Bu, her sorunun çözülebilirliğine duyulan inançtır. matematik problemi işimizde bize çok yardımcı oluyor; içimizde sürekli bir çağrı duyarız: sorun burada, çözüm arayın. Onu saf düşünme yoluyla bulabilirsiniz; çünkü matematikte Ignorabimus diye bir şey yoktur!”
Tutarlılık özelliğinin çok daha önemli olduğunu unutmayın. A priori birinin hayal edebileceği bilimsel teoriÇelişkinin çevrede bir yerde bulunduğu ve bazı önemsiz konularla ilgili olduğu. Ancak tüm önemli sistemlerin tasarımı matematiksel kanıt bir çelişkinin kanıtlanabilirliği öyledir (örneğin, bazı iki çelişkinin çarpımı çok büyük sayılarüçte bire ve bir dördüncüye eşit) hemen herhangi bir matematiksel ifadenin kanıtlanabilirliğine yol açar. Çelişki “yerelleştirilemez”.

Hilbert Programının hedeflerine ulaşmaya yönelik ilk adımlar, henüz formüle edilmeden önce atılmıştı. Üstelik Program mantıksal olarak onları takip ediyordu. Bunlar adımlar.
Kanıt. Mantık. 19. yüzyılın sonunda akıl yürütme sisteminin nasıl resmileştirileceği belli oldu. Bu formalizasyon Gottlob Frege'nin (11/8/1848 - 07/26/1925) çalışmalarında tamamlandı.
Teoriyi ayarlayın. 19. yüzyılın sonunda matematiğin bir başka başarısı da, tüm matematiğin kümeler cinsinden tekdüze olarak temsil edilebileceğinin anlaşılmasıydı (modern bilimlerde olduğu gibi). matematik dersleri yukarıda da hatırlatmıştık). Bu, Georg Cantor'un (3.03.1845 - 6.01.1918) eserlerinde yapılmıştır.

Böylece geriye sadece seçim yapmak kalıyordu. uygun sistem aksiyomlar ve tutarlılık ve tamlığı kanıtlama yolunu izlemeye devam edin. Bu tür kanıtların basit ve güvenilir yollarla elde edilmesi umudu aşağıdakilerle ilişkilendirildi. Aksiyomların ve ispat kurallarının kullanımı oldukça basit süreç formüllerle çalışmak. Formüllerin kendileri basit nesnelerdir, sembol zincirleridir. Örneğin matematik satranç gibi bir oyuna benziyor. Diyelim ki satrançta bazı pozisyonların imkansız olduğunu kanıtlamamız gerekiyor. Prensip olarak - bu elbette her türlü yoldan geçerek yapılabilir. satranç oyunları. Ama daha fazlasını hayal edebilirsiniz basit muhakemeörneğin, taşların alana eklenmediği, fillerin açık kare ve koyu kare olduğu gerçeğine dayalı olarak. Bu tür bir akıl yürütme büyük olasılıkla gerçek sayıları, integralleri ve hatta daha karmaşık matematiksel nesneleri kullanmayacak.

Sistem küme teorisi için aksiyomlar Esas olarak 20. yüzyılın ilk on yıllarında inşa edilmiş olup, modern formülasyona yakın ilk formülasyon Ernst Zermelo'ya (27.7.1871 – 21.5.1953) ait olup 1908 yılında kendisi tarafından yayınlanmıştır.
Hilbert Programının Sonuçları
Hilbert Programına daha sonra ne oldu? Bunu şimdi kısaca formüle edeceğiz ve bir sonraki derste daha ayrıntılı olarak açıklayacağız.
Bir yandan Program başarıyla uygulandı:

Aksiyomatik küme teorisi temeldir modern matematik.

Özellikle otuzlu yıllarda N. Bourbaki kolektif takma adı altında bir grup matematikçi kuruldu. Maksimumu yaratıcı aktivite 1950'li ve 60'lı yıllarda meydana geldi. Bu grup, modern matematiğin önemli bir bölümünü küme teorisi temelinde inşa edilmiş olarak tutarlı ve sistematik bir şekilde sundu.

Aynı zamanda Program temelde başarısız oldu:

Matematik tamamlanmamıştır ve tamamlanamaz.

Matematiğin tutarlılığı yalnızca bazı güvenilir ve ikna edici araçlarla sağlanamaz.

Bu, 1930'larda Kurt Gödel (04/28/1906 - 01/14/1978) tarafından kuruldu.
Küme teorisinin dili ve aksiyomları.BEN. Örnekler
Matematikte bir ispat sistemi (küme teorisi) mantıksal dilin tanımıyla formüle etmeye başlıyoruz.
Mantıksal semboller ve anlamları (anlambilim)
Boolean değerleri: I (doğru), L (yanlış) simgeleri veya 1, 0 simgeleri. 0 ve 1 sembollerinden oluşan kümeyi B olarak göstereceğiz.
Mantıksal işlemler:(değil, olumsuzluk), (ve, bağlaç), (veya, ayrıklık), → (takip, ima), ≡ (eşdeğerlik) 1 (I) ve 0 (A) simgelerine uygulanır ve bunların uygulanmasının sonucu şu şekildedir: aşağıdaki tabloda açıklanmıştır:

A

B

A

AB

AB

A → B

A ≡ B

0

0

1

0

0

1

1

0

1

1

0

1

1

0

1

0

0

0

1

0

0

1

1

0

1

1

1

1

Niceleyiciler, sizin de elbette aşina olduğunuz - X (var X ), sen (herhangi biri için sen )
Kümelerin varlığına ilişkin aksiyom örnekleri
Küme Teorisinin bazı aksiyomları, diğer kümelerden oluşanlar da dahil olmak üzere kümelerin varlığına ilişkin ifadelerdir.
Kümelerden söz edebilmek, özellikle onlara ilişkin aksiyomları formüle edebilmek için mantıksal sembollere küme teorisiyle ilgili sembolleri eklemek gerekir. Ne nasıl yazılır X – boş küme yani hiçbir elemanı olmayan bir küme mi? Örneğin şöyle:

sen ( sen ∊ X ) (herkes için sen bu doğru değil sen ait X )
Bir üyelik sembolüne (∊) ihtiyacımız vardı. Dilimizin alfabesine ekleyelim.

Konuşacak bir şeyimizin olması için en azından bir kümenin varlığından emin olmak iyi olur. Boş (Ø) ile başlayalım:
X sen ( sen ∊ X ) [Boş küme aksiyomu.]

Bazı özel kümeleri, kümelerin özelliklerini vb. tanımlamak istiyoruz. Bunlar için notasyonlar tanıtmak istiyoruz.

Boş kümeyi sıfır olarak kabul edeceğiz.

Nasıl alınır sonraki numara arasından N? Tüm öğelere ekle N hala sadece N. Yani bir sonrakinin unsurlarını ele alacağız. N tüm öğeleri numaralandırır N ve daha fazlası N. Ortaya çıkan tüm öğeler bir küme oluşturur N:

1 (0)

2 (0,1)= (0,(0))

Görev. 5 numaralı (küme) kaç element var? Ve bolluk içinde N?
Bu şekilde oluşturulan bir doğal serinin varlığı aşağıdaki aksiyomla garanti edilir. Anlaşılırlık kolaylığı için onu parçalara ayırdık ve üzerinde yorum yaptık (içinde) köşeli parantezler) bu parçalar:

S (sen (sen ∊ S v (v ∊ sen )) [gibiSdoğal seriyi alabilirsinN; içerecektirsen - sıfır]
sen (sen ∊ S → [ İçin her türlü şey sen itibaren S ]
v (v ∊ S [olacakv itibarenS , ]
w (w ∊ v ≡ (w ∊ sen w = sen ))))) [yanındasen ] [ Sonsuzluk Aksiyomu ]
Ancak bu aksiyom yalnızca doğal seriler tarafından değil aynı zamanda diğer kümeler tarafından da karşılanabilir.
Görev. Mesela ne tür?
Görev. Oluşturduğumuz doğal seriyi nasıl doğru bir şekilde tanımlayabiliriz?
İÇİNDE matematiksel yapılar Kümeler üzerindeki işlemler kullanılır. Zaten başlamış olan yolu takip ederek, bu işlemlerin sonuçlarının varlığını garanti eden aksiyomları eklemeliyiz. İşte başka bir örnek:

usv(w(w ∊ v →w ∊ sen) ≡ v ∊ S) [Derece aksiyomu]
Görev. Son formülün anlamlı bir şekilde herhangi bir kümenin tüm alt kümelerinin varlığını ifade ettiğini kontrol edin.
Elbette, örneğin iki verinin kesişimi olan bir kümeye vb. ihtiyacımız olacak.

Yukarıda yavaş yavaş setler oluşturmaya başladık. Bu yola nasıl devam edileceği açıktır; örneğin, bir tamsayılar kümesi, sonra rasyonel sayılar, üzerinde bir eşdeğerlik ilişkisi bulunan bir tamsayı çiftleri kümesi, sonra bir gerçel sayılar kümesi vb. oluşturmak.