Bir mantıksal denklem sisteminin kaç çözümü vardır. mantık
Sistemleri çözmenin yolları mantıksal denklemler
Kırgizova E.V., Nemkova A.E.
Lesosibirsk Pedagoji Enstitüsü -
Sibirya dalı federal üniversite, Rusya
Tutarlı düşünme, kesin olarak tartışma, hipotez kurma, olumsuz sonuçları çürütme yeteneği kendiliğinden 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 belirleme yöntemlerini inceleyen bir bilimdir.
Mantıksal problemleri çözmeden bu bilimin temellerine hakim olmak imkansızdır. Bilgilerini yeni bir durumda uygulama becerilerinin oluşumunu kontrol ederek gerçekleştirilir. Özellikle, çözme yeteneğidir. mantıksal görevler. Sınavdaki B15 görevleri, mantıksal denklem sistemleri içerdiğinden, artan karmaşıklık görevleridir. Mantıksal denklem sistemlerini çözmenin çeşitli yolları vardır. Bu, bir denkleme indirgeme, doğruluk tablosunun oluşturulması, ayrıştırma, denklemlerin sıralı çözümü vb.
Bir görev:Bir mantıksal denklem sistemi çözün:
Düşünmek bir denkleme indirgeme yöntemi . Bu yöntem, mantıksal denklemlerin dönüşümünü içerir, böylece sağ tarafları doğruluk değerine (yani, 1) eşit olur. Bunu yapmak için mantıksal olumsuzlama işlemini kullanın. Ardından, denklemlerde karmaşık mantıksal işlemler varsa, 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 denklemde birleştirmektir. Bundan sonra, mantık cebir yasalarına dayalı olarak ortaya çıkan denklemin dönüşümlerini yapmalı ve sisteme özel bir çözüm bulmalısınız.
1. Çözüm:Tersini ilk denklemin her iki tarafına da uygulayın:
Çıkarımı "VEYA", "DEĞİL" temel işlemleriyle temsil edelim:
Denklemlerin sol tarafları 1'e eşit olduğundan, bunları "VE" işlemini kullanarak orijinal sisteme eşdeğer tek bir denklemde birleştirebilirsiniz:
De Morgan yasasına göre ilk parantez açıyoruz ve sonucu dönüştürüyoruz:
Ortaya çıkan denklemin bir çözümü vardır: bir= 0 , B=0 ve C=1 .
sonraki yol doğruluk tablolarının yapımı . Mantıksal değerler yalnızca iki değere sahip olduğundan, tüm seçenekleri gözden geçirebilir ve aralarında verilen denklem sisteminin karşılandığı olanları bulabilirsiniz. Yani, sistemin tüm denklemleri için ortak bir doğruluk tablosu oluşturuyoruz ve istenen değerlere sahip bir çizgi buluyoruz.
2. Çözüm:Sistem için bir doğruluk tablosu yapalım:
0 |
0 |
1 |
1 |
0 |
1 |
Kalın, sorunun koşullarının karşılandığı satırdır. Yani A =0 , B =0 ve C =1 .
Yol ayrışma . Buradaki fikir, değişkenlerden birinin değerini (0 veya 1'e eşitleyin) sabitlemek ve böylece denklemleri basitleştirmektir. Ardından ikinci değişkenin değerini düzeltebilirsiniz, vb.
Çözüm 3:İzin vermek A = 0, o zaman:
İlk denklemden elde ettiğimiz B =0 ve ikinciden - С=1. Sistem çözümü: A = 0 , B = 0 ve C = 1 .
Yöntemi de kullanabilirsiniz denklemlerin sıralı çözümü , her adımda incelenen kümeye bir değişken ekleyerek. Bunun için denklemleri, değişkenler alfabetik sıraya göre girilecek şekilde dönüştürmek gerekir. Ardından, sırayla değişkenler ekleyerek bir karar ağacı oluşturuyoruz.
Sistemin ilk denklemi sadece A ve B'ye, ikinci denklem A ve C'ye bağlıdır. A Değişkeni 0 ve 1 olmak üzere 2 değer alabilir:
İlk denklemden şu sonucu çıkar: , Öyleyse ne zaman A = 0 B = 0 elde ederiz ve A = 1 için B = 1 elde ederiz. Böylece, birinci 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 çiziyoruz. A=1 için, ima yanlış olamaz, yani ağacın ikinci dalının çözümü yoktur. saat bir= 0 tek çözümü alıyoruz C= 1 :
Böylece sistemin çözümünü elde ettik: A = 0 , B = 0 ve C = 1 .
Bilgisayar biliminde KULLANIM'da, bir mantıksal denklem sisteminin çözümlerinin sayısını, çözümleri kendileri bulmadan belirlemek çok sık gereklidir, 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şkenlerin değişimi. İlk olarak, mantık cebir yasalarına dayanarak denklemlerin her birini mümkün olduğunca basitleştirmek ve ardından denklemlerin karmaşık kısımlarını yeni değişkenlerle değiştirmek ve çözüm sayısını belirlemek gerekir. yeni sistem. Ardından değiştirme işlemine dönün ve bunun için çözüm sayısını belirleyin.
Bir görev:Denklemin kaç çözümü var ( A → B ) + (C → D ) = 1? A, B, C, D boole değişkenleridir.
Çözüm:Yeni değişkenleri tanıtalım: X = A → B ve Y = C → D . dikkate alınarak yeni 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 ve birinde yanlıştır. Bu nedenle, durum (0;1) üç olası parametre kombinasyonuna karşılık gelecektir. Durum (1;1) - orijinal denklemin parametrelerinin dokuz olası kombinasyonuna karşılık gelecektir. Yani tüm olası çözümler verilen denklem 3+9=15.
Bir mantıksal denklem sisteminin çözüm sayısını belirlemenin aşağıdaki yolu şudur: ikili ağaç. Bu yöntemi bir örnekle ele alalım.
Bir görev:Mantıksal denklemler 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 )*…*( x m -1 → x m) = 1.
farz edelim kix 1 doğrudur, o zaman ilk denklemden şunu elde ederizx 2 ayrıca doğru, ikinciden -x 3 =1 ve bu şekilde devam edene kadar x m= 1. Dolayısıyla (1; 1; …; 1) kümesi m birimler sistemin çözümüdür. şimdi izin verx 1 =0, sonra elimizdeki ilk denklemdenx 2 =0 veya x 2 =1.
Ne zaman x 2 true, diğer değişkenlerin de doğru olduğunu elde ederiz, yani (0; 1; ...; 1) kümesi sistemin çözümüdür. saatx 2 =0 anladık x 3 =0 veya x 3 =, vb. Son değişkene devam ederek, denklemin çözümlerinin aşağıdaki değişken kümeleri olduğunu buluyoruz ( m +1 çözüm, her çözümde m değişken değerler):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Bu yaklaşım, ikili bir ağaç oluşturarak iyi bir şekilde gösterilmiştir. Olası çözümlerin sayısı, oluşturulan ağacın farklı dallarının sayısıdır. olduğunu görmek kolaydır m+1.
Değişkenler |
Odun |
Karar sayısı |
x 1 |
||
x2 |
||
x 3 |
||
Akıl yürütmede ve karar ağacı oluşturmada zorluk yaşanması durumunda, aşağıdakileri kullanarak bir çözüm arayabilirsiniz. doğruluk tabloları, bir veya iki denklem için.
Denklem sistemini şu şekilde yeniden yazıyoruz:
Ve bir denklem için ayrı ayrı bir doğruluk tablosu yapalım:
x 1 |
x2 |
(x 1 → x 2) |
İki denklem için bir doğruluk tablosu yapalım:
x 1 |
x2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Ardından, aşağıdaki üç durumda bir denklemin doğru olduğunu görebilirsiniz: (0; 0), (0; 1), (1; 1). İki denklem sistemi dört durumda (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1) doğrudur. Bu durumda, sadece sıfırlardan ve daha fazlasından oluşan bir çözümün olduğu hemen anlaşılır. m son konumdan başlayarak tüm olası yerler dolana kadar bir birimin eklendiği çözümler. Tahmin edilebilir ki, ortak karar aynı forma sahip olacaktır, ancak böyle bir yaklaşımın bir çözüm olması için varsayımın doğru olduğuna dair kanıt gereklidir.
Yukarıdakilerin tümünü özetleyerek, dikkate alınan yöntemlerin hepsinin evrensel olmadığına dikkat ç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 görevler / O.B. Bogomolov - 2. baskı. – M.: BİNOM. Bilgi Laboratuvarı, 2006. - 271 s.: hasta.
2. Polyakov K.Yu. Mantıksal denklem sistemleri / Bilgisayar bilimi öğretmenleri için eğitici ve metodik gazete: Bilişim No. 14, 2011
Bu materyal, Bilişimde Birleşik Devlet Sınavının B15 (No. 23, 2015) görevindeki mantıksal denklemleri ve mantıksal denklem sistemlerini çözmek için yöntemler sunan bir sunum içerir. Bu görevin sınavın görevleri arasında en zorlarından biri olduğu bilinmektedir. Sunum, uzmanlık sınıflarında "Mantık" konulu dersler verirken ve sınavı geçmeye hazırlanırken faydalı olabilir.
İndirmek:
Ön izleme:
Sunumların önizlemesini kullanmak için bir Google hesabı (hesap) oluşturun ve oturum açın: https://accounts.google.com
Slayt başlıkları:
B15 görevinin çözümü (mantıksal denklemler sistemi) Vishnevskaya M.P., MAOU "Gymnasium No. 3" 18 Kasım 2013, Saratov
Görev B15, bilgisayar bilimi sınavında en zor olanlardan biridir !!! Beceriler kontrol edilir: mantıksal değişkenler içeren ifadeleri dönüştürmek için; doğal dilde, belirli bir mantıksal değişken kümesinin doğru olduğu mantıksal değişkenlerin değer kümesini tanımlayın; Verilen koşulları sağlayan ikili kümelerin sayısını sayın. En zoru çünkü Bunun nasıl yapılacağına dair resmi kurallar yoktur, tahminde bulunmak gerekir.
Olmadan ne yapılmaz!
Olmadan ne yapılmaz!
Kurallar birleşimi: A /\ B , A B , AB , А &B, A ve B ayrımı: A \ / B , A + B , A | B , A veya B olumsuzlaması: A , A, değil A eşdeğeri: A B, A B, A B XOR: A B , A xor B
Değişken ikame yöntemi Aşağıdaki koşulların tümünü karşılayan x1, x2, ..., x9, x10 boole değişkenlerinin kaç farklı değer kümesi vardır: ((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 Cevabın, altında x1, x2, …, x9, x10 olan tüm farklı kümeleri listelemesine gerek yoktur. verilen eşitlik sistemi sağlanır. 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 ele alalım: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Açıkçası, =1 sadece değişkenlerden biri 0 ve diğeri 1 ise XOR işlemini birleşim ve ayrılma cinsinden ifade etmek için şu formülü kullanırız: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1
Adım 2. Sistemin analizi .to. tk = x2k-1 ≡ x2k (t1 = x1 x2 ,….), daha sonra her tk değeri, iki çift x2k-1 ve x2k değerine 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) çiftleridir.
Aşama 3. Çözümlerin sayısını sayma. Her t'nin 2 çözümü vardır, t sayısı 5'tir. t değişkenleri için 2 5 = 32 çözüm vardır. Ancak her t, bir çift x çözümüne karşılık gelir, yani. orijinal sistem 2*32 = 64 çözüme sahiptir. Cevap: 64
Kısmi çözüm eleme yöntemi Aşağıdaki koşulların tümünü 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. Cevabın, altında bu eşitlik sisteminin sağlandığı tüm farklı x1, x2, ..., x5, y 1, y2, ..., y5 kümelerini listelemesine gerek yoktur. Cevap olarak, bu tür kümelerin sayısını belirtmelisiniz.
Çö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 imaları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 döndürür. Bunu bir tablo şeklinde yazalım:
Aşama 1. Denklemlerin sıralı çözümü Т.о. х1,х2,х3,х4,х5 için 6 set çözüm alındı: (00000), (00001), (00011), (00111), (01111), (11111). Benzer şekilde tartışarak, y1, y2, y3, y4, y5 için aynı çözüm kümesi olduğu sonucuna varıyoruz. Çünkü bu denklemler bağımsızdır, yani. içlerinde ortak değişken yoktur, o zaman bu denklem sisteminin çözümü (üçüncü denklemi hesaba katmadan) 6 * 6 = 36 çift “x” ve “evet” olacaktır. Üçüncü denklemi ele alalım: y5→ x5 =1 Çiftler çözümdür: 0 0 0 1 1 1 Çift çözüm değildir: 1 0
Elde edilen çözümleri karşılaştıralım, burada y5 =1, x5=0 uymaz. bu tür 5 çift vardır.Sistemin çözüm sayısı: 36-5=31. Cevap: 31 Kombinatorik aldı!!!
Dinamik programlama yöntemi x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1 mantıksal denkleminin kaç farklı çözümü vardır, burada x 1, x 2, ..., x 6 mantıksal değişkenlerdir? Cevabın, bu eşitliğin sahip olduğu tüm farklı değişken değer kümelerini listelemesi gerekmez. Cevap olarak, bu tür setlerin sayısını belirtmeniz gerekir.
Çözüm Adım 1. Durumun analizi Denklemin sol tarafında ima işlemleri sırayla yazılır, öncelik aynıdır. Yeniden yazın: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Not! Sonraki her değişken bir öncekine değil, bir önceki uygulamanın sonucuna bağlıdır!
Adım 2. Modeli ortaya çıkarmak İlk çıkarımı düşünün, 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 bir aldık ve 1'den biz bir 0 ve bir 1 var. Sadece bir 0 ve üç 1, bu ilk işlemin sonucudur.
Adım 2. Bir kalıbı ortaya çıkarmak x 3'ü ilk işlemin sonucuna bağlayarak şunları 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'den, her birinden 1'den (3 tane var) birer 0 ve 1'den (3 + 3)
Adım 3. Formülü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 yapabilirsiniz: ,
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 öncekine göre nasıl oluşturulduğunu gösterir: : değişkenlerin sayısı 1 2 3 4 5 6 Sıfırların sayısı N ben 1 1 3 5 11 21 Birlerin sayısı E ben 1 2*1+1= 3 2 *1+3= 5 11 21 43 Cevap: 43
Mantıksal ifadelerin sadeleş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 tutulduğu tüm farklı J , K, L, M ve N değer kümelerini listelemesi gerekmez. Cevap olarak, bu tür setlerin sayısını belirtmeniz gerekir.
Çözüm J → K = ¬ J K olduğuna dikkat edin Değişkenlerin değişimini sunuyoruz: J → K=A, M N L =B Denklemi, değişimi hesaba katarak yeniden yazarız: (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 durumlarda mümkündür: M= J=0 M=0, J=1 M=J=1
Çözüm A B , sonra M=J=0 ile 1 + K=0 elde ederiz. Çözüm yok. M=0, J=1 ile 0 + K=0, K=0 ve N ve L - herhangi biri, 4 çözüm elde ederiz: ¬ J K = M N L K N L 0 0 0 0 0 1 0 1 0 0 1 bir
Çözüm 10. M=J=1 ile 0+K=1 *N * L veya K=N*L, 4 çözüm elde ederiz: 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üm // Bilişim, No. 6, 2012, s. 35 – 39. K.Yu. Polyakov. Mantıksal Denklemler // Bilişim, No. 14, 2011, s. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ elektronik kaynak] . http://kpolyakov.narod.ru/school/ege.htm, [Elektronik kaynak].
Ders konusu: Mantıksal denklemleri çözme
eğitici - mantıksal denklemlerin nasıl çözüleceğini, mantıksal denklemleri çözme ve doğruluk tablosuna göre mantıksal bir ifade oluşturma beceri ve yeteneklerinin oluşturulması;eğitici - öğrencilerin bilişsel ilgilerinin gelişimi için koşullar yaratmak, hafızanın, dikkatin gelişimini teşvik etmek, mantıksal düşünme;
eğitici : Başkalarının görüşlerini dinleme becerisinin eğitimine katkıda bulunmak, nihai sonuçlara ulaşmak için irade ve azim eğitimi.
Ders türü: birleşik ders
Teçhizat: bilgisayar, multimedya projektörü, sunum 6.
Dersler sırasında
Temel bilgilerin tekrarı ve güncellenmesi. muayene ev ödevi(10 dakika)
Üzerinde önceki dersler mantık cebirinin temel yasalarıyla tanıştık, mantıksal ifadeleri basitleştirmek için bu yasaları nasıl kullanacağımızı öğrendik.
Mantıksal ifadeleri basitleştirmeyle ilgili ödevi kontrol edelim:
1. Aşağıdaki sözcüklerden hangisi mantıksal koşulu sağlar:
(birinci ünsüz → ikinci ünsüz)٨ (son Mektup sesli harf → sondan bir önceki sesli harf)? Bu tür birkaç kelime varsa, en küçüğünü belirtin.
1) ANNA 2) MARIA 3) OLEG 4) STEPAN
Notasyonu tanıtalım:
A bir ünsüzün ilk harfidir
B bir ünsüzün ikinci harfidir
S son sesli harftir
D - sondan bir önceki sesli harf
Bir ifade yapalım:
Bir tablo yapalım:
2. Hangisini belirtin boole ifadesi ifadeye eşdeğerdir
Orijinal ifadenin yazılmasını ve önerilen seçenekleri basitleştirelim:
3. F ifadesinin doğruluk tablosunun bir parçası verilmiştir:
Hangi ifade F'ye karşılık gelir?için bu ifadelerin değerlerini belirleyelim. belirtilen değerler argümanlar:
Ders konusuna aşinalık, yeni materyallerin sunumu (30 dakika)
Mantığın temellerini ve bugünkü "Mantıksal denklemleri çözme" dersimizin konusunu incelemeye devam ediyoruz. okuduktan bu konu, mantıksal denklemleri çözmenin temel yollarını öğrenecek, mantık cebirinin dilini kullanarak bu denklemleri çözme becerisini ve doğruluk tablosu üzerinde mantıksal bir ifade oluşturma becerisini kazanacaksınız.
1. Mantıksal denklemi çözün
(¬K M) → (¬L M N)=0
Cevabınızı dört karakterlik 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'e karşılık gelir.
Çözüm:
ifadeyi dönüştürelim(¬K M) → (¬L M N)
Her iki terim de yanlış olduğunda ifade yanlıştır. M=0, N=0, L=1 ise ikinci terim 0'a eşittir. İlk terimde, M = 0 olduğundan K = 0 ve
.
Cevap: 0100
2. Denklemin kaç çözümü var (cevabınızda sadece sayıyı belirtiniz)?
Çö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 tablosu derleme
3 yol: SDNF'nin yapımı - bir işlev için mükemmel bir ayırıcı normal biçim - tam düzenli temel bağlaçların bir ayrımı.Orijinal ifadeyi dönüştürelim, bağlaçların ayrılmasını elde etmek için parantezleri açalım:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Bağlaçları tamamlamak için bağlaçları tamamlayalım (tüm argümanların ürünü), parantezleri açalım:
Aynı bağlaçları düşünün:
Sonuç olarak, 9 bağlaç içeren bir SDNF elde ederiz. Bu nedenle, bu fonksiyonun doğruluk tablosu 2 4 =16 değişken değer kümesinden 9 satırda 1 değerine sahiptir.
3. Denklemin kaç çözümü var (cevabınızda sadece sayıyı belirtiniz)?
İfadeyi sadeleştirelim:
,
3 yol: SDNF'nin yapımı
Aynı bağlaçları düşünün:
Sonuç olarak, 5 bağlaç içeren bir SDNF elde ederiz. 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 tablosuna göre mantıksal bir ifade oluşturma:
1 içeren doğruluk tablosunun her satırı için, argümanların çarpımını oluştururuz ve 0'a eşit olan değişkenler, olumsuzlamalı ürüne dahil edilir ve 1'e eşit değişkenler - olumsuzlama olmadan. İstenen F ifadesi, elde edilen ürünlerin toplamından oluşacaktır. Daha sonra mümkünse bu ifade sadeleştirilmelidir.
Örnek: Bir ifadenin doğruluk tablosu verilmiştir. Mantıksal bir ifade oluşturun.
Çözüm:3. Ödev (5 dakika)
Denklemi çözün:
Denklemin kaç çözümü var (sadece sayıyı cevaplayın)?
Verilen doğruluk tablosuna göre mantıklı bir ifade yapınız ve
basitleştirin.
Mantıksal denklem sistemlerini çözmenin çeşitli yolları vardır. Bu, bir denkleme indirgeme, doğruluk tablosunun oluşturulması ve ayrıştırmadır.
Bir görev: Bir mantıksal denklem sistemi çözün:
Düşünmek bir denkleme indirgeme yöntemi . Bu yöntem, mantıksal denklemlerin dönüşümünü içerir, böylece sağ tarafları doğruluk değerine (yani, 1) eşit olur. Bunu yapmak için mantıksal olumsuzlama işlemini kullanın. Ardından, denklemlerde karmaşık mantıksal işlemler varsa, 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 denklemde birleştirmektir. Bundan sonra, mantık cebir yasalarına dayalı olarak ortaya çıkan denklemin dönüşümlerini yapmalı ve sisteme özel bir çözüm bulmalısınız.
1. Çözüm: Tersini ilk denklemin her iki tarafına da uygulayın:
Çıkarımı "VEYA", "DEĞİL" temel işlemleriyle temsil edelim:
Denklemlerin sol tarafları 1'e eşit olduğundan, bunları "VE" işlemini kullanarak orijinal sisteme eşdeğer tek bir denklemde birleştirebilirsiniz:
De Morgan yasasına göre ilk parantez açıyoruz ve sonucu dönüştürüyoruz:
Ortaya çıkan denklemin bir çözümü vardır: A=0, B=0 ve C=1.
sonraki yol doğruluk tablolarının yapımı . Mantıksal değerler yalnızca iki değere sahip olduğundan, tüm seçenekleri gözden geçirebilir ve aralarında verilen denklem sisteminin karşılandığı olanları bulabilirsiniz. Yani, sistemin tüm denklemleri için ortak bir doğruluk tablosu oluşturuyoruz ve istenen değerlere sahip bir çizgi buluyoruz.
2. Çözüm: Sistem için bir doğruluk tablosu yapalım:
0 |
0 |
1 |
1 |
0 |
1 |
Kalın, sorunun koşullarının karşılandığı satırdır. Yani A=0, B=0 ve C=1.
Yol ayrışma . Buradaki fikir, değişkenlerden birinin değerini (0 veya 1'e eşitleyin) sabitlemek ve böylece denklemleri basitleştirmektir. Ardından ikinci değişkenin değerini düzeltebilirsiniz, vb.
Çözüm 3: A = 0 olsun, o zaman:
İlk denklemden B = 0 ve ikincisinden - С = 1 alıyoruz. Sistem çözümü: A = 0, B = 0 ve C = 1.
Bilgisayar biliminde KULLANIM'da, bir mantıksal denklem sisteminin çözümlerinin sayısını, çözümleri kendileri bulmadan belirlemek çok sık gereklidir, 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şkenlerin değişimi. İlk olarak, mantık cebir yasalarına dayanarak denklemlerin her birini mümkün olduğunca basitleştirmek ve ardından denklemlerin karmaşık kısımlarını yeni değişkenlerle değiştirmek ve yeni sisteme çözüm sayısını belirlemek gerekir. Ardından değiştirme işlemine dönün ve bunun için çözüm sayısını belirleyin.
Bir görev:(A → B ) + (C → D ) = 1 denkleminin kaç çözümü vardır? A, B, C, D boole değişkenleridir.
Çözüm: Yeni değişkenleri tanıtalım: X = A → B ve Y = C → D . Yeni değişkenler dikkate alınarak denklem X + Y = 1 şeklinde yazılacaktır.
Ayrım üç durumda doğrudur: (0;1), (1;0) ve (1;1), X ve Y bir ima iken, yani üç durumda doğru ve birinde yanlış. Bu nedenle, durum (0;1) üç olası parametre kombinasyonuna karşılık gelecektir. Durum (1;1) - orijinal denklemin parametrelerinin dokuz olası kombinasyonuna karşılık gelecektir. Dolayısıyla, bu denklemin 3+9=15 olası çözümü vardır.
Bir mantıksal denklem sisteminin çözüm sayısını belirlemenin aşağıdaki yolu şudur: ikili ağaç. Bu yöntemi bir örnekle ele alalım.
Bir görev: Mantıksal denklemler 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 )*…*(x m -1 → x m) = 1.
farz edelim ki x 1 doğrudur, o zaman ilk denklemden şunu elde ederiz x 2 ayrıca doğru, ikinciden - x 3 =1 ve bu şekilde devam edene kadar x m= 1. Bu, m birimlik (1; 1; …; 1) kümesinin sistemin çözümü olduğu anlamına gelir. şimdi izin ver x 1 =0, sonra elimizdeki ilk denklemden x 2 =0 veya x 2 =1.
Ne zaman x 2 true, diğer değişkenlerin de doğru olduğunu elde ederiz, yani (0; 1; ...; 1) kümesi sistemin çözümüdür. saat x 2 =0 anladık x 3 =0 veya x 3 =, vb. Son değişkene devam ederek, denklemin çözümlerinin aşağıdaki değişken kümeleri olduğunu elde ederiz (m + 1 çözüm, her çözümde m değişken değeri vardır):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Bu yaklaşım, ikili bir ağaç oluşturarak iyi bir şekilde gösterilmiştir. Olası çözümlerin sayısı, oluşturulan ağacın farklı dallarının sayısıdır. m + 1'e eşit olduğunu görmek kolaydır.
Odun |
Karar sayısı |
|
x 1 |
||
x2 |
||
x 3 |
||
… |
Akıl yürütmede zorluk olması durumunda niyah ve inşaat deçözüm kükremesi, ile bir çözüm arayabilirsiniz kullanarak doğruluk tabloları, bir veya iki denklem için.
Denklem sistemini şu şekilde yeniden yazıyoruz:
Ve bir denklem için ayrı ayrı bir doğruluk tablosu yapalım:
x 1 |
x2 |
(x 1 → x 2) |
İki denklem için bir doğruluk tablosu yapalım:
x 1 |
x2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |