Tashkent informaciya texnologiyalari universiteti

7.2.Takrar o’rin almastırıw
N ta elementden ibarat A to‘plamdi m ta qism to‘plamlar jiyindisi ko‘riniste neshe tùrli usilda jayiw mumkin degen soraw qo‘yamiz.

Sonday bo‘liw kerak N(B₁)=k₁ , N(B₂)=k₂ , ... , N(B_m)=k_m bo‘lip, k₁, k₂ ,..., k_m berilgen sanlar ushin

Shartler orinlanadii. to‘plamlar umumiy elementlarge iye emes.
A to‘plamniń k₁ elementli B₁ to‘plam ostisini usilda tanlaw mumkin, n-k₁ qalģan elementlarden k₂ elementli B₂ to‘plam ostisini usilda tanlaw mumkin hàm hokazo. Turli xil to‘plamlarni tanlash usullari ko‘bettiriw qaģidasina ko‘re


9 Tema: Oy-pikirler algebrasina kirisiw. Oy-pikir túsinigi. Ápiwayı hám quramalı oy-pikir. Tiykarǵı logikalıq oy-pikirler
Reje:
1. Bul algebrasi.
2. Oy-pikir túsinigi. Oy-pikirler ústinde ekilik ámeller. Ápiwayı hám quramalı oy-pikirler.
Bul algebrasi.
Ekenin aytıw kerek, logikalıq ámeller oy-pikirler algebrasi kózqarastan shınlıq kesteleri menen tolıq xarakterlenedi. Egerde funskiyaning keste formada beriliwin eske alsaq, ol waqıtta oy-pikirler algebrasida da funksiya túsinigin anıqlawımız múmkin.


Ta’rif. x₁, x₂, … ,x_n mulohazalar algerbasiniń x₁, x₂, … ,x_nargumentli f(x₁, x₂, … ,x_n) funksiyasi dep nol hàm bir qabul funksiyaga aytiladi va uning x₁, x₂, … ,x_nargumentlari ham nol hàm bir bòlek qabul qilinadi.

Argument	Bul funksiyalar
x	0	x		1
1	0	1	0	1
0	0	0	1	1

Bàrshe eki ozgeriwshi funksiyalarn sanab o’temiz.

x	Y	0					x							1			1
1	1	0	1	0	0	0	1	0	0	1	1	0	1	0	1	1	1
1	0	0	0	1	0	0	1	1	0	0	0	1	1	1	0	1	1
0	1	0	0	0	1	0	0	1	1	0	1	0	1	1	1	0	1
0	0	0	0	0	0	1	0	0	1	1	0	1	0	1	1	1	1

10 Tema: Bul funktsiyalari. Bul ayniyatlari. Formullardiń teń kushlileri.
Reje:

1. 
   Bul funktsiyalari
   
2. 
   Bul ayniyatlari. Formullardiń teń kushlileri.
   

Tariyp. Eger ózgeriwshiniń sonday a₁, a­₂,...,a_i-1,a_i,...,a_n bahalar kompleksi ámeldegi bolıp, f(a₁, a­₂,...,a_i-1,1,a_i,...,a_n)=f(a₁, a­₂,...,a_i-1,0,a_i,...,a_n) munasabet orinlsnsa, ol waqitta x_i o’zgaruvchiga f(x₁,x₂,...,x_n) funksiyaning ahamiyetsiz qàlbeki) o’zgeriwshisi, eger f(a₁, a­₂,...,a_i-1,1,a_i,...,a_n)≠f(a₁, a­₂,...,a_i-1,0,a_i,...,a_n) munasabet orinlansa,ol waqitda x_i o’zgeriwshisine f(x₁,x₂,...,x_n) funksiyaniń ahimiyetli (qàlbeki emes) o’zgeriwshisi deb ataladi.

Misali.

1	1	0	1	1
1	0	0	1	0
0	1	1	1	0
0	0	1	1	0

Kórinip turıptı, olda, f1 funksiya ushın x ózgeriwshi áhmiyetli ózgeriwshi, y bolsa áhmiyetsiz, f2 ushın eki ózgeriwshi de áhmiyetsiz, f3 ushın eki ózgeriwshi de áhmiyetli.
Formulalar. Formulalardıń teńkuchliligi
Tariyp 1. Tuwrı dúzilgen quramalı oy-pikirge formula dep ataladı.
Formulalar grek háripleri menen belgilenedi: α, β, γ, δ, ….
Eger A₁, A₂, …, A_n mulohazalar α formulada qatnashadigan barcha mulohazalar bo’lsa, α= α(A₁, A₂, …, A_n ) kabi belgilanadi.
Misali 1. a) α(A)= ⌐A;

2. 
   β(A, B, C)=A&B→C;
   
3. 
   γ (A, B)=A&B \/ ⌐A&⌐B)
   

bunda A, B, C, … Ápiwayı oy-pikirler argument yamasa logikalıq ózgeriwshiler, α, β, γ, … formulalar bolsa funktsiya dep da júritiledi. Formulanıń tuwrı dúzilgen bolıwında qawıslardıń ornı júdá zárúrli. Logikada da tap algebra hám arifmetikadagi sıyaqlı qawıslar ámeller rejimin belgilep beredi.
Formulalarda qawıslardı kemeytiw maqsetinde ámellerdiń atqarılıw tártibi tómendegishe kelisip alınǵan. Eger formulada qawıslar bolmasa,
birinshi biykar ámeli - ⌐,
ekinshi kon'yunktsiya - &,
úshinshi bolıp diz'yunktsiya - \/,
odan keyin implikatsiya - → hám
aqırında ekvivalentlik - ~ ámeli atqarıladı.
11 Tema: Predikatlar. Ulıwmalıq hám ámelde barlıq kvantorlari.
REJE
1. Predikatlar.
2. Ulıwmalıq hám ámelde barlıq kvantorlari.
Predikatlar.
Bizge natural sanlar kompleksi N berilgen bolsın.
x element N jıynaqtıń qálegen elementi bolsın. Ol halda tómendegi gápler
A (x) ={x sanı 7 ge bólinedi};
B (x) ={x>10};
C (x) ={x túpkilikli son};
D (x) ={ (x-5) 2<10}
bildirgi gápler bolǵanlıǵı ushın oy-pikir esaplanadı, lekin olardıń ras yamasa ótirikligi haqqında hesh nárse ayta almaymız.
Tariyp. Ras yamasa ótirikligi belgisiz bolǵan oy-pikirler anıqmas oy-pikirler yamasa predikatlar dep ataladı.
Joqarıdaǵı mısallarda x dıń ornına túrli bahalardı qóysaq, túrlishe oy-pikirler payda boladı, yaǵnıy
A (5) ={7 sanı 7 ge bólinedi} =1;
A (13) ={10 sanı 7 ge bólinedi}=0
9. 2. Ulıwmalıq hám ámelde barlıq kvantorlari.
Natural sanlar kompleksinde berilgen qandayda bir P (x) predikatni alaylıq.
Eger P (x) predikat bolsa, ol halda (x) P (x) - jazıw N jıynaqta qálegen x ushın P (x) oy-pikir orınlı degen mánisti ańlatadı. Bul oy-pikir ras boladı, qashanda x dıń qálegen ma`nisinde P (x) orınlı bolsa. Egerde x dıń birgine ma`nisinde orınlı bolmasa, P (x) oy-pikir ótirik boladı.  - belgi ulıwmalıq kvantori dep ataladı.
Mısal 1. A (x) ={4 x+1 sanı túpkilikli son} oy-pikirdi qálegen x ushın tekserip kóremiz:
A(1)={4¹+1=5 soni tub san}=1;
A(2)={4²+1=17 soni tub san}=1;
A(3)={4³+1=257 soni tub san} =1;
A(4)={4⁴+1=65537 soni tub san} =1;
A(5)={4⁵+1=4294967296+1= 4294967297 soni tub san} =0,
Demek,, x=5 de bul mulohaza jalģan bo’ladi.
.

12 Tema: Logika nızamları. Logika funksiyaları ushın raslıq kestesin dúziw
REJE
1. Logika nızamları.
2. Logika funksiyaları ushın raslıq kestein dúziw.
Logika nızamları.
Bizge qandayda bir α, β, γ logikalıq formulalar berilgen bolsın. Bul formulalar ushın tómendegi logika nızamları mudamı orınlı boladı :
1. Ekilengen biykarlaw etiw nızamı : α≡α
2. Kon'yunktsiya hám diz'yunktsiya ámelleriniń idempotentlik nızamı :
α&α≡α,
α\/α≡α

1. 
   Kon'yunktsiya hám diz'yunktsiya ámelleriniń kommutativlik nızamı :
   

α&β≡β&α,
α\/β= β\/α

2. 
   Kon`yunktsiya hàm diz`yunktsiya amelleriniń assotsiativlik nizami:
   

α&(β&γ)≡(α&β)&γ,
α\/(β\/γ)=(α\/ β)\/γ) 
3. Kon'yunktsiya hám diz'yunktsiya ámelleriniń bir-birine salıstırǵanda distributivlik nızamı : α&(β\/γ)≡(α&β)\/(α&γ) ,
α\/(β&γ)≡(α\/β)&(α\/γ)
4.Jutiliw nizamlari α&(α\/β)≡α,
α\/(α&β)≡α
5.De Morgan nizamlari ¬ (α\/β)≡ ⌐ α & ⌐β

A	B	¬ (α\/β)	⌐ α & ⌐β
0	0	1	1
0	1	0	0
1	0	0	0
1	1	0	0

¬ (α&β)≡ ⌐ α\/ ⌐β

A	B	¬ (α&β)	⌐ α\/ ⌐β
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0