Fonksiyon süperpozisyon işlemi. Fonksiyonların süperpozisyonu. Boolean Fonksiyonlarının Özellikleri

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

sonra fonksiyonu çağıracağız bir fonksiyonun süperpozisyonu f(x 1 , x 2 , ... , x n) ve işlevler .

Başka bir deyişle: F = ( f j ) olsun - mutlaka sonlu olmayan bir dizi mantıksal cebir fonksiyonu. Bir f fonksiyonuna, bir veya daha fazla değişkeninin F kümesindeki fonksiyonlarla değiştirilmesiyle bir fonksiyondan elde ediliyorsa, F kümesindeki fonksiyonların süperpozisyonu veya F üzerinde bir fonksiyon denir.

Örnek.

Bir dizi fonksiyon verilsin

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

O zaman F'den fonksiyonların süperpozisyonları örneğin aşağıdaki 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ümedeki fonksiyonların süperpozisyonu

. ð

Tanım.

Fonksiyonlar sisteminin adı tam dolu Değişkenlerin üst üste bindirilmesi ve değiştirilmesi işlemleri kullanılırsa, mantık cebirinin herhangi bir fonksiyonu bu sistemin fonksiyonlarından elde edilebilir. ð

Zaten belirli bir komple sistem setimiz var:

;

Çünkü ;

Çünkü ;

(x+y, xy, 1). ð

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

Kapalı sınıflar.

Mantık cebirinin fonksiyonlarının kümesi (sınıfı) K olarak adlandırılır kapalı sınıf, eğer K'den süperpozisyon ve değişken değiştirme işlemleriyle elde edilen tüm fonksiyonları içeriyorsa ve başka hiçbir fonksiyon içermiyorsa.

K, P 2'den gelen fonksiyonların bir alt kümesi olsun. K'nin kapanışı, süperpozisyon işlemleri ve K kümesindeki fonksiyonların değişkenlerini değiştirme işlemleri kullanılarak temsil edilebilen tüm Boolean fonksiyonlarının kümesidir. Bir K kümesinin kapanışı [K] ile gösterilir.

Kapanış açısından, kapanış ve tamlığın başka tanımlarını da verebiliriz (orijinal olanlara eşdeğer):

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

Eğer [K] = P 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.

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

En önemli kapalı sınıflardan bazılarına bakalım.

1. T 0- 0'ı koruyan fonksiyon sınıfı.

0 sabitini koruyarak f(x 1 , x 2 , ... , x n) mantık cebirinin tüm fonksiyonlarının sınıfını T 0 ile gösterelim, yani f(0, ... , 0 olan fonksiyonlar) ) = 0.

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

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

Ï T 0 olduğu gerçeğinden, örneğin, bunun ayrım ve bağlaç yoluyla ifade edilemeyeceği sonucu çıkar.

T 0 sınıfından f fonksiyonunun tablosu ilk satırda 0 değerini içerdiğinden, T 0'dan gelen fonksiyonlar için yalnızca 2 n - 1 değişken değer kümesinde isteğe bağlı 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 kapalılığı süperpozisyon işlemine göre göstermek yeterlidir, çünkü değişkenlerin değiştirilmesi işlemi x fonksiyonu ile süperpozisyonun özel bir durumudur.

İzin vermek . O halde bunu göstermek yeterlidir. İkincisi eşitlik zincirinden kaynaklanır

2. T 1- 1'i koruyan fonksiyon sınıfı.

1 sabitini koruyarak f(x 1, x 2, ... , x n) mantık cebirinin tüm fonksiyonlarının sınıfını, yani f(1, ... , 1 olan fonksiyonları) T 1 ile gösterelim. ) = 1.

T 1'e ait fonksiyonların ve bu sınıfa ait olmayan fonksiyonların 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ından örneğin x + y'nin ayrım ve bağlaç cinsinden ifade edilemeyeceği sonucu çıkar.

T 0 sınıfına ilişkin sonuçlar önemsiz bir şekilde T 1 sınıfına aktarılır. Böylece elimizde:

T 1 - kapalı sınıf;

.

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

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

L'ye ait olan ve bu sınıfa ait olmayan fonksiyonların 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.

Tam tersini varsayalım. XÚy için belirlenmemiş katsayılara sahip doğrusal bir fonksiyon biçiminde bir ifade arayacağız:

x = y = 0 için a=0'ımız var,

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

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

ama x = 1, y = 1 için 1v 1 ¹ 1 + 1 elde ederiz, bu da xy fonksiyonunun doğrusal olmadığını kanıtlar.

Doğrusal fonksiyonlar sınıfının kapalılığının kanıtı oldukça açıktır.

Doğrusal bir fonksiyon, a 0 , ... , an n katsayısının n+1 değerleri belirtilerek benzersiz bir şekilde belirlendiğinden, n değişkene bağlı fonksiyonların L (n) sınıfındaki doğrusal fonksiyonların sayısı 2'ye eşittir. n+1 .

.

4.S- kendi kendine ikili fonksiyonların sınıfı.

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

Eşitlik tarafından tanımlanan fonksiyona denir fonksiyona ikili .

