Слайд 2
Психология изучает мышление как один из психи-ческих процессов наряду
с эмоциями, волей и т. д. Она уделяет значительное внимание
изучению как механизмов возникновения того или иного опре-деленного типа мышления, так и непосредствен-ное проявление этих типов мышления на практике. Однако психологию не интересует истинность этих типов мышления, наоборот, ее предметом высту-пает исследование отклоняющихся от нормы типов мышления.
Физиология раскрывает механизмы, которые обусловливают процесс мышления. При этом ее мало интересует отражение действительности, возникающее в процессе мышления.
Слайд 3
Логика – закономерности в связях и развитии мыс-ли. В
данном случае в качестве примеров можно привести такие выражения,
как «женская логика», «железная логика», «логика рассуждения».
Необходимо отметить отличие предмета логики от предмета других наук о мышлении.
Логика – наука о структуре и закономерностях правильного мышления.
Философия исследует мышление в целом. Она ре-шает вопрос об отношении человека, а, следова-тельно, его мышления к окружающему миру. При этом философию мало интересуют те механизмы, на основе которых формируется человеческое мышление.
Слайд 4
Своеобразие логики заключается в том, что она изучает
мышление, его содержание, формы, зако-ны, истинность. Поэтому более точным
определе-нием логики как науки будет следующее высказы-вание: логика это наука о законах и формах пра-вильного рассуждения, на основе которых полу-чаем правильные выводы, наука о методах познания.
Логика занимается формальными рассуждениями безотносительно к их содержанию. Отличают правильные (истинные) и неправильные (ложные) утверждения.
Слайд 5
Софизм (от греч. σόφισμα, «мастерство, умение, хитрая выдумка,
уловка, мудрость») — ложное высказывание, которое, тем не менее, при
поверх-ностном рассмотрении кажется правильным. Софизм основан на преднамеренном, сознатель-ном нарушении правил логики. Это отличает его от паралогизма и апории. Логические ошибки, допус-каемы в доказательстве, как и в рассуждениях во-обще непреднамеренно, называются паралогиз-мы (от греч. paralogismos-неправильное рассужде-ние). АПОРИЯ (от греч. aporia — затруднение, не-доумение) — трудноразрешимая проблема, свя-занная с противоречием между данными опыта и их мысленным анализом.
Слайд 6
Софизм Эватла
У древнегреческого софиста Протагора учился со-фистике и
в том числе судебному красноречию не-кий Эватл. По заключенному
между ними договору Эватл должен был заплатить за обучение 10 тысяч драхм только в том случае, если выиграет свой первый судебный процесс. В случае проигрыша первого судебного дела он вообще не был обязан платить.
Однако, закончив обучение, Эватл не стал участво-вать в судебных тяжбах. Как следствие, он считал себя свободным от уплаты за учебу. Это длилось довольно долго, терпение Протагора иссякло, и он сам подал на своего ученика в суд.
Слайд 7
Таким образом, должен был состояться первый судебный процесс
Эватла.
Протагор привёл следующую аргументацию: «Каким бы ни было решение
суда, Эватл должен будет заплатить. Он либо выиграет свой первый процесс, либо проиграет. Если выиграет, то запла-тит по договору, если проиграет, заплатит по реше-нию суда».
Эватл возражал: «Ни в том, ни в другом случае я не должен платить. Если я выиграю, то я не должен платить по решению суда, если проиграю, то по договору».
Слайд 8
Апории Зенона и проблема движения
Ахилл и черепаха. Ахилл
—выдающийся спортс-мен. Черепаха, как известно, одно из самых мед-лительных
животных. Тем не менее Зенон утверж-дал, что Ахилл проиграет черепахе состязание в беге. Примем следующие условия. Пусть Ахилла отделяет от финиша расстояние 1, а черепаху — ½. Двигаться Ахилл и черепаха начинают одновре-менно. Пусть для определенности Ахилл бежит в 2 раза быстрее черепахи. Тогда, пробежав рассто-яние ½, Ахилл обнаружит, что черепаха успела за то же время преодолеть отрезок ¼ и по-прежнему находится впереди героя.
Слайд 9
Далее картина повторяется: пробежав четвертую часть пути, Ахилл
увидит черепаху на одной вось-мой части пути впереди себя
и т. д. Следовательно, всякий раз, когда Ахилл преодолевает отделяющее его от черепахи расстояние, последняя успевает уползти от него и по-прежнему остается впереди. Таким образом, Ахилл никогда не догонит черепа-ху. Начав движение, Ахилл никогда не сможет его завершить. Принципиальная незавершаемость данной последовательности заключается в том, что в ней отсутствует последний элемент. Всякий раз, указав очередной член последова-тельности, мы можем указать и следующий за ним.
Слайд 10
Дихотомия. Для того, чтобы пройти весь путь, дви-жущееся
тело сначала должно пройти половину пути, но чтобы преодолеть
эту половину, надо пройти половину половины и т. д. до бесконеч-ности. Иными словами, при тех же условиях, что и в предыдущем случае, мы будем иметь дело с перевернутым рядом точек: (½)n, ..., (½)3, (½)2, (½)1. Если в случае апории Ахилл и черепаха соответ-ствующий ряд не имел последней точки, то в Дихо-томии этот ряд не имеет первой точки. Следова-тельно, заключает Зенон, движение не может на-чаться. А поскольку движение не только не может закончиться, но и не может начаться, движения нет.
Слайд 11
Существует легенда, о которой вспоминает А. С. Пушкин в стихотворении
«Движение»:
Движенья нет, сказал мудрец брадатый.
Другой смолчал и стал пред
ним ходить.
Сильнее бы не мог он возразить;
Хвалили все ответ замысловатый.
Но, господа, забавный случай сей
Другой пример на память мне приводит:
Ведь каждый день пред нами солнце ходит,
Однако ж прав упрямый Галилей.
Представим себе, что по дороге в одном направле-нии движутся быстроногий Ахилл и две черепахи, из которых Черепаха-1 несколько ближе к Ахиллу, чем Черепаха-2.
Слайд 12
Можно показать, что Ахилл не сможет перегнать Черепаху-1.
За то время, как Ахилл пробежит разделя-ющее их вначале
расстояние, Черепаха-1 успеет уползти несколько вперед и такое положение будет бесконечно повторяться. Ахилл будет все ближе и ближе к Черепахе-1, но никогда не сможет ее пере-гнать. Такой вывод, конечно же, противоречит нашему опыту, но логического противоречия у нас пока нет.
Пусть, однако, Ахилл примется догонять более дальнюю Черепаху-2, не обращая никакого внимания на ближнюю. Можно утверждать, что Ахилл сумеет вплотную приблизиться к Черепахе-2, но это означает, что он перегонит Черепаху-1. Теперь мы приходим уже к логическому противоречию.
Слайд 13
Проанализировав более тщательно две приведен-ные апории, мы обнаружим,
что обе они опира-ются на допущение о непрерывности простран-ства
и времени в смысле их бесконечной делимос-ти. Такое допущение непрерывности отличается от современного, но имело место в древности. Без допущения тезиса о том, что любой пространст-венный или временной интервал можно разделить на меньшие по длине интервалы, обе апории рушатся.
Слайд 14
Различают: формальную логику классическая логика), индуктивную логику, символическую
логику, (Дж. Буль предложил логику рассуждений безотносительно к содержанию
определить фор-мальным символическим языком формальной логики, утверждениям присваиваются абстракт-ные значения True (истина) или False (ложь), прагматистскую логику. В конце XIX – начале XX в.в., возникла логическая теория, получившая наз-вание математической логики. Со временем это направление получило название классической ло-гики. Разнообразные неклассические направле-ния, возникшие позднее, объединяются в такое понятие, как неклассическая логика.
Слайд 15
Классическая логика основывается на принципе, согласно которому каждое
высказывание является либо истинным, либо ложным. Это так называ-емый
принцип двузначности. Логику, основанную на этом принципе, называют двузначной. Ей про-тивопоставляют многозначные системы. В пос-ледних наряду с истинными и ложными утвержде-ниями допускаются также разного рода неопреде-ленные суждения, учет которых не только услож-няет, но и меняет всю картину. В 1920 г. Я. Лукасе-вичем была предложена трехзначная логика, основанная на предположении, что высказывания бывают истинными, ложными и возможными, или неопределенными.
Слайд 16
Логика входит в состав фундаментальных математ-ических дисциплин современной
информатики, объединяемых в дискретной математике.
Логика связана с алгоритмизацией и
автомати-ческим решением задач. Важнейшим достижени-ем логики в приложениях конца ХХ века является разработка основ логического программирования.
Можно выделить четыре функции, которые выпол-няет логика в обществе.
Познавательная функция. Логика позволяет оп-ределить верный путь для достижения истинных знаний, а также выявить последствия, к которым приводит неправильный ход рассуждения.
Слайд 17
Мировоззренческая функция. Логика влияет на формирование человеческого мышления,
которое, в свою очередь, определяет жизненную позицию человека.
Методологическая функция.
Следует отметить, что законы логики играют важную роль в разра-ботке методологий различных наук. В то же время логическая теория также является методом позна-ния.
Идеологическая функция. Логика часто использу-ется в идеологических целях в силу своих внутрен-них антагонизмов и противоречий (например, между материализмом и идеализмом, диалекти-кой и метафизикой).
Слайд 18
Современные приложения логики - проектирование циф-ровых схем, программирование
экспертных систем, уп-равление базами данных, логическое управление.
Различают два
основных раздела математической логики: логика высказываний и логика предикатов.
В логике высказываний рассуждения из вербальной фор-мы преобразуются в символическую форму и определяю-тся основные законы правильных рассуждений. Законы позволяют абстрагироваться от смысла конкретных выска-зываний, выполнить анализ и алгебраические преобразо-вания высказываний в символической форме.
В логике предикатов рассматриваются законы построе-ния утверждений в обобщенной форме с переменными, определяемыми в классах с конкретным информацион-ным смыслом. Язык логики предикатов играет важную роль в искусственном получении знаний.
Слайд 19
Логика высказываний
Раздел логики, в котором изучаются истинностные взаимосвязи
между высказываниями. Высказывания (пропозиции, простые предложе-ния) рассматриваются только с
точки зрения их истинности или ложности, безотносительно к их содержанию.
Формулы высказываний
Простые высказывания – истинные либо ложные по смыслу простые предложения. Примерами простых высказываний являются:
1) свойства объектов,
5-число, Петров высокий, фрукт красный.
Слайд 20
Даже, если мы никогда не видели Петрова и
ябло-ка, мы верим, что это истина и верим в
то, что фрукт красный.
2) отношения между объектами, Олег брат Сергея, 5 больше 7, прямая на плоскости.
3) Двузначные события в технике, в природе, в жизни – контакт F замкнут, двигатель включен, дождь идет, Иванов болен, ...
А почему замкнут – истина, а разомкнут – ложь? На практике нам может быть важнее считать, что истинным является инверсный смысл – разомк-нутый контакт.
Слайд 21
Смысл высказываний для практических приложе-ний может иметь важное
значение, но для фор-мальной логики основная цель состоит в
формаль-ной записи рассуждений и обосновании правиль-ных рассуждений при любых значениях истинно-сти.
Рассуждение “Если (3>5) и (5>7), то (3>7)“ фор-мально правильное и при ложных посылках 3>5, 5>7 и 3>7, если считаем их истинными.
Также можно строить неправильные рассуждения при истинных посылках. Таким образом, различа-ем правильность и истинность рассуждений. В ло-гике высказываний исследуется формальная ис-тинность рассуждений.
Слайд 22
Символическая запись на языке логики позволяет избежать двусмысленности,
свойственной рассуждениям в естественном языке.
Синтаксис языка логики –
формальная запись структуры рассуждений. Семантика языка логики – правильные (истинные – T безотносительно к информационному по-лю) или неправильные (ложные –F безотносительно к ин-формационному полю) утверждения и рассуждения.
Простые высказывания обозначаются буквами – А, B, C, ... и называются атомами. Значения простых высказываний и соответствующих символов {T, F} не связаны с каким-либо смыслом.
Составные высказывания истинные или ложные состоят из простых высказываний, которые разделяются синтак-сически.
Слайд 23
Составные высказывания определяются формулами, сос-тоящими из атомов и
символов, обозначающих связки безотносительно к их содержанию и конкретному
смыслу. Элементарные формулы из одного или двух атомов (прос-тых высказываний) обозначают связки и однозначно оп-ределяются таблицами истинности.
Конъюнкция (И, &)
“Составное высказывание A&B истинное тогда, когда А истинно И В истинно”.
Если класс объектов Q определяется двумя свойствами – высказываниями А и В, или двумя битами информации, то его можно определить высказыванием-конъюнкцией Q=A & B. По отношению к этому классу все множество объектов Q называют универсальным множеством.
Слайд 24
Пример класса.
“четное И положительное число” = “Некоторое число
четное (A) И положительное число”(В).
Пример отношений.
“Сидоров И Петров в
школе”.
В естественном языке связка И может явно отсутствовать, вместо нее может использоваться противопоставление (число четное, но отрицательное), знаки препинания – запятые, точки, несколько подлежащих и прилагательных.
Пример.
Служащие мужского пола с непрерывным стажем работы не меньше пяти лет, получающие пенсионную прибавку.
Рассматривается универсальный класс Служащих.
Слайд 25
Служащие – мужчины (m). Служащие, имеющие стаж работы
не менее 5 лет (f), Служащие получают пенсионную прибавку
(d).
Другая запись этого утверждения через запятые (точки), что эквивалентно связке И.
Формула для этого утверждения – m&f&d определяет класс служащих со свойствами m, d и отношением f.
2) Дизъюнкция (ИЛИ, ) - соединительное ИЛИ.
“Составное высказывание (А В) истинное, когда А ИЛИ В истинны”.
Пример.
“В преступлении могли участвовать A, B, C” – формула рассуждения A&B&C скорее всего неправильная и выби-раем A B C, так как некоторые из {A, B, C} могли не участвовать в преступлении.
Слайд 26
3) отрицание (НЕ, )
Если выказывание “А истинно
“=A,
то “НЕ A - ложно” = А.
Забастовка
продолжается (A) и забастовка не продолжается (А).
4) Эквивалентность (~)
“Высказывание А ~ B истинно тогда, когда А И В истинны ИЛИ А И В ложны”. Предложение можно записать следующим равенством
(A ~ B) = (A&B) (А& B).
Пример.
“Сидоров ходит в школу ТАКЖЕ, КАК Петров” =”Сидоров И Петров в школе ИЛИ Сидорова НЕТ в школе И Петрова НЕТ в школе”.
Слайд 27
5) Исключающее ИЛИ (ЛИБО, ЛИБО, ) – разделительное
ИЛИ.
Связка ЛИБО (ИЛИ /НО НЕИ)
“А либо В истинно (АВ)
тогда и только тогда, когда А ИЛИ В истинны, но А И В ложны” = (AB) ((A B)& (A&B)). Здесь используем тождество.
“Петров ЛИБО Семенов в школе”= “ЛИБО Петров в школе, ЛИБО Семенов в школе” = “Петров ИЛИ Семенов в школе, НО НЕ вместе”.
6) Импликация ()
ЕСЛИ А истинно, ТО B истинно. Здесь А – посылка, а В – следствие.
Пример.
“ЕСЛИ Петров в школе, ТО Сидоров тоже в школе” = ”А нет в школе ИЛИ В в школе”.
Слайд 28
Сходство импликации с другими связками указывает на то,
что при переходе к символической записи утвержде-ний необходимо проверять
по таблице истинности все условия. Неправильный выбор связки приводит к ошибоч-ным рассуждениям.
В математике утверждение "если p, то q" читается как
" p достаточно для q" = "q необходимо для p".
Если выполняется необходимость и достаточность p для q, то утверждения p и q эквивалентны, что можно записать в следующей символической форме
((p q)&(q p)) = (p~q).
Парадоксы импликации — это парадоксы, возникающие в связи с содержанием условных утверждений класси-ческой логики. Главная функция этих утверждений — обоснование одних утверждений ссылкой на другие.
Слайд 29
В классической логике условное утверждение имеет форму «Если
А, то В». Оно ложно только в том случае,
если А истинно, а В ложно, и истинно во всех остальных случаях. Содержание утверждений А и В при этом во внимание не принимается. Если даже они никак не связаны друг с другом по смыслу, составленное из них условное утверждение может быть истинным.
Так истолкованное условное утверждение носит название «материальной импликации». Оно обладает следующими особенностями:
Если B истинно, то истинность всего условного утвержде-ния уже не зависит от истинности A. То есть, истинное утверждение может быть обосновано с помощью любого утверждения. Пример: утверждение «Если дважды два равно пяти, то снег бел» является истинным.
Слайд 30
Если A ложно, то истинность всего условного утверждения
уже не зависит от истинности B. То есть, с
помощью ложного утверждения можно обосновать все, что угодно. Пример: утверждение «Если дважды два равно пяти, то снег красный» является истинным.
Если А является противоречивым утверждением, то истинность всего условного утверждения уже не зависит от истинности В. То есть, из противоречивого утверждения можно вывести все, что угодно. Пример: утверждение «Если дважды два равно четырем и дважды два не равно четырем, то Луна сделана из зеленого сыра» является истинным.
Если В является тавтологией, то истинность всего условно-го утверждения уже не зависит от истинности А. То есть логические законы следуют из любых утверждений.
Слайд 31
Пример: утверждение «Если снег бел, то дважды два
равно четырем или дважды два не равно четырем» является
истинным.
Эта особенность материальной импликации является пря-мым следствием двух основных допущений классической логики:
1) всякое утверждение либо истинно, либо ложно, а треть-его не дано:
2) истинностное значение сложного утверждения зависит только от истинностных значений входящих в него прос-тых утверждений, а также от характера связи между ними, и не зависит от их содержания.
В рамках этих двух допущений более удачное построение условных утверждений невозможно. Подобное положе-ние дел, отстаиваемое классической логикой, получило название «парадоксов материальной импликации».
Слайд 32
С целью решения этих парадоксов была предложена «строгая
импликация», которая как-то отражала связь простых утверждений, составляющих условное
утвержде-ние, по смыслу. Правда, потом оказалось, что строгая импликация сама не свободна от парадоксов. Поэтому был предложен другой вариант условной связи — «реле-вантная импликация», которая разрешает не только пара-доксы материальной импликации, но и парадоксы стро-гой импликации. Этой импликацией можно связывать только такие утверждения, которые имеют общее содер-жание.
Импликация на примере дедукции
Что собой представляет эта импликация, можно посмот-реть на примере дедукции — метода умозаключений, в котором применяются условные утверждения.
Слайд 33
Классическим примером дедукции является следующее:
все люди — смертны,
все греки —
люди,
следовательно, все греки — смертны.
Условная связь этих утверждений станет очевидна,
если мы представим их в следующем виде:
если все люди смертны
и если все греки — люди,
то все греки смертны.
В классической логике это умозаключение имеет следу-ющую форму: если первое, то второе; имеет место пер-вое, значит, есть и второе. Такая форма дедукции является правильной. Неправильной дедукцией будет такая форма: если первое, то второе; имеет место второе; значит, есть и первое. Если вложить в эту форму прежнее содержание, то получится следующее:
Слайд 34
все люди - смертны
все греки - люди
следовательно, все
люди - греки.
Ясно, что это умозаключение является неправильным.
Слайд 35
В качестве классификационного признака берется смерт-ность объектов. Первая
посылка приписывает этот приз-нак наиболее общему классу данной классификации,
то есть классу людей. Само собой, что следующие, более частные классы данной классификации также будут обла-дать этим признаком. Поэтому когда вторая посылка уста-навливает принадлежность греков к данной классифика-ции, то тем самым она наделяет их и признаком смерт-ности. Заключительный вывод только констатирует это, не внося в рассуждения ничего нового.
В свою очередь, в неправильной форме данной дедукции вторая посылка ставит более частный класс на один уровень с исходным классом, из-за чего и происходит обобщение частного признака на этот (исходный) класс.
Слайд 36
Определение. Формула правильно построена (Well formed formula –
Wff), если содержит только перечислен-ные связки, причем бинарные связки
правильно попарно соединяют атомы и формулы. В дальнейшем предполага-ются по умолчанию только Wff- формулы.
Формальная запись рассуждения в Wff позволяет устра-нить неопределенности, свойственные естественному языку. При этом сохраняется независимость и различи-мость простых утверждений в составном высказывании, благодаря применению различных обозначений.
Следствием этого являются:
1) Возможность применения формул для исследования правильности рассуждений и преобразований рассуждений независимо от содержательного смысла.
Слайд 37
При возвращении к содержательной форме сохраняется истинный смысл
исходного утверждения.
2) Возможность соединения в одном рассуждении высказ-ываний
из различных классов – событий, свойств и отно-шений.
Примеры.
Если яблоко зеленое (A), то оно кислое (B) = AB =
= А В = “яблоко не зеленое (А) или кислое (В)”.
Здесь A, B разные свойства для одного класса и пример преобразования формулы, сохраняющей истинностный смысл рассуждения.
2. “Если влажность высокая (А), то после полудня (В) или (либо) вечером (С) будет дождь (В C) “.
Высказывания А, В, С – события из разных классов,
А (В С).
Слайд 38
3. “Лечение не будет найдено (А), пока не
определены причины болезни (В) и не найдены новые лекарства
(С)”.
Высказывания А, В, С – события из разных классов,
В& С А.
4. “Требуется (необходимы !) храбрость (А) и мастер-ство (В), чтобы подняться на эту гору (С)”.
А, В – свойства, С – событие, СА&В.
5. “Для того, чтобы число было нечетным (А), необходимо , чтобы число было простым (В) и не делилось на два (С)”.
А, В, С – свойства чисел, AВ&С.
6. “Если (2<5) (A) и (5>10) (B), то (2≠10) (C)”.
A, B, C – отношения в классе чисел. A& BC.
Слайд 39
Интерпретация логических формул
Определение. Пусть задана формула Ф(A, B),
где A, B – атомы. Подстановка конкретных высказываний (или
просто их значений F или T) и вычисление истинности составного высказывания называется интерпретацией.
Формулы разделяют на:
1) выполнимые – существует интерпретация, при которой формула истинна:
а) если формула Φ истинна в интерпретации I, то Ф(I) выполнима в I, а I называется моделью Ф;
б) если формула Ф ложна в I, то Ф(I) опровергается в I.
2) тавтологии (общезначимые) – формулы, истинные на всех наборах атомов;
3) противоречия – ложные формулы на всех наборах атомов.
Слайд 40
Заменяя содержательные рассуждения формулами, полу-чаем возможность проверить истинность
утверждений в общем случае, когда смысл утверждений не очевиден
и зависит от истинности простых высказываний.
При классификации формул решаются следующие задачи:
1) Проблема автоматической (алгоритмической) проверки формулы на выполнимость (Satisfability Automation Testing – SAT). Если формула не выполнима, то является противоречием.
2) Проблема разрешимости в логике – проверить, является ли формула тавтологией (общезначимой).
Обе задачи связаны с интерпретацией значения формулы. Формулу Ф(A, B) называют логической функцией, если использовать логическую переменную F = Ф(A, B) как значение формулы для всевозможных интерпретаций.
Слайд 41
Пример.
Требуется проверить правильность рассуждения – общезначимость формулы.
“Если
я пойду завтра на первое занятие (a), то должен
буду встать рано (b), а если я пойду вечером на танцы (c), то лягу спать поздно (d). Если я лягу поздно (d), а встану рано (b), то я должен буду довольствоваться пятью часами сна (е). Но я не в состоянии обойтись пятью часами сна (е). Следовательно, я должен или пропустить первое занятие ( а), или не ходить на танцы ( с)”
Слайд 42
противоречие, следова-тельно, заключение есть логическое следствие име-ющихся
посылок.
Пример.
Требуется определить набор значений простых высказы-ваний, при котором
рассуждение ложно и уточнить рассуждение, приводя его к тавтологии.
Проверим истинность следующего рассуждения.
Слайд 43
Студент пойдет домой (a) или останется в институте
(b),
(a b).
Студент решил остаться в институте
(b), следовательно, он не пойдет домой, ( a).
Формула составного высказывания ((a b)&b) a.
Сокращенным способом выбираем значения атомов, опровергающих это утверждение:
a = F при ((a b)&b) = T. При b = Т выражение истинно.
Таким образом, исходная формула может быть ложной и рассуждение не верно.
Действительно, “ошибка” в выборе связки ИЛИ. Должна быть связка ИСКЛЮЧАЮЩЕЕ ИЛИ (a либо b), что можно было уточнить при записи формулы для первого высказывания. ((ab)&b) a.
Слайд 44
Инверсное составное высказывание Ф является про-тиворечием –
на всех интерпретациях ложно, если Ф – тавтология.
Если требуется
доказать общезначимость формулы, то для инверсной формулы (обратный метод) проверяется вы-полнимость (применение обратного метода решения с использованием SAT-алгоритмов).
Для логической формулы F=(S&(A ( B))) может быть построено следующее дерево синтаксического разбора
Слайд 45
Вычисление истинности при интерпретации выполняется в обратном порядке
и представлено графом вычислений
Если в формуле N атомов, то
таблица истинности содер-жит 2N условий (наборов значений) истинности атомов. Таким образом, в общем случае, когда формула противоречива, для решения SAT-проблемы и проверки общезначимости требуется перебор из 2N интерпретаций.
Слайд 46
Принцип подстановки
Утверждение 1. Если формула Ф(A) – тавтология
и форму-ла Ф(B)=Ф(А/B) получена из Ф(A) при подстановке фор-мулы
B вместо любого вхождения символа A в Ф(A) (обо-значим A/B), то формула Ф(B)= Ф(A/B) - тоже тавтология.
Следствие. Если Ф(А) тавтология, то Ф(А/ A) = Ф( А) тавтология.
Пример.
Доказать, что формула Ф(A, B) = А (В А) тавтология.
Сделаем подстановку Ф(А, В) = Ф(А/ А, В/ В ) =
=А ( В А ) = А В А , полученная формула тавтология.
Определение. Две формулы А(x1, ..., xn) и В(x1, …, xn), где x1, …, xn – атомы, называются равносильными (тождест-венно равными), если при любых интерпретациях значе-ния истинности совпадают.
Слайд 47
В этом случае записывается тождество
А(x1, …, xn)
В(x1, …, xn).
Лемма. Формулы А(x1, …, xn) и В(x1,
…, xn) тождественно равны (А=В), если А~В – тавтология.
Например, закон контрапозиции (p q)~( q p) может быть записан в виде тождества (p q) ≡ ( q p).
Следствие. Тождество сохраняется при произвольных перестановках аргументов.
Например, закон контрапозиции (p q) ≡ ( q p) сохраняется при подстановках (q/p, p/q).
Утверждение 2. (Принцип подстановки).
Пусть Ф(A) – формула, в которой выделена формула А и в результате замены формулы А на формулу В(A/B) получим формулу Ф(B), тогда: Ф(A) = Ф(B), если А = В.
Слайд 48
Алгебра логики высказываний
Утверждения в виде тождеств относятся к
законам логики. Применение тождественных подстановок относятся к алгебраическим формальным
преобразованиям.
Законы логики высказываний
1) Законы коммутативности - перестановка формул в симметричных связках &,
a&b = b&a;
a b = b a.
2) Законы ассоциативности - порядок применения бинарных связок и расстановка скобок
a&(b&c) = (a&b)&c;
a (b c) = (a b) c.
Слайд 49
3) Идемпотентность – тождественное исключение эквива-лентных формул в
бинарных связках &,
a a = a;
a&a
= a.
4) Дистрибутивность - распределительный закон для бинарных связок &,
a&(b c) = (a&b) (a&c);
a (b&c) = (a b)&(a c).
5) Законы поглощения
a&(a b) = a;
a (a&b) = a.
Булева алгебра высказываний
Алгебра логики (булева алгебра) определена на множестве высказываний S={A, B, …}.
Слайд 50
Булева алгебра высказываний – метод вычисления значе-ний составных
высказываний, определяемых формулами высказываний.
Дополним множество высказываний S двумя константа-ми:
T=1 и F=0. На множестве S справедливы законы нуля и единицы, что следует из таблиц истинности для бинарных связок &, :
6) Законы нуля и единицы
0 а = а; 1 а = 1;
0 & а = 0; 1 & а = а.
Для произвольного высказывания a и инверсии a, которая, по определению связки НЕ, обозначает единственное высказывание в S для каждого a, выполняются следующие тождества:
Законы дополнительного элемента
a a = 1; a & a = 0.
Слайд 51
При этом также выполняются следующие законы, которые определяют
свойства операции инверсии в алгебре логики:
8) Закон двойного отрицания
( a) = a.
9) Законы двойственности (правила де Моргана) – приведение инверсии к атомам
(a b) = a & b;
(a & b) = a b.
10) Замена импликации бинарными связками &,
a b = a b.
11) Замена эквивалентности
a ~ b = (ab)(ba) = (a b)(b a).
12) Замена исключающего ИЛИ
a b = (a~b) = (ab)(ba) = (a b) (a b).
Слайд 52
13) Законы сокращения – применяются для упрощения формул
a (a&b) = a b;
a&(a b)
= a&b.
14) Правило склеивания – применяется для упрощения формул
(a&b) (a&b) = b.
Законы алгебры логики позволяют применять системати-ческие алгебраические методы преобразования формул логики, которые сводятся к тождественным подстановкам в соответствии с тождествами (1-14).
Атомы в формулах являются булевыми переменными и могут принимать значения {0,1}. Логические связки могут быть заменены знаками (& - логическое умножение ( ), операция отрицания a обозначается инверсией переменной ).
Слайд 53
Булеву алгебру можно использовать для проверки тож-деств, тавтологий,
в преобразованиях, упрощающих рас-суждения.
Применение булевой алгебры для проверки тождеств
Можно
выделить основные законы булевой алгебры и законы, которые могут быть доказаны с применением аксиом. К основным законам относят (1-4, 6,7)
Доказательство правила де Моргана
(a b) = a & b.
Рассмотрим формулу a b a & b = дистрибутивный закон
= (a b a) &(a b b) = 1 закон дополнительного элемента
Слайд 54
Рассмотрим формулу (a b) & a &
b = дистрибутивный
закон
= a & a & b a &b & b) = 0. закон дополнительного элемента
Таким образом, получены тождества:
но согласно законам дополнительного элемента
c c = 1;
c & c = 0,
пусть с = a b, тогда, из полученных тождеств, следует, что
c = (a b) = a & b, что и требовалось доказать.
Слайд 55
Применение алгебры для вычислений – метод Квайна
Метод Квайна
заключается в следующем: последова-тельно подставляются значения истинности в формулу
для аргументов и вычисляются значения иcтиности, или выполняются алгебраические преобразования формул до тех пор, пока не получим конечные значения T или F.
Алгоритм вычислений строится в виде бинарного дерева (двоичной диаграммы) – концевые вершины обозначают все возможные значения формулы.
Слайд 56
Двоичная диаграмма, построенная методом Квайна, может быть использована
для вычислений при заданных наборах значений переменных.
Двоичная бинарная диаграмма
- Binary Decision Diagram (BDD) может быть получена сверткой бинарного дерева относительно значений истинности
if (c) Ф=1;
else Ф=0;
else Ф=0.
Пример. Построить BDD для формулы
Пример. Построить BDD для функции суммирования
Слайд 58
Применение алгебры для доказательства общезначимости
Утверждение 3. Если в
результате тождественных алгебра-ических преобразований формула Ф(a, b, ...) тождествен-но
равна единице, то формула Ф - тавтология (прямой ме-тод доказательства).
Утверждение 4. Если в результате тождественных алгебра-ических преобразований формула Ф(a, b,...) тождествен-но равна нулю, то формула Ф – тавтология (обратный ме-тод доказательства).
Слайд 59
Пример - применение прямого метода.
Требуется проверить общезначимость
формулы транзи-тивности
Пример - применение обратного метода.
Т.е. Ф=0, значит
формула Ф – тавтология.
6. SAT-проблема (прямой метод)
Преобразование формулы в ДНФ позволяет получить конъюнктивные термы, соответствующие выполнимым интерпретациям (наборам).
Слайд 60
Проверка общезначимости формул (обратный метод)
Преобразование инверсии формулы Ф
в ДНФ позволяет опровергнуть общезначимость Ф обратным методом. ДНФ
состоит из конъюнктивных термов, определяющих выполнимые интерпретации.
Пример.
Проверить общезначимость следующей формулы
Ф = (ab c)(a b ac).
Инверсия этой формулы в алгебраической форме
Ф =((ab с)(a b ac)) = (ab) c (ab)(ac) =
= (a b)c (a b)(a c) =
= aс bc aa ba ac bc.
Можно использовать любой из термов для выбора интер-претации, в которой формула Ф выполнима, а Ф не вы-полнима, например, для aс=1 значения a=0 и c=1. Следовательно, формула Ф не общезначима.
Слайд 61
Метод Девиса - Патнема (DP)
Решение SAT-проблемы
КНФ рассматривается как
множество дизъюнктов
S ={s1, s2, …, sn}.
Алгоритм SAT включает
формальные шаги в виде правил преобразования множества S:
1) Правило однолитерных дизъюнктов:
а) Если присутствуют однолитерные дизъюнкты L и дизъ-юнкты L A, то дизъюнкты L A исключаются по закону поглощения L&(L A) = L;
б) Найдем для каждого однолитерного дизъюнкта L дизъ-юнкт, который содержит L , тогда в дизъюнктах можно исключить L по закону сокращения L&(L A) = L&А;
в) после преобразования дизъюнктов вычеркивается од-нолитерный дизъюнкт L, так как S выполнимо при L=1 и оставшееся множество дизъюнктов не зависит от L.
Слайд 62
2) Правило чистых литер:
Литера L – чистая, если
во множестве дизъюнктов S не существует ни одного дизъюнкта
с отрицанием (L)
(L s1)&(L s2)& …&(L sn) = (L s1&s2&…&sn).
Вычеркиваются все дизъюнкты, содержащие L, так как S выполнимо при L=1, а оставшееся множество дизъюнктов не зависит от L.
3) Если правила 1) и 2) не применимы, то можно выбрать для одной из оставшихся литер значение 0 и 1, применить метод Квайна и проверить выполнение правил 1) и 2).
4) Повторить правила 1) - 3), пока не будут получены пустая формула или противоречивые дизъюнкты на шаге 1а. Пустая формула обозначает, что при исключении литер L1L2...Lm=11...1 найдена интерпретация, в которой Ф выполнима.
Слайд 63
Пример.
Проверить выполнимость формулы
Ф = (p q)(p
q)(q t)(q t).
Правила Девиса - Патнема
не применимы, поэтому на первом шаге используем метод Квайна
Получена пустая формула и выбрана интерпретация pqt=110, при которой формула Ф выполнима. Другие интерпретации можно найти по правой ветви дерева при p=0, например, при pqt=001.
Слайд 64
Проверка формулы на общезначимость
Метод DP применим для проверки
формулы на общезна-чимость обратным методом. Для опровержения доста-точно найти
хотя бы одну выполнимую интерпретацию SAT-алгоритмом для инверсной формулы Ф в КНФ.
В этом случае формула Ф выполнима и Ф не общезна-чима.
Если на шаге 1а останутся инверсные однолитерные дизъ-юнкты L и L, то Ф противоречие и Ф общезначима.
Пример. Проверить общезначимость закона транзитивности импликации
Ф = (((p → r)(r → q)) → (p→q) =
= (p → r) (r → q)) (p → q) исключение импликации
Ф = (p → r)(r → q))(p → q) = инверсия Ф
= (p r)(r q)p q исключение всех импликаций
Слайд 65
применяя правило 1 для p и r, получим
противоречие
q&q=0, следовательно, Ф противоречие и Ф общезна-чима.
Пример.
Проверить
общезначимость формулы
Ф = (p q) & (p q) & (r q) → (r & q).
Ф = (p q) & (p q) & (r q) & (r&q )
Слайд 66
Ф выполнима при p=1 и r=1, следовательно, Ф
не обще-значима.
Применение тавтологий в рассуждениях
Схемы рассуждений должны быть логически
правильно построены, только тогда выводы могут быть признаны истинными.
Тавтологии являются формальными схемами правильных рассуждений и стратегией доказательства в математике (например, теоремы элементарной геометрии).
Рассуждения строятся в виде цепочки общезначимых схем рассуждений.
Доказательства общезначимости схем формируются алгебраически или DP-методом.
Слайд 67
Некоторые простые схемы рассуждений:
1) Правило отделения
p(p → q) → q.
“Если условие p истинно
и доказано, что из p всегда сле-дует q, то следствие q истинно.”
(p(p → q)) → q = (pq) q = p q q =1.
Очевидным обобщением правила является правило modus ponens (MP, лат. правило вывода), где p, p → q и q-тавтологии.
Остальные правила также применимы к тавтологиям.
2) Правило Евклида
(p → p) → p.
“Если из предположения, что p ложно следует, что p истинно, то p истинно”.
(p → p) → p = p p = 1.
Слайд 68
3) Правило доказательства разбором случаев
(p q)(p
→ r )( q → r) → r.
“Доказывается утверждение
r, выбираются по крайней мере два условия p и q (одно или оба истинные), для которых может быть доказано (p → r)&(q → r) тогда r истинное утверждение.”
противоречие и Ф общезначима.
4) Правило контрапозиции (доказательство от против-ного)
(p → q) = (q → p)
“(p → q) истинно тогда, кoгда истинно (q → p).
Слайд 69
Требуется доказать, что из истинности утверждения p следует
истинность утверждения q. При этом существует содержательный или конструктивный
метод доказатель-ства тождественного утверждения (q → p). Следовательно, приходим к противоречию с условием p.
Если ((p → q) ~ (q → p)) тавтология, то
Ф = ((p → q) → (q → p))((p → q)(q → p)) тоже тавтология.
Ф = (p q q p) (p q q p) = 1.
5) Правило косвенного доказательства
Слайд 70
“Доказывается утверждение p. Для этого выбирается не-которое утверждение
q, для которого можно доказать, что из p следует
как q, так и (q). Тогда для p приходим к противоречию q& q и утверждение p истинно.”
(p → q)(p → q) → p = (p q)(p q) → p = p → p = 1.
6) Правило доказательства эквивалентностью
(a ~ b) = ((a → b)(b → a)).
“Для доказательства эквивалентности двух утверждений a и b в математике доказываются необходимость и доста-точность для одного из утверждений ((b→a) = (a необхо-димо для b) и (a→b) = (a достаточно для b)). Левая и пра-вая части тождества истинны и ложны при одинаковых интерпретациях”.
Это тождество использовалось при определении связки эквивалентности.
Слайд 71
7) Правило доказательства цепочкой импликаций (свойство транзитивности импликации
– силлогизм – умозаключение, в котором из двух суждений
– посылок получается третье – вывод)
(p → r)(r → q) → (p → q).
“Требуется доказать, что (p → q). Выбирается промежу-точное утверждение r и последовательно доказывается (p → r), далее (r → q). Затем делается вывод (p → q).”
(p → r)(r → q) → (p → q) = p r r q p q = 1.
Аксиоматическая теория высказываний
Схемы аксиом
Множество высказываний составляет предметную об-ласть знаний. Меньшая часть этих высказываний (правил) считается истинной или доказуемой.
Слайд 72
В математической теории доказуемые высказывания на-зываются теоремами. Теоремы
выводятся из некоторых фиксированных истинных высказываний (тавтологий), которые называются
аксиомами. Подобные математи-ческие теории называют аксиоматическими.
В математической логике минимальное множество пер-вичных аксиом, из которых следуют все тавтологии, назы-вают схемами аксиом. Логика высказываний является аксиоматической теорией исчисления высказываний. Теоремами этой теории являются тавтологии.
Известны различные схемы аксиом, например, схемы аксиом Гильберта и Аккермана:
А1) А А → А;
А2) А →(А В);
А3) (А В) →(В А);
А4) (А → В) →(С А → С В).
Слайд 73
Можно подставлять вместо символов любые формулы и в
соответствии с утверждением 2 формулы остаются тавто-логиями. Доказывается, что
все тавтологии могут быть получены из этой схемы аксиом с использованием под-становок и одного правила отделения MP из множества схем правильных рассуждений.
Определение.
Формальное доказательство (схема вывода) – последовательность формул, каждая из которых:
- аксиома;
- получена подстановкой формул в аксиому;
- результат применения правила МР.
Все формулы в последовательности – тавтологии и пос-ледняя формула в этой последовательности - логическое следствие или теорема.
Слайд 74
Из схемы аксиом выводятся только тавтологии, которые обозначаются
В
Вывод
- доказательство теорем – нетривиальная задача, требующая изобретательности и интуиции.
Вывод - альтернатива алгебраическому доказательству и доказано, что он всегда существует.
Пример вывода:
Доказать (А А), используя вывод из аксиом.
1) А А → А; (А1)
2) ((А А) → А) →(А (А А) →А А);
(из А4: С/А, А/(А А), В/А)
3) А (А А) →А А; (МP: (1, 2) → 3)
4) (А →(А А)) →(А → А); (тождественная замена дизъюнкции импликацией)
(А2: В/А)
6) А → А; (МP: (4, 5) → 6)
7) А А; (замена импликации на дизъюнкцию)
8) А А → А А; (А3: В/А, А/А)
9) А А. (МP: (7, 8) → 9)
Теорема доказана.
Правила преобразования тавтологий
1) Удаление конъюнкции (УК, Simplification)
“Если p&q тавтология, то, по определению конъюнкции и импликации, p, q - тавтологии”
p&q
p, q.
Если формула p&q тавтология, то p&q=1 и, по определению конъюнкции, p=q=1.
Слайд 76
2) Введение конъюнкции (ВК, Cojunctions)
“Если p и q
тавтологии, то, по определению конъюнкции, p&q тавтология”
p, q
p&q.
При
доказательстве используются обратные рассуждения для предыдущего правила.
3) Введение дизъюнкции (ВД, Addition)
«Если p - тавтология, то p q –тавтология»
_ p__
p q.
Если p=1, то справедливы тождества p q = 1 q = 1.
4) Удаление дизъюнкции (УД, Disjunction Syllogism)
“Если p q тавтология и p противоречие, то q тавтология”
p q, p
q.
p q=1,p=1, противоречие p=0, p q = 0 q = 1, q=1.
Слайд 77
5) Дизъюнктивное расширение (ДР)
“Если p → q тавтология,
то при добавлении к условию p и следствию q
любого высказывания получим тавтологию”
__ p → q___
p b → q b.
Тавтология p → q = p q = 1,
тождества p q = p q b = (p b) (q b) =
= (p b) →(q b) =1.
6) Транзитивность импликации (ТИ, Hipotez Syllogism)
«Если (p → r) и (r → q) тавтологии, то по закону транзитивности (p → q) тавтология»
p → r, r → q
p → q.
7) Конструктивная Дилемма (СD)
a b, a → c, b → d
c d.
Слайд 78
Тавтологии (a b)(b→d) = (a→b)(b→d) = (a→d)
= 1 (6- правило)
(a→d) = (d→a)(a→c) = (d→c)=(d
c) = 1 (6-правило)
(c d) тавтология.
Утверждение о полноте теории высказываний
Если формула А – тавтология, то она является теоремой исчисления высказываний.
Утверждение о непротиворечивости
Не существует формулы А такой, что А и А являются теоремами.
Следствие. Существуют формулы, которые не являются тавтологиями. Если А – тавтология, то А – не тавтология (противоречие).
Слайд 79
Логический вывод из гипотез
Гипотезы – истинные по определению,
убеждению или опыту утверждения в некоторой области.
В отличие
от аксиом теории высказываний гипотезы Г не обязательно тавтологии, но непротиворечивы. В отличие от вывода в аксиоматической теории, вывод формулы В из гипотез (Г B) подтверждает не общезначимость форму-лы В, а только ее истинность при интерпретациях, в кото-рых истинны гипотезы Г. Формула В вне этой области ис-тинности конкретных гипотез может быть ложной.
Следовательно, правильные рассуждения имеют смысл только в данной конкретной области знаний. Причем тав-тология не может быть получена при выводе из гипотез, которые не являются тавтологиями - что следует из полно-ты и непротиворечивости теории исчисления высказыва-ний.
Слайд 80
Прямой метод вывода
Определение.
Формула В логическое следствие из
гипотез Г={F1, F2, …, Fm}(m≥0), если при любой интерпретация
I, где F1(I) и F2(I) … и Fm(I) истинны B(I) так же истинно. Обозначается F1F2…Fm В.
Утверждение 7.
Если Г={F1, F2, ..., Fn} B, то Ф = F1&F2 &…&Fn → В =
= F1 F2 ... Fn B = (F1 → (F2 → ... → (Fn → B))...) тавтология.
Таким образом, прямой метод вывода любой формулы В из гипотез сводится к доказательству общезначимости формулы.
Для заданных гипотез F1, F2, …, Fn строится цепочка формул с применением правил вывода, пока не будет получена заданная формула B.
Слайд 81
Правила при выводе из гипотез:
- если существует
интерпретация I, при которой гипотезы выполнимы, то и следствие
из гипотез в этой интерпрета-ции выполнимо;
- если гипотезы общезначимы в некоторой области интер-претации, тогда и следствие общезначимо в этой области.
Правила логического вывода аксиоматической теории высказываний применимы и при выводе из гипотез.
1) Правило отделения (MP, modus ponens)
А, A → B
B.
По определению импликации (A B)A = AB = B = 1, при A=1.
Слайд 82
2) Отрицательный модус (MT, modus tollens)
A → B,B
A.
По определению импликации (A B)B =AB
=A = 1 при B = 1.
3) Удаление конъюнкции (УК)
P&Q
P, Q.
По определению конъюнкции, если P(I)&Q(I) выполнима в I, то P(I), Q(I) так же выполнимы.
4) Введение конъюнкции (ВК)
P(I), Q(I)
P(I)&Q(I).
Если P(I) и Q(I) выполнимые гипотезы в интерпретации I, то и конъюнкция P(I)&Q(I) выполнима в этой интерпре-тации.
Слайд 83
5) Введение дизъюнкции (ВД, Addition)
A(I)__
A(I) B(I).
Если A(I) выполнима, то A(I)
B(I) тоже выполнима в этой интерпретации.
A(I) →(A(I) B(I)) = A(I) A(I) B(I) = 1 тавтология при любых интерпретациях, следовательно A(I) B(I) выполнима при I.
6) Удаление дизъюнкции (УД)
P(I) Q(I), P(I)
Q(I).
ЕслиP(I) выполнима в некоторой интерпретации I и
P(I) Q(I) выполнима в этой интерпретации, то выполни-ма и Q(I).
(P(I) Q(I))&P(I) = P(I)&P(I) Q(I)&P(I) = 0 Q(I)&P(I)
выполнима и Q(I) (по УК).
Слайд 84
7) Дизъюнктивное расширение (ДР)
P(I) → Q(I)____
P(I) B(I) → Q(I) B(I).
(P(I)
→ Q(I)) → (P(I) B(I) → Q(I) B(I)) =
= (P(I) → Q(I)) → (P(I)&B(I) Q(I) B(I)) =
= (P(I) → Q(I)) → (P(I) Q(I) B(I)) = (P(I) → Q(I)) → ((P(I) → Q(I)) B(I)) = Р(I) → (Р(I) B(I)) = 1, тавтология, при любых интерпретациях, следовательно, выполнима при I.
8) Транзитивность импликации (ТИ)
(P(I) → R(I)), (R(I) → Q(I))
P(I) → Q(I).
Если (P(I) → R(I)) и (R(I) → Q(I)) выполнимы в интерпретации I, то (P(I) → Q(I)) выполнима в этой интерпретации.
Слайд 85
(P(I) → R(I)) &(R(I) → Q(I)) = (P(I)
R(I)) &(R(I) Q(I))
(P(I) R(I)) &(R(I)
Q(I)) →(P(I) Q(I)) =
= P(I) & R(I) R(I)& Q(I) P(I) Q(I) =
=P(I) Q(I) R(I) R(I) = T выполнима при любых интерпретациях, следовательно, P(I)→Q(I), выполнима в I.
9) Конструктивная Дилемма (СD)
a b, a → c, b → d
c d
((a b)(a → c)(b → d)) → (c d) =
= ((ab) (ac) (bd)) (c d) =
= (a a b c d) = T, при любых интерпретациях.
Пример.
Есть три гипотезы: AB, A→C, B→D
Предполагаемое следствие из гипотез: C D.
(гипотеза);
2) A B → C B
(правило ДР к 1 → 2);
3) B → D (гипотеза);
4) C B → C D (правило ДР к 3 → 4);
5) A B → C D (правило ТИ к 2, 4 → 5)
6) A B (гипотеза);
7) C D (правило МР к 5, 6 → 7).
Пример.
Гипотезы: (A&D)→B, A, C, C→D
Следствие: B.
7) B (МР 5, 6 → 7).
1) A (гипотеза);
2) C (гипотеза);
3) C → D (гипотеза);
4) D (МР 2, 3 → 4);
5) A&D (ВК 1, 4);
6) (A&D) → B (гипотеза);
Слайд 87
Эффективный частный случай логического вывода из гипо-тез известен
как метод математической индукции. Осознание метода математической индукции как
отдель-ного важного метода восходит к Блезу Паскалю и Герсо-ниду. Современное название метода было введено де Морганом в 1838 году.
ЛЁВИ бен Гершом (Герсонид) (1288-1344) — средневеко-вый еврейский ученый, философ, математик, астроном, талмудист. Он оставил ряд сочинений на иврите по мате-матике, астрономии, философии, богословию, психологии, медицине, физике, метеорологии, астрологии. В трактате «Дело вычислителя» (1321) Герсонид первым в Европе вы-вел основные комбинаторные формулы для подсчета чис-ла сочетаний, перестановок и размещений; для их доказа-тельства применил метод математической индукции.
Слайд 88
В трактате «О синусах, хордах и дугах» Леви
бен Гершом доказал теорему синусов; составил пятизначные таблицы синусов.
Изобретенный им навигационный квадрант на-шел применение в мореплавании.
Метод математической индукции заключается в следующем:
1) утверждается гипотеза P(0) - базис индукции;
2) доказывается P(0) a P(1);
3) доказывается P(n) a P(n+1);
