Absorpsiyon yasaları ve dışlamanın yapıştırılması. Mantığın absorpsiyon cebiri kanunları

"Eski" elektronik bilgisayarlara dayanan modern bilgisayarlar, temel çalışma ilkeleri olarak belirli varsayımlara dayanmaktadır. Bunlara mantık cebirinin yasaları denir. İlk kez, böyle bir disiplin (elbette modern haliyle olduğu kadar ayrıntılı olarak değil) eski Yunan bilim adamı Aristoteles tarafından tanımlandı.

İçinde önermeler hesabının çalışıldığı ayrı bir matematik dalını temsil eden mantığın cebiri, bir dizi iyi tanımlanmış sonuç ve sonuçlara sahiptir.

Konuyu daha iyi anlamak için, gelecekte mantık cebiri yasalarını öğrenmeye yardımcı olacak kavramları analiz edeceğiz.

Belki de incelenen disiplindeki ana terim bir ifadedir. Bu, aynı anda hem yanlış hem de doğru olamayacak bir ifadedir. Her zaman bu özelliklerden yalnızca birine sahiptir. Aynı zamanda, doğruya 1, yanlışa 0 değeri vermek ve ifadenin kendisine bir tür A, B, C demek geleneksel olarak kabul edilir. Diğer bir deyişle, A=1 formülü, A ifadesinin şu anlama gelir: doğru. İfadeler çeşitli şekillerde işlenebilir. Bunlarla gerçekleştirilebilecek eylemleri kısaca ele alalım. Ayrıca, mantığın cebir yasalarına bu kurallar bilinmeden hakim olunamayacağına da dikkat edin.

1. Ayrılık iki ifade - "veya" işleminin sonucu. Ya yanlış ya da doğru olabilir. "v" karakteri kullanılmıştır.

2. Bağlaç.İki önermeyle yapılan böyle bir eylemin sonucu, ancak her iki orijinal önerme de doğruysa yeni bir sonuç olacaktır. İşlemde "ve", "^" simgesi kullanılır.

3. Sonuç."A ise B" işlemi. Sonuç, yalnızca A doğru ve B yanlışsa yanlış olan bir ifadedir. "->" simgesi kullanılır.

4. Denklik.İşlem "A ancak ve ancak B ne zaman". Bu ifade, her iki değişken de aynı değere sahipse doğrudur. Sembol "<->».

İma etmeye yakın bir takım operasyonlar da vardır ancak bunlar bu yazıda ele alınmayacaktır.

Şimdi mantık cebirinin temel yasalarına daha yakından bakalım:

1. Değişmeli veya değişmeli, birleştirme veya ayırma işlemlerinde mantıksal terimlerin yerlerinin değiştirilmesinin sonucu etkilemediğini belirtir.

2. Birleştirici veya birleştirici. Bu yasaya göre, birleştirme veya ayırma işlemlerinde değişkenler gruplar halinde birleştirilebilir.

3. Dağıtım veya dağıtım. Kanunun özü, denklemlerdeki aynı değişkenlerin mantık değiştirilmeden parantez içinden alınabilmesidir.

4. De Morgan yasası (ters çevirme veya olumsuzlama). Bağlaç işleminin olumsuzlanması, orijinal değişkenlerin olumsuzlanmasının ayrışmasına eşdeğerdir. Ayrılmanın olumsuzlanması, sırayla, aynı değişkenlerin olumsuzlanmasının birleşimine eşittir.

5. Çift olumsuzlama. Belirli bir ifadenin iki kez olumsuzlanması, orijinal ifadenin üç kez olumsuzlanmasıyla sonuçlanır.

6. İdempotans yasası mantıksal toplama için şuna benzer: x v x v x v x = x; çarpma için: x^x^x^=x.

7. Çelişmezlik yasası diyor ki: iki ifade, eğer çelişkiliyseler, aynı anda doğru olamazlar.

8. Üçüncünün hariç tutulması yasası. Birbirine zıt iki ifadeden biri daima doğrudur, diğeri yanlıştır, üçüncüsü verilmez.

9. Absorpsiyon yasası mantıksal toplama için şu şekilde yazılabilir: x v (x ^ y) = x, çarpma için: x ^ (x v y) = x.

10. Yapıştırma yasası. İki bitişik bağlaç, daha düşük dereceli bir birleşim oluşturmak için birbirine yapışabilir. Bu durumda, orijinal bağlaçların yapıştırıldığı değişken kaybolur. Mantıksal toplama örneği:

(x^y) v (-x^y)=y.

Mantık cebirinin yalnızca en çok kullanılan yasalarını ele aldık, ki bu aslında çok daha fazla olabilir, çünkü genellikle mantıksal denklemler uzun ve süslü bir biçim alır ve bu, bir dizi benzer yasa uygulanarak azaltılabilir.

Kural olarak, sonuçları sayma ve tanımlama kolaylığı için özel tablolar kullanılır. Tablosu bir ızgara dikdörtgenin genel yapısına sahip olan mantık cebirinin mevcut tüm yasaları, her değişkeni ayrı bir hücreye dağıtarak boyanır. Denklem ne kadar büyükse, tabloları kullanmak o kadar kolay olur.

Ayrık Matematik: Matematiksel Mantık

Ders 8

Boolean fonksiyonların minimizasyonu. Quine-McCluskey Yöntemi

Boole Cebir Kanunları

Matematiksel mantıkta, mantıksal ifadelerin özdeş dönüşümlerine izin veren mantıksal çarpma, mantıksal toplama ve olumsuzlama ( ,+, - ) işlemlerini içeren özel bir cebir olan Boole cebri tanımlanır. Bu yasalar şunları içerir:

iktidarsızlık yasası (aynılık)

değişme yasası

bir  b = b bir

ilişkilendirme yasası

bir + (b + c) = (bir + b) + c

a  (b  c) = (a  b)  c

dağıtım yasaları

Bağlantının ayrılmaya göre dağılımı

A  (b + c) = a  b + a  c

Bağlantıya göre ayrışmanın dağılımı

A + b  c = (a + b)  (a + c)

Çift Negatif Hukuk

De Morgan'ın yasaları

Absorpsiyon yasaları

bir + bir  b = bir

bir  (a + b) = bir

0 ve 1 mantıksal sabitleriyle eylemleri tanımlayan yasalar

bir + 0 = bir

 0 = 0

bir + 1 = 1

bir  1 = bir

1 = 0

Yukarıda tartışılan tüm yasaların meşruiyeti, örneğin doğruluk tabloları kullanılarak kolayca kanıtlanabilir.
Ek yasalar

Boole cebirinin ek yasaları, temel yasaların sonuçlarıdır ve mantıksal fonksiyonların yazılmasını basitleştirmede çok faydalıdır.
bağlama kanunu

Bu kimliğin kanıtı, birinci dağılım yasası kullanılarak gerçekleştirilir:

Bu kimliğin kanıtı, ikinci dağıtım yasası kullanılarak gerçekleştirilir:

Blake-Poretsky yasası

Eylem yasalarını mantıksal sabitler, yetersizlik ve yapıştırma ile uygulayarak, bu özdeşlik şu şekilde kanıtlanabilir:

Mantıksal bir ifadenin evrişim yasası

Bu kimlik, mantıksal sabitlerle çalışma, dağılma, yetersizlik ve yapıştırma yasalarını art arda kullanarak kanıtlanabilir:

Mantık İşlevlerini Basitleştirme

Fonksiyonların normal gösterim biçimleri için, bir fonksiyonun karmaşıklığı kavramı, böyle bir gösterimdeki birincil terimlerin sayısı olarak tanımlanır. Bir fonksiyonun karmaşıklığını azaltmak için normal form dönüşümlerine denir. basitleştirme . Mantıksal fonksiyonları basitleştirmek için mantık cebirinin tüm kanunları kullanılır.

Görevler.

Aşağıdaki işlevlerle SDNF'yi basitleştirin:

1. (a b)  c

2. (a b)  c

Fonksiyonu mükemmel bir ayırıcı biçimde temsil ediyoruz ve mantığın cebir yasalarını kullanarak basitleştiriyoruz:

SDNF =

Daha fazla basitleştirme mümkün değildir.

Fonksiyonu mükemmel bir ayırıcı biçimde temsil ediyoruz ve mantığın cebir yasalarını kullanarak basitleştiriyoruz:

SDNF =
5.

Fonksiyonu mükemmel bir ayırıcı biçimde temsil ediyoruz ve mantığın cebir yasalarını kullanarak basitleştiriyoruz:

Quine-McCluskey Yöntemi

Mantıksal fonksiyonların minimizasyonu, dört adımdan oluşan Quine-McClussky yöntemi kullanılarak gerçekleştirilebilir:

Fonksiyonun üzerinde doğru olduğu kümeleri (bileşenleri) ikili eşdeğerler biçiminde gösterelim.
İkili eşdeğerleri katmanlara göre (ikili eşdeğer birimlerin sayısına göre) ve komşu katmanlarda yapıştırıcı (ilgili bileşenlere yapıştırma kuralını uygulayın) kümelerine göre düzenleriz, mümkün olduğunca maksimum aralıkları elde ederiz; yapıştırmaya katılan her seti işaretliyoruz. Yalnızca bu kümeler veya aralıklar birbirine yapıştırılır, aralarındaki fark yalnızca bir basamak değerindedir: 001 ve 000, 001- ve 101-, vb.
Sütunları fonksiyonun ikili doğruluk kümelerine karşılık gelen ve satırları maksimum aralıklara karşılık gelen bir Quine tablosu oluşturalım. i'nci küme j'inci aralık tarafından kapsanıyorsa, karşılık gelen satır ve sütunun kesiştiği noktada 1'i ayarlayın, aksi takdirde 0'ı ayarlayın veya hiçbir şey ayarlamayın.
Quine tablosunun, fonksiyonun doğru olduğu tüm kümeleri içeren (kapsayan) minimum sayıda maksimum aralıktan oluşan minimum örtüsünü buluyoruz.

Demetlerde (1, 3, 5, 7, 11, 13, 15) doğru olan bir F1 fonksiyonunu ele alalım. Bu fonksiyonun mükemmel ayrık normal formu şöyledir:

Gerçek kümelerin ikili eşdeğerleri aşağıdaki gibidir:

1	0001
3	0011
5	0101
7	0111
11	1011
13	1101
15	1111

İkili setleri katmanlara göre düzenleyelim ve mümkün olduğu sürece yapıştırma işlemini gerçekleştirelim.

0001  	00-1 	0-1
0011  	0-01 	--11
0101  	-011 	-1-1
0111   	0-11  
1101  	-101 
1011  	01-1  
1111   	11-1 
	-111  
	1-11 

Sonra bir Quine tablosu oluşturuyoruz:

	0001	0011	0101	0111	1011	1101	1111
0--1	1	1	1	1
--11		1		1	1	1	1
-1-1			1	1		1	1

Tablomuzda 0001 ve 1011 kümeleri mümkün olan tek şekilde kapsanmaktadır, bu nedenle bunları kapsayan minimum aralıklara denir. zorunlu ve biçim kaplama çekirdeği, çünkü herhangi bir kapsama dahil edilmelidir. Tabloda karşılık gelen birimlerin altı çizilmiştir, (0- -1, -11) aralıkları sadece kapsamın çekirdeğini oluşturmaz, aynı zamanda tüm Quine tablosunu da kapsar.
Böylece, incelenen fonksiyonun minimum formunu şu şekilde elde ettik:

MDNF = (0 - - 1, - - 1 1) =

Birkaç örneğe bakalım.
Görevler.

1. MDNF işlevlerini bulunf1 =

x1 x2 x3 x4
0 0 0 0	0
0 0 0 1	1
0 0 1 0	1
0 0 1 1	1
0 1 0 0	1
0 1 0 1	0
0 1 1 0	0
0 1 1 1	1
1 0 0 0	0
1 0 0 1	1
1 0 1 0	1
1 0 1 1	1
1 1 0 0	0
1 1 0 1	1
1 1 1 0	0
1 1 1 1	1

İncelenen fonksiyonun mükemmel DNF'si şu şekildedir:

0001 	00-1 	-0-1
0010 	-001 	-01-
0100	001- 	--11
0011 	-010 	1-1
1010 	0-11 
1001 	-011 
0111 	101- 
1011 	10-1 
1101 	1-01 
1111 	-111 
	1-11 
	11-1 

İlk sütun, herhangi bir yapıştırmaya katılmayan bir küme içerir - bu, 0100 maksimum aralığının kendisidir.Üçüncü sütunda, buna dört maksimum aralık daha eklenir: (-0-1, -01-, --11, 1--1 ).

Bir Quine tablosu oluşturuyoruz:

	0001	0010	0100	0011	1010	1001	0111	1011	1101	1111
0100			1
-0-1	1					1		1	1
-01-		1		1	1			1
--11				1			1	1		1
1--1						1		1	1	1

Zorunlu aralıkları içerecek olan kapsamın özünü tanımlayalım:

(0100, -0-1, -01-, --11). Bu durumda, kapsama çekirdeği tüm tabloyu bir bütün olarak kapsar.

Minimal ayrık normal form f1 şu forma sahiptir:

2. MDNF işlevlerini bulun f 2( x 1, x 2, x 3), 0,2,3,6 ve 7 kümelerinde tek değerler alır.

için bir doğruluk tablosu oluşturalım. f2

x1 x2 x3	F2
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	1
1 0 0	0
1 0 1	0
1 1 0	1
1 1 1	1

SDNF =
İkili kümeleri katmanlara göre düzenleyelim ve yapıştırma işlemini gerçekleştirelim:

000 	0-0 	--0
010 	-00 
100 	-10 
110 	1-0 
111 	11-

Yapıştırma sonucunda sadece iki maksimum aralığımız oldu: (11-, --0). Bir Quine tablosu oluşturmadan, minimal bir kapsam oluşturdukları açıktır, çünkü bu aralıklardan herhangi birinin silinmesi f2(x1, x2, x3) fonksiyonunun üzerinde bulunduğu kümelerin kaybına yol açacaktır. ) doğru. MDNF = x1 x2 +x3.

EDEBİYAT

Guseva A.I. Bilgisayar bilimini öğrenmek: çözümleri için görevler ve yöntemler - M.: DIALOGUE-MEPhI, 2003.
Gorbatov V.A. Ayrık matematiğin temelleri. - M.: Bilim. Fizmatlit, 1999.-544s

Mantık cebirinin beş yasası vardır:

1. Tekil elementler yasası

1*X=X
0*X=0
1+X=1
0 + X = X

Mantık cebirinin bu yasası, mantık cebirinin aksiyomlarının yukarıdaki ifadelerinden doğrudan çıkar.

Üstteki iki ifade, anahtarlar oluştururken yararlı olabilir, çünkü "2I" öğesinin girişlerinden birine mantıksal sıfır veya bir uygulayarak, sinyali çıkışa iletebilir veya çıkışta sıfır potansiyel oluşturabilirsiniz.

Bu ifadeleri kullanmanın ikinci çeşidi, çok basamaklı bir sayının belirli basamaklarının seçici olarak sıfırlanması olasılığıdır. "VE" işleminin bitsel uygulaması ile, hanenin bir önceki değerini bırakabilir veya karşılık gelen hanelere bir birim veya sıfır potansiyel uygulayarak sıfırlayabilirsiniz. Örneğin 6, 3 ve 1 hanelerinin sıfırlanması gerekmektedir. O zamanlar:

Yukarıdaki mantık cebiri yasalarını kullanma örneğinde, maskedeki gerekli basamakları (alt sayı) sıfırlamak için karşılık gelen basamakların yerine sıfırların ve kalanlara birlerin yazıldığı açıkça görülmektedir. rakamlar. Orijinal sayıda (üstteki sayı) 6 ve 1 basamak yerine birimler yer almaktadır. "VE" işlemini gerçekleştirdikten sonra bu yerlerde sıfırlar belirir. Orijinal sayıdaki üçüncü rakamın yerine sıfır gelir. Ortaya çıkan sayıda, bu yerde de sıfır bulunur. Kalan haneler problemin durumu gereği değiştirilmez.

Aynı şekilde mantığın cebirinin temel kanunlarından biri olan tekil elemanlar kanunu yardımıyla ihtiyacımız olan rakamlarda birimleri yazabiliriz. Bu durumda tekil unsurlar kanununun alttaki iki ifadesini kullanmak gerekir. "VEYA" işleminin bitsel uygulaması ile, hanenin bir önceki değerini bırakabilir veya karşılık gelen hanelere sıfır veya birlik potansiyel uygulayarak sıfırlayabilirsiniz. Bir sayının 7 ve 6 bitlik birimlerini yazmak istensin. O zamanlar:

Burada maskede (alt sayı) yedinci ve altıncı bitlerde birler yazdık. Kalan bitler sıfır içerir ve bu nedenle, satırın altındaki sonuç sayısında gördüğümüz orijinal sayının ilk durumunu değiştiremez.

Tekil elemanlar yasasının ilk ve son ifadeleri, daha az girdili mantık öğeleri olarak daha çok girdi ile kullanılmasına izin verir. Bunu yapmak için, "VE" devresindeki kullanılmayan girişler, Şekil 1'de gösterildiği gibi bir güç kaynağına bağlanmalıdır:

Şekil 1. "3I-NOT" mantık öğesinde uygulanan "2I-NOT" şeması

Aynı zamanda "OR" devresindeki kullanılmayan girişler, tek elemanlar kanununa göre devrenin ortak kablosuna Şekil 2'de gösterildiği gibi bağlanmalıdır.

Şekil 2. "2I-NOT" elemanına uygulanan "NOT" devresi

Mantık cebirinin aksiyomlarından çıkan aşağıdaki mantık cebiri yasaları, olumsuzlama yasalarıdır.

2. Olumsuzluk kanunları

a. Tamamlayıcı Elemanlar Kanunu

Mantık cebirinin bu yasasının ifadeleri, mantık devrelerini en aza indirmek için yaygın olarak kullanılır. Bu tür alt ifadeleri bir mantıksal fonksiyonun genel ifadesinden izole etmek mümkünse, o zaman dijital devre elemanlarının gerekli giriş sayısını azaltmak ve hatta bazen tüm ifadeyi bir mantıksal sabite indirgemek mümkündür.

Mantık cebirinin yaygın olarak kullanılan bir başka yasası da çifte olumsuzlama yasasıdır.

b. iki kez hayır

Çift olumsuzlama yasası, hem mantıksal ifadeleri basitleştirmek (ve dijital kombinatoryal devrelerin maliyetini basitleştirmenin ve azaltmanın bir sonucu olarak) hem de "2I-NOT" ve "2OR-" gibi mantıksal öğelerden sonra sinyallerin ters çevrilmesini ortadan kaldırmak için kullanılır. OLUMSUZLUK". Bu durumda, mantık cebiri yasaları, sınırlı sayıda mantık elemanı kullanarak verili dijital devrelerin uygulanmasını mümkün kılar.

c. Olumsuz Mantık Yasası

Negatif mantık yasası herhangi bir sayıda değişken için geçerlidir. Bu mantık cebiri yasası, "VEYA" mantıksal öğelerini kullanarak uygulamanıza izin verir ve bunun tersi de geçerlidir: "VEYA" mantıksal işlevini "VE" mantıksal öğelerini kullanarak uygulamak. Bu, AND kapılarını uygulamak kolay olduğu, ancak OR kapılarını uygulamak oldukça zor olduğu için TTL devresinde özellikle kullanışlıdır. Negatif mantık yasası sayesinde, "VEYA" öğelerini "VE" mantıksal öğeleri üzerinde uygulamak mümkündür. Şekil 3, "2OR" mantık öğesinin " " öğesi ve iki invertör üzerindeki uygulamasını göstermektedir.

Şekil 3. "2I-NOT" öğesi ve iki invertör üzerinde uygulanan "2OR" mantık öğesi

Aynı şey montaj "VEYA" şeması için de söylenebilir. Gerekirse bu devrenin girişinde ve çıkışında invertörler kullanılarak montaj "AND" haline getirilebilir.

3. Kombinasyon kanunları

Mantık cebirinin birleşimsel yasaları büyük ölçüde sıradan cebirin birleşimsel yasalarına karşılık gelir, ancak farklılıklar da vardır.

a. totoloji kanunu (çoklu tekrar)

X + X + X + X = X
X * X * X * X = X

Mantık cebirinin bu yasası, daha fazla girdiye sahip mantık kapılarının daha az girdiye sahip kapılar olarak kullanılmasına izin verir. Örneğin, Şekil 4'te gösterildiği gibi "3I" mantıksal elemanı üzerinde iki girişli "2I" devresini uygulayabilirsiniz:

Şekil 4. "3I-NOT" mantık öğesinde uygulanan "2I-NOT" şeması

veya "2NAND-NOT" devresini Şekil 5'te gösterildiği gibi normal bir invertör olarak kullanın:

Şekil 5. "2I-NOT" mantıksal elemanında uygulanan "NOT" devresi

Bununla birlikte, birkaç girişi birleştirmenin, önceki elemanların akım tüketimini artıran ve bir bütün olarak dijital devrenin hızını olumsuz yönde etkileyen mantık elemanının giriş akımlarını ve kapasitesini arttırdığı konusunda uyarılmalıdır.

Mantıksal bir öğedeki girdilerin sayısını azaltmak için, mantık cebirinin başka bir yasasını - yukarıda gösterildiği gibi tekil öğelerin yasasını - kullanmak daha iyidir.

Mantık cebirinin yasalarını incelemeye devam ediyoruz:

b. taşınabilirlik yasası

A + B + C + D = A + C + B + D

c. kombinasyon hukuku

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

d. dağıtım yasası

X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /parantezleri açarak ispatlayalım/ =
= X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3

4. Absorpsiyon kuralı (bir değişken diğerlerini absorbe eder)

X1 + X1X2X3 =X1(1 + X2X3) = X1

5. Yapıştırma kuralı (yalnızca bir değişken tarafından gerçekleştirilir)

Sıradan matematikte olduğu gibi mantığın cebirinde de işlemlerin önceliği vardır. İlk önce bu yapılır:

Parantez içinde işlem
Bir işlenenle işlem (tek işlem) - "DEĞİL"
Bağlaç - "ve"
Ayrılma - "VEYA"
Toplam modulo iki.

Aynı sıradaki işlemler, mantıksal ifadenin yazıldığı sırada soldan sağa doğru gerçekleştirilir. Mantığın cebiri doğrusaldır ve bunun için süperpozisyon ilkesi geçerlidir.

Edebiyat:

"Mantığın cebirinin yasaları" makalesiyle birlikte şunları okurlar:

Hafızasız herhangi bir mantık devresi tamamen bir doğruluk tablosu ile tanımlanır... Bir doğruluk tablosu uygulamak için sadece bu satırları dikkate almak yeterlidir...
http://website/digital/SintSxem.php

Kod çözücüler (kod çözücüler), bir tür ikili kodu diğerine dönüştürmenize olanak tanır. Örneğin...
http://web sitesi/dijital/DC.php

Çoğu zaman, dijital ekipman geliştiricileri tam tersi bir sorunla karşı karşıya kalır. Bir sekizlik veya ondalık satır kodunu şuna dönüştürmek istiyorsunuz...
http://web sitesi/digital/coder.php

Çoklayıcılar, birkaç girişi bir çıkışa bağlamanıza izin veren cihazlardır ...
http://web sitesi/dijital/MS.php

Cihazlara çoğullama çözücüler denir ... Çoklayıcıdan önemli bir fark ...
http://web sitesi/digital/DMS.php

İşlevleri dönüştürmek için, mantıksal problemlerin koşullarını resmileştirerek elde edilen formülleri basitleştirin, temel mantıksal yasalara dayalı olarak mantık cebirinde eşdeğer dönüşümler gerçekleştirilir. Bu kanunlardan bazıları, aritmetik ve cebirdeki benzer kanunlarla aynı şekilde formüle edilmiş ve yazılmıştır, diğerleri ise sıra dışı görünmektedir.

Mantık cebirinin yasaları bazen teoremler.

Önerme cebirinde, mantıksal yasalar eşdeğer formüllerin eşitliği olarak ifade edilir.

Tüm yasaların geçerliliği, yazılı yasanın sol ve sağ kısımları için doğruluk tabloları oluşturularak doğrulanabilir. Mantık cebir yasalarını kullanarak ifadeyi sadeleştirdikten sonra doğruluk tabloları aynıdır.

Bazı yasaların geçerliliği, doğruluk tablosu araçları kullanılarak kanıtlanabilir.

Resim 1.

örnekler

Figür 3

Mantık cebirinin temel yasalarını kullanarak orijinal ifadeyi sadeleştirelim:

Şekil 4

(De Morgan yasası, AND için dağılım yasası, idempotans yasası, bir değişkenin tersiyle çalışması).

Tablo, $x$ ve $y$ değişkenlerinin tüm değer kümeleri için, Şekil 2'deki formülün $1$ değerini aldığını, yani aynı şekilde doğru olduğunu göstermektedir.

Şekil 6

Kaynak ifadesinin $x$ ve $y$ değişkenlerinin karşılık gelen değerleri üzerinde Basitleştirilmiş ifade ile aynı değerleri aldığı tablodan görülebilmektedir.

Mantık cebirinin temel yasalarını uygulayarak Şekil 5'teki ifadeyi sadeleştirelim.

Şekil 7

(De Morgan yasası, absorpsiyon yasası, I için dağılım yasası).

Şekil 9

Tablo, $x$ ve $y$ değişkenlerinin tüm değer kümeleri için, Şekil 8'deki formülün $0$ değerini aldığını, yani tamamen yanlış olduğunu göstermektedir.