Açıkçası, ikili fonksiyon tablosu (değişken değer kümelerinin standart sıralamasıyla), fonksiyon değerleri sütununu ters çevirerek (yani 0'ı 1 ve 1 ile 0 ile değiştirerek) orijinal fonksiyon tablosundan elde edilir. ve onu ters çeviriyorum.

Bunu görmek kolaydır

(x 1 Ü x 2)* = x 1 Ü x 2,

(x 1 Ü x 2)* = x 1 Ü x 2 .

Tanımdan (f*)* = f sonucu çıkar, yani f fonksiyonu f*'a dualdir.

Bir fonksiyonun diğer fonksiyonlar aracılığıyla süperpozisyon kullanılarak ifade edilmesine izin verin. Soru şu; uygulayan bir formülün nasıl oluşturulacağı? Kümelerde bulunan tüm farklı değişken sembollerini = (x 1, ..., x n) ile gösterelim.

Teorem 2.6. Eğer j fonksiyonu f, f 1, f 2, ..., f m fonksiyonlarının süperpozisyonu olarak elde edilirse, yani

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

Kanıt.

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

Teorem kanıtlandı. ð

Dualite ilkesi teoremden çıkar: Eğer bir A formülü f(x 1 , ... , x n) fonksiyonunu gerçekleştiriyorsa, o zaman A'dan elde edilen formül, içerdiği fonksiyonları ikili fonksiyonlarıyla değiştirerek elde edilen formül f ikili fonksiyonunu gerçekleştirir. *(x 1 , ... , xn).

P 2'den itibaren tüm öz-dual fonksiyonların sınıfını S ile gösterelim:

S = (f | f* = f)

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

0, 1, xy, xy Ï S .

Kendi kendine ikili fonksiyonun daha az önemsiz bir örneği, fonksiyondur.

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

Süperpozisyona ikili fonksiyon teoremini kullanarak, şunu elde ederiz:

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

Kendi kendine ikili bir işlev için kimlik geçerlidir

setlerde falan ve zıttı diyeceğimiz self-dual fonksiyonu zıt değerler alır. Kendi kendine ikili fonksiyonun tamamen standart tablonun satırlarının ilk yarısındaki değerleri tarafından belirlendiği anlaşılmaktadır. Bu nedenle, n değişkene bağlı fonksiyonların S (n) sınıfındaki öz-dual fonksiyonların sayısı şuna eşittir:

.

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

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

Mantık cebirinde monoton fonksiyon kavramını tanımlamadan önce, onun değişkenleri kümesi üzerinde bir sıralama ilişkisini tanıtmak gerekir.

Setin setten önce geldiğini söylüyorlar (veya "daha fazla değil" veya "küçük veya eşit") ve tüm i = 1, ... , n için a i £ b i ise gösterimini kullanın. Eğer ve ise, o zaman kümenin kesinlikle kümeden önce geldiğini (veya kümeden "kesinlikle daha az" veya "daha az") söyleyeceğiz ve gösterimini kullanacağız. Bu bağıntıların hiçbiri geçerli değilse ve kümelerine karşılaştırılabilir denir. Ö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. Dolayısıyla £ bağıntısı (çoğunlukla öncelik ilişkisi olarak adlandırılır) B n kümesi üzerinde kısmi bir sıradır. 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 dersimizin kapsamını çok aşan son derece önemli bir kavramdır.

Artık monoton fonksiyon kavramını tanımlama fırsatına sahibiz.

Mantıksal cebir fonksiyonunun adı monoton herhangi iki küme için ve eşitsizlik geçerli olacak şekilde . Mantık cebirinin tüm monoton fonksiyonlarının kümesi M ile, n değişkene bağlı tüm monoton fonksiyonların kümesi ise M(n) ile gösterilir.

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

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

x+y, x®y, x°y Ï M .

Monoton fonksiyonlar M sınıfının kapalı bir sınıf olduğunu gösterelim. xОМ olduğundan, kapalılığı doğrulamak için kapalılığı süperpozisyon işlemine göre göstermek yeterlidir, çünkü değişen değişkenlerin işlemi x fonksiyonuyla süperpozisyonun özel bir durumudur.

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

Sırasıyla değişken kümeleri olsun, j, f 1 , ... , f m fonksiyonları ve j fonksiyonunun değişkenleri kümesi bunlardan ve yalnızca f 1 , ... , f m fonksiyonlarında görünen değişkenlerden oluşur. Değişkenin 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ğu nedeniyle

ve f fonksiyonunun monotonluğu nedeniyle

Buradan anlıyoruz

N değişkene bağlı monotonik fonksiyonların sayısı tam olarak bilinmemektedir. Alt sınır kolaylıkla elde edilebilir:

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

Ayrıca yukarıdan bakıldığında çok yüksek bir tahmin olduğu ortaya çıkıyor:

Bu tahminleri hassaslaştırmak modern araştırmanın önemli ve ilginç bir görevidir.

Tamlık kriteri

Artık bir işlevler sisteminin tamlığı için gerekli ve yeterli koşulları belirleyen bir tamlık kriteri (Post teoremi) formüle edip kanıtlayabiliyoruz. Tamlık kriterinin formülasyonuna ve ispatına, bağımsız ilgiye sahip birkaç gerekli lemma ile giriş yapalım.

Lemma 2.7. Kendinden ikili olmayan fonksiyon hakkında Lemma.

Eğer f(x 1 , ... , x n)Ï S ise, x ve `x fonksiyonlarını değiştirerek bundan bir sabit elde edilebilir.

Kanıt. FÏS'den bu yana 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 fonksiyonundaki argümanları değiştirelim:

x i ile değiştirilir ,

yani, fonksiyonu koyalım ve düşünelim

Böylece bir sabit elde etmiş olduk (hangi sabit olduğu bilinmese de: 0 mı yoksa 1 mi). ð

Lemma 2.8. Monotonik olmayan fonksiyonla ilgili Lemma.

Eğer 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 sabitleri değiştirerek ondan bir olumsuzlama elde edilebilir. 1.

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

x yerine ben geçeceğim

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

Lemma 2.9. Doğrusal olmayan fonksiyonla ilgili Lemma.

Eğer f(x 1 ,...,x n) Ï L ise, 0, 1 sabitlerini değiştirerek ve 'x fonksiyonunu kullanarak x 1 & x 2 fonksiyonunu elde edebiliriz.

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

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

Böylece, ayrık normal formda yazılan bir fonksiyon, belirtilen ilişkiler uygulandıktan, parantezlerin açılmasından ve basit cebirsel dönüşümlerden sonra bir polinom mod 2 (Zhegalkin polinomu) haline gelir:

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

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

Sonuç olarak, f fonksiyonu için Zhegalkin polinomunda en az iki faktör içeren bir terim vardır. 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 ,..., x n) + f 4 (x3,...,xn),

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

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

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.

Sahip olduğumuz olumsuzlama işlemini kullanalım ve j(x 1 ,x 2)'den elde edilen 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ça görülüyor 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. ð

Lemma 2.10. Tamlık kriterinin ana lemması.

Mantıksal 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 işlevlerinden, değişkenlerin üst üste bindirilmesi ve değiştirilmesi işlemleriyle 0, 1 sabitleri ve işlev elde edilebilir.

Kanıt. Fonksiyonu ele alalım. Daha sonra

.

Aşağıdaki sunumda 1) ve 2) olarak belirtilen, müteakip değerlendirmelerin iki olası durumu vardır.

1). Birim setindeki fonksiyon 0 değerini alır:

.

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

var çünkü

Ve .

Kendinin dual olmayan bir fonksiyonunu ele alalım. Fonksiyonu zaten elde ettiğimiz için, kendinden ikili olmayan bir fonksiyona ilişkin lemmayı (lemma) kullanarak 2.7. ) adresinden bir sabit alabilirsiniz. İkinci sabit, fonksiyon 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 cebirindeki fonksiyon sistemlerinin tamlığı için bir kriter (Post teoremi).

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

gereklilik. F tam bir sistem olsun. F'nin belirtilen sınıflardan birinde yer aldığını varsayalım, onu K ile gösterelim, 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 ) fonksiyonlarının tamamının T 0 , T 1 , L , S , M beş kapalı sınıftan herhangi birinde yer almamasına izin verin. F'de aşağıdaki fonksiyonları alalım:

Daha sonra ana lemmayı temel alarak (lemma 2.10 ) 0'ı korumayan bir fonksiyondan, 1'i korumayan bir fonksiyona, kendi kendine ikili olmayan ve monoton olmayan fonksiyonlardan, 0, 1 sabitleri ve olumsuzluk fonksiyonu elde edilebilir:

.

Doğrusal olmayan fonksiyonlara ilişkin lemmayı temel alır (lemma 2.9 ) sabitlerden, olumsuzlamadan ve doğrusal olmayan bir fonksiyondan bağlacı elde edebiliriz:

.

Fonksiyon sistemi - mantık cebirinin herhangi bir fonksiyonunu mükemmel bir ayrık normal form biçiminde temsil etme olasılığı hakkındaki teoreme göre eksiksiz bir sistem (ayrılma, formdaki bağlaç ve olumsuzlama yoluyla ifade edilebileceğini unutmayın) ).

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

Örnekler.

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

X	sen	x|y

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

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

f(0,0) = 1, f(1,1) = 0, dolayısıyla x | yÏM.

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 olmaması ne anlama geliyor?
x | y.

Tamlık kriterine dayanarak f(x,y) = x | komple bir sistem oluşturur. ð

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

Gerçekten mi, .

Böylece sistemimizin fonksiyonları arasında şunu bulduk: 0'ı korumayan bir fonksiyon, 1'i korumayan bir fonksiyon, kendi kendine ikili olmayan, monoton olmayan ve doğrusal olmayan fonksiyonlar. Tamlık kriterine dayanarak, işlevler sisteminin komple bir sistem oluşturur. ð

Dolayısıyla tamlık kriterinin mantık cebirindeki fonksiyon sistemlerinin tamlığını belirlemek için yapıcı ve etkili bir yol sağladığına inanıyoruz.

Şimdi tamlık kriterinden üç sonuç çıkaralım.

Sonuç 1. Mantık cebirinin tüm fonksiyon kümesiyle (K¹P 2) çakışmayan mantık cebirinin herhangi bir kapalı K fonksiyonu sınıfı, oluşturulmuş kapalı sınıflardan en az birinde bulunur.

Tanım. Kapalı sınıf K denir ön dolu, eğer K eksikse ve herhangi bir fÏ K fonksiyonu için K È (f) sınıfı tamdır.

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

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

Sonucu kanıtlamak için, yalnızca bu sınıflardan hiçbirinin diğerinde bulunmadığını kontrol etmeniz gerekir; bu, örneğin farklı sınıflara ait aşağıdaki işlevler tablosuyla doğrulanır:

	T0	T 1	L	S	M
	+	-	+	-	+
	-	+	+	-	+
	-	-	+	+	-

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

Tamlık kriterinin kanıtından, beşten fazla fonksiyonun ayırt edilemeyeceği sonucu çıkar. Ana lemmanın kanıtından (Lemma 2.10 ) şu şekildedir ya kendi kendine ikili değildir ya da birliği korumaz ve monoton değildir. Bu nedenle dörtten fazla fonksiyona ihtiyaç duyulmaz.

Belirli bir fonksiyonun argümanı yerine bir fonksiyonu başka bir argümanla değiştirmekten oluşan fonksiyonların üst üste binmesi (veya dayatılması) kavramını tanıyalım. Örneğin, fonksiyonların süperpozisyonu bir fonksiyon verir ve fonksiyonlar da benzer şekilde elde edilir.

Genel olarak, bir fonksiyonun belirli bir etki alanında tanımlandığını ve fonksiyonun bir etki alanında tanımlandığını ve değerlerinin tümünün etki alanında yer aldığını varsayalım. O zaman z değişkeninin, y'ye kadar, kendisi bir a'dır. işlevi

Belirli bir değer verildiğinde, önce ona karşılık gelen y değerini bulurlar (bir işaretle karakterize edilen kurala göre) ve ardından karşılık gelen y değerini (kurala göre) ayarlarlar.

bir işaretle karakterize edilir, değerinin seçilen x'e karşılık geldiği kabul edilir. Bir fonksiyondan veya karmaşık bir fonksiyondan elde edilen fonksiyon, fonksiyonların üst üste binmesinin sonucudur

Fonksiyonun değerlerinin, fonksiyonun tanımlandığı Y bölgesinin sınırlarını aşmadığı varsayımı çok önemlidir: atlanırsa saçmalık ortaya çıkabilir. Örneğin, yalnızca x'in değerlerini dikkate alabileceğimizi varsayarak, aksi takdirde ifadenin bir anlam ifade etmeyeceğini varsayalım.

Bir fonksiyonun karmaşık olarak karakterizasyonunun, z'nin x'e fonksiyonel bağımlılığının doğasıyla değil, yalnızca bu bağımlılığın belirtilme şekliyle ilgili olduğunu burada vurgulamanın yararlı olduğunu düşünüyoruz. Örneğin, Sonra için y'yi girelim

Burada fonksiyonun karmaşık bir fonksiyon olarak belirtildiği ortaya çıktı.

Artık fonksiyonların üst üste binmesi kavramı tam olarak anlaşıldığına göre, analizde incelenen fonksiyon sınıflarının en basitlerini doğru bir şekilde karakterize edebiliriz: bunlar öncelikle yukarıda listelenen temel fonksiyonlar ve daha sonra onlardan elde edilenlerin hepsidir. Dört aritmetik işlem ve süperpozisyon kullanarak, art arda sonlu sayıda uygulandı. Bunların son halleriyle temel düzeyde ifade edildiği söylenir; bazen onlara temel de denir.

Daha sonra, daha karmaşık bir analitik cihaza (sonsuz seriler, integraller) hakim olduktan sonra, analizde de önemli bir rol oynayan ancak temel fonksiyonlar sınıfının ötesine geçen diğer fonksiyonlarla tanışacağız.

Konu: “İşlev: kavram, atama yöntemleri, temel özellikler. Ters fonksiyon. Fonksiyonların süperpozisyonu."

Ders epigrafı:

“Bir şeyi araştırın ve onun hakkında düşünmeyin

öğrenildi - kesinlikle işe yaramaz.

Bir şeyi araştırmadan düşünmek

ön düşünce konusu -

Konfüçyüs.

Dersin amacı, psikolojik ve pedagojik hedefleri:

1) Genel eğitim (normatif) hedefi: Öğrencilerle bir fonksiyonun tanımını ve özelliklerini gözden geçirin. Fonksiyonların süperpozisyonu kavramını tanıtmak.

2) Öğrencilerin matematiksel gelişiminin amaçları: Öğrencilerin zihinsel deneyimlerinin, mantıksal-tümdengelimli ve tümevarımlı, analitik ve sentetik geri dönüşümlü düşünme, cebirsel ve figüratif-grafik düşünme yetenekleri de dahil olmak üzere matematiksel zekalarının anlamlı bilişsel yapısının gelişimini sürdürmek için standart dışı eğitim ve matematik materyallerinin kullanılması anlamlı genelleme ve somutlaştırma, öğrencilerin üstbilişsel bir yeteneği olarak yansıtma ve bağımsızlığa; eğitimsel ve matematiksel zekanın psikolojik mekanizmaları olarak yazılı ve sözlü konuşma kültürünün gelişimini sürdürmek.

3) Eğitim görevleri: Matematiğe bilişsel ilgisi, sorumluluğu, görev duygusu, akademik bağımsızlığı, grupla, öğretmenle, sınıf arkadaşlarıyla işbirliği yapma iletişim becerisine sahip öğrencilerin kişisel eğitimini sürdürmek; Rekabetçi eğitimsel ve matematiksel faaliyetler için otogojik yetenek, yüksek ve en yüksek sonuçlar için çabalama (acmeic güdü).

Ders türü: yeni materyal öğrenmek; önde gelen matematiksel içerik kriterine göre - pratik bir ders; öğrenciler ve öğretmen arasındaki bilgi etkileşiminin türü kriterine göre - bir işbirliği dersi.

Ders ekipmanları:

1. Eğitim literatürü:

1) Kudryavtsev'in matematiksel analizi: Ders kitabı. üniversite ve üniversite öğrencileri için. 3 cilt olarak T. 3. – 2. baskı, revize edilmiştir. ve ek – M.: Daha yüksek. okul, 1989. – 352 s. : hasta.

2) Demidovich problemleri ve matematiksel analizde alıştırmalar. – 9. baskı. – M.: “Nauka” yayınevi, 1977.

2. Çizimler.

Ders ilerlemesi.

1. Dersin konusunun ve ana eğitim hedefinin duyurulması; Oturuma hazırlanırken öğrencilerin görev, sorumluluk ve bilişsel ilgi duygusunu teşvik etmek.

2.Sorulara dayalı materyalin tekrarı.

a) Bir fonksiyon tanımlayın.

Temel matematik kavramlarından biri fonksiyon kavramıdır. Fonksiyon kavramı, iki kümenin elemanları arasında ilişki kurmakla ilişkilidir.

Boş olmayan iki küme olsun ve verilsin. Her öğeyi yalnızca bir öğeyle eşleştiren f eşleşmesine denir işlev ve y = f(x) yazar. Ayrıca f fonksiyonunun da olduğunu söylüyorlar. görüntüler çok üstüne çok.

https://pandia.ru/text/79/018/images/image003_18.gif" width = "63" height = "27">.gif" width = "59" yükseklik = "26"> denir anlamlar kümesi f fonksiyonu ve E(f) ile gösterilir.

b) Sayısal fonksiyonlar. Fonksiyon grafiği. Fonksiyonları belirtme yöntemleri.

Fonksiyon verilsin.

Eğer ve kümelerinin elemanları gerçel sayılar ise f fonksiyonu çağrılır. sayısal fonksiyon . x değişkeni denir argüman veya bağımsız değişken ve y – işlev veya bağımlı değişken(x'ten). X ve y miktarlarına ilişkin olarak, bunların fonksiyonel bağımlılık.

Fonksiyon grafiği y = f(x), Oksi düzleminin tüm noktalarının kümesidir; bunların her biri için x, argümanın değeridir ve y, fonksiyonun karşılık gelen değeridir.

Y = f(x) fonksiyonunu belirtmek için, x'i bilerek y'nin karşılık gelen değerini bulmayı sağlayan bir kuralın belirtilmesi gerekir.

Bir işlevi belirtmenin en yaygın üç yolu şunlardır: analitik, tablosal ve grafiksel.

Analitik yöntem: Bir fonksiyon bir veya daha fazla formül veya denklem olarak belirtilir.

Örneğin:

Y = f(x) fonksiyonunun tanım alanı belirtilmemişse, karşılık gelen formülün anlamlı olduğu argümanın tüm değerlerinin kümesiyle çakıştığı varsayılır.

Bir fonksiyonu belirlemenin analitik yöntemi en gelişmiş yöntemdir çünkü y = f(x) fonksiyonunun tam olarak incelenmesini mümkün kılan matematiksel analiz yöntemlerini içerir.

Grafik yöntemi: Fonksiyonun grafiğini ayarlar.

Grafik görevinin avantajı açıklığı, dezavantajı ise yanlışlığıdır.

Tablo yöntemi: Bir işlev, bir dizi bağımsız değişken değeri ve karşılık gelen işlev değerlerinden oluşan bir tabloyla belirtilir. Örneğin, trigonometrik fonksiyonların iyi bilinen değer tabloları, logaritmik tablolar.

c) Fonksiyonun temel özellikleri.

1. D kümesinde tanımlanan y = f(x) fonksiyonuna denir eşit , eğer koşullar ve f(-x) = f(x) karşılanırsa; garip , eğer koşullar ve f(-x) = -f(x) karşılanırsa.

Çift fonksiyonun grafiği Oy eksenine göre simetriktir ve tek fonksiyon orijine göre simetriktir. Örneğin – çift fonksiyonlar; ve y = sinx, https://pandia.ru/text/79/018/images/image014_3.gif" width="73" height="29"> – genel formdaki işlevler, yani ne çift ne de tek.

2. y = f(x) fonksiyonu D kümesinde tanımlı olsun ve olsun. Argümanların herhangi bir değeri için aşağıdaki eşitsizlik aşağıdaki gibi olursa: sonra fonksiyon çağrılır artan sette; Eğer sonra fonksiyon çağrılır azalmayan https://pandia.ru/text/79/018/images/image021_1.gif" width = "117" height = "28 src = "> adresinde, ardından işlev çağrılır. azalan Açık ; - artmayan .

https://pandia.ru/text/79/018/images/image023_0.gif" width="13" height="13">D değeri (x) üzerinde artan, artmayan, azalan ve azalmayan işlevler +T)D ve f(x+T) = f(x) eşitliği geçerlidir.

T periyodundaki periyodik bir fonksiyonun grafiğini çizmek için, onu T uzunluğundaki herhangi bir parça üzerinde çizmek ve bunu tüm tanım alanı boyunca periyodik olarak sürdürmek yeterlidir.

Periyodik bir fonksiyonun temel özelliklerini not edelim.

1) Aynı T periyoduna sahip periyodik fonksiyonların cebirsel toplamı, T periyoduna sahip bir periyodik fonksiyondur.

2) Eğer f(x) fonksiyonu T periyoduna sahipse, f(ax) fonksiyonunun T/a periyodu vardır.

d) Ters fonksiyon.

D tanım tanım kümesi ve E..gif" width=48" height=22"> değer kümesiyle bir y = f(x) fonksiyonu verilse, o zaman bir x = z(y) fonksiyonu olsun E tanımının etki alanı ve D değerlerinin bir kümesi tanımlanır. Böyle bir z(y) fonksiyonu çağrılır tersi f(x) fonksiyonuna yazılır ve aşağıdaki biçimde yazılır: . y = f(x) ve x = z(y) fonksiyonlarının karşılıklı olarak ters olduğu söylenir. Y = f(x) fonksiyonunun tersi olan x = z(y) fonksiyonunu bulmak için, x için f(x) = y denklemini çözmek yeterlidir.

Örnekler:

1. y = 2x fonksiyonu için ters fonksiyon x = ½ y fonksiyonudur;

2. İşlev için ters fonksiyon fonksiyondur.

Ters fonksiyonun tanımından, y = f(x) fonksiyonunun ancak ve ancak f(x)'in D ve E kümeleri arasında bire-bir yazışmayı belirtmesi durumunda tersinin olduğu sonucu çıkar. kesinlikle monotonik bir fonksiyonun tersi vardır . Ayrıca, eğer bir fonksiyon artarsa ​​(azalırsa), o zaman ters fonksiyon da artar (azalır).

3. Yeni materyalin incelenmesi.

Karmaşık fonksiyon.

D kümesinde y = f(u) fonksiyonu ve kümede u = z(x) fonksiyonu tanımlansın ve karşılık gelen değer için . Daha sonra kümede u = f(z(x)) fonksiyonu tanımlanır ve buna denir. karmaşık fonksiyon x'ten (veya süperpozisyon belirtilen işlevler veya fonksiyondan fonksiyon ).

u = z(x) değişkeni çağrılır ara argüman karmaşık fonksiyon.

Örneğin, y = sin2x fonksiyonu, y = sinu ve u = 2x olmak üzere iki fonksiyonun süperpozisyonudur. Karmaşık bir fonksiyonun birden fazla ara argümanı olabilir.

4. Tahtada birkaç örnek çözmek.

5. Dersin sonucu.

1) pratik dersin teorik ve uygulamalı sonuçları; öğrencilerin zihinsel deneyim düzeylerinin farklılaştırılmış değerlendirmesi; konuya hakim olma düzeyleri, yeterlilikleri, sözlü ve yazılı matematiksel konuşmanın kalitesi; gösterilen yaratıcılık düzeyi; bağımsızlık ve yansıma düzeyi; inisiyatif düzeyi, bireysel matematiksel düşünme yöntemlerine bilişsel ilgi; işbirliği düzeyleri, entelektüel rekabet, yüksek düzeyde eğitim ve matematik etkinliği arzusu vb.;

2) Gerekçeli notların, ders puanlarının duyurulması.

Biraz set olsun k sonlu sayıda Boole fonksiyonundan oluşur. Bu kümedeki fonksiyonların süperpozisyonu, sonlu sayıda iki işlemin uygulanmasıyla elde edilen yeni fonksiyonlardır;

bir fonksiyona dahil olan herhangi bir değişkeni şuradan yeniden adlandırabilirsiniz: k;

herhangi bir değişken yerine kümeden bir işlev koyabilirsiniz k veya önceden oluşturulmuş bir süperpozisyon.

Süperpozisyona karmaşık fonksiyon da denir.

Örnek 7. 1. Bir işlev verilirse X|sen(Schaeffer vuruşu), o zaman süperpozisyonları özellikle aşağıdaki fonksiyonlar olacaktır. x|x,x|(x|y),x|(y|z) vesaire.

Kapatarak gelen işlevler kümesi k tüm süperpozisyonların kümesi denir. Fonksiyon sınıfı k isminde kapalı, eğer kapanışı kendisiyle örtüşüyorsa.

Fonksiyonlar kümesi denir tamamlamak, eğer kapanışı tüm mantıksal işlevlerle çakışıyorsa. Başka bir deyişle, tam bir küme, diğer tüm Boolean fonksiyonlarının ifade edilebildiği bu tür fonksiyonların bir kümesidir.

Yedekli olmayan tam bir işlevler kümesine temel denir("yedeksiz", setten bazı işlevlerin kaldırılması durumunda bu setin artık tamamlanmayacağı anlamına gelir).

Örnek 7.2. Bağlaç, ayrıklık ve olumsuzluk tam bir kümedir (Bölüm 5'te buna ikna olmuştuk), ancak bir temel değildir, çünkü bu küme gereksizdir, çünkü De Morgan'ın kuralları kullanılarak bir bağlaç veya ayrıklık kaldırılabilir. Herhangi bir fonksiyon Zhegalkin polinomu olarak temsil edilebilir (Bölüm 6). Fonksiyonların birleşimi, toplama modulo 2 ve sabitler 0 ve 1'in tam bir küme olduğu açıktır, ancak bu dört fonksiyon da bir temel değildir, çünkü 1+1=0 ve bu nedenle 0 sabiti tam kümenin dışında tutulabilir. set (polinomları oluşturmak için Zhegalkin sabiti 0 gereklidir çünkü “1+1” ifadesi bir Zhegalkin polinomu değildir).

Bazı setlerin eksiksizliğini kontrol etmenin yollarından birinin İLE başka bir tam kümenin fonksiyonlarının bu kümedeki işlevler aracılığıyla ifade edilip edilmediğini kontrol etmektir (bunu aşağıdaki işlevler aracılığıyla kontrol edebilirsiniz). İLE bağlaç ve olumsuzluk veya ayrıklık ve olumsuzluk ifade edilebilir.

Böyle bir fonksiyonun kendisinin bir temel oluşturduğu fonksiyonlar vardır (burada sadece bütünlüğün kontrol edilmesi yeterlidir; fazlalık olmadığı açıktır). Bu tür işlevlere Scheffer işlevleri denir. Bu isim Schaeffer vuruşunun temel olmasından kaynaklanmaktadır. Schaeffer asalının aşağıdaki doğruluk tablosuyla tanımlandığını hatırlayın:

Açık olduğundan, yani olumsuzlama Schaeffer darbesinin bir üst üste binmesidir ve o zaman ayrım Schaeffer vuruşunun kendisi bir temeldir. Benzer şekilde Peirce oku da bir Scheffer fonksiyonudur (öğrenciler bunu kendileri kontrol edebilirler). 3 veya daha fazla değişkenli fonksiyonlar için çok sayıda Sheffer fonksiyonu vardır (elbette diğer Boolean fonksiyonlarını çok sayıda değişkenli bir Sheffer fonksiyonu aracılığıyla ifade etmek zordur, bu nedenle teknolojide nadiren kullanılırlar).

Bir bilgi işlem cihazının çoğunlukla tam bir işlevler kümesine (çoğunlukla temellere) dayalı olduğunu unutmayın. Eğer cihaz birleşme, ayrılma ve olumsuzlama üzerine kuruluysa, o zaman DNF'yi en aza indirme sorunu bu cihazlar için önemlidir; Cihaz başka fonksiyonları temel alıyorsa bu fonksiyonlar aracılığıyla ifadeleri algoritmik olarak en aza indirebilmek faydalı olacaktır.

Şimdi belirli işlev kümelerinin tamlığını açıklığa kavuşturmaya geçelim. Bunu yapmak için en önemli 5 fonksiyon sınıfını listeliyoruz:

• T 0, sıfır kümesinde 0 değerini alan tüm mantıksal işlevlerin kümesidir ( T 0 fonksiyon sınıfıdır, muhafaza 0);
• T 1, birim kümesinde 1 değerini alan tüm mantıksal işlevlerin kümesidir ( T 1 bir fonksiyon sınıfıdır, muhafaza ünitesi) (işlevlerin sayısının N T 0 ve T 1 sınıflarına ait değişkenler 2 2n-1'e eşittir);
• L- Sınıf doğrusal fonksiyonlar, yani Zhegalkin polinomunun yalnızca birinci derece değişkenleri içerdiği fonksiyonlar;
• M- Sınıf monoton işlevler. Bu fonksiyonların sınıfını daha ayrıntılı olarak açıklayalım. 2 takım olsun N değişkenler: s1 = (x 1, x 2,..., x n)

s 1 = ( X 1 , X 2 , … , xn) ve s 2 = (sen 1 , sen 2, … , y p). Kümenin s olduğunu söyleyeceğiz 1, s 2 (s 1 £ s 2) kümesinden küçüktür, eğer hepsi x i £ y ben .Açıkçası, tüm setler değilNdeğişkenler birbiriyle karşılaştırılabilir (örneğin,n = 2 (0,1) ve (1,0) kümeleri birbiriyle karşılaştırılamaz). İşlev:Ndeğişkenler denirmonoton, daha küçük bir kümede ise daha az veya eşit değer alır. Elbette bu eşitsizlikler yalnızca karşılaştırılabilir kümeler üzerinde test edilmelidir. Karşılaştırılamaz kümelerin, bir kümede (0,1) ve diğerinde (1,0) tipinde bazı koordinatların karşılık gelen yerlerde bulunduğu kümeler olduğu açıktır (ayrık matematikte monoton fonksiyonlar tıpkı “monoton olarak artan fonksiyonlar gibidir) ”, “monoton olarak azalan” fonksiyonlar burada dikkate alınmaz).

Örnek. Aşağıdaki tabloda işlevler F 1 ,F 2 monoton işlevlerdir ve işlevler F 3 ,F 4 - HAYIR.

Değişkenlerin doğal sırası, eğer bir küme başka bir kümeden küçükse, o zaman mutlaka doğruluk tablosunda yer almasıyla sağlanır. daha yüksek“daha ​​büyük” set. Bu yüzden doğruluk tablosunda ise()üstte sıfırlar var,ve sonra olanlar,o zaman bu fonksiyon kesinlikle monotondur.Ancak ters çevirmeler mümkündür, yani bir, bazı sıfırlardan önce gelir, ancak işlev hala monotondur(bu durumda “üst” ve “alt” sıfıra karşılık gelen kümeler eşsiz; doğruluk tablosu tarafından verilen işlevin doğru olup olmadığı kontrol edilebilir değişkenler kümesinin doğal sırasına göre(00010101), monotondur);

Teorem .T fonksiyon sınıfları 0 ,T 1 ,L,M,Kapalı.

Bu ifade doğrudan bu sınıfların tanımından ve aynı zamanda kapalılığın tanımından gelmektedir.

Boole fonksiyonları teorisinde aşağıdaki Post teoremi çok önemlidir.

Post'un teoremi .Bazı K fonksiyon setlerinin tam olabilmesi için, T sınıflarının her birine ait olmayan fonksiyonları içermesi gerekli ve yeterlidir. 0 ,T 1 ,L,M,S.

Dikkat Ne gereklilik Bu ifadeler bariz Bu yüzden Nasıl Eğer hepsi bu işlevler itibaren işe alım İLE dahil V bir itibaren listelendi sınıflar, O Ve Tüm süperpozisyonlar, A Araç, Ve kısa devre işe alım dahil istemek V Bu Sınıf Ve Sınıf İLE Olumsuz olabilir olmak tam dolu.

Yeterlilik Bu ifadeler kanıtlanmış yeterli zor, Bu yüzden burada gösterilmiyor.

Bu teoremden, belirli bir fonksiyon kümesinin tamlığını belirlemenin oldukça basit bir yolu izlenir. Bu işlevlerin her biri için yukarıda listelenen sınıflara üyelik belirlenir. Sonuçlar sözde girilir Gönderi tablosu(Örneğimizde bu tablo 4 fonksiyon için derlenmiştir ve “+” işareti fonksiyonun ilgili sınıfa ait olduğunu, “-” işareti fonksiyonun içinde yer almadığını göstermektedir).

Post teoremine göre, fonksiyonlar kümesi ancak ve ancak Post tablosunun her sütununda en az bir eksi varsa tamamlanacaktır. Dolayısıyla yukarıdaki tablodan bu 4 fonksiyonun tam bir set oluşturduğu ancak bu fonksiyonların bir temel olmadığı anlaşılmaktadır. Bu işlevlerden 2 temel oluşturabilirsiniz: F 3 ,F 1 Ve F 3 ,F 2. Tam kümeler, bir miktar temel içeren herhangi bir kümedir.

Post'un tablosundan doğrudan temel fonksiyon sayısının 5'ten fazla olamayacağı sonucu çıkıyor. Aslında bu sayının 4'ten küçük veya ona eşit olduğunu kanıtlamak zor değil.

Bağımsız değişkenleri değiştirme ve yeniden adlandırma işlemleri kullanılarak f 1 , f 2 ,…f n işlevlerinden elde edilen bir f işlevine denir süperpozisyon işlevler.

Bir f fonksiyonunu diğer fonksiyonların üst üste binmesi olarak ifade eden herhangi bir formül, hesaplanması için bir yöntem belirtir, yani tüm alt formüllerinin değerleri hesaplanırsa formül hesaplanabilir. Bir alt formülün değeri, bilinen bir ikili değişken değerleri kümesinden hesaplanabilir.

Her formülü kullanarak mantıksal bir fonksiyonun tablosunu geri yükleyebilirsiniz, ancak bunun tersi mümkün değildir, çünkü Her mantıksal fonksiyon farklı temellerdeki çeşitli formüllerle temsil edilebilir.

Aynı mantıksal fonksiyon olan f i'yi temsil eden F i ve F j formüllerine denir eş değer . Yani eşdeğer formüller şöyledir:

1. f 2 (x 1 ; x 2)=(x 1 ×`x 2)=ù(`x 1 Úx 2)= ù(x 1 ®x 2);

2. f 6 (x 1 ; x 2)=(`x 1 ×x 2 Úx 1 ×`x 2)= ù(x 1 “x 2)=(x 1 Åx 2);

3. f 8 (x 1 ; x 2)=(`x 1 ×`x 2)= ù(x 1 Úx 2)=(x 1 ¯x 2);

4. f 14 (x 1 ;x 2)=(`x 1 Ú`x 2)= ù(x 1 ×x 2)=x 1 ½x 2 ;

5. f 9 (x 1 ;x 2)=((`x 1 ×`x 2)Ú(x 1 ×x 2))=(x 1 “x 2) ;

6. f 13 (x 1 ;x 2)= (`x 1 Üx 2)=(x 1 ®x 2).

