inštrukcije > matematika > Osnove logike in teorija množic

Objavljeno: 22.2.2019

Osnove logike in teorija množic

Osnove logike

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.$

Primer negacije:

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.

Primer konjukcije:

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.

Primer disjunkcije:

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.

Primer implikacije:

Č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.

Primer ekvivalence:

Š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.$

Teorija množic

Množico lahko podano na tri različne načine:

njene elemente naštejemo,
njene elemente enolično določimo s kakšno skupno lastnostjo,
ali narišemo diagram.

Množico, ki nas v danem primeru zanimajo, imenujemo univerzalna množica in jo označimo z $U$. Prazna množica (oznaka: $\emptyset$) je množica, ki ne vsebuje nobenega elementa.

Operacije nad množicami

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.

Računski primeri

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.$}