Mantıksal denklem sistemlerini çözme yöntemleri. Mantıksal denklem sistemlerini çözme yöntemleri

Noskin Andrey Nikolayeviç,
bilgisayar bilimi öğ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 bilgisayar bilimi ve BİT alanında KIM Birleşik Devlet Sınavının en zor görevidir. 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.
Durumu daha da karmaşık hale getiren şey, bu blokta çok sayıda farklı görevin bulunması ve herhangi bir şablon çözümü seçmenin imkansız olmasıdır.
Bu durumu düzeltmek için pedagojik topluluk bu tür problemleri çözmek için iki ana yöntemi tamamlıyor: bit zincirleri kullanarak çözme (2) ve haritalama yöntemi (3).
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 yaşandı.
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şarabilen öğ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.
Bir mantıksal denklem sisteminin kaç farklı çözümü vardır?

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

(z1 ^ z2)= (¬z 3V¬ z 4 )
(z3 ^ z4)= (¬ z 5 V¬ z 6 )
...
(z9 ^ z10) = (¬ z 11 V¬ z 12)

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 yöntem, öğrencilerin güvenlerini yeniden kazanmalarına ve bu tür problemleri başarıyla çözmelerine olanak tanıdı.

Edebiyat:

1.FIPI. BİLGİ BİLİMİ ve BİT alanında 2015 Birleşik Devlet Sınavına katılanların tipik hatalarının analizine dayanarak hazırlanan, öğretmenler için metodolojik öneriler. Erişim modu: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

Mantıksal denklem sistemlerini çözmenin çeşitli yolları vardır. Bu, tek bir denkleme indirgeme, doğruluk tablosu oluşturma ve ayrıştırmadır.

Görev: Bir mantıksal denklem sistemini çözün:

düşünelim bir denkleme indirgeme yöntemi . Bu yöntem, mantıksal denklemlerin, sağ tarafları doğruluk değerine (yani 1) eşit olacak şekilde dönüştürülmesini içerir. Bunu yapmak için mantıksal olumsuzlama işlemini kullanın. Daha sonra, denklemler karmaşık mantıksal işlemler içeriyorsa, bunları temel olanlarla değiştiririz: "VE", "VEYA", "DEĞİL". Bir sonraki adım, "VE" mantıksal işlemini kullanarak denklemleri sisteme eşdeğer bir şekilde birleştirmektir. Bundan sonra ortaya çıkan denklemi mantıksal cebir yasalarına göre dönüştürüp sisteme özel bir çözüm elde etmelisiniz.

Çözüm 1:İlk denklemin her iki tarafına ters çevirme uygulayın:

“VEYA” ve “DEĞİL” temel işlemleri aracılığıyla bunun ne anlama geldiğini hayal edelim:

Denklemlerin sol tarafları 1'e eşit olduğundan, bunları "VE" işlemini kullanarak orijinal sisteme eşdeğer bir denklemde birleştirebiliriz:

İlk parantezi De Morgan yasasına göre açıyoruz ve elde edilen sonucu dönüştürüyoruz:

Ortaya çıkan denklemin tek bir çözümü vardır: A =0, B=0 ve C=1.

Bir sonraki yöntem doğruluk tabloları oluşturma . Mantıksal niceliklerin yalnızca iki değeri olduğundan, tüm seçenekleri gözden geçirebilir ve aralarında belirli bir denklem sisteminin karşılandığı seçenekleri bulabilirsiniz. Yani sistemin tüm denklemleri için ortak bir doğruluk tablosu oluşturuyoruz ve gerekli değerleri içeren bir doğru buluyoruz.

Çözüm 2: Sistem için bir doğruluk tablosu oluşturalım:

Görev koşullarının karşılandığı satır kalın harflerle vurgulanmıştır. Yani A=0, B=0 ve C=1.

Yol ayrışma . Buradaki fikir, değişkenlerden birinin değerini sabitlemek (bunu 0 veya 1'e eşitlemek) ve böylece denklemleri basitleştirmektir. Daha sonra ikinci değişkenin değerini düzeltebilirsiniz, vb.

Çözüm 3: A = 0 olsun, o zaman:

İlk denklemden B = 0 ve ikinciden - C = 1 elde ederiz. Sistemin çözümü: A = 0, B = 0 ve C = 1.

Bilgisayar bilimlerindeki Birleşik Devlet Sınavında, bir mantıksal denklem sisteminin çözüm sayısını belirlemek, çözümleri kendileri bulmadan sıklıkla gereklidir; bunun için de belirli yöntemler vardır; Bir mantıksal denklem sisteminin çözüm sayısını bulmanın ana yoludeğişkenleri değiştirmek. Öncelikle denklemlerin her birini mantıksal cebir yasalarına göre mümkün olduğunca basitleştirmeniz, ardından denklemlerin karmaşık kısımlarını yeni değişkenlerle değiştirip yeni sistemin çözüm sayısını belirlemeniz gerekiyor. Daha sonra değiştirme işlemine geri dönün ve bunun için çözüm sayısını belirleyin.

Görev:(A →B) + (C →D) = 1 denkleminin kaç çözümü var? A, B, C, D mantıksal değişkenlerdir.

Çözüm: Yeni değişkenleri tanıtalım: X = A →B ve Y = C →D. Yeni değişkenler dikkate alınarak denklem şu şekilde yazılacaktır: X + Y = 1.

Ayrışma üç durumda doğrudur: (0;1), (1;0) ve (1;1), X ve Y çıkarımlardır, yani üç durumda doğrudur ve birinde yanlıştır. Bu nedenle (0;1) durumu üç olası parametre kombinasyonuna karşılık gelecektir. Durum (1;1) – orijinal denklemin dokuz olası parametre kombinasyonuna karşılık gelecektir. Bu, bu denklemin toplam olası çözümlerinin 3+9=15 olduğu anlamına gelir.

Bir mantıksal denklem sisteminin çözüm sayısını belirlemenin bir sonraki yolu şudur: ikili ağaç. Bir örnek kullanarak bu yönteme bakalım.

Görev: Mantıksal denklem sisteminin kaç farklı çözümü vardır:

Verilen denklem sistemi aşağıdaki denkleme eşdeğerdir:

(X 1 → X 2 )*(X 2 → X 3 )*…*(xm -1 → xm) = 1.

Diyelim ki X 1 – doğrudur, o zaman ilk denklemden bunu elde ederiz X 2 ikincisinden itibaren de doğru - X 3 =1 ve bu şekilde devam edene kadar xm= 1. Bu, m birimlik (1; 1; …; 1) kümesinin sistemin bir çözümü olduğu anlamına gelir. Şimdi izin ver X 1 =0 ise elimizdeki ilk denklemden X 2 =0 veya X 2 =1.

Ne zaman X 2 doğruysa, geri kalan değişkenlerin de doğru olduğunu, yani (0; 1; ...; 1) kümesinin sistemin bir çözümü olduğunu elde ederiz. Şu tarihte: X 2 =0 bunu anladık X 3 =0 veya X 3 = vb. Son değişkene devam edersek, denklemin çözümlerinin aşağıdaki değişken kümeleri olduğunu görüyoruz (m +1 çözüm, her çözüm değişkenlerin m değerini içerir):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Bu yaklaşım, bir ikili ağaç oluşturularak iyi bir şekilde gösterilmiştir. Olası çözümlerin sayısı, oluşturulan ağacın farklı dallarının sayısıdır. m+1'e eşit olduğunu görmek kolaydır.

Muhakemede zorluk yaşanması durumunda araştırma ve inşaatbir çözüm arayabileceğiniz çözümlerin sayısı kullanarak doğruluk tabloları, bir veya iki denklem için.

Denklem sistemini şu şekilde yeniden yazalım:

Ve bir denklem için ayrı ayrı doğruluk tablosu oluşturalım:

İki denklem için doğruluk tablosu oluşturalım:

Bilgisayar bilimleri sınavının A ve B bölümlerindeki bazı problemler nasıl çözülür?

Ders #3. Mantık. Mantık fonksiyonları. Denklemleri çözme

Çok sayıda Birleşik Devlet Sınavı problemi önerme mantığına ayrılmıştır. Çoğunu çözmek için önermeler mantığının temel yasalarını bilmek, bir ve iki değişkenli mantıksal fonksiyonların doğruluk tablolarını bilmek yeterlidir. Önermeler mantığının temel yasalarını vereceğim.

1. Ayrıklık ve birleşimin değişmezliği:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Ayrışma ve birleşmeye ilişkin dağıtım yasası:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Olumsuzlamanın olumsuzlanması:
   ¬(¬a) ≡ a
4. Tutarlılık:
   a ^ ¬а ≡ yanlış
5. Özel üçüncü:
   a ˅ ¬а ≡ doğru
6. De Morgan'ın yasaları:
   ¬(a˅b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Basitleştirme:
   a ˄ a ≡ a
   bir ˅ bir ≡ bir
   a ˄ doğru ≡ a
   a ˄ yanlış ≡ yanlış
8. Emilim:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. İmanın değiştirilmesi
   a → b ≡ ¬a˅b
10. Kimliğin değiştirilmesi
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Mantıksal fonksiyonların gösterimi

N değişkenli herhangi bir mantıksal fonksiyon - F(x 1, x 2, ... x n) bir doğruluk tablosuyla belirtilebilir. Böyle bir tablo, her biri için bu kümedeki bir fonksiyonun değerinin belirtildiği 2n değişken kümesi içerir. Bu yöntem, değişken sayısı nispeten az olduğunda iyidir. Zaten n > 5 için temsil zayıf bir şekilde görünür hale gelir.

Başka bir yol, bilinen oldukça basit fonksiyonları kullanarak fonksiyonu bir formülle tanımlamaktır. Herhangi bir mantıksal fonksiyon yalnızca f i fonksiyonlarını içeren bir formülle ifade edilebiliyorsa, bir fonksiyonlar sistemi (f 1, f 2, ... f k) tam olarak adlandırılır.

Fonksiyonlar sistemi (¬, ˄, ˅) tamamlandı. Yasa 9 ve 10, ima ve kimliğin olumsuzlama, bağlaç ve ayrım yoluyla nasıl ifade edildiğini gösteren örneklerdir.

Aslında, iki işlevden oluşan bir sistem de -olumsuzlama ve bağlaç ya da olumsuzlama ve ayrıklık- tamdır. De Morgan yasalarından, kişinin bir bağlacı olumsuzlama ve ayrıklık yoluyla ifade etmesine ve buna göre bir ayrıklığı olumsuzlama ve bağlaç yoluyla ifade etmesine izin veren fikirler izlenir:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

Paradoksal olarak tek bir fonksiyondan oluşan bir sistem tamamlanmış durumdadır. İki ikili fonksiyon vardır: içi boş bir sistemi temsil eden, Peirce oku ve Schaeffer vuruşu adı verilen anti-bağlantı ve antidisjunction.

Programlama dillerinin temel işlevleri genellikle özdeşlik, olumsuzluk, bağlaç ve ayrılmayı içerir. Birleşik Devlet Sınavı problemlerinde, bu işlevlerin yanı sıra, sıklıkla imalara rastlanır.

Mantıksal işlevlerle ilgili birkaç basit probleme bakalım.

Sorun 15:

Doğruluk tablosunun bir kısmı verilmiştir. Verilen üç fonksiyondan hangisi bu parçaya karşılık gelir?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

İşlev numarası 3.

Sorunu çözmek için temel fonksiyonların doğruluk tablolarını bilmeniz ve işlemlerin önceliklerini hatırlamanız gerekir. Bağlacın (mantıksal çarpma) daha yüksek önceliğe sahip olduğunu ve ayırmadan (mantıksal toplama) daha önce yürütüldüğünü hatırlatmama izin verin. Hesaplamalar sırasında üçüncü kümede 1 ve 2 numaralı fonksiyonların 1 değerine sahip olduğu ve bu nedenle parçaya karşılık gelmediği kolaylıkla fark edilebilir.

Sorun 16:

Verilen sayılardan hangisi koşulu karşılıyor:

(en anlamlı rakamdan başlayan rakamlar azalan sıradadır) → (sayı - çift) ˄ (düşük rakam - çift) ˄ (yüksek rakam - tek)

Bu tür birkaç sayı varsa, en büyüğünü belirtin.

1. 13579
2. 97531
3. 24678
4. 15386

Bu koşul 4 numara ile karşılanmaktadır.

İlk iki sayı, en düşük rakamın tek olması nedeniyle koşulu sağlamamaktadır. Bağlacın koşullarından biri yanlışsa, koşulların birleşimi yanlıştır. Üçüncü sayı için en büyük rakam şartı sağlanmamıştır. Dördüncü sayı için sayının alt ve üst basamaklarında aranan koşullar karşılanmıştır. Bağlacın ilk terimi de doğrudur, çünkü öncül yanlışsa çıkarım da doğrudur, ki buradaki durum da budur.

Sorun 17: İki tanık şu ifadeyi verdi:

Birinci tanık: Eğer A suçluysa, o zaman B daha da suçlu, C ise masumdur.

İkinci tanık: İkisi suçlu. Geriye kalanlardan biri de kesinlikle suçlu ve suçlu ama tam olarak kim olduğunu söyleyemem.

İfadelerden A, B ve C'nin suçluluğuna ilişkin ne gibi sonuçlar çıkarılabilir?

Cevap: İfadelerden A ve B'nin suçlu, C'nin ise masum olduğu sonucu çıkıyor.

Çözüm: Elbette sağduyuya dayalı olarak cevap verilebilir. Ancak bunun kesin ve resmi olarak nasıl yapılabileceğine bakalım.

Yapılacak ilk şey ifadeleri resmileştirmektir. Karşılık gelen şüphelinin suçlu olması durumunda her biri doğru (1) değerine sahip olan A, B ve C olmak üzere üç mantıksal değişkeni tanıtalım. Daha sonra ilk tanığın ifadesi şu formülle verilir:

bir → (B ˄ ¬C)

İkinci tanığın ifadesi şu formülle verilir:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Her iki tanığın ifadesinin doğru olduğu varsayılır ve karşılık gelen formüllerin birleşimini temsil eder.

Bu okumalar için bir doğruluk tablosu oluşturalım:

Özet kanıt yalnızca bir durumda doğrudur ve açık bir cevaba yol açar: A ve B suçludur ve C masumdur.

Bu tablonun analizinden ikinci tanığın ifadesinin daha bilgilendirici olduğu sonucu çıkmaktadır. İfadesinin gerçekliğine göre, yalnızca iki olası seçenek ortaya çıkıyor: A ve B suçlu, C masum veya A ve C suçlu ve B masum. İlk tanığın ifadesi daha az bilgilendiricidir - onun ifadesine karşılık gelen 5 farklı seçenek vardır. Her iki tanığın ifadeleri birlikte şüphelilerin suçluluğu konusunda net bir cevap veriyor.

Mantıksal denklemler ve denklem sistemleri

F(x 1, x 2, …x n) n değişkenli mantıksal bir fonksiyon olsun. Mantıksal denklem şuna benzer:

F(x 1, x 2, …x n) = C,

C sabiti 1 veya 0 değerine sahiptir.

Mantıksal bir denklemin 0'dan 2'ye kadar farklı çözümü olabilir. Eğer C 1'e eşitse, çözümler F fonksiyonunun doğru (1) değerini aldığı doğruluk tablosundaki tüm değişken kümeleridir. Geriye kalan kümeler C'nin sıfıra eşit olduğu denklemin çözümleridir. Her zaman yalnızca formun denklemlerini düşünebilirsiniz:

F(x 1 , x 2 , …x n) = 1

Aslında denklem şu şekilde verilsin:

F(x 1, x 2, …x n) = 0

Bu durumda eşdeğer denkleme gidebiliriz:

¬F(x 1 , x 2 , …x n) = 1

k mantıksal denklemden oluşan bir sistem düşünün:

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

F k (x 1 , x 2 , …x n) = 1

Bir sistemin çözümü, sistemin tüm denklemlerinin karşılandığı bir dizi değişkendir. Mantıksal fonksiyonlar açısından, bir mantıksal denklemler sisteminin çözümünü elde etmek için, orijinal F fonksiyonlarının birleşimini temsil eden, mantıksal F fonksiyonunun doğru olduğu bir küme bulunmalıdır:

Ф = F 1 ˄ F 2 ˄ … F k

Değişken sayısı küçükse, örneğin 5'ten azsa, F fonksiyonu için sistemin kaç çözüme sahip olduğunu ve çözüm sağlayan kümelerin neler olduğunu söylememize olanak tanıyan bir doğruluk tablosu oluşturmak zor değildir.

Mantıksal denklem sistemine çözüm bulmaya yönelik bazı USE problemlerinde değişken sayısı 10'a ulaşır. O zaman doğruluk tablosu oluşturmak neredeyse imkansız bir iş haline gelir. Sorunu çözmek farklı bir yaklaşım gerektirir. Rastgele bir denklem sistemi için, bu tür problemlerin çözümüne olanak sağlayan, numaralandırma dışında genel bir yöntem yoktur.

Sınavda önerilen problemlerde çözüm genellikle denklem sisteminin özelliklerinin dikkate alınmasına dayanır. Tekrar ediyorum, bir dizi değişken için tüm seçenekleri denemek dışında sorunu çözmenin genel bir yolu yok. Çözüm sistemin özelliklerine göre oluşturulmalıdır. Bilinen mantık yasalarını kullanarak bir denklem sisteminin ön basitleştirmesini gerçekleştirmek genellikle faydalıdır. Bu sorunu çözmek için başka bir yararlı teknik aşağıdaki gibidir. Tüm kümelerle ilgilenmiyoruz, yalnızca F fonksiyonunun 1 değerine sahip olduğu kümelerle ilgileniyoruz. Tam bir doğruluk tablosu oluşturmak yerine, onun analogunu (ikili karar ağacı) oluşturacağız. Bu ağacın her dalı bir çözüme karşılık gelir ve F fonksiyonunun 1 değerine sahip olduğu bir kümeyi belirtir. Karar ağacındaki dalların sayısı, denklem sisteminin çözümlerinin sayısıyla örtüşür.

İkili karar ağacının ne olduğunu ve nasıl oluşturulduğunu çeşitli problemlerden örnekler kullanarak açıklayacağım.

Sorun 18

İki denklem sistemini 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?

Cevap: Sistemin 36 farklı çözümü vardır.

Çözüm: Denklem sistemi iki denklem içerir. 5 değişkene (x 1, x 2, ...x 5) bağlı olarak ilk denklemin çözüm sayısını bulalım. İlk denklem 5 denklemden oluşan bir sistem olarak düşünülebilir. Gösterildiği gibi, denklem sistemi aslında mantıksal fonksiyonların birleşimini temsil eder. Bunun tersi de doğrudur: koşulların birleşimi bir denklem sistemi olarak düşünülebilir.

İlk denklem olarak kabul edilebilecek bağlacın ilk terimi olan (x1→ x2) çıkarımı için bir karar ağacı oluşturalım. Bu ağacın grafiksel temsili şöyle görünür:

Ağaç, denklemdeki değişken sayısına göre iki seviyeden oluşur. Birinci düzey, birinci değişken X1'i tanımlar. Bu seviyenin iki dalı, bu değişkenin olası değerlerini yansıtır - 1 ve 0. İkinci seviyede, ağacın dalları yalnızca denklemin doğru olduğu X2 değişkeninin olası değerlerini yansıtır. Denklem bir çıkarımı belirttiğinden, X1'in 1 değerine sahip olduğu bir dal, X2'nin bu dalda 1 değerine sahip olmasını gerektirir. X1'in 0 değerine sahip olduğu bir dal, X2 değerlerine sahip iki dal üretir. 0 ve 1'e eşittir Oluşturulan ağaç, X 1 → X 2 sonucunun 1 değerini aldığı üç çözümü tanımlar. Her dalda, denklemin çözümünü veren karşılık gelen bir değişken değerler kümesi yazılır.

Bu kümeler şunlardır: ((1, 1), (0, 1), (0, 0))

Aşağıdaki denklemi, yani X 2 → X 3 sonucunu ekleyerek karar ağacını oluşturmaya devam edelim. Denklem sistemimizin özelliği, sistemin her yeni denkleminin önceki denklemden bir değişken kullanması ve yeni bir değişken eklemesidir. X 2 değişkeni ağaçta zaten değerlere sahip olduğundan, X 2 değişkeninin 1 değerine sahip olduğu tüm dallarda X 3 değişkeni de 1 değerine sahip olacaktır. Bu tür dallar için ağacın yapısı bir sonraki seviyeye devam eder ancak yeni dallar görünmez. X 2 değişkeninin 0 değerine sahip olduğu tek dal, X 3 değişkeninin 0 ve 1 değerlerini alacağı iki dala ayrılacaktır. Böylece, özellikleri göz önüne alındığında, yeni bir denklemin her eklenmesi bir çözüm ekler. Orijinal ilk denklem:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
6 çözümü var. Bu denklemin tam karar ağacı şöyle görünür:

Sistemimizin ikinci denklemi birinciye benzer:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Tek fark, denklemin Y değişkenlerini kullanmasıdır. Bu denklemin de 6 çözümü vardır. Xi değişkenlerine ilişkin her çözüm, Yj değişkenlerine ilişkin her çözümle birleştirilebildiğinden, toplam çözüm sayısı 36'dır.

Oluşturulan karar ağacının yalnızca çözüm sayısını (dal sayısına göre) değil, aynı zamanda ağacın her bir dalına yazılan çözümlerin kendisini de verdiğini lütfen unutmayın.

Sorun 19

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

Bu görev önceki görevin değiştirilmiş halidir. Aradaki fark, X ve Y değişkenlerini ilişkilendiren başka bir denklemin eklenmesidir.

X 1 → Y 1 denkleminden, X 1'in değeri 1 olduğunda (böyle bir çözüm mevcut), Y 1'in de 1 değerine sahip olduğu sonucu çıkar. Dolayısıyla, X 1 ve Y 1'in değerlerine sahip olduğu bir küme vardır. 1. X 1, 0'a eşit olduğunda, Y 1, hem 0 hem de 1 olmak üzere herhangi bir değere sahip olabilir. Bu nedenle, X 1'in 0'a eşit olduğu her küme ve bu tür 5 küme vardır, Y değişkenli 6 kümenin tümüne karşılık gelir. Bu nedenle toplam çözüm sayısı 31'dir.

Sorun 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Çözüm: Temel denklikleri hatırlayarak denklemimizi şu şekilde yazıyoruz:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Döngüsel çıkarımlar zinciri, değişkenlerin aynı olduğu anlamına gelir, dolayısıyla denklemimiz şu denkleme eşdeğerdir:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Tüm X i'ler 1 veya 0 olduğunda bu denklemin iki çözümü vardır.

Sorun 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Çözüm: Tıpkı 20. problemde olduğu gibi, döngüsel çıkarımlardan özdeşliklere geçiyoruz ve denklemi şu şekilde yeniden yazıyoruz:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Bu denklem için bir karar ağacı oluşturalım:

Sorun 22

Aşağıdaki denklem sisteminin kaç çözümü vardır?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Cevap: 64

Çözüm: Aşağıdaki değişken değişimini uygulayarak 10 değişkenden 5 değişkene geçelim:

Y 1 = (X 1 ≡ X 2); Y2 = (X3 ≡X4); Y3 = (X5 ≡X6); Y4 = (X7 ≡X8); Y5 = (X9 ≡X10);

O zaman ilk denklem şu şekli alacaktır:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Denklem şu şekilde yazılarak basitleştirilebilir:

(Y 1 ≡ Y 2) = 0

Geleneksel forma geçerek sistemi formda sadeleştirmelerden sonra yazıyoruz:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Bu sistemin karar ağacı basittir ve değişken değişken değerlerine sahip iki daldan oluşur:

Orijinal X değişkenlerine dönersek, Y değişkenindeki her değer için X değişkenlerinde 2 değer bulunduğunu, dolayısıyla Y değişkenlerindeki her çözümün X değişkenlerinde 2 5 çözüm ürettiğini unutmayın. İki dal 2 * 2 üretir. 5 çözüm olduğuna göre toplam çözüm sayısı 64 olur.

Gördüğünüz gibi, bir denklem sistemini çözmenin her problemi kendi yaklaşımını gerektirir. Yaygın bir teknik, denklemleri basitleştirmek için eşdeğer dönüşümler gerçekleştirmektir. Yaygın bir teknik, karar ağaçları oluşturmaktır. Kullanılan yaklaşım kısmen, değişkenlerin tüm olası değer kümelerinin değil, yalnızca işlevin 1 (doğru) değerini aldığı kümelerin oluşturulduğu tuhaflığıyla bir doğruluk tablosu oluşturmayı anımsatıyor. Çoğu zaman önerilen problemlerde tam bir karar ağacı oluşturmaya gerek yoktur, çünkü ilk aşamada, örneğin problem 18'de yapıldığı gibi, sonraki her seviyede yeni dalların görünüm modelini oluşturmak mümkündür. .

Genel olarak, mantıksal denklemlerden oluşan bir sisteme çözüm bulmayı içeren problemler iyi matematik alıştırmalarıdır.

Sorunun manuel olarak çözülmesi zorsa, denklemleri ve denklem sistemlerini çözmek için uygun bir program yazarak çözümü bilgisayara emanet edebilirsiniz.

Böyle bir program yazmak zor değil. Böyle bir program, Birleşik Devlet Sınavında sunulan tüm görevlerle kolayca başa çıkacaktır.

Tuhaf bir şekilde, mantıksal denklem sistemlerine çözüm bulma görevi bir bilgisayar için zordur ve bilgisayarın da sınırları olduğu ortaya çıkar. Bilgisayar, değişken sayısının 20-30 olduğu problemlerle oldukça kolay başa çıkabilir ancak daha büyük boyutlu problemler üzerinde uzun süre düşünmeye başlayacaktır. Gerçek şu ki, küme sayısını belirten 2 n fonksiyonu, n arttıkça hızla büyüyen bir üstel sayıdır. O kadar hızlıdır ki, sıradan bir kişisel bilgisayar, günde 40 değişkenin olduğu bir işin üstesinden gelemez.

Mantıksal denklemleri çözmek için C# dilinde program

Mantıksal denklemleri çözmek için bir program yazmak birçok nedenden dolayı faydalıdır; yalnızca Birleşik Devlet Sınavı test problemlerine kendi çözümünüzün doğruluğunu kontrol etmek için kullanabileceğiniz için. Diğer bir neden ise böyle bir programın Birleşik Devlet Sınavındaki C kategorisi görevlerinin gerekliliklerini karşılayan bir programlama görevinin mükemmel bir örneği olmasıdır.

Bir program oluşturma fikri basittir; tüm olası değişken değer kümelerinin tam olarak aranmasına dayanır. Belirli bir mantıksal denklem veya denklem sistemi için değişkenlerin sayısı n bilindiğinden, sıralanması gereken kümelerin sayısı da bilinir - 2 n. C# dilinin temel işlevlerini (olumsuzlama, ayırma, bağlaç ve özdeşlik) kullanarak, belirli bir değişkenler kümesi için mantıksal bir denkleme veya denklemler sistemine karşılık gelen mantıksal işlevin değerini hesaplayan bir program yazmak zor değildir. .

Böyle bir programda, küme sayısına göre bir döngü oluşturmanız, kümenin sayısına göre döngünün gövdesinde kümenin kendisini oluşturmanız, bu küme üzerindeki fonksiyonun değerini hesaplamanız ve eğer bu değer ise 1 ise küme denklemin çözümünü verir.

Programı uygularken ortaya çıkan tek zorluk, set numarasına göre değişken değerler setinin kendisini oluşturma göreviyle ilgilidir. Bu sorunun güzelliği, görünüşte zor olan bu görevin aslında birçok kez ortaya çıkan basit bir soruna indirgenmesidir. Aslında, i sayısına karşılık gelen sıfırlardan ve birlerden oluşan değişken değerler kümesinin, i sayısının ikili gösterimini temsil ettiğini anlamak yeterlidir. Böylece, ayarlanan sayıya göre bir dizi değişken değer elde etmeye yönelik karmaşık görev, bir sayıyı ikiliye dönüştürme gibi tanıdık bir göreve indirgenir.

Sorunumuzu çözen, C#'taki bir fonksiyon şöyle görünür:

///

///

/// mantıksal fonksiyon - yöntem,

/// imzası DF temsilcisi tarafından belirtilen kişi

///

/// değişken sayısı

/// çözüm sayısı

static int SolveEquations(DF eğlenceli, int n)

bool kümesi = yeni bool[n];

int m = (int)Math.Pow(2, n); //küme sayısı

int p = 0, q = 0, k = 0;

//Set sayısına göre aramayı tamamla

for (int i = 0; i< m; i++)

//Sonraki setin oluşumu - set,

//i sayısının ikili gösterimiyle belirtilir

for (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Fonksiyonun setteki değerini hesaplıyoruz

Programı anlamak için program fikrinin açıklamaları ve metnindeki yorumların yeterli olduğunu umuyorum. Sadece verilen fonksiyonun başlığını açıklamaya odaklanacağım. SolveEquations fonksiyonunun iki giriş parametresi vardır. Eğlence parametresi, çözülmekte olan denklem veya denklem sistemine karşılık gelen mantıksal bir fonksiyonu belirtir. n parametresi eğlenceli değişkenlerin sayısını belirtir. Sonuç olarak SolveEquations işlevi, mantıksal işlevin çözüm sayısını, yani işlevin doğru olarak değerlendirdiği kümelerin sayısını döndürür.

Bazı F(x) işlevlerinin aritmetik, dize veya mantıksal türde bir değişken olan x giriş parametresine sahip olması okul çocukları için yaygındır. Bizim durumumuzda daha güçlü bir tasarım kullanılıyor. SolveEquations işlevi, parametreleri yalnızca basit değişkenler değil aynı zamanda işlevler de olabilen F(f) tipindeki işlevler olan üst düzey işlevlere atıfta bulunur.

SolveEquations işlevine parametre olarak aktarılabilecek işlevlerin sınıfı şu şekilde belirtilir:

temsilci bool DF(bool değişkenleri);

Bu sınıf, vars dizisi tarafından belirtilen mantıksal değişkenlerin değerlerinin bir kümesi olarak parametre olarak iletilen tüm işlevlere sahiptir. Sonuç, bu kümedeki işlevin değerini temsil eden bir Boolean değeridir.

Son olarak, çeşitli mantıksal denklem sistemlerini çözmek için SolveEquations işlevini kullanan bir program var. SolveEquations işlevi aşağıdaki ProgramCommon sınıfının bir parçasıdır:

sınıf ProgramıOrtak

temsilci bool DF(bool değişkenleri);

statik void Main(string argümanları)

Console.WriteLine("Ve İşlevler - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("Fonksiyonun 51 çözümü var - " +

Denklemleri Çöz(Fun51, 5));

Console.WriteLine("Fonksiyonun 53 çözümü var - " +

Denklemleri Çöz(Fun53, 10));

statik bool FunAnd(bool değişkenleri)

dönüş değişkenleri && değişkenler;

statik bool Fun51(bool değişkenleri)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

statik bool Fun53(bool değişkenleri)

f = f && ((değişkenler == değişkenler) || (değişkenler == değişkenler));

f = f && ((değişkenler == değişkenler) || (değişkenler == değişkenler));

f = f && ((değişkenler == değişkenler) || (değişkenler == değişkenler));

f = f && ((değişkenler == değişkenler) || (değişkenler == değişkenler));

f = f && ((değişkenler == değişkenler) || (değişkenler == değişkenler));

f = f && ((değişkenler == değişkenler) || (değişkenler == değişkenler));

f = f && (!((değişkenler == değişkenler) || (değişkenler == değişkenler)));

Bu programın çözüm sonuçları şöyle görünür:

Bağımsız çalışma için 10 görev

1. Üç fonksiyondan hangisi eşdeğerdir:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Verilen doğruluk tablosunun bir parçasıdır:

Bu parça üç işlevden hangisine karşılık gelir:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Jüri üç kişiden oluşuyor. Karar, jüri başkanının jüri üyelerinden en az birinin desteğiyle lehte oy kullanması halinde verilir. Aksi takdirde herhangi bir karar alınmaz. Karar verme sürecini resmileştiren mantıksal bir işlev oluşturun.
5. Dört yazı-tura atışının üç kez tura gelmesi durumunda X, Y'yi kazanır. X'in getirisini açıklayan mantıksal bir fonksiyon tanımlayın.
6. Cümle içindeki kelimeler birden başlanarak numaralandırılır. Aşağıdaki kuralların karşılanması durumunda bir cümlenin doğru kurulduğu kabul edilir:
   1. Çift sayılı bir sözcük sesli harfle bitiyorsa, eğer varsa sonraki sözcük sesli harfle başlamalıdır.
   2. Tek sayılı bir sözcük ünsüzle bitiyorsa, eğer varsa sonraki sözcük ünsüzle başlamalı ve sesli harfle bitmelidir.
      Aşağıdaki cümlelerden hangisi doğru kurulmuştur:
   3. Annem Masha'yı sabunla yıkadı.
   4. Bir lider her zaman bir modeldir.
   5. Gerçek iyidir ama mutluluk daha iyidir.
7. Denklemin kaç çözümü var:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Denklemin tüm çözümlerini listeleyin:
   (a → b) → c = 0
9. Aşağıdaki denklem sisteminin kaç çözümü vardır:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Denklemin kaç çözümü var:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Sorunlara cevaplar:

1. b ve c fonksiyonları eşdeğerdir.
2. Parça b fonksiyonuna karşılık gelir.
3. Jüri başkanı karara “lehte” oy verdiğinde mantıksal P değişkeni 1 değerini alsın. M 1 ve M 2 değişkenleri jüri üyelerinin görüşlerini temsil etmektedir. Olumlu bir karar vermeyi belirten mantıksal fonksiyon şu şekilde yazılabilir:
   P ˄ (M 1 ˅ M 2)
4. i'inci madeni para atıldığında tura geldiğinde P i mantıksal değişkeninin 1 değerini almasına izin verin. X getirisini belirten mantıksal fonksiyon şu şekilde yazılabilir:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Cümle b.
6. Denklemin 3 çözümü vardır: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Belediye bütçeli eğitim kurumu

"Ortaokul No. 18"

Başkurdistan Cumhuriyeti Salavat şehrinin kentsel bölgesi

Mantıksal denklem sistemleri

Bilgisayar bilimlerinde Birleşik Devlet Sınavı sorunları

Birleşik Devlet Sınavı görevlerindeki “Mantık Cebirinin Temelleri” bölümü çözülmesi en zor ve zor olanlardan biri olarak kabul edilir. Bu konuda tamamlanan görevlerin ortalama yüzdesi en düşük olup 43,2'dir.

2018 KIM spesifikasyonuna dayanan bu blok, farklı zorluk seviyelerinde dört görev içerir.

Görev 23'ün zorluk seviyesi yüksektir, dolayısıyla tamamlanma yüzdesi en düşüktür. Hazırlanan mezunların (81-100 puan) %49,8'i görevi tamamladı; orta derecede hazırlıklı olan mezunlar (61-80 puan) %13,7'sini tamamladı; geri kalan öğrenci grubu ise bu görevi tamamlamadı.

Bir mantıksal denklem sistemini çözmenin başarısı, mantık yasalarının bilgisine ve sistemi çözme yöntemlerinin kesin olarak uygulanmasına bağlıdır.

Haritalama yöntemini kullanarak bir mantıksal denklem sistemini çözmeyi düşünelim.

(23.154 Polyakov K.Yu.) Denklem sisteminin kaç farklı çözümü vardır?

((X1  sen1 )  (X2  sen2 ))  (X1  X2 )  (y1  sen2 ) =1

((X2  sen2 )  (X3  sen3 ))  (X2  X3 )  (y2  sen3 ) =1

((X7  sen7 )  (X8  sen8 ))  (X7  X8 )  (sen7  sen8 ) =1

Nerede X1 , X2 ,…, X8, en1 ey2 ,…,y8 - mantıksal değişkenler? 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. Sistemde yer alan tüm denklemler aynı tipte olup, her denklem dört değişken içermektedir. x1 ve y1'i bildiğimiz için, x2 ve y2'nin ilk denklemi sağlayan tüm olası değerlerini bulabiliriz. Benzer şekilde akıl yürüterek bilinen x2 ve y2'den ikinci denklemi sağlayan x3, y3'ü bulabiliriz. Yani, (x1, y1) çiftini bildiğimiz ve (x2, y2) çiftinin değerini belirlediğimizde, (x3, y3) çiftini bulacağız ve bu da (x4, y4) çiftine yol açacaktır. ve benzeri.

İlk denklemin tüm çözümlerini bulalım. Bu iki şekilde yapılabilir: akıl yürütme ve mantık yasalarını uygulama yoluyla bir doğruluk tablosu oluşturmak.

Doğruluk tablosu:

Doğruluk tablosu oluşturmak emek yoğun ve zaman açısından verimsiz bir iştir, bu nedenle ikinci yöntemi kullanıyoruz: mantıksal akıl yürütme. Ürün ancak ve ancak her faktörün 1'e eşit olması durumunda 1'e eşittir.

(X1  sen1 )  (X2  sen2 ))=1

(X1  X2 ) =1

(sen1  sen2 ) =1

İlk denkleme bakalım. 0 0, 0 1, 1 1 olduğunda sonuç 1'e eşittir, bu da (01), (10) için (x1 y1)=0 anlamına gelir, o zaman çift (X2  sen2 ) herhangi bir (00), (01), (10), (11) olabilir ve (x1 y1) = 1, yani (00) ve (11) olduğunda (x2 y2) = 1 çifti şu sonucu alır: aynı değerler (00) ve (11). İkinci ve üçüncü denklemlerin yanlış olduğu çiftleri, yani x1=1, x2=0, y1=1, y2=0'ı bu çözümün dışında bırakalım.

Toplam çift sayısı 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Mantıksal denklem sisteminin kaç farklı çözümü vardır?

(X 1  (X 2  sen 2 ))  (y 1  sen 2 ) = 1

(X 2  (X 3  sen 3 ))  (y 2  sen 3 ) = 1

...

( X 6  ( X 7  sen 7 ))  ( sen 6  sen 7 ) = 1

X 7  sen 7 = 1

Çözüm. 1) Denklemler aynı tiptedir, dolayısıyla akıl yürütmeyi kullanarak ilk denklemin tüm olası (x1,y1), (x2,y2) çiftlerini bulacağız.

(X1  (X2  sen2 ))=1

(sen1  sen2 ) = 1

İkinci denklemin çözümü (00), (01), (11) çiftleridir.

İlk denklemin çözümlerini bulalım. Eğer x1=0 ise x2, y2 – herhangi biri, eğer x1=1 ise x2, y2 (11) değerini alır.

(x1, y1) ve (x2, y2) çiftleri arasında bağlantı kuralım.

Her aşamadaki çift sayısını hesaplamak için bir tablo oluşturalım.

Son denklemin çözümleri dikkate alındığında X 7  sen 7 = 1, (10) çiftini hariç tutalım. 1+7+0+34=42 toplam çözüm sayısını bulun

3)(23.180) Bir mantıksal denklem sisteminin kaç farklı çözümü vardır?

(X1  X2 )  (X3  X4 ) = 1

(X3  X4 )  (X5  X6 ) = 1

(X5  X6 )  (X7  X8 ) = 1

(X7  X8 )  (X9  X10 ) = 1

X1  X3  X5  X7  X9 = 1

Çözüm. 1) Denklemler aynı türdedir, dolayısıyla akıl yürütmeyi kullanarak ilk denklemin tüm olası (x1,x2), (x3,x4) çiftlerini bulacağız.

(X1  X2 )  (X3  X4 ) = 1

Sırada 0 (1 0) veren çiftleri çözümden çıkaralım, bunlar (01, 00, 11) ve (10) çiftleridir.

(x1,x2), (x3,x4) çiftleri arasında bağlantı kuralım

n değişkenli mantıksal bir fonksiyon olsun. Mantıksal denklem şuna benzer:

C sabiti 1 veya 0 değerine sahiptir.

Mantıksal bir denklemin 0'dan farklı çözümlere sahip olabilir. Eğer C 1'e eşitse, çözümler F fonksiyonunun doğru (1) değerini aldığı doğruluk tablosundaki tüm değişken kümeleridir. Geriye kalan kümeler C'nin sıfıra eşit olduğu denklemin çözümleridir. Her zaman yalnızca formun denklemlerini düşünebilirsiniz:

Aslında denklem şu şekilde verilsin:

Bu durumda eşdeğer denkleme gidebiliriz:

k mantıksal denklemden oluşan bir sistem düşünün:

Bir sistemin çözümü, sistemin tüm denklemlerinin karşılandığı bir dizi değişkendir. Mantıksal fonksiyonlar açısından, bir mantıksal denklemler sisteminin çözümünü elde etmek için, orijinal fonksiyonların birleşimini temsil eden, mantıksal F fonksiyonunun doğru olduğu bir küme bulunmalıdır:

Değişken sayısı küçükse, örneğin 5'ten azsa, o zaman fonksiyon için sistemin kaç çözümü olduğunu ve çözümleri veren kümelerin neler olduğunu söylemenize olanak tanıyan bir doğruluk tablosu oluşturmak zor değildir.

Mantıksal denklem sistemine çözüm bulmaya yönelik bazı USE problemlerinde değişken sayısı 10'a ulaşır. O zaman doğruluk tablosu oluşturmak neredeyse imkansız bir iş haline gelir. Sorunu çözmek farklı bir yaklaşım gerektirir. Rastgele bir denklem sistemi için, bu tür problemlerin çözümüne olanak sağlayan, numaralandırma dışında genel bir yöntem yoktur.

Sınavda önerilen problemlerde çözüm genellikle denklem sisteminin özelliklerinin dikkate alınmasına dayanır. Tekrar ediyorum, bir dizi değişken için tüm seçenekleri denemek dışında sorunu çözmenin genel bir yolu yok. Çözüm sistemin özelliklerine göre oluşturulmalıdır. Bilinen mantık yasalarını kullanarak bir denklem sisteminin ön basitleştirmesini gerçekleştirmek genellikle faydalıdır. Bu sorunu çözmek için başka bir yararlı teknik aşağıdaki gibidir. Tüm kümelerle değil, yalnızca fonksiyonun 1 değerine sahip olduğu kümelerle ilgileniyoruz. Tam bir doğruluk tablosu oluşturmak yerine, onun analogunu (ikili karar ağacı) oluşturacağız. Bu ağacın her dalı bir çözüme karşılık gelir ve fonksiyonun 1 değerine sahip olduğu bir kümeyi belirtir. Karar ağacındaki dalların sayısı, denklem sisteminin çözümlerinin sayısıyla örtüşür.

İkili karar ağacının ne olduğunu ve nasıl oluşturulduğunu çeşitli problemlerden örnekler kullanarak açıklayacağım.

Sorun 18

İki denklem sistemini 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?

Cevap: Sistemin 36 farklı çözümü vardır.

Çözüm: Denklem sistemi iki denklem içerir. 5 değişkene bağlı olarak ilk denklemin çözüm sayısını bulalım - . İlk denklem 5 denklemden oluşan bir sistem olarak düşünülebilir. Gösterildiği gibi, denklem sistemi aslında mantıksal fonksiyonların birleşimini temsil eder. Tersi ifade de doğrudur; koşulların birleşimi bir denklem sistemi olarak düşünülebilir.

İlk denklem olarak kabul edilebilecek bağlacın ilk terimi olan () sonucunu çıkarmak için bir karar ağacı oluşturalım. Bu ağacın grafiksel temsili böyle görünüyor

Ağaç, denklemdeki değişken sayısına göre iki seviyeden oluşur. Birinci düzey ilk değişkeni tanımlar. Bu düzeyin iki dalı, bu değişkenin olası değerlerini yansıtır - 1 ve 0. İkinci düzeyde, ağacın dalları yalnızca denklemin doğru olarak değerlendirdiği değişkenin olası değerlerini yansıtır. Denklem bir çıkarımı belirttiğinden, 1 değerine sahip bir dal, bu dalda 1 değerinin olmasını gerektirir. 0 değerine sahip bir dal, 0 ve 1 değerlerine sahip iki dal üretir. ağaç, anlamı 1 değerini alan üç çözümü belirtir. Her dalda, denklemin çözümünü veren karşılık gelen bir değişken değerleri kümesi yazılır.

Bu kümeler şunlardır: ((1, 1), (0, 1), (0, 0))

Aşağıdaki denklemi ve aşağıdaki çıkarımı ekleyerek karar ağacını oluşturmaya devam edelim. Denklem sistemimizin özelliği, sistemin her yeni denkleminin önceki denklemden bir değişken kullanması ve yeni bir değişken eklemesidir. Değişken ağaçta zaten değerlere sahip olduğundan değişkenin 1 değerine sahip olduğu tüm dallarda değişken de 1 değerine sahip olacaktır. Bu tür dallar için ağacın yapımı bir sonraki seviyeye devam eder, ancak yeni şube görünmüyor. Değişkenin 0 değerine sahip olduğu tek bir dal, değişkenin 0 ve 1 değerlerini alacağı iki dala ayrılacaktır. Böylece, yeni bir denklemin her eklenmesi, özgüllüğü göz önüne alındığında, bir çözüm ekler. Orijinal ilk denklem:

6 çözümü var. Bu denklemin tam karar ağacı şöyle görünür:

Sistemimizin ikinci denklemi birinciye benzer:

Tek fark, denklemin Y değişkenlerini kullanmasıdır. Bu denklemin de 6 çözümü vardır. Her değişken çözüm, her değişken çözümle birleştirilebildiğinden toplam çözüm sayısı 36'dır.

Oluşturulan karar ağacının yalnızca çözüm sayısını (dal sayısına göre) değil, aynı zamanda ağacın her bir dalına yazılan çözümlerin kendisini de verdiğini lütfen unutmayın.

Sorun 19

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?

Bu görev önceki görevin değiştirilmiş halidir. Aradaki fark, X ve Y değişkenlerini ilişkilendiren başka bir denklemin eklenmesidir.

Denklemden, değeri 1 olduğunda (böyle bir çözüm mevcut), o zaman 1 değerine sahip olduğu sonucu çıkar. Dolayısıyla, üzerinde değerleri 1 olan bir küme vardır. 0'a eşit olduğunda, hem 0 hem de 1 herhangi bir değeri vardır. Bu nedenle, 0'a eşit olan her küme ve bu tür 5 küme vardır, Y değişkenli 6 kümenin tümüne karşılık gelir. Bu nedenle toplam çözüm sayısı 31'dir.

Sorun 20

Çözüm: Temel denklikleri hatırlayarak denklemimizi şu şekilde yazıyoruz:

Döngüsel çıkarımlar zinciri, değişkenlerin aynı olduğu anlamına gelir, dolayısıyla denklemimiz şu denkleme eşdeğerdir:

Bu denklemin, tümü 1 veya 0 olduğunda iki çözümü vardır.

Sorun 21

Denklemin kaç çözümü var:

Çözüm: Tıpkı 20. problemde olduğu gibi, döngüsel çıkarımlardan özdeşliklere geçiyoruz ve denklemi şu şekilde yeniden yazıyoruz:

Bu denklem için bir karar ağacı oluşturalım:

Sorun 22

Aşağıdaki denklem sisteminin kaç çözümü vardır?