Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.nature.web.ru/db/msg.html?mid=1158346&uri=node1.html
Дата изменения: Unknown
Дата индексирования: Mon Apr 11 12:29:27 2016
Кодировка: Windows-1251
Научная Сеть >> Н.В.Верещагин, А.Шень Логические формулы и схемы (статья из "Математическое просвещение", сер.3. Вып. 4.)
Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Обратите внимание!
 
  Наука >> Математика >> Алгебра, математическая логика и теория чисел | Популярные статьи
 Написать комментарий  Добавить новое сообщение
 См. также

Популярные статьиМ.Н. Вялый "Сложность вычислительных задач": ШеньВерещагин

Next: 2. Полные системы связок Up: Логические формулы и схемы Previous: Логические формулы и схемы Contents:

1. Высказывания и операции

"Если число $\pi$ рационально, то $\pi$ - алгебраическое число. Но оно не алгебраическое. Значит, $\pi$ не рационально". Мы не обязаны знать, что такое число $\pi$, какие числа называют рациональными и какие алгебраическими, чтобы признать, что это рассуждение правильно - в том смысле, что из двух сформулированных посылок действительно вытекает заключение. Такого рода ситуации - когда некоторое утверждение верно независимо от смысла входящий в него высказываний - составляют предмет логики высказываний.

Такое начало (особенно если учесть, что курс логики входит в программу философского факультета, где в свое время изучалась и "диалектическая логика") настораживает, но на самом деле наши рассмотрения будут иметь вполне точный математический характер, хотя мы начнем с неформальных мотивировок.

Высказывания могут быть истинными и ложными. Например, " $2^{16}\relax +1$ - простое число" - истинное высказывание, а "$2^{32}+1$ - простое число" - ложное (это число делится на $641$). Про высказывание "существует бесконечно много простых $p$, для которых $p+2$ - также простое" никто не берется сказать наверняка, истинно оно или ложно. А фраза "$x$ делится на $2$" в этом смысле не является высказыванием, пока не сказано, чему равно $x$; при разных $x$ получаются разные высказывания, одни истинные (при четном $x$), другие - ложные (при нечетном $x$).

Высказывания можно соединять друг с другом с помощью логических связок. Эти связки имеют довольно странные, но традиционные названия и обозначения (табл. 1).


Таблица 1. Логические связки, обозначения и названия
связка обозначение название
$A$ и $B$ $A\& B$    $A\land B$ конъюнкция
  $A$ and $B$  
$A$ или $B$     $A\lor B$    $A$ or $B$ дизъюнкция
не $A$ $\lnot A$    $\sim A$    $\overline{A}$ отрицание
$A$ неверно not $A$  
из $A$ следует $B$ $A\rightarrow B$      $A\Rightarrow B$ импликация
если $A$, то $B$ $A\supset B$ следование
$A$ влечет $B$ if $A$ then $B$  
$B$ - следствие $A$    


Отметим также, что в $A\Rightarrow B$ высказывание $A$ называют посылкой, или антецедентом импликации, а $B$ - заключением, или консеквентом.

Говорят также, что высказывание имеет истинностное значение И (истина), если оно истинно, или Л (ложь), если оно ложно. Иногда вместо И употребляется буква T (true) или число $1$, а вместо Л - буква F (false) или число $0$. (На первый взгляд идея выбрать числа 0 и 1 произвольным образом кажется дикой - какая польза могла бы быть, скажем, от сложения истинностных значений? Удивительным образом в последние годы обнаружилось, что такая польза есть, и если оперировать с истиной и ложью как элементами конечного поля, можно получить много неожиданных результатов.)

Логические связки позволяют составлять сложные высказывания из простых. При этом истинность составного высказывания определяется истинностью его частей в соответствии с таблицей 2.


Таблица 2. Таблицы истинности для логических связок
$A$ $B$ $A\land B$ $A\lor B$ $A \to B$
Л Л Л Л И
Л И Л И И
И Л Л И Л
И И И И И
                 
$A$ $\lnot A$
Л И
И Л


Те же правила можно изложить словесно. Высказывание $A\land B$ истинно, если оба высказывания $A$ и $B$ истинны. Высказывание $A\lor B$ истинно, если хотя бы одно из высказываний $A$ и $B$ истинно. Высказывание $A \to B$ ложно в единственном случае: если $A$ истинно, а $B$ ложно. Наконец, $\lnot A$ истинно в том и только том случае, когда $A$ ложно.

Из всех связок больше всего вопросов вызывает импликация. В самом деле, не очень понятно, почему надо считать, скажем, высказывания "если $2\times 2=5$, то $2\times 2=4$" и "если $2\times 2=5$, то $3\times 3=1$" истинными. (Именно так говорят наши таблицы: $\textbf{Л}\to\textbf{И}= \textbf{Л}\to\textbf{Л}=\textbf{И}$.) Следующий пример показывает, что в таком определении есть смысл.

Общепризнанно, что если число $x$ делится на $4$, то оно делится на $2$. Это означает, что высказывание

\begin{displaymath} \text{($x$ делится на $4$)} \to \text{($x$ делится на $2$)} \end{displaymath}

истинно при всех $x$. Подставим сюда $x=5$: обе части ложны, а импликация истинна. При $x=6$ посылка импликации ложна, а заключение истинно, и вся импликация истинна. Наконец, при $x=8$ посылка и заключение истинны и вся импликация истинна. С другой стороны, обратное утверждение (если $x$ делится на $2$, то $x$ делится на $4$) неверно, и число $2$ является контрпримером. При этом посылка импликации истинна, заключение ложно, и сама импликация ложна. Таким образом, если считать, что истинность импликации определяется истинностью ее частей (а не наличием между ними каких-то причинно- следственных связей), то все строки таблицы истинности обоснованы. Чтобы подчеркнуть такое узко- формальное понимание импликации, философски настроенные логики называют ее "материальной импликацией".

Теперь от неформальных разговоров перейдем к определениям. Элементарные высказывания (из которых составляются более сложные) мы будем обозначать маленькими латинскими буквами (с индексами, если понадобится) и называть пропозициональными переменными. Из них строятся пропозициональные формулы (слово "пропозициональный" для краткости будем опускать) по таким правилам:

  • Всякая пропозициональная переменная есть формула.
  • Если $A$ - пропозициональная формула, то $\lnot A$ - пропозициональная формула.
  • Если $A$ и $B$ - пропозициональные формулы, то $(A\land B)$, $(A\lor B)$ и $(A\to B)$ - пропозициональные формулы.

Можно еще сказать так: формулы - это минимальное множество, обладающее указанными свойствами (слово "минимальное" здесь существенно: ведь если бы мы объявили любую последовательность переменных, скобок и связок формулой, то эти три свойства были бы тоже выполнены).

Пусть формула $\varphi $ содержит $n$ переменных $p_1,p_2,\dots,p_n$. Если подставить вместо этих переменных истинностные значения (И или Л), то по таблицам можно вычислить истинностное значение формулы в целом. Таким образом, формула задает некоторую функцию от $n$ аргументов, каждый из которых может принимать значения Л и И. Значения функции также лежат в множестве $\{\textbf{Л},\textbf{И}\}$, которое мы будем обозначать $\bbB $. Как уже говорилось, мы будем следовать традиции и отождествлять И с единицей, а Л - с нулем, тем самым $\bbB $ есть $\{0,1\}$. Формула $\varphi $ задает отображение $\bbB ^n\to\bbB $. Такие отображения называют также булевыми функциями от $n$ аргументов.

Пример 1.   Рассмотрим формулу $(p\land (q\land \lnot r))$. Она истинна в единственном случае - когда $p$ и $q$ истинны, а $r$ ложно (см. табл. 3).


Таблица 3. Таблица истинности конъюнкции $(p\land (q\land \lnot r))$
\begin{table}\begin{displaymath} \begin{array}{\vert c\vert c\vert c\vert c\vert... ... 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ \hline \end{array} \end{displaymath}\end{table}


Некоторые формулы выражают логические законы - составные высказывания, истинные независимо от смысла их частей. Такие формулы (истинные при всех значениях входящих в них переменных) называют тавтологиями.

Пример 2.   Формула $((p \land q)\to p)$ является тавтологией (это можно проверить, например, составив таблицу). Она выражает такой логический закон: из конъюнкции утверждений следует первое из них.

Задача 1.   Как выглядит симметричное утверждение для дизъюнкции?

Две формулы называют эквивалентными, если они истинны при одних и тех же значениях переменных (другими словами, если они задают одну и ту же булеву функцию). Например, формула $(p \land (p\to q))$ истинна лишь при $p=q=\textbf{И}$ и потому эквивалентна формуле $(p\land q)$.

Рассмотрим формулу $((p\lor q)\land q)$. Она истинна, если и только если переменная $q$ истинна. Хотелось бы сказать, что она эквивалентна формуле $q$, но тут есть формальная трудность: она содержит две переменные и потому задает функцию от двух аргументов (типа $\bbB\times\bbB\to\bbB $), в то время как $q$ задает функцию от одного аргумента. Мы не будем обращать на это внимания и будем считать эти формулы эквивалентными. Вообще, если есть список переменных $p_1,\dots,p_n$, содержащий все переменные некоторой формулы $\varphi $ (и, возможно, еще какие-то переменные), можно считать, что формула $\varphi $ задает функцию от $n$ аргументов, возможно, на деле зависящую не от всех аргументов (постоянную по некоторым аргументам).

После таких оговорок легко проверить следующий факт: формулы $\varphi $ и $\psi$ эквивалентны тогда и только тогда, когда формула $((\varphi\to\psi) \land (\psi\to\varphi))$ является тавтологией. Используя сокращение $(p\leftrightarrow q)$ для $((p\to q)\land(q\to p))$, можно записывать утверждения об эквивалентности формул в виде тавтологий. Вот несколько таких эквивалентностей:

Теорема 1.   Следующие формулы являются тавтологиями:
\begin{align*} (p\land q) &\leftrightarrow (q \land p); %%[1.8pt] ((p\land q) ... ... (\lnot q\to \lnot p); %%[1.8pt] p&\leftrightarrow \lnot\lnot p. \end{align*}

Доказательство. Первые четыре эквивалентности выражают коммутативность и ассоциативность конъюнкции и дизъюнкции. Проверим, например, вторую: левая и правая части истинны в единственном случае (когда все переменные истинны), и потому эквивалентны. (Для дизъюнкции удобнее смотреть, когда она ложна.)

Две следующие эквивалентности утверждают дистрибутивность - заметим, что в отличие от сложения и умножения в кольцах здесь верны оба свойства дистрибутивности. Проверить эквивалентность легко, если отдельно рассмотреть случаи истинного и ложного $p$.

Следующие два свойства называются законами де Моргана. Их легко проверить, вспомнив, что конъюнкция истинна, а дизъюнкция ложна ровно в одном случае. Законы де Моргана иногда выражают словами: "конъюнкция двойственна дизъюнкции".

Далее следуют два очевидных закона поглощения (один из них мы уже упоминали).

За ними идет правило контрапозиции, которое говорит, в частности, что утверждения "если $x$ совершенно, то $x$ нечетно" и "если $x$ нечетно, то $x$ несовершенно" равносильны. Хотя оно и очевидно проверяется с помощью таблиц истинности, с ним связан любопытный парадокс. Вот он. Биолог А выдвинул гипотезу: все вороны черные. Проверяя ее, он вышел во двор и обнаружил на дереве ворону. Она оказалось черной. Вроде бы у него есть основания радоваться - гипотеза подтверждается. Биолог Б переформулировал гипотезу так: все не- черные предметы - не вороны (применив наше правило контрапозиции) и не стал выходить во двор, а открыл холодильник и нашел там оранжевый предмет. Он оказался апельсином, а не вороной. Биолог Б обрадовался - гипотеза подтверждается - и позвонил биологу А. Тот удивляется - у него тоже есть апельсин в холодильнике, но с его точки зрения никакого отношения к его гипотезе апельсин не имеет$\dots$

Последнее (и очевидное) правило называется снятием двойного отрицания. $ \qedsymbol$

Задача 2.   Перечисленные эквивалентности соответствуют равенствам для множеств: например, первая гарантирует, что $P\cap Q=Q\cap P$ для любых множеств $P$ и $Q$. Какие утверждения соответствуют остальным эквивалентностям?

Задача 3.   Две формулы, содержащие только переменные и связки $\land$, $\lor$ и $\lnot$, эквивалентны. Докажите, что они останутся эквивалентными, если всюду заменить $\land$ на $\lor$ и наоборот.

Заметим, что далеко не все тавтологии имеют ясный интуитивный смысл. Например, формула $(p\to q)\lor (q\to p)$ является тавтологией (если одно из утверждений $p$ и $q$ ложно, то из него следует все, что угодно; если оба истинны, то тем более формула истинна), хотя и отчасти противоречит нашей интуиции - почему, собственно, из двух никак не связанных утверждений одно влечет другое? Еще более загадочна тавтология

\begin{displaymath} ((p\to q)\to p)\to p \end{displaymath}

(хотя ее ничего не стоит проверить с помощью таблиц истинности).


отступление о пользе скобок. На самом деле наши рассуждения содержат серьезный пробел. Чтобы обнаружить его, зададим себе вопрос: зачем нужны скобки в формулах? Представим себе, что мы изменим определение формулы, и будем говорить, что $P \land Q$ и $P \lor Q$ являются формулами для любых $P$ и $Q$. Останутся ли наши рассуждения в силе?

Легко понять, что мы столкнемся с трудностью при определении булевой функции, соответствующей формуле. В этом определении мы подставляли нули и единицы на место переменных и затем вычисляли значение формулы с помощью таблиц истинности для связок. Но теперь, когда мы изменили определение формулы, формула $p\land q \lor r$ может быть получена двумя способами  - из формул $p\land q$ и $r$ с помощью операции $\lor$ и из формул $p$ и $q\lor r$ с помощью операции $\land$. Эти два толкования дадут разный результат при попытке вычислить значение $0 \land 0 \lor 1$.

Из сказанного ясно, что скобки нужны, чтобы гарантировать однозначность синтаксического разбора формулы. Точнее говоря, верно такое утверждение:

Теорема 2. (однозначность разбора)   $\phantom{\hbox{\hskip1pt}}$Пропозициональная формула, не являющаяся переменной, может быть представлена ровно в одном из трех видов $(A\land B)$, $(A\lor B)$ или $\lnot A$, где $A$ и $B$ - некоторые формулы, причем $A$ и $B$ (в первых двух случаях) восстанавливаются однозначно.

Доказательство. Формальное доказательство можно провести так: определим понятие скобочного итога как разницы между числом открывающихся и закрывающихся скобок. Индукцией по построению формулы легко доказать такую лемму: Скобочный итог любой формулы равен нулю. Скобочный итог любого начала формулы неотрицателен и равен нулю, лишь если это начало совпадает со всей формулой, пусто или состоит из одних символов отрицания. Слова "индукцией по построению" значат вот что: мы проверяем интересующее нас утверждение для переменных, а также доказываем, что если оно верно для формул $A$ и $B$, то оно верно и для формул $(A\land B)$, $(A\lor B)$ и $\lnot A$.

После того как лемма доказана, разбор формулы проводится так: если она начинается с отрицания, то может быть образована лишь по третьему правилу. Если же она начинается со скобки, то надо скобку удалить, а потом искать начало, имеющее нулевой скобочный итог. Такое начало единственно. (Это легко проверить, используя лемму.) Тем самым формула разбирается однозначно. $ \qedsymbol$

В дальнейшем мы будем опускать скобки, если они либо не играют роли (например, можно написать конъюнкцию трех членов, не указывая порядок действий в силу ассоциативности), либо ясны из контекста.

Задача 4.   Польский логик Лукасевич предлагал обходиться без скобок, записывая в формулах сначала знак операции, а потом операнды (без пробелов и разделителей). Например, $(a+b)\times(c+(d\times e))$ в его обозначениях запишется как $\times+ a b+c \times d e$. Эту запись еще называют польской записью. Обратная польская запись отличается от нее тем, что знак операции идет после операндов. Покажите, что в обоих случаях порядок действий восстанавливается однозначно.

Next: 2. Полные системы связок Up: Логические формулы и схемы Previous: Логические формулы и схемы Contents:


Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования