Главная » Реферат » Математическая логика реферат

Доклад: Математическая логика и логика здравого смысла. Математическая логика реферат


Реферат Математическая логика

скачать

Реферат на тему:

План:

Введение

Математи́ческая ло́гика (теоретическая логика, символическая логика) — раздел математики, изучающий доказательства и вопросы оснований математики. «Предмет современной математической логики разнообразен.»[1] Согласно определению П. С. Порецкого, «математическая логика есть логика по предмету, математика по методу». Согласно определению Н. И. Кондакова, «математическая логика — вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков).»[2] Это определение соответствует определению С. К. Клини: математическая логика — это «логика, развиваемая с помощью математических методов».[3] Также А. А. Марков определяет современную логику «точной наукой, применяющей математические методы».[4] Все эти определения не противоречат, а дополняют друг друга.

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

Важную роль в математической логике играют понятия дедуктивной теории и исчисления. Исчислением называется совокупность правил вывода, позволяющих считать некоторые формулы выводимыми. Правила вывода подразделяются на два класса. Одни из них непосредственно квалифицируют некоторые формулы как выводимые. Такие правила вывода принято называть аксиомами. Другие же позволяют считать выводимыми формулы A, синтаксически связанные некоторым заранее определённым способом с конечными наборами A_1, \ldots A_n выводимых формул. Широко применяемым правилом второго типа является правило modus ponens: если выводимы формулы A и (A\to B), то выводима и формула B.

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

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

Многие из рассматриваемых в математической логике языков обладают семантически полными и семантически пригодными исчислениями. В частности, известен результат К. Гёделя о том, что так называемое классическое исчисление предикатов является семантически полным и семантически пригодным для языка классической логики предикатов первого порядка. С другой стороны, имеется немало языков, для которых построение семантически полного и семантически пригодного исчисления невозможно. В этой области классическим результатом является теорема Гёделя о неполноте, утверждающая невозможность семантически полного и семантически пригодного исчисления для языка формальной арифметики.

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

1. Разделы математической логики

Примечания

  1. С. И. Адян, Математическая энциклопедия, М.: «Советская энциклопедия», т.3, с. 568, 571.
  2. Н. И. Кондаков, Логический словарь-справочник, М.: «Наука», 1975, с. 259.
  3. С. К. Клини, Математическая логика, М., 1973, с.12.
  4. А. А. Марков, Большая советская энциклопедия, Изд. 3, Предмет и метод современной логики.

Литература

wreferat.baza-referat.ru

Реферат: Математическая Логика

Конспекты лекций по математической логике.

 

1.         Теория алгоритмов

1.1  Различные подходы к определению алгоритма:

10.  Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).

20.  Машина с неограниченными регистрами (МНР).

30 Машина Тьюринга – Поста (МТ-П).

40 Нормальные алгоритмы Маркова (НАМ).

 

  1.1.1  Машина с неограниченными регистрами (МНР).

Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.

Допустимые команды:

   Z(n)      - обнуление регистра Rn.

   S(n)      - увеличение числа в регистре Rn на 1.

   T(m,n)  - копирует содержимое Rm в регистор Rn.

   I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером n , если нет

   следующая.

  Программа для МНР должна быть последовательностью команд Z, S, T, I  с определенным порядком, выполняемые последовательно.

 

  Тезис Черча (Churcha): Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.

 

  1.1.2  Машина Тьюринга - Поста.

Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита:  , где  - пустой символ (пустое слово), который может принадлежать и не принадлежать А. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии . Также существуют внутренние состояния машины:

Слово в данном алфавите - любая конечная упорядоченная  последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).

Допустимые команды:

1)    ,где .

2)    (остановка программы).

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

 

  1.1.3  Нормальные алгоритмы Маркова.

Тип машины перерабатывающий слова, в которой существует некий алфавит , для которого W - множество всех слов.

Допустимые команды: (Для машин этого типа важна последовательность команд.)

 

  1.1.4  Реализация функции натурального переменного.

 но мы допускаем не всюду определенную функцию.

 то это означает, что 

притом , если f не определена, то и программа не должна ничего выдавать.

 

притом , если f не определена, то и программа не должна ничего выдавать.

( , а числа представляются в виде  ,например  .)

1.2  Эквивалентность трех подходов к понятию алгоритм.

 

1.2.1  Теорема об эквивалентности понятия вычислимой функции.

  вычислима: ()

1)      Если существует программа МНР, которая вычисляет эту функцию.

2)      Если существует программа МТ-П, которая вычисляет эту функцию.

3)      Если существует программа НАМ, которая вычисляет эту функцию.

 

Использование НАМ:          

        

 

Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.

 Пусть  которая вычисляется на МТ-П, вычислим её на НАМ.

 

НАМ:  

 

Команда МТП:  преобразуется по правилам:

Команда МТП:            

 

2.  Булевы функции.

2.1  Основные определения

2.1.1  Декартово произведение

 - мн-во всевозможных упорядоченных пар элементов из А и В.

Пример: 

 

 

2.1.2  Декартова степень произвольного множества.

Опр:  - множество всевозможных упорядоченных наборов длины n , элементов множества А.   

 

2.1.3  Определение булевой функции от n переменных.

Любое отображение  - называется булевой функцией от n переменных, притом множество

 

2.1.4  Примеры булевой функции.

1)         логическая сумма (дизъюнкция).

2)       логическое умножение (конъюнкция).

3)       сложение по модулю два.

4)       логическое следствие (импликация).

5)       отрицание.

 

 

2.1.5  Основные булевы тождества.

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

2)        (коммутативность)

3)        (свойство нуля)

4)        (закон поглощения для 1)

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

6)        (коммутативность)

7)        (свойство нуля по умножению)

8)        (свойство нейтральности 1 по умножению)

9)        (дистрибутивность)

10)    (дистрибутивность 2)

11)    (закон поглощения)

12)    (   Законы    

13)     де Моргана)

14)    (закон снятия двойного отрицания)

15)    (tertium non datur – третьего не дано)

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

17) 

18) 

19) 

20) 

21)       (Свойства

22)            идемпотентности)

 

2.2  Дизъюнктивные нормальные формы.

 

2.2.1  Основные определения.

 - конечный алфавит из переменных.

Рассмотрим слово:

Экспоненциальные обозначения:

 - элемент конъюнкции.

S – длина элемента конъюнкции.

ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.

Любая булева функция может быть представлена как ДНФ

 

2.2.2  Теорема о совершенной ДНФ.

Любая булева функция  тождественно не равная 0 может быть разложена в ДНФ следующего вида:

 

Опр: Носитель булевой функции

.

Лемма:

1)       это элементарно 

2)       возьмем набор

а) 

б) 

Доказательство: , будем доказывать, что.

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

2)      Докажем, что . Возьмем другой набор из

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

 

2.2.3  Некоторые другие виды ДНФ.

Опр:  - называется минимальной ДНФ, если она имеет  - наименьшую возможную длину из всех ДНФ данной функции.

 

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

 

(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)

 

Опр: К-мерной гранью называется такое подмножество , которая является носителем некоторой элементарной конъюнкции длины: n-k.

 

Опр: Предположим дана функция  и есть . Грань называется отмеченной, если она целиком содержится в носителе Т.

 

Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.

 

Предложение: Любую отмеченную грань можно вложить в максимальную грань.

 

Предложение:

 

(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)

 

Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.

 

Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.

 

Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.

 

Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.

 

3  Логические Исчисления.

 

3.1  Исчисления высказывания (ИВ).

 

3.1.1  Определения.

Опр: V – словом в алфавите А, называется любая конечная упорядоченная последовательность его букв.

 

Опр: Формативная последовательность слов – конечная последовательность слов и высказываний , если они имеют формат вида:

Опр: F – формулой ИВ, называется любое слово, входящее в какую-нибудь формативную последовательность.

 

Пример:

 

 

Опр: Аксиомы – специально выделенное подмножество формул.

1)            

2)            

3)            

4)            

5)            

6)            

7)            

8)            

9)            

10)        

11)        

 

Reg – правила вывода ИВ (некоторые правила преобразования первого слова в другое).

a – символ переменной

 - произвольное слово ИВ (формула)

Отображение  действует так, что на место каждого вхождения символа а , пишется слово .

Пример:

Правило modus ponens:        

 

3.1.2  Формальный вывод.(простейшая модель доказательства теоремы)

Опр: Последовательность формул ИВ, называется формальным выводом, если каждая формула этой последовательности имеет следующий вид:

Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в какой-нибудь формальный вывод.   - выводимая формула ИВ.

 

Пример: 

 

Правило одновременной  подстановки.

Замечание: Если формула  выводима, то выводима и

Возьмем формативную последовательность вывода   и добавим в неё , получившаяся последовательность является формальным выводом.

(Если выводима  то если  , то выводима  )

 

Теор: Если  выводимая формула , то  ( - различные символы переменных) выводима

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

 

3.1.3  Формальный вывод из гипотез.

Опр: Формальным выводом из гипотез (формулы), называется такая последовательность слов , каждая из которых удовлетворяет условию:

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

Лемма: ; : то тогда

Напишем список:

     

Лемма: 

Док:     

 

3.1.4  Теорема Дедукции.

Если из

 

1)      и 2а)  , где   по правилу m.p. , ч.т.д.

2б)   - уже выводили , ч.т.д.

 

Базис индукции: N=1   - формальный вывод из длинного списка

 (только что доказано), осуществим переход по индукции:

 по индукции

 и по лемме 2

Пример:

 по теореме дедукции

 

3.2  Критерий выводимости в ИВ.

3.2.1  Формулировка теоремы.

 - тавтология

при любой интерпретации алфавита (символов переменных)

 

3.2.2  Понятие интерпретации.

символ переменной   переменную поставим в соответствие.

, где  - проекция на .

               ;  - только символ

               переменных, т.к.

               это заглавное слово

               формативной последо-

               вательности вида:

 

Где:

 

3.2.3  Доказательство теоремы.

формальный

вывод      

 

 

(1)    

 

 

 

 

 

 

 

 

 

3.3  Непротиворечивость ИВ.

3.3.1  Определение.

1)      ИВ противоречиво, если формула А выводима в нем. .

2)      формула выводима в ИВ)ИВ противоречиво.

3)      ИВ противоречиво.

ИВ непротиворечиво, если оно не является противоречивым.

 

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

Док-во: (1) Если , то соответствующая ей булева функция будет тождественно равна 1.

 

(2)  Если любая формула выводима, то выводима и А, что соответствует пункту 1.

(3)  Пусть  и   - булева функция

       - противоречие.

 

3.4  Формальные исчисления.

Алфавит – конечное или счетное множество символов, возможно, разбитых на группы. Алфавит должен быть упорядоченным множеством.

Слово – конечная упорядоченная последовательность символов алфавита, в т.ч. пустое слово.

V – множество всех слов.

 

Вычислимая функция от нескольких натуральных переменных

( f – может быть не всюду определенной )

f – называется вычислимой, если  такая машина Тьюринга, которая её вычисляет.

 

 - разрешимое множество, если характеристическая функция

 - является вычислимой.

Множество  называется перечислимым, если  такая вычислимая функция

М - разрешимо  М и N \M перечислимы.

М – перечислимо  М – область определения некоторой вычислимой функции.

Множество всех формул F – некоторое разрешимое подмножество V.

Т – счетное множество, если  его биективное отображение на V.

 - обозначение счетного множества. ( - алеф-нуль)

 

Если  и зафиксировано биективное и вычислимое отображение  (вычис.),

то L – ансамбль.

V – ансамбль (слова лексикографически упорядочены и занумерованы)

 

Определение: В произвольном формальном исчислении:  - множество всех аксиом – разрешимое подмножество множества всех формул.

Правило вывода:

  ,при  разрешимо. Для ИВ N=2.

Пример:

      (пустое слово)  ,

   1 и 2 – формальные выводы.

   3 – не является формальным выводом.

4.1  Определение предиката.

 - высказывание, содержащее переменную.

 - предметная область предиката.

 

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

 

-местный предикат – произвольное отображение  

 

Множество истинности данного предиката

 -

 - характеристическая

функция от x на множестве

А - совпадает

с предикатами

 

 

4.2  Понятие квантора.

k – связанная переменная

n – свободная переменная

 

  t – свободная, x – связанная.

 , a,b,y – свободные переменные, x – связанная.

    

 

4.3  Геометрическая интерпретация навешивания кванторов.

 

 

Пронесение отрицания через кванторы

    

Геометрическое 'доказательство':

 не обладает свойством, что прямая  целиком лежит в

 ч.т.д.

 

 

 

 

www.referatmix.ru

Реферат на тему Математическая логика и логика здравого смысла

СОДЕРЖАНИЕ   Введение. 3 1.   Математическая логика (бессмысленная логика) и логика «здравого смысла»  4 2. Математические суждения и умозаключения. 6 3.Математическая логика и «Здравый смысл» в XXI веке. 11 4.   Неестественная логика в основаниях математики. 12 Заключение. 17 Список литературы.. 18

Введение Расширение области логических интересов связано с общими тенденциями развития научного знания. Так, возникновение математической логики в середине XIX века явилось итогом многовековых чаяний математиков и логиков о построении универсального символического языка, свободного от «недостатков» естественного языка (прежде всего его многозначности, т.е. полисемии). Дальнейшее развитие логики связано с совокупным использованием классической и математической логики в прикладных областях. Неклассические логики (деонтическая, релевантная, логика права, логика принятия решений и др.) часто имеют дело с неопределенностью и нечеткостью исследуемых объектов, с нелинейным характером их развития. Так, при анализе достаточно сложных задач в системах искусственного интеллекта возникает проблема синергизма различных типов рассуждения при решении одной и той же задачи. Перспективы развития логики в русле сближения с информатикой связаны с созданием определенной иерархии возможных моделей рассуждения, включающих рассуждения на естественном языке, правдоподобные рассуждения и формализованные дедуктивные выводы. Это решается средствами классической, математической и неклассической логик. Таким образом, речь идет не о разных «логиках», а о разной степени формализации мышления и «размерности» логических значений (двузначная, многозначная и др. логика). Выделение основных направлений современной логики: 1. общей, или классической логики; 2. символической, или математической логики; 3. неклассической логики.

1.                Математическая логика (бессмысленная логика) и логика «здравого смысла» Математическая логика понятие достаточно неконкретное, из-за того, что математических логик также бесконечно много. Здесь будем обсуждать некоторые из них, отдавая больше дань традиции, чем здравому смыслу. Поскольку, весьма возможно, в этом и заключен здравый смысл... Логично? Математическая логика учит логично рассуждать не больше, чем любой другой раздел математики. Это связано с тем, что "логичность" рассуждений в логике определяется самой логикой и корректно может использоваться только в самой логике. В жизни же мы, размышляя логически, как правило используем разные логики и разные методы логических рассуждений, безбожно перемешивая дедукцию с индукцией... Более того, в жизни мы строим свои рассуждения исходя из противоречивых посылок, например, "Не откладывай на завтра, что можно сделать сегодня" и "Поспешишь людей насмешишь". Нередко бывает, что непонравившийся нам логический вывод приводит к пересмотру исходных посылок (аксиом). Пожалуй, настало время сказать про логику, возможно, самое главное: классическая логика не занимается смыслом. Ни здравым, ни каким другим! Для изучения здравого смысла, между прочим, существует психиатрия. Но в психиатрии логика скорее вредна. Разумеется, размежевывая логику со смыслом, имеем в виду прежде всего классическую логику и житейское понимание здравого смысла. Нет запретных направлений в математике, поэтому исследование логикой смысла, и наоборот, в различных видах присутствует в ряде современных ответвлений логической науки. (Хорошо сложилось последнее предложение, хотя определить термин "логическая наука" не возьмусь даже приблизительно). Смыслом, если угодно - семантикой, занимается, например, теория моделей. Да и вообще, термин семантика часто заменяют термином интерпретация. И если мы согласимся с философами, что интерпретация (отображение!) об'екта есть осмысление его в некотором данном аспекте, то пограничные сферы математики, которые могут привлекаться для наступления на смысл в логике, становятся неохватными! В практическом плане семантикой вынуждено интересоваться теоретическое программирование. А в нем, кроме просто семантики, есть и операционная, и денотационная, и процедуральная и т.д. и т.п. семантики... Еще лишь упомянем апофеоз - ТЕОРИЮ КАТЕГОРИЙ, которая довела семантику до формального малопонятного синтаксиса, где смысл уже настолько простой - разложенный по полочкам, что до него простому смертному совсем невозможно докопаться... Это для избранных. Так чем же занимается логика? Хотя бы в самой классической ее части? Логика занимается только тем, чем она занимается. (А это она определяет предельно строго). Главное в логике – это строго определиться! Задать аксиоматику. А дальше логические выводы должны быть(!) в значительной степени автоматическими... Другое дело рассуждения по поводу этих выводов! Но эти рассуждения уже вне рамок логики! Поэтому в них требуется строгий математический смысл! [6] Может показаться, что это простая словесная эквилибристика. НЕТ! В качестве примера некоторой логической (аксиоматической) системы возьмем известную игру 15. Зададим (перемешаем) начальное расположение квадратных фишек. Далее игрой (логическим выводом!), а конкретно - перемещением фишек на свободное место, может заниматься некое механическое устройство, а вы можете терпеливо смотреть и радоваться, когда в результате возможных передвижек в коробочке сложится последовательность от 1 до 15. Но никто не запрещает контролировать механическое устройство и подсказывать ему, ИСХОДЯ ИЗ здравого СМЫСЛА правильные перемещения фишек, чтобы ускорить процесс. А может быть даже доказать, используя для логических рассуждений, например, такой раздел математики, как КОМБИНАТОРИКА, что при данном начальном расположении фишек получить требуемую финальную комбинацию невозможно вообще! Не больше здравого смысла присутствует и в той части логики, которую называют ЛОГИЧЕСКОЙ АЛГЕБРОЙ. Здесь вводятся ЛОГИЧЕСКИЕ ОПЕРАЦИИ и определяются их свойства. Как показала практика, в некоторых случаях законы этой алгебры могут соответствовать логике жизни, а в некоторых нет. Из за такого непостоянства законы логики нельзя считать законами с точки зрения практики жизни. Их знание и механическое использование может не только помогать, но и вредить. Особенно психологам и юристам. Ситуация осложняется тем, что наряду с законами алгебры логики, которые то соответствуют, то не соответствуют жизненным рассуждениям, есть логические законы, которые часть логиков категорически не признают. Это относится прежде всего к так называемым законам ИСКЛЮЧЕННОГО ТРЕТЬЕГО и ПРОТИВОРЕЧИЯ.

В мышлении понятия не выступают разрозненно, они определенным способом связываются между собой. Формой связи понятий друг с другом является суждение. В каждом суждении устанавливается некоторая связь или некоторое взаимоотношение между понятиями, и этим самым утверждается наличие связи или взаимоотношений между объектами, охватываемыми соответствующими понятиями. Если суждения правильно отображают эти объективно существующие зависимости между вещами, то мы такие суждения называем истинными, в противном случае суждения будут ложными. Так, например, суждение "всякий ромб является параллелограммом" - истинное суждение; суждение "всякий параллелограмм является ромбом" - ложное суждение. Таким образом, суждение - это такая форма мышления, в которой отображается наличие или отсутствие самого объекта (наличие или отсутствие каких-либо его признаков и связей). Мыслить - значит высказывать суждения. С помощью суждений мысль, понятие получают свое дальнейшее развитие. Так как во всяком понятии отображается определенный класс объектов, явлений или взаимоотношений между ними, то всякое суждение можно рассматривать как включение или невключение (частичное или полное) одного понятия в класс другого понятия. Например, суждение "всякий квадрат есть ромб" указывает, что понятие "квадрат" включается в понятие "ромб"; суждение "пересекающиеся прямые не являются параллельными" указывает, что пересекающиеся прямые не принадлежат множеству прямых, называемых параллельными. Суждение имеет свою языковую оболочку - предложение, однако не всякое предложение является суждением. Характерным признаком суждения является обязательное наличие истинности или ложности в выражающем его предложении. Например, предложение "треугольник АВС равнобедренный" выражает некоторое суждение; предложение "Будет ли АВС равнобедренным?" не выражает суждения. Каждая наука по существу представляет собой определенную систему суждений об объектах, являющихся предметом ее изучения. Каждое из суждений оформляется в виде некоторого предложения, выраженного в терминах и символах, присущих этой науке. Математика также представляет собой определенную систему суждений, выраженных в математических предложениях посредством математических или логических терминов или соответствующих им символов. Математические термины (или символы) обозначают те понятия, которые составляют содержание математической теории, логические термины (или символы) обозначают логические операции, с помощью которых из одних математических предложений строятся другие математические предложения, из одних суждений образуются другие суждения, вся совокупность которых и составляет математику как науку. Вообще говоря, суждения образуются в мышлении двумя основными способами: непосредственно и опосредованно. В первом случае с помощью суждения выражается результат восприятия, например "эта фигура -т- круг". Во втором случае суждение возникает в результате особой мыслительной деятельности, называемой умозаключением. Например, "множество данных точек плоскости таково, что их расстояние от одной точки одинаково; значит, эта фигура - окружность". В процессе этой мыслительной деятельности обычно осуществляется переход от одного или нескольких связанных между собой суждений к новому суждению, в котором содержится новое знание об объекте изучения. Этот переход и является умозаключением, которое представляет собой высшую форму мышления. Итак, умозаключением называется процесс получения нового суждения вывода из одного или нескольких данных суждений. Например, диагональ параллелограмма делит его на два конгруэнтных треугольника (первое суждение). Сумма внутренних углов треугольника равна 2d (второе суждение). Сумма внутренних углов параллелограмма равна 4d (новое суждение-вывод). Познавательное значение математических умозаключений чрезвычайно велико. Он" расширяют границы наших знаний об объектах и явлениях реального мира в силу того, что большая часть математических предложений является выводом из сравнительно небольшого числа основныхo суждений, которые получены, как правило, путем непосредственного опыта и в которых отражены наши наиболее простые и общие знания об его объектах. Умозаключение отличается (как форма мышления) от понятия и суждения тем, что оно представляет собой логическую операцию над отдельными мыслями. Не всякое сочетание суждений между собой представляет собой умозаключение: между суждениями должна существовать определенная логическая связь, отражающая объективную связь, существующую в реальной действительности. Например, из суждений "сумма внутренних углов треугольника равна 2d" и "2*2=4" нельзя сделать вывод.  Понятно, какое значение в системе наших математических знаний имеет умение правильно строить различные математические предложения или делать выводы в процессе рассуждения. Разговорный язык плохо приспособлен для выражения тех или иных суждений, а тем более для выявления логической структуры рассуждений. Поэтому естественно, что возникла необходимость усовершенствования языка, используемого в процессе рассуждения. Математический (а точнее, символический) язык оказался для этого самым подходящим. Возникшая" в XIX в. специальная область науки - математическая логика не только полностью решила проблему создания теории математического доказательства, но и оказала большое влияние на развитие математики в целом. Формальную логику (возникшую еще в глубокой древности в трудах Аристотеля) не отождествляют с математической логикой (возникшей в XIX в. в работах английского математика Дж. Буля). Предметом формальной логики является изучение законов взаимосвязи суждений и понятий в умозаключениях и правилах доказательства. Математическая логика отличается от формальной логики тем, что она, исходя из основных законов формальной логики, исследует закономерности логических процессов на основе применения математических методов: "Логические связи, которые существуют между суждениями, понятиями и т. д., находят свое выражение в формулах, толкование которых свободно от неясностей, какие легко могли бы возникнуть при словесном выражении. Таким образом, для математической логики характерна формализация логических операций, полнее абстрагирование от конкретного содержания предложений (выражающих какое-либо суждение). Проиллюстрируем сказанное одним примером. Рассмотрим следующее умозаключение: "Если все растения красные и все собаки - растения, то все собаки красные". Каждое из используемых здесь суждений и то суждение, которое мы получили в результате сдержанного умозаключения, кажется явной бессмыслицей. Однако с точки зрения математической логики мы имеем здесь дело с верным предложением, так как в математической логике истинность или ложность умозаключения зависит только от истинности или ложности составляющих его посылок, а не от их конкретного содержания. Поэтому если одним из основных понятий формальной логики является суждение, то аналогичным ему понятием математической логики является понятие высказывания-утверждения, для которого имеет смысл лишь говорить, истинно оно или ложно. Не следует думать, что для каждого высказывания характерно отсутствие "здравого смысла" в его содержании. Просто содержательная часть предложения, составляющего то или иное высказывание, в математической логике отходит на второй план, несущественна для логического построения или анализа того или иного вывода. (Хотя, конечно существенна для. понимания содержания того, о чем идет речь при рассмотрении o данного вопроса.) Понятно, что в самой математике рассматриваются содержательные высказывания. Устанавливая различные связи и отношения между понятиями, математические суждения утверждают или отрицают какие-либо отношения между объектами и явлениями реальной действительности. Логика - не только сугубо математическая, но также и философская наука. В XX веке эти две взаимосвязанные ипостаси логики оказались разведенными в разные стороны. С одной стороны логика понимается как наука о законах правильного мышления, а с другой - она преподносится как совокупность слабо связанных друг с другом искусственных языков, которые называются формальными логическими системами. Для многих очевидно, что мышление - это некий сложный процесс, с помощью которого решаются житейские, научные или философские проблемы и рождаются гениальные идеи или роковые заблуждения. Язык же понимается многими просто как средство, с помощью которого результаты мышления можно передать современникам или оставить потомкам. Но, связав в своем сознании мышление с понятием "процесс", а язык с понятием "средство", мы по сути перестаем замечать тот непреложный факт, что в данном случае "средство" не подчинено полностью "процессу", а в зависимости от нашего целенаправленного или неосознанного выбора тех или словесных штампов оказывает сильнейшее влияние на ход и результат самого "процесса". Причем известно немало случаев, когда такое "обратное влияние" оказывается не только тормозом для правильного мышления, но порою даже его разрушителем. С философской точки зрения задача, поставленная в рамках логического позитивизма, так и не была выполнена. В частности, в своих поздних исследованиях один из основоположников этого направления Людвиг Витгенштейн пришел к выводу, что естественный язык нельзя реформировать в соответствии с разработанной позитивистами программой. Даже язык математики в целом устоял перед мощным напором "логицизма", хотя многие термины и структуры предлагаемого позитивистами языка вошли в некоторые разделы дискретной математики и существенно дополнили их. Популярность логического позитивизма как философского направления во второй половине XX столетия заметно упала - многие философы пришли к выводу, что отказ от многих "нелогичностей" естественного языка, попытка втиснуть его в рамки основополагающих принципов логического позитивизма влечет за собой дегуманизацию процесса познания, а вместе с этим и дегуманизацию человеческой культуры в целом. Многие методы рассуждений, которые используются в естественном языке, часто весьма трудно однозначно отобразить на языке математической логики. В некоторых случаях такое отображение приводит к существенному искажению сути естественного рассуждения. И есть основание полагать, что эти проблемы являются следствием исходной методологической установки аналитической философии и позитивизма о нелогичности естественного языка и о необходимости его коренного реформирования. Сама исходная методологическая установка позитивизма также не выдерживает критики. Обвинять разговорный язык в нелогичности просто абсурдно. На самом деле нелогичность характеризует не сам язык, а многих пользователей этого языка, которые просто не знают или не хотят использовать логику и компенсируют этот изъян психологическими или риторическими приемами воздействия на публику, либо в своих рассуждениях используют в качестве логики систему, которая называется логикой лишь по недоразумению. В то же время имеется немало людей, речь которых отличается ясностью и логичностью, и эти качества не определяются знанием или незнанием основ математической логики.

4.                Неестественная логика в основаниях математики В рассуждениях тех, кого можно отнести к законодателям или последователям формального языка математической логики, нередко обнаруживается своеобразная "слепота" по отношению к элементарным логическим ошибкам. На эту слепоту в основополагающих работах Г. Кантора, Д. Гильберта, Б. Рассела, Дж. Пеано и др. еще в начале нашего столетия обратил внимание один из великих математиков Анри Пуанкаре [2]. Одним из примеров такого нелогичного подхода к рассуждениям является формулировка знаменитого парадокса Рассела, в котором необоснованно смешиваются два сугубо разнородных понятия "элемент" и "множество". Во многих современных работах по логике и математике, в которых заметно влияние программы Гильберта, не находят объяснения многие явно нелепые с точки зрения естественной логики утверждения. Соотношение между "элементом" и "множеством" является простейшим примером такого рода. Во многих работах этого направления утверждается, что некоторое множество (назовем его A) может быть элементом другого множества (назовем его B). Например, в широко известном руководстве по математической логике [2] мы встретим такую фразу: "Множества сами могут быть элементами множеств, так, например, множество всех множеств целых чисел имеет своими элементами множества". Заметим, что это утверждение не просто оговорка. Оно содержится в качестве "скрытой" аксиомы в формальной теории множеств, которую многие специалисты считают основанием современной математики, а также в формальной системе, которую построил математик К. Гедель при доказательстве своей знаменитой теоремы о неполноте формальных систем [2]. Эта теорема относится к довольно узкому классу формальных систем (в их число входят формальная теория множеств и формальная арифметика), логическая структура которых явно не соответствует логической структуре естественных рассуждений и обоснований. Однако уже более полувека она является предметом бурного обсуждения среди логиков и философов в контексте общей теории познания. При таком широком обобщении этой теоремы получается, что принципиально непознаваемыми являются многие элементарные понятия. Но при более трезвом подходе оказывается, что теорема Геделя показала лишь несостоятельность программы формального обоснования математики, предложенной Д. Гильбертом и подхваченной многими математиками, логиками и философами. Более широкий методологический аспект теоремы Геделя вряд ли можно считать приемлемым до тех пор, пока не получен ответ на следующий вопрос: является ли программа обоснования математики, предложенная Гильбертом, единственно возможной? Чтобы понять двусмысленность утверждения "множество A есть элемент множества B", достаточно задать простой вопрос: "Из каких элементов в этом случае сформировано множество B?". С точки зрения естественной логики возможны лишь два исключающих друг друга варианта объяснения. Объяснение первое. Элементами множества B являются имена некоторых множеств и, в частности, имя или обозначение множества A. Например, множество всех четных чисел содержится как элемент в множестве всех имен (или обозначений) множеств, выделенных по каким-либо признакам из множества всех целых чисел. Можно привести более понятный пример: множество всех жирафов содержится как элемент в множестве всех известных видов животных. В более широком контексте множество B можно также сформировать из концептуальных определений множеств или ссылок на множества. Объяснение второе. Элементами множества B являются элементы некоторых других множеств и, в частности, все элементы множества A. Например, каждое четное число есть элемент множества всех целых чисел или каждый жираф есть элемент множества всех животных. Но тогда получается, что в обоих случаях выражение "множество A является элементом множества B" не имеет смысла. В первом случае оказывается, что элементом множества B является не само по себе множество A, а его имя (или обозначение, или ссылка на него). В этом случае неявно устанавливается отношение эквивалентности между множеством и его обозначением, что неприемлемо ни с точки зрения обычного здравого смысла, ни с точки зрения несовместимой с чрезмерным формализмом математической интуиции. Во втором случае оказывается, что множество A включено в множество B, т.е. является его подмножеством, но не элементом. Здесь тоже явная подмена понятий, поскольку отношение включения множеств и отношение принадлежности (быть элементом множества) в математике имеют принципиально различный смысл. Знаменитый парадокс Рассела, подорвавший доверие логиков к понятию "множество", основан на этой нелепости - в основе парадокса лежит двусмысленная предпосылка о том, что множество может быть элементом другого множества. Возможен еще один вариант объяснения. Пусть множество A задано простым перечислением его элементов, например, A = {a, b}. Множество B в свою очередь задано перечислением некоторых множеств, например, B = {{a, b}, {a, c}}. В данном случае кажется очевидным, что элементом B является не имя множества A, а само множество A. Но даже в этом случае элементы множества A не являются элементами множества B, и множество A здесь рассматривается как неразделимая совокупность, которая вполне может быть заменена его именем. Но если бы мы считали элементами B все элементы содержащихся в нем множеств, то в этом случае множество B было бы равно множеству {a, b, c}, и множество A в этом случае было бы не элементом B, а его подмножеством. Таким образом, получается, что этот вариант объяснения в зависимости от нашего выбора, сводится к ранее перечисленным вариантам. А если никакого варианта выбора не предложено, то получается элементарная двусмысленность, которая часто приводит к "необъяснимым" парадоксам. Можно было бы не уделять особого внимания этим терминологическим нюансам, если бы не одно обстоятельство. Оказывается, что многие парадоксы и несообразности современной логики и дискретной математики являются прямым следствием или подражанием этой двусмысленности. Например, в современных математических рассуждениях часто используется понятие "самоприменимость", которое лежит в основе парадокса Рассела. В формулировке этого парадокса под самоприменимостью подразумевается существование множеств, которые являются элементами самих себя. Такое утверждение сразу же приводит к парадоксу. Если мы рассмотрим множество всех "несамоприменимых" множеств, то окажется, что оно является одновременно "самоприменимым" и "несамоприменимым.

Заключение Математическая логика немало способствовала бурному развитию информационных технологий в XX веке, но из ее поля зрения выпало понятие "суждение", которое появилось в логике еще во времена Аристотеля и на котором, как на фундаменте, держится логическая основа естественного языка. Такое упущение отнюдь не способствовало развитию логической культуры общества и у многих даже породило иллюзию, что компьютеры способны мыслить не хуже самого человека. Многих даже не смущает то обстоятельство, что на фоне всеобщей компьютеризации в преддверии третьего тысячелетия логические нелепости в пределах самой науки (я уж не говорю о политике, законотворческой деятельности и о псевдонауке) встречаются даже чаще, чем в конце XIX века. И для того, чтобы понять суть этих нелепостей, нет необходимости обращаться к сложным математическим структурам с многоместными отношениями и рекурсивными функциями, которые применяются в математической логике. Оказывается, для понимания и анализа этих нелепостей вполне достаточно применить намного более простую математическую структуру суждения, которая не только не противоречит математическим основам современной логики, но в чем-то дополняет и расширяет их.

1.                Васильев Н. А. Воображаемая логика. Избранные труды. - М.: Наука. 1989; - стр. 94-123. 2.                Кулик Б.А. Основные принципы философии здравого смысла (познавательный аспект) // Новости искусственного интеллекта, 1996, No 3, с. 7-92. 3.                Кулик Б.А. Логические основы здравого смысла / Под редакцией Д.А. Поспелова. - СПб, Политехника, 1997. 131 с. 4.                Кулик Б.А. Логика здравого смысла. - Здравый смысл, 1997, No 1(5), с. 44 - 48. 5.                Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967. 6.                Соловьев А. Дискретная математика без формул. 2001// http://soloviev.nevod.ru/2001/dm/index.html

bukvasha.ru

Реферат - «математическая логика» - Разное

Министерство образования РФ

Муниципальное общеобразовательное учреждение средняя общеобразовательная школа № 2

Реферат на тему:

«МАТЕМАТИЧЕСКАЯ ЛОГИКА»

Выполнила ученица 8А класса

Малова Анна Игоревна

Руководитель

Мосенкова Любовь Анатольевна

Вязьма

2007

I.Вступление.

Логика ведет свое происхождение от ораторского искусства. Убедить собеседника невозможно, если оратор сам себе противоречит ( уж если ты сказал, что снег белый, не следует ссылаться на его черноту…). В Древней Греции, где важнейшие вопросы решались на советах, всякий уважающий себя философ, политический деятель или литератор старался строить речь так, чтобы она была доходчива и разумна. В античном мире чрезвычайно ценилось умение высказываться точно, кратко и остроумно. Не потеряло актуальности это умение и потом, недаром появилось выражение «краткость – сестра таланта». Зачастую не имея никаких данных о жизни многих выдающихся древних мудрецов, мы, тем не менее, знаем о них хотя бы по одному афоризму, некогда произнесенному ими. Как жил Евклид, чем интересовался, кроме геометрии? Эти факты неизвестны, зато все знают, как он ответил ученику, спросившему: « Какая польза будет мне от изучения математики?». Разгневанный Евклид позвал слугу и сказал: «Дай ему грош, он ищет выгоды, а не знаний».

Любовь к точной фразе привела древнегреческих философов к логике. Что из чего следует и почему? Можно ли, например, утверждать, что Сократ смертен, если дано, что все люди смертны и Сократ человек? Можно. А если дано, что все люди смертны и Сократ тоже смертен, верно, ли, что Сократ человек? Неверно: вдруг Сократом зовут не только древнегреческого мудреца, но и его собаку?

Законы логики, правила вывода верных утверждений из заданных посылок наиболее полно исследовал великий древнегреческий философ Аристотель.

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

1.Ночью все кошки серы. Мой зверь – кот. Значит, ночью он серый.

2.Треугольник с равными сторонами правильный. У этого треугольника все стороны равны. Значит он – правильный.

Ничем! Если первая и вторая фразы верны, верен и вывод. Именно так и была построена геометрия Евклида: несколько фраз были объявлены верными; если же они верны, то истинны все выводы, правильно построенные (по законам логики) на основе этих нескольких фраз…

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

Философия рассматривает познание как диалектичес­кий процесс отражения действительности в сознании лю­дей. Он осуществляется в двух основных формах: в форме чувственного познания и в форме абстрактного мышления, Чувственное познание позволяет нам отражать отдельные предметы и их свойства в виде ощущений, восприятий и представлений. Например, покупая какой-либо товар, мы оцениваем его вкусовые и обонятельные качества, прики­дываем, радует ли он наш глаз и т. и. Логическое познание, существующее в форме понятий, суждений и умозаключе­ний, позволяет нам проникать в глубинные структуры ве­щей и явлений. С его помощью мы даем название покупае­мому товару, судим о цене и целесообразности покупки. Если философия дает нам общее представление о ступенях, этапах познания, то логика занимается преимущественно логической ступенью. В центре ее внимания понятия, суждения и умозаключения как важнейшие инструменты мыслительной деятельности людей. Если философия оценивает результативность познания с помощью понятия ис­тины, то логика рассматривает вышеназванные формы как способы получения истинного знания. Если философия интересуется наиболее общими законами природы, общес­тва и мышления, то предметом логики являются те законы

II. Основная часть

1. Теоретические основы математической логики, ее законы.

Помимо законов материалистической диалектики человеческое мышление подчиняется еще законам логики. Вот основные законы логики: закон тождества, закон непротиворечия, закон исключенного третьего, закон достаточного основания и т.д. Они используются при оперировании понятиями и суждениями, применяются в умозаключениях, доказательствах и опровержениях. Первые три были открыты Аристотелем, четвертый - В. Г. Лейбницем. Логические законы отражают в сознании человека определенные отношения, существующие между объектами, или отражают такие обычные свойства предметов, как их относительная устойчивость, определенность, несовместимость в одном и том же предмете одновременного наличия и отсутствия одних и тех же признаков. Законы логики отражают объективное в субъективном сознании человека, поэтому их нельзя отменить или заменить другими. имеют общечеловеческий характер, т. к. они едины для людей всех рас, наций, профессий. Основные логические законы сложились исторически в результате многовековой практики познания. Они отражают такие важные свойства правильного мышления, как его определенность, непротиворечивость, обоснованность, четкость мышления, выбор "или-или" в определенных "жестких" ситуациях. Кроме основных, существует много неосновных законов логики, которые надо выполнять при оперировании понятиями, или суждениями, или умозаключениями. Законы логики, как основные, так и неосновные в мышлении функционируют в качестве принципов правильного рассуждения в ходе доказательства истинных суждений и теорий и опровержения ложных суждений и ложных гипотез. Законы логики играют роль универсальных связей мышления и общих принципов любой мыслительной деятельности, выражающих требования методологического характера. Нарушение Законов логики приводит к логической ошибке - как непреднамеренной - паралогизму (от греч. paralogismos), так и сознательной - софизму (от греч. sophisma – уловка, выдумка, головоломка), хотя эти типы ошибок возникают и в других ситуациях.

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

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

Закон непротиворечия.

Закон непротиворечия формулируется так: "Два противоположных суждения не могут быть истинными в одно и то же время и в одном и том же отношении.

В предметах объективного мира невозможно одновременное присутствие и отсутствие какого-либо свойства или отношения (например, невозможно в один и тот же момент делать какую-то работу и ничего не делать). Одновременное утверждение о каком-нибудь предмете, действии, признаке предмета и т. д. и отрицание этого утверждения есть формально-логическое противоречие. Идея, выражаемая законом непротиворечия, проста: высказывание и его отрицание не могут быть одновременно истинными. Пусть х обозначает непроизвольное высказывание, не-х – отрицание этого высказывания. Тогда закон можно представить так: « неверно, что х и не-х ». Неверно, например, что Солнце – звезда и Солнце не является звездой, что человек – разумное существо и вместе с тем не является разумным, таких примеров можно привести множество.

К противоположным относятся суждения простые следующих 4 типов (здесь S - одинаковые термины и Р - одинаковые термины).

1. А - "Данное S есть Р" и Е - "Данное S не есть Р".

2. А - "Все S есть Р" и Е - "Ни одно S не есть Р".

3. А - "Все S есть Р" и О - "Некоторые S не есть Р".

4. Е - "Ни одно S не есть Р" и J - "Некоторые S есть Р".

1, 3, 4-я пары суждений таковы, что если одно из суждений этой пары истинно, то другое обязательно ложно, поэтому они называются противоречащими или отрицающими друг друга, и их можно обозначить а и а (не-а). Конъюнкция их, т. е. формула а \/ а выражает формально-логическое противоречие. Суждения 2-й пары А и Е могут быть одновременно ложными, поэтому их нельзя обозначить как а и а (например, "Все богатые люди счастливы" и "Ни один богатый человек не является счастливым"). В исчислении высказываний двузначной логики закон непротиворечия выражается формулой а, /\ а. (Неверно, что а и не-а). Но эта формула не полностью, неадекватно представляет закон непротиворечия, открытый Аристотелем, т. к. она не распространяется на суждения А и Е, а закон непротиворечия Аристотеля распространяется на них. Противоречия не возникают, если речь идет о разных предметах или об одном предмете, но взятом в разном отношении или рассматриваемом в разное время (например, суждение "Эта книга является новой" и суждение "Эта книга не является новой" не противоречат друг другу, если речь идет об одной и той же книге, но рассматриваемой в разное время).

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

Но нет противоречия в утверждении « осень настала и еще не настала». Подразумевается, что, хотя по календарю уже осень, тепло, как летом. Точно так же, как нет его в предложениях: «Речка движется и не движется. Песня слышится и не слышится».

Отношение логики к противоречиям лишено двусмысленности и неопределенности: где есть противоречия, там логика поколеблена.

« Логической противоречивости, -- писал В.И.Ленин, -- при условии, конечно, правильного логического мышления – не должно быть не в экономическом, не в политическом анализе».

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

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

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

Неявные противоречия. Никто, пожалуй, не утверждает прямолинейно, что дождь идет и не идет или что трава зеленая и одновременно не зеленая. А если и утверждает, то только в переносном смысле. Противоречия вкрадываются в утверждения, как правило, в неявном виде. Чаще всего противоречия довольно легко обнаружить.

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

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

-- Сеньор, немой явился…и хочет с вами поговорить.

Давая партнеру, возможность поправить ошибку, другой актер ответил:

-- А Вы уверены, что он немой?

-- Во всяком случае, он сам так говорит…

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

Противоречие может быть и более скрытным.

М.Твен рассказывает о беседе с репортером, явившемся взять у него интервью:

-- Если у вас брат?

-- Да, мы звали его Билль. Бедный Билль.

-- Так он умер?

-- Мы никогда не могли узнать этого. Глубокая тайна парит над этим делом. Мы были – усопший и я – двумя близнецами и, имея две недели от роду, купались в одной лохани. Один из нас утонул, но никогда не могли узнать который. Одни думают, что Билль, другие – что я.

-- Странно, но вы-то, что вы об этом думаете?

-- Слушайте, я открою вам тайну, которой не поверял еще ни одной живой душе. Один из нас двоих имел особенный знак на левой руке, и это был я. Так что тот ребенок, что утонул…

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

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

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

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

Испанский писатель XVI-XVII вв. Ф.Кеведо так озаглавил свою сатиру: «Книга обо всем и еще, о многом другом». Его не смутило то, что, если книга охватывает «все», для «многого другого» уже не остается места.

Классической фигурой стилистики, едва ли не ровесницей самой поэзии является оксюморон – сочетание логически враждующих понятий, вместе создающих новое представление. «Пышное природы увядание», «свеча темно горит» (А.С.Пушкин), «живой труп» (Л.Н.Толстой), «ваш сын прекрасно болен» (В.В.Маяковский) – все это оксюмороны. А в строках стихотворения А.А.Ахматовой «смотри, ей весело грустить, такой нарядно обнаженной» сразу два оксюморона. Один поэт сказал о Г.Р.Державине: «Он врал правду Екатерине». Без противоречия так хорошо и точно, пожалуй, не скажешь.

«…Все мы полны противоречий. Каждый из нас – просто случайная мешанина несовместимых качеств. Учебник логики скажет вам, что абсурдно утверждать, будто желтый цвет имеет цилиндрическую форму, а благодарность тяжелее воздуха; но в той смеси абсурдов, которое составляет человеческое «Я», желтый цвет вполне может оказаться лошадью с тележкой, а благодарность – серединой будущей недели». Этот отрывок из романа английского писателя С.Моэма «Луна и грош» выражает сложность, а нередко и прямую противоречивость душевной жизни человека. «…Человек знает, что хорошо, но делает то, что плохо», -- с горечью заметил Сократ.

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

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

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

Есть, однако, теория, в случае которой десятилетия упорнейших усилий не дали ответа на вопрос, является она противоречивой или нет. Это математическая теория множеств, лежащая в основе всей математики. Закон непротиворечия не действует в логике “размытых” множеств, ибо в ней к “размытым” множествам, “размытым” алгоритмам можно одновременно применять утверждение и отрицание (напр., “Этот мужчина пожилой” и “Он ещё не является пожилым”, т.к. понятие “пожилой мужчина” является “нечетким” понятием, не имеющим чётко очерченного объёма). До сих пор речь шла о выражении формально-логического противоречия в форме а, но оно может выражаться и без отрицания, когда берутся несовместимые утвердительные суждения (об этом см. Закон тождества). На таком противоречии построен габровский анекдот под названием “Реклама”:

Значит, это самая новая ткань?

Только вчера получил, прямо с фабрики!

А она не линючая?

Да что вы! Больше месяца висела на витрине, и ничего ей не сделалось!

Закон непротиворечия квалифицирует формально-логическое противоречие как серьёзную ошибку, несовместимую с логическим мышлением.

^ Закон исключенного третьего.

Формулировка закона исключенного третьего такова: "Из двух противоположных суждений, одно истинно, другое ложно, а третьего не дано" .

Закон исключенного третьего, как и закон непротиворечия, он устанавливает связь между противоречащими друг другу утверждениями: из двух таких утверждений одно является истинным. У предметов объективного мира какой-либо признак, или присутствует, или его нет. Так, например, из двух суждений: "У птицы есть крылья", и "У птицы нет крыльев", первое истинно, второе - ложно, и третьего - промежуточного - суждения не может быть. Закон исключенного третьего впервые был открыт и сформулирован Аристотелем. Двузначная логика имеет дело с жесткой ситуацией, где суждение может быть либо истинным, либо ложным и каждое суждение может иметь только одно из этих истинностных значений. В противоречащих (контрадикторных) суждениях, отрицающих друг друга, одно суждение истинно, а другое - ложно. К противоречащим относятся суждения простые следующих трех типов, где S - одинаковые термины и P - одинаковые термины: 1. - "Данное S есть P" и Е - "Данное S не есть Р". 2. А - "Все S есть Р" и О - "Некоторые S не есть Р". 3. Е - "Ни одно S не есть Р" и J - "Некоторые S есть Р". Одно из этих суждений в каждой из пар можно обозначить переменной а, а другое - а. Формула закона исключенного третьего в исчислении высказываний двузначной логики записывается так: а \/ а (где знак "\/" обозначает нестрогую дизъюнкцию, союз "или"). Точнее этот закон выражается формулой а \/ а, где "\/" обозначает строгую дизъюнкцию, характеризующую несовместимость а и а. В мышлении закон исключенного третьего предполагает четкий выбор одной из двух взаимоисключающих альтернатив ("да" или "нет"). С другой стороны, действие этого закона ограничено наличием неопределенности в познании, причинами которой являются различные переходные состояния и ситуации, т. е. изменения, переход предметов и их отдельных свойств в свою противоположность (например, теплая еда через некоторое время остывает и становится холодной, новая обувь со временем становится старой и др.). Кроме того, отражение объективного мира на определенном этапе познания всегда неполно, неточно, т. к. соответствует лишь этому этапу знаний человека о мире. Например, нельзя заранее сказать, какое суждение о каком-нибудь будущем событии будет истинным, до тех пор пока действие не закончится. Пример таких суждений: "Завтра я непременно справлюсь с заданием" или "Завтра я ни за что не справлюсь с заданием". Закон исключенного третьего не действует, когда имеются три или более значений истинности суждений. В трехзначной логике используются три значения истинности суждений (например, социологических анкетах предлагаются три ответа: "да", "нет" и "не знаю"; при голосовании предусматриваются следующие позиции: "за", "против" и "воздержался". В неклассических многозначных логиках закон исключенного третьего, т. е. формула а \/ а не является тавтологией (или выводимой формулой).

Рассказывают историю про одного владельца собаки, который очень гордился воспитанием своего любимца. На его команду: «Эй! Приди или не приходи!» -- собака всегда либо приходила, либо нет. Так что команда в любом случае оказывалась выполненной.

Человек говорит прозой или не говорит прозой, кто-то рыдает или не рыдает, собака выполняет команду или не выполняет и т.п. – других вариантов не существует. Мы можем не знать, противоречива некоторая конкретная теория или нет, но на основе закона исключенного третьего еще до начала исследования мы вправе заявить: она или непротиворечива, или противоречива.

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

В сказке А.Н.Толстого «Золотой ключик, или Приключения Буратино» народный лекарь Богомол заключает после осмотра Буратино:

-- Одно из двух: или пациент жив, или он умер. Если он жив – он останется, жив или не останется жив. Если он мертв – его можно оживить или нельзя оживить.

Закон исключенного третьего кажется самоочевидным, и трудно представить, что кто-то мог предложить отказаться от него. Немецкий математик Д.Гильберт утверждал даже, что «отнять у математиков закон исключенного третьего – это то же самое, что забрать у астрономов телескоп или запретить боксерам пользоваться кулаками». И, тем не менее в современной логике имеются системы, в которых этот закон отбрасывается. Очевидное в одно время и в одних обстоятельствах способно потерять свою очевидность в другое время и в свете других обстоятельств.

Закон тождества.

Закон тождества формулируется так: “В процессе определённого рассуждения всякое понятие и суждения должны оставаться тождественными самим себе”.

Закон тождества – один из основных законов правильного мышления, соблюдение которого помогает определённости, точности и ясности употребления понятий и суждений. Умозаключение:

Материя вечна.

Сукно – материя.

Сукно вечно.

построено не правильно, ибо понятие “материя” в первой и второй посылках трактуется в разных смыслах, - в философском и обыденном, следовательно, произошло нарушение закона тождества

Закон тождества в традиционной логике (Двузначная логика) для суждений записывают как “а есть а”, а для понятий “А есть А”. В математической логике закон тождества представляется в логике высказываний как а а, или а – а, где а обозначает любое высказывание (суждение). В философии тождество понимается как равенство, сходство двух или нескольких предметов в каком либо отношении. Например, все гейзеры тождественны в том, что они являются источниками, периодически выбрасывающими фонтаны горячей воды и пара до высоты 20-40 м и более. В природе и обществе нет даже двух абсолютно тождественных предметов (например, двух близнецов, двух одинаковых цветков и т.д.), тождество существует в связи с различием. Но мы отвлекаемся от существующих различий и фиксируем своё внимание только на тождестве.

Закон тождества в мышлении представляет собой нормативное правило (принцип), гласящие, что в процессе рассуждения нельзя подменять одну мысль другой, одно понятие другим, иначе возникнут логические ошибки, называемые “подменой понятия” или “подменой тезиса”. Закон тождества означает также, что тождественные мысли нельзя выдавать за различные, и наоборот, различные – за тождественные. Люди, выступающие не по обсуждаемой теме или употребляющие термины и понятия в ином смысле, чем принято, и не предупреждающие об этом, нарушают закон тождества. Например, иногда люди вкладывают различный смысл в такие понятия, как “материалист”, “идеалист”, “наука”, “демократия”, “свобода слова” и др., поэтому происходит отождествление нетождественного, то есть нарушение закона тождества. Логические ошибки часто происходят при употреблении омонимов, то есть слов, имеющих два или более значений (“движение”, “следствие”, ”ребро”, “поле”, “коса”, ”мир” и т.д.). Например, “Из-за рассеянности шахматист не раз на турнирах терял очки”. На нарушении закона тождества строятся анекдоты, каламбуры, двусмысленности. Например, один из габровских анекдотов под названием “Логика”:

Какая температура в комнате? – спросил габровец у жены.

Пятнадцать градусов, - ответила жена.

А на улице?

Двадцать.

Тогда открой окно, - распорядился он, - пусть войдут ещё пять градусов.

Соблюдение закона тождества в мышлении помогает избежать непонимания

Закон тождества, пожалуй, самый простой из всех логических законов Древнекитайский философ Конфуций поучал своего ученика: «То, что знаешь, считай, что знаешь, то, что не знаешь, считай, что не знаешь». Это не просто повторение одного и того же: знать что-либо и знать, что это знаешь, не одно и то же.

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

Законы контрапозиции говорят о перемене позиций высказываний с помощью отрицания: из условного отрицания «Если А, то В» вытекает высказывание «Если не – В, то не – А», и наоборот; из «если А, то не - В» вытекает «Если В, то не - А»; из «Если не – А, то В» следует «Если не – В, то А». Например, из «Если сверкает молния, то гремит гром» следует «Если нет грома, то нет и молнии»; из «Если нет причины, нет и следствия» вытекает «Если есть следствие, есть также причина» и т.п. контрапозиция – это, выражаясь шахматным языком, рокировка высказываний. Редкая шахматная партия обходится без рокировки, и редкое наше рассуждение проходит без использования контрапозиции.

Закон, названный именем шотландского логика прошлого века А. де Моргана, но известный еще со средних веков, связывает между собою «и» и «или»: «неверно, что А и В, только в том случае, когда не –А или не –В; неверно, что А или В, только если неверно А и неверно В».

Два закона, известные еще с глубокой древности, -- это так называемые «модус поненс» и «модус толленс». Первый из них позволяет от утверждения условной связи и утверждения ее основания перейти к утверждению ее следствия. Второй говорит, что если следствие правильной условной связи неверно, то неверным является и его основание. Например, если справедливо, что в случае дождя земля обязательно мокрая, и верно, что идет дождь, то верно, что земля мокрая. Если же верно, что в дождь земля всегда мокрая, а она не является мокрой, то это означает, что дождь не идет.

Шерлок Холмс однажды заметил: «Отбросьте все невозможное, и то, что останется, будет ответом». Имеется в виду закон: «или А, или В, или С; но А неверно и В неверно; следовательно, С».

Еще один логический закон говорит об ошибочных следствиях: «Если А, то В или С; но В неверно и С неверно; значит, неверно и А».

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

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

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

«И»,»Или»

«Или», «И». всякое высказывание может быть истинным или ложным. Третий вариант трудно себе представить, поэтому древнегреческие философы и пользовались «принципом исключенного третьего» -- считали, что не может утверждение быть и не истинным, и не ложным. Вслед за ними также считаем и мы. Логика без принципа «исключенного третьего» упоминается разве лишь в фантастических романах, да и то в шутку…

А теперь попробуем собрать одно высказывание из двух частей. Как мы часто это делаем, соединим две фразы словечком «или». «В углу шуршит мышь или крокодил». Верно ли это высказывание? Зависит от того, кто на самом деле шуршит в углу. Если это и вправду мышь, фраза верна. Если (как не трудно себе это представить) это крокодил, опять же высказывание верно. Если в углу дружно шуршат мышь с крокодилом, она верна снова! И лишь если в углу нет ни мыши, ни крокодила, а шуршит сбежавший из клетки хомяк, высказывание оказывается ложным. Это – свойство, присущее именно «или»: два утверждения, связанные этим словом, составляют верное высказывание, если хотя бы одно из утверждений справедливо, и ложное, если оба утверждения неверны. А теперь составим маленькую табличку (здесь И – «истинное утверждение», Л – «ложное»):

И или И = И

И или Л = И

Л или И = И

Л или Л = Л

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

И и И = И

И и Л = Л

Л и И = Л

Л и Л = Л

Фраза, связанная этим словом, верна в том единственном случае, когда верны обе части!

В этом тексте несколько раз употреблялась конструкция фразы «если так, то будет этак». Посмотрим, когда верно утверждение такого типа? Оно верно, если верна первая часть (посылка) и одновременно верна вторая (заключение). Оно неверно, если верна посылка, но неверен вывод: несомненно, ложным является высказывание «если разбить чашку, то будет землетрясение». А если посылка неверна? Может показаться невероятным, но в этом случае высказывание истинно. Из ложной посылки следует что угодно! На самом деле ничего удивительного в этом нет: вам самим случалось, и не раз, употреблять фразы вроде «если 2х2=5, то я папа римский». Попробуйте доказать, что такое утверждение ложно! Оно означает лишь, что 2х2 не равно 5, и вы не папа римский, следовательно, оно истинно. Получим такую таблицу истинности:

И → И = И

И → Л = Л

Л → И = И

Л → Л = И

«И» и «или» -- это элементарные действия логики, так же как сложение и умножение – это действия арифметики. Между логическими и арифметическими операциями есть некоторое сходство, и сейчас мы его продемонстрируем. Пусть у нас только две цифры, 0 и 1. будем обозначать истину единицей, а ложь – нулем. Тогда наша табличка истинности для «или» напоминает таблицу двоичного сложения: 0+0=0; 1+0=!; 0+1=1, и только для «сложения» двух истин (1+1=1) мы получим не тот ответ, который дает нам двоичная арифметика (там 1+1=10), но по большому счету он не слишком сильно отличается от арифметического, ибо нуля мы не получим все равно. Результат же логического умножения – «и» -- полностью совпадает с арифметическим: 0х0=0; 1х0=0; 0х1=0; 1х1=1…

Закон достаточного основания.

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

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

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

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

^ Закон контрапозиции

«Закон контрапозиции» — это общее название для ряда логических законов, позволяющих с помощью отрицания менять ме^ Конструктивная и деструктивная дилеммы

Дилеммами называются рассуждения, посылками которых являются, по меньшей мере, два условных высказывания (высказывания с «если, то») и одно разделительное высказывание (высказывание с «или»).

Выделяются следующие разновидности дилеммы.

^ Простая конструктивная (утверждающая) дилемма:

Если А, то С.

Если В, то С.

А или В. - С

Например: «Если прочту детектив Агаты Кристи, то хорошо проведу вечер; если прочту детектив Жоржа Сименона, тоже хорошо проведу вечер; прочту детектив Кристи или прочту детектив Сименона; значит, хорошо проведу вечер».

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

Если бы было справедливо первое допущение, теорема была бы верна;

при справедливости второго допущения теорема также была бы верна;

при верном третьем допущении теорема ве

www.ronl.ru

Реферат: Математическая Логика

Конспекты лекций по математической логике.

1. Теория алгоритмов

1.1 Различные подходы к определению алгоритма:

10 . Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).

20 . Машина с неограниченными регистрами (МНР).

30 Машина Тьюринга – Поста (МТ-П).

40 Нормальные алгоритмы Маркова (НАМ).

1.1.1 Машина с неограниченными регистрами (МНР).

Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.

Допустимые команды:

Z(n) - обнуление регистра Rn .

S(n) - увеличение числа в регистре Rn на 1.

T(m,n) - копирует содержимое Rm в регистор Rn .

I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером n , если нет

следующая.

Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.

Тезис Черча ( Churcha ) : Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.

1.1.2 Машина Тьюринга - Поста.

Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: , где - пустой символ (пустое слово), который может принадлежать и не принадлежать А . Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии. Также существуют внутренние состояния машины:

Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).

Допустимые команды:

1) ,где .

2) (остановка программы).

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

1.1.3 Нормальные алгоритмы Маркова.

Тип машины перерабатывающий слова, в которой существует некий алфавит , для которого W - множество всех слов.

Допустимые команды: (Для машин этого типа важна последовательность команд.)

1.1.4 Реализация функции натурального переменного.

но мы допускаем не всюду определенную функцию.

то это означает, что

притом ,если f не определена, то и программа не должна ничего выдавать.

притом ,если f не определена, то и программа не должна ничего выдавать.

(, а числа представляются в виде ,например .)

1.2 Эквивалентность трех подходов к понятию алгоритм.

1.2.1 Теорема об эквивалентности понятия вычислимой функции.

вычислима: ()

1) Если существует программа МНР, которая вычисляет эту функцию.

2) Если существует программа МТ-П, которая вычисляет эту функцию.

3) Если существует программа НАМ, которая вычисляет эту функцию.

Использование НАМ:

Теор .: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.

Пусть которая вычисляется на МТ-П, вычислим её на НАМ.

МТ-П:

НАМ:

Команда МТП: преобразуется по правилам:

Команда МТП:

2. Булевы функции.

2.1 Основные определения

2.1.1 Декартово произведение

- мн-во всевозможных упорядоченных пар элементов из А и В.

Пример :

2.1.2 Декартова степень произвольного множества.

Опр : - множество всевозможных упорядоченных наборов длины n , элементов множества А.

2.1.3 Определение булевой функции от n переменных.

Любое отображение - называется булевой функцией от n переменных, притом множество

2.1.4 Примеры булевой функции.

1) логическая сумма (дизъюнкция).

2) логическое умножение (конъюнкция).

3) сложение по модулю два.

4) логическое следствие (импликация).

5) отрицание.

2.1.5 Основные булевы тождества.

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

2) (коммутативность)

3) (свойство нуля)

4) (закон поглощения для 1)

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

6) (коммутативность)

7) (свойство нуля по умножению)

8) (свойство нейтральности 1 по умножению)

9) (дистрибутивность)

10) (дистрибутивность 2)

11) (закон поглощения)

12) ( Законы

13) де Моргана)

14) (закон снятия двойного отрицания)

15) (tertium non datur – третьего не дано)

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

17)

18)

19)

20)

21) (Свойства

22) идемпотентности)

2.2 Дизъюнктивные нормальные формы.

2.2.1 Основные определения.

- конечный алфавит из переменных.

Рассмотрим слово:

Экспоненциальные обозначения:

- элемент конъюнкции.

S – длина элемента конъюнкции.

ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.

Любая булева функция может быть представлена как ДНФ

2.2.2 Теорема о совершенной ДНФ.

Любая булева функция тождественно не равная 0 может быть разложена в ДНФ следующего вида:

Опр : Носитель булевой функции

.

Лемма :

1) это элементарно

2) возьмем набор

а)

б)

Доказательство: , будем доказывать, что.

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

2) Докажем, что . Возьмем другой набор из

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

2 .2.3 Некоторые другие виды ДНФ.

Опр: - называется минимальной ДНФ , если она имеет - наименьшую возможную длину из всех ДНФ данной функции.

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

(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)

Опр: К-мерной гранью называется такое подмножество , которая является носителем некоторой элементарной конъюнкции длины: n-k.

Опр: Предположим дана функция и есть . Грань называется отмеченной , если она целиком содержится в носителе Т .

Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.

Предложение: Любую отмеченную грань можно вложить в максимальную грань.

Предложение:

(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)

Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.

Опр: Элементарная конъюнкция называется минимальной , если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.

Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.

Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.

3 Логические Исчисления.

3.1 Исчисления высказывания (ИВ).

3.1.1 Определения.

Опр: V – словом в алфавите А , называется любая конечная упорядоченная последовательность его букв.

Опр: Формативная последовательность слов – конечная последовательность слов и высказываний , если они имеют формат вида:

Опр: F – формулой ИВ , называется любое слово, входящее в какую-нибудь формативную последовательность.

Пример:

Опр: Аксиомы – специально выделенное подмножество формул.

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

Reg – правила вывода ИВ (некоторые правила преобразования первого слова в другое).

a – символ переменной

- произвольное слово ИВ (формула)

Отображение действует так, что на место каждого вхождения символа а , пишется слово .

Пример:

Правило modus ponens :

3.1.2 Формальный вывод. (простейшая модель доказательства теоремы)

Опр: Последовательность формул ИВ, называется формальным выводом, если каждая формула этой последовательности имеет следующий вид:

Опр: Выводимый формулой (теоремой) ИВ называется любая формула входящая в какой-нибудь формальный вывод. - выводимая формула ИВ.

Пример:

Правило одновременной подстановки.

Замечание : Если формула выводима, то выводима и

Возьмем формативную последовательность вывода и добавим в неё , получившаяся последовательность является формальным выводом.

(Если выводима то если , то выводима )

Теор: Если выводимая формула , то ( - различные символы переменных) выводима

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

3.1.3 Формальный вывод из гипотез.

Опр: Формальным выводом из гипотез (формулы), называется такая последовательность слов , каждая из которых удовлетворяет условию:

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

Лемма: ; : то тогда

Напишем список:

Лемма :

Док:

3.1.4 Теорема Дедукции.

Если из

1) и 2а) , где по правилу m.p., ч.т.д.

2б) - уже выводили , ч.т.д.

Базис индукции: N=1 - формальный вывод из длинного списка

(только что доказано), осуществим переход по индукции:

по индукции

и по лемме 2

Пример:

по теореме дедукции

3.2 Критерий выводимости в ИВ.

3.2.1 Формулировка теоремы.

- тавтология

при любой интерпретации алфавита (символов переменных)

3.2.2 Понятие интерпретации.

символ переменной переменную поставим в соответствие.

, где - проекция на .

; - только символ

переменных, т.к.

это заглавное слово

формативной последо-

вательности вида:

Где:

3.2.3 Доказательство теоремы.

формальный

вывод

(1)

3.3 Непротиворечивость ИВ.

3.3.1 Определение.

1) ИВ противоречиво , если формула А выводима в нем. .

2) формула выводима в ИВ)ИВ противоречиво .

3) ИВ противоречиво .

ИВ непротиворечиво , если оно не является противоречивым.

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

Док-во : (1) Если , то соответствующая ей булева функция будет тождественно равна 1.

(2) Если любая формула выводима, то выводима и А , что соответствует пункту 1.

(3) Пусть и - булева функция

- противоречие.

3.4 Формальные исчисления.

Алфавит – конечное или счетное множество символов, возможно, разбитых на группы. Алфавит должен быть упорядоченным множеством.

Слово – конечная упорядоченная последовательность символов алфавита, в т.ч. пустое слово.

V – множество всех слов.

Вычислимая функция от нескольких натуральных переменных

( f – может быть не всюду определенной )

f – называется вычислимой , если такая машина Тьюринга, которая её вычисляет.

- разрешимое множество, если характеристическая функция

- является вычислимой.

Множество называется перечислимым, если такая вычислимая функция

М - разрешимо М и N \M перечислимы.

М – перечислимо М – область определения некоторой вычислимой функции.

Множество всех формул F – некоторое разрешимое подмножество V .

Т – счетное множество, если его биективное отображение на V .

- обозначение счетного множества. ( - алеф-нуль)

Если и зафиксировано биективное и вычислимое отображение (вычис.),

то L – ансамбль .

V – ансамбль (слова лексикографически упорядочены и занумерованы)

Определение : В произвольном формальном исчислении: - множество всех аксиом – разрешимое подмножество множества всех формул.

Правило вывода:

,при разрешимо. Для ИВ N =2.

Пример :

(пустое слово) ,

1 и 2 – формальные выводы.

3 – не является формальным выводом.

4 Предикаты и кванторы.

4.1 Определение предиката.

- высказывание, содержащее переменную.

- предметная область предиката.

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

- местный предикат – произвольное отображение

Множество истинности данного предиката

-

- характеристическая

функция от x на множестве

А - совпадает

с предикатами

4.2 Понятие квантора.

k – связанная переменная

n – свободная переменная

t – свободная, x – связанная.

, a,b,y – свободные переменные, x – связанная.

4.3 Геометрическая интерпретация навешивания кванторов.

Пронесение отрицания через кванторы

Геометрическое 'доказательство':

не обладает свойством, что прямая целиком лежит в

ч.т.д.

www.yurii.ru

Доклад - Математическая логика и логика здравого смысла

СОДЕРЖАНИЕ

Введение. 3

1.Математическая логика (бессмысленная логика) и логика «здравого смысла» 4

2. Математические суждения и умозаключения. 6

3.Математическая логика и «Здравый смысл» в XXI веке. 11

4.Неестественная логика в основаниях математики. 12

Заключение. 17

Список литературы… 18

Введение

Расширение области логических интересов связано с общими тенденциями развития научного знания. Так, возникновение математической логики в середине XIX века явилось итогом многовековых чаяний математиков и логиков о построении универсального символического языка, свободного от «недостатков» естественного языка (прежде всего его многозначности, т.е. полисемии).

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

Выделение основных направлений современной логики:

1. общей, или классической логики;

2. символической, или математической логики;

3. неклассической логики.

1. Математическая логика (бессмысленная логика) и логика «здравого смысла»

Математическая логика понятие достаточно неконкретное, из-за того, что математических логик также бесконечно много. Здесь будем обсуждать некоторые из них, отдавая больше дань традиции, чем здравому смыслу. Поскольку, весьма возможно, в этом и заключен здравый смысл… Логично?

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

Пожалуй, настало время сказать про логику, возможно, самое главное: классическая логика не занимается смыслом. Ни здравым, ни каким другим! Для изучения здравого смысла, между прочим, существует психиатрия. Но в психиатрии логика скорее вредна.

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

(Хорошо сложилось последнее предложение, хотя определить термин «логическая наука» не возьмусь даже приблизительно). Смыслом, если угодно — семантикой, занимается, например, теория моделей. Да и вообще, термин семантика часто заменяют термином интерпретация. И если мы согласимся с философами, что интерпретация (отображение!) об'екта есть осмысление его в некотором данном аспекте, то пограничные сферы математики, которые могут привлекаться для наступления на смысл в логике, становятся неохватными!

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

Еще лишь упомянем апофеоз — ТЕОРИЮ КАТЕГОРИЙ, которая довела семантику до формального малопонятного синтаксиса, где смысл уже настолько простой — разложенный по полочкам, что до него простому смертному совсем невозможно докопаться… Это для избранных.

Так чем же занимается логика? Хотя бы в самой классической ее части? Логика занимается только тем, чем она занимается. (А это она определяет предельно строго). Главное в логике – это строго определиться! Задать аксиоматику. А дальше логические выводы должны быть(!) в значительной степени автоматическими...

Другое дело рассуждения по поводу этих выводов! Но эти рассуждения уже вне рамок логики! Поэтому в них требуется строгий математический смысл! [6]

Может показаться, что это простая словесная эквилибристика. НЕТ! В качестве примера некоторой логической (аксиоматической) системы возьмем известную игру 15. Зададим (перемешаем) начальное расположение квадратных фишек. Далее игрой (логическим выводом!), а конкретно — перемещением фишек на свободное место, может заниматься некое механическое устройство, а вы можете терпеливо смотреть и радоваться, когда в результате возможных передвижек в коробочке сложится последовательность от 1 до 15. Но никто не запрещает контролировать механическое устройство и подсказывать ему, ИСХОДЯ ИЗ здравого СМЫСЛА правильные перемещения фишек, чтобы ускорить процесс. А может быть даже доказать, используя для логических рассуждений, например, такой раздел математики, как КОМБИНАТОРИКА, что при данном начальном расположении фишек получить требуемую финальную комбинацию невозможно вообще!

Не больше здравого смысла присутствует и в той части логики, которую называют ЛОГИЧЕСКОЙ АЛГЕБРОЙ. Здесь вводятся ЛОГИЧЕСКИЕ ОПЕРАЦИИ и определяются их свойства. Как показала практика, в некоторых случаях законы этой алгебры могут соответствовать логике жизни, а в некоторых нет. Из за такого непостоянства законы логики нельзя считать законами с точки зрения практики жизни. Их знание и механическое использование может не только помогать, но и вредить. Особенно психологам и юристам. Ситуация осложняется тем, что наряду с законами алгебры логики, которые то соответствуют, то не соответствуют жизненным рассуждениям, есть логические законы, которые часть логиков категорически не признают. Это относится прежде всего к так называемым законам ИСКЛЮЧЕННОГО ТРЕТЬЕГО и ПРОТИВОРЕЧИЯ.

В мышлении понятия не выступают разрозненно, они определенным способом связываются между собой. Формой связи понятий друг с другом является суждение. В каждом суждении устанавливается некоторая связь или некоторое взаимоотношение между понятиями, и этим самым утверждается наличие связи или взаимоотношений между объектами, охватываемыми соответствующими понятиями. Если суждения правильно отображают эти объективно существующие зависимости между вещами, то мы такие суждения называем истинными, в противном случае суждения будут ложными. Так, например, суждение «всякий ромб является параллелограммом» — истинное суждение; суждение «всякий параллелограмм является ромбом» — ложное суждение.

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

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

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

Суждение имеет свою языковую оболочку — предложение, однако не всякое предложение является суждением.

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

Например, предложение «треугольник АВС равнобедренный» выражает некоторое суждение; предложение «Будет ли АВС равнобедренным?» не выражает суждения.

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

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

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

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

Сумма внутренних углов треугольника равна 2d (второе суждение).

Сумма внутренних углов параллелограмма равна 4d (новое суждение-вывод).

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

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

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

Например, из суждений «сумма внутренних углов треугольника равна 2d» и «2*2=4» нельзя сделать вывод.

Понятно, какое значение в системе наших математических знаний имеет умение правильно строить различные математические предложения или делать выводы в процессе рассуждения. Разговорный язык плохо приспособлен для выражения тех или иных суждений, а тем более для выявления логической структуры рассуждений. Поэтому естественно, что возникла необходимость усовершенствования языка, используемого в процессе рассуждения. Математический (а точнее, символический) язык оказался для этого самым подходящим. Возникшая" в XIX в. специальная область науки — математическая логика не только полностью решила проблему создания теории математического доказательства, но и оказала большое влияние на развитие математики в целом.

Формальную логику (возникшую еще в глубокой древности в трудах Аристотеля) не отождествляют с математической логикой (возникшей в XIX в. в работах английского математика Дж. Буля). Предметом формальной логики является изучение законов взаимосвязи суждений и понятий в умозаключениях и правилах доказательства. Математическая логика отличается от формальной логики тем, что она, исходя из основных законов формальной логики, исследует закономерности логических процессов на основе применения математических методов: «Логические связи, которые существуют между суждениями, понятиями и т. д., находят свое выражение в формулах, толкование которых свободно от неясностей, какие легко могли бы возникнуть при словесном выражении. Таким образом, для математической логики характерна формализация логических операций, полнее абстрагирование от конкретного содержания предложений (выражающих какое-либо суждение).

Проиллюстрируем сказанное одним примером. Рассмотрим следующее умозаключение: „Если все растения красные и все собаки — растения, то все собаки красные“.

Каждое из используемых здесь суждений и то суждение, которое мы получили в результате сдержанного умозаключения, кажется явной бессмыслицей. Однако с точки зрения математической логики мы имеем здесь дело с верным предложением, так как в математической логике истинность или ложность умозаключения зависит только от истинности или ложности составляющих его посылок, а не от их конкретного содержания. Поэтому если одним из основных понятий формальной логики является суждение, то аналогичным ему понятием математической логики является понятие высказывания-утверждения, для которого имеет смысл лишь говорить, истинно оно или ложно. Не следует думать, что для каждого высказывания характерно отсутствие „здравого смысла“ в его содержании. Просто содержательная часть предложения, составляющего то или иное высказывание, в математической логике отходит на второй план, несущественна для логического построения или анализа того или иного вывода. (Хотя, конечно существенна для. понимания содержания того, о чем идет речь при рассмотрении o данного вопроса.)

Понятно, что в самой математике рассматриваются содержательные высказывания. Устанавливая различные связи и отношения между понятиями, математические суждения утверждают или отрицают какие-либо отношения между объектами и явлениями реальной действительности.

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

Для многих очевидно, что мышление — это некий сложный процесс, с помощью которого решаются житейские, научные или философские проблемы и рождаются гениальные идеи или роковые заблуждения. Язык же понимается многими просто как средство, с помощью которого результаты мышления можно передать современникам или оставить потомкам. Но, связав в своем сознании мышление с понятием „процесс“, а язык с понятием „средство“, мы по сути перестаем замечать тот непреложный факт, что в данном случае „средство“ не подчинено полностью „процессу“, а в зависимости от нашего целенаправленного или неосознанного выбора тех или словесных штампов оказывает сильнейшее влияние на ход и результат самого „процесса“. Причем известно немало случаев, когда такое „обратное влияние“ оказывается не только тормозом для правильного мышления, но порою даже его разрушителем.

С философской точки зрения задача, поставленная в рамках логического позитивизма, так и не была выполнена. В частности, в своих поздних исследованиях один из основоположников этого направления Людвиг Витгенштейн пришел к выводу, что естественный язык нельзя реформировать в соответствии с разработанной позитивистами программой. Даже язык математики в целом устоял перед мощным напором „логицизма“, хотя многие термины и структуры предлагаемого позитивистами языка вошли в некоторые разделы дискретной математики и существенно дополнили их. Популярность логического позитивизма как философского направления во второй половине XX столетия заметно упала — многие философы пришли к выводу, что отказ от многих „нелогичностей“ естественного языка, попытка втиснуть его в рамки основополагающих принципов логического позитивизма влечет за собой дегуманизацию процесса познания, а вместе с этим и дегуманизацию человеческой культуры в целом.

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

4. Неестественная логика в основаниях математики

В рассуждениях тех, кого можно отнести к законодателям или последователям формального языка математической логики, нередко обнаруживается своеобразная „слепота“ по отношению к элементарным логическим ошибкам. На эту слепоту в основополагающих работах Г. Кантора, Д. Гильберта, Б. Рассела, Дж. Пеано и др. еще в начале нашего столетия обратил внимание один из великих математиков Анри Пуанкаре [2].

Одним из примеров такого нелогичного подхода к рассуждениям является формулировка знаменитого парадокса Рассела, в котором необоснованно смешиваются два сугубо разнородных понятия „элемент“ и „множество“. Во многих современных работах по логике и математике, в которых заметно влияние программы Гильберта, не находят объяснения многие явно нелепые с точки зрения естественной логики утверждения. Соотношение между „элементом“ и „множеством“ является простейшим примером такого рода. Во многих работах этого направления утверждается, что некоторое множество (назовем его A) может быть элементом другого множества (назовем его B).

Например, в широко известном руководстве по математической логике [2] мы встретим такую фразу: „Множества сами могут быть элементами множеств, так, например, множество всех множеств целых чисел имеет своими элементами множества“. Заметим, что это утверждение не просто оговорка. Оно содержится в качестве „скрытой“ аксиомы в формальной теории множеств, которую многие специалисты считают основанием современной математики, а также в формальной системе, которую построил математик К. Гедель при доказательстве своей знаменитой теоремы о неполноте формальных систем [2]. Эта теорема относится к довольно узкому классу формальных систем (в их число входят формальная теория множеств и формальная арифметика), логическая структура которых явно не соответствует логической структуре естественных рассуждений и обоснований.

Однако уже более полувека она является предметом бурного обсуждения среди логиков и философов в контексте общей теории познания. При таком широком обобщении этой теоремы получается, что принципиально непознаваемыми являются многие элементарные понятия. Но при более трезвом подходе оказывается, что теорема Геделя показала лишь несостоятельность программы формального обоснования математики, предложенной Д. Гильбертом и подхваченной многими математиками, логиками и философами. Более широкий методологический аспект теоремы Геделя вряд ли можно считать приемлемым до тех пор, пока не получен ответ на следующий вопрос: является ли программа обоснования математики, предложенная Гильбертом, единственно возможной? Чтобы понять двусмысленность утверждения „множество A есть элемент множества B“, достаточно задать простой вопрос: „Из каких элементов в этом случае сформировано множество B?“. С точки зрения естественной логики возможны лишь два исключающих друг друга варианта объяснения. Объяснение первое. Элементами множества B являются имена некоторых множеств и, в частности, имя или обозначение множества A. Например, множество всех четных чисел содержится как элемент в множестве всех имен (или обозначений) множеств, выделенных по каким-либо признакам из множества всех целых чисел. Можно привести более понятный пример: множество всех жирафов содержится как элемент в множестве всех известных видов животных. В более широком контексте множество B можно также сформировать из концептуальных определений множеств или ссылок на множества. Объяснение второе. Элементами множества B являются элементы некоторых других множеств и, в частности, все элементы множества A. Например, каждое четное число есть элемент множества всех целых чисел или каждый жираф есть элемент множества всех животных. Но тогда получается, что в обоих случаях выражение „множество A является элементом множества B“ не имеет смысла. В первом случае оказывается, что элементом множества B является не само по себе множество A, а его имя (или обозначение, или ссылка на него). В этом случае неявно устанавливается отношение эквивалентности между множеством и его обозначением, что неприемлемо ни с точки зрения обычного здравого смысла, ни с точки зрения несовместимой с чрезмерным формализмом математической интуиции. Во втором случае оказывается, что множество A включено в множество B, т.е. является его подмножеством, но не элементом. Здесь тоже явная подмена понятий, поскольку отношение включения множеств и отношение принадлежности (быть элементом множества) в математике имеют принципиально различный смысл. Знаменитый парадокс Рассела, подорвавший доверие логиков к понятию „множество“, основан на этой нелепости — в основе парадокса лежит двусмысленная предпосылка о том, что множество может быть элементом другого множества.

Возможен еще один вариант объяснения. Пусть множество A задано простым перечислением его элементов, например, A = {a, b}. Множество B в свою очередь задано перечислением некоторых множеств, например, B = {{a, b}, {a, c}}. В данном случае кажется очевидным, что элементом B является не имя множества A, а само множество A. Но даже в этом случае элементы множества A не являются элементами множества B, и множество A здесь рассматривается как неразделимая совокупность, которая вполне может быть заменена его именем. Но если бы мы считали элементами B все элементы содержащихся в нем множеств, то в этом случае множество B было бы равно множеству {a, b, c}, и множество A в этом случае было бы не элементом B, а его подмножеством. Таким образом, получается, что этот вариант объяснения в зависимости от нашего выбора, сводится к ранее перечисленным вариантам. А если никакого варианта выбора не предложено, то получается элементарная двусмысленность, которая часто приводит к „необъяснимым“ парадоксам.

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

Например, в современных математических рассуждениях часто используется понятие „самоприменимость“, которое лежит в основе парадокса Рассела. В формулировке этого парадокса под самоприменимостью подразумевается существование множеств, которые являются элементами самих себя. Такое утверждение сразу же приводит к парадоксу. Если мы рассмотрим множество всех „несамоприменимых“ множеств, то окажется, что оно является одновременно „самоприменимым“ и „несамоприменимым.

Заключение

Математическая логика немало способствовала бурному развитию информационных технологий в XX веке, но из ее поля зрения выпало понятие “суждение», которое появилось в логике еще во времена Аристотеля и на котором, как на фундаменте, держится логическая основа естественного языка. Такое упущение отнюдь не способствовало развитию логической культуры общества и у многих даже породило иллюзию, что компьютеры способны мыслить не хуже самого человека. Многих даже не смущает то обстоятельство, что на фоне всеобщей компьютеризации в преддверии третьего тысячелетия логические нелепости в пределах самой науки (я уж не говорю о политике, законотворческой деятельности и о псевдонауке) встречаются даже чаще, чем в конце XIX века. И для того, чтобы понять суть этих нелепостей, нет необходимости обращаться к сложным математическим структурам с многоместными отношениями и рекурсивными функциями, которые применяются в математической логике. Оказывается, для понимания и анализа этих нелепостей вполне достаточно применить намного более простую математическую структуру суждения, которая не только не противоречит математическим основам современной логики, но в чем-то дополняет и расширяет их.

1. Васильев Н. А. Воображаемая логика. Избранные труды. — М.: Наука. 1989; — стр. 94-123.

2. Кулик Б.А. Основные принципы философии здравого смысла (познавательный аспект) // Новости искусственного интеллекта, 1996, No 3, с. 7-92.

3. Кулик Б.А. Логические основы здравого смысла / Под редакцией Д.А. Поспелова. — СПб, Политехника, 1997. 131 с.

4. Кулик Б.А. Логика здравого смысла. — Здравый смысл, 1997, No 1(5), с. 44 — 48.

5. Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967.

6. Соловьев А. Дискретная математика без формул. 2001//http://soloviev.nevod.ru/2001/dm/index.html

www.ronl.ru

Реферат - Элементы математической логики

Потопахин Виталий Валерьевич, методист ХКЦТТ

Искусство логического мышления

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

Любая наука, начинается с точного определения понятий с которыми она имеет дело.

Определим основные понятия и мы:

Посылка — это утверждение, из которого мы исходим в своих рассуждениях.

Следствие — это утверждение являющееся результатом наших рассуждений.

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

Гипотеза — это утверждение, истинность которого требуется доказать.

Противоречие — это ситуация, когда в процессе наших рассуждений получились два взаимоисключающих утверждения.

Суждение — это единица мышления.

Основные законы:

Закон тождества. Всякий предмет, есть то, что он есть. Что это означает: Если мы, в своих рассуждениях, используем какое — либо понятие, то на любом этапе рассуждений, это понятие должно означать одно и тоже. Иногда за соблюдением закона тождества надо специально следить. Например, при использовании многозначных слов. Нарушение закона может завести в тупик. К примеру, понятием энергии часто обозначаются совершенно разные явления. Например, физическая энергия и психическая энергия. Если мы опустим, тот факт, что это два разных явления, то законы, которым подчиняется физическая энергия, можно будет автоматически переносить на явления связанные с проявлением психической энергии, что и будет ошибкой. Приведём более простой пример: Предположим, вы изучили правила дорожного движения принятые в России. Закон тождества говорит, что правила принятые в России, это совсем не те правила, которые приняты во Франции. Если же вы пренебрежёте законом тождества, то будучи во Франции вы рискуете попасть в аварию.

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

Закон исключенного третьего. Если есть два суждения и одно исключает другое, то одно из них истина, а другое ложь. В реальной жизни это не всегда так. Приведём пример: Первое утверждение «Я пользуюсь методами математической логики каждый день моей жизни.», второе утверждение «Я никогда не пользуюсь методами математической логики». Очевидно, что они противоречат друг другу, однако они вполне могут оказаться одновременно ложными. Например, если вы специалист по математической логике, то вы должны часто пользоваться её методами, но вряд ли они нужны вам каждый день вашей жизни. Закон исключенного третьего предназначен для использовании в области точных наук, в которых такие ситуации не встречаются или встречаются достаточно редко.

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

Методы мышления

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

Дедукция: Это метод рассуждений, при котором некоторые истинные утверждения берутся в качестве посылок. Затем с помощью умозаключений из этих посылок получаются выводы, которые в свою очередь становятся посылками для следующих умозаключений. Получается цепочка умозаключений, в начале которой находится некоторое количество очевидных утверждений, а в конце утверждения, истинность которых уже далеко не очевидна, если не знать всей цепочки.

Очень яркий литературный пример использования дедуктивного метода это герой А. Конан-Дойля Шерлок Холмс. Конечно, применение дедукции Холмсом далеко от математической точности и строгой критики рассказы о нём не выдерживают, но суть метода в рассказах Конан-Дойля демонстрируется очень наглядно.

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

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

1 Комната 2 Комната
В этой комнате находится принцесса, а в другой комнате сидит тигр. В одной из этих комнат находится принцесса; кроме того, в одной из этих комнат сидит тигр.

Кроме того, принцу было сказано, что на одной табличке написана правда, а на другой нет.

Начнем рассуждения. Для каждой из табличек возможны только два варианта, либо ложь, либо истина. Рассмотрим с этой позиции табличку на первой комнате.

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

Табличка на первой двери ложна. Тогда табличка на второй двери истинна. Из ложности первой таблички следует, что принцесса находится в комнате 2, а тигр в комнате 1. Из истинности второй табличке следует, что в одной из комнат есть принцесса и в одной из комнат есть тигр. Эти утверждения не противоречат друг другу, следовательно вторая ситуация непротиворечива и чего в свою очередь следует что принцесса находится во второй комнате.

Задача для самостоятельного решения:

1 Комната 2 Комната
По крайней мере в одной из комнат находится принцесса Принцесса в другой комнате.

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

Математическая логика

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

Как создать такую теорию?

Ответ: точно так же, как и любую другую математическую теорию. Надо предельно точно описать используемые понятия и определить над ними операции. Первым кто проделал такую работу и создал первую математическую логику был Джорж Булль. Эта математика по его имени стала называться булевой алгеброй или логикой высказываний. И сейчас мы ей займемся. Итак.

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

Последняя договорённость очень важна. Если рассматривать смысл высказываний, то работать с ними будет слишком сложно, так как смысл очень неопределённое понятие. А если мы решим, что важна только истинность высказывания, то проблема значительно упрощается. В этом случае совершенно неважно о чём говорится в высказывании. Отпадает необходимость обозначать высказывание целым предложением, раскрывающим его смысл. Для обозначения вполне достаточно будет одной буквы. Разные высказывания будем обозначать разными буквами. Окончательно объектами нашей математики будут переменные величины обозначаемые буквами или комбинациями букв и имеющие только два значения: Истина и Ложь.

Операции: Операции над высказываниями, это операции над буквенными переменными и могущие принимать в качестве результата только два значения. Далее мы будем называть такие операции логическими.

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

Как можно составить логическую операцию? Очень просто. Приведем пример. Пусть дано высказывание А. Оно может быть либо истинно, либо ложно. Определим высказывание В следующим образом: пусть В истинно когда А ложно и ложно когда А истинно. Мы только что установили соответствие между высказыванием А и высказыванием В. Другими словами мы составили логическую операцию, аргументом которой является высказывание А и результатом высказывание В. Операция определённая таким образом называется отрицанием и записывается так — ùА. Еще говорят так — “не А”

Определим еще четыре логические операции:

Коньюкция. Это логическая операция устанавливающая соответствие между высказываниями А и В и высказыванием С следующим образом: Если А и В истинны то С также истинно. Если же хотя бы одно из них ложно то С также ложно. Обозначение: АÙВ. Можно сказать так “ А и В “ и еще эту операцию называют логическим умножением.

Дизьюкция. Это логическая операция устанавливающая соответствие между высказываниями А и В и высказыванием С следующим образом: Если А и В ложны то С также ложно. Если же хотя бы одно из высказываний А и В истинно то С также истинно. Обозначение: АÚВ. Можно сказать так “ А или В ” и еще эту операцию называют логическим умножением.

Эквиваленция. Это логическая операция устанавливающая соответствие между высказываниями А и В и высказыванием С следующим образом: Если А и В одновременно ложны или же истинны то С истинно иначе С ложно. Обозначение: А=В

Импликация. Это логическая операция устанавливающая соответствие между высказываниями А и В и высказыванием С следующим образом: Пусть А посылка и В следствие, тогда:

если А ложно то С истинно ( то есть из ложного утверждения может следовать все что угодно)

если А истинно и В истинно то С истинно ( из истинного утверждения можно вывести истинное )

если А истинно и В ложно то С ложно ( из истинного утверждения не может следовать ложное )

Обозначение: А®В

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

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

А В не А А или В А и В А следует В А эквив. В
Истина Истина ложь истина Истина Истина истина
Истина Ложь ложь истина ложь Ложь ложь
Ложь Истина истина истина ложь Истина ложь
Ложь Ложь истина ложь ложь Истина истина

Сложное высказывание

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

А В АÚВ (АÚВ)®А
1 1 1 1
1 1 1
1 1
1

Составьте для тренировки таблицы истинности следующих сложных высказываний:

АÚ(АÚùВ) А®(ВÙА)
(ВÚА)®А А®(ВÚВ)
ù(АÚù(В®А)) (ùВÚА)®(ВÚА)
ù(В®А)®(АÙВ) В®(ù(В®А)®(ùА®В))

Схема умозаключения

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

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

Для начала определим два важных понятия:

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

Схема умозаключения. Схема умозаключения, это способ получения тождественно-истинных высказываний. Схема утверждает что если высказывание А истинно и истинна импликация А®В, то высказывания В также является истинным (это ясно из определения импликации). Таким образом, если мы найдём способ проверить истинность посылки и импликации, истинность следствия получается автоматически.

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

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

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

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

Заключение

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

Еще несколько вопросов для самостоятельной работы.

Приведите пример дедуктивного рассуждения.

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

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

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

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

www.ronl.ru

Смотрите также