Herhangi bir F formülü bir F i alt formülü içeriyorsa, F i'nin eşdeğer bir Fj ile değiştirilmesi herhangi bir Boole vektör kümesi için F formülünün değerini değiştirmez, ancak açıklamasının biçimini değiştirir. Yeni elde edilen F` formülü F formülüne eşdeğerdir.

Karmaşık cebirsel ifadeleri basitleştirmek için Boolean fonksiyonları gerçekleştirilir eşdeğer dönüşümler Boole cebiri yasalarını kullanarak ve oyuncu değişikliği kuralları Ve ikame ,

Boole cebiri formüllerini yazarken şunu unutmayın:

· sol parantez sayısı sağ parantez sayısına eşittir,

· iki bitişik mantıksal bağlaç yoktur, yani aralarında bir formül olmalıdır,

· iki bitişik formül yoktur, yani aralarında mantıksal bir bağlantı olmalıdır,

· mantıksal bağlaç “×” mantıksal bağlaç “Ú”dan daha güçlüdür,

· “ù” (F 1 ×F 2) veya (F 1 Ú F 2) formülünü ifade ediyorsa, öncelikle bu dönüşümler De Morgan yasasına göre yapılmalıdır: ù(F 1 ×F 2) = ` F 1 Ú` F 2 veya ù(F 1 ÚF 2)=`F 1 ×`F 2 ;

· operasyon " × ”, parantezleri atlamanıza izin veren “Ú”den daha güçlüdür.

Örnek: F=x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 formülünün eşdeğer dönüşümlerini gerçekleştirin.

· değişme kanununa göre:

F=x 3 ×x 1 ×x 2 ×`x 4 Üx 3 ×`x 1 Üx 3 ×`x 2 Üx 3 ×x 4 ;

· dağıtım yasasına göre:

F=x 3 ×x 1 ×x 2 ×`x 4 Üx 3 ×`x 1 Üx 3 ×(`x 2 Üx 4);

· dağıtım yasasına göre:

F=x 3 ×x 1 ×x 2 ×`x 4 Üx 3 ×(`x 1 Ü`x 2 Üx 4);

· dağıtım yasasına göre:

F=x 3 ×((x 1 ×x 2 ×`x 4)Ú(`x 1 Ü`x 2 Üx 4));

· De Morgan yasasına göre:

F=x 3 ×((x 1 ×x 2 ×`x 4)Úù(x 1 ×x 2 ×`x 4));

· çelişki yasasına göre:

Böylece x 1 ×x 2 ×x 3 ×`x 4 Ü`x 1 ×x 3 Ü`x 2 ×x 3 Üx 3 ×x 4 =x 3 .

Örnek: formül dönüşümlerini gerçekleştir

F=(x 1 ×`x 2 Ü`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ü`x 1 ×x 2 );

