Mantıksal denklemlerin çözümü. Mantıksal işlemlerin önceliği

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 bir doğruluk tablosu oluşturmak zor değildir; bu, sistemin kaç çözüme sahip olduğunu ve çözüm sağlayan kümelerin neler olduğunu söylememize olanak tanır.

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. Bir değişkenin 0 değerine sahip olduğu tek bir dal, değişkenin 0 ve 1 değerlerini alacağı iki dallara ayrılacaktır. Böylece, yeni bir denklemin kendine özgülüğü göz önüne alındığında her eklenmesi 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 denklemde Y değişkenleri kullanılıyor.Bu denklemin de 6 çözümü var. 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 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?

Yıl sonunda üç varsayımdan yalnızca birinin doğru olduğu ortaya çıktı. Yıl sonunda hangi bölümler kâr etti?

Çözüm. Sorun koşullarından varsayımları mantıksal ifadeler şeklinde yazalım: “B bölümünden kâr elde etmek, elde etmek için gerekli bir koşul değildir.

A bölümüyle kâr ":F 1 (A, B, C) = A → B

“A bölümünün kar etmesi için en az bir B ve C bölümünden kar elde etmek yeterli değildir”: F 2 (A, B, C) = (B + C) → A

“A ve B bölümleri aynı anda kâr etmeyecektir”: F 3 (A, B, C) = A B

Koşuldan, üç varsayımdan yalnızca birinin doğru olduğu bilinmektedir. Bu, aşağıdaki üç mantıksal ifadeden hangisinin tamamen yanlış olmadığını bulmamız gerektiği anlamına gelir:

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

Sonuç olarak yıl sonunda ikinci varsayımın doğru, birinci ve üçüncü varsayımın ise yanlış olduğu ortaya çıktı.

Dolayısıyla C bölümü kar elde edecek, ancak A ve B bölümü kar alamayacaktır.

Mantık Denklemlerini Çözme

Devlet merkezi test metinlerinde mantıksal bir denklemin kökünü bulmayı isteyen bir görev (A8) vardır. Bir örnek kullanarak bu tür görevleri çözmenin yollarına bakalım.

Mantıksal denklemin kökünü bulun: (A + B)(X AB) = B + X → A.

İlk çözüm bir doğruluk tablosu oluşturmaktır. Denklemin sağ ve sol tarafları için doğruluk tabloları oluşturalım ve bu tabloların son sütunlarındaki değerlerin hangi X'te çakıştığını görelim.

F1 (A, B, X) = (A+ B)(X AB)

F2 (A, B, X) = B+ X→ A

Ortaya çıkan doğruluk tablolarını karşılaştıralım ve F 1 (A, B, X) ve F 2 (A, B, X) değerlerinin çakıştığı satırları seçelim.

Yalnızca argüman sütunlarını bırakarak yalnızca seçilen satırları yeniden yazalım. X değişkenine A ve B'nin bir fonksiyonu olarak bakalım.

Açıkçası, X = B → A.

İkinci çözüm, denklemdeki eşittir işaretini eşdeğer bir işaretle değiştirmek ve ardından ortaya çıkan mantıksal denklemi basitleştirmektir.

Daha fazla çalışmayı kolaylaştırmak için önce mantıksal denklemin sağ ve sol taraflarını basitleştirelim ve olumsuzlarını bulalım:

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

Mantıksal denklemimizdeki eşittir işaretini bir denklik işaretiyle değiştirelim:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +

+ (X A B+ X A B+ X A B) (B+ X A) =

= (X A B+ X B+ X A B) + (X A B+ X A B) =

X ve X çarpanlarını parantez dışında alarak bu ifadenin mantıksal terimlerini yeniden düzenleyelim.

X(A B) + X(B+ AB) = X(A B) + X(B+ A) =

T = A B'yi gösterelim, o halde

X T+ X T= X↔ T.

Dolayısıyla mantıksal bir denklemin çözümü olması için: X = A B = B + A = B → A.

Bilgisayar mantık öğeleri. Fonksiyonel diyagramların oluşturulması

