Математическая логика, множества, функции

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

Высказывание - это повествовательное предложение, о котором можно сказать истинно оно или ложно.  

Высказывания обозначаются: $p$, $q$, $r$ ...

Для того, чтобы не писать "истина" и "ложь" ("true" и "false") часто используют лишь начальные буквы этих слов "и" и "л" или "1" и "0", или символы "$ \top $" и "$ \bot $".

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

Введем следующие обозначения для операций: $ \wedge $ или & – конъюнкция, $ \vee $ – дизъюнкция, $\neg $ – отрицание, $ \Rightarrow $ – импликация, $ \Leftrightarrow $ – эквиваленция. Символы $ \wedge $ или &, $ \vee $, $\neg $, $ \Rightarrow $, $ \Leftrightarrow $, называются логическими операциями или связками.

операция логическая операция новое высказывание
конъюнкция ($p$ и $q$) $ \wedge $ $p \wedge q$  ($p$ и $q$)
дизъюнкция ($p$ или $q$) $ \vee $ $p \vee q$  ($p$ или $q$) 
импликация (если $p$ ... тогда $q$) $ \Rightarrow $ $p \Rightarrow q$  (если $p$, тогда $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$... и символы истины и лжи "1" и "0", или "$ \top $" и "$ \bot $")
  2. и выражения вида: $A \vee B$, $A \wedge B$, $A \Rightarrow B$, $A \Leftrightarrow B$, $\neg A$, где $A$ и $B$ формулы логики высказываний.

При написании сложных формул, для задания приоритета логических операций используют скобки.

Тавтология

Тавтологией называется тождественно истинное высказывание относительно значений своих компонентов.

Свойства логтческих операций

  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. Нейтральный элемент для операции конъюнкции и дизъюнкции
    $p \wedge 0 \Leftrightarrow p$,
    $p \vee 0 \Leftrightarrow p$.