Mantıksal denklem sistemlerinin grafiksel çözümü. Mantıksal denklem sistemlerini çözme yöntemleri

Bu materyal çözüm yöntemlerini sunan bir sunum içermektedir. mantıksal denklemler ve bilgisayar bilimlerinde Birleşik Devlet Sınavının B15 (No. 23, 2015) görevindeki mantıksal denklem sistemleri. Bu görevin Birleşik Devlet Sınavı görevleri arasında en zorlarından biri olduğu bilinmektedir. Sunum, özel sınıflarda “Mantık” konulu dersler verirken ve Birleşik Devlet Sınavına hazırlanırken yararlı olabilir.

İndirmek:

Ön izleme:

Sunum önizlemelerini kullanmak için kendiniz için bir hesap oluşturun ( hesap) Google'a gidin ve giriş yapın: https://accounts.google.com

Slayt başlıkları:

B15 görevinin çözümü (mantıksal denklem sistemleri) Vishnevskaya M.P., MAOU “Spor Salonu No. 3” 18 Kasım 2013, Saratov

Görev B15, bilgisayar bilimlerinde Birleşik Devlet Sınavındaki en zor görevlerden biridir!!! Aşağıdaki beceriler test edilir: mantıksal değişkenler içeren ifadeleri dönüştürmek; belirli bir mantıksal değişken kümesinin doğru olduğu mantıksal değişkenlerin değer kümesini doğal dilde tanımlayın; Verilen koşulları sağlayan ikili kümelerin sayısını sayın. En zor şey çünkü... bunun nasıl yapılacağına dair resmi bir kural yoktur, tahmin gerektirir.

Onsuz yapamayacağınız şey!

Sembollerin birleşimi: A /\ B , A  B , AB , A &B, A ve B ayrımı: A \ / B , A + B , A | B , A veya B olumsuzluğu:  A , A, A değil Eşdeğerlik: A  B, A  B, A  B dışlayıcı “veya”: A  B , A xor B

Değişken değiştirme yöntemi Aşağıda listelenen tüm koşulları karşılayan x1, x2, ..., x9, x10 mantıksal değişkenlerinin kaç farklı değer kümesi mevcuttur: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Yanıtın tüm farklı x1, x2, …, x9, x10 kümelerini listelemesi gerekmez; bu eşitlik sistemi geçerlidir. Cevap olarak bu tür setlerin sayısını belirtmelisiniz (demo versiyonu 2012)

Çözüm Adım 1. Değişkenleri değiştirerek basitleştirin t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Sadeleştirmeden sonra: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Denklemlerden birini düşünün: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Açıkçası, yalnızca değişkenlerden biri 0 ve diğeri 1 olduğunda =1 olur XOR işlemini birleşme ve ayrılma yoluyla ifade etmek için formülü kullanalım: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Adım 2. Sistem analizi ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .İle. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), o zaman tk'nin her değeri iki x2k-1 ve x2k değer çiftine karşılık gelir, örneğin: tk =0 iki çifte karşılık gelir - (0 ,1) ve (1, 0) ve tk =1 – (0,0) ve (1,1) çiftleri.

Aşama 3. Çözümlerin sayısını saymak. Her t'nin 2 çözümü vardır, t sayısı 5'tir. Yani. t değişkenleri için 2 5 = 32 çözüm vardır. Ancak her t için bir x çözümü çifti vardır, yani. orijinal sistemin 2*32 = 64 çözümü vardır. Cevap: 64

Çözümlerin bir kısmını ortadan kaldırma yöntemi Aşağıda listelenen tüm koşulları karşılayan x1, x2, ..., x5, y1,y2,..., 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; y5 → x5 =1. Yanıtın, bu eşitlik sisteminin geçerli olduğu tüm farklı x1, x2, ..., x5, y1, y2, ..., y5 kümelerini listelemesi gerekmez. Cevap, bu tür kümelerin sayısını belirtmelidir.

Çözüm. Aşama 1. Denklemlerin sıralı çözümü x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 İlk denklem, 1'e eşit olan çeşitli uygulama işlemlerinin birleşimidir, yani. çıkarımların her biri doğrudur. Çıkarım yalnızca bir durumda yanlıştır, 1  0 olduğunda, diğer tüm durumlarda (0  0, 0  1, 1  1) işlem 1 değerini döndürür. Bunu tablo biçiminde yazalım:

Aşama 1. Denklemlerin sıralı çözümü T.o. x1, x2, x3, x4, x5 için 6 set çözüm elde edildi: (00000), (00001), (00011), (00111), (01111), (11111). Benzer şekilde akıl yürüterek, y1, y2, y3, y4, y5 için aynı çözüm kümesinin olduğu sonucuna varırız. Çünkü bu denklemler bağımsızdır, yani. ortak değişkenleri yoksa, bu denklem sisteminin çözümü (üçüncü denklemi hesaba katmadan) 6 * 6 = 36 çift "X" ve "Y" olacaktır. Üçüncü denklemi ele alalım: y5→ x5 =1 Çözüm çiftlerden oluşur: 0 0 0 1 1 1 Çift bir çözüm değildir: 1 0

Elde edilen çözümleri karşılaştıralım, y5 =1 olduğunda x5=0 uygun değildir. böyle 5 çift var.Sistemin çözüm sayısı: 36-5= 31. Cevap: 31 Kombinatoriğe ihtiyaç vardı!!!

Dinamik programlama yöntemi Kaç tane çeşitli çözümler x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1 mantıksal denklemi vardır, burada x 1, x 2, …, x 6 mantıksal değişkenlerdir? Cevabın, bu eşitliğin geçerli olduğu tüm farklı değişken değer kümelerini listelemesi gerekmez. Cevap olarak bu tür setlerin miktarlarını belirtmeniz gerekiyor.

Çözüm Adımı 1. Durumun Analizi Denklemin solunda ima işlemleri sıralı olarak yazılmıştır, öncelik aynıdır. Tekrar yazalım: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Sonraki her değişken bir öncekine değil, önceki uygulamanın sonucuna bağlıdır!

Adım 2. Deseni ortaya çıkarma İlk çıkarımı ele alalım, X 1 → X 2. Doğruluk tablosu: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Bir 0'dan 2 birim elde ettik ve 1'den 1 elimizde bir 0 ve bir 1 var. Sadece bir tane 0 ve üç tane 1 var, bu ilk işlemin sonucudur.

Adım 2. Bir modeli ortaya çıkarma X 3'ü ilk işlemin sonucuna bağlayarak şunu elde ederiz: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 İki 0'dan – iki 1, her 1'den (3 vardır) bir 0 ve bir 1 (3+3)

Adım 3. T.o formülünün türetilmesi. i değişkenli bir denklem için sıfırların sayısını N i ve birlerin sayısını E i hesaplamak için formüller oluşturabilirsiniz: ,

Adım 4. Tablonun Doldurulması Yukarıdaki formülleri kullanarak sıfır ve birlerin sayısını hesaplayarak, i = 6 için tabloyu soldan sağa dolduralım; tablo bir sonraki sütunun bir öncekinden nasıl oluşturulduğunu gösterir: değişken sayısı 1 2 3 4 5 6 Sıfır sayısı N i 1 1 3 5 11 21 Birlerin sayısı E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Cevap: 43

Mantıksal ifadelerin basitleştirilmesini kullanan yöntem Denklemin kaç farklı çözümü var ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 burada J, K, L, M, N mantıksal değişkenlerdir? Cevabın, bu eşitliğin geçerli olduğu J, K, L, M ve N'nin tüm farklı değer kümelerini listelemesi gerekmez. Cevap olarak bu tür setlerin sayısını belirtmeniz gerekiyor.

Çözüm J → K = ¬ J  K olduğuna dikkat edin. Değişkenlerin değişimini tanıtalım: J → K=A, M  N  L =B Değişikliği dikkate alarak denklemi yeniden yazalım: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Açıkçası, A ve B'nin aynı değerleri için A  B 6. Son çıkarımı düşünün M → J =1 Bu şu durumda mümkündür: M= J=0 M=0, J=1 M=J=1

Çözüm Çünkü A  B, sonra M=J=0 olduğunda 1 + K=0 elde ederiz. Çözüm yok. M=0, J=1 olduğunda 0 + K=0, K=0 elde ederiz ve N ve L herhangi bir 4 çözümdür: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Çözüm 10. M=J=1 olduğunda 0+K=1 *N * L veya K=N*L elde ederiz, 4 çözüm: 11. Toplamın 4+4=8 çözümü vardır Cevap: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Bilgi kaynakları: O.B. Bogomolova, D.Yu. Usenkov. B15: yeni görevler ve yeni çözümler // Bilişim, Sayı. 6, 2012, s. 35 – 39. K.Yu. Polyakov. Mantıksal denklemler // Bilişim, Sayı 14, 2011, s. 30-35. http://ege-go.ru/zadania/grb/b15/, [Elektronik kaynak]. http://kpolyakov.narod.ru/school/ege.htm, [Elektronik kaynak].

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. Keyfi bir denklem sistemi için genel yöntem Bu tür sorunların çözülmesine olanak sağlayan kaba kuvvetten farklıdır.

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. Görünüşe göre bu grafik görüntü bu ağaç

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, o zaman toplam sayısı 36 çözüm var.

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?

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.

Ayrıklık ve birleşimin değişmezliği:
a ˅ b ≡ b ˅ a
a^b ≡ b^a
Ayrışma ve birleşmeye ilişkin dağıtım yasası:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Olumsuzluğun olumsuzlanması:
¬(¬a) ≡ a
Tutarlılık:
a ^ ¬а ≡ yanlış
Özel üçüncü:
a ˅ ¬а ≡ doğru
De Morgan'ın yasaları:
¬(a˅b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b
Basitleştirme:
a ˄ a ≡ a
bir ˅ bir ≡ bir
a ˄ doğru ≡ a
a ˄ yanlış ≡ yanlış
Emilim:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
İmanın değiştirilmesi
a → b ≡ ¬a˅b
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 takip eder:

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

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

(X 1 → X 2) ˄ ¬ X 3 ˅ X 4
(¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
¬ 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.

13579
97531
24678
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; bu durumda.

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 buna göre cevap verilebilir. sağduyu. 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:

A	B	C	F1	F2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Ö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 - 5 tane var Çeşitli seçenekler, onun ifadesine karşılık gelir. 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

Devam ediyoruz geleneksel biçimşeklinde basitleştirmeler yaptıktan sonra sistemi 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. Genel resepsiyon 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, tüm kümelerin oluşturulmaması özelliğiyle bir doğruluk tablosu oluşturmayı anımsatmaktadır. olası değerler değişkenler, ancak yalnızca işlevin 1 (doğru) değerini aldığı değişkenler. Önerilen problemlerde çoğu zaman tam bir karar ağacı oluşturmaya gerek yoktur, çünkü halihazırda İlk aşamaörneğin problem 18'de yapıldığı gibi, sonraki her seviyede yeni dalların ortaya çıkmasına ilişkin bir model 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. Bir bilgisayar, değişken sayısının 20-30 olduğu görevlerle oldukça kolay başa çıkabilir, ancak uzun süre problemler üzerinde düşünmeye başlayacaktır. daha büyük boyut. 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. Bu yüzden zor görev set numarasına göre bir dizi değişken değer elde etmek, bir sayıyı ikili sisteme dönüştürmenin iyi bilinen problemine iner.

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

///

/// çözüm sayısını sayma programı

/// mantıksal denklem (denklem sistemi)

///

/// 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 sayıyı belirtir fonksiyon değişkenleri eğlence. 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 işlevlere aittir yüksek mertebeden– parametreleri yalnızca basit değişkenler değil aynı zamanda işlevler de olabilen F(f) tipi işlevler.

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

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

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

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

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

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

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

(X 1˅ ¬X 2) ˄ (X 3 → X 4)
(X 1 → X 3) ˄ X 2 ˅ X 4
X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 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.
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.
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.
Denklemin kaç çözümü var:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
Denklemin tüm çözümlerini listeleyin:
(a → b) → c = 0
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
Denklemin kaç çözümü var:
((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Sorunlara cevaplar:

b ve c fonksiyonları eşdeğerdir.
Parça b fonksiyonuna karşılık gelir.
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)
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))
Cümle b.
Denklemin 3 çözümü vardır: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

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 bu karar verme yeteneğidir. mantık problemleri. Birleşik Devlet Sınavındaki B15 Görevleri, mantıksal denklem sistemleri içerdikleri için artan karmaşıklığa sahip görevlerdir. seçebilirsiniz çeşitli yollar Mantıksal denklem sistemlerini çözme. 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 elde etmelisiniz. özel çözüm sistemler.

Çö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 bir tane inşa ediyoruz genel tablo Sistemin tüm denklemleri için doğruluk ve gerekli değerleri içeren doğruyu bulun.

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








0	0	1	1	0	1

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 çözüm sayısını belirlemeniz gerekir. yeni sistem. 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 . Yenilik dikkate alındığında değişken denklemşeklinde 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. Yani toplam Muhtemel çözümler bu denklemin 3+9=15.

Bir mantıksal denklem sisteminin çözüm sayısını belirlemenin bir sonraki yolu şudur: ikili ağaç. Hadi düşünelim Bu methodÖrneğin.

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.

Değişkenler	Ağaç	Çözüm sayısı
x 1
x 2
x 3

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:

x 1	x 2	(x1 →x2)

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

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

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.

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:

Çö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:








0	0	1	1	0	1

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

Çö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, ç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 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ğru 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.

Öyleymiş gibi yapalım X 1 – doğruysa, 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):