inštrukcije > matematika > Osnove logike in teorija množic
Objavljeno: 22.2.2019
Vsak smiseln povedni stavek v matematiki imenujemo izjava. Zanimalo nas bo samo, ali je izjava pravilna ali nepravilna.
Primer:
A: Število 5 je praštevilo.
B: Število 14 je deljivo s 4.
C: Vsak kvadrat je pravokotnik.
Izjavi A in C sta pravilni, B je nepravilna. Pravilno izjavo označimo s p, nepravino z n.
Naj bo A izjava. Če jo zanikamo, dobimo naspotno izjavo ali negacijo izjave A. To ozačimo z $\neg A.$ Če je prvotna izjava pravilna, je negirana izjava nepravilna in obratno; če je prvotna izjava nepravilna, je negirana izjava pravilna. Velja tudi, da je negacija negirane izjave kar prvotna izjava: $\neg \neg A = A.$
A: Število 11 je praštevilo.
$\neg A$: Število 11 ni praštevilo. (n)
Izjave na različne načine združujemo v sestavljene izjave.
Sestavljeno izjavo, kjer hkrati veljata A in B, imenujemo konjukcija ali stik izjav. Oznaka za stik je $\land$ in $A \land B$ prebermo kot "A in B." Takšna izjava je pravilna, če sta pravilni obe izjavi, drugače je nepravilna.
Pravokotnik ima štiri stranice in hkrati $5 \cdot 2 = 10.$
Konjukcija je pravilna, saj sta pravilni obe izjavi.
Sestavljeno izjavo, pri kateri velja vsaj ena od izjav A in B, imenujemo disjunkcija oziroma razmik. Oznaka za razmik je $\lor$ in izraz $A \lor B$ preberemo kot "A ali B". Z pravilnost razmika zahtevamo, da je vsaj ena od izjav pravilna. Nepravilna je le v primeru, ko sta obe izjavi nepravilni.
a) $(2 \cdots 4 = 9) \land (2+4=6)$
Disjunkcija $A \land B$ je pravilna, ker je druga izjava pravilna. b) $(2+5=6)\land (7 \: je \: sodo \: število)$
Disjunkcija $A \land B$ je nepravilna, ker sta obe izjavi nepravilni.
Implikacija je izjava oblike $A \rightarrow B$, kar preberemo kot "Če A, potem B". Izjava A je pogoj ali hipoteza, B pa posledica ali sklep. Implikacija je nepravilna, če iz pravilnega pogoja sledi nepravilen. Drugače je pravilna.
Če je število deljivo z 9, potem je deljivo tudi s 3.
Sklep je jasen, saj velja $9=3 \cdot 3.$ Ne velja pa obratno! Če je število deljivo s 3, ni nujno, da je deljivo tudi z 9 (primer: 24 je deljivo s 3, ni pa deljivo z 9).
Ekvivalenca je izjava oblike $A \iff B$, kar pomeni: "Izjava A velja natanko tedaj, ko velja B" oz. "A velja če in samo če velja B". Ekvivalenca je pravilna, če sta izjavi A in B hkrati pravilni oz. nepravilni.
Število je deljivo s 15, če in samo če je deljivo s 5 in 3.
Če število ni deljivo s 15, potem ni deljivo z vsaj enim od faktorjev 5 ali 3. Če pa je število deljivo s 3 in 5, potem pa je deljivo tudi s $3 \cdot 5=15.$
Resničnostna tabela:
\begin{array}{c | c | c | c | c | c | c} A & B & \neg A & A \land B & A \lor B & A \rightarrow B & A \equiv B \\\hline n & n & p & n & n & p & p \\\hline n & p & p & n & p & p & n \\\hline p & n & n & n & p & n & n \\\hline p & p & n & n & p & p & p \\\hline \end{array}
Podobno kot pri računskih operacijah tudi pri izjavah z oklepaji določimo vrstni red izvajanja operacij. Če oklepajev ni, velja naslednji prioritetni vrstni red: Najvišjo prioriteto ima negacija, sledijo konjukcija, disjunkcija, implikacija in ekvivalenca. Pri hkratnem izvajanju enake izjavne povezave, velja pravilno združevanja od leve proti desni.
Primer:
$A \lor B \land \neg C \rightarrow D$
lahko zapišemo kot:
$(A \lor (B \land (\neg C))) \rightarrow D.$
Množico lahko podano na tri različne načine:
Množica $A$ je podmnožice $B$, če je vsak element iz $A$ tudi element množice $B$. To označimo z $A \subset B.$ Množici $A$ in $B$ sta enaki natanko takrat, ko je množica A podmnožica B in obratno.
Presek množic $A$ in $B$ je množica vseh tistih elementov, ki so v množici $A$ in množici $B$. Oznaka: $A \cap B$. Unija množic $A$ in $B$ je množica vseh tistih elementov, ki so v množici $A$ ali v množici $B$ kar označimo z $A \cup B.$
Množici $A$ in $B$ sta disjunktni (tuji), če je njun presek prazna množica.
Razlika množic $A - B$ je množica vseh tistih elementov, ki so v A in niso v B. Označimo z $A - B$ ali $A \backslash B.$
Naj bo množica A podmožica U. Komplement množice A glede na njeno univerzalno množico U, je množica elementov, ki so v U in niso v A. Oznaka: $A^C.$
Kartezični produkt nepraznih množic $A$ in $B$ je množica vseh urejenih parov $(a,b)$, kjer je prvi element iz A in drugi iz B. To zapišemo kot $A \times B = \{ (a,b); (a \in A) \land (b \in B)\}.$
Potenčna množica $\mathcal{P} A$ množice $A$ je množica vseh njenih podmnožic. Množica z $n$ elementi ima $2^n$ podmnožic.
Moč množice $A$ s končno mnogo elementi je enaka številu elementov $n$ množice $A$: $m(A) = n.$ Za množici A in B pravimo, da sta enako močni, če velja $m(A) = m(B).$
Množica $A$ je števno neskončna, če je enako možna kot množica naravnih števil in ima moč kontinuuma, če je enako močna kot množica realnih števil.
Moč unije dveh netujih končnih množic A in B dobimo tako, da seštejemo moči obeh množic in odštejemo moč preseka, saj smo elemente pri seštevanju šteli dvakrat: $$m(A \cup B) = m(A) + m(B) - m(A \cap B).$$ Če ima množica $A$ $m$ elementov in $B$ $n$ elementov, ima njun kartezični produkt $m \cdot n$ elementov.
Primer 1:
Dani sta množici: $A = \{b,c,d,e,f,g,h,j\}$ in $B = \{a,b,c,g,i,j\}$. Zapišimo presek, unijo, obe razliki množic in $(B - A) \times (A -B).$
presek: $A \cap B = \{b, c, g ,j \}$
unija: $A \cup B = \{ a,b,c,d,e,f,g,h,i,j \}$
razliki: $A \backslash B = \{ d,e,f,h \}$ in $B \backslash A = \{ a,i \}$
$(B - A) \times (A -B) = \{ (a,d), (a,e), (a,f), (a,h), (i,d), (i,e), (i,f), (i,h) \}.$ }
Primer 2:
Med 32 učenci v razredu jih ima doma 8 samo mačko, 6 samo psa in 5 samo zlate ribice, 3 imajo psa in zlate ribice, 2 imata zlate ribice in mačko, 5 jih ima mačko in psa, eden pa vse tri živali. Koliko učencev v razredu nima doma nobene živali? Koliko učencev ima doma mačko ali psa, nimajo pa zlatih ribic?
Množice uprizorimo z diagramom. Če želimo izvedeti, kdo nima nobene živali, samo seštejemo vse učence, ki imajo vsaj eno žival. Torej: $8 + 6 + 5 + 3 + 2 + 5 + 1 = 30$ in $32- 30 =2.$ Dva učenca torej nimata hišnih ljubljenčkov.
Če želimo izvedeti, kdo ima mačko in psa, nima pa zlatih ribic, moramo pogledati presek med učenci z mačkami in psi. Torej: $ 9 + 6 + 5 = 19.$}