Formüller ve mantık yasaları

Bir giriş dersinde matematiksel mantığın temelleri, matematiğin bu bölümünün temel kavramlarıyla tanıştık ve şimdi konu doğal olarak devam ediyor. Yeni teorik veya hatta teorik olmayan, ancak genel eğitim materyallerine ek olarak, pratik görevler bizi bekliyor ve bu nedenle bu sayfaya bir arama motorundan girdiyseniz ve / veya materyalde yetersiz yönlendirildiyseniz, lütfen yukarıdaki bağlantıyı takip edin ve önceki makale ile başlayın. Ek olarak, uygulama için 5'e ihtiyacımız var. doğruluk tabloları mantıksal işlemler hangi ben şiddetle tavsiye ederim elle yeniden yaz.

UNUTMAYIN, BASKI YAPMAYIN, yani, tekrar anlamak ve kendi elinizle kağıda yeniden yazmak için - böylece gözlerinizin önünde olsunlar:

- tablo DEĞİLDİR;
- tablo I;
- VEYA tablo;
- çıkarım tablosu;
- denklik tablosu.

Bu çok önemli. Prensip olarak, onları numaralandırmak uygun olacaktır. "Tablo 1", "Tablo 2" vb., ancak bu yaklaşımın kusurunu defalarca vurguladım - dedikleri gibi, bir kaynakta tablo ilk, diğerinde - yüz birinci olacak. Bu nedenle "doğal" isimler kullanacağız. Devam ediyoruz:

Aslında, mantıksal formül kavramına zaten aşinasınız. Sana bir standart vereceğim, ama oldukça esprili tanım: formüller ifadelerin cebirleri denir:

1) herhangi bir temel (basit) ifade;

2) eğer ve formüllerse, formüller de formun ifadeleridir.
.

Başka formül yok.

Özellikle formül, mantıksal çarpma gibi herhangi bir mantıksal işlemdir. İkinci noktaya dikkat edin - izin verir özyinelemeli keyfi olarak uzun bir formül "oluşturmanın" yolu. kadarıyla - formüller, o zaman - ayrıca bir formül; ve formüller olduğundan, o zaman - ayrıca bir formül, vb. Herhangi bir temel ifade (yine tanımlandığı gibi) formüle birden fazla kez dahil edilebilir.

formül Olumsuzörneğin, bir kayıt var - ve burada "cebirsel çöp" ile bariz bir analoji var, bu da sayıların eklenmesi mi yoksa çarpılması mı gerektiği açık değil.

Mantıksal formül şu şekilde görüntülenebilir: mantıksal işlev... Aynı bağlacı fonksiyonel formda yazalım:

Bu durumda, temel ifadeler, klasik mantıkta 2 değer alabilen argümanların (bağımsız değişkenler) rolünü de oynar: NS veya Uzanmak... Aşağıda, kolaylık olması için bazen basit ifadelere atıfta bulunacağım. değişkenler.

Mantıksal formülü (fonksiyonu) açıklayan tablo, daha önce açıklandığı gibi çağrılır, doğruluk şeması... Lütfen - tanıdık resim:

Doğruluk tablosunu oluşturma prensibi şu şekildedir: "girişte" listelemeniz gerekir tüm olası kombinasyonlar temel ifadeler (argümanlar) alabilen gerçekler ve yalanlar. Bu durumda, formül iki ifade içerir ve bu tür dört kombinasyonun olduğunu bulmak kolaydır. “Çıkışta”, tüm formülün (fonksiyonun) karşılık gelen mantıksal değerlerini alıyoruz.

Buradaki "çıkış"ın "tek adımda" ortaya çıktığını söylemeliyim, ancak genel durumda mantıksal formül daha karmaşıktır. Ve bu tür "zor durumlarda" gözlemlemeniz gerekir mantıksal işlemlerin yürütme sırası:

- önce olumsuzlama yapılır;
- ikincisi - bağlaç;
- sonra - ayrılma;
- o zaman ima;
- ve son olarak, denklik en düşük önceliğe sahiptir.

Bu nedenle, örneğin, gösterim, önce mantıksal çarpma ve ardından - mantıksal toplama gerçekleştirmeniz gerektiğini ima eder:. Tıpkı "sıradan" cebirde olduğu gibi - "önce çarparız, sonra toplarız."

Eylemlerin sırası her zamanki gibi değiştirilebilir - parantezlerle:
- burada, her şeyden önce, ayırma gerçekleştirilir ve ancak o zaman "daha güçlü" bir işlem yapılır.

Muhtemelen herkes anlar ama her itfaiyeci için: ve bu iki farklı formüller! (hem biçimsel hem de maddi anlamda)

Formül için bir doğruluk tablosu oluşturalım. Bu formül iki temel ifade içerir ve "girişte" olası tüm bir ve sıfır kombinasyonlarını listelememiz gerekir. Karışıklığı ve yanlış anlamaları önlemek için kombinasyonları listelemeyi kabul ediyoruz. kesinlikle bu sırayla (aslında en başından beri fiili kullanıyorum):

Formül iki mantıksal işlem içerir ve önceliklerine göre, her şeyden önce gerçekleştirmeniz gerekir. olumsuzlama ifadeler. Pekala, "pe" sütununu reddediyoruz - olanları sıfırlara ve sıfırları birlere dönüştürüyoruz:

İkinci adımda, sütunlara bakar ve onlara uygularız. VEYA operasyon... Biraz ileri koşarak, ayrılmanın permutable olduğunu söyleyeceğim. (ve aynı şey), ve bu nedenle sütunlar normal sırayla - soldan sağa - analiz edilebilir. Mantıksal toplama yaparken aşağıdaki uygulamalı akıl yürütmeyi kullanmak uygundur: "İki sıfır varsa, en az bir birim bir ise sıfır koyarız":

Doğruluk tablosu oluşturulur. Şimdi eski güzel imayı hatırlayalım:

… Dikkatle, dikkatle… son sütunlara bakıyoruz…. Önerme cebirinde bu tür formüllere denir. eşdeğer veya birebir aynı:

(üç yatay çizgi kimlik simgesidir)

Dersin ilk bölümünde, imayı temel mantıksal işlemlerle ifade edeceğime söz verdim ve sözün gerçekleşmesi çok uzun sürmedi! İlgilenenler, uygulamaya anlamlı bir anlam katabilir. (örneğin, "Yağmur yağıyorsa dışarısı nemlidir") ve eşdeğer ifadeyi bağımsız olarak analiz edin.

formüle edelim genel tanım: iki formül denir eşdeğer (özdeş) bu değişken formüllerinde yer alan herhangi bir değer kümesi için aynı değerleri alırlarsa (temel ifadeler)... Ayrıca söylenir ki "Formüller, doğruluk tabloları eşleşiyorsa eşdeğerdir" ama bu cümleyi pek sevmiyorum.

1. Egzersiz

Formül için bir doğruluk tablosu hazırlayın ve bildiğiniz kimliğin doğru olduğundan emin olun.

Problem çözme sırasını bir kez daha tekrarlayalım:

1) Formül iki değişken içerdiğinden, toplamda 4 olası sıfır ve bir kümesi olacaktır. Bunları yukarıda belirtilen sırayla yazıyoruz.

2) Çıkarımlar, bağlaçtan daha "zayıftır", ancak parantez içinde verilmiştir. Aşağıdaki uygulamalı akıl yürütmeyi kullanmak uygun olsa da, sütunu dolduruyoruz: "Birden sıfır geliyorsa, diğer tüm durumlarda sıfır koyarız - bir"... Ardından, çıkarım için sütunu doldururuz ve aynı zamanda, Dikkat!- sütunlar ve "sağdan sola" analiz edilmelidir!

3) Ve son aşamada, son sütunu doldurun. Ve burada şöyle akıl yürütmek uygundur: "Sütunlarda iki birim varsa, diğer tüm durumlarda bir tane koyarız - sıfır".

Son olarak doğruluk tablosunu kontrol ediyoruz. eşdeğerler .

Önerme cebirinin temel denklikleri

Henüz iki tanesiyle tanıştık ama konu bunlarla da sınırlı değil tabii ki. Oldukça fazla kimlik var ve bunların en önemlilerini ve en ünlülerini listeleyeceğim:

Bir birleşimin değişebilirliği ve bir ayrılmanın değişebilirliği

değişebilirlik permütasyon:

1. sınıftan tanıdık kurallar: "Çarmı (toplam), faktörlerin (terimler) permütasyonundan değişmez"... Ancak, bu özelliğin görünen tüm basitliği için, her zaman doğru değildir, özellikle değişmeli değildir. matris çarpımı (genel olarak yeniden düzenlenemezler), a vektörlerin vektör çarpımı- anti-değişmeli (vektörlerin permütasyonu bir işaret değişikliği gerektirir).

Ayrıca burada yine matematiksel mantığın formalizmini vurgulamak istiyorum. Yani, örneğin, ifadeler "Öğrenci sınavı geçti ve içti" ve "Öğrenci içti ve sınavı geçti" maddi bakış açısından farklıdır, ancak biçimsel hakikat açısından ayırt edilemez. ... Her birimiz bu tür öğrencileri tanıyoruz ve etik nedenlerden dolayı belirli isimleri seslendirmeyeceğiz =)

Mantıksal çarpma ve toplamanın ilişkilendirilebilirliği

Veya "okul tarzında" - bir kombinasyon özelliği ise:

Dağılım özellikleri

Lütfen ikinci durumda "parantez açma" hakkında konuşmanın yanlış olacağını unutmayın, burada belirli bir anlamda "kurgu" - sonuçta, tamamen kaldırılabilirler: çünkü çarpma daha güçlü bir işlemdir.

Ve yine - bu görünüşte "banal" özellikler tüm cebirsel sistemlerde yerine getirilmez ve ayrıca kanıt gerektirir (çok yakında bahsedeceğiz)... Bu arada, ikinci dağıtım yasası "olağan" cebirimizde bile geçerli değildir. Ve aslında:

İktidarsızlık yasası

Ne yapmalı, Latince ...

Sağlıklı bir ruhun doğrudan bir ilkesi: "Ben ve ben benim", "Ben veya ben de benim" =)

Ve sonra birkaç benzer kimlik var:

... hmm, benim bile takıldığım bir şey ... yarın bir felsefe doktoruyla uyanabilmen için =)

Çifte olumsuzlama yasası

Pekala, burada Rus diliyle ilgili bir örnek zaten kendini gösteriyor - herkes iki parçacığın "evet" anlamına gelmediğini çok iyi biliyor. Ve inkarın duygusal rengini arttırmak için genellikle üç "değil" kullanılır:
- küçücük bir kanıtla bile ortaya çıktı!

Absorpsiyon yasaları

- "Oğlan var mıydı?" =)

Doğru kimlikte parantezler atlanabilir.

De Morgan'ın yasaları

Sıkı Öğretmen varsayalım (kimin adını da biliyorsun :)) eğer bir sınav koyar - Öğrenci 1. soruyu yanıtladı ve – Öğrenci 2. soruyu cevapladı... Daha sonra bunu belirten açıklama Öğrenci Olumsuz sınavı geçti, ifadeye eşdeğer olacaktır - Öğrenci Olumsuz 1. soruyu cevapladım veya 2. soruda.

Yukarıda belirtildiği gibi, denklikler, doğruluk tabloları kullanılarak standart bir şekilde gerçekleştirilen ispata tabidir. Aslında, ima ve denkliği ifade eden denklikleri zaten kanıtladık ve şimdi bu sorunu çözme tekniğini pekiştirmenin zamanı geldi.

Kimliğini kanıtlayalım. Tek bir ifade içerdiğinden, "girişte" yalnızca iki seçenek mümkündür: bir veya sıfır. Ardından, tek bir sütun atayarak onlara uygularız. kural VE:

Sonuç olarak, "çıkışta", gerçeği ifadenin gerçeğiyle örtüşen bir formül elde edilir. Denklik kanıtlanmıştır.

Evet, bu kanıt ilkel (ve birisi bunun da "aptal" olduğunu söyleyecektir), ama tipik bir matoloji öğretmeni onun için kalbini yerinden oynatacaktır. Bu nedenle, bu kadar basit şeyler bile hafife alınmamalıdır.

Şimdi, örneğin, de Morgan yasasının geçerliliğine ikna olalım.

Önce sol taraf için bir doğruluk tablosu yapalım. Ayrışma parantez içinde olduğundan, önce onu çalıştırırız, ardından sütunu olumsuzlarız:

Ardından, sağ taraf için bir doğruluk tablosu yapalım. Burada da her şey şeffaftır - her şeyden önce daha "güçlü" olumsuzlamalar yaparız, sonra sütunlara uygularız kural VE:

Sonuçlar örtüşür, böylece kimlik kanıtlanır.

Herhangi bir denklik şu şekilde temsil edilebilir: gerçek formülle aynı... Demek oluyor HERHANGİ bir orijinal sıfır ve bir kümesi İÇİN"Çıkışta" kesinlikle bir tane elde edilir. Ve bunun çok basit bir açıklaması var: Doğruluk tabloları ve aynı olduğu için, o zaman, elbette, eşdeğerdirler.Örneğin, eşdeğer olarak, az önce ispatlanmış de Morgan'ın kimliğinin sol ve sağ taraflarını birleştirelim. :

Veya daha kompaktsa:

ödev 2

Aşağıdaki denklikleri kanıtlayın:

B)

Eğitimin sonunda kısa bir çözüm. tembel değiliz! Yalnızca doğruluk tablolarını derlemeye değil, aynı zamanda Açıkça sonuçları formüle edin. Geçenlerde belirttiğim gibi, basit şeyleri ihmal etmek çok ama çok pahalıya mal olabilir!

Mantık yasalarını tanımaya devam ediyoruz!

Evet, bu doğru - onlarla zaten güçlü ve ana ile çalışıyoruz:

NS NS denir gerçek formülle aynı veya mantık yasası.

Denklikten aynı doğru formüle önceden gerekçelendirilmiş geçiş sayesinde, yukarıda sıralanan tüm özdeşlikler mantık yasalarıdır.

Aldığı formül Yalan NS içerdiği değişkenlerin herhangi bir değer kümesi denir aynı şekilde yanlış formülle veya çelişki.

Eski Yunanlılardan gelen bir çelişkinin tescilli bir örneği:
- hiçbir ifade aynı anda hem doğru hem de yanlış olamaz.

Kanıt önemsizdir:

"Çıkışta" yalnızca sıfırlar alınır, bu nedenle formül geçerlidir özdeş yanlış.

Bununla birlikte, herhangi bir çelişki aynı zamanda bir mantık yasasıdır, özellikle:

Bu kadar kapsamlı bir konuyu tek bir makalede ele almak imkansız ve bu nedenle kendimi sadece birkaç yasayla sınırlayacağım:

Dışlanan üçüncü yasa

- klasik mantıkta, herhangi bir ifade doğru veya yanlıştır ve üçüncüsü yoktur. "Olmak ya da olmamak" sorusudur.

Kendi başınıza bir doğruluk levhası hazırlayın ve öyle olduğundan emin olun. aynı şekilde doğru formül.

karşıtlık yasası

Özünü tartıştığımızda bu yasa aktif olarak tartışıldı. gerekli kondisyon, hatırlamak: "Yağmur sırasında nemliyse, dışarısı kuruysa, kesinlikle yağmur yağmamıştır.".

Ayrıca bu yasadan, eğer adil ise Düz teorem, sonra bazen denilen ifade zıt teorem.

Eğer doğruysa ters teorem, o zaman çelişki yasası sayesinde, teorem de geçerlidir, ters ters:

Ve yine bilgilendirici örneklerimize geri dönelim: ifadeler için - sayı 4'e tam bölünür - sayı 2'ye tam bölünür adil Düz ve zıt teoremler ama yanlış ters ve ters ters teoremler. Pisagor teoreminin "yetişkin" formülasyonu için, 4 "yön"ün tümü doğrudur.

kıyas kanunu

Ayrıca türün klasikleri: "Bütün meşeler ağaçtır, bütün ağaçlar bitkidir, bu nedenle bütün meşeler bitkidir.".

Pekala, burada yine matematiksel mantığın formalizmine dikkat çekmek istiyorum: eğer katı Öğretmenimiz belirli bir Öğrencinin bir meşe ağacı olduğunu düşünüyorsa, o zaman biçimsel bir bakış açısından bu Öğrenci kesinlikle bir bitkidir =) ... bunu düşünürsün, o zaman belki gayri resmi olanla da = )

Formül için bir doğruluk tablosu oluşturalım. Mantıksal işlemlerin önceliğine göre aşağıdaki algoritmaya bağlıyız:

1) çıkarımları gerçekleştiririz ve. Genel olarak konuşursak, 3. çıkarımı hemen uygulayabilirsiniz, ancak onunla daha uygundur. (ve izin verilebilir!) biraz sonra anla;

2) sütunlara uygula kural VE;

3) şimdi yapıyoruz;

4) ve son adımda imayı sütunlara uygularız ve .

İşaret ve orta parmaklarınızla işlemi kontrol etmekten çekinmeyin :))


Son sütundan, yorum yapmadan her şeyin açık olduğunu düşünüyorum:
, gereğince, gerektiği gibi.

ödev 3

Aşağıdaki formülün bir mantık yasası olup olmayacağını öğrenin:

Eğitimin sonunda kısa bir çözüm. Evet ve neredeyse unutuyordum - ilk sıfır ve bir kümelerini kıyas yasasının ispatında olduğu gibi tam olarak aynı sırada listeleyelim. Tabii ki, çizgiler yeniden düzenlenebilir, ancak bu, benim çözümümle karşılaştırmayı büyük ölçüde karmaşıklaştıracaktır.

Boole Formüllerini Dönüştürme

"Mantıksal" amaçlarına ek olarak, eşdeğerlikler, formülleri dönüştürmek ve basitleştirmek için yaygın olarak kullanılır. Kabaca söylemek gerekirse, bir kimliğin bir parçası bir başkasıyla değiştirilebilir. Yani, örneğin, mantıksal bir formülde bir parçaya rastlarsanız, o zaman, idempotency yasasına göre, onun yerine basitçe yazabilirsiniz (ve yapmalısınız). Görüyorsanız, o zaman absorpsiyon yasasına göre girişi basitleştirin. Vesaire.

Ayrıca önemli bir şey daha var: özdeşlikler yalnızca temel ifadeler için değil, aynı zamanda keyfi formüller için de geçerlidir. Örneğin:

, nerede (ne kadar karmaşık olursa olsun) formüller.

Örneğin, karmaşık çıkarımı dönüştürelim. (1. kimlik):

Daha sonra, parantez içine "karmaşık" de Morgan yasasını uygularız, oysa işlemlerin önceliği nedeniyle bu yasadır. :

Parantezler şu şekilde kaldırılabilir: içeride "daha güçlü" bir bağlaç var:

Eh, genel olarak değişme ile, her şey basittir - hiçbir şey belirtmenize bile gerek yoktur ... tasım yasası bir şey için ruhuma battı :))

Böylece, yasa daha karmaşık bir biçimde yeniden yazılabilir:

"Meşe, ağaç, bitki" mantıksal zincirini yüksek sesle söyleyin ve yasanın anlamının, imaların yeniden düzenlenmesinden hiç değişmediğini anlayacaksınız. Belki de ifadeler daha orijinal hale geldi.

Eğitim olarak formülü sadeleştirelim.

Nereden başlamalı? Her şeyden önce, eylemlerin sırasını anlamak için: burada olumsuzlama, ifadeye "biraz daha zayıf" bir bağlaçla "bağlanan" parantezin tamamına uygulanır. Esasen, önümüzde iki faktörün mantıksal bir ürünü var: Kalan iki işlemden çıkarım en düşük önceliğe sahiptir ve bu nedenle tüm formül aşağıdaki yapıya sahiptir:.

Kural olarak, ilk adım(lar) eşdeğerlik ve imalardan kurtulur. (Eğer öylelerse) ve formülü üç ana mantıksal işleme indirgeyin. Ne söyleyebilirsin…. Bu mantıklı.

(1) Kimliği kullanıyoruz ... Ve bizim durumumuzda.

Bunu genellikle parantezlerle "sökme" takip eder. Önce tüm çözüm, sonra yorumlar. "Tereyağı" almamak için "sıradan" eşitlik simgelerini kullanacağım:

(2) De Morgan yasasını dış parantezlere uygularız, burada.

absorpsiyon teoremi iki biçimde yazılır - ayrık ve

sırasıyla bağlaç:

A + AB = A (16)

A (A + B) = A (17)

İlk teoremi ispatlayalım. Parantezlerin dışındaki A harfini çıkaralım:

A + AB = A (1 + B)

Teoreme göre (3) 1 + B = 1, bu nedenle

A (1 + B) = A 1 = A

İkinci teoremi kanıtlamak için parantezleri genişletiyoruz:

A (A + B) = A A + AB = A + AB

Bu az önce kanıtlanmış ifadedir.

Absorpsiyon teoreminin uygulanmasına ilişkin birkaç örneği ele alalım.

boole formüllerinin basitleştirilmesi.

yapıştırma teoremi ayrıca iki formu vardır - ayrık ve

bağlaç:

İlk teoremi ispatlayalım:

teorem (5) ve (4)'e göre

İkinci teoremi kanıtlamak için parantezleri genişletiyoruz:

Teorem (6)'ya göre, bu nedenle:

Absorpsiyon teoremi ile (16) A + AB = A

Soğurma teoremi, yapıştırma teoremi gibi, basitleştirmek için uygulanır.

boole formülleri, örneğin:

De Morgan teoremi Boole cebrinin üç temel işlemini birbirine bağlar

Ayrılma, bağlaç ve ters çevirme:

İlk teorem şu şekildedir: bir bağlacın tersi bir ayrılmadır

inversiyonlar. İkincisi: ayrılmanın tersine çevrilmesi, tersine çevrilmelerin birleşimidir. Morgan'ın teoremleri, sol ve sağ taraflar için doğruluk tabloları kullanılarak kanıtlanabilir.

De Morgan teoremi daha fazla değişkene uygulanabilir:

ders 5

Karmaşık ifadeleri tersine çevirme

De Morgan'ın teoremi sadece bireysel bağlaçlar için geçerli değildir

veya ayrımlar, aynı zamanda daha karmaşık ifadeler için.

ifadenin tersini bulun AB + CD'si , bağlaçların ayrılması olarak sunulur. Olumsuzluk işaretleri yalnızca değişkenlerin üzerindeyse, ters çevirme tamamlanmış kabul edilecektir. Notasyonu tanıtalım: AB = X;

CD = Y, sonra

İfadede (22) bulun ve değiştirin:

Böylece:

Bağlaç biçiminde bir ifade düşünün:

(A + B) (C + D)

şeklinde tersini bulalım.

Notasyonu tanıtalım: A + B = X; C + D = Y, sonra

Bunları ifadede bulun ve değiştirin

Böylece:

Karmaşık ifadeleri ters çevirirken aşağıdaki kuralı kullanabilirsiniz. Tersine çevirmeyi bulmak için, bağlantı işaretlerini ayrılma işaretleriyle ve ayırma işaretlerini - birleşim işaretleriyle değiştirmek ve her bir değişkenin üzerine ters çevirmeler koymak gerekir:

Boole işlevi kavramı

V genel durumda, bir işlev (lat.functio - yürütme, uyumluluk,

haritalama), kümenin her bir öğesinin kendisine göre olduğu bir kuraldır (yasa). X, bağımsız değişkenin değer aralığı olan NS, kümenin belirli bir elemanı ilişkilidir F,

bağımlı değişkenin değer aralığı olarak anlaşılan F ... Boole fonksiyonları durumunda X = F = (0,1). Herhangi bir Boole formülü, bir işlevi tanımlamak için kural olarak kullanılabilir, örneğin:

Sembol F burada A'nın argümanları gibi bir fonksiyon var, M.Ö, ikili değişken.

Bağımsız değişkenler bağımsız değişkenlerdir, herhangi bir değer alabilirler - 0 veya 1. F - bağımlı değişken. Anlamı tamamen değişkenlerin değerleri ve aralarındaki mantıksal bağlantılarla belirlenir.

Bir fonksiyonun ana özelliği: değerini belirlemek için, genel durumda, bağlı olduğu tüm argümanların değerlerini bilmek gerekir. Örneğin, yukarıdaki işlev üç bağımsız değişken A'ya bağlıdır, M.Ö. A=1 alırsak,

yani sıfıra eşit olmayan yeni bir ifade ortaya çıktı veya

birim. şimdi izin ver V= 1. O zaman

yani, bu durumda, fonksiyonun sıfıra mı yoksa bire mi eşit olduğu bilinmiyor.

Sonunda kabul edelim İLE BİRLİKTE= 0. Sonra şunu elde ederiz: F = 0. Böylece, orijinal ifadede A = 1 alırsak, V= 1, İLE BİRLİKTE = 0 ise, fonksiyon sıfır değeri alacaktır: f = 0.

Düşünmek değişken değer kümesi kavramı .

Fonksiyonun bağlı olduğu tüm argümanlara bazı değerler atanırsa, o zaman bir dizi argüman değerinden bahseder.

sadece bir set olarak adlandırın. Argüman değerleri kümesi, sıfırlar ve birler dizisidir, örneğin 110, burada ilk hane ilk argümana, ikinciden ikinciye ve üçüncüden üçüncüye karşılık gelir. Açıkçası, birinci, ikinci veya diyelim ki beşinci argümanın ne olduğu konusunda önceden anlaşmak gerekir. Bunun için harflerin alfabetik düzenini kullanmak uygundur.

örneğin, eğer

sonra Latin alfabesine göre ilk argüman R, ikinci -

Q,üçüncü - X, dördüncü - U. Ardından, argümanların değer kümesine göre kolaydır

fonksiyonunun değerini bulunuz. Örneğin 1001 kümesi verilsin.

kayıtlar, yani 1001 setinde verilen fonksiyon bire eşittir.

Bir dizi argüman değerinin bir koleksiyon olduğunu tekrar unutmayın.

sıfırlar ve birler. İkili sayılar da sıfırlar ve birler kümeleridir.

Bu şu soruyu gündeme getiriyor - kümeler ikili olarak kabul edilebilir mi?

sayılar? Bu mümkündür ve çoğu durumda özellikle ikili dosya varsa çok uygundur.

sayıyı ondalık sisteme çevir. örneğin, eğer

A = 0, B = 1, C = 1, NS = 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

yani, verilen küme ondalık olarak 6 ile numaralandırılmıştır.

Argümanların değerlerini ondalık sayıya göre bulmanız gerekiyorsa, o zaman

ters sırada hareket ederiz: önce ondalık sayıyı ikili sayıya çeviririz, sonra sola o kadar çok sıfır ekleriz ki toplam basamak sayısı argüman sayısına eşit olur, ardından argümanların değerlerini buluruz.

Örneğin, A argümanlarının değerlerini bulmamız gerekiyor, B, C, D, E, F 23 numaralı küme ile 23 sayısını ikili sisteme yöntemiyle çeviriyoruz

ikiye bölme:

Sonuç olarak 23 10 = 10111 2 elde ederiz. Bu sayı beş basamaklıdır ve yalnızca

altı argüman vardır, bu nedenle sola bir sıfır yazılmalıdır:

23 10 = 0101111 2. Buradan şunu buluyoruz:

A = 0, B = 1, C = 0, D = 1, E = 1, F = 1.

Sayı biliniyorsa kaç küme vardır NS argümanlar? Açıkçası, n-bitlik ikili sayılar olduğu kadar, yani 2 n

ders 6

Boole işlevi

Bir yolunu zaten biliyoruz. Analitiktir, yani ikili değişkenleri ve mantıksal işlemleri kullanan matematiksel bir ifadedir. Buna ek olarak, en önemlisi tablo olan başka yöntemler de vardır. Tablo, tüm olası bağımsız değişken değerleri kümelerini listeler ve her küme için işlev değeri belirtilir. Böyle bir tabloya yazışma (doğruluk) tablosu denir.

Fonksiyonu örnek olarak kullanma

bunun için bir arama tablosunun nasıl oluşturulacağını bulalım.

İşlev üç bağımsız değişkene bağlıdır A, B, C. Bu nedenle tabloda

A, B, C argümanları için üç sütun ve f fonksiyonunun değerleri için bir sütun sağlıyoruz. A sütununun soluna başka bir sütun yerleştirmek yararlıdır. İçinde, üç basamaklı ikili sayılar olarak kabul edilirlerse, kümelere karşılık gelen ondalık sayılar yazacağız. Bu ondalık

sütun, tabloyla çalışmanın rahatlığı için tanıtıldı, bu nedenle prensipte,

ihmal edilebilir.

Tabloyu dolduruyoruz. LLC numaralı satır şunları içerir:

A = B = C = 0.

Fonksiyonun değerini bu küme üzerinde tanımlayalım:

f sütununda, 000 kümesi olan satıra sıfır yazın.

Sonraki set: 001, cilt. e. A = B = 0, С = 1. Fonksiyonun değerini bulun

bu sette:

001 kümesinde, işlev 1'dir, bu nedenle, satırdaki f sütununda

001 numara, bir tane yazın.

Benzer şekilde diğer tüm kümelerdeki fonksiyonların değerlerini hesaplıyoruz ve

tüm tabloyu doldurun.

çağrışım x 1 (x 2 x 3) = (x 1 x 2) x 3; x 1 Ú (x 2 Ú x 3) = (x 1 Ú x 2) Ú x 3. değişebilirlik x 1 x 2 = x 2 x 1 x 1 Ú x 2 = x 2 Ú x 1 Bir bağlacın ayrılmaya göre dağılımı x 1 (x 2 Ú x 3) = x 1 x 2 Ú x 1 x 3. Bir bağlaçla ilgili olarak bir ayrılmanın dağılımı x 1 Ú (x 2 × x 3) = (x 1 Úx 2) × (x 1 Úx 3). * Idempotency (totoloji) iki kez hayır Sabit özellikler x & 1 = x; (evrensel küme yasaları) x & 0 = 0; (sıfır set kanunları) De Morgan'ın kuralları (yasalar) Çelişki (tamamlayıcılık) yasası Üçüncü (tamamlayıcılık) dışlama yasası Bütün bu formüllerin ispatları önemsizdir. Bir seçenek, sol ve sağ taraflar için doğruluk tabloları oluşturmak ve bunları karşılaştırmaktır. Yapıştırma kuralları Temel bağlaçlar için yapıştırma kuralı dağıtım yasasından, tamamlayıcılık yasasından ve evrensel küme yasasından çıkar: iki bitişik bağlacın ayrılması, orijinal bağlaçların ortak bir parçası olan tek bir temel bağlaçla değiştirilebilir . Temel toplamlar için yapıştırma kuralı, ikinci tür dağıtım yasasından, tamamlayıcılık yasasından ve sıfır kümesi yasasından çıkar: iki komşu tümcenin birleşimi, orijinal tümcelerin ortak parçası olan bir temel tümce ile değiştirilebilir. . Absorpsiyon kuralı İki temel ürünün toplamı için soğurma kuralı, birinci tür dağılım yasasından ve evrensel küme yasalarından kaynaklanır: biri diğerinin ayrılmaz bir parçası olan iki temel bağlacın ayrılması, daha az işlenenli bir bağlaçla değiştirilebilir . Temel toplamların çarpımı için soğurma kuralı, ikinci tür dağıtım yasasından ve sıfır kümesi yasalarından kaynaklanır: biri diğerinin ayrılmaz bir parçası olan iki temel ayrımın birleşimi, daha az sayıda işlenene sahip bir temel ayrım ile değiştirilebilir. dağıtım kuralı Bu kural, yapıştırmanın ters eylemini tanımlar. Temel bir ürünü, daha yüksek bir değerdeki (r = n'ye kadar, yani aşağıda tartışılacağı gibi, birliğin bileşenlerine kadar) mantıksal bir toplamına genişletme kuralı, evrensel kümenin yasalarından, dağılımdan, birinci tür hukuktur ve üç aşamada gerçekleştirilir: Sıra r'nin genişletilebilir temel ürününde, n'nin birimi oluşturan bileşenin sırası olduğu n-r birimlerinin faktörleri olarak tanıtılır; Her birim, orijinal temel üründe mevcut olmayan bazı değişkenlerin mantıksal toplamı ve bunun olumsuzlaması ile değiştirilir: x ben v `x ben = 1; Tüm parantezler, birinci tür dağıtım yasası temelinde açılır, bu da, rütbe r'nin ilk temel ürününün, birimin 2 n-r bileşenlerinin mantıksal bir toplamına genişletilmesine yol açar. Temel ürünü açma kuralı, Boole Cebirinin (FAL) işlevlerini en aza indirmek için kullanılır. Sıra r'nin temel bir toplamını, sıra n'nin (sıfırın bileşenleri) temel toplamlarının ürününe genişletme kuralı, sıfır kümesi (6) yasalarını ve ikinci tür dağıtım yasasını (14) takip eder ve üç durumda gerçekleştirilir. aşamalar: Derece r'nin genişletilebilir toplamında, n-r sıfırları terimler olarak sunulur; Her sıfır, ilk toplamda ve bunun olumsuzlanmasında bulunmayan bazı değişkenlerin mantıksal bir ürünü olarak temsil edilir: x ben·` x ben = 0; Ortaya çıkan ifade, ikinci tür (14) dağıtım yasası temelinde dönüştürülür, böylece r sıralamasının ilk toplamı, sıfırın 2 n-r bileşeninin mantıksal bir ürününe dönüşür. 16. Eksiksiz bir sistem kavramı. Komple sistem örnekleri (kanıtlı) Tanım. Herhangi bir Boole işlevi A üzerinde bir formülle ifade edilebiliyorsa, bir Boole işlevi A kümesine tam sistem (P2'de) denir. Fonksiyonlar sistemi A = ( f 1, f 1, ..., fm) tam olana denir temel. Asgari bir temel, en az bir işlevin kaldırılması için bir temeldir. f1 bu temeli oluşturan, işlevler sistemini dönüştürür (f 1, f 1, ..., fm) eksik. Teorem. A = (∨, &,) sistemi tamamlandı. Kanıt. F mantığının cebirinin işlevi aynı sıfırdan farklıysa, o zaman f, yalnızca ayrılma, birleşme ve olumsuzlamayı içeren mükemmel bir ayırıcı normal form biçiminde ifade edilir. f ≡ 0 ise, o zaman f = x & x. Teorem kanıtlanmıştır. Lemma. A sistemi tamamlanmışsa ve A sisteminin herhangi bir işlevi başka bir B sistemine göre bir formülle ifade edilebiliyorsa, B de tam bir sistemdir. Kanıt. Rastgele bir Boole fonksiyonu f (x 1,…, x n) ve iki fonksiyon sistemi düşünün: A = (g 1, g 2,…) ve B = (h 1, h 2,…). A sistemi tamamlanmış olduğu için f fonksiyonu bunun üzerinde bir formülle ifade edilebilir: f (x 1,…, x n) = ℑ nerede g ben = ℜ ben yani, f fonksiyonu şu şekilde temsil edilir: f (x 1,…, x n) = ℑ [ℜ1, ℜ2, ...] başka bir deyişle, B üzerinden bir formülle temsil edilebilir. Boole cebrinin tüm fonksiyonlarını bu şekilde incelersek, B sisteminin de tamamlanmış olduğunu elde ederiz. Lemma kanıtlanmıştır. Teorem. Aşağıdaki sistemler P 2'de tamamlanmıştır: 4) (&, ⊕, 1) bir Zhegalkin temeli. Kanıt. 1) A = (&, V,) sisteminin tamamlandığı bilinmektedir (Teorem 3). B = (V) sisteminin tam olduğunu gösterelim. Gerçekten de, de Morgan yasasından (x & y) = (x ∨ y) x & y = (x ∨ y) elde ederiz, yani bağlaç ayırma ve olumsuzlama ile ifade edilir ve A sisteminin tüm fonksiyonları B sistemi üzerinden formüllerle ifade edilir. Öngörüye göre B sistemi tamamlanmıştır. 2) 1. maddeye benzer şekilde: (x ∨ y) = x & y ⇔ x ∨ y = (x & y) ve Önerme 2, 2. maddenin doğruluğunu ima eder. 3) x | y = (x & y), x | x = x; x & y = (x | y) = (x | y) | (x | y) ve Lemma 2'ye göre sistem tamamlanmıştır. 4) x = x ⊕1 ve Önerme 2'ye göre sistem tamamlanmıştır. Teorem kanıtlanmıştır. 17. Zhegalkin cebiri. Operasyon özellikleri ve eksiksizliği Zhegalkin bazında S4 = (⊕, &, 1) tanımlanan Boole fonksiyonları kümesine denir Zhegalkin cebiri. Temel özellikler. 1. değiştirilebilirlik h1⊕h2 = h2⊕h1 h1 & h2 = h2 & h1 2. çağrışım h1⊕ (h2⊕h3) = (h1⊕h2) ⊕h3 h1 & (h2 & h3) = (h1 & h2) & h3 3. dağıtımcılık h1 & (h2⊕h3) = (h1 & h2) ⊕ (h1 & h3) 4. sabitlerin özellikleri 5.h⊕h = 0 h & h = h Beyan... Diğer tüm Boole fonksiyonları, Zhegalkin cebirinin işlemleri cinsinden ifade edilebilir: x → y = 1⊕x⊕xy x ↓ y = 1⊕x⊕y⊕xy 18.Polynom Zhegalkina. İnşaat yöntemleri. Örnek. Zhegalkin polinomu (bir polinom modulo 2) n değişkenler x 1, x 2 ... x n, formun bir ifadesi olarak adlandırılır: c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n, burada C k sabitleri 0 veya 1 değerlerini alabilir. Zhegalkin polinomu ayrı değişkenlerin ürünlerini içermiyorsa, buna doğrusal (doğrusal fonksiyon) denir. Örneğin, f = x⊕yz⊕xyz ve f 1 = 1⊕x⊕y⊕z polinomlardır ve ikincisi doğrusal bir fonksiyondur. teorem... Her Boole işlevi benzersiz bir şekilde bir Zhegalkin polinomu olarak temsil edilir. Belirli bir fonksiyonda Zhegalkin polinomlarını oluşturmak için ana yöntemler aşağıda verilmiştir. 1. Tanımsız katsayılar yöntemi. Verilen bir f (x 1, x 2 ... x n) fonksiyonunu gerçekleştiren gerekli Zhegalkin polinomu P (x 1, x 2 ... x n) olsun. şeklinde yazalım P = c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n C k katsayılarını bulun. Bunu yapmak için, doğruluk tablosunun her satırından değişkenlere x 1, x 2 ... x n değerlerini sırayla atarız. Sonuç olarak, benzersiz bir çözümü olan 2 n bilinmeyenli 2 n denklemli bir sistem elde ederiz. Bunu çözdükten sonra, polinom P'nin katsayılarını buluyoruz (X 1, X 2 ... X n). 2. Formülleri bir dizi bağlaç (, &) üzerinden dönüştürmeye dayalı bir yöntem. Bazı formüller oluşturun F verilen f (X 1, X 2 ... X n) fonksiyonunu gerçekleştirerek bağlaçlar (, &) kümesi üzerinde. Daha sonra, her yerde A formunun alt formüllerini A⊕1 ile değiştirin, dağılım yasasını kullanarak parantezleri genişletin (özellik 3'e bakın) ve ardından özellik 4 ve 5'i uygulayın. Örnek... f (X, Y) = X → Y fonksiyonunun Zhegalkin polinomunu oluşturun Çözüm. 1. (tanımsız katsayılar yöntemi). Gerekli polinomu formda yazalım: P = c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy Çıkarımın doğruluk tablosunu kullanarak, şunu buluruz: f (0,0) = P (0,0) = C 0 = 1 f (0,1) = P (0,1) = C 0 ⊕C 2 = 1 f (1,0) = P (1,0) = C 0 ⊕C 1 = 0 f (1,1) = P (1,1) = C 0 ⊕C 1 ⊕C 2 ⊕C 12 = 1 C 0 = 1, C 1 = 1, C 2 = 0, C 12 = 1'i sırasıyla bulduğumuz yerden Bu nedenle: x → y = 1⊕X⊕XY. 2. (Formüllerin dönüşüm yöntemi.). Elimizde: x → y = xvy = (xy) = (x (y⊕1)) ⊕1 = 1⊕x⊕xy Zhegalkin cebirinin (diğer cebirlere kıyasla) avantajının, Boole fonksiyonlarının dönüşümlerini oldukça basit bir şekilde gerçekleştirmeyi mümkün kılan mantığın aritmetikleştirilmesinde yattığını unutmayın. Boole cebri ile karşılaştırıldığında dezavantajı, formüllerin hantal olmasıdır. Benzer bilgiler. Kümeler üzerinde düşünülen işlemler, sayılar cebirinin iyi bilinen temel yasalarına benzeyen belirli yasalara tabidir. Bu, adı tanımlar cebir ayarla Mantıksal çalışmalarını cebir ve mantık arasında bir analoji fikrine dayandıran İngiliz matematikçi John Boole'un adıyla ilişkilendirilen, genellikle Boolean küme cebiri olarak adlandırılan . Rastgele A, B ve C kümeleri için aşağıdaki kimlikler geçerlidir (Tablo 3.1): Tablo 3.1 1. Kimlik yasası 2. Bir birliğin değiştirilebilirliği 2'. kesişim yer değiştirmesi 3. Dernek birlikteliği 3'. kavşak ilişkilendirme 4. Bir birliğin kesişim açısından dağılımı 4'. Birliğe göre kesişim dağılımı 5. Boş eylem yasaları ve evrensel U setleri (dışlanan üçüncü yasası) 5'. Boş eylem yasaları ve evrensel U setleri (çelişki yasası) 6. Dernek bağımsızlığı yasası 6'. Kesişim bağımsızlığı yasası 7. De Morgan yasası 7'. De morgan yasası 8. Yok etme yasası (emilim) sekiz'. Eliminasyon (absorpsiyon) yasası 9. Yapıştırma yasası dokuz'. bağ yasası 10. Poretsky yasası on'. Poretsky yasası 11. Evrim yasası (çiftin tümleyeni) Kesişme () ve birleşim () işlemlerine ilişkin kümelerin cebiri yasaları, dualite ilkesine tabidir: herhangi bir yasada tüm kesişim işaretleri birleşim işaretleri ile değiştirilirse ve tüm birleşim işaretleri kesişme işaretleri ile değiştirilirse, evren işareti (U) boş küme işareti (Ø) ile değiştirilir ve boş işaret evrenin işaretidir, sonra tekrar doğru kimliği elde ederiz. Örneğin (bu ilkeden dolayı), aşağıdakilerden kaynaklanır, vb. 3.1. Euler-Venn Diyagramlarını Kullanarak Kimliklerin Doğruluğunu Test Etme Küme cebirinin tüm yasaları, Euler-Venn diyagramları kullanılarak görselleştirilebilir ve kanıtlanabilir. Bu gerektirir: Karşılık gelen diyagramı çizin ve tüm kümeleri eşitliğin sol tarafında gölgeleyin. Başka bir diyagram çizin ve aynısını denklemin sağ tarafı için yapın. Bu özdeşlik, ancak ve ancak aynı alan her iki diyagramda da gölgeliyse doğrudur. Açıklama 3.1. Kesişen iki daire, tüm evrensel seti dört alana böler (bkz. Şekil 3.1). Açıklama 3.2. Kesişen üç daire, tüm evrensel seti sekiz bölgeye ayırır (bkz. Şekil 3.2): Açıklama 3.2.Çeşitli örneklerin koşullarını kaydederken, genellikle notasyon kullanılır:  - ...'den ... takip eder ...;  - ancak ve ancak…. Görev 3.1 ... Küme cebir ifadelerini basitleştirin: Çözüm. Görev 3 .2 ... Kimlikleri kanıtlayın: (AB) \ B \ u003d A \ B; A (BC) = A \ (A \ B)  (A \ C). Çözüm. Görev 3.3 ... Aşağıdaki bağıntıları iki şekilde kanıtlayın: diyagramları kullanarak ve kümelerin eşitliğinin tanımını kullanarak. Çözüm. 2. Kümelerin eşitliği tanımını kullanarak ispat. Tanım olarak, aşağıdaki ilişkiler aynı anda geçerliyse X ve Y kümeleri eşittir: XY ve YX. önce bunu gösterelim ... İzin vermek NS- kümenin keyfi bir elemanı , yani NS ... Demek oluyor NSU ve NS ... Bu nedenle şu şekildedir: NSA veya NSV. Eğer NSA, o zaman NSĀ, yani ... Eğer NSB, o zaman , bu şu anlama gelir ... Böylece, kümenin her elemanı. ... aynı zamanda kümenin bir elemanıdır Yani Şimdi bunun tersini ispatlayalım, yani ... İzin vermek ... Eğer NSĀ, o zaman NSU ve NSA, yani NSАВ. Bu nedenle şu şekildedir: ... Eğer , sonra NSU ve NSV. Anlamına geliyor, NSАВ, yani ... Bu nedenle, kümenin her elemanının aynı zamanda kümenin bir elemanıdır , yani . Anlamına geliyor, , gereğince, gerektiği gibi. A (BC) = (AB)  (AC); 1. Diyagramla ispat: İzin vermek NSА (ВС). Sonra NSA ve NSВС. Eğer NS o zaman NS Söylenenlerle çelişmeyen АВ, yani NS (АВ)  (АС). Eğer NS, sonra NSАС. Buradan, NS (AB)  (AC). Böylece, A (BC)  (AB)  (AC. şimdi izin ver NS (AB)  (AC). Eğer NSАВ, daha sonra NSA ve NSV. Bu nedenle şu şekildedir: NSA ve NSВС, yani NSА (ВС). Eğer NSАС, sonra NSA ve NSC. Bu nedenle şu şekildedir: NSA ve NSВС, yani NSА (ВС). Böylece, (AB)  (AC)  A (BC). Bu nedenle, A (BC) = (AB)  (AC). Q.E.D. Yeterliliği ispatlarken AB =  elde ettik. Açıktır ki, C, yani ilişki kanıtlanmıştır. İspatta en genel durum dikkate alındı. Bununla birlikte, diyagramlar oluşturulurken burada daha fazla seçenek mümkündür. Örneğin, eşitlik durumu АВ = С veya , boş kümeler durumu vb. Açıkçası, tüm olası seçenekleri hesaba katmak zor olabilir. Bu nedenle, diyagramları kullanarak ilişkilerin ispatının her zaman doğru olmadığına inanılmaktadır. 2. Kümelerin eşitliği tanımını kullanarak ispat. İhtiyaç. АВС ve element olsun NSA. Bu durumda A kümesinin bir elemanının aynı zamanda kümenin bir elemanı olacağını gösterelim. . İki durumu düşünün: NSB veya . Eğer NS o zaman NSАВС, yani NSС ve bunun bir sonucu olarak, . Eğer , sonra ... Gerekliliği kanıtlanmıştır. şimdi izin ver ve NSАВ. elemanı olduğunu gösterelim. NS ayrıca C kümesinin bir elemanı olacaktır. Eğer NSАВ, daha sonra NSA ve NSV. kadarıyla , anlamına geliyor NSC. Yeterliliği kanıtlanmıştır. 1. Diyagramla ispat: 2. Kümelerin eşitliği tanımını kullanarak ispat. AB olsun. Öğeyi düşünün NSВ (veya ). Benzer şekilde: NSА (veya NSĀ). Yani kümenin herhangi bir elemanı aynı zamanda Ā kümesinin bir elemanıdır. Ve eğer durum bu olabilir ... Q.E.D. Görev 3.4. Belirtilen alanları sembolik olarak ifade edin ve elde edilen ifadeleri basitleştirin. Çözüm. Arama alanı iki izole bölümden oluşmaktadır. Geleneksel olarak onlara üst ve alt diyelim. Temsil ettikleri çokluk şu şekilde tanımlanabilir: M = ( x xA ve NSB ve NSC veya NSC ve NSA ve NSB). Kümelerdeki işlemlerin tanımından şunu elde ederiz: M = ((AB) \ C)  (C \ A \ B). Bu ifadeyi temel işlemleri kullanarak yazalım - tamamlayıcı, birleşim ve kesişim: Her sembolün bir oluşumuna sahip olduğumuz için bu ifadeyi basitleştirmek imkansızdır. Bu, bu formülün en basit şeklidir. Bu alan A \ B \ C ve ABC kümelerinin birleşimi olarak düşünülebilir. Tanım olarak, M = ( x xA ve xB ve NSC veya NSA ve NSB ve NSC). Basitleştirelim: Bağımsız bir çözüm için görevler. 1. Basitleştirin: 2. Diyagramları, küme cebiri yasalarını ve kümelerin eşitliğinin tanımını kullanarak kanıtlayın: (AB) \ B \ u003d A \ B; A (BC) = A \ (A \ B)  (A \ C); АВ = АВ  А = В; A \ B =   AB = A. 3. Herhangi bir A için eşitliği sağlayan bir X kümesi olup olmadığını öğrenin: AX = A; (cevap );

De Morgan Kanunları, İskoç matematikçi Augustus de Morgan tarafından mantıksal olumsuzlama kullanarak mantıksal işlem çiftlerini birbirine bağlayan mantıksal kurallardır. Augustus de Morgan, klasik mantıkta aşağıdaki ilişkilerin doğru olduğunu belirtti: değil (A ve B) = (A değil) veya (B değil) değil (A veya B) = (A değil) ve (B değil) Bizim için daha tanıdık bir biçimde, bu oranlar aşağıdaki biçimde yazılabilir: De Morgan yasaları aşağıdaki gibi formüle edilebilir: Ben de Morgan kanunu:İki basit ifadenin ayrılığının reddi, bu ifadelerin olumsuzlamalarının bir araya gelmesiyle eşdeğerdir. II de Morgan yasası:İki basit ifadenin birleşiminin inkarı, bu ifadelerin olumsuzlamalarının ayrılmasıyla eşdeğerdir. De Morgan yasalarının uygulamasını belirli örneklerle ele alalım. Örnek 1. Formülü, karmaşık ifadelerin olumsuzlaması olmayacak şekilde dönüştürün. İlk de Morgan yasasını kullanarak şunları elde ederiz: Basit B ve C ifadelerinin birleşimini reddetmek için ikinci de Morgan yasasını uygularız, şunu elde ederiz: , Böylece: . Sonuç olarak, bileşik ifadelerin reddedilmediği ve tüm olumsuzlamaların yalnızca basit ifadelere atıfta bulunduğu eşdeğer bir ifade elde ettik. Doğruluk tablolarını kullanarak kararın geçerliliğini kontrol edebilirsiniz. Bunu yapmak için, orijinal ifade için doğruluk tabloları oluşturuyoruz: ve de Morgan yasalarının yardımıyla gerçekleştirilen dönüşümler sonucunda elde edilen bir ifade için: . Tablo 1. M.Ö A \ / B / \ C Tablolardan da görebileceğiniz gibi, ilk mantıksal ifade ile de Morgan yasaları kullanılarak elde edilen mantıksal ifade eşdeğerdir. Bu, doğruluk tablolarında aynı değer kümelerini aldığımız gerçeğiyle kanıtlanmıştır.