Роберт столл множества. Логика. Аксиоматические теории icon

Роберт столл множества. Логика. Аксиоматические теории



НазваРоберт столл множества. Логика. Аксиоматические теории
Сторінка8/13
Ю. А. Шихановича
Дата конвертації16.01.2013
Розмір3.45 Mb.
ТипДокументи
скачать >>>
1   ...   5   6   7   8   9   10   11   12   13

Примеры В


1. Докажем, что


|=


Объяснение цифр, стоящих слева в нижеследующих строках, дано

дальше:

{1} (1) A→C правило р;

{1} (2) правило t; |= (1) - (2) на основании

тавтологии 11;

{3} (3) B→D правило р;

{3} (4) правило t; |= (3) - (4) на основании

тавтологии 11;


[98]


{1,3} (5) правило t; |= (2)(4)→(5) на основа-

нии тавтологии 7;

{6} (6) АВ правило p;

{1, 3, 6} (7) правило t; |= (5)(6)→(7) на основа-

нии тавтологии 1;


Цифры в круглых скобках рядом с каждой формулой обозначают и номер формулы, и номер строки вывода, в которую она входит. Номера в фигурных скобках в каждой строке соответствуют посылкам, от которых зависит формула в этой строке, т. е. формула в строке п есть логическое следствие из посылок, обозначенных номерами в фигурных скобках в этой строке. Так, формула в строке 5 есть логическое следствие посылок в строках 1 и 3, а формула в строке 7 есть логическое следствие посылок в строках 1, 3 и 6, т. е. всех посылок. В частности, в строке, заключающей в себе посылку, в фигурных скобках слева стоит как раз номер этой строки, поскольку такая формула не зависит от других строк. Фигурные скобки применены в номерах слева умышленно, так как такое обозначение напоминает о том, что формула в этой строке есть логическое следствие совокупности посылок, обозначенных этими номерами.

Перепишем теперь помещенный выше вывод, вводя при этом некоторые практические сокращения. Читателю предлагается в этой записи добавить номера использованных тавтологий:

{1} (1) A→С p

{1} (2) 1 t

{3} (3) B→D p

{1, 3} (4) 3 t

{6} (5) 2, 4t

{1, 3, 6} (6) CD 5, 6t

[101]


2.5. Исчисление высказываний. Приложения


Обратимся теперь к обыденным приложениям теории вывода, рассмотренной в предыдущих параграфах. Обычно в число условий, сопутствующих изложению какого-либо доказательства, входит наличие слушателя, имеющего право принимать или отвергать утверждение, что некоторое высказывание В представляет собой логическое следствие высказываний А1, А2,....., Аm. В этом случае самостоятельно рассуждающий человек захочет доказать либо, что B — логическое следствие из всех А,


[102]


либо, что рассуждение не логично, т. е. что можно приписать рассматриваемым простым компонентам такие истинностные значения, что одновременно все А получат значения Т, а В — значение F. Самый подходящий способ решения всего вопроса состоит в следующем: принять, что истинностное значение высказывания В есть F, а каждого из А — Т, и проанализировать, что получается из необходимого приписывания истинностных значений для простых компонентов. Такой анализ приводит либо к противоречию, доказывающему, что В есть логическое следствие из всех А, либо к приписыванию для каждого из простых компонентов такого истинностного значения, что все допущения будут удовлетворяться: последнее подтверждает, что это рассуждение не логично.

Изложенный здесь метод доказательства того, что некоторая формула есть логическое следствие других, обесценивает метод, выдвинутый в предшествующем разделе, поскольку второй метод так быстро приводит к результату. Однако первый метод имеет свои достоинства (во всяком случае, с педагогической точки зрения). Например, он ведет к ознакомлению с тавтологиями теоремы 2.4. Случаи использования тавтологий весьма обычны в математических доказательствах, и читателю следует приобрести навык в распознавании тавтологий, как таковых. Например, тавтология 20 оправдывает призывное заключение, что если контрапозиция высказывания есть логическое следствие из А, то и — тоже логическое следствие из А.


Примеры А


I. Рассмотрим следующее рассуждение.

Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встану рано, то я буду вынужден довольствоваться пятью часами сна. Я просто не в состоянии обойтись пятью часами сна. Следовательно, я должен или пропустить завтра первое занятие, или не ходить на танцы.

Чтобы исследовать, справедливо ли это рассуждение, символизуем его, заменяя простые высказывания буквами. Пусть ^ С означает «Я иду (пойду) завтра на первое занятие»; G — «Я должен встать рано»; D — «Я иду (пойду) вечером на танцы»; S — «Я лягу спать поздно», а Е — «Я могу обойтись пятью часами сна». Тогда посылки можно записать символически в следующем виде:









[103]


а искомое заключение будет





Следуя описанному выше методу анализа, примем, что имеет значение F, а каждая из посылок имеет значение Т. Тогда и С, и D должны иметь значение Т. Далее, как следует из первой посылки, и G, и S имеют значение Т. Это и вторая посылка влекут за собой, что Е имеет значение Т. Но это противоречит допущению, что третья посылка имеет значение Т.

Таким образом, доказано, что есть логическое следствие имеющихся посылок.

2. Предположим, что дано следующее утверждение:


|=


Примем, что имеет значение F, а каждая из посылок —Т. Первое допущение удовлетворяется, если приписать В значение Т, а D — значение F. В таком случае С имеет значение F и А — значение Т. При таких истинностных значениях каждая из посылок получает значение Т, а принимает значение F. Следовательно, рассуждение не логично.

С изложенным выше связан, но отличается от него вопрос о непротиворечивости множества высказываний, которое предлагается рассматривать как систему посылок для вывода. Множество {А1, А2,....., Аm} высказываний непротиворечиво (в исчислении высказываний), если существует по меньшей мере одно такое распределение истинностных значений простым компонентам, что все А одновременно получают значение Т. Противоречивость множества высказываний есть отрицание его непротиворечивости. Так, {А1, А2,....., Аm} есть противоречивое множество, если при всяком распределении истинностных значений простым компонентам по меньшей мере одно из А получает значение F. Короче говоря, {А1, А2,....., Аm} непротиворечиво если имеет значение Т по меньшей мере для одной комбинации приписываемых простым компонентам истинностных значений, и {А1, А2,....., Аm} противоречиво, если имеет значение F для всех комбинаций истинностных значений, приписываемых простым компонентам.

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


[104]


Теорема 2.8. Множество высказываний {А1, А2,....., Аm} противоречиво, если из него в качестве логического следствия можно вывести противоречие.

Доказательство. Примем, что для некоторой формулы В А1, А2,....., Аm |= . Тогда |= и искомое заключение следует из истинностной таблицы для импликации.

Противоречия играют также важную роль в методе косвенного доказательства (называемого также доказательством от противного, или доказательством reductio ad absurdum). Основой такого вида доказательства служит следующий результат:

Теорема 2.9. А1, А2,....., Аm |= В, если в качестве логического следствия из А1, А2,....., Аm и можно вывести противоречие.

Доказательство. Примем, что для некоторой формулы С А1, А2,....., Аm , |= . Тогда А1, А2,....., Аm |= . Рассмотрим теперь такое распределение истинностных значений, приписываемых данным простые компонентам, что каждая А принимает значение Т. Тогда имеет значение Т. Это и то, что получает значение F, влечет за собой для значение F, и, следовательно, В имеет значение Т.


[105]


Упражнения


Применить рассмотренный в этом параграфе метод для доказательства логичности или нелогичности рассуждений, приведенных в упр. 1 – 12. если рассуждение логично, построить для него доказатель-


[106]


ство. Пользуйтесь везде предложенными в тексте буквами для символической записи рассуждения.

1. Я пойду домой (H) или останусь здесь и выпью стаканчик (S). Я не пойду домой. Следовательно, я останусь и выпью.

2. Если Джон ляжет сегодня поздно (S), он будет утром в отупении (D). Если он ляжет не поздно, то ему будет казаться, что не стоит жить (L). Следовательно, или Джон будет завтра в отупении, или ему будет казаться, что не стоит жить.

3. Заработная плата возрастет (W) только, если будет инфляция (J). Если будет инфляция, то увеличится стоимость жизни (^ С). Заработная плата возрастет. Следовательно, увеличится стоимость жизни.

4. Если 2 — простое число (Р), то это наименьшее простое число (L). Если 2 — наименьшее простое число, то 1 не есть простое число (N). Число 1 не есть простое число. Следовательно, 2 — простое число.

5. Джон или переутомился (E), или болен (S). Если он переутомился, то он раздражается (^ С). Он не раздражается. Следовательно, он болен.

6. Если завтра будет холодно (С), я надену теплое пальто (H), если рукав будет починен (S). Завтра будет холодно, а рукав не будет починен. Следовательно, я не надену теплое пальто.

7. Если исход скачек будет предрешен сговором (R) или в игорных домах будут орудовать шулеры (^ H), то доходы от туризма упадут (D), И город пострадает (S). Если доходы от туризма упадут, полиция будет довольна (Р). Полиция никогда не бывает довольна. Следовательно, исход скачек не предрешен сговором.

8. Если Доджеры выиграют (D), то Лос-Анджелес будет торжествовать (L), а если выиграет Уайт-Сокс (^ W), то торжествовать будет Чикаго (С). Выиграют или Доджеры, или Уайт-Сокс. Однако если выиграют Доджеры, то Чикаго не будет торжествовать, а если выиграет Уайт-Сокс, то не будет торжествовать Лос-Анджелес. Итак, Чикаго будет торжествовать тогда и только тогда, когда не будет торжествовать Лос-Анджелес.

9. Или Сэлли и Боб одного возраста (^ S), или Сэлли старше Боба (О). Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста (N). Если Сэлли старше Боба, то Боб старше Уолтера (W). Следовательно или Нэнси и Боб не одного возраста, или Боб старше Уолтера.

10. Если 6 — составное число (^ S), то 12 — составное число (W). Если 12 — составное число, то существует простое число, большее чем 12 (Р). Если существует простое число больше 12, то существует составное число больше 12 (С). Если 6 делится на 2 (D), то 6 — составное число. Число 12 составное. Следовательно, 6 — составное число.


[107]


11. Если я поеду автобусом (^ В), а автобус опоздает (L), то я пропущу назначенное свидание (М). Если я пропущу назначенное свидание и начну огорчаться (D), то мне не следует ехать домой (Н). Если я не получу эту работу (I), то я начну огорчаться и мне следует поехать домой. Следовательно, если я поеду автобусом и автобус опоздает, то я получу эту работу.

12. Если Смит победит на выборах (^ N), он будет доволен (Н), а если он будет доволен, то он плохой борец в предвыборной кампании (С). Но если он провалится на выборах, то потеряет доверие партии (Р). Он плохой борец в предвыборной кампании, если он потеряет доверие партии. Если он плохой борец в предвыборной кампании, ему следует выйти из партии (R). Смит или победит на выборах, или провалится. Следовательно, ему нужно выйти из партии.


[108]


^ 2.6. Исчисление предикатов. Символизация обычного языка


Теория вывода, которую дает исчисление высказываний, недостаточна для математики, да и для обычных рассуждений. Например, из посылок:


«Всякое рациональное число есть действительное число»,

«3 есть рациональное число»,


конечно, можно вывести заключение


«3 есть действительное число».


Однако логичность этого рассуждения нельзя установить в исчислении "высказываний. Объясняется это тем, что исчисление высказываний ограничивается структурой предложений в терминах предложений-компонентов, а приведенный выше вывод требует анализа структуры предложения в смысле связи субъекта и предиката, как это делается в грамматике. Иными словами, исчисление высказываний не разделяет предложение на достаточно «тонкие» составляющие для удовлетворения" большинства целей. С другой стороны, оказывается, что, добавив три дополнительных логических понятия, называемых термами, предикатами и кванторами, можно символизовать очень многое в обычном и математическом языке так, что становится возможным анализ рассуждения. Опишем эти три понятия.

В математике практикуется введение букв вроде х или у, занимающих место названий отдельных предметов. Например, чтобы описать те действительные числа, квадраты которых минус сами числа равны 12, мы пишем равенство х2 — x =12, рассматривая таким образом х как заместитель названия любого такого числа (пока неизвестного). Или, при обычном употреблении х, оно в равенстве


sin2 x + cos2 х = 1


замещает название произвольного действительного или даже комплексного числа. При таком применении, как в равенстве х2 — x =12, мы привыкли называть х неизвестным, а в равенстве sin2 x + cos2 х = 1 обычно х называют переменной. Мы будем пользоваться буквами из второй половины алфавита при символизации обычного языка подобно


[109]


тому, как это сделано выше, т. е. в качестве неизвестного или переменной. В логике принято употреблять слово «переменная» в обоих случаях, и вопрос, должно ли х служить переменной в интуитивном понимании слова или неизвестным, решается в зависимости от формы выражения, в которое x входит. Поскольку в конце концов мы намерены освободить все символы от какого бы то ни было смыслового значения, проще всего сделать это с самого начала в отношении переменных. Мы достигаем этого, определяя предметную переменную как букву или букву с нижним или верхним индексом. Переменные образуют один из классов термов.

Мы будем также пользоваться буквами и символами в качестве названий конкретных, вполне определенных предметов, т. е. применять буквы и символы вместо собственных имен. Применяемые с этой целью буквы и символы называются предметными постоянными. Например, «3» есть предметная постоянная, так как это название числа 3. «Уинстон Черчилль» тоже предметная постоянная. Чтобы сделать обозначение кратким, мы будем пользоваться вместо собственного имени, если для него кет общепринятого символа, одной из первых букв алфавита. Например, можно положить, что


а = Уинстон Черчилль,


если мы хотим перевести в символическую форму предложение


«Уинстон Черчилль был великим государственным деятелем».


Собственные имена часто даются в виде «описания», которое мы считаем названием предмета, по самой своей структуре недвусмысленно обозначающим этот предмет. Например,


Первый президент Соединенных Штатов


и


Такое действительное число х, что для всех действительных чисел у


xy = y


представляют собой описания. Если положить


b — Георг Вашингтон,


то мы можем написать


b = первый президент Соединенных Штатов.


[110]


Далее, мы имеем


1= такое действительное число х, что для всякого у ху = у.


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

Перейдем теперь к понятию предиката. В грамматике предикат (сказуемое) есть то слово (или несколько слов) в предложении, которое выражает, что говорится о субъекте (подлежащем): например, «есть действительное число», «имеет черный цвет», «завидует». В логике слово «предикат» употребляется в более общем смысле, чем в грамматике. Дело в том, что, вводя в предикате переменную, замещающую нужный предмет (например, «х есть действительное число»), мы получаем «высказывательную функцию» в том смысле, что для каждого значения переменной х (из соответствующей области определения) результат есть высказывание. Хотя в грамматике «Джон любит» не будет предикатом, но если ввести букву x, заменяющую объект (любви Джона), т. е. написать


Джон любит х,


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


х меньше у, у делится на х, z есть сумма х и у.


Результатом является понятие об п - местном предикате как о выражении, обладающем тем свойством, что, приписав значения переменным из соответствующих областей определения, мы получаем высказывание. Для удобства в число значений п включаем и 0, понимая под 0-местным предикатом высказывание.

Рассмотрим теперь примеры перевода в символическую форму.


Примеры А


1. Предложение

Каждое рациональное число есть действительное число (1)

можно перевести в следующее:

Для любого х, если х есть рациональное число, то х есть действительное число. (2)


[111]


В обычной грамматике «есть действительное число» — предикат в предложении (1). В переводе (2) дополнительный предикат «х есть рациональное число» заменяет имя нарицательное «рациональное число». Обозначая через Q(х) «х есть рациональное число», а через R(х) «х есть действительное число», мы можем выразить (2) в символической форме в виде


Для любого х, Q(х) → R (х). (3)


Далее, высказывание «3 — рациональное число» можно записать символически так:


Q(3). (4)


С использованием введенных пока символов (3) и (4) дают переводы посылок рассуждения, приведенного в начале этого параграфа.


2. Предложение

Некоторые действительные числа являются рациональными

можно перевести так:


Существует такое х, что х — действительное число и

х — рациональное число.


Пользуясь введенными выше предикатами, можно теперь символически записать наше предложение в виде


Существует такое х, что R(x)Q(x). (5)


3. Предложение

Существует такое х, что R(x) → Q(x). (6)


должно иметь тот же смысл, что и


Существует такое х, что (x), (7)


поскольку мы только заменили «R(х) → Q(х)» его эквивалентом «». Можно (7) перевести теперь словами так:

Существует нечто, которое или не есть действительное число, или есть

рациональное число.

Конечно, это высказывание [имеющее тот же смысл, что и (6)] не имеет того же смысла, что и (5). В самом деле, как только мы укажем предмет, не являющийся действительным числом, мы должны будем согласиться с (6). Резюмируя, можно сказать: смыслы (6) и (5) различны.


На основании принятых допущений, если переменным предиката приписать подходящие значения, то мы получим высказывание. Например, если S(x) обозначает «x есть второкурсник», то из этого предиката


[112]


получается высказывание «Джон есть второкурсник». Высказывание можно получить из S(x) также, если предпослать ему выражение «Для всякого x».


Для всякого х х есть второкурсник. (8)


Несомненно, мы предпочли бы перефразировать (8) в виде:


Всякий человек — второкурсник. (9)


Выражение «для всякого х» называется квантором общности. Мы считаем «для всякого х», «для всех x» и «для каждого x» выражениями, имеющими одинаковый смысл, и символически записываем любое из них

в виде


или (x).


Пользуясь этим обозначением, мы можем записать (8) или (9) в следующей символической форме:


(x)S(x).


Подобным же образом, предпослав S(x) выражение «существует x (такое, что)», получаем высказывание, имеющее тот же смысл, что и «существуют второкурсники». Выражение «существует x» называется квантором существования. Мы считаем «существует х», «для некоторых x», «по меньшей мере для одного х» выражениями, имеющими одинаковый смысл, и символически записываем любое из них в виде


.


Таким образом, «S(x)» представляет собой в символической форме предложение «существуют второкурсники».

В каждом из примеров А квантор стоит не только перед предикатом, но и перед «формой от x»26; под этим мы будем понимать временно выражение, составленное из одноместных предикатов Р(х), ... с использованием сентенциональных связок. Применяя обозначение, введенное для квантора общности, мы можем теперь записать предложение «всякое рациональное число есть действительное число» в окончательном виде:


(x)(Q(x)R(x)). (10)


Возможно, читатель уже заметил, что это просто значит то же. что и QR. В самом деле, если вспомнить определение «отношения включения» для множеств, то станет ясно, что (10) представляет случай, под-


[113]


ходящий под это определение. Далее, отметим, что (10) типично для высказываний вида «всякое то-то есть то-то».

Подобным же образом предложение «некоторые действительные числа являются рациональными» можно перевести в символическую форму следующим образом:


(11)


Смысл этого предложения сводится просто к тому, что RQ — непустое множество; это — симметричная форма первоначального предложения. Обычная ошибка начинающих состоит в следующем: исходя из того, что высказывание вида «всякое то-то есть то-то» можно символически записать в виде (10), они заключают, что высказывание «некоторые то-то суть то-то» можно символически записать как





Однако, как отмечено в третьем из примеров А, такое высказывание имеет тот же смысл, что и





Мы должны признать это истинным, как только будет указан предмет, который не является действительным числом. Следовательно, выражение не имеет отношения к тому, что мы хотели сказать, т. е. что некоторые действительные числа являются рациональными.

1   ...   5   6   7   8   9   10   11   12   13



Схожі:

Роберт столл множества. Логика. Аксиоматические теории iconСэм Столл 100 собак, которые изменили цивилизацию: Самые знаменитые в истории собаки
«Сэм Столл. 100 собак, которые изменили цивилизацию: Самые знаменитые в истории собаки»: Астрель-Аст; Москва; 2009
Роберт столл множества. Логика. Аксиоматические теории iconПроект володимира кулеба роберт (Боббі) Чарльтон «сер»
Його гарматні удари з лівої ноги приводили в трепет воротарів усього світу. Його працездатність і невтомність вражали. Його бездоганна...
Роберт столл множества. Логика. Аксиоматические теории iconИнформационное письмо
Целью конференции является рассмотрение на конкретном материале теоретических оснований, методов и приемов наименее разработанного...
Роберт столл множества. Логика. Аксиоматические теории iconЧех Л. А., и о. зам директора научной библиотеки
Среди множества корпоративных проектов, организуемых в современном библиотечно-информационном сообществе, выделяется динамичностью...
Роберт столл множества. Логика. Аксиоматические теории iconБухгалтерский учет в Украине: от теории к практике
Редакция издания «Баланс» просит Вас принять участие в анкетировании, с целью определения читательских потребностей и ожиданий, повышения...
Роберт столл множества. Логика. Аксиоматические теории iconУдк 811. 161. 2’25: 811. 161. 1 Ббк 81. 2 Рецензенты
Гусева Е. И. Динамика термина: Заимствование. Обновление метаязыка. Развитие лингвистической теории. – Мариуполь, Ультрамарин, 2012....
Роберт столл множества. Логика. Аксиоматические теории iconИордания и Израиль две страны, словно затейливая мозаика, искустно собранная из множества ярких и неповторимых кусочков. Находясь на перекрестке христианства, ислама и иудаизма, эти страны из века в век бережно хранят на своей земле святые места трех великих религий.
Иордания и Израиль две страны, словно затейливая мозаика, искустно собранная из множества ярких и неповторимых кусочков. Находясь...
Роберт столл множества. Логика. Аксиоматические теории iconIii международная научно-практическая конференция "Приоритетные научные направления: от теории к практике" (нн-3)
Приглашаем Вас принять участие в студенческой международной научно-практической конференции студентов, магистрантов, аспирантов и...
Роберт столл множества. Логика. Аксиоматические теории iconДетский лагерь "Спартак"
Старинная часть города архитектурный заповедник. Ее часто называют 'Харманит' из-за множества мельниц 'харманов', которы находились...
Роберт столл множества. Логика. Аксиоматические теории iconЧто же такое аудио-визуальная стимуляция?
«сегментов пазлов» ложится в тему, как и почему работают приборы аудио-визуальной стимуляции. Следующие теории появились благодаря...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©sm.znaimo.com.ua 2000-2015
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи

Разработка сайта — Веб студия Адаманов