Bir mantıksal denklem sisteminin çözüm sayısını bulma. mantık

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, burada J, K, L, M, N mantıksal değişkenlerdir?

Çözüm.

(N ∨ ¬N) ifadesi herhangi bir N için doğrudur, bu nedenle

J ∧ ¬K ∧ L ∧ ¬M = 0.

Mantıksal denklemin her iki tarafına da olumsuzlamayı uygulayın ve de Morgan yasasını ¬ (A ∧ B) = ¬ A ∨ ¬ B kullanın. ¬J ∨ K ∨ ¬L ∨ M = 1 elde ederiz.

Bileşen ifadelerinden en az biri 1 ise mantıksal toplam 1'e eşittir. Bu nedenle, ortaya çıkan denklem, denklemde yer alan tüm değerlerin 0'a eşit olduğu durumlar dışında, herhangi bir mantıksal değişken kombinasyonunu karşılar. Her biri. 4 değişkenden biri 1 veya 0'a eşit olabilir, bu nedenle tüm olası kombinasyonlar 2 · 2 · 2 · 2 = 16. Bu nedenle denklemin 16 -1 = 15 çözümü vardır.

Bulunan 15 çözümün, mantıksal değişken N'nin iki olası değerinden herhangi birine karşılık geldiğine dikkat etmek gerekir, bu nedenle orijinal denklemin 30 çözümü vardır.

Cevap: 30

Denklemin kaç farklı çözümü vardır

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

nerede J, K, L, M, N boole değişkenleridir?

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.

A → B = ¬A ∨ B ve ¬ (A ∨ B) = ¬A ∧ ¬B formüllerini kullanırız

İlk alt formülü düşünün:

(J → K) → (M ∧ N ∧ L) = ¬ (¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

İkinci alt formülü düşünün

(J ∧ ¬K) → ¬ (M ∧ N ∧ L) = ¬ (J ∧ ¬K) ∨ ¬ (M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Üçüncü alt formülü düşünün

1) M → J = 1, bu nedenle,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Birleştirelim:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 bu nedenle 4 çözüm vardır.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Birleştirelim:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L Dolayısıyla 4 çözüm vardır.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Cevap: 4 + 4 = 8.

Cevap: 8

Denklemin kaç farklı çözümü vardır

((K ∨ L) → (L ∧ M ∧ N)) = 0

nerede K, L, M, N boole değişkenleridir? Cevap, bu eşitliğin tutulduğu tüm farklı K, L, M ve N değer kümelerini listelemek zorunda değildir. Cevap olarak, bu tür kümelerin sayısını belirtmeniz gerekir.

Çözüm.

İşlemler için daha basit gösterim kullanarak denklemi yeniden yazalım:

((K + L) → (L M N)) = 0

1) "ima" işleminin doğruluk tablosundan (ilk probleme bakınız) bu eşitliğin ancak ve ancak aynı zamanda doğru olduğu sonucu çıkar.

K + L = 1 ve L M N = 0

2) birinci denklemden, K veya L değişkenlerinden en az birinin 1'e (veya her ikisinin birlikte) eşit olduğu sonucu çıkar; bu nedenle, üç durumu düşünün

3) K = 1 ve L = 0 ise, ikinci eşitlik herhangi bir M ve N için geçerlidir; İki boole değişkeninin (00, 01, 10 ve 11) 4 kombinasyonu olduğu için 4 farklı çözümümüz var

4) K = 1 ve L = 1 ise, ikinci eşitlik M · N = 0 için geçerlidir; böyle 3 kombinasyon var (00, 01 ve 10), 3 çözümümüz daha var

5) K = 0 ise, mutlaka L = 1 (ilk denklemden); bu durumda ikinci eşitlik M · N = 0'da sağlanır; böyle 3 kombinasyon var (00, 01 ve 10), 3 çözümümüz daha var

6) toplamda 4+3+3=10 çözüm elde ederiz.

Cevap: 10

Denklemin kaç farklı çözümü vardır

(K ∧ L) ∨ (M ∧ N) = 1

Çözüm.

(K ∧ L) ve (M ∧ N) sırasıyla 01, 11, 10 olduğunda ifade üç durumda doğrudur.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N 1'e eşittir ve aynı anda 1 dışında K ve L keyfidir. Bu nedenle, 3 çözüm vardır.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 çözüm.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 çözüm.

Cevap: 7.

Cevap: 7

Denklemin kaç farklı çözümü vardır

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0

nerede X, Y, Z, P boole değişkenleridir? Cevabın, verilen eşitliğin sahip olduğu tüm farklı değer kümelerini listelemesi gerekmez. Cevap olarak, yalnızca bu tür kümelerin sayısını belirtmeniz gerekir.

Çözüm.

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0 =>

¬ (X ∧ Y ∨ Z) ​​​​∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Mantıksal VEYA yalnızca bir durumda yanlıştır: her iki ifade de yanlış olduğunda.

Buradan,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y=1.

Bu nedenle, denklemin tek bir çözümü vardır.

Cevap 1

Denklemin kaç farklı çözümü vardır

(K ∨ L) ∧ (M ∨ N) = 1

nerede K, L, M, N boole değişkenleridir? Cevabın, bu eşitliğin sahip olduğu tüm farklı K, L, M ve N değer kümelerini listelemesi gerekmez. Cevap olarak, yalnızca bu tür kümelerin sayısını belirtmeniz gerekir.

Çözüm.

Mantıksal VE yalnızca bir durumda doğrudur: tüm ifadeler doğru olduğunda.

K ∨ L = 1, M ∨ N = 1.

Denklemlerin her biri 3 çözüm verir.

Hem A hem de B'nin her biri üç durumda doğru değerler alıyorsa, A ∧ B = 1 denklemini düşünün, o zaman tüm denklemin 9 çözümü vardır.

Bu nedenle cevap 9'dur.

Cevap: 9

Denklemin kaç farklı çözümü vardır

((A → B) ∧ C) ∨ (D ∧ ¬D) = 1,

nerede A, B, C, D boole değişkenleridir?

Cevabın, bu eşitliğin sahip olduğu tüm farklı A, B, C, D değer kümelerini listelemesi gerekmez. Cevap olarak, bu tür setlerin sayısını belirtmeniz gerekir.

Çözüm.

Mantıksal "VEYA", ifadelerden en az biri doğru olduğunda doğrudur.

(D ∧ ¬D) = herhangi bir D için 0.

Buradan,

(A → B) ∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, bu bize her D için 3 çözüm verir.

(D ∧ ¬ D) = 0, bize iki çözüm verir (D = 1 için, D = 0).

Bu nedenle: toplam çözümler 2 * 3 = 6.

Toplamda 6 çözüm var.

Cevap: 6

Denklemin kaç farklı çözümü vardır

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

nerede K, L, M, N boole değişkenleridir? Cevabın, bu eşitliğin sahip olduğu tüm farklı K, L, M ve N değer kümelerini listelemesi gerekmez. Cevap olarak, yalnızca bu tür kümelerin sayısını belirtmeniz gerekir.

Çözüm.

Denklemin her iki tarafına da olumsuzlama uygulayın:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Mantıksal VEYA üç durumda doğrudur.

Seçenek 1.

K ∧ L ∧ M = 1, sonra K, L, M = 1 ve ¬L ∧ M ∧ N = 0. N herhangi bir, yani 2 çözümdür.

