Главная Промышленная автоматика.

0.:*. НЕКОТОРЫЕ понятия МАТЕМАТИЧЕСКОЙ ЛОГИКИ

(2) последнее утверждение последовательности является тем утверждением, которое надо доказать.

Утверждение, для которого можно найти доказательство, называется теоремой этой формальной системы. Очевидно, каждая аксиома формальной системы является теоремой.

Доказательство любой математической теоремы можно по крайней мере мысленно формулировать в этих терминах. Однако если детально проверять, является лн каждое утверждение аксиомой или получается из предыдущих утверждений с помощью исходных правил вывода, то доказательства всех теорем, кроме самых элементарных, станут слишком длинными. Задача нахождения доказательств такого вида сама по себе очень трудоемка даже для вычислительных машин.

Поэтому математики постоянно пользуются различными сокращениями, уменьшающими длину доказательства. Утверждения, ранее доказанные как теоремы, можно вставлять в доказательства. Можно опускать некоторые утверждения, когда (как мы надеемся) ясно, что происходит. Эти приемы практикуются в сущности везде, и данная книга не составляет исключения.

Известно, что невозможно дать универсальный метод доказательства теорем. Однако в последующих разделах мы упомянем о некоторых широко распространенных частных приемах.

0.3.2, Доказательство индукцией

Допустим, мы хотим доказать, что утверждение 5 (п) о натуральном числе п истинно для всех чисел из множества Л.

Если N конечно, то один из методов доказательства заключается в проверке того, что S [п) истинно для каждого значения п из N. Этот метод иногда называют доказательством исчерпыванием.

Если Л/бесконечное подмножество натуральных чисел, то можно применить простую математическую индукцию. Пусть Лр -наименьшее число из iV. Чтобы доказать, что S (п) истинно для всех nN, надо

(1) показать, что S (п) истинно (это называется базисом индукции),

(2) предполагая, что S (т) истинно для всех m < п, принадлежащих N, показать, что 5 (л) тоже истинно (это называется шагом индукции).

Пример 0.14. Пусть S{n) - утверждение

Мы хотим показать, что 5 (п) истинно для всех положительных целых чисел. Таким образом, N = {\, 2, 3, ...}.

Базис. Для л=1 имеем 1 = l.

Шаг индукции. Предполагая, что S (1), .,S (п) истинны (в частности, что 5 (л) истинно), имеем

l+3 + 5+...-f (2л--1)Н-(2 (Л4-1) -1) = /г + 2л+1 = (д+1)

так что S{n-\~\) тоже истинно.

Отсюда заключаем, что S{n) истинно для всех положительных целых чисел. □

Примеры доказательств индукцией, применяемых не к натуральным числам, читатель найдет в разд. 0.5.5.

0.3.3. Логические связки

Утверждения (теоремы) часто формулируются в виде „Р тогда и только тогда, когда Q" или „Р-необходимое и достаточное условие для причем Р и Q сами являются утверждениями. Термины если, тогда, только тогда, необходимо, достаточно и др. имеют точный смысл в логике.

Логическая связка-это символ, с помощью которого можно образовать утвержденпе из более простых утверждений. Примеры логических связок: или, и, не, влечет, причем яг-унарная связка (т. е. присоединяемая к одному утверждению), а остальные- бинарные связки (т. е. связывающие два утверждения). Если Р и Q - утверждения, то Р и Q, Р или Q, не Р и Р влечет Q-тоже утверждения.

Символ Л обозначает связку и, V-связку или, - не и

-влечет.

Существуют точные правила, определяющие истинность или ложность утверждения, содержащего логические связки . Например, утверждение Р и Q истинно только тогда, когда истинны оба утверждения Р и Q. Свойства логических связок можно резюмировать в виде таблицы, называемой таблицей истинности, в которой даны значения составных утверждений в зависимости от значений их компонент. На рис. 0.5 приведена таблица истинности для логических связок и, или, не и влечет.

Pv Q

Рис. 0.5. Таблицы истинности для связок и, или, не и влечет. 2 л. Ахо, Дж> Ульыан, т. 1 33



) Предполагается, что связка не предшествует связке влечет. Таким образом, правильная фразировка этого утверждения такая: (не Q) влечет {не Р). Вообще не предшествует и, и предшествует изи, или предшествует влечет.

жденне Я тогда и только тогда, когда Q часто пишут так: если Р то Q и обратно. Заметим, что утверждение него обращение имеют разные таблицы истинности.

УПРАЖНЕНИЯ

Определение. Хороший пример формальной математической системы - исчисление высказываний. Формально исчисление высказываний можно определить как систему состоящую из

(1) множества исходных символов,

(2) правил образования правильно построенных утверждений

(высказываний),

(3) множества аксиом,

(4) правил вывода.

(1) Исходными символами системы являются (, ), -->, и бесконечное множество символов переменных а:,, а.;, а, .... Символ можно трактовать как влечет, а символ--- - как не.

(2) Правильно построенное утверждение образуется в результате одного илн более применений следующих правил:

(а) Символ переменной является утверждением.

(б) Если А и В -утверждения, то (~ Л) и (Л-*В) -тоже утверждения.

(3) Пусть Л, В и С-утверждения. Тогда аксиомы системы - это утверждения

А1: {А-*{В~А))

А2: ((Л -> (В ~> С)) -> {{А В) (Л С))) A3: ((- В - Л) ((- В Л) В))

(4) Правилом вывода является схема заключения (modus ро-nens), т. е. аз утверждений (Л-+В) и Л можно вывести утверждение В.

Мы будем опускать некоторые скобки, когда это не вызывает недоразумений. Утверждение а->-а является теоремой системы of; в качестве ее доказательства можно взять последовательность утверждений:

(О (а-((а"->а)-а))-

.{{а-

.(а а))--(а -й)) полу-.а) и с = а.

чается из А2 при А -а, В ,

(ii) >fl)-a) Б силу А1.

(iU) (а~>(а-.а)) -(а->й) по схеме заключения из (О и (а).

(iv) а-{а-а) из А1.

v) а~а по схеме заключения из (т) и (iv).

*0.3.I. Докажите, что (-стемы (5.

.а)-а является теоремой си-

Из ЭТОЙ таблицы видно, что Р-ложно только тогда, когда Р истинно, а Q ложно. Может показаться несколько странным, что если Р ложно, то Р влечет Q всегда истинно независимо от значения Q. Но в логике это обычное явление: если гипотеза ложна, из нее следует все, что угодно.

Рассмотрим теперь утверждение Р если и только если Q. Это утверждение состоит из двух частей: Р если Q и Р только если Q. Вместо Р если Q обычно говорят если Q то Р - это лишь другой способ выражения утверждения Q влечет Р. Вместо Р только если Q часто говорят Р только тогда, когда Q.

В действительности следующие шесть утверждений равносильны:

(1) Я влечет Q,

(2) если Р то Q,

(3) Р только если Q,

(4) Р только тогда, когда Q,

(5) Q~ необходимое условие для Р,

(6) Р-достаточное условие для Q.

Чтобы показать, что утверждение Р тогда и только тогда, когда Q (или Р если и только если Q) истинно, нужно показать, что одновременно Q влечет Р я Р влечет Q. Таким образом, утверждение Р тогда и только тогда, когда Q истинно в точности тогда, когда Р я Q либо оба истинны, либо оба ложны.

Существует несколько различных способов показать, что утверждение Р влечет Q всегда истинно. Один из них заключается в том, чтобы показать, что утверждение не Q влечет не Р) всегда истинно. Читателю следует проверить, что не Q влечет не Р имеет точно ту же таблицу истинности, что и Р влечет Q. Утверждение не Q влечет не Р называется контрапозицией утверждения Р влечет Q.

Один из важных методов доказательства - доказательство от противного, иногда называемое косвенным доказательством илн приведением к противоречию. Чтобы этим методом показать, что Р влечет Q истинно, нужно показать, что утверждение не Q и Р влечет ложь истинно. Иначе говоря, мы пре/1Полагаем, что Q ложно, и если из предположения, что Р истинно, мы сможем получить заведомо ложное утверждение, то Р влечет Q должно быть истинно.

Утверждением, обратным к утверждению если Р то Q (или его обращением), называется утверждение если Q то Р. Утвер-



(ассоциативность)

0.3.2. Тавтологией называется утверждение, истинное для всевозможных значений входящих в него переменных. Покажите, что каждая теорема системы сУ является тавтологией. Указание: Докажите это индукцией по числу шагов вывода, необходимых для получения теоремы.

**0.3.3. Докажите обращение утверждения, сформулированного в упр. 0.3.2, а именно: каждая тавтология является теоремой. Таким образом, простой метод выяснения того, является ли утверждение исчисления высказываний теоремой, заключается в том, чтобы выяснить, является ли это утверждение тавтологией .

0.3.4. Постройте таблицу истинности утверждения если Р то если Q то R.

Определение. Булеву алгебру можно трактовать как систему, в которой можно комбинировать переменные, принимающие значения истина и ложь, с помощью логических связок, неформально интерпретируемых как и, или и нет. Формально булева алгебрй-это множество В вместе с операциями • {и), + {или) и {не). Аксиомами булевой алгебры служат следующие утверждения: Для всех а, Ь и с, принадлежащих В,

(1) Qf (Ы-с) = (а + &)+с а-{ЬС){а-Ь)С,

(2) а-\-b bа (коммутативность) a-b = b-a,

(3) й - (/? + с) (а. й) + (fl. с) (дистрибутивность) а+{Ь.с){аА-Ь)-{а-с).

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

(4) й + О-а а-\ а,

(5) а-{-а\ а-а = 0.

Правилом вывода является замена равного равным.

*0.3.5. Покажите, что следующие утверждения являются теоремами в любой булевой алгебре: (а) О-!.

(6) a-f (Ь-й)-а + Ь,

(в) а = а.

Какова неформальная интерпретация этих теорем? 36

0.3.6. Пусть Л-множество. Покажите, что (Л)-булева алгебра, если операциями -!-, и " служат U, П и дополнение относительно универсального множества Л.

**0.3.7. Пусть В -булева алгебра и :В=п. Покажите, что rt -2" для некоторого натурального числа т.

0.3.8. Докажите индукцией, что

0.3.9. Докажите индукцией, что

(1+2+...+д)-1» + 2+...4-л5 *0.3.10. Что неверно в следующем рассуждении? Теорема. Все кошки одного цвета.

Доказательство. Пусть Л - множество, состоящее из п кошек, п\. ,Докажем* индукцией по л, что все кошки в А одного цвета.

Базис. Если I, то все кошки в Л, очевидно, одного цвета.

Шаг индукции. Предположим, что если Л-любое множество, состоящее из п кошек, то все они одного цвета. Пусть Л - множество, состоящее из д+1 кошек, л1. Выбросим из Л одну кошку. Тогда у нас останется множество Л", состоящее нз п кошек, которые по предположению индукции все одного цвета. Выбросим из Л" вторую кошку и вернем тда ранее выброшенную. Снова имеем множество, состоящее из п кошек, которые по предположению индукции все одного цвета. Так как две выброшенные кошки должны иметь один и тот же цвет, то множество Л должно состоять из кошек одного цвета. Таким образом, в любом множестве, состоящем из л кошек, все они одного цвета. □

*0.3.11. Пусть 7 -полный порядок на множестве Л и S (а) - утверждение об элементе аА. Предположим, что если S {Ь) истинно для всех таких Ьфа, что bRa, то S (а) тоже истинно. Покажите, что тогда S{a) истинно для всех а € Л. Заметим, что это -обобщение принципа простой математической индукции.

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

0.3.13. Покажите, что существуют 16 бинарных логических связок.

0.3.14. Два логических утверждения эквивалентны, если они имеют одинаковые таблицы истинности. Покажите, что

(а) {Р /\0) эквивалентно Р \/ Q,

(б) ~ (Р v Q) эквивалентно Р /\- Q.





0 1 2 3 [4] 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0037