lysa/ru/chapters/2/1-basic-logic.ltx

\s{Базовая логика}\label{2.1-basic-logic}

\ss{True и False}

``Правда`` или ``Ложь`` – за время вашего обучения вы наверняка сталкивались 
с вопросами, ответами на которые были ``Правда`` или ``Ложь``.
Надеюсь, это ``правда`` так. В математике мы будем иметь дело с задачами,
где нам нужно будет решить, что нечто является правдой или нет. Более того,
мы встретим кучу выражений, которые могут быть или не быть правдой, и нам нужно будет
понять, как они связаны друг с другом. Помните об этом, пока читаете этот раздел,
в нем представлены некоторые правила о том, как решать такие вопросы.

Мы создадим два ``значения`` и назовем их \truenm\ и \falsenm соответственно.
Эти значения называются ``Булевы''. Они названы вчесть математика Джорджа Буля,
который довольно долго их изучал.

\truenm\ и \falsenm\ не очень интересны сами по себе. Но когда у нас есть куча
вещей, которые являются \truenm\ или \falsenm, мы можем комбинировать их вместе
тремя основными способами:

\begin{itemize}
\item $A \land B$ нужно читать как ``$A$ логическое-и $B$.'' Оба должны быть \truenm.
  Если один из них \falsenm, значит $A \land B$ является \falsenm. Таким образом,
  если $A$ и $B$ оба \truenm, тогда $A \land B$ является \truenm.

\item $A \lor B$ нужно читать как ``$A$ логическое-или $B$.'' Если $A$ или $B$ \truenm,
  то $A \lor B$ тоже \truenm. Такой же результат если они оба \truenm.

\item Иногда мы хотим сказать `$A$ не является \truenm'. Вместо того, чтобы писать
  так каждый раз, я буду использовать символ $\lnot$. Таким образом,
  $\lnot A$ нужно читать как `логическое-не $A$'.

\end{itemize}

\ss{Логика}

Математики слишком ленивы, чтобы писать штуки типа ``если $A$ является \truenm, то
$B$ тоже \truenm, но если $B$ является \truenm, это не обязательно значит, что
$A$ является \truenm.'' Так что в математике они используют символы. Я тоже ленивый и
тоже буду использовать эти символы.

\begin{itemize}
\item $A \implies B$ означает, что ``если $A$ является \truenm, то $B$ тоже должно быть
  \truenm.'' Всегда следуйте за стрелкой. $A \implies B$ нужно читать как ``из $A$ следует $B$.''

\item $A \impliedby B$ это то же самое, что написать $B \implies A$. Часто удобнее написать
  именно $A \impliedby B$. $A \impliedby B$ нужно читать как ``$A$ следует из $B$.''

\item $A \iff B$ означает, что $A \implies B$ и $B \implies A$. Вы можете подумать, что
  $A \iff B$ равносильно ``Сказать $A$ то же самое, что сказать $B$.'' Однако, нужно читать $\iff$ как
  ``если (и только если).'' ``Если (и только если)'' довольно долго писать, и $\iff$ часто
  не очень подходит по контексту. Так что я иногда буду использовать ессли (с двумя `f')
  вместо ``если (и только если)''.

\item $A \notimplies B$ означает ``из $A$ не следует $B$.'' \xtb{Не смотря на это}, это не
  означает, что из $A$ следует что $B$ ложно. Это попросту означает, что информация о
  $A$ не говорит вам ничего о $B$. Поняли? Аналогичное значение имеет выражение $A \notimpliedby B$.

\item Для любого $A$ всегда является правдой, что $A \implies A$.

\item Для любого $A$ всегда является правдой, что $A \notimplies \lnot A$.

\end{itemize}

Итак, я слишком ленив, так что я заканчиваю писать ``для каждого $A$, $B$, и $C$\ldots''
Вместо этого я буду использовать символ $\forall$. Это перевернутая буква А, и
она служит для обозначения `для всех'. Нужно читать её именно как `для всех'.
Так что предложение в начале абзаца будет выглядеть как $\forall A,B,C \ldots$

\begin{itemize}
\item Окей, время поупражняться в чтении записи:

  \[\forall A,B,C \semicolon \parens{\parens{A \implies B} \land \parens{B \implies C}}
  \implies \parens{A \implies C} \]

  Для этого мы можем использовать такое выражение, как $A \implies B \implies C$.
  \footnote{Обычная критика для такой записи относится к ассоциативности.
    Так как многие люди читают $A \implies B \implies C$ как
    $\parens{A \implies B} \implies C$. И это переводится как ``если $B$ следует
    из $A$, то $C$ – \truenm'', что \xti{не совсем} то, что мы хотим. Решение в том,
    чтобы не пытаться группировать операторы как выше, или использовать скобки, когда
    вы хотите их сгруппировать.}

  Вы наверное смущены таким куском математики. Давайте я прочитаю его для вас.
  ``для всех $A$, $B$ и $C$, если мы знаем что $A \implies B$ и $B \implies C$,
  то правдой является выражение $A \implies C$.'' Иногда я пишу часть $\forall\ldots$
  после выражения. То есть я мог написать выражение выше, как

  \[\parens{\parens{A \implies B} \land \parens{B \implies C}} \implies \parens{A \implies C} \semicolon \forall A,B,C\]

\item Если вы знаете, что $A \implies B$, то $\lnot A \imliedby \lnot B$.
\end{itemize}

Будьте остороны. Если два независимых выражения являются \truenm, это не значит,
что из одного следуюет другое. Так, значения $A$, $B$ и $C$ сами по себе не
\truenm и \falsenm, а выражения, при вычислении которых результатом является
\truenm или \falsenm.

\begin{ExcList}
  \Exercise{Дано $A$, правда ли, что $A \iff A$?}
  \Answer{Да. мы знаем,
    что $A \implies A$. Помните, что $A \iff A$ просто говорит нам
    $\parens{A \implies A} \land \parens{A \impliedby A}$. Так же помните, что
    $A \impliedby B$ это $B \implies A$ для ленивых. Итак, если вы знаете, что
    $A \implies A$, то должно быть правдой $A \impliedby A$ и, следовательно,
    $A \iff A$. }

  \Exercise{Дано $A$, верно ли, что $A \land A \iff A$?}
  \Answer{Да. Здесь есть два случая, с которыми мы можем иметь дело:
    \[
    \left\{
      \begin{array}{rrcl}
        A := \true  \to & \true \land \true   & \iff & \true  \\
        A := \false \to & \false \land \false & \iff & \false \\
      \end{array}
    \right.
    \]
    В обоих случаях $A \land A \iff A$. ч.т.д. Эта техника называется ``доказательство
    перебором''. Мы взяли все возможные случаи --- в данном случае их всего два ---
    и доказали теорему для каждого из них.

    Если вам незнакома запись $A := \true \to \ldots$, то ее нужно читать как
    ``допустим $A$ будет \truenm, тогда \ldots'' }

  \Exercise{Даны $A$ и $B$, всегда ли для них верно, что
    $A \land B \iff B \land A$?}
  \Answer{Да. В предыдущем упражнении мы показали, что $A \land A \iff A$. Таким
    образом, если $A$ и $B$ оба \truenm, или оба из них \falsenm, ответ – да.
    И получается, что единственный случай, который мы должны рассмотреть, это
    когда $A$ является \truenm и $B$ – \falsenm.\footnote{Вы наверное гадаете,
      почему я не рассматриваю случай, когда $A$ является \falsenm и $B$ является \truenm.
      Из случаев, что мы рассмотрели ранее, видно, что если $A \iff B$, то $B \iff A$.
      Так что если $A \land B \iff B \land A$, то $B \land A \iff A \land B$}

    Если $\true \land \false \iff \false$, и $\false \land \true \iff \false$.}

  \Exercise{Даны $A$, $B$, и $C$, всегда ли для них верно, что $\parens{A \land B} \land
    C \iff A \land \parens{B \land C}$?}
  \Answer{Да.}

  \Exercise{Дано $A$, верно ли, что $A \lor A \iff A$?}
  \Answer{Да.}

  \Exercise{Даны $A$ и $B$, оба являются значениями True/False, всегда ли для них
    верно, что $A \lor B \iff B \lor A$?}
  \Answer{Да.}

  \Exercise{Даны $A$, $B$, и $C$, всегда ли верно, что $\parens{A \lor B} \lor
    C \iff A \lor \parens{B \lor C}$?}
  \Answer{Да.}

  \Exercise{Даны $A$, $B$, и $C$, каков будет результат выражения
    $A \land \parens{B \lor C}$?}
  \Answer{$A \land \parens{B \lor C} \iff \parens{A \land B} \lor \parens{A
      \land C}$}

  \Exercise{Как вы думаете, какой результат выражения $\lnot\parens{A \land B}$?}
  \Answer{Я объясню подробнее в \cref{2.2-more-logic}, но ответ:

    \[\lnot\parens{A \land B} \iff \parens{\lnot A} \lor \parens{\lnot B}
    \semicolon \forall A,B \]
  }
  
  \Exercise{Как вы думаете, какой результат выражения $\lnot\parens{A \lor B}$?}
  \Answer{Я объясню подробнее в \cref{2.2-more-logic}, но ответ:

    \[\lnot\parens{A \lor B} \iff \parens{\lnot A} \land \parens{\lnot B}
    \semicolon \forall A, B \]
  }

  \Exercise{По одному из законов мы знаем, что

    \[ \parens{A \implies B} \implies \parens{\lnot A \impliedby \lnot B} \sfall A,B \]

    Следующее выражение верно?

    \[ \parens{A \implies B} \iff \parens{\lnot A \impliedby \lnot B} \sfall A,B \]

    В будущем, я не буду вставлять ``следующее выражение верно\ldots''. Большей частю
    потому, что я ленивый, но так же потому, что вы, читатель, можете потратить много времени,
    пытаясь понять цель данной фразы. Так что в будущем я буду писать:

    \[ \parens{A \implies B} \Qiff \parens{\lnot A \impliedby \lnot B} \sfall A,B \]

    (Заметили ? после $\iff$). Теперь вы знаете точно, о чем этот вопрос, и я могу писать
    поменьше.

  }
  \Answer{Да, просто применяем закон еще раз. Давайте переформулируем закон:

    \[ \parens{A \implies B} \implies \parens{\lnot A \impliedby \lnot B} \sfall A, B\]
    \[ \parens{\lnot A \impliedby \lnot B} \impliedby \parens{A \implies B} \sfall A,B \]
    \[ \parens{\lnot B \implies \lnot A} \impliedby \parens{B \impliedby A} \sfall A,B \]
    \[ \parens{\lnot B \implies \lnot A} \impliedby \parens{B \impliedby A} \sfall A,B \]

    Пусть $C := \lnot B$, $D := \lnot A$

    \[ \parens{C \implies D} \impliedby \parens{\lnot C \impliedby \lnot D} \sfall C,D \]

    Мы знаем из закона, что

    \[ \parens{C \implies D} \implies \parens{\lnot C \impliedby \lnot D} \sfall C,D \]

    Следовательно,

    \[ \parens{C \implies D} \iff \parens{\lnot C \impliedby \lnot D} \sfall C,D \]
    \[ \parens{A \implies B} \iff \parens{\lnot A \impliedby \lnot B} \sfall A,B \]

    ч.т.д.
  }
\end{ExcList}