Mantığın cebir yasalarını uygulayarak ifadeyi sadeleştirelim:

Şekil 10.

Şekil 12.

(De Mogrgan yasası, dağılım).

Şekil 11'deki ifade için bir doğruluk tablosu yapalım:

Şekil 13.

Tablodan, Şekil 11'deki ifadenin bazı durumlarda $1$ değerini aldığı ve bazı durumlarda - $0$, yani mümkün olduğu görülebilir.

(de Morgan kuralı, ortak çarpanı, bir değişkenin tersi ile işlem kuralını çıkarırız).

(idempotent kanunu kullanılarak mümkün olan ikinci faktör tekrarlanır; ardından ilk iki ve son iki faktör birleştirilir ve yapıştırma kanunu kullanılır).

(yardımcı bir mantıksal faktör ekleriz

Önerme Cebirinin Kanunları

Önermeler cebiri (mantığın cebiri), önermeler üzerindeki mantıksal işlemleri ve karmaşık önermeleri dönüştürmek için kuralları inceleyen matematiksel mantığın bir bölümüdür.

Birçok mantıksal problemi çözerken, genellikle koşullarını resmileştirerek elde edilen formülleri basitleştirmek gerekir. Önerme cebirindeki formüllerin basitleştirilmesi, temel mantıksal yasalara dayanan eşdeğer dönüşümler temelinde gerçekleştirilir.

Önerme cebiri yasaları (mantığın cebiri) totolojilerdir.

Bazen bu yasalara teorem denir.

Önerme cebirinde, mantıksal yasalar eşdeğer formüllerin eşitliği olarak ifade edilir. Yasalar arasında, bir değişken içerenler özellikle ayırt edilir.

Aşağıdaki yasalardan ilk dördü, önerme cebirinin temel yasalarıdır.

kimlik yasası:

A=A

Her kavram ve yargı kendisiyle özdeştir.

Özdeşlik yasası, akıl yürütme sürecinde kişinin bir düşünceyi diğeriyle, bir kavramı diğeriyle değiştiremeyeceği anlamına gelir. Bu yasa ihlal edilirse, mantıksal hatalar mümkündür.

Örneğin, doğru bir şekilde akıl yürütme, dilin sizi Kiev'e getireceğini söylüyor, ancak dün füme bir dil satın aldım, bu da artık Kiev'e güvenle yanlış gidebileceğim anlamına geliyor, çünkü "dil" birinci ve ikinci sözcükleri farklı kavramları ifade ediyor.

Akıl yürütmede: Hareket sonsuzdur. Okula gitmek harekettir. Bu nedenle, sonsuza dek okula gitmek "hareket" kelimesi iki farklı anlamda kullanılır (birincisi - felsefi anlamda - maddenin bir niteliği olarak, ikincisi - sıradan anlamda - uzayda hareket etme eylemi olarak), hangi yanlış bir sonuca götürür.

Çelişmezlik yasası :

Aynı anda, ifade doğru veya yanlış olabilir, üçüncüsü yoktur. Ya A doğrudur ya da A değildir. Hariç tutulan orta kanunun uygulanmasına ilişkin örnekler:

1. 12345 sayısı ya çifttir ya da tektir, üçüncüsü verilmez.

2. Şirket zararda veya başa baş durumda faaliyet gösteriyor.

3. Bu sıvı asit olabilir veya olmayabilir.

Dışlanan ortanın yasası, tüm mantıkçılar tarafından evrensel bir mantık yasası olarak kabul edilen bir yasa değildir. Bu yasa, bilişin katı bir durumla ilgilendiği durumlarda geçerlidir: "ya-ya da", "doğru-yanlış". Belirsizliğin olduğu yerde (örneğin, gelecekle ilgili muhakemede), dışlanan orta kanunu çoğu zaman uygulanamaz.

Aşağıdaki ifadeyi göz önünde bulundurun: Bu cümle yanlıştır. Yanlış olduğunu iddia ettiği için doğru olamaz. Ama yanlış da olamaz, çünkü o zaman doğru olurdu. Bu ifade ne doğru ne de yanlıştır ve bu nedenle dışlanan orta yasası ihlal edilir.

Bu örnekteki paradoks (Yunanca paradoxos - beklenmedik, garip), cümlenin kendisine atıfta bulunmasından kaynaklanmaktadır. Bir başka iyi bilinen paradoks da berber sorunudur: Bir şehirde berber, kendi saçını kesenler dışında tüm sakinlerin saçını keser. Berberin saçını kim keser? Mantıkta, biçimselliği nedeniyle, kendine gönderme yapan böyle bir ifadenin biçimini elde etmek mümkün değildir. Bu, mantık cebirinin yardımıyla tüm olası düşünce ve argümanları ifade etmenin imkansız olduğu fikrini bir kez daha doğrular. Önerme denkliğinin tanımına dayanarak, önerme cebirinin geri kalan yasalarının nasıl elde edilebileceğini gösterelim.

Örneğin, eşdeğer (eşdeğer) A'nın ne olduğunu belirleyelim (çift olumsuzlama A, yani olumsuzlama A'nın olumsuzlanması).Bunu yapmak için bir doğruluk tablosu oluşturacağız:

Eşdeğerlik tanımı gereği, değerleri A sütununun değerleriyle eşleşen sütunu bulmalıyız. Bu, A sütunu olacaktır.

Böylece, çift olumsuzlama yasasını formüle edebiliriz:

Bir ifadeyi iki kez olumsuzlarsak, sonuç orijinal ifadedir. Örneğin, ifade A = Matroskin - kedi A'ya eşdeğerdir = Matroskin'in bir kedi olmadığı doğru değil.

Benzer şekilde, aşağıdaki yasalar türetilebilir ve doğrulanabilir:

Sabit özellikler:

iktidarsızlık kanunları:

Ne kadar tekrar edersek edelim: televizyon açık veya televizyon açık veya televizyon açık... ifadenin anlamı değişmeyecektir. Benzer şekilde, tekrardan dışarısı sıcak, dışarısı sıcak, ... bir derece daha ısınmayacak.

Değişme kanunları:

Bir v B = B v Bir

A ve B = B ve A

Ayrılma ve birleşme işlemlerinde A ve B işlenenleri değiştirilebilir.

İlişkilendirme yasaları:

Bir v(B v C) = (A v B) v C;

A & (B & C) = (A & B) & C.

İfade yalnızca ayırma işlemini veya yalnızca bağlaç işlemini kullanıyorsa, parantezleri ihmal edebilir veya keyfi olarak düzenleyebilirsiniz.

Dağıtım yasaları:

A v (B & C) = (A v B) &(A v C)

(dağıtımsal ayrışma
bağlaçla ilgili)

A & (B v C) = (A & B) v (A & C)

(bağlaç dağılımı
ayrılma ile ilgili)

Ayrıma göre dağılma yasası cebirdeki dağılma yasasına benzer, ancak birleşmeye göre dağılma ayrılma yasasının bir benzeri yoktur, yalnızca mantıkta geçerlidir. Bu nedenle kanıtlanması gerekir. Kanıt en iyi doğruluk tablosu kullanılarak yapılır:

Absorpsiyon yasaları:

Bir v (A & B) = A

A & (A v B) = A

Absorpsiyon yasalarının ispatını kendiniz yapın.

De Morgan yasaları:

De Morgan yasalarının sözlü formülasyonları:

Anımsatıcı kural: kimliğin sol tarafında, olumsuzlama işlemi tüm ifadenin üzerindedir. Sağ tarafta, kırılmış gibi görünüyor ve olumsuzlama, basit ifadelerin her birinin üzerinde duruyor, ancak aynı zamanda işlem değişiyor: ayrılmadan birleşmeye ve bunun tersi.

De Morgan yasasının uygulanmasına örnekler:

1) Arapça veya Çince biliyorum ifadesi, Arapça bilmiyorum ve Çince bilmiyorum ifadesiyle aynı şey değildir.

2) Dersi öğrendiğim ve ikili aldığım doğru değil ifadesi Ya dersi öğrenmedim ya da ikili almadım ifadesi ile aynıdır.

Etki ve eşdeğerlik işlemlerinin değiştirilmesi

Çıkarım ve eşdeğerlik işlemleri bazen belirli bir bilgisayarın veya bir programlama dilinden derleyicinin mantıksal işlemleri arasında yer almaz. Ancak bu işlemler birçok sorunun çözümü için gereklidir. Bu işlemleri olumsuzlama, ayırma ve bağlaç işlemleri dizileriyle değiştirmek için kurallar vardır.

Böylece, ima işlemini aşağıdaki kurala göre değiştirebilirsiniz: