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

Математичка логика

Исказ или суд је афирмативна (потврдна) реченица која има смисла и која је или тачна или нетачна. $\top \top$

Исказе означавамо словима $p$, $q$, $r$ ...

Тачном исказу се придружује истинитосна $ \top $ вредност (те), а нетачном истинитосна вредност $ \bot $ (не-те).

 

Основне логичке операције

операција симбол нови исказ
конјункција (и) $ \wedge $ $p \wedge q$  ($p$ и $q$)
дисјункција (или) $ \vee $ $p \vee q$  ($p$ или $q$) 
импликација (ако ... онда) $ \Rightarrow $ $p \Rightarrow q$  (ако $p$ онда $q$)
еквиваленција(ако и само ако) $ \Leftrightarrow $ $p \Leftrightarrow q$  ($p$ ако и само ако $q$)
негација (не) $\neg $ $\neg p$ (не $p$)
дисјункција (или – или) $\underline  \vee  $ $p \underline  \vee  q$  ($p$ или $q$, али не оба)

 

Таблице истинитости

$p$ $q$ $p \wedge q$ $p \vee  q$ $p \Rightarrow  q$ $p \Leftrightarrow q$ $p \underline  \vee  q$
$\top$ $\top$ $\top$ $\top$ $\top$ $\top$ $ \bot $
$\top$ $ \bot $ $ \bot $ $\top$ $ \bot $ $ \bot $ $\top$
$ \bot $ $ \bot $ $\top$ $\top$ $\top$ $ \bot $ $\top$
$ \bot $ $ \bot $ $ \bot $ $ \bot $ $\top$ $\top$ $ \bot $

 

$p$ $\neg p$
$\top$ $ \bot $
$ \bot $ $\top$

 

Исказне формуле

Исказне формуле су

  1. Исказна слова $p$, $q$, $r$... 
  2. Ако су $A$ и $B$ исказне формуле, онда су и $A \vee B$, $A \wedge B$, $A \Rightarrow B$, $A \Leftrightarrow B$, $\neg A$ исказне формуле.
  3. Исказне формуле се могу добити само помоћу коначног броја примена 1 и 2.

За образовање сложених исказа, поред логичних операција, користе се и заграде, којима се истиче приоритет операције.

 

Таутологије

Исказне формуле које имају истинитосну вредност $\top$ за ма које вредности исказних слова зову се таутологије.

Таутологијама се називају особине логичких операција и логички закони.

 

Важније особине логичких операција

  1. Комутативност конјункције, дисјункције и еквиваленције
    $p \wedge q \Leftrightarrow q \wedge  p$, 
    $p \vee q \Leftrightarrow q \vee p$,
    $(p \Leftrightarrow q) \Leftrightarrow (q \Leftrightarrow p)$
  2. Асоцијативност конјункције, дисјункције и еквиваленције
    $(p \wedge q) \wedge r \Leftrightarrow p \wedge (q \vee r)$,
    $(p \vee q) \vee r \Leftrightarrow p \vee (q \vee r)$,
    $(p \Leftrightarrow q) \vee r \Leftrightarrow p \Leftrightarrow (q \Leftrightarrow r)$.
  3. Идемпотентност конјункције, дисјункције
    $p \wedge p \Leftrightarrow p$,
    $p \vee p \Leftrightarrow p$.
  4. Дистрибутивност конјукције према динсјункцији и обрнуто
    $p \wedge (q \vee r) \Leftrightarrow (p \wedge q) \vee (p \wedge r)$,
    $p \vee (q \wedge r) \Leftrightarrow (p \vee q) \wedge (p \vee r)$.
  5. Апосорптивност конјукције према динсјункцији и обрнуто
    $p \wedge (q \vee q) \Leftrightarrow p$,
    $p \vee (q \wedge q) \Leftrightarrow p$.
  6. Инволутивност негације
    $\neg (\neg p) \Leftrightarrow p$.
  7. Неутрални елемент за конјункцију и дин