Boole fonksiyonlarının üst üste binmesi. Süperpozisyon ve kapatma işlemleri. Tamlık, bir fonksiyonlar sisteminin temeli Fonksiyonların üst üste binmesi nedir

Bir f(x 1 , x 2 , ... , x n) fonksiyonu olsun ve fonksiyonlar

sonra işlev çağrılacak fonksiyon süperpozisyonu f(x 1 , x 2 , ... , x n) ve işlevler .

Başka bir deyişle: F = ( f j ) olsun - bir dizi mantık cebir fonksiyonu, mutlaka sonlu değildir. Bir f fonksiyonu, bir veya daha fazla değişkeninin F kümesindeki fonksiyonlarla değiştirilmesiyle elde ediliyorsa, F kümesindeki fonksiyonların üst üste binmesi veya F üzerinde fonksiyon olarak adlandırılır.

Örnek.

fonksiyon kümesine izin ver

F \u003d (f 1 (x 1), f 2 (x 1, x 2, x 3), f 3 (x 1, x 2)).

O zaman F'den fonksiyonların üst üste binmesi, örneğin şu fonksiyonlar olacaktır:

j 1 (x 2, x 3) = f 3 (f 1 (x 2), f 1 (x 3));

j 2 (x 1, x 2) = f 2 (x 1, f 1 (x 1), f 3 (x 1, x 2)).

Mükemmel DNF - bir kümeden fonksiyonların üst üste binmesi

. ð

Tanım.

fonksiyon sistemi denir tamamlamak, eğer mantık cebirinin herhangi bir fonksiyonu, süperpozisyon ve değişken değiştirme işlemleri kullanılarak bu sistemin fonksiyonlarından elde edilebiliyorsa. ð

Halihazırda bazı eksiksiz sistemlerimiz var:

;

Çünkü ;

Çünkü ;

(x+y, xy, 1). ð

Sistemin tamamlandığı koşullar nasıl belirlenir. Tamlık kavramıyla yakından ilgili olan, kapalı bir sınıf kavramıdır.

kapalı sınıflar

Mantık cebirinin fonksiyonlarının kümesine (sınıfı) K denir kapalı sınıf, K'den elde edilen tüm fonksiyonları, süperpozisyon ve değişken değiştirme işlemleriyle içeriyorsa ve başka herhangi bir fonksiyon içermiyorsa.

K, P2'deki fonksiyonların bir alt kümesi olsun. K'nin kapanması, K kümesinden değişken fonksiyonların üst üste bindirilmesi ve değiştirilmesi işlemleriyle temsil edilebilen tüm Boole fonksiyonlarının kümesidir. Bir K kümesinin kapanışı [K] ile gösterilir.

Kapatma açısından, diğer kapatma ve tamlık tanımları (orijinal olanlara eşdeğer) verilebilir:

K = [K] ise K kapalı bir sınıftır;

[K] = Р 2 ise K tam bir sistemdir.

Örnekler.

* (0), (1) - kapalı sınıflar.

* Tek değişkenli fonksiyonlar kümesi kapalı bir sınıftır.

* - kapalı sınıf.

* (1, x+y) sınıfı kapalı bir sınıf değildir.

En önemli kapalı sınıflardan bazılarını ele alalım.

1. T 0- 0'ı koruyan işlevler sınıfı.

Mantık cebiri f(x 1 , x 2 , ... , x n)'nin 0 sabitini koruyan tüm fonksiyonlarının sınıfını, yani f(0, ... , 0) = olan fonksiyonları T 0 ile gösterin 0.

T 0'a ait olan ve bu sınıfa ait olmayan fonksiyonlar olduğunu görmek kolaydır:

0, x, xy, xÚy, x+y О T 0 ;

Örneğin, W T 0'ın takip ettiği gerçeğinden yola çıkarak, bu ayrılma ve birleşme terimleriyle ifade edilemez.

İlk satırda T 0 sınıfından f işlevi tablosu 0 değerini içerdiğinden, T 0'dan işlevler için yalnızca 2 n - 1 değişken değeri kümesinde keyfi değerler ayarlayabilirsiniz, yani

,

0'ı koruyan ve n değişkene bağlı olan işlevler kümesi nerede.

T 0'ın kapalı bir sınıf olduğunu gösterelim. xОT 0 olduğundan, kapalılığı doğrulamak için, süperpozisyon işlemine göre kapalılığı göstermek yeterlidir, çünkü değişkenlerin değiştirilmesi işlemi x fonksiyonu ile özel bir süperpozisyon durumudur.

İzin vermek . O zaman bunu göstermek yeterlidir. İkincisi, eşitlikler zincirinden gelir

2.T1- 1'i koruyan işlevler sınıfı.

Mantık cebiri f(x 1 , x 2 , ... , x n)'nin sabit 1'i koruyan tüm fonksiyonlarının sınıfını T 1 ile gösterin, yani f(1, ... , 1) = olan fonksiyonlar 1.

T 1'e ait fonksiyonlar ve bu sınıfa ait olmayan fonksiyonlar olduğunu görmek kolaydır:

1, x, xy, xÚy, xºy О T 1 ;

0, , x+y Ï T 1 .

x + y П T 0 olması gerçeği, örneğin, x + y'nin ayrılma ve birleşme terimleriyle ifade edilemeyeceğini ima eder.

T 0 sınıfıyla ilgili sonuçlar önemsiz bir şekilde T 1 sınıfına taşınır. Böylece elimizde:

T 1 - kapalı sınıf;

.

3.L- doğrusal fonksiyonların sınıfı.

Mantık cebiri f(x 1 , x 2 , ... , x n)'nin doğrusal olan tüm fonksiyonlarının sınıfını L ile gösterin:

L sınıfına ait olan ve bu sınıfa ait olmayan fonksiyonlar olduğunu görmek kolaydır:

0, 1, x, x+y, x 1 º x 2 = x 1 + x 2 + 1, = x+1 О L;

Örneğin, xÚy Ï L olduğunu kanıtlayalım.

Tersini varsayalım. xÚy için katsayıları tanımlanmamış doğrusal bir fonksiyon biçiminde bir ifade arayacağız:

x = y = 0 için a=0'a ​​sahibiz,

x = 1, y = 0 için b = 1'e sahibiz,

x = 0, y = 1 için g = 1'e sahibiz,

ama sonra x = 1, y = 1 için 1Ú 1 ¹ 1 + 1'e sahibiz, bu da xÚy fonksiyonunun lineer olmadığını kanıtlar.

Lineer fonksiyonlar sınıfının kapalılığının ispatı oldukça açıktır.

Bir lineer fonksiyon, a 0 , ... , an n katsayısının n+1 değeri belirtilerek benzersiz bir şekilde tanımlandığından, n değişkene bağlı fonksiyonların L(n) sınıfındaki lineer fonksiyon sayısı 2 n+1'dir. .

.

4.S- öz ikili işlevlerin sınıfı.

Kendi kendine ikili işlevler sınıfının tanımı, sözde ikilik ve ikili işlevler ilkesinin kullanımına dayanmaktadır.

Eşitlik tarafından tanımlanan fonksiyon çağrılır işleve ikili .

İkili işlev tablosunun (değişken değer kümelerinin standart sıralamasıyla), orijinal işlev tablosundan işlev değerleri sütununun ters çevrilmesiyle (yani 0'ı 1 ile ve 1'i 0 ile değiştirerek) elde edildiği açıktır. ve çevirerek.

bunu görmek kolay

(x 1 Ú x 2)* = x 1 Ù x 2 ,

(x 1 Ù x 2)* = x 1 Ú x 2 .

Tanımdan (f*)* = f, yani f fonksiyonunun f*'ye dual olduğu sonucu çıkar.

Bir fonksiyonun diğer fonksiyonlar açısından süperpozisyon kullanılarak ifade edilmesine izin verin. Soru, uygulayan bir formülün nasıl oluşturulacağıdır? Kümelerde meydana gelen tüm farklı değişken sembollerini = (x 1 , ... , x n) ile gösterin.

Teorem 2.6. j fonksiyonu, f, f 1 , f 2 , ... , f m fonksiyonlarının üst üste binmesi olarak elde edilirse, bu şu anlama gelir:

bir süperpozisyona ikili bir fonksiyon, ikili fonksiyonların bir süperpozisyonudur.

Kanıt.

j*(x 1 ,...,x n) = ` f(`x 1 ,...,`x n) =

Teorem kanıtlanmıştır. ð

Dualite ilkesi şu teoremden çıkar: A formülü f(x 1 , ... , x n) fonksiyonunu uygularsa, A'dan elde edilen formül, içerdiği fonksiyonları ikilileriyle değiştirerek f* ikili fonksiyonunu uygular. (x 1 , ... , xn).

P 2'deki tüm öz ikili fonksiyonların sınıfını S ile belirtin:

S = (f | f* = f )

S'ye ait fonksiyonlar ve bu sınıfa ait olmayan fonksiyonlar olduğunu görmek kolaydır:

0, 1, xy, xÚy П S .

Kendinden ikili işlevin daha az önemsiz bir örneği, işlevdir.

h(x, y, z) = xy Ú xz Úyz;

süperpozisyon ikili fonksiyon teoremini kullanarak, elimizdeki

h*(x, y, z)= (x Ú y)Ù(x Ú z) Ù (y Ù z) = x y Ú x z Ú y z; h = h* ; h О S.

Kendinden ikili bir işlev için kimliğe sahibiz

yani setler ve zıt diyeceğimiz öz ikili fonksiyon zıt değerler alır. Kendinden ikili bir fonksiyonun tamamen standart tablonun satırlarının ilk yarısındaki değerleri tarafından belirlendiğini takip eder. Bu nedenle, n değişkene bağlı fonksiyonların S(n) sınıfındaki öz ikili fonksiyonların sayısı:

.

Şimdi S sınıfının kapalı olduğunu kanıtlayalım. xОS olduğundan, kapalılığı doğrulamak için, süperpozisyon işlemine göre kapalılığı göstermek yeterlidir, çünkü değişkenlerin değiştirilmesi işlemi x fonksiyonu ile özel bir süperpozisyon durumudur. İzin vermek . O zaman bunu göstermek yeterlidir. İkincisi doğrudan kurulur:

5.M- monoton fonksiyonların sınıfı.

Mantık cebirinin tekdüze bir fonksiyonu kavramını tanımlamadan önce, değişkenlerinin koleksiyonları kümesi üzerinde bir sıralama ilişkisi tanıtmak gerekir.

Kümenin kümeden önce geldiği söylenir (veya "büyük değil" veya "küçüktür veya eşittir") ve gösterim, tüm i = 1, ... , n için a i £ b i ise kullanılır. Eğer ve ise, o zaman kümenin kesinlikle kümeden önce geldiğini söyleyeceğiz (ya “kesinlikle küçük” ya da “kümeden” küçük) ) ve notasyonu kullanacağız. ve kümeleri karşılaştırılabilir olarak adlandırılır, eğer biri , veya ise Bu ilişkilerden hiçbirinin sağlanmadığı durumda, ve kümeleri karşılaştırılamaz olarak adlandırılır. Örneğin, (0, 1, 0, 1) £ (1, 1, 0, 1), ancak (0, 1, 1, 0) ve (1, 0, 1, 0) kümeleri karşılaştırılamaz. Böylece £ ilişkisi (sıklıkla öncelik ilişkisi olarak adlandırılır) B n kümesi üzerinde kısmi bir düzendir. Aşağıda kısmen sıralı B 2 , B 3 ve B 4 kümelerinin diyagramları bulunmaktadır .

Tanıtılan kısmi sıra ilişkisi, kursumuzun kapsamının çok ötesinde, son derece önemli bir kavramdır.

Artık monoton bir fonksiyon kavramını tanımlayabilecek durumdayız.

Mantık cebirinin işlevi denir monoton, eğer herhangi iki küme için ve , öyle ki , eşitsizlik . Mantık cebirinin tüm monoton fonksiyonlarının kümesi M ile gösterilir ve n değişkene bağlı tüm monoton fonksiyonların kümesi M (n) ile gösterilir.

M sınıfına ait fonksiyonlar ve bu sınıfa ait olmayan fonksiyonlar olduğunu görmek kolaydır:

0, 1, x, xy, xÚy О M;

x+y, x®y, xºy П M .

Monoton M fonksiyonları sınıfının kapalı bir sınıf olduğunu gösterelim. xОМ kapalılığı haklı çıkarmak için, süperpozisyon işlemine göre kapalılığı göstermek yeterlidir, çünkü değişkenlerin değişim işlemi x fonksiyonu ile özel bir süperpozisyon durumudur.

İzin vermek . O zaman bunu göstermek yeterlidir.

Izin vermek j, f 1 , ... , f m fonksiyonlarının sırasıyla değişken kümeleri olsun ve j işlevinin değişkenler kümesi bunlardan ve yalnızca f 1 , ... , f m işlevlerinde meydana gelen değişkenlerden oluşur. , ve değişkeninin iki değer kümesi olsun ve olsun. Bu kümeler kümeleri tanımlar değişken değerler , öyle ki . f 1 , ... , f m fonksiyonlarının monotonluğundan dolayı

ve f fonksiyonunun monotonluğu nedeniyle

buradan anlıyoruz

n değişkene bağlı monoton fonksiyonların sayısı tam olarak bilinmemektedir. Daha düşük tahmin kolayca elde edilebilir:

burada - n/2'nin tamsayı kısmıdır.

Yukarıdan bir fazla tahmin almak kadar kolay:

Bu tahminlerin iyileştirilmesi, modern araştırmanın önemli ve ilginç bir görevidir.

tamlık kriteri

Şimdi, bir fonksiyonlar sisteminin tamlığı için gerekli ve yeterli koşulları belirleyen bir tamlık kriteri (Post teoremi) formüle etme ve kanıtlama konumundayız. Tamlık kriterinin formülasyonuna ve ispatına, yine bağımsız olarak ilgi çeken birkaç gerekli önermeyle başlayalım.

Önlem 2.7. Kendinden ikili olmayan bir fonksiyonla ilgili Lemma.

f(x 1 , ... , x n)П S ise, x ve `x fonksiyonlarını değiştirerek ondan bir sabit elde edebiliriz.

Kanıt. fÏS olduğundan, değişkenlerin bir dizi değeri vardır.
=(a 1 ,...,a n) öyle ki

f(`a 1 ,...,`a n) = f(a 1 ,...,a n)

f işlevindeki argümanları değiştirelim:

x i ile değiştirilir ,

yani, ayarlıyoruz ve işlevi göz önünde bulunduruyoruz

Böylece bir sabitimiz oldu (ancak ne tür bir sabit olduğu bilinmiyor: 0 veya 1). ð

Önlem 2.8. Tekdüze olmayan bir fonksiyon üzerinde Lemma.

f(x 1 ,...,x n) fonksiyonu monoton değilse, f(x 1 ,...,x n) П M ise, değişkenleri değiştirerek ve 0 ve 1 sabitlerini değiştirerek olumsuzlanabilir.

Kanıt. f(x 1 ,...,x n) П M olduğundan, değişkenlerinin kümeleri ve değerleri vardır, , , öyle ki , ve i'nin en az bir değeri için bir i'ye sahibiz< b i . Выполним следующую замену переменных функции f:

x i ile değiştirilecek

Böyle bir ikameden sonra, j(x) değişkenli bir fonksiyon elde ederiz, bunun için:

Bu, j(x)=`x anlamına gelir. Lemma kanıtlanmıştır. ð

Önlem 2.9. Doğrusal olmayan bir fonksiyonda Lemma.

f(x 1 ,...,x n) П L ise, o zaman 0, 1 sabitlerini değiştirerek ve `x fonksiyonunu kullanarak, ondan x 1 & x 2 fonksiyonu elde edilebilir.

Kanıt. f'yi bir DNF (örneğin, mükemmel bir DNF) olarak temsil ediyoruz ve ilişkileri kullanıyoruz:

Örnek. Bu dönüşümlerin uygulanmasına iki örnek verelim.

Böylece, ayırıcı normal formda yazılmış bir fonksiyon, yukarıdaki ilişkileri, açma parantezlerini ve basit cebirsel dönüşümleri uyguladıktan sonra, mod 2 polinomuna (Zhegalkin polinomu) dönüşür:

burada A 0 bir sabittir ve A i, x 1 ,..., x n , i = 1, 2, ... , r'den bazı değişkenlerin birleşimidir.

Her A i bağlacı yalnızca bir değişkenden oluşuyorsa, f, önermenin koşuluyla çelişen doğrusal bir fonksiyondur.

Bu nedenle, f fonksiyonu için Zhegalkin polinomu en az iki çarpan içeren bir terim içerir. Genelliği kaybetmeden, bu faktörler arasında x 1 ve x 2 değişkenlerinin olduğunu varsayabiliriz. Daha sonra polinom aşağıdaki gibi dönüştürülebilir:

f = x 1 x 2 f 1 (x 3 ,..., x n) + x 1 f 2 (x 3 ,..., x n) + x 2 f 3 (x 3 ,..., xn) + f 4 (x 3 ,..., x n),

burada f 1 (x 3 ,..., x n) ¹ 0 (aksi halde polinom, x 1 x 2 bağlacını içeren bağlacı içermez).

(a 3 ,...,a n) f 1 (a 3 ,...,a n) = 1 olacak şekilde olsun.

j(x 1 ,x 2) = f(x 1 ,x 2 , a 3 ,...,a n) = x 1 x 2 +ax 1 +bx 2 +g ,

burada a, b, g, 0 veya 1'e eşit sabitlerdir.

Elimizdeki olumsuzlama işlemini kullanalım ve j(x 1 ,x 2)'den kaynaklanan y(x 1 ,x 2) fonksiyonunu aşağıdaki gibi ele alalım:

y(x 1 ,x 2) = j(x 1 +b, x 2 +a)+ab+g.

açık ki

y(x 1 ,x 2) =(x 1 +b)(x 2 +a)+a(x 1 +b)+b(x 2 +a)+g+ab+g = x 1 x 2 .

Buradan,

y(x 1 ,x 2) = x 1 x 2 .

Lemma tamamen kanıtlanmıştır. ð

Önlem 2.10. Tamlık kriterinin ana önermesi.

Mantık cebir fonksiyonlarının F=( f ) sınıfı, birliği korumayan, 0'ı korumayan, kendi kendine ikili olmayan ve monoton olmayan fonksiyonlar içeriyorsa:

daha sonra bu sistemin fonksiyonlarından, süperpozisyon işlemleri ve değişkenlerin değiştirilmesi ile 0, 1 sabitleri ve fonksiyonu elde edilebilir.

Kanıt. Bir fonksiyon düşünelim. Daha sonra

.

Aşağıda 1) ve 2) olarak gösterilen iki müteakip değerlendirme durumu mümkündür.

1). Kimlik kümesindeki işlev 0 değerini alır:

.

Fonksiyonun tüm değişkenlerini x değişkeni ile değiştirelim. Daha sonra fonksiyon

Çünkü

Ve .

Kendinden ikili olmayan bir işlev alın. İşlevi zaten elde ettiğimiz için, kendinden ikili olmayan işlev lemma (lemma 2.7. ) den bir sabit elde edebilirsiniz. İkinci sabit, kullanılarak birinciden elde edilebilir. Böylece, ele alınan ilk durumda, sabitler ve olumsuzlama elde edilir. . İkinci durum ve onunla birlikte tamlık kriterinin ana lemması tamamen kanıtlanmıştır. ð

Teorem 2.11. Mantık cebirinin fonksiyon sistemleri için tamlık kriteri (Post teoremi).

F = (f i ) fonksiyonları sisteminin eksiksiz olması için, beş kapalı sınıf olan T 0 , T 1 , L , S, M'nin hiçbirinde tamamen yer almaması gerekli ve yeterlidir, yani, F'deki T 0 , T 1 , L , S, M sınıflarının her biri, bu sınıfa ait olmayan en az bir fonksiyon vardır.

gereklilik. F bir tam sistem olsun. F'nin belirtilen sınıflardan birinde yer aldığını varsayalım, onu K ile gösterin, yani. F Н K. K tam bir sistem olmayan kapalı bir sınıf olduğundan, son dahil etme imkansızdır.

Yeterlilik. F = (f i ) fonksiyon sisteminin tamamen beş kapalı sınıf T 0 , T 1 , L , S, M'nin hiçbirinde içermemesine izin verin. F fonksiyonlarını alın:

Ardından, ana lemmaya (lemma) dayalı olarak 2.10 ) 0'ı korumayan bir işlevden, 1'i korumayan bir işlevden, kendinden ikili olmayan ve monoton olmayan işlevlerden, 0, 1 sabitlerini ve olumsuzlama işlevini alabilirsiniz:

.

Doğrusal olmayan fonksiyon lemmasına ( Lemma 2.9 ) sabitlerden, olumsuzlamadan ve doğrusal olmayan bir fonksiyondan bir bağlaç elde edebilirsiniz:

.

fonksiyon sistemi - mantık cebirinin herhangi bir işlevini mükemmel bir ayırıcı normal form biçiminde temsil etme olasılığına ilişkin teoreme göre eksiksiz bir sistem (ayrılmanın, biçimdeki bağlaç ve olumsuzlama yoluyla ifade edilebileceğini unutmayın) ).

Teorem tamamen ispatlanmıştır. ð

Örnekler.

1. f(x,y) = x|y fonksiyonunun tam bir sistem oluşturduğunu gösterelim. x½y işlevinin bir değerler tablosunu oluşturalım:

f(0,0) = 1, yani x | ypT 0 .

f(1,1) = 0, yani x | evet 1

f(0,0) = 1, f(1,1) = 0, dolayısıyla x | evet

f(0,1) = f(1,0) = 1, - zıt kümelerde x | y aynı değerleri alır, dolayısıyla x | evet.

Son olarak, fonksiyonun doğrusal olmadığı anlamına gelir
x | y.

Tamlık kriterine göre f(x,y) = x | y tam bir sistem oluşturur. ð

2. Fonksiyonlar sisteminin olduğunu gösterelim. eksiksiz bir sistem oluşturur.

Gerçekten mi, .

Böylece, sistemimizin fonksiyonları arasında, 0'ı korumayan bir fonksiyon, 1'i korumayan bir fonksiyon, öz ikili olmayan, monoton olmayan ve doğrusal olmayan fonksiyonlar bulduk. Bütünlük kriterine dayanarak, fonksiyonlar sisteminin şu şekilde olduğu iddia edilebilir: eksiksiz bir sistem oluşturur. ð

Böylece, tamlık kriterinin mantık cebirindeki fonksiyon sistemlerinin tamlığını belirlemek için yapıcı ve verimli bir yol sağladığını gördük.

Şimdi tamlık kriterinin üç doğal sonucunu formüle edelim.

sonuç 1. Mantık cebirinin tüm fonksiyon kümesiyle (K¹P 2) örtüşmeyen herhangi bir kapalı K sınıfı fonksiyon, inşa edilmiş kapalı sınıflardan en az birinde bulunur.

Tanım. Kapalı K sınıfı denir ön tamamlama, K eksikse ve herhangi bir fW işlevi için K sınıfı È (f)-tamamlanır.

Tanımdan, önceden tamamlanmış bir sınıfın kapalı olduğu anlaşılmaktadır.

Sonuç 2. Mantık cebirinde yalnızca beş önceden tamamlanmış sınıf vardır, yani: T 0 ,T 1 , L , M , S .

Sonucu kanıtlamak için, yalnızca bu sınıflardan hiçbirinin diğerinde yer almadığını doğrulamak gerekir; bu, örneğin aşağıdaki işlevlerin farklı sınıflara ait olduğu tablo ile onaylanır:

Sonuç 3. Herhangi bir eksiksiz işlev sisteminden, dörtten fazla işlev içermeyen eksiksiz bir alt sistem seçilebilir.

Tamlık kriterinin ispatından, beşten fazla fonksiyonun ayırt edilemeyeceği sonucu çıkar. Ana lemmanın ispatından (lemma 2.10 ) bunu takip eder ya kendi kendine ikili değildir ya da kimliğini korumaz ve monoton değildir. Bu nedenle, dörtten fazla fonksiyona gerek yoktur.

Bilim camiasında, bu konuda iyi bilinen bir şaka "doğrusal olmama", "fil olmayan" ile karşılaştırılır - "filler" dışındaki tüm canlılar "fil değildir". Benzerlik, birkaç istisna dışında çevremizdeki dünyadaki çoğu sistem ve olgunun doğrusal olmaması gerçeğinde yatmaktadır. Buna rağmen, okulda bize "doğrusal" düşünme öğretiliyor; bu, ister fiziksel, ister biyolojik, psikolojik veya sosyal yönleri olsun, Evrenin her yeri kaplayan doğrusal olmayanlığını algılamaya hazır olmamız açısından çok kötü. Doğrusal olmama, çevredeki dünyanın bilişinin ana zorluklarından birini kendi içinde yoğunlaştırır, çünkü toplam kütlelerindeki sonuçlar nedenlerle orantılı değildir, iki neden etkileşim halindeyken ek değildir, yani sonuçlar daha fazladır. basit bir süperpozisyondan daha karmaşık, nedenlerin işlevleri. Yani aynı anda hareket eden iki sebebin varlığı ve tesiriyle elde edilen sonuç, her bir sebebin ayrı ayrı varlığında, başka bir sebebin yokluğunda elde edilen sonuçların toplamı değildir.

Tanım 9. Bazı X aralığında r-f(lz) işlevi Z değerleri kümesiyle tanımlanır ve y = /(z) işlevi Z kümesinde tanımlanır, o zaman y işlevi karmaşık bir işlevdir x (veya fonksiyonun üst üste binmesi) ve z değişkeni - karmaşık bir fonksiyonun bir ara değişkeni.

Kontrol, üç klasik yönetim fonksiyonunun - muhasebe, kontrol ve analiz (geriye dönük) üst üste binmesi olarak temsil edilebilir. Entegre bir yönetim işlevi olarak kontrol, yalnızca bir çözüm hazırlamayı değil, aynı zamanda uygun yönetim araçlarını kullanarak uygulanması üzerinde kontrol sağlamayı da mümkün kılar.

Bilindiği gibi /50/, herhangi bir zaman fonksiyonu, farklı periyotlar, genlikler ve fazlara sahip basit harmonik fonksiyonların bir üst üste binmesi (kümesi) olarak temsil edilebilir. Genel olarak, P(t) = f(t),

Geçici veya dürtü tepkileri deneysel olarak belirlenir. Süperpozisyon yöntemine göre kullanıldıklarında, seçilen girdi eylem modeli önce temel zaman fonksiyonlarına ayrıştırılır ve ardından bunlara verilen yanıtlar toplanır.Son işleme bazen evrişim denir ve ifadelerdeki integraller (24) .. (29) evrişim integralleridir, bunlardan integrali daha basit olan seçilir.

Bu teorem, koşullu ekstremum problemini koşulsuz ekstremum problemlerinin bir süperpozisyonuna indirger. Aslında, R (g) fonksiyonunu tanımlarız

Üst üste binme ((>(f(x))), burada y(y) bir değişkenin azalmayan dışbükey bir fonksiyonudur, /(x) bir dışbükey fonksiyondur, bir dışbükey fonksiyondur.

Örnek 3.28. Örnek 3.27'ye geri dönelim. Şek. 3.24, bu örnekteki niceleyicilere karşılık gelen iki üyelik fonksiyonunun üst üste bindirilmesinin sonucunu kesikli noktalı bir eğri olarak gösterir. 0.7'lik bir kesme seviyesi kullanılarak, x ekseni üzerinde bulanık aralıklar elde edildi. Artık dispeçrenin planın değişmesini beklemesi gerektiğini söyleyebiliriz.

Süperpozisyon yönteminden farklı olarak F fonksiyonunu tanımlamanın başka bir yolu, herhangi bir niceleyiciyi başka bir niceleyiciye uygularken, orijinal üyelik fonksiyonunun belirli bir monoton dönüşümünün meydana gelmesidir; veya başkası.

Örnek 3.29. Şek. Şekil 3.25, XA ve X'in niceleyici ile sıklıkla eşleştiği durum için üst üste bindirme ve esneme ile kesme ile elde edilen iki sonucu göstermektedir. Aradaki fark, süperpozisyonun genellikle üyelik işlevinde sıklıkla meydana gelen değerleri seçmesi gibi görünüyor. Kaydırma ve uzatma durumunda, sonucu, istenirse örneğin çok sık değerle yaklaşık olarak tahmin edilebilecek olan, sık-sık sık değerine sahip yeni bir niceleyicinin ortaya çıkışı olarak yorumlayabiliriz.

Kesin olarak artan bir fonksiyon ile bir tercih ilişkisini temsil eden bir fayda fonksiyonunun üst üste binmesinin de bu tercih ilişkisini temsil eden bir fayda fonksiyonu olduğunu gösterin. Aşağıdaki işlevlerden hangisi böyle bir dönüşüm görevi görebilir?

Bağıntılardan (2) ilki, tekdüze azalmayan mutlak sürekli fonksiyonlar ailesine ait her bir F(x) fonksiyonunun bir ve sadece bir sürekli w(j) fonksiyonu ile ilişkili olduğu kuralın bir kaydından başka bir şey değildir. Bu kural doğrusaldır, yani süperpozisyon ilkesi bunun için doğrudur

Kanıt. Eşleme F sürekli ise, М0 işlevi, sürekli fonksiyonların üst üste binmesi olarak süreklidir. İddianın ikinci bölümünü kanıtlamak için, işlevi göz önünde bulundurun.

Karmaşık e fonksiyonları (süperpozisyonlar)

İşlevsel dönüşüm yöntemi aynı zamanda buluşsal bir yaklaşımın kullanılmasını da içerir. Örneğin, B ve C operatörleri olarak logaritmik dönüşümlerin kullanılması, tanımlanabilir modeller oluşturmak için bilgi kriterlerine ve güçlü bir bilgi teorisi aracının kullanımına yol açar. B operatörü, (.) işleviyle çarpma operatörlerinin üst üste binmesi olsun ve K0 () işleviyle kayması olsun, C operatörü - operatör

Burada, (1)-(3) sayılı varyasyonel problemlerin çözümünün sonuçları genel hatlarıyla sunulacaktır. Sıralı doğrusallaştırma yöntemiyle (19–21) 1962–1963'te, yöntemin teknolojisi yeni şekillenmeye başladığında ve test edilirken çözüldüler. Bu nedenle, sadece bazı ayrıntılara odaklanacağız. Her şeyden önce, C ve C2 fonksiyonlarının, bir tabloda verilenler de dahil olmak üzere yardımcı fonksiyonların üst üste binmesi olan oldukça karmaşık ifadelerle verildiğini not ediyoruz. Bu nedenle eşlenik sistemi çözerken φ=-fx tabloda belirtilen işlevleri kullanarak. Tipik olarak, bu tür tablolar, bağımsız argümanın değişim bölgesindeki bir dizi düğüm için az sayıda değer içerir ve aralarında, daha doğru enterpolasyon yöntemlerinin kullanılması nedeniyle haklı olmadığı için, fonksiyon doğrusal olarak enterpolasyona tabi tutulur. tablo değerlerinin yanlışlığı (kural olarak, deneysel nitelikteki işlevsel bağımlılıklar tablolarda belirtilir). Bununla birlikte, amaçlarımız için, türevlenebilir / (x, u) işlevlerine ihtiyacımız var, bu nedenle bir tablo işlevini tamamlamanın düzgün yöntemlerini (örneğin, spline'ları kullanarak) tercih etmeliyiz.

Şimdi (DA ve (q) frekans niceleyicilerin bazı değerlerine karşılık gelen keyfi fonksiyonlar olsun. Şekil 3.23, bu fonksiyonlara karşılık gelen iki tek kamburlu eğriyi göstermektedir. Üst üste gelmelerinin sonucu, bir ile gösterilen çift kamburlu bir eğridir. kesikli çizgi Anlamı nedir Örneğin, (EVET nadirdir ve (d - sıklıkla,

F'yi bu şekilde tanımlamanın avantajı, monoton dönüşümler altında üyelik fonksiyonunun formunun önemli ölçüde değişmemesidir. Tek modluluğu veya monotonluğu korunur ve fonksiyonun (2.16) yeni biçiminden geçiş yamuk bir forma sahiptir, ardından doğrusal süperpozisyon (2.15) yamuk bulanık bir sayıdır (bölüm hesaplama kuralı kullanılarak kolayca kanıtlanır). Ve üyelik fonksiyonlarıyla yapılan işlemler, köşeleri olan işlemlere indirgenebilir. Yamuk sayısını (2.16) (ab, a2, az, a4) olarak belirtirsek, burada a yamuk köşelerinin apsislerine karşılık gelir, o zaman

- (geç lat. superpositio, - bindirme, lat. superpositus'tan - üstüne serilir) (kompozisyon) - mantıksal matematiksel işlem. c.l.'den elde etmekten oluşan hesap. verilen yeni fonksiyon g (f)'nin belirli bir hesabının verilen f ve g fonksiyonları (ifade g ... ... Felsefi Ansiklopedi

Süperpozisyon (bindirme) terimi, aşağıdaki kavramlara atıfta bulunabilir: Fonksiyonların süperpozisyon bileşimi (karmaşık fonksiyon) Süperpozisyon ilkesi, fizik ve matematikte süreçlerin (örneğin dalgaların) üst üste binmesini tanımlayan bir ilkedir ve sonuç olarak, ... ... Vikipedi

Fonksiyonların bileşimi, karmaşık bir işlevin iki işlevinin bileşimi ... Matematiksel Ansiklopedi

Bu terimin başka anlamları da vardır, bkz. Süperpozisyon. Kuantum mekaniği ... Vikipedi

Bu makale veya bölüm, kaynakların veya harici bağlantıların bir listesini içerir, ancak dipnot eksikliği nedeniyle bireysel ifadelerin kaynakları belirsizliğini koruyor ... Wikipedia

Ayrık işlevsel sistemler teorisinde, bir Boole işlevi, bir Boole kümesinin olduğu ve n'nin negatif olmayan bir tam sayı olduğu, işlevin yakınlığı veya yeri olarak adlandırılan bir tür işlevidir. 1 (bir) ve 0 (sıfır) öğeleri standart olarak yorumlanır ... ... Wikipedia

Matematiğin ve matematiğin temelleri için en önemlilerinden biri. arıtma olarak hizmet eden kavramların mantık sınıflarını içerir. etkili bir şekilde hesaplanabilir bir aritmetik fonksiyon ve etkili bir şekilde karar verilebilir bir aritmetik yüklem kavramları ve nihayetinde ve ... ... Felsefi Ansiklopedi

Bir sürünün değerlerini hesaplayan bir fonksiyon, önceden belirlenmiş verimli bir prosedür veya algoritma kullanılarak gerçekleştirilebilir. Hesaplamalı süreçlerin karakteristik bir özelliği, ilk verilerden sırayla meydana gelen problemlerin istenen değerlerinin hesaplanmasıdır ... ... Matematiksel Ansiklopedi

Bu makalenin içeriğini "Karmaşık bir fonksiyonun türevi" makalesine aktarmak gerekir. Makaleleri birleştirerek projeye yardımcı olabilirsiniz. Birleştirmenin tavsiye edilebilirliğini tartışmanız gerekiyorsa, bu şablonu şablonla değiştirin ((birleştirmek için)) ... Wikipedia

- (lat. kompozisyon kompozisyonu, ciltleme, ekleme, bağlantı): Vikisözlük'te "kompozisyon" için bir giriş vardır Sanat Kompozisyon (güzel sanatlar), tasarım veren bir sanat formunun düzenleyici bir bileşenidir ... Wikipedia

Kitabın

• Ayrık Matematik. Temel küme-teorik yapılar. Bölüm VI, A. I. Shirokov. Kılavuz, "Ayrık matematiğin temel küme-teorik yapıları" bölümünün VI kısmıdır. Ch'de. XI Aşağıdaki kavramlar dikkate alınır: işlevlerin bileşimleri (§1); fonksiyonlar,…

Bir fonksiyonun tanımı, ayar alanı ve değer seti. Fonksiyon gösterimi ile ilgili tanımlar. Karmaşık, sayısal, gerçek, monoton ve çok değerli fonksiyonların tanımları. Sınırlandırılmış fonksiyonlar için maksimum, minimum, üst ve alt sınırların tanımları.

İşlev y=f (X) X kümesinin her x öğesinin Y kümesinin bir ve yalnızca bir y öğesiyle ilişkilendirildiği yasa (kural, eşleme) denir.

X kümesi denir işlev kapsamı.
y öğeleri kümesi ∈ Y X kümesinde ön görüntüleri olan , denir işlev değerleri kümesi(veya menzil).

İhtisas işlevler bazen denir tanım kümesi veya bir dizi görev fonksiyonlar.

eleman x ∈ X isminde işlev bağımsız değişkeni veya bağımsız değişken.
y elemanı ∈ Y isminde fonksiyon değeri veya bağımlı değişken.

Eşleme f'nin kendisi denir fonksiyon karakteristiği.

Karakteristik f, eğer iki eleman ve tanım kümesinden eşit değerlere sahipse: , o zaman özelliğine sahiptir.

Özelliği ifade eden karakter, fonksiyon değer öğesinin karakteri ile aynı olabilir. Yani, şu şekilde yazabilirsiniz: Aynı zamanda, y'nin işlev değerleri kümesinden bir öğe olduğunu ve x öğesinin y öğesiyle ilişkilendirildiği bir kural olduğunu hatırlamakta fayda var.

Fonksiyonun kendisini hesaplama süreci üç adımdan oluşur. İlk adımda, X kümesinden bir x elemanı seçiyoruz. Ayrıca, kural yardımıyla, x elemanı Y kümesinin elemanı ile ilişkilendirilir. Üçüncü adımda bu eleman y değişkenine atanır.

Fonksiyonun özel değeri bağımsız değişkeninin seçilen (özel) değeri için işlevin değerini adlandırın.

f fonksiyonunun grafiğiçiftler kümesi denir.

Karmaşık işlevler

Tanım
ve fonksiyonları verilsin. Ayrıca, f fonksiyonunun alanı, g fonksiyonunun bir dizi değerini içerir. O zaman g fonksiyonunun etki alanındaki her t elemanı, bir x elemanına karşılık gelir ve bu x, y'ye karşılık gelir. Bu yazışma denir karmaşık fonksiyon: .

Karmaşık bir fonksiyon da denir fonksiyonların bileşimi veya üst üste binmesi ve bazen şu şekilde anılır:

Matematiksel analizde, bir fonksiyonun karakteristiği bir harf veya sembolle gösteriliyorsa, o zaman aynı karşılığı verdiği kabul edilir. Bununla birlikte, diğer disiplinlerde, aynı özelliğe sahip, ancak farklı argümanlara sahip eşlemelerin farklı kabul edildiği başka bir notasyon yolu vardır. Yani, eşlemeler ve ayrı kabul edilir. Fizikten bir örnek verelim. Diyelim ki momentumun koordinata bağımlılığını düşünüyoruz. Ve koordinatın zamana bağımlılığını alalım. O halde momentumun zamana bağlılığı karmaşık bir fonksiyondur. Ancak kısa olması için şu şekilde gösterilir: Bu yaklaşımla ve farklı işlevlere sahiptir. Argümanların aynı değerleri ile farklı değerler verebilirler. Matematikte bu gösterim kabul edilmez. Azaltma gerekiyorsa yeni bir özellik girilmelidir. Örneğin . O zaman ve'nin farklı işlevler olduğu açıkça görülür.

Geçerli İşlevler

Fonksiyonun kapsamı ve değerleri kümesi herhangi bir küme olabilir.
Örneğin, sayısal diziler, tanım alanı doğal sayılar kümesi ve değerler kümesi gerçek veya karmaşık sayılar olan işlevlerdir.
Çapraz çarpım da bir fonksiyondur, çünkü iki vektör için ve vektörün yalnızca bir değeri vardır. Burada tanım alanı, olası tüm vektör çiftlerinin kümesidir. Değerler kümesi, tüm vektörlerin kümesidir.
Boole ifadesi bir işlevdir. Tanım alanı, gerçek sayılar kümesidir (veya "0" öğesiyle karşılaştırma işleminin tanımlandığı herhangi bir kümedir). Değer kümesi iki öğeden oluşur - "doğru" ve "yanlış".

Sayısal fonksiyonlar matematiksel analizde önemli bir rol oynar.

Sayısal işlev değerleri gerçek veya karmaşık sayılar olan bir fonksiyondur.

Gerçek veya gerçek fonksiyon değerleri gerçek sayılar olan bir fonksiyondur.

Maksimum ve minimum

Gerçek sayıların bir karşılaştırma işlemi vardır. Bu nedenle, gerçek fonksiyonun değer kümesi sınırlandırılabilir ve en büyük ve en küçük değerlere sahip olabilir.

Gerçek işlev denir yukarıdan sınırlı (aşağıdan), aşağıdaki eşitsizliğin herkes için geçerli olduğu böyle bir M sayısı varsa:
.

Sayı işlevi denir sınırlı, eğer bir M sayısı varsa, öyle ki:
.

Maksimum M (minimum m) f işlevi , bazı X kümelerinde , işlevin argümanının bazı değerleri için değeri olarak adlandırılır , bunun için tümü için ,
.

üst yüz veya tam üst sınır gerçek, yukarıdan sınırlı, fonksiyona, değerlerinin aralığını yukarıdan sınırlayan sayıların en küçüğü denir. Yani, bu, herkes için ve herhangi biri için, işlevinin değeri s′ : 'yi aşan böyle bir argümanın olduğu bir s sayısıdır.
Fonksiyonun üst sınırı şu şekilde gösterilebilir:
.

Yukarıdan sınırsız bir fonksiyonun üst sınırı

alt yüz veya hassas alt sınır gerçek, aşağıdan sınırlı, fonksiyon, değerlerinin aralığını aşağıdan sınırlayan sayıların en büyüğü olarak adlandırılır. Yani, bu bir i sayısıdır ve kendisi için herkes ve herhangi biri için öyle bir argüman vardır ki, fonksiyonun değeri i′'den küçüktür.
Bir fonksiyonun alt sınırı şu şekilde gösterilebilir:
.

Aşağıdan sınırsız bir fonksiyonun alt sınırı sonsuzdaki noktadır.

Böylece, boş olmayan bir X kümesi üzerindeki herhangi bir gerçek fonksiyonun bir üst ve alt sınırı vardır. Ancak her işlevin bir maksimumu ve bir minimumu yoktur.

Örnek olarak, açık bir aralıkta tanımlanan bir işlevi düşünün.
Bu aralıkta yukarıdan değerle sınırlıdır. 1 ve altında - değer 0 :
hepsi için .
Bu işlevin üst ve alt yüzleri vardır:
.
Ama maksimumu ve minimumu yoktur.

Aynı işlevi aralıkta ele alırsak, o zaman bu kümenin üstünde ve altında sınırlıdır, üst ve alt sınırları vardır ve bir maksimumu ve bir minimumu vardır:
hepsi için ;
;
.

Monoton fonksiyonlar

Artan ve Azalan Fonksiyonların Tanımları
Fonksiyonun bazı X gerçek sayıları kümesinde tanımlanmasına izin verin. işlev denir kesinlikle artan (kesinlikle azalan)
.
işlev denir azalmayan (artmayan), aşağıdaki eşitsizliğin geçerli olduğu tüm türler için:
.

Monoton bir fonksiyonun tanımı
işlev denir monoton azalmıyorsa veya artmıyorsa.

Birden Çok Değerli İşlevler

Çok değerli bir fonksiyon örneği. Dalları farklı renklerle işaretlenmiştir. Her dal bir özelliktir.

Fonksiyonun tanımından da anlaşılacağı gibi, tanım alanındaki her x elemanı, değerler kümesinden sadece bir elemanla ilişkilendirilir. Ancak, x öğesinin birkaç veya sonsuz sayıda görüntüye sahip olduğu eşlemeler vardır.

Örnek olarak, işlevi düşünün yay sinüsü: . Bu fonksiyonun tersidir sinüs ve denklemden belirlenir:
(1) .
Aralığa ait bağımsız değişken x'in belirli bir değeri için , bu denklem sonsuz sayıda y değerini karşılar (şekle bakın).

Denklem (1)'in çözümlerine bir kısıtlama getirelim. İzin vermek
(2) .
Bu koşul altında, verilen değer denklemin (1) yalnızca bir çözümüne karşılık gelir. Yani, (2) koşulu altında denklem (1) ile tanımlanan karşılık gelme bir fonksiyondur.

Koşul (2) yerine, formun başka herhangi bir koşulu empoze edilebilir:
(2.n) ,
burada n bir tamsayıdır. Sonuç olarak, n'nin her değeri için, diğerlerinden farklı olarak kendi fonksiyonumuzu elde ederiz. Bu işlevlerin birçoğu çok değerli işlev. Ve (2.n) koşulu altında (1)'den belirlenen fonksiyon şu şekildedir: çok değerli fonksiyon dalı.

Bu, bazı kümelerde tanımlanan işlevlerin bir koleksiyonudur.

Çok değerli işlev dalıçok değerli işlevde yer alan işlevlerden biridir.

tek değerli fonksiyon bir fonksiyondur.

Referanslar:
O.I. İblisler. Matematiksel analiz üzerine dersler. Bölüm 1. Moskova, 2004.
L.D. Kudryavtsev. Matematiksel analiz kursu. Cilt 1. Moskova, 2003.
SANTİMETRE. Nikolsky. Matematiksel analiz kursu. Cilt 1. Moskova, 1983.

Tek döngülü (hafıza öğeleri içermeyen) ayrık mantık cihazları, çıktıda belirli bir dizi mantık cebir işlevi uygular `Fm=(F 1 ,F 2 ,…,Fm), her an yalnızca cihaz girişlerinin durumuna bağlı olan `x n =(X 1 ,X 2 ,…,xn): `F m = `F m(x n). Uygulamada, bu tür cihazlar, belirli bir seti (sistemi) uygulayan ayrı bölünemez elemanlardan tasarlanır ve üretilir ( F) bazı öğelerin çıktılarını diğerlerinin girdilerine bağlayarak cebirin temel işlevleri.

Mantıksal cihazlar tasarlarken aşağıdaki sorular önemlidir.

1. Bir temel işlevler sistemi ( F). çıktı fonksiyonları nelerdir F ben fonksiyonları kullanılarak elde edilebilir ( F}?

2. Çıktı Boole işlevleri kümesi ( F) (özellikle, mantık cebirinin tüm fonksiyon setine eşittir) R 2). Temel fonksiyonların ilk sistemi ne olmalıdır ( F), bu, kümenin işlevlerinden herhangi birinin çıktısında elde edilmesini sağlar ( F}?

Bu sorulara makul bir cevap için, fonksiyon sistemlerinin süperpozisyon, kapalılık ve tamlık kavramları kullanılır.

Tanım. Mantıksal bağlaçlar kümesini düşünün ( F) bazı işlev sistemlerine karşılık gelen ( F} . Üst üste binme{F), ( üzerinde bir formül tarafından uygulanabilen herhangi bir j işlevidir. F}.

Uygulamada, süperpozisyon, ('den) yerine geçen işlevlerin sonucu olarak temsil edilebilir. F) aynı kümeden bir işleve argüman olarak.

örnek 1. Bir işlev sistemi düşünün ( F} = {F 1 (X) =x, f 2 (x, y)= X&y, f 3 (x, y)=XÚ y). Fonksiyonda yerine koyma F 3 (x, y) ilk bağımsız değişken yerine X işlev F 1 (X), ikinci yerine - F 2 (x, y), süperpozisyonu elde ederiz H(x, y)=F 3 (F 1 (X), F 2 (x, y))=xÚ X& de. Yerine koymanın fiziksel uygulaması Şekil 1.18'de verilmiştir.

Tanım.İzin vermek M- mantık cebirinin bazı fonksiyonları ( P 2). Tüm süperpozisyonların kümesi M isminde kapatma setleri M ve [ ile gösterilir M]. Edinme [ M]orijinal set tarafından M isminde kapanış işlemi. Bir demet M isminde işlevsel olarak kapalı sınıf, Eğer [ M] = M. altküme MÍ M isminde M'de işlevsel olarak eksiksiz sistem, Eğer [ M] = M.

Kapatma [ M], elde edilebilecek tüm işlev kümesidir. M süperpozisyon işlemini uygulayarak, yani tüm olası ikameler.

Notlar. 1. Açıkçası, herhangi bir işlev sistemi ( F) kendi içinde işlevsel olarak eksiksizdir.

2 . Genelliği kaybetmeden, aynı işlevin olduğunu varsayabiliriz. F(X)=x değişkenlerin doğruluk değerlerini değiştirmeyen , başlangıçta herhangi bir fonksiyon sistemine dahil edilir.

Örnek 2. Aşağıda ele alınan fonksiyon sistemleri için ( F) aşağıdakileri yapın:

1) kapanışı bul [ F],

2) sistemin ( F) kapalı sınıf,

3) içinde işlevsel olarak eksiksiz sistemler bulun ( F}.

Çözüm.

BEN. ( F}={0} . İşlevi değiştirirken ( fº 0) kendi içine, anladık, yani. yeni işlevler oluşturulmaz. Bu şu anlama gelir: [ F] = {F). Ele alınan sistem işlevsel olarak kapalı bir sınıftır. İçindeki işlevsel olarak eksiksiz sistem birdir ve bütüne eşittir ( F}.

II. ( F} = {0,Ø } . Değiştirme Ø (Ø X), orijinal sistemi resmi olarak genişletmeyen özdeş bir işlev verir. Ancak, Ø (0) yerine aynı birim elde ederiz - orijinal sistemde olmayan yeni bir fonksiyon: Ø (0)=1 . Diğer tüm ikamelerin uygulanması yeni fonksiyonlara yol açmaz, örneğin: ØØ 0 = 0, 0(Ø X)=0.

Böylece, süperpozisyon işleminin uygulanması, orijinaline kıyasla daha geniş bir fonksiyon kümesi elde etmeyi mümkün kılmıştır [ F]=(0,Ø ,1). Bu katı bir giriş anlamına gelir: ( F} Ì [ F]. Kaynak sistemi ( F) işlevsel olarak kapalı bir sınıf değildir. Sistemin kendisinden başka F) içinde işlevsel olarak tamamlanmış başka sistem yoktur, çünkü bir işlevden kısıtlanması durumunda f= 0, ikame ile olumsuzlanamaz ve aynı sıfır, tek bir olumsuzlama işlevinden elde edilemez.

III. ( F) = (& ,Ú ,Ø ) Bu sistemin kapanışı, mantık cebirinin tüm fonksiyon kümesidir. P 2 , çünkü herhangi birinin formülü, temel işlevleri kullanan DNF veya CNF olarak temsil edilebilir ( F) = (& ,Ú ,Ø). Bu gerçek, dikkate alınan işlevler sisteminin eksiksiz olduğunun yapıcı bir kanıtıdır. P 2: [F]= P 2 .

çünkü içinde P 2, ( dışında sonsuz sayıda başka işlev içerir. F) = (& ,Ú ,Ø ), bu kesin bir oluşum anlamına gelir: ( F}Ì[ F]. Ele alınan sistem işlevsel olarak kapalı bir sınıf değildir.

Sistemin kendisine ek olarak, alt sistemler ( F) 1 = (& ,Ø ) ve ( F) 2 = (Ú ,Ø ). Bu, de Morgan kuralları kullanılarak, mantıksal toplama işlevi Ú'nin (& , Ø) cinsinden ve mantıksal çarpma işlevinin &'nin (Ú, Ø) cinsinden ifade edilebileceği gerçeğinden çıkar:

(X & de) = Ø (` XÚ` de), (X Ú de) = Ø ( X &`de).

İşlevsel olarak tamamlanmış diğer alt sistemler ( F) HAYIR.

İşlev alt sisteminin eksiksizliğini kontrol etme ( F) 1 M ( F) tüm sistemde ( F) indirgenerek üretilebilir ( F) 1'den diğerine, açıkça ( F) sistemi.

Alt sistemin eksikliği ( F) 1 inç ( F) ['nin tam olarak oluştuğu kanıtlanarak doğrulanabilir F 1 ] М [ F].

Tanım. altküme MÍ M isminde işlevsel temel(temel)sistemler M, Eğer [ M] = M ve herhangi bir işlevin dışlanmasından sonra, geri kalanlar kümesi tam değildir. M .

Yorum. Fonksiyon sisteminin temelleri (F) tüm işlevsel olarak eksiksiz alt sistemleridir (F) 1 , tamlık kaybı olmadan indirgenemez (F).

Örnek 3. Örnek 2'de ele alınan tüm sistemler için tabanları bulun.

Çözüm.1 ve 2 numaralı durumlarda, sadece sistemlerin kendileri işlevsel olarak eksiksizdir ve bunları daraltmak imkansızdır. Bu nedenle, onlar da bazdır.

Durum 3'te, işlevsel olarak tamamlanmış iki tane vardır ( F)alt sistemler ( F) 1 = (&,Ø ) ve ( F) 2 =(Ú,Ø ), tamlık kaybı olmadan indirgenemez. Sistemin temelleri olacaklar ( F} = {&,Ú,Ø}.

Tanım. Sisteme izin ver ( F) kapalı bir sınıftır. Onun alt kümesi ( F) 1 M ( F) arandı sınıfı önceden tamamlama{F), Eğer ( F) 1 eksik ( F} ([F 1 ] М [ F]) ve sistemden herhangi bir j işlevi için( F) dahil değil ( F) 1 (jО( F} \ {F) 1) doğrudur: [ JÈ { F} 1 ] = [F], yani ek jk ( F) 1, ('de tamamlar) F} .

Görevler

1. Fonksiyon setlerinin kapalılığını kontrol edin:

a) (Ø); b) (1,Ø); c) ((0111); (10)); d) ((11101110); (0110)); e) ((0001); (00000001); (0000000000000001); ... ).

2. İşlev sistemlerinin eksiksiz olup olmadığını kontrol edin. P 2:

a) (0,Ø); b) ((0101) , (1010) ); v); d) ((0001) , (1010) ).

3. Fonksiyon sisteminin kapanışını ve temelini bulun:

a) (0 , 1 , Ø ); b) ((1000) , (1010), (0101) ); c) ((0001) , (1110), (10) ); d) ((1010) , (0001), (0111) ).

1.10.2 Sabitleri koruyan işlevler. Sınıflar T 0 ve T 1

Tanım.İşlev F(`x n) kaydeder 0 ise F(0,..., 0) = 0. İşlev F(x n) kaydeder 1 eğer F(1, ... , 1) = 1.

çok sayıda özellik N 0 ve 1 depolayan değişkenler sırasıyla, T 0 N Ve T 1 N. 0 ve 1'i koruyan mantık cebirinin tüm fonksiyon kümeleri , Tayin etmek T 0 Ve T 1. Setlerin her biri T 0 ve T 1, kapalı bir ön tamamlama sınıfıdır R 2 .

Temel işlevlerden T 0 ve T 1, örneğin & ve Ú'yi içerir. Herhangi bir fonksiyonun sınıflara ait olması T 0 , T 1, doğruluk tablosundaki değerler vektörünün ilk ve son değeri ile veya fonksiyon analitik olarak belirtildiğinde formüldeki sıfırların ve birlerin doğrudan ikame edilmesiyle kontrol edilebilir.

Tanım.Kopyalamak fonksiyonda birkaç bağımsız değişken yerine aynı değişkenin ikame edildiği böyle bir ikame denir. Aynı zamanda önceden birbirinden bağımsız değer alan kümelerdeki değişkenlerin değerleri hep aynı olacaktır.

GÖREVLER

1.Sınıf üyeliğini kontrol edin T 0 Ve T 1 fonksiyonlar:

a) genelleştirilmiş toplama, b) genelleştirilmiş çarpma, c) sabitler, d) huÚ yz, e) X® de® hu, e) XÅ de, Ve)( X 1 A … Å X n) ® ( y 1 A … Å y m) ne zaman n,mÎ N.

2. Her sınıfın kapalı olduğunu kanıtlayın T 0 Ve T 1 .

3. Eğer F(x n) Ï T 0 , o zaman sabit 1 veya olumsuzlama, ikameyi kopyalayarak ondan elde edilebilir.

4. Eğer F(x n) Ï T 1 , sonra ondan, ikameyi çoğaltarak, 0 sabitini veya olumsuzlamayı elde edebilirsiniz.

5. Her bir sınıfın önceden tamamlanmış olduğunu kanıtlayın T 0 Ve T 1 (örneğin, genişletilmiş sistemi ( F} = {& ,Ú ,Ø }).

6. Sınıfların gücünü bulun T 0 N Ve T 1 N.