Математичка логика, скупови, релације и функције

Скупови

Скуп (мноштво, колекција) и његови елементи (чланови) су основни појмови математике.
Скуп је одређен ако су познати сви његови елементиили особине које они задовољавају.
Скуп $А$ се може задати навођењем његових елемената, односно аналитички:

$A = \left\{ {x,y,z,...} \right\}$

или синтетички

$A = \left\{ {x|P\left( x \right)} \right\}$

чиме се означава скуп свих елемената x који имају особину $P$.

Ако је $А$ скуп, тада $x \in A$ значи

  • да је $x$ елемент скупа $А$,
  • да $x$ припада скупу $А$,
  • да је $x$ у скупу $А$.

Ако $x$ не припада скупу $А$ пише се $x \notin A$.

 

Подскуп (Инклузија)

Скуп $А$ је подскуп скупа $B$, ако је сваки елемент скупа $А$ и елемент скупа $B$.
Да је $А$ подскуп скупа $B$, означава се са $A \subset B$ или, $B \supset A$, а $ \supset $ односно $ \subset $ је знак иклузије.

Логичким симболима инклузија се дефинише:

$A \subset B \Leftrightarrow \left( {\forall x} \right)\left( {x \in A \Rightarrow x \in B} \right)$

 

Једнакост скупова

Скупови $А$ и $B$ су једнаки ако и само ако је $A \subset B$ и $B \supset A$. Тада се пише $A = B$. Ако скупови  $А$ и $B$ нису једнаки, пише се $A \ne B$.

 

Прави подскуп

Ако је $A \subset B$ и $A \ne B$, онда је $А$ прави подскуп скупа $B$.

 

Унија скупова

Унија скупова $А$ и $B$ је скуп свих елемената који се налазе бар у једном од скупова $А$ и $B$.
Унија скупова $А$ и $B$ означава се са $A \cup B$, помоћу логичких симбола се дефинише:

$A \cup B = \left\{ {x|x \in A \vee x \in B} \right\}$

 

Пресек скупова

Пресек скупова $А$ и $B$ је скуп свих елемената који су и у скупу $А$ и у скупу $B$.
Пресек скупова $А$ и $B$ означава се са $A \cap B$, а помоћу логичких симбола се дефинише: 

$A \cap B = \left\{ {x|x \in A \wedge x \in B} \right\}$

 

Разлика два скупа

Разлика два скупа $А$ и $B$ је скуп свих елемената скупа $А$, који припадају скупу $B$. Разлика скупова $А$ и $B$ означава се са $A\backslash B$, а помоћу логичких симбола се дефинише:

$A\backslash B = \left\{ {x|x \in A \wedge x \notin B} \right\}$

 

Симетрична разлика два скупа

Симетрична разлика скупова $А$ и $B$ је унија скупова $A\backslash B$ и $B\backslash A$ и означава се са $A\Delta B$

$A\Delta B = (A\backslash B) \cup (B\backslash A)$

skupovi unija skupovi presek skupovi razlika skupovi simetricna razlika

Венови дијаграми: а) унија, б) пресек, в) разлика, г) симетрична разлика скупова.

 

Комплемент скупа

Ако је $A \subset I$, скуп ${C_I}A = I$ $\ А$ је комплемент скупа $А$ у односу на скуп $I$.

skupovi komplement skupa

Комплемент скупа $А$ у односу на скуп $I$.

 

Празан скуп

Празан скуп је скуп без елемената. Обележава се са $\emptyset $, а помоћу логичких симбола се дефинише:

$A = \emptyset \Leftrightarrow (\forall x) \notin A$

 

Дисјунктни скупови

Два су скупа дисјунктна ако немају заједничких елемената, тј. скупови $А$ и $B$ су дисјунктни ако је $A \cap B = \emptyset $

 

Партиција скупа

Скуп непразних скупова $\left\{ {{A_1},{A_2}} \right.,...,\left. {{A_n}} \right\}$ скупа $А$ чини партицију скупа $А$ ако задовољава следеће услове:

  1. $\left( {{\forall _i}} \right)\left( {{\forall _j}} \right)\left( {i \ne j \Rightarrow {A_i} \cap {A_j} = \emptyset } \right)$ , i=1,...,n; j=1,....n
  2. ${A_1} \cup {A_2} \cup ... \cup {A_n} = A$

 

Партитивни скуп

Партитивни скуп $P(А)$ скупа $А$ је скуп свих његових подскупова, подразумевајући и сам скуп $А$, као и празан скуп.

$P\left( A \right) = \left\{ {X\backslash X \subset A} \right\}$

 

Важније особине операције са скуповима

  1. Комутативност пресека, уније и симетричне разлике
    $A \cap B = B \cap A,{\text{  }}A \cup B = B \cup A,{\text{  }}A\Delta B = B\Delta A$
  2. Асоцијативност пресека, уније симетричне разлике
    $\left( {A \cap B} \right) \cap C = A \cap \left( {B \cap C} \right)$, $\left( {A \cup B} \right) \cup C = A \cup \left( {B \cup C} \right)$ и $\left( {A\Delta B} \right)\Delta C = A\Delta \left( {B\Delta C} \right)$
  3. Идемпотентност пресека и уније
    $A \cap A = A,{\text{  }}A \cup A = A$.
  4. Дистрибутивност пресека према унији и обрнуто
    $A \cap \left( {B \cup C} \right) = \left( {A \cap B} \right) \cup \left( {A \cap C} \right)$, ${\text{A}} \cup \left( {B \cap C} \right) = \left( {A \cup B} \right) \cap \left( {A \cup C} \right)$
  5. Апсорптивност пресека према унији и обрнуто 
    $A \cap \left( {A \cup B} \right) = A,{\text{  }}A \cup \left( {A \cap B} \right) = A$
  6. Инволутивност комплемената
    ${C_I}\left( {{C_I}A} \right) = A$
  7. Транзитивност инклузије 
    $\left( {C \subset B} \right) \wedge \left( {B \subset A} \right) \Rightarrow C \subset A$
  8. Дистрибутивност пресека према пресеку и уније према унији
    $\left( {A \cap B} \right) \cap C = \left( {A \cap C} \right) \cap \left( {B \cap C} \right)$, $\left( {A \cup B} \right) \cup C = \left( {A \cup C} \right) \cup \left( {B \cup C} \right)$
  9. За сваки скуп $A \subset I$ и празан скуп $\emptyset $
    $\emptyset \subset A \subset I$,
    $A \cap \emptyset  = \emptyset  \cap A = \emptyset $,
    $A \cup \emptyset  = \emptyset  \cup A = A$,
    $A \cap I = I \cap A = A$,
    $A \cup I = I \cup A = I$.

 

Декартов производ

Уређен пар, чија је прва компонента $a$, а друга $b$, обележава се $(a, b)$.
Уређени парови $(a, b)$ и $(c, d)$ једнаки су ако и само ако је $a=c$ и $b=d$.
Уређена n-торка се означава са $\left( {{a_1},{a_2},...,{a_n}} \right)$, а једнакост уређених n-торки елемената дефинисана је са:


$\left( {{a_1},{a_2},...,{a_n}} \right) = \left( {{b_1},{b_2},...,{b_n}} \right) \Leftrightarrow {a_1} = {b_1} \wedge {a_2} = {b_2} \wedge ... \wedge {a_n} = {b_n}$.


Декартов производ скупа А и B је скуп

 

$A \times B = \left\{ {\left( {x,y} \right)|x \in A \wedge y \in B} \right\}$

 

Декартов производ $n$ скупа скупова $А_1, А_2,.....,А_n$ је

${A_1} \times {A_2} \times ..... \times {A_n} = \left\{ {\left( {{x_1},{x_2},...,{x_n}} \right)|{x_1} \in {A_1} \wedge {x_2} \in {A_2} \wedge ... \wedge {x_n} \in {A_n}} \right\}$

Декартови производи $A \times A,A \times A \times A$,... обележавају се са ${A^2}, {A^3}$,...