Математика I: логика, множества, комбинаторика и низи

Лекција за првата година на факултет: искази и логички сврзници, таблици на вистинитост, операции со множества, математичка индукција, пермутации и варијации, аритметичка и геометриска низа – со решени примери и тестови.

1. Логика

Исказ (суд) е реченица што е или вистинита ( $⊤$ ) или невистинита ( $⊥$ ). Од два исказа $p$ и $q$ со логичките сврзници $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$ се добиваат нови искази.

Негација $\neg p$ („не $p$ “) е вистинита кога $p$ е невистинит и обратно.

$p$	$\neg p$
$⊤$	$⊥$
$⊥$	$⊤$

Конјункција $p \land q$ („ $p$ и $q$ “) е вистинита само кога двата исказа се вистинити; доволен е еден невистинит за да биде невистинита.

$p$	$q$	$p \land q$
$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊥$
$⊥$	$⊤$	$⊥$
$⊥$	$⊥$	$⊥$

Дисјункција $p \lor q$ („ $p$ или $q$ “) е невистинита само кога двата исказа се невистинити.

$p$	$q$	$p \lor q$
$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊤$
$⊥$	$⊤$	$⊤$
$⊥$	$⊥$	$⊥$

Импликација $p \Rightarrow q$ („од $p$ следува $q$ “) е невистинита само кога $p$ е вистинит, а $q$ невистинит.

$p$	$q$	$p \Rightarrow q$
$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊥$
$⊥$	$⊤$	$⊤$
$⊥$	$⊥$	$⊤$

Еквиваленција $p \Leftrightarrow q$ („ $p$ ако и само ако $q$ “) е вистинита кога $p$ и $q$ имаат иста вредност.

$p$	$q$	$p \Leftrightarrow q$
$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊥$
$⊥$	$⊤$	$⊥$
$⊥$	$⊥$	$⊤$

Тавтологија е формула што е вистинита за сите вредности на исказите. Се проверува со таблица на вистинитост.

Пример 1. Докажи дека $(p \Rightarrow q) \Leftrightarrow (\neg p \lor q)$ е тавтологија.

$p$	$q$	$\neg p$	$p \Rightarrow q$	$\neg p \lor q$	$(p \Rightarrow q) \Leftrightarrow (\neg p \lor q)$
$⊤$	$⊤$	$⊥$	$⊤$	$⊤$	$⊤$
$⊤$	$⊥$	$⊥$	$⊥$	$⊥$	$⊤$
$⊥$	$⊤$	$⊤$	$⊤$	$⊤$	$⊤$
$⊥$	$⊥$	$⊤$	$⊤$	$⊤$	$⊤$

Последната колона е секогаш $⊤$ : формулата е тавтологија. Затоа импликацијата може да се замени со $\neg p \lor q$ .

Пример 2. Што претставува формулата $((p \land \neg q) \lor (\neg p \land q)) \Rightarrow (p \lor q)$ ?

$p$	$q$	$p \land \neg q$	$\neg p \land q$	$(p \land \neg q) \lor (\neg p \land q)$	$p \lor q$	$\Rightarrow$
$⊤$	$⊤$	$⊥$	$⊥$	$⊥$	$⊤$	$⊤$
$⊤$	$⊥$	$⊤$	$⊥$	$⊤$	$⊤$	$⊤$
$⊥$	$⊤$	$⊥$	$⊤$	$⊤$	$⊤$	$⊤$
$⊥$	$⊥$	$⊥$	$⊥$	$⊥$	$⊥$	$⊤$

И оваа формула е тавтологија: кога точно еден од исказите е вистинит, вистинито е и „ $p$ или $q$ “.

Закони

$p \land q \Leftrightarrow q \land p$ – комутативен закон за конјункција
$(p \land q) \land r \Leftrightarrow p \land (q \land r)$ – асоцијативен закон за конјункција
$p \lor q \Leftrightarrow q \lor p$ – комутативен закон за дисјункција
$(p \lor q) \lor r \Leftrightarrow p \lor (q \lor r)$ – асоцијативен закон за дисјункција
$(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$ – закон за контрапозиција
$\neg (p \land q) \Leftrightarrow \neg p \lor \neg q$ , $\neg (p \lor q) \Leftrightarrow \neg p \land \neg q$ – закони на Де Морган

Провери се:

p = ⊤

q = ⊥

→

p \Rightarrow q

Одговор: $⊥$ .

2. Множества

Операции со множества

$A \cup B = {x ∣ x \in A \lor x \in B}$ – унија: елементите што се барем во едното множество
$A \cap B = {x ∣ x \in A \land x \in B}$ – пресек: заедничките елементи
$A ∖ B = {x ∣ x \in A \land x \notin B}$ – разлика
$A Δ B = (A ∖ B) \cup (B ∖ A)$ – симетрична разлика
$A^{c} = \overset{―}{A} = C_{B} A = {x ∣ x \in B \land x \notin A}$ – комплемент на $A$ во $B$
$P (A) = {X ∣ X \subseteq A}$ – партитивно множество: сите подмножества на $A$ ; ако $A$ има $n$ елементи, $P (A)$ има $2^{n}$
$A \times B = {(x, y) ∣ x \in A \land y \in B}$ – Декартов производ: сите подредени парови

Пример. Множествата се зададени со својство и се пишуваат со набројување:

${x ∣ x \in Z \land - 2 \leq x \leq 7} = {- 2, - 1, 0, 1, 2, 3, 4, 5, 6, 7}$
$\{x\mid x\in\mathbb N,\ x\text{ непарен}\land x<10\}=\{1,3,5,7,9\}$
${x ∣ x \in R \land x^{2} - 25 = 0} = {- 5, 5}$

За $A = {1, 2, 3, 4}$ и $B = {3, 4, 5}$ :

$A \cup B = {1, 2, 3, 4, 5}$ , $A \cap B = {3, 4}$ , $A ∖ B = {1, 2}$ , $A Δ B = {1, 2, 5}$
$P ({1, 2}) = {\emptyset, {1}, {2}, {1, 2}}$ , ${1, 2} \times {a, b} = {(1, a), (1, b), (2, a), (2, b)}$

3. Математичка индукција

Многу својства на природните броеви се докажуваат со принципот на математичка индукција, во три чекори:

проверка: тврдењето важи за $n = 1$ ;
претпоставка: тврдењето важи за $n = k$ ;
доказ: тогаш важи и за $n = k + 1$ .

Пример. Докажи дека $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ .

1) За $n = 1$ : $1 = \frac{1 \cdot 2}{2}$ ✓.

2–3) Нека $1 + 2 + \dots + k = \frac{k (k + 1)}{2}$ . Тогаш $1 + 2 + \dots + k + (k + 1) = \frac{k (k + 1)}{2} + (k + 1) = \frac{(k + 1) (k + 2)}{2}$ , што е формулата за $n = k + 1$ ✓.

4. Комбинаторика

Факториел: $n! = n \cdot (n - 1) \dots 3 \cdot 2 \cdot 1$ , $1! = 1$ , $0! = 1$ ; $3! = 6$ , $5! = 120$ .

Пермутации (подредувања) на $n$ различни елементи: $P (n) = n!$

Ако меѓу $n$ елементи има групи од $k_{1}, k_{2}, \dots$ еднакви, пермутации со повторување: $P (n; k_{1}, k_{2}, \dots) = \frac{n!}{k_{1}! k_{2}! \dots}$

Пример. Колку различни зборови се добиваат од буквите на зборот TEUTA (5 букви, T двапати)?

$P (5; 2, 1, 1, 1) = \frac{5!}{2! 1! 1! 1!} = \frac{120}{2} = 60$

Пример. Колку шестцифрени броеви со различни цифри се пишуваат со цифрите 0, 1, 2, 3, 4, 5? Од сите $6!$ подредувања се одземаат оние што почнуваат со 0 ( $5!$ ):

$6! - 5! = 5! (6 - 1) = 120 \cdot 5 = 600$

Варијации без повторување: подредени избори на $k$ од $n$ различни елементи: $V_{n}^{k} = \frac{n!}{(n - k)!} = n (n - 1) \dots (n - k + 1)$

Пример. $n = 10$ , $k = 5$ : $V_{10}^{5} = \frac{10!}{5!} = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 30240$

Варијации со повторување (секој елемент може да се избере повеќепати): ${\overset{―}{V}}_{n}^{k} = n^{k}$

Пример. Со цифрите 1 и 2 ( $n = 2$ ) двоцифрени ( $k = 2$ ) и трицифрени ( $k = 3$ ) низи:

${\overset{―}{V}}_{2}^{2} = 2^{2} = 4$ : 11, 12, 21, 22; ${\overset{―}{V}}_{2}^{3} = 2^{3} = 8$ : 111, 112, 121, 122, 211, 212, 221, 222.

Ако редоследот не е важен, тоа се комбинации: $C_{n}^{k} = (\binom{n}{k}) = \frac{n!}{k! (n - k)!}$ .

5. Низи

Низа е функција од природните броеви: $a_{1}, a_{2}, a_{3}, \dots$ ; $a_{n}$ е општиот член.

Пример. Првите пет члена на низите:

$a_{n} = \frac{1}{2 n}$ : $\frac{1}{2}, \frac{1}{4}, \frac{1}{6}, \frac{1}{8}, \frac{1}{10}$
$a_{n} = (- 1)^{n} \frac{1}{2^{n}}$ : $- \frac{1}{2}, \frac{1}{4}, - \frac{1}{8}, \frac{1}{16}, - \frac{1}{32}$
$a_{n} = \frac{3 n + 2}{n}$ : $5, 4, \frac{11}{3}, \frac{14}{4}, \frac{17}{5}$
$a_{n} = \frac{(- 1)^{n} n^{2}}{n} = (- 1)^{n} n$ : $- 1, 2, - 3, 4, - 5$

Аритметичка низа: секој член е претходниот плус ист број $d$ (разлика). На пример $1, 3, 5, 7, \dots$ ( $d = 2$ ), $4, 10, 16, 22, \dots$ ( $d = 6$ ).

$a_{n} = a_{1} + (n - 1) d$ – општ член

$S_{n} = \frac{n}{2} (a_{1} + a_{n}) = \frac{n}{2} (2 a_{1} + (n - 1) d)$ – збир на првите $n$ членови

Пример. Фирма за продажба на телефони на 1 март заработила 2000 €, а секој следен ден заработката растела за 125 €. Колку заработила до крајот на март?

Заработка на 31 март: $a_{31} = 2000 + 30 \cdot 125 = 5750$ €

Вкупно за 31 ден: $S_{31} = \frac{31}{2} (2000 + 5750) = \frac{31 \cdot 7750}{2} = 120125$ €

Геометриска прогресија: секој член е претходниот помножен со ист број $q$ (количник). На пример $2, 4, 8, 16, 32, \dots$ ( $q = 2$ ).

$a_{n} = a_{1} q^{n - 1}$ – општ член

$S_{n} = a_{1} \frac{q^{n} - 1}{q - 1}$ – збир на првите $n$ членови ( $q \neq 1$ )

Тестови

Провери се со тестовите (по 10 задачи, со решенија):

Математика I – основи – тест 1 – Логика: искази и таблици на вистинитост
Математика I – основи – тест 2 – Множества и математичка индукција
Математика I – основи – тест 3 – Комбинаторика: пермутации и варијации
Математика I – основи – тест 4 – Низи: аритметичка и геометриска