Ayrık Matematik
Ayrık matematik, ayrı ve sayılabilir şeylerin matematiğidir: doğru ya da yanlış, kümenin içinde ya da dışında, bu yol ya da şu yol. Bilgisayarların üzerinde çalıştığı matematiktir ve açıp kapatabildiğin mantıkla başlar.
Son güncelleme
Ayrık matematik, ayrı ve sayılabilir şeylerin matematiğidir. Bir önerme doğrudur ya da yanlıştır, bir eleman bir kümededir ya da değildir, bir ağda iki nokta arasında bağlantı vardır ya da yoktur. Arada hiçbir şey yoktur; "ayrık" kelimesinin anlamı budur ve bir bilgisayar dünyayı tam olarak böyle görür.
İlk ders altı konuyu kapsar: mantık, kümeler, sayma, graflar, sayılar teorisi ve ispat. Mantık önce gelir, çünkü öteki her konu onunla yazılır. Aşağıdan bir bağlaç seç ve p ile q'yu değiştir.
p ∧ q için doğruluk tablosu
| p | q | p ∧ q |
|---|---|---|
| D | D | D |
| D | Y | Y |
| Y | D | Y |
| Y | Y | Y |
p ile q'yu değiştir ya da bir satıra tıkla. Vurgulanan satır, onların seçtiği satırdır.
p'yi "x, A'dadır", q'yu "x, B'dedir" diye oku. Taralı bölgeler önermenin doğru olduğu yerlerdir; nokta şu anki satırdır.
p ∧ q
Okunuşu p ve q
Bu değerlerle p ∧ q doğrudur.
Yalnızca p ile q'nun ikisi de doğruysa doğru.
Kümeler olarak VE kesişimdir: x, ancak ve ancak A'da ve B'deyse A ∩ B'dedir.
Mantık: önermeler ve bağlaçlar
Bir önerme, "7 asaldır" ya da "yağmur yağıyor" gibi ya doğru ya da yanlış olan bir cümledir. Mantık, birkaç bağlaçla küçük önermelerden büyüklerini kurar ve bir doğruluk tablosu, girdilerin her birleşimi için sonucun ne olduğunu listeler.
| sembol | adı | nasıl okunur | ne zaman doğru |
|---|---|---|---|
| ∧ | VE, ve bağlacı | "p ve q" | ikisi de doğruysa |
| ∨ | VEYA, veya bağlacı | "p veya q" | en az biri doğruysa |
| ¬ | DEĞİL, olumsuzlama | "p değil" | p yanlışsa |
| ⊕ | YA DA, dışlayan veya (XOR) | "p ya da q, ama ikisi birden değil" | tam olarak biri doğruysa |
| → | İSE, koşullu önerme | "p ise q" | p doğru ve q yanlış olan durum dışında her durumda |
| ↔ | ANCAK VE ANCAK, iki yönlü koşullu önerme | "p ancak ve ancak q" | p ile q aynı değere sahipse |
Bunlardan ikisi insanları şaşırtır. Mantıktaki VEYA kapsayıcıdır: "p veya q", ikisi de doğru olduğunda da doğrudur; gündelik dildeki "çay mı, kahve mi?" sorusundan farklı olarak. Dışlayan sürümün kendi adı vardır: XOR, Türkçe ders kitaplarında "ya da".
Öteki İSE bağlacıdır. p → q yalnızca tek bir satırda yanlıştır: p doğru ve q yanlış olduğunda. Onu bir söz gibi düşün: "yağmur yağarsa şemsiye getireceğim". Söz yalnızca yağmur yağar ve şemsiye olmazsa bozulur. Kuru bir günde, ne taşırsan taşı, söz bozulmamıştır; bu yüzden önerme doğru sayılır.
Denk önermeler
İki önerme, doğruluk tabloları her satırda örtüşüyorsa denktir. Araçta VEYA'yı seç ve p'yi olumsuzla: ¬p ∨ q sütunu, p → q sütunuyla aynıdır; yani ikisi aynı şeyi söyler.
En kullanışlı denklikler, DEĞİL'in VE ile VEYA'nın içinden nasıl geçtiğini söyleyen De Morgan kurallarıdır:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Sözle: "ikisi birden değil", "biri ya da öteki yanlış" ile aynıdır; "hiçbiri" de "ikisi de yanlış" ile aynıdır. Programcılar bunları her gün "(giriş yapmış ve doğrulanmış) değil" gibi bir koşulu yeniden yazmak için kullanır.
Mantık ve kümeler tek bir fikirdir
p'yi "x, A'dadır", q'yu "x, B'dedir" diye oku. O zaman VE kesişim, VEYA birleşim, DEĞİL tümleyen olur ve her doğruluk tablosu taranmış bir Venn şemasıdır; aracın tablonun yanına bir tane çizmesinin nedeni budur. De Morgan kuralları kümeler hakkında kurallara dönüşür:
(A ∩ B)′ = A′ ∪ B′
Küme gösterimi sayfası bunların her birini tıklayabileceğin bir şema üzerinde tarar.
Sayma
Ayrık matematikte saymak, listelemeden saymak demektir. İşin çoğunu iki kural yapar.
Çarpma kuralı. Bir seçim m yolla, ikinci bir seçim n yolla yapılabiliyorsa ikisi birlikte m × n yolla yapılabilir. 4 haneli bir şifrenin her hanesi için 10 seçenek vardır, yani 10^4 = 10000 olası şifre vardır.
Kombinasyonlar. Sıra önemli değilken n şeyden k tanesini seçmenin yolu sayısı C(n, k) diye yazılır. 8 malzemeden 3'ünü seçmek:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
Pay sıralı seçimleri sayar; 3 × 2 × 1'e bölmek, aynı üç malzemenin seçilmiş olabileceği 6 sıralamayı ortadan kaldırır.
Cevap 6 × 5 bölü 2, yani 15'tir. 30 bulduysan her ikiliyi iki kez, her sıralamada bir kez saymışsındır.
Graflar
Bir graf (çizge), köşe denen noktaların kenar denen çizgilerle birleştirildiği bir kümedir. Bağlantılardan oluşan her şeyi modeller: kasabalar arasındaki yollar, bir sosyal ağdaki arkadaşlar, web sayfaları arasındaki bağlantılar.
İlk bir sonuç: 5 kişi birbiriyle birer kez el sıkışırsa C(5, 2) = 10 el sıkışma olur. Her kişi 4 el sıkar; bu 5 × 4 = 20 el ucu verir ve her el sıkışmanın iki ucu vardır, yani 20 / 2 = 10. Bu akıl yürütme el sıkışma lemmasıdır: bütün köşelerin derecelerinin toplamı, kenar sayısının iki katıdır.
Sayılar teorisi ve ispat
Modüler aritmetik, bir saat üzerindeki aritmetiktir. 17 mod 5, 17'nin 5'e bölümünden kalan olan 2'dir. Saat 8'den dokuz saat sonra saat 5'tir, çünkü 17 mod 12, 5'tir. Aynı fikir, çok büyük sayılarla, güvenli web sitelerinin arkasındaki RSA şifrelemesinin çalışma biçimidir.
Tümevarımla ispat, bir önermenin her n tam sayısı için geçerli olduğunu iki adımda gösterir: onu n = 1 için kontrol et, sonra bir n için geçerliyse n + 1 için de geçerli olduğunu göster. Örneğin şunu böyle kanıtlarsın:
1 + 2 + ... + n = n(n + 1) / 2
yalnızca denediğin değerler için değil, her n için.
Ayrık matematik ne işe yarar
- Programlama: her if ifadesi mantıktır ve De Morgan kuralları koşulları yeniden yazar.
- Veritabanları: tabloları birleştiren ya da süzen bir sorgu, küme işlemleridir.
- Algoritmalar: sayma, girdi büyüdükçe bir programın kaç adım attığını söyler.
- Ağlar ve haritalar: en kısa yollar ve sosyal ağlar graf problemleridir.
- Güvenlik: şifreleme sayılar teorisine ve modüler aritmetiğe dayanır.
- Donanım: bir işlemci mantık kapılarından yapılır ve bunlar silikona dökülmüş doğruluk tablolarıdır.
Ayrık matematik zor mu?
Cebirden ve kalkülüsten farklı bir şekilde zordur. Ezberlenecek formül azdır ve aritmetik küçüktür, ama pek çok soru bir şeyi hesaplamanı değil kanıtlamanı ister ve ikna edici bir akıl yürütme yazmak çoğu öğrenci için yeni bir beceridir.
En çok yardımcı olan, örüntüyü aramadan önce küçük durumları elle çalışmaktır: Venn şemasını çiz, doğruluk tablosunu yaz, her durumu listele. Gösterim ilk başta ağır görünür, ama çoğu bu sayfadaki ve küme gösterimi sayfasındaki sembollerden ibarettir.
Sık sorulan sorular
- Ayrık matematik nedir?
- Düzgün biçimde değişen nicelikler yerine ayrı, sayılabilir nesneleri inceleyen matematik dalıdır. Ana konuları mantık, kümeler, sayma, graflar, sayılar teorisi ve ispattır. Kalkülüs şeylerin sürekli olarak nasıl değiştiğini sorar; ayrık matematik kaç tane, hangileri ve bir önermenin doğru olup olmadığını sorar.
- Ayrık matematik zor mu?
- Kalkülüsten farklı bir şekilde zordur. Uygulanacak formül daha az, kurulacak akıl yürütme daha çoktur ve pek çok öğrenci için ispat yazmak üzerine kurulu ilk derstir. Cebir genellikle hafiftir. Onu zor bulan öğrenciler çoğunlukla ispata alışmaya çalışıyordur ve bu, küçük örneklerle pratik yaptıkça hızla düzelir.
- Ayrık matematik ne işe yarar?
- Bilgisayar bilimindeki neredeyse her şeye. Devreler ve if ifadeleri mantıkla çalışır, veritabanı sorgularının altında kümeler yatar, sayma bir algoritmanın ne kadar sürdüğünü söyler, graflar ağları ve haritaları modeller, sayılar teorisi de çevrim içi ödemeleri koruyan şifrelemenin temelidir.
- Ayrık matematikte hangi konular işlenir?
- Tipik bir ilk ders önermeler mantığını ve doğruluk tablolarını, kümeleri ve Venn şemalarını, fonksiyonları ve bağıntıları, tümevarım dahil ispat yöntemlerini, permütasyon ve kombinasyonla saymayı, temel olasılığı, grafları ve ağaçları ve modüler aritmetiği kapsar. Bazı dersler indirgeme bağıntılarını ve Boole cebirini de ekler.
- Bilgisayar bilimi için ayrık matematik gerekir mi?
- Evet. Neredeyse her bilgisayar bilimi bölümü onu, genellikle birinci ya da ikinci yılda, zorunlu tutar; çünkü algoritmalar, veri yapıları ve hesaplama kuramı onu varsayar. Yalnızca programlama için onsuz başlayabilirsin, ama mantık, kümeler ve sayma günlük kodda çoğu kişinin beklediğinden daha erken karşına çıkar.
- Ayrık ve sürekli matematik arasındaki fark nedir?
- Ayrık matematik, tam sayılar, doğru ve yanlış ya da bir ağın düğümleri gibi tek tek listeleyebileceğin değerlerle uğraşır. Kalkülüs gibi sürekli matematik ise zaman, uzaklık ya da sıcaklık gibi bir aralıktaki herhangi bir değeri alabilen niceliklerle uğraşır.
- Doğruluk tablosu nedir?
- Bir mantıksal önermenin girdileri için doğru ve yanlışın her birleşimini ve her birinde önermenin değerini listeleyen bir tablodur. p ve q gibi iki girdiyle dört satır vardır. Doğruluk tablosu, iki önermenin denk olduğunu kanıtlamanın yoludur: sütunları her satırda örtüşüyorsa her zaman aynı değeri alırlar.