Bilgisayar teknolojisinin gelişmesiyle birlikte matematiksel mantığın, bilgisayar teknolojisinin tasarımı ve programlanması konularıyla yakından ilişkili olduğu ortaya çıktı. Mantık cebiri başlangıçta geliştirme aşamasında geniş uygulama alanı buldu röle kontağışemalar Bilgisayar tasarımıyla ilgilenen mühendislerin dikkatini Boole cebri kullanarak elektrik devrelerini analiz etme olasılığına çeken ilk temel araştırma, Aralık 1938'de Amerikalı Claude Shannon tarafından "Merdiven Devrelerinin Sembolik Analizi" yayınlandı. Bu makaleden sonra Boole cebiri kullanılmadan bilgisayar tasarımı yapılamazdı.

Mantık öğesi ayırma, birleştirme ve ters çevirmenin mantıksal işlemlerini uygulayan bir devredir. Bir okul fizik dersinden aşina olduğunuz, elektriksel röle-kontak devreleri aracılığıyla mantıksal elemanların uygulanmasını düşünelim.

Kontakların seri bağlantısı

Kontakların paralel bağlantısı

Devrelerin durumunun, kontakların tüm olası durumlarına bağımlılık tablosunu derleyelim. Aşağıdaki gösterimleri tanıtalım: 1 – kontak kapalı, devrede akım var; 0 – kontak açık, devrede akım yok.

Gördüğünüz gibi seri bağlantılı bir devre, bağlantının mantıksal işlemine karşılık gelir, çünkü devredeki akım yalnızca A ve B kontakları aynı anda kapatıldığında ortaya çıkar. Paralel bağlantılı bir devre, yalnızca her iki kontak açık olduğu anda devrede akım olmadığından, mantıksal ayırma işlemine karşılık gelir.

Ters çevirmenin mantıksal işlemi, prensibi bir okul fizik dersinde incelenen bir elektromanyetik rölenin kontak devresi aracılığıyla gerçekleştirilir. X kapalıyken x kontağı açıktır ve bunun tersi de geçerlidir.

Bilgisayarların mantıksal devrelerini oluşturmak için röle kontak elemanlarının kullanılması, düşük güvenilirlik, büyük boyutlar, yüksek güç tüketimi ve düşük performans nedeniyle kendini haklı çıkarmamıştır. Elektronik cihazların (vakum ve yarı iletken) ortaya çıkışı, saniyede 1 milyon anahtarlama ve daha yüksek hızlara sahip mantık elemanlarının inşa edilmesi olasılığını yarattı. Yarı iletken mantık elemanları, elektromanyetik röleye benzer şekilde anahtar modunda çalışır. Kontak devreleri için sunulan teorinin tamamı yarı iletken elemanlara aktarılmıştır. Yarı iletkenlerdeki mantık elemanları, kontakların durumuyla değil, giriş ve çıkıştaki sinyallerin varlığıyla karakterize edilir.

Temel mantıksal işlemleri uygulayan mantıksal öğeleri ele alalım:

fonksiyona karşılık gelen diyagram:

&F(X, Y, Z)

Bağlaç normalini kullanarak problemleri çözme

Ve ayırıcı-normal formlar

İÇİNDE Mantık problemi kitapları genellikle, uygulayan bir fonksiyon yazmanız gereken standart problemleri içerir. Merdiven diyagramını basitleştirin ve bu fonksiyon için bir doğruluk tablosu oluşturun. Ters problem nasıl çözülür? Rastgele bir doğruluk tablosu verildiğinde, işlevsel veya röle diyagramı oluşturmanız gerekir. Bugün bu konuyu ele alacağız.

Herhangi bir mantıksal cebir fonksiyonu üç işlemin birleşimi ile temsil edilebilir: birleşme, ayrılma ve ters çevirme. Bunun nasıl yapıldığını bulalım. Bunu yapmak için birkaç tanım yazalım.

Minterm, belirli sayıda değişkenin birleşimi veya bunların olumsuzlanmasıyla oluşan bir fonksiyondur. Minterm mümkün olan tüm kümelerden yalnızca biri için 1 değerini alır

argümanlar ve diğerleri için değer 0'dır. Örnek: x 1 x 2 x 3 x 4 .

Bir maxterm, belirli sayıda değişkenin ayrılması veya bunların olumsuzlanmasıyla oluşturulan bir fonksiyondur. Maxterm olası kümelerden birinde 0, diğerlerinde ise 1 değerini alır.

Örnek: x 1 + x 2 + x 3.

İşlev ayırıcı normal form(DNF) mintermlerin mantıksal toplamıdır.

Örnek: x 1x 2+ x 1x 2+ x 1x 2x 3.

Bağlaç normal formu(CNF), temel ayrımların (maxterms) mantıksal bir ürünüdür.

Örnek: (x 1+ x 2+ x 3) (x 1+ x 2) .

Mükemmel ayırıcı normal form Her bir mintermde tüm değişkenlerin veya bunların olumsuzlamalarının mevcut olduğu DNF denir.

Örnek: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Mükemmel birleştirici normal form her bir maksimum terimde tüm değişkenlerin veya bunların olumsuzlamalarının mevcut olduğu CNF olarak adlandırılır.

Örnek: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

Tablodan mantıksal fonksiyon yazma

Herhangi bir mantıksal fonksiyon SDNF veya SCNF olarak ifade edilebilir. Örnek olarak tabloda sunulan f fonksiyonunu düşünün.

G0, G1, G4, G5, G7 fonksiyonları mintermlerdir (tanıma bakınız). Bu fonksiyonların her biri üç değişkenin çarpımı veya tersidir ve yalnızca bir durumda 1 değerini alır. F fonksiyonunun değerinde 1 elde etmek için bir minterme ihtiyaç duyulduğu görülmektedir. Sonuç olarak, bu fonksiyonun SDNF'sini oluşturan minterm sayısı, fonksiyon değerindeki birim sayısına eşittir: f= G0+G1+G4+G5+G7. Böylece, SDNF şu forma sahiptir:

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

Benzer şekilde SKNF'yi de oluşturabilirsiniz. Faktörlerin sayısı, fonksiyon değerlerindeki sıfırların sayısına eşittir:

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

Böylece tablo şeklinde verilen herhangi bir mantıksal fonksiyon formül olarak yazılabilir.

Doğruluk tablosu kullanarak SDNF oluşturmaya yönelik algoritma

Bazı fonksiyonların doğruluk tablosu verilmiştir. Bir SDNF oluşturmak için aşağıdaki adım dizisini uygulamanız gerekir:

1. Fonksiyonun 1 değerini aldığı tüm tablo satırlarını seçin.

2. Bu tür her satır için, tüm argümanların veya bunların ters çevrilmelerinin (minterm) bir birleşimini atayın. Bu durumda 0 değerini alan argüman olumsuzlamalı olarak minterme dahil edilir, 1 değeri ise olumsuzluksuz olarak dahil edilir.

3. Son olarak elde edilen tüm mintermlerin ayrımını oluşturuyoruz. Mintermlerin sayısı mantıksal fonksiyonun birim sayısıyla eşleşmelidir.

Doğruluk tablosu kullanarak SCNF oluşturmaya yönelik algoritma

Bazı fonksiyonların doğruluk tablosu verilmiştir. SKNF'yi oluşturmak için aşağıdaki adım dizisini uygulamanız gerekir:

1. Fonksiyonun 0 değerini aldığı tablonun tüm satırlarını seçin.

2. Bu tür her satır için, tüm argümanların veya bunların ters çevrilmelerinin (maxterm) bir ayrımını atayın. Bu durumda 1 değerini alan bir argüman maxterm'e olumsuzlamayla dahil edilir ve 1 değeri olumsuzlama olmadan dahil edilir.

3. Son olarak elde edilen tüm maksimum terimlerin birleşimini oluşturuyoruz. Maxterms sayısı mantıksal fonksiyonun sıfır sayısıyla eşleşmelidir.

İki formdan (SDNF veya SKNF) daha az harf içeren olanı tercih etmeyi kabul edersek, doğruluk tablosu fonksiyonunun değerleri arasında daha az sayıda varsa, SKNF - daha az sıfır varsa SDNF tercih edilir.

Örnek. Üç değişkenli bir mantıksal fonksiyonun doğruluk tablosu verilmiştir. Bu işlevi uygulayan mantıksal bir formül oluşturun.

Bu doğruluk tablosunda fonksiyon değerinin 0 olduğu satırları seçelim.

F(A, B, C) = (A+ B+ C) (A+ B+ C)

Bir doğruluk tablosu oluşturarak türetilmiş fonksiyonu kontrol edelim.

Başlangıç ​​ve son doğruluk tablolarını karşılaştırarak mantıksal fonksiyonun doğru şekilde oluşturulduğu sonucuna varabiliriz.

Problem çözme

1. Üç öğretmen Olimpiyat için problemleri seçiyor. Aralarından seçim yapabileceğiniz çeşitli görevler var. Her bir görev için her öğretmen kendi görüşünü ifade eder: kolay (0) veya zor (1) bir görev. Bir görev, en az iki öğretmen tarafından zor olarak işaretlenirse Olimpiyat görevine dahil edilir, ancak üç öğretmenin tümü de zor olarak değerlendirilirse, o zaman böyle bir görev Olimpiyat görevine çok zor olarak dahil edilmez. Görev Olimpiyat görevine dahilse 1, dahil değilse 0 çıktısı verecek bir cihazın mantıksal diyagramını yapın.

İstenilen fonksiyon için bir doğruluk tablosu oluşturalım. Üç girdi değişkenimiz var (üç öğretmen). Bu nedenle gerekli fonksiyon üç değişkenin fonksiyonu olacaktır.

Problem durumunu analiz ederek aşağıdaki doğruluk tablosunu elde ederiz:

SDNF'yi inşa ediyoruz. F(A, B, C) = ABC+ ABC+ ABC

Şimdi bu fonksiyonun mantıksal bir diyagramını oluşturuyoruz.

B&1F(A,B,C)

2. Bilgisayar biliminin temel dersinde Şehir Olimpiyatı, 2007.Üç katlı bir evin girişi için herhangi bir kattaki anahtarın tüm evin ışıklarını açıp kapatabileceği bir elektrik devre şeması oluşturun.

Yani ışığı açıp kapatmak için kullanmamız gereken üç anahtarımız var. Her anahtarın iki durumu vardır: yukarı (0) ve aşağı (1). Her üç anahtarın da 0 konumunda olması durumunda girişteki ışıkların söndüğünü varsayalım. Daha sonra üç anahtardan herhangi birini 1 konumuna getirdiğinizde girişteki ışığın yanması gerekmektedir. Açıkçası, herhangi bir anahtarı 1 konumuna getirdiğinizde girişteki ışık sönecektir. Üçüncü anahtar 1 konumuna getirilirse girişteki ışık yanacaktır. Bir doğruluk tablosu oluşturuyoruz.

O zaman F(A, B, C) = ABC+ ABC+ ABC+ ABC olur.

Not. Bu sorunu başarıyla çözmek için aşağıdaki mantıksal formülleri unutmayın:

x → y= x+ y x y= x y+ x y

x ↔ y= x y+ x y

Bize üç değişkenli F 1 (A, B, C) = C → A + B = C + A B'den oluşan mantıksal bir fonksiyon verilmiştir.

B ve C değişkenlerini aynı anda değiştirelim: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Bu iki fonksiyon için doğruluk tabloları oluşturalım:

Ortaya çıkan tabloyu analiz edelim. Tablonun sekiz satırından yalnızca ikisinde (2. ve 3.) fonksiyon değeri değişmez. Bu satırlarda A değişkeninin değerini tersine çevirmediğine, ancak B ve C değişkenlerinin bunu tersine çevirdiğine dikkat edin.

Şu satırları kullanarak SKNF fonksiyonlarını oluşturuyoruz:

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .

A+ (B↔ C) = A+ B C= (B C) → A

Bu nedenle istenilen cevap 4'tür.

4. Mantıksal bir fonksiyonun değerini değiştirme koşulu F (A, B, C) = C + AB iken A ve B argümanlarını aynı anda değiştirmek şuna eşittir:

Ortaya çıkan tabloyu analiz edelim. Tablonun sekiz satırından yalnızca ikisinde (1. ve 7.) fonksiyon değerini değiştirir. Bu satırlarda C değişkeninin değerini değiştirmediğini ancak A ve B değişkenlerinin değerini değiştirdiğini lütfen unutmayın.

Şu satırları kullanarak SDNF işlevlerini oluşturuyoruz:

F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)

Bu nedenle istenilen cevap 2'dir.

Referanslar

1. Shapiro S.I. Mantıksal ve oyun problemlerini çözme(mantıksal ve psikolojik çalışmalar). – M.: Radyo ve İletişim, 1984. – 152 s.

2. Sholomov L.A. Ayrık mantıksal ve bilgi işlem aygıtları teorisinin temelleri. – M.: Bilim. Ch. ed. fiziksel - paspas. yanıyor, 1980. - 400 s.

3. Pukhalsky G.I., Novoseltseva T.Ya. Entegre devrelerde ayrık cihazların tasarımı: El Kitabı. – M.: Radyo ve İletişim, 1990.

Mantıksal denklem sistemlerini çözme yöntemleri

Kırgizova E.V., Nemkova A.E.

Lesosibirsk Pedagoji Enstitüsü –

Sibirya Federal Üniversitesi Şubesi, Rusya

Tutarlı düşünme, ikna edici akıl yürütme, hipotezler kurma ve olumsuz sonuçları çürütme yeteneği kendi başına gelmez; bu beceri mantık bilimi tarafından geliştirilmiştir. Mantık, bazı ifadelerin doğruluğunu veya yanlışlığını, diğer ifadelerin doğruluğu veya yanlışlığı temelinde tespit etmeye yönelik yöntemleri inceleyen bir bilimdir.

Mantıksal problemleri çözmeden bu bilimin temellerine hakim olmak imkansızdır. Kişinin bilgisini yeni bir durumda uygulamaya yönelik becerilerin gelişiminin test edilmesi, geçerek gerçekleştirilir. Özellikle mantıksal problemleri çözme yeteneğidir. Birleşik Devlet Sınavındaki B15 Görevleri, mantıksal denklem sistemleri içerdikleri için artan karmaşıklığa sahip görevlerdir. Mantıksal denklem sistemlerini çözmenin çeşitli yolları vardır. Bu, bir denkleme indirgeme, doğruluk tablosu oluşturma, ayrıştırma, denklemlerin sıralı çözümü vb.'dir.

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

Hadi 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 bir çözümü vardır: bir= 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:İzin vermek A = 0 ise:

Elde ettiğimiz ilk denklemden B =0 ve ikinciden itibaren – C=1. Sistemin çözümü: A = 0, B = 0 ve C = 1.

Yöntemi de kullanabilirsiniz Denklemlerin sıralı çözümü , her adımda, söz konusu kümeye bir değişken eklenir. Bunu yapmak için denklemleri, değişkenler alfabetik sıraya göre girilecek şekilde dönüştürmek gerekir. Daha sonra değişkenleri sırayla ekleyerek bir karar ağacı oluşturuyoruz.

Sistemin ilk denklemi yalnızca A ve B'ye, ikinci denklemi ise A ve C'ye bağlıdır. A değişkeni 0 ve 1 olmak üzere 2 değer alabilir:

İlk denklemden şu sonuç çıkıyor , Öyleyse ne zaman A = 0 ve B = 0 elde ederiz ve A = 1 için B = 1 elde ederiz. Dolayısıyla ilk denklemin A ve B değişkenlerine göre iki çözümü vardır.

Her seçenek için C değerlerini belirlediğimiz ikinci denklemi tasvir edelim. A =1 olduğunda sonuç yanlış olamaz, yani ağacın ikinci dalının çözümü yoktur. Şu tarihte: bir= 0 tek çözümü buluyoruz C= 1 :

Böylece sistemin çözümünü elde ettik: A = 0, B = 0 ve C = 1.

Bilgisayar bilimlerindeki Birleşik Devlet Sınavında, çoğu zaman bir mantıksal denklem sisteminin çözüm sayısını, çözümleri kendileri bulmadan belirlemek gerekir; bunun için de belirli yöntemler vardır. Bir mantıksal denklem sisteminin çözüm sayısını bulmanın ana yolu değ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:Denklemin kaç çözümü var ( bir → B ) + (C → D ) = 1? 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 bir imadır, yani üç durumda doğru, 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.

Öyleymiş gibi yapalımX 1 – doğruysa, ilk denklemden bunu elde ederizX 2 ikincisinden itibaren de doğru -X 3 =1 ve bu şekilde devam edene kadar xm= 1. Yani (1; 1; …; 1) kümesi M birimler sistemin çözümüdür. Şimdi izin verX 1 =0 ise elimizdeki ilk denklemdenX 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ümde M değişken değerleri):

(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. Eşit olduğunu görmek kolaydır m +1.

Akıl yürütmede ve karar ağacı oluşturmada zorluklar olması durumunda, kullanarak bir çözüm arayabilirsiniz. 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:

Daha sonra, aşağıdaki üç durumda bir denklemin doğru olduğunu görebilirsiniz: (0; 0), (0; 1), (1; 1). İki denklemden oluşan bir sistem dört durumda doğrudur (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Bu durumda sadece sıfır ve daha fazlasından oluşan bir çözümün olduğu hemen anlaşılır. M Son konumdan başlayarak mümkün olan tüm yerler dolduruluncaya kadar her seferinde bir birimin eklendiği çözümler. Genel çözümün aynı formda olacağı varsayılabilir ancak böyle bir yaklaşımın çözüm olabilmesi için varsayımın doğru olduğunun kanıtlanması gerekir.

Yukarıdakilerin hepsini özetlemek gerekirse, tartışılan yöntemlerin hepsinin evrensel olmadığı gerçeğine dikkatinizi çekmek isterim. Her mantıksal denklem sistemini çözerken, çözüm yönteminin seçilmesi gereken özellikleri dikkate alınmalıdır.

Edebiyat:

1. Mantıksal problemler / O.B. Bogomolov – 2. baskı. – M.: BİNOM. Bilgi Laboratuvarı, 2006. – 271 s.: hasta.

2. Polyakov K.Yu. Mantıksal denklem sistemleri / Bilgisayar bilimleri öğretmenleri için eğitimsel ve metodolojik gazete: Bilişim No. 14, 2011.

Ders konusu: Mantık Denklemlerini Çözme

Gelişimsel - öğrencilerin bilişsel ilgisinin gelişmesi için koşullar yaratmak, hafızanın, dikkatin ve mantıksal düşünmenin gelişimini teşvik etmek;

eğitici : Başkalarının fikirlerini dinleme yeteneğini geliştirmek, Nihai sonuçlara ulaşmak için irade ve azmi beslemek.

Ders türü: birleşik ders

Teçhizat: bilgisayar, multimedya projektörü, sunum 6.

Dersler sırasında

Temel bilgilerin tekrarı ve güncellenmesi. Ödev kontrolü (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:

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ı

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.

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.

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. Olumsuzluğun 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:
   bir ˄ bir ≡ bir
   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ış olur. İ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 değil, 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şit 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. X2 değişkeninin 0 değerine sahip olduğu tek dal, X3 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 denklemde Y değişkenleri kullanılıyor.Bu denklemin de 6 çözümü var. 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 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 mevcuttur), 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ş edebilir, 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 çözmeye yönelik bir program yazmak, yalnızca Birleşik Devlet Sınavı test sorunlarına kendi çözümünüzün doğruluğunu kontrol etmek için kullanabildiğiniz için birçok nedenden dolayı faydalıdır. 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 döngünün gövdesinde küme sayısına göre bir döngü oluşturmanız, küme sayısını kullanarak kümenin kendisini oluşturmanız, bu küme üzerindeki fonksiyonun değerini hesaplamanız ve eğer bu ise değer 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 Fonksiyonlar - " +

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)