Seçenek 2.

¬L ∧ M ∧ N = 1, sonra N, M = 1; L = 0, K herhangi bir, yani 2 çözümdür.

Dolayısıyla cevap 4'tür.

Cevap: 4

A, B ve C, ifadenin doğru olduğu tam sayılardır.

¬ (A = B) ∧ ((A> B) → (B> C)) ∧ ((B> A) → (C> B))).

A = 45 ve C = 43 ise B nedir?

Çözüm.

Bu karmaşık ifadenin üç basit ifadeden oluştuğunu unutmayın.

1) ¬ (A = B); (A> B) → (B> C); (B> A) → (C> B);

2) bu basit ifadeler ∧ (VE, bağlaç) işlemiyle bağlanır, yani aynı anda yürütülmeleri gerekir;

3) ¬ (A = B) = 1'den hemen sonra A B;

4) A> B olduğunu varsayalım, o zaman ikinci koşuldan 1 → (B> C) = 1 elde ederiz; bu ifade ancak ve ancak B> C = 1 ise doğru olabilir;

5) öyleyse elimizde A> B> C var, sadece 44 sayısı bu duruma karşılık geliyor;

6) her ihtimale karşı A 0 → (B> C) = 1 seçeneğini işaretleyin;

bu ifade herhangi bir B için doğrudur; şimdi elde ettiğimiz üçüncü koşula bakıyoruz

bu ifade ancak ve ancak C> B ise doğru olabilir ve burada bir çelişki elde ettik, çünkü C> B> A olan böyle bir B sayısı yoktur.

Cevap: 44.

Cevap: 44

Bir mantık işlevi için bir doğruluk tablosu yapın

X = (A ↔ B) ∨ ¬ (A → (B ∨ C))

A argümanının değerlerinin sütununun 27 sayısının ikili bir kaydı olduğu, B argümanının değerlerinin sütunu 77 sayısıdır, C argümanının değerlerinin sütunu 120 sayısı. Sütundaki sayı, en anlamlı bitten en az anlamlıya (sıfır kümesi dahil) yukarıdan aşağıya doğru yazılır. X fonksiyonunun değerlerinin elde edilen ikili gösterimini ondalık sayı sistemine dönüştürün.

Çözüm.

İşlemlerin daha basit gösterimini kullanarak denklemi yazalım:

1) bu üç değişkenli bir ifadedir, dolayısıyla doğruluk tablosunda satırlar olacaktır; bu nedenle, A, B ve C tablosunun sütunlarını oluşturmak için kullanılan sayıların ikili gösterimi 8 basamaktan oluşmalıdır.

2) 27, 77 ve 120 sayılarını ikili sisteme çeviriyoruz, girişi hemen sayıların başında sıfırlarla 8 haneye tamamlıyoruz

3) Her kombinasyon için X fonksiyonunun değerlerini hemen yazmanız pek olası değildir, bu nedenle ara sonuçları hesaplamak için tabloya ek sütunlar eklemek uygundur (aşağıdaki tabloya bakın)

4) tablonun sütunlarını doldurun:

değer sadece A = B olan satırlarda 1'dir.

B veya C = 1 olan satırlarda değer 1'dir.

değer yalnızca A = 1 ve B + C = 0 olan satırlarda 0'dır.

değer, önceki sütunun tersidir (0, 1 ile değiştirilir ve 1, 0 ile değiştirilir)

sonuç X (son sütun) iki sütunun mantıksal toplamıdır ve

5) cevabı almak için X sütunundaki bitleri yukarıdan aşağıya yazın:

6) bu sayıyı ondalık sisteme çeviriyoruz:

Cevap: 171

(10 (X + 1) · (X + 2)) için doğru olan en büyük X tamsayısı nedir?

Çözüm.

Bir denklem, iki ilişki arasındaki bir uygulama işlemidir:

1) Elbette, burada örnek 2208'deki yöntemin aynısını uygulayabilirsiniz, ancak ikinci dereceden denklemleri çözmeniz gerekecek (istemiyorum ...);

2) Koşul olarak, yalnızca tam sayılarla ilgilendiğimizi unutmayın, bu nedenle orijinal ifadeyi bir şekilde dönüştürmeyi deneyebilir, eşdeğer bir ifade elde edebiliriz (köklerin tam değerleri bizi hiç ilgilendirmiyor!);

3) Eşitsizliği düşünün: hem pozitif hem de negatif sayılar olabileceği açıktır;

4) Etki alanında ifadenin tüm tamsayılar için ve etki alanında - tüm tamsayılar için doğru olduğunu kontrol etmek kolaydır (kafa karıştırmamak için katı olmayan eşitsizlikleri kullanmak daha uygundur ve bunun yerine ve);

5) Bu nedenle, tamsayılar için eşdeğer bir ifadeyle değiştirebilirsiniz.

6) ifadenin doğruluk alanı - iki sonsuz aralığın birleşimi;

7) Şimdi ikinci eşitsizliği ele alalım: hem pozitif hem de negatif sayılar olabileceği açıktır;

8) Bölgede, ifade tüm tamsayılar için doğrudur ve bölgede - tüm tamsayılar için, bu nedenle tamsayılar için eşdeğer bir ifade ile değiştirilebilir.

9) ifadenin doğruluk alanı - kapalı bir aralık;

10) Verilen ifade, alanlar dışında her yerde doğrudur ve;

11) Değerin artık uygun olmadığına dikkat edin, çünkü orada ve yani, ima 0 verir;

12) Koşulu sağlayan 2, (10 (2 + 1) · (2 ​​​​+ 2)) veya 0 → 0 yerine koymak.

Yani cevap 2'dir.

Cevap: 2

İfadenin doğru olduğu en büyük X tamsayısı nedir?

(50 (X + 1) (X + 1))?

Çözüm.

İplik dönüşümünü uygulayalım ve ifadeyi dönüştürelim:

(50 (X + 1) (X + 1)) ⇔ ¬ (X 2> 50) ∨ ((X + 1) 2) ∨ (| X + 1 |).

Mantıksal VEYA, en az bir mantıksal ifade doğru olduğunda doğrudur. Her iki eşitsizliği de çözdükten ve en az birinin sağlandığı en büyük tamsayının 7 olduğunu gördüğümüzü dikkate alarak (şekilde sarı, ikinci eşitsizliğin pozitif bir çözümünü gösterir, mavi - birinci).

Cevap: 7

Mantıksal ifadenin kullanıldığı K, L, M, N değişkenlerinin değerlerini belirtin.

(¬ (M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

YANLIŞ. Cevabı 4 karakterlik bir dize olarak yazın: K, L, M ve N değişkenlerinin değerleri (belirtilen sırada). Yani, örneğin 1101 satırı, K = 1, L = 1, M = 0, N = 1 olduğu gerçeğine karşılık gelir.

Çözüm.

İş 3584'ü çoğaltır.

Cevap: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Çözüm.

Uygulama dönüşümünü uygulayalım:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Denklemin her iki tarafına da olumsuzlama uygulayın:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Hadi dönüştürelim:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Bu nedenle, M = 0, N = 0, şimdi düşünün (¬K ∧ L ∨ M ∧ L):

M = 0, N = 0 olduğu gerçeğinden M ∧ L = 0, sonra ¬K ∧ L = 1, yani K = 0, L = 1 olduğu sonucu çıkar.

Cevap: 0100

Mantıksal ifadenin kullanıldığı K, L, M, N değişkenlerinin değerlerini belirtin.

(¬ (M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

YANLIŞ. Cevabınızı dört karakterlik bir dize olarak yazın: K, L, M ve N değişkenlerinin değerleri (belirtilen sırada). Yani örneğin 1101 satırı K = 1, L = 1, M = 0, N = 1'e karşılık gelir.

Çözüm.

Daha basit işlem gösterimi kullanarak denklemi yazalım ("ifade yanlıştır" koşulu, mantıksal sıfıra eşit olduğu anlamına gelir):

1) koşulun formülasyonundan, ifadenin yalnızca bir değişken kümesi için yanlış olması gerektiği sonucu çıkar.

2) "ima" işleminin doğruluk tablosundan, bu ifadenin yalnızca ve ancak aynı zamanda yanlış olduğu sonucu çıkar.

3) birinci eşitlik (mantıksal çarpım 1'e eşittir), ancak ve ancak ve ancak ve ile sağlanır; buradan aşağıdaki gibidir (mantıksal toplam sıfıra eşittir), bu sadece şurada olabilir; bu nedenle, zaten üç değişken tanımladık

4) ikinci koşuldan, için ve elde ederiz.

Görevi çoğaltır

Cevap: 1000

Mantıksal ifadenin kullanıldığı P, Q, S, T mantıksal değişkenlerinin değerlerini belirtin.

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) yanlış.

Cevabı dört karakterlik bir dize olarak yazın: P, Q, S, T değişkenlerinin değerleri (belirtilen sırada).

Çözüm.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Çıkarımın dönüşümünü uygulayın:

¬Q ∨ S ∨ Т = 0 => S = 0, T = 0.

Cevap: 0100

Mantıksal ifadenin kullanıldığı K, L, M, N değişkenlerinin değerlerini belirtin.

(K → M) ∨ (L ∧ K) ∨ ¬N

YANLIŞ. Cevabınızı dört karakterlik bir dize olarak yazın: K, L, M ve N değişkenlerinin değerleri (belirtilen sırada). Yani örneğin 1101 satırı K = 1, L = 1, M = 0, N = 1'e karşılık gelir.

Çözüm.

Mantıksal "VEYA", ancak ve ancak her iki ifade de yanlışsa yanlıştır.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

İlk ifade için ima dönüşümünü uygulayalım:

¬K ∨ M = 0 => K = 1, M = 0.

İkinci ifadeyi düşünün:

(L ∧ K) ∨ ¬N = 0 (ilk ifadenin sonucuna bakın) => L ∨ ¬N = 0 => L = 0, N = 1.

Cevap: 1001.

Cevap: 1001

Mantıksal ifadenin kullanıldığı K, L, M, N değişkenlerinin değerlerini belirtin.

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

NS. Cevabınızı dört karakterlik bir dize olarak yazın: K, L, M ve N değişkenlerinin değerleri (belirtilen sırada). Yani örneğin 1101 satırı K = 1, L = 1, M = 0, N = 1'e karşılık gelir.

Çözüm.

Mantıksal "VE", ancak ve ancak her iki ifade de doğruysa doğrudur.

1) (K → M) = 1 Çıkarım dönüşümünü uygulayın: ¬K ∨ M = 1

2) (K → ¬M) = 1 Çıkarımın dönüşümünü uygulayın: ¬K ∨ ¬M = 1

Dolayısıyla K = 0 olur.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 K = 0 gerçeğinden K ∨ (M ∧ ¬L ∧ N) = 1 ifadesinin dönüşümünü uygularız.

Mantıksal denklem sistemlerini çözmenin yolları

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

Lesosibirsk Pedagoji Enstitüsü -

Sibirya Federal Üniversitesi, Rusya Şubesi

Tutarlı düşünme, kanıtlarla akıl yürütme, hipotez kurma, olumsuz sonuçları çürütme yeteneği kendiliğinden gelmez, bu beceri mantık bilimi tarafından geliştirilmiştir. Mantık, diğer ifadelerin doğruluğuna veya yanlışlığına dayanarak bazı ifadelerin doğruluğunu veya yanlışlığını belirleme yöntemlerini inceleyen 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, bu mantıksal sorunları çözme yeteneğidir. 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 tablosu oluşturma, ayrıştırma, denklemlerin sıralı çözümü vb.

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

Düşünmek bir denkleme indirgeme yöntemi ... Bu yöntem, mantıksal denklemleri, sağ tarafları doğruluk değerine (yani, 1) eşit olacak şekilde dönüştürmeyi içerir. Bunun için mantıksal olumsuzlama işlemi kullanılır. 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. Ardından ortaya çıkan denklemin dönüşümünü mantık cebiri kanunlarına göre 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 olan tek bir denklemde birleştirebilirsiniz:

İ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.

sonraki yol doğruluk tabloları oluşturmak ... 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 yerine getirildiğini bulabilirsiniz. Yani sistemdeki tüm denklemler için ortak bir doğruluk tablosu oluşturuyoruz ve gerekli değerlere sahip satırı buluyoruz.

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

Sorunun koşullarının yerine getirildiği satır koyu renkle vurgulanmıştı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 vb. düzeltebilirsiniz.

Çözüm 3:İzin vermek A = 0, o zaman:

Elde ettiğimiz ilk denklemden B = 0 ve ikinciden - C = 1. Sistem çö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. 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.

Sistemdeki ilk denklem 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: bu nedenle, için A = 0 ve B = 0 elde ederiz ve A = 1 için B = 1 elde ederiz. Böylece, ilk denklemin A ve B değişkenleri için iki çözümü vardır.

Her seçenek için C değerlerini belirlediğimiz ikinci denklemi çizelim. A = 1 için, ima yanlış olamaz, yani ağacın ikinci dalının çözümü yoktur. NS 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 bilimi sınavında, çoğu zaman bir mantıksal denklem sisteminin çözümlerinin 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şkenlerin değişimi... İlk olarak, mantık cebir yasalarına dayanan 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 sistemin çözüm sayısını belirlemek gerekir. Ardından 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 ( 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 ... 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 ve birinde yanlıştır. Bu nedenle, durum (0; 1), üç olası parametre kombinasyonuna karşılık gelecektir. Durum (1; 1) - orijinal denklemin dokuz olası parametre kombinasyonuna karşılık gelecektir. Bu, bu denklemin 3 + 9 = 15 olası çözümü olduğu anlamına gelir.

Bir mantıksal denklem sisteminin çözüm sayısını belirlemenin bir sonraki yolu, ikili ağaç... Bu yöntemi bir örnekle ele alalım.

Görev:Bir 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 )*…*( 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 sahip olduğumuz ilk denklemdenx 2 = 0 veya x 2 =1.

Ne zaman x 2 gerçekten diğer değişkenlerin de doğru olduğunu anlıyoruz, yani (0; 1;…; 1) kümesi sistemin bir çözümüdür. NSx 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şkenlerin değerleri):

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

Akıl yürütmede ve bir karar ağacı oluşturmada zorluklar olması durumunda, aşağıdakileri 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ı bir doğruluk tablosu derleyelim:

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

Ayrıca, 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, bazı 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. Genel çözümün aynı forma sahip olacağı varsayılabilir, ancak böyle bir yaklaşımın çözüm olabilmesi için varsayımın doğru olduğunun kanıtı gereklidir.

Yukarıdakilerin tümünü özetleyerek, dikkate alınan tüm yöntemlerin 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 görevler / O.B. Bogomolov - 2. baskı. - M.: BİNOM. Bilgi Laboratuvarı, 2006.-- 271 s.: hasta.

2. Polyakov K.Yu. Mantıksal denklem sistemleri / Bilişim öğretmenleri için eğitim-yöntemli gazete: Bilişim No. 14, 2011

Belediye bütçe eğitim kurumu

"Ortaokul numarası 18"

kentsel bölge şehir Salavat, Başkurdistan Cumhuriyeti

Mantıksal denklem sistemleri

bilişimde sınavın görevlerinde

USE görevlerindeki "Mantık Cebirinin Temelleri" bölümü, en zor ve en az çözülmüş olanlardan biri olarak kabul edilir. Bu konudaki görevleri tamamlama ortalama yüzdesi 43,2 ile en düşüktür.

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

Görev 23 en yüksek zorluk seviyesindedir, bu nedenle en düşük tamamlanma yüzdesine sahiptir. Hazırlanan mezunlardan (81-100 puan), tamamlayanların %49,8'i, ortalama hazırlanan (61-80 puan) %13,7'si başa çıkmakta, geri kalan öğrenci grubu bu görevi yerine getirmemektedir.

Bir mantıksal denklem sistemini çözmenin başarısı, mantık yasalarının bilgisine ve sistemi çözmek için yöntemlerin doğru uygulanmasına bağlıdır.

Haritalama yöntemiyle bir mantıksal denklem sisteminin çözümünü düşünün.

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

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (y1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

nerede x1 , x2 ,…, x8, NS1 , NS2 , ..., y8 - boole değişkenleri? 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... Sistemde yer alan tüm denklemler aynı tipte olup, her denklemde dört değişken yer almaktadır. x1 ve y1'i bilerek, ilk denklemi sağlayan tüm olası x2 ve y2 değerlerini bulabiliriz. Benzer şekilde tartışarak, bilinen x2 ve y2'den ikinci denklemi sağlayan x3, y3'ü bulabiliriz. Yani, (x1, y1) çiftini bilerek ve (x2, y2) çiftinin değerini belirleyerek, (x3, y3) çiftini bulacağız ve bu da (x4, y4) çiftine yol açacaktır. ve bunun gibi.

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

Doğruluk şeması:

Doğruluk tablosunun oluşturulması zaman açısından zahmetli ve verimsizdir, bu nedenle ikinci yöntemi kullanıyoruz - mantıksal akıl yürütme. Çarpım, ancak ve ancak her bir faktör 1 ise 1'dir.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

İlk denklemi düşünün. Sıra 0 0, 0 1, 1 1 olduğunda 1'dir, yani (01), (10 için (x1 y1) = 0, sonra çift (x2  y2 ) herhangi bir (00), (01), (10), (11) olabilir ve (x1 y1) = 1 için, yani (00) ve (11) için (x2 y2) = 1 çifti aynı değerler (00) ve (11). İkinci ve üçüncü denklemlerin yanlış olduğu, yani x1 = 1, x2 = 0, y1 = 1, y2 = 0 olan çiftleri bu çözümden hariç tutuyoruz.

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

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

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Çözüm. 1) Denklemler aynı tiptedir, bu nedenle, akıl yürütme yöntemiyle, ilk denklemin tüm olası çiftlerini (x1, y1), (x2, y2) buluruz.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

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

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

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

Her aşamada çift sayısını hesaplamak için bir tablo yapalım.

Son denklemin çözümleri dikkate alındığında x 7  y 7 = 1, çifti (10) hariç tutun. Toplam çözüm sayısını bulun 1 + 7 + 0 + 34 = 42

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

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Çözüm. 1) Denklemler aynı tiptedir, bu nedenle, akıl yürütme yöntemiyle, ilk denklemin tüm olası çiftlerini (x1, x2), (x3, x4) buluruz.

(x1  x2 )  (x3  x4 ) = 1

Dizide 0 (1 0) veren çiftleri çözümden çıkarırız, bunlar (01, 00, 11) ve (10) çiftleridir.

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

Yıl sonunda, üç varsayımdan sadece biri doğru çıktı. Yıl sonunda hangi bölümler kâr etti?

Çözüm. Problem ifadesinden varsayımları mantıksal ifadeler şeklinde yazalım: “B alt bölümü ile kar elde etmek, elde etmek için gerekli bir koşul değildir.

A alt bölümüne göre kar ": F 1 (A, B, C) = A → B

"En az bir B ve C bölümünün kar etmesi, A bölümünün kar etmesi için yeterli değil": F 2 (A, B, C) = (B + C) → A

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

Üç varsayımdan sadece birinin doğru olduğu koşuldan bilinmektedir. Bu, aşağıdaki üç mantıksal ifadeden hangisinin aynı şekilde 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) (AB + 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ılların sonuçlarına göre ikinci varsayım doğru, birinci ve üçüncü varsayım yanlış çıktı.

Sonuç olarak, C bölümü kar alacak ve A ve B bölümleri kar etmeyecek.

Mantıksal denklemleri çözme

Devlet merkezileştirilmiş test metinlerinde, mantıksal bir denklemin kökünü bulmanın önerildiği bir görev (A8) vardır. Bir örnek kullanarak bu tür görevlerin nasıl çözüleceğine bir göz atalı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 hangi X'te bu tabloların son sütunlarındaki değerler çakışacak görelim.

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

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

Elde edilen 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 bağımsız değişken sütunlarını bırakarak yalnızca seçili 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 elde edilen mantıksal denklemi basitleştirmektir.

Daha fazla çalışmayı kolaylaştırmak için önce mantıksal denklemin sağ ve sol taraflarını sadeleştirelim ve olumsuzlukları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 denklemimizde eşittir işaretini 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 belirtin, sonra

X T + X T = X↔ T.

Bu nedenle, bir mantıksal denklemin çözümü için: X = A B = B + A = B → A.

Bir bilgisayarın mantıksal öğeleri. İşlevsel diyagramlar oluşturma

BT'nin gelişmesiyle, matematiksel mantığın bilgisayar teknolojisinin tasarımı ve programlanmasıyla yakından bağlantılı olduğu ortaya çıktı. Mantık cebiri, başlangıçta geliştirmede geniş uygulama buldu röle kontağışemalar. Bilgisayar mühendislerinin dikkatini Boole cebiri kullanarak elektrik devrelerini analiz etme olasılığına çeken ilk temel araştırma, Aralık 1938'de Amerikan Claude Shannon "Röle kontak devrelerinin sembolik analizi" tarafından yayınlandı. Bu makaleden sonra, Boole cebiri kullanılmadan bilgisayar tasarımı tamamlanmış sayılmaz.

mantıksal öğe ayrılma, birleşme ve tersine çevirme gibi mantıksal işlemleri gerçekleştiren bir devredir. Bir okul fizik dersinden aşina olduğunuz elektriksel röle kontak devreleri aracılığıyla mantık elemanlarının uygulanmasını düşünün.

Kişilerin seri bağlantısı

Kontakların paralel bağlantısı

Devrelerin durumunun her türlü kontak durumuna bağımlılık tablosunu oluşturalım. Tanımları 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 mantıksal işlem birleşimine karşılık gelir, çünkü devredeki akım sadece A ve B kontakları aynı anda kapatıldığında ortaya çıkar. Paralel bağlantılı bir devre, yalnızca her iki kontağın açık olduğu anda devrede akım olmadığından, mantıksal ayrılma işlemine karşılık gelir.

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

Bilgisayarların mantık devrelerini oluşturmak için röle kontak elemanlarının kullanımı, düşük güvenilirlik, büyük boyutlar, yüksek güç tüketimi ve düşük hız nedeniyle kendisini haklı çıkarmamıştır. Elektronik cihazların (vakum ve yarı iletken) ortaya çıkışı, saniyede 1 milyon anahtar ve daha yüksek hızlarda mantık elemanları oluşturma olasılığını yarattı. Yarı iletkenlerdeki mantık elemanları, bir elektromanyetik röleye benzer şekilde anahtar modunda çalışır. Temas devreleri için özetlenen tüm teori, yarı iletken elemanlara taşınır. Yarı iletkenlerdeki mantık elemanları, kontakların durumu ile değil, giriş ve çıkışta sinyallerin varlığı ile karakterize edilir.

Temel mantıksal işlemleri uygulayan mantıksal öğeleri göz önünde bulundurun:

fonksiyona karşılık gelen devre:

& F (X, Y, Z)

Bağlaç normali kullanarak problem çözme

ve ayrık-normal formlar

V mantıkla ilgili problemli kitaplar genellikle uygulayan bir işlev yazmanız gereken standart görevleri karşılar. merdiven diyagramı, basitleştirin ve bu fonksiyon için bir doğruluk tablosu oluşturun. Ters problem nasıl çözülür? İsteğe bağlı bir doğruluk tablosu verilir, işlevsel veya röle kontaklı bir devre oluşturmanız gerekir. Bugün bu sorunla ilgileneceğiz.

Mantık cebirinin herhangi bir işlevi, üç işlemin bir kombinasyonu ile temsil edilebilir: birleştirme, ayırma ve ters çevirme. Bunun nasıl yapıldığını görelim. Bunu yapmak için birkaç tanım yazacağız.

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

bağımsız değişkenler ve diğerleri için 0 değeri. Örnek: x 1 x 2 x 3 x 4.

Maxterm, bir dizi değişkenin veya bunların olumsuzlamalarının ayrılmasıyla oluşturulan bir fonksiyondur. Maxterm, olası kümelerden birinde 0, diğerlerinde 1 değerini alır.

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

içinde işlev ayrık 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 DNF olarak adlandırılır ve tüm değişkenlerin veya olumsuzlamalarının bulunduğu her mintermde.

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

Mükemmel birleştirici normal form CNF olarak adlandırılır ve tüm değişkenler veya bunların olumsuzlamaları her maksimum terimde bulunur.

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

Tabloya göre mantıksal fonksiyon kaydı

Herhangi bir mantıksal işlev, SDNF veya SKNF olarak ifade edilebilir. Örnek olarak, tabloda gösterilen f fonksiyonunu ele alalım.

G0, G1, G4, G5, G7 fonksiyonları mintermlerdir (tanıma bakınız). Bu fonksiyonların her biri, üç değişkenin veya bunların tersinin çarpımıdır ve sadece bir durumda 1 değerini alır. Görüldüğü gibi f fonksiyonunun değerinde 1 almak için bir minterme ihtiyaç vardır. Bu nedenle, 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 aşağıdaki 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.

SKNF benzer şekilde oluşturulabilir. Faktör sayısı, fonksiyonun değerlerindeki sıfır 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 biçiminde belirtilen herhangi bir mantıksal işlevi formül biçiminde yazmak mümkündür.

Doğruluk tablosuna göre SDNF oluşturmak için algoritma

Bazı fonksiyonların doğruluk tablosu verilmiştir. SDNF'yi oluşturmak için aşağıdaki adım sırasını gerçekleştirmeniz gerekir:

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

2. Bu tür her bir satıra, tüm argümanların birleşimini veya bunların tersine çevrilmesini (minterms) karşılık olarak koyun. Bu durumda, 0 değerini alan argüman, olumsuzlama ile minterme ve olumsuzlama olmadan 1 değerine dahil edilir.

3. Son olarak, elde edilen tüm mintermlerin bir ayrımını oluşturuyoruz. Minterm sayısı, mantıksal işlevin birim sayısıyla eşleşmelidir.

Doğruluk tablosuna göre SKNF oluşturmak için algoritma

Bazı fonksiyonların doğruluk tablosu verilmiştir. SKNF'yi oluşturmak için aşağıdaki adım sırasını gerçekleştirmeniz gerekir:

1. Fonksiyonun 0 olarak değerlendirildiği tablonun tüm satırlarını seçin.

2. Bu tür her bir satıra, tüm argümanların veya bunların tersine çevrilmelerinin (maxterms) bir ayrımını atayın. Bu durumda, 1 değerini alan argüman, olumsuzlama ile maksimum terime ve olumsuzlama olmadan 1 değerine dahil edilir.

3. Son olarak, elde edilen tüm maxtermlerin birleşimini oluşturuyoruz. Maksimum terimlerin sayısı, mantıksal işlevin sıfırlarının sayısıyla eşleşmelidir.

İki formdan (SDNF veya SKNF) daha az harf içereni tercih etmeyi kabul edersek, doğruluk tablosu fonksiyonunun değerleri arasında daha az sayıda varsa SDNF, daha az sıfır varsa SKNF 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.

Verilen doğruluk tablosunda, fonksiyonun değerinin 0'a eşit olduğu satırları seçelim.

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

Bir doğruluk tablosu derleyerek türetilmiş işlevi kontrol edelim.

İlk ve son doğruluk tablosunu karşılaştırarak, mantıksal işlevin doğru bir şekilde oluşturulduğu sonucuna varabiliriz.

Sorunları çözmek

1. Üç öğretmen Olimpiyat için problemleri seçer. Aralarından seçim yapabileceğiniz birkaç görev var. Her görev için, öğretmenlerin her biri kendi görüşünü ifade eder: kolay (0) veya zor (1) görev. En az iki öğretmen zor olarak işaretlerse bir görev Olimpiyat görevine dahil edilir, ancak üç öğretmen de zor olduğunu düşünüyorsa, böyle bir görev Olimpiyat görevine çok zor olarak dahil edilmez. Görev Olympiad görevine dahilse 1, dahil değilse 0 verecek cihazın mantıksal bir diyagramını yapın.

Gerekli fonksiyonun doğruluk tablosunu oluşturalım. Üç girdi değişkenimiz var (üç öğretmen). Bu nedenle, gerekli fonksiyon üç değişkenli bir fonksiyon olacaktır.

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

SDNF'yi oluşturuyoruz. F (A, B, C) = ABC + ABC + ABC

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

B ve 1F (A, B, C)

2. Bilgisayar biliminin temel kursunda Şehir Olimpiyatı, 2007.Üç katlı bir binanın girişi için bir elektrik devre şeması oluşturun, böylece herhangi bir kattaki bir anahtar evin içindeki ışığı açıp kapatabilir.

Yani, ışığı açıp kapatmamız gereken üç anahtarımız var. Her anahtarın iki durumu vardır: yukarı (0) ve aşağı (1). Üç anahtarın tümü 0 konumundaysa, merdiven ışığının kapalı olduğunu varsayalım. Ardından, üç anahtardan herhangi birini 1 konumuna getirdiğinizde girişteki ışık yanmalıdır. Açıkçası, herhangi bir anahtarı 1 konumuna getirdiğinizde, girişteki ışık sönecektir. Üçüncü anahtar 1 konumuna çevrilirse, girişteki ışık yanacaktır. Bir doğruluk tablosu oluşturuyoruz.

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

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

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

x ↔ y = x y + x y

Bize F 1 (A, B, C) = C → A + B = C + A B olmak üzere üç değişkenli bir mantıksal fonksiyon verildi.

B ve C değişkenlerini aynı anda değiştirin: 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 ediyoruz. Tablonun sekiz satırından sadece ikisinde (2. ve 3.) fonksiyon değerini değiştirmez. Bu satırlarda A değişkeninin değerini tersine değiştirmediğini, ancak B ve C değişkenlerinin değiştirdiğini unutmayın.

SCNF işlevlerini şu satırlar üzerinde 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 istenen cevap 4'tür.

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

Ortaya çıkan tabloyu analiz ediyoruz. Tablonun sekiz satırından sadece 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ğiştirdiğini unutmayın.

Bu satırlar için SDNF işlevleri 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 istenen cevap 2'dir.

Referanslar

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

2. Sholomov L.A. Ayrık mantıksal ve bilgi işlem cihazları teorisinin temelleri. - M.: Bilim. Bölüm ed. fiziksel - mat. yak., 1980 .-- 400 s.

3. Pukhalskiy G.I., Novoseltseva T.Ya. Entegre mikro devrelerde ayrık cihazların tasarımı .: El kitabı. - M.: Radyo ve iletişim, 1990.

Bilgisayar Bilimleri Sınavının A ve B Bölümlerindeki Bazı Problemler Nasıl Çözülür

Ders numarası 3. mantık. Mantıksal fonksiyonlar. Denklemleri Çözme

Çok sayıda USE problemi, ifadelerin mantığına ayrılmıştır. Çoğunu çözmek için, ifade mantığının temel yasalarını, bir ve iki değişkenli mantıksal fonksiyonların doğruluk tablolarını bilmek yeterlidir. İşte önerme mantığının temel yasaları.

1. Ayrışma ve bağlaçların değiştirilebilirliği:
   bir ˅ b ≡ b ˅ bir
   bir ^ b ≡ b ^ bir
2. Ayrılma ve bağlaçla ilgili dağıtım yasası:
   a ˅ (b ^ c) ≡ (a ˅ b) ^ (a ˅ c)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Olumsuzlama olumsuzlaması:
   ¬ (¬a) ≡ bir
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
   bir ˄ doğru ≡ bir
   a ˄ yanlış ≡ yanlış
8. emilim:
   bir ˄ (a ˅ b) ≡ bir
   bir ˅ (a ˄ b) ≡ bir
9. çıkarımı değiştirme
   a → b ≡ ¬a ˅ b
10. Kimlik Değiştirme
    a ≡ b ≡ (a ˄ b) ˅ (¬a ˄ ¬b)

Mantıksal fonksiyon gösterimi

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

Başka bir yol, iyi bilinen oldukça basit işlevleri kullanarak bir formülle bir işlev tanımlamaktır. Herhangi bir mantıksal işlev, yalnızca f i işlevlerini içeren bir formülle ifade edilebiliyorsa, bir işlevler sistemine (f 1, f 2,… f k) tam denir.

Fonksiyonlar sistemi (¬, ˄, ˅) tamamlanmıştır. Yasa 9 ve 10, ima ve özdeşliğin olumsuzlama, birleşme ve ayrılma yoluyla nasıl ifade edildiğinin örnekleridir.

Aslında, iki işlevli bir sistem de tamdır - olumsuzlama ve birleşme veya olumsuzlama ve ayrılma. De Morgan'ın yasalarından, olumsuzlama ve ayrılma yoluyla birleşmeyi ifade etmeye ve buna göre, ayrılmayı olumsuzlama ve birleşme yoluyla ifade etmeye izin veren temsiller takip eder:

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

Paradoksal olarak, yalnızca bir işlevden oluşan bir sistem tamamlanmıştır. İki ikili işlev vardır - içi boş bir sistemi temsil eden Peirce oku ve Schaeffer vuruşu olarak adlandırılan birleşme önleyici ve ayrılma önleyici.

Programlama dillerinin temel işlevleri genellikle özdeşlik, olumsuzlama, bağlaç ve ayrılma içerir. Sınavın görevlerinde bu işlevlerin yanı sıra çıkarımlarla da sıklıkla karşılaşılmaktadır.

Birkaç basit Boole görevine bakalım.

Sorun 15:

Doğruluk tablosunun bir parçası verilir. Yukarıdaki üç işlevden hangisi bu snippet'e 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.

Problemi çözmek için temel fonksiyonların doğruluk tablolarını bilmeniz ve işlemlerin önceliklerini hatırlamanız gerekir. Bir bağlaç (mantıksal çarpma) daha yüksek bir önceliğe sahiptir ve bir ayırmadan (mantıksal toplama) daha önce yürütülür. Hesaplarken, üçü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 kolayca fark edilir.

Sorun 16:

Verilen sayılardan hangisi koşulu sağlar:

(rakamlar, en anlamlı basamakla başlar, azalan sırada gider) → (sayı - çift) ˄ (en küçük anlamlı basamak - çift) ˄ (en anlamlı basamak - tek)

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

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

Koşul 4 sayısı ile karşılanır.

İlk iki sayı, en az anlamlı basamağın tek olması koşulunu sağlamaz. Bağlacın terimlerinden biri yanlışsa, koşulların birleşimi yanlıştır. Üçüncü sayı için en anlamlı basamak koşulu sağlanmaz. Dördüncü sayı için sayının alt ve üst hanelerinde aranan şartlar sağlanır. Bağlantının ilk terimi de doğrudur, çünkü bu durumda olduğu gibi, öncülü yanlışsa ima doğrudur.

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

Birinci tanık: A suçluysa, B daha da suçludur ve C masumdur.

İkinci tanık: İki kişi suçlu. Ve kalanlardan tam olarak biri suçlu ve suçlu ama tam olarak kim olduğunu söyleyemem.

Tanıklığa dayanarak A, B ve C'nin suçluluğu hakkında hangi sonuçlar çıkarılabilir?

Cevap: Tanıklıktan, A ve B'nin suçlu ve C'nin masum olduğu sonucu çıkar.

Çözüm: Elbette cevap sağduyuya dayalı olarak verilebilir. Ancak bunun katı ve resmi olarak nasıl yapılabileceğini görelim.

Yapılacak ilk şey ifadeleri resmileştirmek. Üç boole değişkeni tanıtalım - A, B ve C, bunların her biri (1) ilgili şüpheli suçluysa doğrudur. Daha sonra ilk tanığın ifadesi şu formülle verilir:

A → (B ˄ ¬C)

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

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

Her iki tanığın ifadelerinin de doğru olduğu varsayılır ve ilgili formüllerin birleşimini temsil eder.

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

Özet tanıklık 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 da anlaşılmaktadır. Tanıklığının gerçeğinden, sadece iki olası seçenek çıkıyor - A ve B suçlu ve 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. Birlikte, her iki tanığın ifadeleri, şüphelilerin suçluluğu hakkında net bir cevap verir.

Mantık denklemleri ve denklem sistemleri

F (x 1, x 2,… x n) n değişkenin mantıksal bir fonksiyonu olsun. Mantıksal denklem:

F (x 1, x 2, ... x n) = С,

Sabit C, 1 veya 0 değerine sahiptir.

Bir mantıksal denklemin 0 ila 2 n arasında farklı çözümü olabilir. C 1'e eşitse, çözümler, doğruluk tablosundaki F fonksiyonunun doğru (1) değerini aldığı tüm değişken kümeleridir. 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

Gerçekten, denklem verilsin:

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

Bu durumda, eşdeğer denkleme gidebilirsiniz:

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

Bir k mantıksal denklem sistemi 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

Sistemin çözümü, sistemin tüm denklemlerinin sağlandığı bir değişkenler kümesidir. Mantıksal fonksiyonlar açısından, bir mantıksal denklem sistemine bir çözüm elde etmek için, orijinal F fonksiyonlarının birleşimini temsil eden, mantıksal fonksiyonun Ф 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, o zaman Ф fonksiyonu için sistemin kaç çözümü olduğunu ve çözüm veren kümelerin neler olduğunu söylememize izin veren bir doğruluk tablosu oluşturmak zor değildir.

Bir mantıksal denklem sistemine çözüm bulma konusundaki bazı USE problemlerinde, değişkenlerin sayısı 10'a ulaşır. Ardından, bir doğruluk tablosu oluşturmak neredeyse çözülmez bir problem haline gelir. Sorunu çözmek için farklı bir yaklaşım gereklidir. Rastgele bir denklem sistemi için, bu tür problemleri çözmeye izin veren numaralandırma dışında genel bir yöntem yoktur.

Sınav için önerilen problemlerde, çözüm genellikle denklem sisteminin özelliklerinin dikkate alınmasına dayanmaktadır. Tekrar ediyorum, bir dizi değişken için tüm seçenekleri sıralamak dışında, sorunu çözmenin genel bir yolu yoktur. Çözüm, sistemin özelliklerine göre oluşturulmalıdır. İyi bilinen mantık yasalarını kullanarak bir denklem sisteminin ön basitleştirmesini gerçekleştirmek genellikle yararlıdır. Bu sorunu çözmek için başka bir yararlı teknik aşağıdaki gibidir. Tüm kümelerle ilgilenmiyoruz, sadece Φ fonksiyonunun 1 değerine sahip olduğu kümelerle ilgileniyoruz. Tam bir doğruluk tablosu oluşturmak yerine, onun analogunu - bir ikili karar ağacını - oluşturacağız. Bu ağacın her bir dalı bir çözüme karşılık gelir ve Ф fonksiyonunun 1 değerine sahip olduğu bir kümeyi tanımlar. Karar ağacındaki dalların sayısı, denklem sisteminin çözümlerinin sayısı ile çakışır.

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

ödev 18

İki denklemli bir sistemi 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ı ilk denklemin çözüm sayısını bulalım - x 1, x 2,… x 5. İlk denklem, sırayla, 5 denklemli 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 grafik gösterimi şöyle görünür:

Ağaç, denklemdeki değişken sayısına göre iki seviyeden oluşmaktadır. İlk seviye, ilk değişken X 1'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 X 2 değişkeninin olası değerlerini yansıtır. Denklem bir çıkarım tanımladığı için, X 1'in 1 olduğu dal, o dalda X 2'nin 1 olmasını gerektirir. X 1'in 0 olduğu dal, X 2 değerleri 0 ve 1 olan iki dal oluşturur. Oluşturulan ağaç üç tane tanımlar. X 1 → X 2 uygulamasının 1 değerini aldığı çözümler. Her dalda, denkleme bir çözüm veren karşılık gelen bir dizi değişken değeri yazılır.

Bu kümeler: ((1, 1), (0, 1), (0, 0))

Aşağıdaki denklemi, aşağıdaki çıkarımı X 2 → X 3 ekleyerek karar ağacını oluşturmaya devam ediyoruz. Denklem sistemimizin özelliği, sistemdeki her yeni denklemin ö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 X3 değişkeni de 1 değerine sahip olacaktır. Bu tür dallar için ağaç yapımı devam eder. sonraki seviye, ancak yeni dallar görünmüyor. X 2 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, özgüllüğü verilen her yeni denklemin eklenmesi bir çözüm ekler. . Orijinal ilk denklem:

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

Sistemimizin ikinci denklemi birincisine benzer:

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

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

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

ödev 19

Aşağıdaki koşulların tümünü karşılayan x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 boole değişkenleri için kaç farklı değer kümesi var?

(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 bir modifikasyonudur. Aradaki fark, X ve Y değişkenlerini bağlamak için başka bir denklemin eklenmesidir.

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

ödev 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 denkliği hatırlayarak denklemimizi şu şekilde yazarız:

(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 kimliği anlamına gelir, bu nedenle denklemimiz aşağıdaki denkleme eşdeğerdir:

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

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

ödev 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ı Problem 20'de olduğu gibi, denklemi şu şekilde yeniden yazarak döngüsel çıkarımlardan özdeşliğe geçiyoruz:

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

ödev 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 tanıtarak 10 değişkenden 5 değişkene gidelim:

Y1 = (X1 ≡ X2); Y2 = (X3 ≡X4); Y3 = (X5 ≡X6); Y4 = (X 7 ≡ X 8); 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, sadeleştirmelerden sonra sistemi şu şekilde yazıyoruz:

¬ (Y 1 ≡ Y 2) = 1

¬ (Y 2 ≡ Y 3) = 1

¬ (Y 3 ≡ Y 4) = 1

¬ (Y 4 ≡ Y 5) = 1

Bu sistem için karar ağacı basittir ve değişen değişken değerlere sahip iki daldan oluşur:

Orijinal değişkenler X'e dönersek, Y değişkeninin her değerinin X değişkenlerinin 2 değerine karşılık geldiğine dikkat edin, bu nedenle Y değişkenlerindeki her çözüm, X değişkenlerinde 2 5 çözüm üretir. İki dal 2 * 2 5 çözüm üretir , yani toplam çözüm sayısı 64'tür.

Gördüğünüz gibi, bir denklem sistemini çözmek için her problem kendi yaklaşımını gerektirir. Yaygın bir teknik, denklemleri basitleştirmek için eşdeğer dönüşümler gerçekleştirmektir. Karar ağaçları oluşturmak da yaygın bir tekniktir. Kullanılan yaklaşım, tüm olası değişken değer kümelerinin oluşturulmadığı, ancak yalnızca işlevin 1 (doğru) değerini aldığı bir doğruluk tablosunun oluşturulmasına benzer. Genellikle, önerilen problemlerde, tam bir karar ağacı oluşturmaya gerek yoktur, çünkü zaten ilk aşamada, örneğin yapıldığı gibi, her bir sonraki seviyede yeni dalların görünümünün düzenliliğini kurmak mümkündür. Sorun 18.

Genel olarak, bir mantıksal denklem sistemine çözüm bulma problemleri iyi matematiksel alıştırmalardır.

Sorunu elle çözmek zorsa, denklemleri ve denklem sistemlerini çözmek için uygun bir program yazarak sorunun çözümünü bir bilgisayara emanet edebilirsiniz.

Böyle bir program yazmak zor değil. Böyle bir program, sınavda sunulan tüm görevlerle kolayca başa çıkabilir.

İşin garibi, ancak mantıksal denklem sistemlerine çözüm bulma sorunu bir bilgisayar için de zor, bilgisayarın da sınırları olduğu ortaya çıktı. Bir bilgisayar, değişken sayısının 20-30 olduğu görevlerle oldukça basit bir şekilde başa çıkabilir, ancak daha büyük görevler üzerinde uzun süre düşünmeye başlayacaktır. Buradaki nokta, küme sayısını belirten 2 n fonksiyonunun, artan n ile hızla büyüyen bir üstel olmasıdır. O kadar hızlı ki, sıradan bir kişisel bilgisayar günde 40 değişkenli bir görevin üstesinden gelemez.

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

Mantıksal denklemleri çözmek için bir program yazmak birçok nedenden dolayı yararlıdır, çünkü sadece onun yardımıyla USE test problemlerinin kendi çözümünüzün doğruluğunu kontrol edebilirsiniz. Diğer bir neden de, böyle bir programın, sınavda kategori C problemlerinin gereksinimlerini karşılayan bir programlama problemine mükemmel bir örnek olmasıdır.

Bir program oluşturma fikri basittir - tüm olası değişken değer kümelerinin eksiksiz bir sayımına dayanır. Belirli bir mantıksal denklem veya bir denklem sistemi için değişkenlerin sayısı n bilindiğinden, numaralandırılması gereken küme sayısı - 2 n de bilinir. C# dilinin temel işlevlerini kullanarak - olumsuzlama, ayırma, bağlaç ve özdeşlik, belirli bir değişken kümesi için mantıksal bir denkleme veya denklem sistemine karşılık gelen mantıksal bir işlevin değerini hesaplayan bir program yazmak kolaydır. .

Böyle bir programda set sayısına göre çevrim oluşturmanız, set sayısı ile çevrimin gövdesinde setin kendisini oluşturmanız, bu set üzerindeki fonksiyonun değerini hesaplamanız ve bu değer 1 ise, sonra küme denklemin bir çözümünü verir.

Programın uygulanmasında ortaya çıkan tek zorluk, değişken değerler setini set numarasına göre oluşturma görevi ile ilişkilidir. Bu görevin güzelliği, görünüşte zor olan bu görevin aslında bir kereden fazla ortaya çıkmış basit bir göreve dönüşmesidir. Gerçekten de, sıfırlardan ve birlerden oluşan i sayısına karşılık gelen değişkenlerin değer kümesinin, i sayısının ikili gösterimini temsil ettiğini anlamak yeterlidir. Bu nedenle, bir dizi sayıdan bir dizi değişken değeri elde etmenin zor görevi, bir sayıyı ikili bir sisteme dönüştürmenin iyi bilinen görevine indirgenir.

Sorunumuzu çözen fonksiyon C#'da şöyle görünür:

///

///

/// boole işlevi - yöntem,

/// imzası DF temsilcisi tarafından belirlenen

///

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

/// karar sayısı

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

bool küme = yeni bool [n];

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

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

// Küme sayısı üzerinden tam yineleme

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

// Bir sonraki kümeyi oluşturan - küme,

// i sayısının ikili gösterimi ile verilir

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

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

// Fonksiyonun setteki değerini hesapla

Programı anlamak için programın fikrinin açıklamalarının ve metnindeki yorumların yeterli olduğunu umuyorum. Sadece verilen fonksiyonun başlığının açıklaması üzerinde duracağım. SolveEquations işlevinin iki giriş parametresi vardır. Fun parametresi, çözülecek denklem veya denklem sistemine karşılık gelen mantıksal bir işlevi belirtir. n parametresi eğlence için 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 x giriş parametresinin aritmetik, dize veya mantıksal türde bir değişken olması, okul çocukları için gelenekseldir. Bizim durumumuzda daha güçlü bir yapı kullanılıyor. SolveEquations işlevi, parametreleri yalnızca basit değişkenler değil, aynı zamanda işlevler de olabilen F (f) tipi işlevler olan üst düzey işlevlere atıfta bulunur.

SolveEquations işlevine parametre olarak geçirilebilecek işlevlerin sınıfı şu şekilde tanımlanır:

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

Tüm işlevler, vars dizisi tarafından belirtilen bir dizi boole değişkeni değeri parametresi olarak geçirilen bu sınıfa aittir. Sonuç, bu kümedeki fonksiyonun değerini temsil eden bir Boole değeridir.

Sonuç olarak, birkaç mantıksal denklem sistemini çözmek için SolveEquations işlevinin kullanıldığı bir program vereceğim. SolveEquations işlevi, aşağıdaki ProgramCommon sınıfının bir parçasıdır:

sınıf ProgramıOrtak

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

statik boşluk Ana (dize argümanları)

Console.WriteLine ("İşlevleri ve Kararları Var -" +

SolveEquations (FunAnd, 2));

Console.WriteLine ("İşlevler 51 çözümleri -" +

SolveEquations (Fun51, 5));

Console.WriteLine ("İşlevler 53 çözümleri -" +

SolveEquations (Fun53, 10));

statik bool FunAnd (bool değişkenleri)

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

statik bool Fun51 (bool değişkenleri)

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

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

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

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

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

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 için çözümün sonuçları şöyle görünür:

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

1. Üç işlevden hangisi eşdeğerdir:
   1. (X → Y) ˅ ¬Y
   2. ¬ (X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄ Y
2. Doğruluk tablosunun bir parçası verilmiştir:

Bu pasaj, üç 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. Jüri başkanı, jüri üyelerinden en az birinin desteğiyle oy kullanırsa karar alınır. Aksi halde karar verilmez. Karar verme sürecini resmileştiren mantıksal bir işlev oluşturun.
5. Dört kez yazı tura atıldıktan sonra üç kez tura atılırsa X Y'yi kazanır. X'in kazançlarını açıklayan bir Boole işlevi belirtin.
6. Cümledeki kelimeler birden başlayarak numaralandırılır. Aşağıdaki kurallar karşılanırsa bir cümle iyi biçimlendirilmiş olarak kabul edilir:
   1. Numaralandırmadaki çift bir kelime sesli harfle bitiyorsa, bir sonraki kelime varsa sesli harfle başlamalıdır.
   2. Numaralandırmadaki tek bir kelime ünsüz ile bitiyorsa, bir sonraki kelime varsa ünsüzle başlamalı ve sesli harfle bitmelidir.
      Aşağıdaki cümlelerden hangisi iyi oluşturulmuştur:
   3. Annem Masha'yı sabunla yıkadı.
   4. Lider her zaman bir örnektir.
   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

Görevlere cevaplar:

1. b ve c fonksiyonları eşdeğerdir.
2. Parça, b işlevine karşılık gelir.
3. Jüri başkanı karar için "oy" kullandığında mantıksal değişken P 1 değerini alsın. M 1 ve M 2 değişkenleri jüri üyelerinin görüşlerini temsil eder. Olumlu bir kararın benimsenmesini belirleyen mantıksal işlev aşağıdaki gibi yazılabilir:
   P ˄ (M 1 ˅ M 2)
4. i-inci yazı tura sırasında turalar düştüğünde boole değişkeni P i 1 değerini alsın. X getirisini belirleyen mantıksal fonksiyon aşağıdaki gibi yazılabilir:
   ¬ ((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Teklif 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)