Введение в логику

Введение в логику

                С.ИНТУ ИТ





    У НАЦИОНАЛЬНЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ



            Введение в логику


2-е издание, исправленное

Биллиг В.А.



Национальный Открытый Университет “ИНТУИТ”
2016


2

Введение в логику/ В.А. Биллиг - М.: Национальный Открытый Университет “ИНТУИТ”, 2016
В курсе проводится краткий исторический обзор логики как науки, рассматривается дедуктивный и индуктивный методы вывода и их применение в повседневной жизни.
Достаточно подробно рассматриваются базисные математические понятия - множества, отношения, функции. Наряду с традиционными для школьного курса понятиями логики высказываний -бинарных логических функций, построения таблиц истинности, законов логики высказываний, рассматриваются и более сложные вопросы, такие как, например, конъюнктивные и дизъюнктивные нормальные формы записи логических формул. Изложение теоретического материала сопровождается рассмотрением конкретных логических задач.
(c) ООО “ИНТУИТ.РУ”, 2014-2016
(c) Биллиг В.А., 2014-2016

3

        Исторический обзор

Видео

Логика возникла в те времена, когда человечество приобрело речь и овладело словом. Название “логика” связано с греческим словом “логос”, означающим “слово”, “речь”, “мысль”. Логику можно рассматривать как науку о рассуждениях. Логика изучает, насколько корректно строятся наши рассуждения. Целью логического вывода является установление истинности некоторого рассуждения. Но истинность зависит не только от корректности вывода, но и от истинности исходных положений, лежащих в основе вывода.

Жрецы первобытных времен, философы античного периода давали пример убедительных рассуждений. Философские школы учили логике. Философские диспуты, характерные для этих школ, ставили целью доказать или опровергнуть некоторое положение. Выражение “в споре рождается истина” берет начало от этих диспутов. Эти диспуты не сводятся к спорам “а ты кто такой!”. Для победы в диспуте важна была логика рассуждений. Не менее важно было и то, какие истины лежали в основе вывода.

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

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

Конфуций родился в 551 г. до н. э., а умер в 479 г. до н. э. Учитель Кун, как называют Конфуция в Китае, имел много учеников, которые сохранили высказывания Конфуция в книге “Беседы и суждения”, дошедшей до наших дней. Конфуцианство почитаемо не только в Китае, но и во всем современном мире, - институты Конфуция созданы во многих странах.

Вот некоторые примеры высказываний Конфуция, которые следует считать истинными:

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

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

Кто из школьников не знает имени великого Пифагора, родившегося на 20 лет раньше Конфуция (годы жизни: 570 г. до н. э. - 490 г. до н. э.), основавшего пифагорейскую


4

философскую школу. Знания в школе передавались устно, к счастью, один из учеников Пифагора составил три книги с записями его учения.

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

  в В основе всех вещей лежит число.
  • Познать мир — значит познать управляющие им числа.

Примером такого знания является знаменитая теорема Пифагора - “В прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов катетов”.

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

Через 10 лет после смерти Конфуция в Афинах родился Сократ (годы жизни: 469 г. до н. э. - 399 г. до н. э.), имевший многочисленных учеников. Подобно Пифагору и Конфуцию, Сократ не вел записей своих бесед с учениками. Но и то, чему учил Сократ, дошло до наших дней благодаря записям его учеников, прежде всего, Платона.

Платон (годы жизни: 428 г. до н. э. - 348 г. до н. э.) долгие годы был учеником Сократа. Являясь одновременно почитателем Пифагора, он во время своих путешествий посетил пифагорейскую школу. Известно, что он купил у ученика Пифагора рукописи с изложением учения Пифагора за огромные по тем временам деньги. В 40 лет Платон основал академию, состоявшую из учителей и учеников. Многочисленные книги, написанные Платоном, идеи, высказанные в этих книгах, оказали большое влияние на развитие философской мысли.

Аристотель (годы жизни: 384г. до н. э. - 322 г. до н. э.) двадцать лет провел в академии Платона. Затем основал собственную школу, названную лицеем. Аристотелем написаны множество книг по самым разным областям знания.

Философ, прежде всего, математик Евклид, современник Аристотеля, точные годы жизни которого неизвестны, создал “Начала” - фундаментальный труд, состоящий из 12 томов. Первый из этих томов завершала теорема Пифагора. “Начала” Евклида стали примером построения формальных математических систем, в основе которых лежит базис из аксиом - положений, которые признаются истинными и не требуют доказательств. На основе аксиом доказываются первые теоремы. Используя уже доказанные теоремы, доказываются новые теоремы, - так строится математическая теория. Более 2000 лет труд Евклида являлся основным учебником по геометрии (заметьте, современные учебники живут не более десяти лет!). Математика является примером рассуждений, где все положения математической теории, за исключением аксиом теории, строго доказываются.

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


5

считается Аристотель. Основы логики изложены в его труде “Органон” (что означает: инструмент, метод), содержащем 6 книг.

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

  з Закон “Исключающего третьего”. Истинно либо высказывание Q, либо его отрицание, третьего не дано. Этот закон справедлив в формальной логике, но не всегда справедлив в естественной речи. Аристотелю были хорошо знакомы многочисленные парадоксы, такие как, например “парадокс лжеца”, суть которого в следующем. Будем называть лжецом того, кто всегда говорит неправду. Пусть некий человек говорит “я лжец”. Если это высказывание истинно, то из сути высказывания следует, что говорящий - “лжец”. Но если он лжец, то он солгал и, следовательно, он не лжец, так что высказывание ложно. Парадокс лжеца не разрешим в формальной логике, где действует закон “Исключающего третьего”.
  • Закон “Непротиворечивости”. Невозможно одновременно утверждать, что Q верно, и что Q неверно”.

Аристотель исследовал и методы вывода истинных утверждений: дедукцию и индукцию.

Установление истинности - одна из важнейших задач, которые приходится решать человеку. Математика дает пример строгости в установлении истинности теорем математики, - каждая теорема строго доказывается. Но установление истинности важно не только в математике, но и в нашей повседневной жизни. В суде, когда решается вопрос, - виновен или невиновен подсудимый. В медицине, когда предлагается новое лекарство, - обладает ли оно вредными побочными эффектами. В технике, когда решается вопрос об эффективности предлагаемого решения. Наконец, тогда, когда решается вопрос, соответствует ли наш поступок, наши действия, тем этическим принципам, которые человечество признает истинными.

У художника Ге есть знаменитая картина “Что есть истина?”, на которой изображен римский прокуратор Пилат, задающий этот вопрос Христу, приведенному к прокуратору на суд. Заповеди христианства, уже в течение тысячелетий являются истинами, которыми следует руководствоваться человеку в своих деяниях.


6

        Логический вывод - индукция

Видео

Целью логического вывода является установление истинности нового утверждения, исходя из истинности ранее установленных утверждений. Крайне важно умение делать корректные выводы. Но истинность конечного утверждения зависит не только от корректности вывода. Если первоначальные утверждения, лежащие в основе любого вывода не верны, то и истинность заключительного утверждения не может считаться доказанной. Из неверных фактов и неверных правил нельзя вывести корректные следствия, каким бы корректным ни был вывод. С другой стороны, из истинных фактов и правил, нельзя сделать корректные заключения, если не пользоваться корректными правилами вывода.

        Индукция - полная и частичная

Индуктивный метод вывода - это метод вывода “от частного к общему”. Из истинности некоторых частных утверждений делается вывод об истинности общего случая. Индукция бывает полной, гарантирующей истинность вывода, и неполной, когда истинность не гарантируется. Пусть X - некоторое конечное множество элементов - Xi, X2,... Xn. Если удается доказать справедливость свойства Q для всех Xi (i = 1...n), то справедливо общее утверждение, что множество X обладает свойством Q.

Такой способ доказательства является полной индукцией.

Рассмотрим некоторые примеры неполной индукции.

Пример 1:

  • Число 5 нацело делится на 5;
  • Число 15 нацело делится на 5;
  • Число 25 нацело делится на 5;
  • Гипотеза: Все числа, заканчивающиеся на 5, нацело делятся на 5.

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

Если число N заканчивается на 5, то его можно представить в виде: N = k * 10 + 5, где k - целое число. Тогда N / 5 = 2 * k + 1 - целое число, что и доказывает истинность гипотезы.

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


7

Пример 2:

  • Нечетное число 3 простое число;
  • Нечетное число 5 простое число;
  • Нечетное число 7 простое число;
  • Гипотеза: Все нечетные числа - простые числа.

Гипотеза легко опровергается. Достаточно привести один пример нечетного числа, не являющегося простым. Таковым, например, является следующее нечетное число 9.

Пример 3: Числа градины.

Рассмотрим целое число N. Будем выполнять над ним следующие преобразования, если N четно, то новое значение равно N/2, иначе новое значение равно 3*N + 1. Процесс преобразования будем продолжать. Процесс завершается, если на некотором шаге значение N станет равным 1, иначе он продолжается до бесконечности (возможен цикл или бесконечное возрастание N).

  • При N =  2 процесс завершается: 2 -> 1;
  • При N =  3 процесс завершается: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1;
  • При N =  4 процесс завершается: 4 -> 2 -> 1;
  • При N =  5 процесс завершается: 5 -> 16 -> 8 -> 4 -> 2 -> 1;
  • Гипотеза: процесс завершается при любом N.

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


8

        Логический вывод - дедукция

Видео


        Дедукция

Дедуктивный метод вывода - это метод вывода “от общего к частному”. Из истинности некоторого общего утверждения делается вывод об истинности частного случая. Следующие рассуждения являются классическим примером дедуктивного вывода, известным со времен античных философов:

  • Все греки - люди.
  • Сократ - грек.
  • Следовательно: Сократ - человек.

Вот более современный пример, использующий тот же метод вывода:

  • Каждый школьник изучает информатику.
  • Пётр - школьник.
  • Следовательно: Пётр - изучает информатику.

А вот пример некорректного вывода:

  • Каждый школьник изучает информатику.
  • Пётр - не школьник.
  • Следовательно: Пётр - не изучает информатику.

А этот вывод вполне корректен и соответствует правилам логики:

  • Каждый школьник изучает информатику.
  • Пётр - не изучает информатику.
  • Следовательно: Пётр - не школьник.

        Метод математической индукции

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

  • Вначале доказать истинность Q(No) для некоторого частного случая N = No. Обычно N₀ равно 0 или 1.
  • Далее необходимо доказать общее утверждение: Из справедливости Q(k) для k >=


9

    N₀, следует справедливость Q(k + 1).


Если оба предыдущих пункта доказаны, то утверждение Q(N) справедливо для всех частных случаев, где N >= N₀.

Пример 1: Доказать Q(N):

      /2 _ Лг*(Лг+1)*(2*Лг+1)
L,;. i! —        ё

  •  Базис индукции: (N 0 = 1)
  •  Шаг индукции: Пусть            ■—" ' ~     -. Тогда
     у-.Ь+1 -2 _ fc*(fc+l)*(2*fc+ll , /т , i\2 _ fc+l*((fc+L) + L)*(2*(fc4-l)4-l) — б                     г- Vе ■+■ 1J —        в           .

Базис и шаг индукции доказаны. Отсюда следует справедливость утверждения для любого значения N >= 1.

Пример 2: Число слов длины n в алфавите T из m символов равно: k = mⁿ.

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

  •  Базис индукции: N0 = 1. Слов длины 1 ровно m - это символы алфавита T.
  •  Шаг индукции: Пусть предположение утверждения выполняется для слов длины k, - таких слов mk. Докажем, что в этом случае утверждение остается истинным и для слов длины k + 1. Действительно, пусть построено множество слов длины k. Тогда можно построить множество слов длины k + 1 следующим образом. Каждое слово длины k можно продолжить одним из символов алфавита, получая слово длины k +1. Таким образом, каждое слово длины k порождает m слов длины k + 1. Никаких других слов длины k + 1, кроме порожденных таким способом, не существует. Отсюда следует, что число слов длины k + 1 равно: mk * m = mk⁺¹, что и требовалось доказать.

Следовательно, наше утверждение справедливо для слов произвольной длины (n >= 1)


10