· De Morgan kanununa göre

F=(x 1 ×`x 2 Ü`x 1 ×x 2)×(`x 1 Ü`x 2)Ú(x 1 ×x 2)×(`x 1 Üx 2)×(x 1 Ü`x 2);

· dağıtım yasasına göre:

F=x 1 ×`x 2 Ü`x 1 ×x 2 Üx 1 ×x 2 ;

· Değişebilirlik ve dağılım yasalarına göre:

F= 'x 1 ×x 2 Üx 1 ×('x 2 Üx 2);

· çelişki yasasına göre:

F= 'x 1 ×x 2 Üx 1;

· Poretsky yasasına göre

Böylece (x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2 ) = (x 2 Üx 1).

Örnek: F=ù(`x 1 Úx 2)Ú((`x 1 Úx 3)×x 2) formülünü dönüştürün.

· De Morgan yasasına göre:

F= ù(`x 1 Üx 2)×ù((`x 1 Üx 3)×x 2);

· De Morgan yasasına göre:

F=x 1 ×`x 2 ×(ù(`x 1 × 3)Ú`x 2);

· De Morgan yasasına göre:

F=x 1 ×`x 2 ×(x 1 ×`x 3 Ü`x 2);

· dağıtım yasasına göre:

F=x 1 ×`x 2 ×`x 3 Üx 1 ×`x 2 ;

· emilim yasasına göre:

Böylece ù(`x 1 Üx 2)×((`x 1 Üx 3)×x 2)= x 1 ×`x 2 .

Örnek: Formülü dönüştürün:

F=ù(x 1 ®x 2)×(`x 3 Ú`x 4)Ú(x 1 ¯x 2)×ù(x 3 ×x 4).

1) formülü Boole cebirinin tabanına dönüştürün:

F=ù(`x 1 Üx 2)×(`x 3 Ü`x 4)Úù(x 1 Üx 2)× ù(x 3 ×x 4);

2) ikili değişkenlerin önündeki “`” işaretini atlayın:

F=(x 1 ×`x 2)×(`x 3 Ü`x 4)Ú(`x 1 ×`x 2)×(`x 3 Ü`x 4);

3) formülü dağıtım yasasına göre dönüştürün:

F=x 1 ×`x 2 ×`x 3 Üx 1 ×`x 2 ×`x 4 Ü`x 1 ×`x 2 ×`x 3 Ü`x 1 ×`x 2 ×`x 4 ;

4) dağıtım yasasına göre x 2'yi parantezlerin dışına çıkarın:

F=`x 2 ×(x 1 ×`x 3 × 1 ×`x 4 ×`x 1 ×`x 3 ×`x 1 ×`x 4);

5) dağıtım yasasına göre dönüşüm:

F=`x 2 ×(`x 3 ×(x 1 Ü`x 1)Ú`x 4 ×(x 1 Ü`x 1));

6) çelişki yasasını kullanın:

F=`x 2 ×(`x 3 Ü`x 4)

Boolean Fonksiyonlarının Özellikleri

Sık sık şu soru ortaya çıkıyor: Her Boolean fonksiyonu f 0, f 1,..f 15 formüllerinin üst üste bindirilmesiyle temsil edilebilir mi? Bu formüllerin üst üste bindirilmesini kullanarak herhangi bir Boole fonksiyonu oluşturma olasılığını belirlemek için, bunların özelliklerini ve işlevsel olarak eksiksiz bir sistem kullanma koşullarını belirlemek gerekir.

Kendinden ikili Boole işlevleri

kendi kendine ikili , eğer f(x 1 ;x 2 ;…x n)=`f(`x 1 ;`x 2 ;…`x n).

Örneğin, f 3 (x 1 ;x 2)=x 1 , f 5 (x 1 ;x 2)=x 2 , f 10 (x 1 ;x 2)=`x 2 ve f 12 (x 1) işlevleri ;x 2)=`x 1 kendi kendine ikilitir, çünkü argümanın değeri değiştiğinde değerleri de değişir.

Kendi kendine ikili Boole fonksiyonlarından süperpozisyon işlemleriyle elde edilen herhangi bir fonksiyonun kendisi de kendi kendine ikilitir. Bu nedenle, kendi kendine ikili Boole fonksiyonları kümesi, kendi kendine ikili olmayan fonksiyonların oluşumuna izin vermez.

Monoton Boole fonksiyonları

f(x 1 ; x 2 ;…x n) fonksiyonu çağrılır monoton , eğer her s 1i £s 2i Boolean vektörü (s 11 ; s 12 ;……;s 1n) ve (s 21 ;s 22 ;……;s 2n) için aşağıdaki koşul sağlanırsa: f(s 11 ;s 12 ;… ;s 1i ;…;s 1n)£f(s 21 ;s 22 ;…;s 2i ;…;s 2n).

Örneğin, f(x 1 ; x 2) fonksiyonları için monoton fonksiyonlar şunlardır:

eğer (0; 0) £ (0; 1), o zaman f(0; 0) £ f (0; 1),

eğer (0; 0)£(1; 0), o zaman f(0; 0)£f(1; 0),

eğer (0; 1) £ (1; 1), o zaman f(0; 1) £ f (1; 1),

eğer (1; 0) £ (1; 1), o zaman f(1; 0) £ f(1; 1) ise.

Aşağıdaki işlevler bu koşulları karşılar:

f 0 (x 1; x 2)=0; f 1 (x 1 ; x 2)=(x 1 ×x 2); f3(x1;x2)=x1; f 5 (x 1 ; x 2)=x 2 ; f 7 (x 1 ;x 2)=(x 1 Üx 2); f15(x1;x2)=1.

Monotonik Boolean fonksiyonlarından süperpozisyon işlemi kullanılarak elde edilen herhangi bir fonksiyonun kendisi monotondur. Bu nedenle monotonik fonksiyonlar kümesi monotonik olmayan fonksiyonların oluşmasına izin vermez.

Doğrusal Boole fonksiyonları

F 4 =(×; Å; 1) temeline dayanan Zhegalkin cebiri, herhangi bir mantıksal fonksiyonun, her terimi 0£i£ dahilindeki bir Boolean vektörünün I Boolean değişkenlerinin birleşimi olan bir polinomla temsil edilmesine izin verir. N:

P(x 1 ; x 2 ;…x n)=b 0 ×1 Å b i ×x i Å 1 £ j ¹ k £ n b j ×x j ×x k Å……Å b 2n-1 ×x 1 ×x 2 ×... ×xn.

Örneğin mantıksal işlevler için f 8 (x 1 ; x 2)

Zhegalkin polinomu şu şekildedir: P(x 1; x 2)=1Å x 1 Å x 2 Å x 1 ×x 2.

Zhegalkin cebirinin avantajları mantıksal formüllerin "aritmetikleştirilmesi" iken dezavantajları ise özellikle çok sayıda ikili değişkenin karmaşıklığıdır.

İkili değişkenlerin bağlaçlarını içermeyen Zhegalkin polinomları; P(x 1 ; x 2 ;…;x n)=b 0 ×1Åb 1 ×x 1 Å…Åb n ×x n denir doğrusal .

Örneğin, f9 (x 1; x 2) = 1Åx 1 Åx 2 veya f12 (x 1; x 2) = 1Åx 1.

Toplama işlemi modulo 2'nin temel özellikleri Tablo 1.18'de verilmiştir.

Mantıksal bir fonksiyon herhangi bir temelde bir tablo veya formülle belirtilmişse; Çeşitli Boolean değişken kümeleri için bir Boolean fonksiyonunun değerlerini biliyorsanız, o zaman hepsini hesaplayabilirsiniz.

Zhegalkin polinomunun katsayıları b i, bilinen tüm ikili değişken kümeleri için bir denklem sistemi derler.

Örnek: verilen bir Boole fonksiyonu f(x 1 ;x 2)=x 1 Üx 2. Bu fonksiyonun değerleri tüm Boolean değişken kümeleri için bilinir.

F(0;0)=0=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;

f(1;0)=1=b 0 ×1Å b 1 ×1Å b 2 ×0Å b 3 ×1×0;

f(1;1)=1=b 0 ×1Å b 1 ×1Å b 2 ×1Å b 3 ×1×1;

b 0 =0'ı nerede buluruz? b1 =1; b2 =1; b3 =1.

Bu nedenle, (x 1 Úx 2)=x 1 Åx 2 Åx 1 ×x 2, yani ayrılma doğrusal olmayan bir Boole fonksiyonudur.

Örnek: verilen bir Boole fonksiyonu f(x 1 ;x 2)=(x 1 ®x 2). Bu fonksiyonun değerleri aynı zamanda tüm ikili değişken kümeleri için de bilinir.

F(0;0)=1=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;

f(0;1)=1=b 0 ×1Å b 1 ×0 Å b 2 ×1Å b 3 ×0×1;

f(1;0)=0=b 0 ×1Åb 1 ×1Åb 2 ×0Åb 3 ×1×0;

f(1;1)=1=b 0 ×1Åb 1 ×1Åb 2 ×1Åb 3 ×1×1;

b 0 =1'i nerede buluruz; b1 =1; b2 =0; b3 =1.

Bu nedenle, (x 1 ®x 2)=1Å x 2 Å x 1 ×x 2.

Tablo 1.19, Tablo 1.15'teki Boole fonksiyonlarının ana temsilcileri için Zhegalkin polinomlarını göstermektedir.

Mantıksal bir fonksiyon için analitik bir ifade verilirse ve çeşitli ikili değişken kümeleri için değerleri bilinmiyorsa, Boole cebiri F 2 =(` ; ×)'nin birleşik tabanına dayalı bir Zhegalkin polinomu oluşturmak mümkündür. :

f(x 1 ; x 2)=(x 1 Üx 2) olsun.

O halde (x 1 Úx 2)=ù(`x 1 ×`x 2)=((x 1 Å 1)×(x 2 Å 1))Å 1=x 1 ×x 2 Å x 1 ×1Å x 2 × 1Å 1×1Å1=

(x 1 Åx 2 Åx 1 ×x 2).

f(x 1 ;x 2)=(x 1 ®x 2) olsun.

O zaman (x 1 ®x 2)=(`x 1 Úx 2)=ù(x 1 ×`x 2)=x 1 ×(x 2 Å 1)Å 1=x 1 ×x 2 Å x 1 ×1Å 1 = =(1Åx 1 Åx 1 ×x 2).

f(x 1 ;x 2)=(x 1 “x 2) olsun.

O halde (x 1 "x 2)=(`x 1 ×`x 2 Úx 1 ×x 2)=ù(ù(`x 1 ×`x 2)×ù(x 1 ×x 2))=((( x 1 Å1)×(x 2 Å1))Å1)× ×(x 1 ×x 2 Å)Å1=(x 1 ×x 2 Åx 1 Åx 2 Å1Å1)×(x 1 ×x 2 Å1)Å1=x 1 ×x 2 Åx 1 ×x 2 Åx 1 ×x 2 Åx 1 Å

x 1 ×x 2 Åx 2 Å1=(1Åx 1 Åx 2).

Doğrusal mantıksal işlevlerden süperpozisyon işlemi kullanılarak elde edilen herhangi bir işlevin kendisi doğrusaldır. Bu nedenle doğrusal fonksiyonlar kümesi, doğrusal olmayan fonksiyonların oluşumuna izin vermez.

1.5.6.4. “0”ı saklayan işlevler

f(x 1 ; x 2 ;...x n) fonksiyonuna, eğer ikili değişkenlerin (0; 0;...0) değer kümeleri için fonksiyon f(0; 0;…0)=0 .

Örneğin, f 0 (0; 0)=0, f 3 (0; 0)=0, f 7 (0; 0)=0, vb.

“0”ı koruyan fonksiyonlardan süperpozisyon işlemiyle elde edilen her fonksiyonun kendisi de “0”ı koruyan bir fonksiyondur. Dolayısıyla “0”ı koruyan fonksiyonlar kümesi, “0”ı korumayan fonksiyonların oluşmasına izin vermez.

1.5.6.5. “1”i saklayan işlevler

f(x 1 ; x 2 ;…x n) fonksiyonuna, ikili değişkenlerin (1; 1;…1) değer kümeleri için f(1;1;…1) değerini alması durumunda “1”i koruyarak denir. )=1.

Örneğin, f 1 (1; 1)=1, f3(1; 1)=1, f 5 (1; 1)=1, vb.

“1”i koruyan fonksiyonlardan süperpozisyon işlemi kullanılarak elde edilen her fonksiyonun kendisi de “1”i koruyandır. Dolayısıyla “1”i koruyan fonksiyonlar kümesi, “1”i korumayan fonksiyonların oluşmasına izin vermez.