Mantıksal denklem sistemleri. Mantık. Mantık fonksiyonları. Denklemleri çözme

Hizmetin amacı. Çevrimiçi hesap makinesi aşağıdakiler için tasarlanmıştır: mantıksal bir ifade için doğruluk tablosu oluşturma.
Doğruluk tablosu – giriş değişkenlerinin tüm olası kombinasyonlarını ve bunlara karşılık gelen çıkış değerlerini içeren bir tablo.
Doğruluk tablosu 2n satır içerir; burada n giriş değişkenlerinin sayısıdır ve n+m sütunlardır, burada m çıkış değişkenleridir.

Talimatlar. Klavyeden girerken aşağıdaki kuralları kullanın:

Boole ifadesi:

Doğruluk tablosu için ara tabloların türetilmesi
SKNF'nin inşaatı
SDNF'nin inşaatı
Zhegalkin polinomunun inşası
Veitch-Karnaugh haritasının inşası
Boolean Fonksiyonunu Minimize Etme

Örneğin, abc+ab~c+a~bc mantıksal ifadesi şu şekilde girilmelidir: a*b*c+a*b=c+a=b*c
Verileri mantıksal bir diyagram biçiminde girmek için bu hizmeti kullanın.

Mantıksal bir işlev girme kuralları

1. V (ayrılma, OR) sembolü yerine + işaretini kullanın.
2. Mantıksal bir fonksiyondan önce bir fonksiyon tanımının belirtilmesine gerek yoktur. Örneğin, F(x,y)=(x|y)=(x^y) yerine basitçe (x|y)=(x^y) girmeniz gerekir.
3. En yüksek miktar değişkenler 10'a eşittir.

Bilgisayar mantık devrelerinin tasarımı ve analizi, matematiğin özel bir dalı olan mantık cebiri kullanılarak gerçekleştirilir. Mantık cebirinde üç ana mantıksal fonksiyon ayırt edilebilir: “DEĞİL” (olumsuzlama), “VE” (bağlaç), “OR” (ayrılma).
Herhangi bir mantıksal cihaz oluşturmak için, her bir çıkış değişkeninin mevcut giriş değişkenlerine bağımlılığını belirlemek gerekir; bu bağımlılığa anahtarlama fonksiyonu veya mantıksal cebir fonksiyonu denir.
Mantıksal cebir fonksiyonu, değerlerinin tümü 2n verilirse tamamen tanımlanmış olarak adlandırılır; burada n, çıkış değişkenlerinin sayısıdır.
Tüm değerler tanımlanmamışsa fonksiyona kısmen tanımlanmış denir.
Bir cihazın durumu bir mantık cebir fonksiyonu kullanılarak açıklanıyorsa cihaza mantıksal denir.
Mantıksal bir cebir fonksiyonunu temsil etmek için aşağıdaki yöntemler kullanılır:
Cebirsel formda, mantıksal elemanları kullanarak mantıksal bir cihazın devresini oluşturabilirsiniz.


Şekil 1 - Mantıksal cihaz şeması

Mantık cebirinin tüm işlemleri tanımlanmıştır doğruluk tabloları değerler. Doğruluk tablosu bir işlemin sonucunu belirler. herkes mümkün Orijinal ifadelerin x mantıksal değerleri. Uygulama işlemlerinin sonucunu yansıtan seçeneklerin sayısı, mantıksal ifadedeki ifadelerin sayısına bağlı olacaktır. Mantıksal bir ifadedeki ifadelerin sayısı N ise, olası argüman değerlerinin 2 N farklı kombinasyonu olduğundan doğruluk tablosu 2 N satır içerecektir.

NOT Operasyonu - mantıksal olumsuzlama (tersine çevirme)

Basit veya karmaşık bir mantıksal ifade olabilen tek bir argümana mantıksal bir işlem UYGULANMAZ. İşlemin sonucu aşağıdaki DEĞİLDİR:

• orijinal ifade doğruysa, onun olumsuzlanmasının sonucu yanlış olacaktır;
• orijinal ifade yanlışsa, olumsuzlamanın sonucu doğru olacaktır.

Olumsuzlama işlemi için aşağıdaki kurallar kabul edilmez:
A değil, Ā, A değil, ¬A, !A
Olumsuzlama işleminin sonucu aşağıdaki doğruluk tablosuna göre BELİRTİLMEZ:

A	A değil
0	1
1	0

Olumsuzlama işleminin sonucu, orijinal ifade yanlış olduğunda doğrudur ve bunun tersi de geçerlidir.

VEYA işlemi - mantıksal toplama (ayırma, birleştirme)

Mantıksal VEYA işlemi, basit veya karmaşık bir mantıksal ifade olabilen iki ifadeyi birleştirme işlevini yerine getirir. Mantıksal bir işlemin başlangıç ​​noktası olan ifadelere argümanlar denir. OR işleminin sonucu, yalnızca orijinal ifadelerden en az birinin doğru olması durumunda doğru olacak bir ifadedir.
Kullanılan tanımlar: A veya B, A V B, A veya B, A||B.
VEYA işleminin sonucu aşağıdaki doğruluk tablosuyla belirlenir:
VEYA işleminin sonucu, A doğru olduğunda veya B doğru olduğunda veya hem A hem de B doğru olduğunda doğrudur; A ve B argümanları yanlış olduğunda yanlıştır.

VE Operasyonu - mantıksal çarpma (bağlaç)

AND mantıksal işlemi, basit veya karmaşık bir mantıksal ifade olabilen iki ifadenin (argümanların) kesişme işlevini yerine getirir. AND işleminin sonucu, yalnızca her iki orijinal ifadenin de doğru olması durumunda doğru olacak bir ifadedir.
Kullanılan tanımlar: A ve B, A Λ B, A & B, A ve B.
AND işleminin sonucu aşağıdaki doğruluk tablosuyla belirlenir:

A	B	A ve B
0	0	0
0	1	0
1	0	0
1	1	1

AND işleminin sonucu, yalnızca A ve B ifadelerinin her ikisinin de doğru olması ve diğer tüm durumlarda yanlış olması durumunda doğrudur.

“EĞER-SONRA” işlemi - mantıksal sonuç (gösterim)

Bu işlem, birincisi bir koşul, ikincisi ise bu koşulun bir sonucu olan iki basit mantıksal ifadeyi birbirine bağlar.
Kullanılan tanımlar:
A ise B; A, B'yi gerektirir; eğer A ise B; A→B.
Doğruluk tablosu:

A	B	bir → B
0	0	1
0	1	1
1	0	0
1	1	1

Çıkarma işleminin sonucu, yalnızca A öncülü doğru ve B sonucu (sonuç) yanlışsa yanlıştır.

“A ancak ve ancak B ise” işlemi (eşdeğerlik, eşdeğerlik)

Kullanılan gösterim: A ↔ B, A ~ B.
Doğruluk tablosu:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

"Ekleme modulo 2" işlemi (XOR, özel veya kesin ayırma)

Kullanılan gösterim: A XOR B, A ⊕ B.
Doğruluk tablosu:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Eşdeğerlik işleminin sonucu yalnızca A ve B'nin aynı anda hem doğru hem de yanlış olması durumunda doğrudur.

Mantıksal işlemlerin önceliği

• Parantez içindeki eylemler
• İnversiyon
• Bağlaç (&)
• Ayrıklık (V), Özel OR (XOR), toplam modulo 2
• Anlam (→)
• Eşdeğerlik (↔)

Mükemmel ayırıcı normal form

Bir formülün mükemmel ayırıcı normal formu(SDNF), temel bağlaçların ayrılması olan ve aşağıdaki özelliklere sahip olan eşdeğer bir formüldür:

1. Formülün her mantıksal terimi, F(x 1,x 2,...x n) fonksiyonunda yer alan tüm değişkenleri içerir.
2. Formülün tüm mantıksal terimleri farklıdır.
3. Tek bir mantıksal terim bile bir değişkeni ve onun olumsuzlanmasını içermez.
4. Bir formüldeki hiçbir mantıksal terim aynı değişkeni iki kez içermez.

SDNF, doğruluk tabloları veya eşdeğer dönüşümler kullanılarak elde edilebilir.
Her işlev için SDNF ve SCNF, permütasyona kadar benzersiz şekilde tanımlanır.

Mükemmel birleştirici normal form

Bir formülün mükemmel konjonktif normal formu (SCNF) Bu, temel ayrımların bir birleşimi olan ve aşağıdaki özellikleri karşılayan, ona eşdeğer bir formüldür:

1. Tüm temel ayrımlar F(x 1 ,x 2 ,...x n) fonksiyonunda yer alan tüm değişkenleri içerir.
2. Tüm temel ayrımlar farklıdır.
3. Her temel ayrım bir kez bir değişken içerir.
4. Tek bir temel ayrım, bir değişkeni ve onun olumsuzlanmasını içermez.

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

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

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

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

Mantıksal fonksiyonların gösterimi

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

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

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

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

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

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

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

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

Sorun 15:

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

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

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

İşlev numarası 3.

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

Sorun 16:

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

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

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

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

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

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

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

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

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

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

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

Çözüm: Elbette 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. Onun ifadesinin doğruluğundan yalnızca iki şey çıkıyor: olası seçenekler- A ve B suçlu, C masumdur veya A ve C suçlu, B masumdur. İ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ç, sayıya göre iki seviyeden oluşur. denklem değişkenleri. 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şkenleri için her çözüm, Yj değişkenleri için her çö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?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

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

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

Sorun 20

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

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

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

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

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

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

Sorun 21

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

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

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

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

Sorun 22

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

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

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

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

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

Cevap: 64

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

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

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

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

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

(Y 1 ≡ Y 2) = 0

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

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

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

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

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

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

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

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

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

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

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

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

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

Programı uygularken ortaya çıkan tek zorluk, set numarasına göre değişken değerler setinin kendisini oluşturma göreviyle ilgilidir. Bu sorunun güzelliği, görünüşte zor olan bu görevin aslında birçok kez ortaya çıkan basit bir soruna indirgenmesidir. Aslında, i sayısına karşılık gelen sıfırlardan ve birlerden oluşan değişken değerler kümesinin, i sayısının ikili gösterimini temsil ettiğini anlamak yeterlidir. 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 eğlenceli değişkenlerin sayısını belirtir. Sonuç olarak SolveEquations işlevi, mantıksal işlevin çözüm sayısını, yani işlevin doğru olarak değerlendirdiği kümelerin sayısını döndürür.

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

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

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

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

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

sınıf ProgramıOrtak

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

statik void Main(string argümanları)

Console.WriteLine("Ve Fonksiyonlar - " +

SolveEquations(FunAnd, 2));

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

Denklemleri Çöz(Fun51, 5));

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

Denklemleri Çöz(Fun53, 10));

statik bool FunAnd(bool değişkenleri)

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

statik bool Fun51(bool değişkenleri)

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

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

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

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

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

statik bool Fun53(bool değişkenleri)

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

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

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

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

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

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

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

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

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

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

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:

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

Sorunlara cevaplar:

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

Bu materyal, bilgisayar bilimlerinde Birleşik Devlet Sınavının B15 (No. 23, 2015) görevindeki mantıksal denklemleri ve mantıksal denklem sistemlerini çözmeye yönelik yöntemler sunan bir sunum içerir. 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 bir Google hesabı oluşturun ve bu hesaba 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ürme; 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!

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. Sıralı çözüm denklemler 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 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 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. Bir modeli ortaya çıkarmak İlk çıkarım olan X 1 → X 2'yi ele alalım. 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. Rastgele bir denklem sistemi için, bu tür problemlerin çözümüne olanak sağlayan, numaralandırma dışında genel bir yöntem yoktur.

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

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

Sorun 18

İki denklem sistemini karşılayan x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 mantıksal değişkenlerinin kaç farklı değer kümesi vardır?

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

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

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

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

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

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

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

Sistemimizin ikinci denklemi birinciye benzer:

Tek fark denklemde Y değişkenleri kullanılıyor.Bu denklemin de 6 çözümü var. Her değişken çözüm, her değişken çözümle birleştirilebildiğinden toplam çözüm sayısı 36'dır.

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

Sorun 19

Aşağıda listelenen tüm koşulları karşılayan x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 mantıksal değişkenlerinin kaç farklı değer kümesi vardır?

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

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

Sorun 20

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

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

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

Sorun 21

Denklemin kaç çözümü var:

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

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

Sorun 22

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

Ders konusu: Mantık Denklemlerini Çözme

Eğitici – mantıksal denklemleri çözme yöntemlerini incelemek, mantıksal denklemleri çözme becerilerini geliştirmek ve doğruluk tablosunu kullanarak mantıksal bir ifade oluşturmak;

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

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

Ders türü: birleşik ders

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

Dersler sırasında

Temel bilgilerin tekrarı ve güncellenmesi. Sınav Ev ödevi(10 dakika)

Önceki derslerde mantıksal cebirin temel yasalarıyla tanıştık ve bu yasaları mantıksal ifadeleri basitleştirmek için kullanmayı öğrendik.

Mantıksal ifadeleri basitleştirmeye ilişkin ödevimize bir göz atalım:

1. Aşağıdaki kelimelerden hangisi mantıksal koşulu karşılıyor:

(ilk harf ünsüz → ikinci harf ünsüz)٨ (son harf sesli harfi → sondan bir önceki sesli harf)? Bu tür birkaç kelime varsa, bunlardan en küçüğünü belirtin.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Aşağıdaki gösterimi tanıtalım:

A – ilk harf ünsüz

B – ikinci harf ünsüz

S – son harf sesli harfi

D – sondan bir önceki sesli harf

Bir ifade yapalım:

Bir tablo yapalım:

2. Hangi mantıksal ifadenin ifadeye eşdeğer olduğunu belirtin

Orijinal ifadenin ve önerilen seçeneklerin kaydını basitleştirelim:

3. F ifadesinin doğruluk tablosunun bir parçası verildiğinde:

Hangi ifade F ile eşleşir?

Argümanların belirtilen değerleri için bu ifadelerin değerlerini belirleyelim:

Dersin konusuna giriş, yeni materyallerin sunumu (30 dakika)

Mantığın temellerini incelemeye devam ediyoruz ve bugünkü dersimizin konusu “Mantıksal Denklemleri Çözmek”. Bu konuyu inceledikten sonra mantıksal denklemleri çözmenin temel yollarını öğrenecek, mantıksal cebir dilini kullanarak bu denklemleri çözme becerisini ve doğruluk tablosu kullanarak mantıksal bir ifade oluşturma becerisini kazanacaksınız.

1. Bir mantık denklemini çözün

(¬K M) → (¬L M N) =0

Cevabınızı dört karakterden oluşan bir dize olarak yazın: K, L, M ve N değişkenlerinin değerleri (bu sırayla). Yani örneğin 1101 satırı K=1, L=1, M=0, N=1 gerçeğine karşılık gelir.

Çözüm:

İfadeyi dönüştürelim(¬K  M) → (¬L  M  N)

Her iki terim de yanlış olduğunda bir ifade yanlıştır. M =0, N =0, L =1 ise ikinci terim 0'a eşittir. İlk terimde K = 0, çünkü M = 0 ve
.

Cevap: 0100

2. Denklemin kaç çözümü var (cevabınızda yalnızca sayıyı belirtin)?

Çözüm: ifadeyi dönüştürün

(A +B )*(C +D )=1

A +B =1 ve C +D =1

Yöntem 2: doğruluk tablosunun hazırlanması

3 yollu: bir SDNF'nin inşası - bir fonksiyon için mükemmel bir ayırıcı normal form - tam düzenli temel bağlaçların ayrıklığı.

Bağlaçların ayrıklığını elde etmek için orijinal ifadeyi dönüştürelim, parantezleri açalım:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Tam bağlaçlara (tüm argümanların çarpımı) bağlaçları ekleyelim, parantezleri açalım:

Aynı bağlaçları dikkate alalım:

Sonuç olarak 9 bağlaç içeren bir SDNF elde ediyoruz. Bu nedenle, bu fonksiyonun doğruluk tablosu, 2 4 =16 değişken değer kümesinden oluşan 9 satırda 1 değerine sahiptir.

3. Denklemin kaç çözümü var (cevabınızda yalnızca sayıyı belirtin)?

İfadeyi basitleştirelim:

,

3 yollu: SDNF'nin inşası

Aynı bağlaçları dikkate alalım:

Sonuç olarak 5 bağlaç içeren bir SDNF elde ediyoruz. Bu nedenle, bu fonksiyonun doğruluk tablosu, 2 4 = 16 değişken değer kümesinden oluşan 5 satırda 1 değerine sahiptir.

Doğruluk tablosu kullanarak mantıksal bir ifade oluşturmak:

doğruluk tablosunun 1 içeren her satırı için argümanların bir çarpımını oluşturuyoruz ve 0'a eşit değişkenler olumsuzlama ile çarpıma dahil ediliyor ve 1'e eşit değişkenler olumsuzlama olmadan dahil ediliyor. İstenilen F ifadesi, elde edilen ürünlerin toplamından oluşacaktır. Daha sonra mümkünse bu ifadenin basitleştirilmesi gerekir.

Örnek: Bir ifadenin doğruluk tablosu verilmiştir. Mantıksal bir ifade oluşturun.

Çözüm:

3. Ödev (5 dakika)

Denklemi çözün:

Denklemin kaç çözümü var (cevabınızda yalnızca sayıyı belirtin)?

Verilen bir doğruluk tablosunu kullanarak mantıksal bir ifade oluşturun ve

basitleştirin.