Noskin Andrey Nikolayeviç,
BT öğretmeni
en yüksek yeterlilik kategorisi,
Askeri Bilimler Adayı, Doçent
GBOU Lisesi No. 1575, Moskova
Bilgisayar bilimi ve BİT alanında KIM Birleşik Devlet Sınavından 23. problemi çözmek için optimize edilmiş haritalama yöntemi
Birleşik Devlet Sınavı KIM'deki en zor görevlerden biri, belirtilen koşulu karşılayan mantıksal değişkenlerin farklı değer kümelerinin sayısını bulmanız gereken problem 23'tür.
Bu görev belki de en zor görev Bilişim ve BİT alanında KIM Birleşik Devlet Sınavı. Kural olarak, sınava girenlerin %5'inden fazlası bununla baş edemiyor (1).
Bu görevi tamamlayan öğrencilerin bu kadar küçük bir yüzdesi şu şekilde açıklanmaktadır:
- öğrenciler mantıksal işlemlerin işaretlerini karıştırabilir (unutabilir);
- hesaplamaların yapılması sürecindeki matematiksel hatalar;
- bir çözüm ararken akıl yürütmede hatalar;
- mantıksal ifadeleri basitleştirme sürecindeki hatalar;
- öğretmenler, tüm işi tamamladıktan sonra bu sorunu çözmeyi tavsiye ediyor, çünkü
hatalar çok büyüktür ve görevin “ağırlığı” yalnızca bir temel noktadır.
Ayrıca bazı öğretmenlerin kendileri de bu tür problemleri çözmekte zorluk çekmekte ve bu nedenle çocuklarla daha basit problemleri çözmeye çalışmaktadırlar.
Ayrıca durumu karmaşıklaştıran şey bu blokta çok sayıdaçeşitli görevler ve bir şablon çözümü seçmek imkansızdır.
Bu durumu düzeltmek için pedagojik topluluk, sorunları çözmek için ana iki yöntemi sonlandırıyor bu türden: bit zincirlerini (2) ve eşleme yöntemini (3) kullanan çözüm.
Bu yöntemleri iyileştirme (optimize etme) ihtiyacı, görevlerin hem yapı hem de değişken sayısı açısından sürekli değişmesinden kaynaklanmaktadır (yalnızca bir tür X değişkeni, iki tür X ve Y değişkeni, üç tür: X, Y , Z).
Sorunları çözmek için bu yöntemlere hakim olmanın zorluğu, K.Yu. Polyakov'un bu tür problemlere ilişkin 38 analizi bulunmaktadır (4). Bazı analizler bir soruna birden fazla türde çözüm sağlar.
Son zamanlarda Bilgisayar bilimlerinde KIM Birleşik Devlet Sınavında X ve Y değişkenleriyle ilgili iki tür sorun vardır.
Görüntüleme yöntemini optimize ettim ve öğrencilerimi geliştirilmiş yöntemi kullanmaya teşvik ettim.
Bu sonuç verir. Bu görevi başaran öğrencilerimin yüzdesi geçenlere göre %43'e kadar çıkıyor. Kural olarak, bilgisayar bilimleri alanında Birleşik Devlet Sınavına her yıl 11. sınıfların tamamından 25 ila 33 kişi girmektedir.
İki tür değişkenli problemler ortaya çıkmadan önce öğrenciler haritalama yöntemini çok başarılı bir şekilde kullanıyorlardı ancak mantıksal ifadede Y'nin ortaya çıkmasından sonra çocukların cevaplarının artık testlerle örtüşmediğini fark etmeye başladım. Yeni bir değişken türüyle eşleme tablosunun nasıl oluşturulacağı konusunda tam olarak net olmadıkları ortaya çıktı. Sonra kolaylık sağlamak için tüm ifadenin çocuklar için uygun olduğu gibi tek bir değişken türüne indirgenmesi gerektiği düşüncesi aklıma geldi.
Bu tekniği daha ayrıntılı olarak anlatacağım. Kolaylık sağlamak için, (4)'te verilen mantıksal ifadeler sistemi örneğini kullanarak bunu ele alacağım.
Kaç tane çeşitli çözümler bir sistemi var mantıksal denklemler
(x 1 ^ ve 1)=(¬x 2 V ¬
sen 2
)
(x 2 ^ ve 2)= (¬
X 3
V ¬
sen 3
)
...
(x 5 ^ y 5)
= (¬
X 6
V ¬
sen 6
)
Çözüm:
1. Mantıksal denklem sisteminin analizinden 6 değişkenin olduğunu görüyoruz. X ve 6 değişken sen. Bu değişkenlerden herhangi biri yalnızca iki değer (0 ve 1) alabildiğinden, bu değişkenleri aynı türden 12 değişkenle (örneğin Z) değiştiriyoruz.
2. Şimdi sistemi aynı türden yeni değişkenlerle yeniden yazalım. Görevin zorluğu değişkenleri değiştirirken dikkatli notlar almak olacaktır.
(z1 ^ z2)=
(¬z 3V¬
z 4
)
(z3 ^ z4)=
(¬
z 5
V¬
z 6
)
...
(z9 ^ z10)
=
(¬
z 11
V¬
z 12)
3. Tüm seçenekleri gözden geçireceğimiz bir tablo oluşturalım z 1 , z 2 , z 3 , z 4 , ilk mantıksal denklemde dört değişken olduğundan tablonun 16 satırı olacaktır (16=2 4); bu tür değerleri tablodan kaldır z 4 , ilk denklemin çözümü yoktur (üstü çizili sayılar).
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 |
4. Tabloyu analiz ederek değişken çiftlerini görüntülemek için bir kural oluşturuyoruz (örneğin, bir çift) Z 1 Z 2 =00 karşılık gelirçift Z 3 Z 4 = 11) .
5. Sistemin çözümü olan değişken çiftlerinin sayısını hesaplayarak tabloyu doldurun. 
6. Tüm sonuçları toplayın: 9 + 9 + 9 + 27 = 54
7. Cevap: 54.
Birleşik Devlet Sınavı KIM'deki 23. problemi çözmek için yukarıda optimize edilen metodoloji, öğrencilerin güvenlerini yeniden kazanmalarına ve bu tür problemleri başarıyla çözmelerine olanak tanıdı.
Edebiyat:
1.FIPI. Yönergeleröğretmenler için, BİLGİSAYAR BİLİMİ ve BİT alanında 2015 Birleşik Devlet Sınavı katılımcılarının yaptığı tipik hataların analizine dayanarak hazırlanmıştır. Erişim modu: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2.K.Yu. Polyakov, M.A. Roitberg.Mantıksal denklem sistemleri: bit dizileri kullanılarak çözüm. Bilişim Dergisi, Sayı: 12, 2014, s. 4-12. Yayınevi "1 Eylül", Moskova.3. E.A. Mironçik, Görüntüleme yöntemi. Dergi Bilişim, Sayı 10, 2013, s. 18-26. Yayınevi "1 Eylül", Moskova.
Mantıksal denklem sistemlerini çözme yöntemleri
Bir mantıksal denklem sistemini, örneğin bir doğruluk tablosu kullanarak (değişkenlerin sayısı çok fazla değilse) veya bir karar ağacı kullanarak, önce her denklemi basitleştirerek çözebilirsiniz.
1. Değişken değiştirme yöntemi.
Yeni değişkenlerin tanıtılması, denklem sistemini basitleştirmenize ve bilinmeyenlerin sayısını azaltmanıza olanak tanır.Yeni değişkenler birbirinden bağımsız olmalıdır. Basitleştirilmiş sistemi çözdükten sonra orijinal değişkenlere dönmeliyiz.
Belirli bir örnek kullanarak bu yöntemin uygulanmasını ele alalım.
Örnek.
((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0
Çözüm:
Yeni değişkenleri tanıtalım: A=(X1≡ X2); B=(X3 ≡ X4); C=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).
(Dikkat! x1, x2, ..., x10 değişkenlerinin her biri yeni değişkenlerden yalnızca birine dahil edilmelidir. değişkenler A, B, C, D, E, yani yeni değişkenler birbirinden bağımsızdır).
O zaman denklem sistemi şöyle görünecektir:
(A ∧ B) ∨ (¬A ∧ ¬B)=0
(B ∧ C) ∨ (¬B ∧ ¬C)=0
(C ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Ortaya çıkan sistem için bir karar ağacı oluşturalım:
A=0 denklemini düşünün, yani. (X1≡ X2)=0. 2 kökü vardır:
X1 ≡ X2 |
||
Aynı tablodan A=1 denkleminin de 2 kökü olduğu görülmektedir. Karar ağacındaki kök sayısını düzenleyelim:
Bir dalın çözüm sayısını bulmak için her seviyedeki çözüm sayısını çarpmanız gerekir. Sol dalda 2 tane var⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 çözüm; sağ dalda da 32 çözüm var. Onlar. tüm sistemin 32+32=64 çözümü var.
Cevap: 64.
2. Akıl yürütme yöntemi.
Mantıksal denklem sistemlerini çözmenin zorluğu, tam bir karar ağacının hantallığında yatmaktadır. Akıl yürütme yöntemi, ağacın tamamını oluşturmanıza değil, kaç dalının olacağını anlamanıza olanak tanır. Bu yönteme belirli örnekler kullanarak bakalım.
Örnek 1. Aşağıda listelenen tüm koşulları karşılayan x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 mantıksal değişkenlerinin kaç farklı değer kümesi vardır?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
x1\/y1 =1
Cevabın, bu eşitlik sisteminin karşıladığı x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 değişkenlerinin tüm farklı değer kümelerini listelemesi gerekmez. Cevap olarak bu tür setlerin sayısını belirtmeniz gerekiyor.
Çözüm :
Birinci ve ikinci denklemler üçüncü koşulla ilişkili bağımsız değişkenleri içerir. Birinci ve ikinci denklemler için bir çözüm ağacı oluşturalım.
Birinci ve ikinci denklemlerden oluşan bir sistemin çözüm ağacını temsil etmek için, birinci ağacın her dalının değişkenlere ilişkin bir ağaçla devam etmesi gerekir. en . Bu şekilde oluşturulan ağacın 36 dalı bulunacaktır. Bu dallardan bazıları sistemin üçüncü denklemini sağlamamaktadır. İlk ağaca ağacın dal sayısını işaretleyelim"e" üçüncü denklemi sağlayan:
Açıklayalım: Üçüncü koşulun sağlanması için x1=0 olduğunda y1=1 olması gerekir, yani ağacın tüm dalları"X" , burada x1=0 ağaçtan yalnızca bir dal ile devam ettirilebilir"e" . Ve ağacın yalnızca bir dalı için"X" (sağda) ağacın tüm dalları uyuyor"y". Böylece tüm sistemin tam ağacı 11 dal içerir. Her dal orijinal denklem sisteminin bir çözümünü temsil eder. Bu, tüm sistemin 11 çözümü olduğu anlamına gelir.
Cevap: 11.
Örnek 2. Denklem sisteminin kaç farklı çözümü vardır?
(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1
(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.
………………
(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1
(X1 ≡ X10) = 0
burada x1, x2, …, x10 mantıksal değişkenlerdir? Cevabın, bu eşitliğin geçerli olduğu tüm farklı değişken değer kümelerini listelemesi gerekmez. Cevap olarak bu tür setlerin sayısını belirtmeniz gerekiyor.
Çözüm : Sistemi basitleştirelim. İlk denklemin bir kısmı için bir doğruluk tablosu oluşturalım:
X1 ∧ X10 | ¬X1 ∧ ¬X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10) |
||
Son sütuna dikkat edin, eylemin sonucuyla eşleşiyor X1 ≡ X10.
X1 ≡ X10 |
Sadeleştirmeden sonra şunu elde ederiz:
(X1 ≡ X2) ∨ (X1 ≡ X10)=1
(X2 ≡ X3) ∨ (X2 ≡ X10)=1
(X3 ≡ X4) ∨ (X3 ≡ X10)=1
……
(X9 ≡ X10) ∨ (X9 ≡ X10)=1
(X1 ≡ X10) = 0
Son denklemi düşünün:(X1 ≡ X10) = 0, yani. x1, x10 ile çakışmamalıdır. İlk denklemin 1'e eşit olması için eşitliğin doğru olması gerekir(X1 ≡ X2)=1, yani. x1, x2 ile eşleşmelidir.
İlk denklem için bir çözüm ağacı oluşturalım:
İkinci denklemi düşünün: x10=1 ve x2=0 için parantez1'e eşit olmalıdır (yani x2, x3 ile çakışır); x10=0 ve x2=1 braketi için(X2 ≡ X10)=0, yani braket (X2 ≡ X3) 1'e eşit olmalıdır (yani x2, x3 ile çakışır):
Bu şekilde akıl yürüterek tüm denklemler için bir karar ağacı oluşturuyoruz:
Dolayısıyla denklem sisteminin yalnızca 2 çözümü vardır.
Cevap: 2.
Örnek 3.
Aşağıda listelenen tüm koşulları karşılayan x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 mantıksal değişkenlerinin kaç farklı değer kümesi vardır?
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1
(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1
(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1
(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1
Çözüm:
1. denklem için bir çözüm ağacı oluşturalım:
İkinci denklemi düşünün:
- x1=0 olduğunda : ikinci ve üçüncü parantez 0'a eşit olacaktır; ilk parantezin 1'e eşit olması için, y1=1, z1=1 (yani bu durumda - 1 çözüm)
- x1=1 olduğunda : ilk parantez 0'a eşit olacaktır; ikinci veya üçüncü parantez 1'e eşit olmalıdır; y1=0 ve z1=1 olduğunda ikinci parantez 1'e eşit olacaktır; y1=1 ve z1=0 olduğunda üçüncü parantez 1'e eşit olacaktır (yani bu durumda - 2 çözüm).
Geri kalan denklemler için de benzer şekilde. Her ağaç düğümü için elde edilen çözüm sayısını not edelim:
Her dalın çözüm sayısını bulmak için, elde edilen sayıları her dal için ayrı ayrı (soldan sağa) çarpın.
1 dal: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 çözüm
Dal 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 çözümler
3. dal: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 çözümler
4. dal: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 çözüm
5. dal: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 çözümler
Ortaya çıkan sayıları toplayalım: Toplamda 31 çözüm var.
Cevap: 31.
3. Kök sayısında doğal artış
Bazı sistemlerde bir sonraki denklemin kök sayısı bir önceki denklemin kök sayısına bağlıdır.
Örnek 1. Aşağıda listelenen tüm koşulları karşılayan x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 mantıksal değişkenlerinin kaç farklı değer kümesi vardır?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Basitleştirelim ilk denklem:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Daha sonra sistem şu şekli alacaktır:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
Vesaire.
Her bir sonraki denklemin bir öncekinden 2 kökü daha vardır.
4 denklemin 12 kökü vardır;
Denklem 5'in 14 kökü vardır
Denklem 8'in 20 kökü vardır.
Cevap: 20 kök.
Bazen kök sayısı Fibonacci kanununa göre artar.
Bir mantıksal denklem sistemini çözmek yaratıcı bir yaklaşım gerektirir.
Değişkenleri değiştirerek mantıksal denklem sistemlerini çözme
Değişkenlerin ikame yöntemi, bazı değişkenlerin denklemlere yalnızca belirli bir ifade biçiminde dahil edilmesi ve başka hiçbir şey içermemesi durumunda kullanılır. Daha sonra bu ifade yeni bir değişkenle gösterilebilir.
Örnek 1.
Aşağıda listelenen tüm koşulları karşılayan x1, x2, x3, x4, x5, x6, x7, x8 mantıksal değişkenlerinin kaç farklı değer kümesi vardır?
(x1 → x2) → (x3→ x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Cevabın, bu eşitlik sisteminin karşıladığı x1, x2, x3, x4, x5, x6, x7, x8 değişkenlerinin tüm farklı değer kümelerini listelemesi gerekmez. Cevap olarak bu tür setlerin sayısını belirtmeniz gerekiyor.
Çözüm:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
O zaman sistemi tek bir denklem şeklinde yazabiliriz:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Her işlenen 1 değerini aldığında bağlaç 1'dir (doğru). sonuçların her biri doğru olmalıdır ve bu, (1 → 0) dışındaki tüm değerler için doğrudur. Onlar. y1, y2, y3, y4 değişkenlerinin değerleri tablosunda sıfırın solunda olmamalıdır:
Onlar. koşullar 5 set y1-y4 için karşılanmıştır.
Çünkü y1 = x1 → x2 ise, y1 = 0 değerine tek bir x1, x2: (1, 0) kümesinde ulaşılır ve y1 = 1 değeri – üç x1, x2: (0,0) , (0 kümesinde) elde edilir ,1), (1.1). Aynı şekilde y2, y3, y4 için de.
y1 değişkenine ait her küme (x1,x2), y2 değişkenine ait her kümeyle (x3,x4) birleştirildiği için, x değişkenlerinin küme sayıları çarpılır:
|
x1…x8 başına set sayısı |
||||
Küme sayısını toplayalım: 1 + 3 + 9 + 27 + 81 = 121.
Cevap: 121
Örnek 2.
Aşağıda listelenen tüm koşulları karşılayan x1, x2, ... x9, y1, y2, ... y9 mantıksal değişkenlerinin kaç farklı değer kümesi vardır?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
Cevap olarak gerek yok Verilen eşitlik sisteminin karşılandığı x1, x2, ... x9, y1, y2, ... y9 değişkenlerinin tüm farklı değer kümelerini listeleyin. Cevap olarak bu tür setlerin sayısını belirtmeniz gerekiyor.
Çözüm:
Değişkenlerde değişiklik yapalım:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Sistem tek bir denklem olarak yazılabilir:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Eşdeğerlik yalnızca her iki işlenenin eşit olması durumunda doğrudur. Bu denklemin iki çözüm kümesi vardır:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Çünkü zi = (xi ≡ yi), bu durumda zi = 0 değeri iki (xi,yi) kümesine karşılık gelir: (0,1) ve (1,0) ve zi = 1 değeri iki kümeye (xi,yi) karşılık gelir ): (0 ,0) ve (1,1).
O halde ilk z1, z2,…, z9 kümesi 2 9 kümeye (x1,y1), (x2,y2),…, (x9,y9) karşılık gelir.
Aynı sayı ikinci küme z1, z2,…, z9'a karşılık gelir. O halde toplam 2 9 +2 9 = 1024 küme vardır.
Cevap: 1024
Özyinelemenin görsel olarak belirlenmesi yöntemini kullanarak mantıksal denklem sistemlerini çözme.
Bu yöntem, denklem sisteminin oldukça basit olması ve değişkenleri eklerken küme sayısını artırma sırasının açık olması durumunda kullanılır.
Örnek 3.
Denklem sisteminin kaç farklı çözümü vardır?
¬x9 ∨ x10 = 1,
burada x1, x2, … x10 mantıksal değişkenlerdir?
Cevabın, bu eşitlik sisteminin karşılandığı tüm farklı x1, x2, ... x10 değer kümelerini listelemesi gerekmez. Cevap olarak bu tür setlerin sayısını belirtmeniz gerekiyor.
Çözüm:
İlk denklemi çözelim. Bir ayrıklığın işlenenlerinden en az biri 1'e eşitse 1'e eşittir. çözümler kümelerdir:
x1=0 için, x2'nin iki değeri (0 ve 1) vardır ve x1=1 için yalnızca bir x2 (1) değeri vardır, öyle ki (x1,x2) kümesi denklemin bir çözümüdür . Toplamda 3 set bulunmaktadır.
x3 değişkenini toplayalım ve ikinci denklemi ele alalım. İlkine benzer, yani x2=0 için x3'ün iki değeri (0 ve 1) vardır ve x2=1 için yalnızca bir x3 (1) değeri vardır, öyle ki (x2) kümesi ,x3) denklemin bir çözümüdür. Toplamda 4 set bulunmaktadır.
Başka bir değişken eklerken bir kümenin eklendiğini görmek kolaydır. Onlar. (i+1) değişken kümelerinin sayısı için yinelemeli formül:
N i +1 = N i + 1. O zaman on değişken için 11 küme elde ederiz.
Cevap: 11
Çeşitli türlerdeki mantıksal denklem sistemlerini çözme
Örnek 4.
Aşağıda listelenen tüm koşulları karşılayan x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 mantıksal değişkenlerinin kaç farklı değer kümesi vardır? ?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
Cevap olarak gerek yok Bu eşitlik sisteminin karşılandığı x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 değişkenlerinin tüm farklı değer kümelerini listeleyin.
Cevap olarak bu tür setlerin sayısını belirtmeniz gerekiyor.
Çözüm:
Sistemin üç denkleminin farklı bağımsız değişken kümelerinde aynı olduğuna dikkat edin.
İlk denkleme bakalım. Bir bağlaç yalnızca tüm işlenenleri doğruysa (1'e eşit) doğrudur (1'e eşit). Anlamı (1,0) hariç tüm demetlerde 1'dir. Bu, ilk denklemin çözümünün aşağıdaki x1, x2, x3, x4 kümeleri olacağı anlamına gelir; burada 1, 0'ın solunda görünmez (5 küme):
Benzer şekilde, ikinci ve üçüncü denklemlerin çözümleri kesinlikle aynı y1,…,y4 ve z1,…, z4 kümeleri olacaktır.
Şimdi sistemin dördüncü denklemini analiz edelim: x 4 ∧ y 4 ∧ z 4 = 0. Çözüm, değişkenlerden en az birinin 0'a eşit olduğu tüm x4, y4, z4 kümeleri olacaktır.
Onlar. x4 = 0 için tüm olası kümeler (y4, z4) uygundur ve x4 = 1 için, içinde en az bir sıfırın bulunduğu (y4, z4) kümeleri uygundur: (0, 0), (0,1) ), (1, 0).
|
Set sayısı |
||||
Toplam set sayısı 25 + 4*9 = 25 + 36 = 61'dir.
Cevap: 61
Tekrarlayan formüller oluşturarak mantıksal denklem sistemlerini çözme
Tekrarlayan formüller oluşturma yöntemi, küme sayısını artırma sırasının belli olmadığı ve hacimler nedeniyle bir ağaç oluşturmanın imkansız olduğu karmaşık sistemleri çözerken kullanılır.
Örnek 5.
Aşağıda listelenen tüm koşulları karşılayan x1, x2, ... x7, y1, y2, ... y7 mantıksal değişkenlerinin kaç farklı değer kümesi vardır?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Cevapta, bu eşitlik sisteminin karşılandığı x1, x2, ..., x7, y1, y2, ..., y7 değişkenlerinin tüm farklı değer kümelerinin listelenmesine gerek yoktur. Cevap olarak bu tür setlerin sayısını belirtmeniz gerekiyor.
Çözüm:
Sistemin ilk altı denkleminin aynı olduğuna ve yalnızca değişkenler kümesinde farklı olduğuna dikkat edin. İlk denkleme bakalım. Çözümü aşağıdaki değişken kümeleri olacaktır:
Şunu belirtelim:
(x1,y1)'den A 1'e kadar değişkenlerdeki tuple sayısı (0,0),
(x1,y1)'den B 1'e kadar değişkenlerdeki tuple sayısı (0,1),
(x1,y1)'den C 1'e kadar değişkenlerdeki tuple sayısı (1,0),
(x1,y1)'den D 1'e kadar olan değişkenlerdeki (1,1) dizilerinin sayısı.
(x2,y2) ile A 2 arasındaki değişkenlerdeki tuple sayısı (0,0),
(x2,y2)'den B 2'ye kadar değişkenlerdeki tuple sayısı (0,1),
(x2,y2)'den C2'ye kadar değişkenlerdeki tuple sayısı (1,0),
(x2,y2)'den D 2'ye kadar değişkenlerdeki (1,1) demetlerinin sayısı.
Karar ağacından şunu görüyoruz
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
(x2,y2) değişkenleri üzerindeki (0,0) kümesinin, (x1,y1) değişkenleri üzerindeki (0,1), (1,0) ve (1,1) kümelerinden elde edildiğine dikkat edin. Onlar. A 2 =B 1 +C 1 +D 1.
(x2,y2) değişkenleri üzerindeki (0,1) kümesi, (x1,y1) değişkenleri üzerindeki (0,1), (1,0) ve (1,1) kümelerinden elde edilir. Onlar. B 2 =B 1 +C 1 +D 1.
Benzer şekilde tartışarak C 2 =B 1 +C 1 +D 1 olduğunu görüyoruz. D2 = D1.
Böylece tekrarlayan formüller elde ederiz:
A i+1 = B ben + C ben + D ben
B ben+1 = B ben + C ben + D ben
C ben+1 = B ben + C ben + D ben
D ben+1 = A ben +B ben + C ben + D ben
Hadi bir masa yapalım
| Setler | Tanım. | Formül |
Set sayısı |
||||||
| ben=1 | ben=2 | ben=3 | ben=4 | ben=5 | i=6 | i=7 | |||
| (0,0) | bir ben | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B ben | B i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C ben | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D ben | D ben+1 =D ben | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Son denklem (x7 ∨ y7) = 1, x7=0 ve y7=0 dışındaki tüm kümeler tarafından sağlanır. Tablomuzda bu tür setlerin sayısı A 7'dir.
O halde toplam küme sayısı B 7 + C 7 + D 7 = 127+127+1 = 255
Cevap: 255
Denklemlerin kullanımı hayatımızda oldukça yaygındır. Birçok hesaplamada, yapı yapımında ve hatta sporda kullanılırlar. İnsanoğlu eski zamanlarda denklemleri kullandı ve o zamandan beri kullanımları daha da arttı. Matematikte önermeler mantığıyla ilgili bazı problemler vardır. Bu tür bir denklemi çözmek için belirli miktarda bilgiye sahip olmanız gerekir: önerme mantığı yasaları bilgisi, 1 veya 2 değişkenli mantıksal fonksiyonların doğruluk tabloları bilgisi, mantıksal ifadeleri dönüştürme yöntemleri. Ayrıca mantıksal işlemlerin şu özelliklerini de bilmeniz gerekir: bağlaç, ayırma, ters çevirme, ima ve eşdeğerlik.
\değişkenler - \'nin herhangi bir mantıksal işlevi bir doğruluk tablosuyla belirtilebilir.
Birkaç mantıksal denklemi çözelim:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Çözüme \[X1\] ile başlayalım ve bu değişkenin hangi değerleri alabileceğini belirleyelim: 0 ve 1. Daha sonra yukarıdaki değerlerin her birini dikkate alıp \[X2.\]'nin ne olabileceğini göreceğiz.
Tablodan da görülebileceği gibi mantıksal denklemimizin 11 çözümü vardır.
Bir mantık denklemini çevrimiçi olarak nerede çözebilirim?
Denklemi https://sitemizden çözebilirsiniz. Özgür çevrimiçi çözücü Herhangi bir karmaşıklıktaki çevrimiçi denklemleri birkaç saniye içinde çözmenize olanak tanır. Tek yapmanız gereken, verilerinizi çözücüye girmenizdir. Ayrıca web sitemizde video talimatlarını izleyebilir ve denklemin nasıl çözüleceğini öğrenebilirsiniz. Hala sorularınız varsa, bunları http://vk.com/pocketteacher VKontakte grubumuzda sorabilirsiniz. Grubumuza katılın, size yardımcı olmaktan her zaman mutluluk duyarız.
Ders konusu: Mantık Denklemlerini Çözme
Eğitici – mantıksal denklemleri çözme yöntemlerini incelemek, mantıksal denklemleri çözme becerilerini geliştirmek ve doğruluk tablosunu kullanarak mantıksal bir ifade oluşturmak;Gelişimsel - gelişme için koşullar yaratmak bilişsel ilgiÖğrenciler hafıza, dikkat gelişimini teşvik eder, mantıksal düşünme;
eğitici : Başkalarının fikirlerini dinleme yeteneğini geliştirmek, başarma isteğini ve azmini beslemek Nihai sonuçlar.
Ders türü: birleşik ders
Teçhizat: bilgisayar, multimedya projektörü, sunum 6.
Dersler sırasında
Temel bilgilerin tekrarı ve güncellenmesi. Sınav Ev ödevi(10 dakika)
Önceki derslerde mantıksal cebirin temel yasalarıyla tanıştık ve bu yasaları mantıksal ifadeleri basitleştirmek için kullanmayı öğrendik.
Mantıksal ifadeleri basitleştirmeye ilişkin ödevimize bir göz atalım:
1. Aşağıdaki kelimelerden hangisi mantıksal koşulu karşılıyor:
(ilk harf ünsüz → ikinci harf ünsüz)٨ (son harf sesli harfi → sondan bir önceki sesli harf)? Bu tür birkaç kelime varsa, bunlardan en küçüğünü belirtin.
1) ANNA 2) MARIA 3) OLEG 4) STEPAN
Aşağıdaki gösterimi tanıtalım:
A – ilk harf ünsüz
B – ikinci harf ünsüz
S – son harf sesli harfi
D – sondan bir önceki sesli harf
Bir ifade yapalım:
Bir tablo yapalım:
2. Hangi mantıksal ifadenin ifadeye eşdeğer olduğunu belirtin
Orijinal ifadenin ve önerilen seçeneklerin kaydını basitleştirelim:
3. F ifadesinin doğruluk tablosunun bir parçası verildiğinde:
Hangi ifade F ile eşleşir?
Argümanların belirtilen değerleri için bu ifadelerin değerlerini belirleyelim:
Dersin konusuna giriş, yeni materyallerin sunumu (30 dakika)
Mantığın temellerini incelemeye devam ediyoruz ve bugünkü dersimizin konusu “Mantıksal Denklemleri Çözmek”. Bu konuyu inceledikten sonra mantıksal denklemleri çözmenin temel yollarını öğrenecek, mantıksal cebir dilini kullanarak bu denklemleri çözme becerisini ve doğruluk tablosu kullanarak mantıksal bir ifade oluşturma becerisini kazanacaksınız.
1. Bir mantık denklemini çözün
(¬K M) → (¬L M N) =0
Cevabınızı dört karakterden oluşan bir dize olarak yazın: K, L, M ve N değişkenlerinin değerleri (bu sırayla). Yani örneğin 1101 satırı K=1, L=1, M=0, N=1 gerçeğine karşılık gelir.
Çözüm:
İfadeyi dönüştürelim(¬K M) → (¬L M N)
Her iki terim de yanlış olduğunda bir ifade yanlıştır. M =0, N =0, L =1 ise ikinci terim 0'a eşittir. İlk terimde K = 0, çünkü M = 0 ve 
.
Cevap: 0100
2. Denklemin kaç çözümü var (cevabınızda yalnızca sayıyı belirtin)?
Çözüm: ifadeyi dönüştürün
(A +B )*(C +D )=1
A +B =1 ve C +D =1
Yöntem 2: doğruluk tablosunun hazırlanması
3 yollu: bir SDNF'nin inşası - bir fonksiyon için mükemmel bir ayırıcı normal form - tam düzenli temel bağlaçların ayrıklığı.Bağlaçların ayrıklığını elde etmek için orijinal ifadeyi dönüştürelim, parantezleri açalım:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Tam bağlaçlara (tüm argümanların çarpımı) bağlaçları ekleyelim, parantezleri açalım:
Aynı bağlaçları dikkate alalım:
Sonuç olarak 9 bağlaç içeren bir SDNF elde ediyoruz. Bu nedenle, bu fonksiyonun doğruluk tablosu, 2 4 =16 değişken değer kümesinden oluşan 9 satırda 1 değerine sahiptir.
3. Denklemin kaç çözümü var (cevabınızda yalnızca sayıyı belirtin)?
İfadeyi basitleştirelim:
,
3 yollu: SDNF'nin inşası
Aynı bağlaçları dikkate alalım:
Sonuç olarak 5 bağlaç içeren bir SDNF elde ediyoruz. Bu nedenle, bu fonksiyonun doğruluk tablosu, 2 4 = 16 değişken değer kümesinden oluşan 5 satırda 1 değerine sahiptir.
Doğruluk tablosu kullanarak mantıksal bir ifade oluşturmak:
doğruluk tablosunun 1 içeren her satırı için argümanların bir çarpımını oluşturuyoruz ve 0'a eşit değişkenler olumsuzlama ile çarpıma dahil ediliyor ve 1'e eşit değişkenler olumsuzlama olmadan dahil ediliyor. İstenilen F ifadesi, elde edilen ürünlerin toplamından oluşacaktır. Daha sonra mümkünse bu ifadenin basitleştirilmesi gerekir.
Örnek: Bir ifadenin doğruluk tablosu verilmiştir. Mantıksal bir ifade oluşturun.
Çözüm:3. Ödev (5 dakika)
Denklemi çözün:
Denklemin kaç çözümü var (cevabınızda yalnızca sayıyı belirtin)?
Verilen bir doğruluk tablosunu kullanarak mantıksal bir ifade oluşturun ve
basitleştirin.
