Презентация на тему "Математическая логикаи теория алгоритмов"

Содержание

• 
  Слайд 1

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

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

• 
  Слайд 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) Исключающее ИЛИ (ЛИБО, ЛИБО, ) – разделительное ИЛИ. Связка ЛИБО (ИЛИ /НО НЕИ) “А либо В истинно (АВ) тогда и только тогда, когда АИЛИВ истинны, но АИВ ложны” = (AB)  ((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) = AB = = А В = “яблоко не зеленое (А) или кислое (В)”. Здесь A, Bразные свойства для одного класса и пример преобразования формулы, сохраняющей истинностный смысл рассуждения. 2. “Если влажность высокая (А), то после полудня (В) или (либо) вечером (С) будет дождь (В C) “. Высказывания А, В, С – события из разных классов, А (В  С).

• 
  Слайд 38
  

  3. “Лечение не будет найдено (А), пока не определены причины болезни (В) и не найдены новые лекарства (С)”. Высказывания А, В, С – события из разных классов, В& С А. 4. “Требуется (необходимы !) храбрость (А) и мастер-ство(В), чтобы подняться на эту гору (С)”. А, В – свойства, С – событие, СА&В. 5. “Для того, чтобы число было нечетным (А), необходимо , чтобы число было простым (В) и не делилось на два (С)”. А, В, С – свойства чисел, AВ&С. 6. “Если (210) (B), то (2≠10) (C)”. A, B, C – отношения в классе чисел. A& BC.

• 
  Слайд 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), что можно было уточнить при записи формулы для первого высказывания. ((ab)&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 = (ab)(ba) = (a b)(b a). 12) Замена исключающего ИЛИ a b = (a~b) = (ab)(ba) = (a b)  (ab).

• 
  Слайд 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)может быть получена сверткой бинарного дереваотносительно значений истинности

• 
  Слайд 57
  

  if (a) 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  (ab)(ac) = = (ab)c (ab)(ac) = = aс bcaabaacbc. Можно использовать любой из термов для выбора интер-претации, в которой формула Ф выполнима, а Ф не вы-полнима, например, для 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) (А →(А А)) →(А → А); (тождественная замена дизъюнкции импликацией)

• 
  Слайд 75
  

  5) А → А А; (А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, modusponens) А, A → B B. По определению импликации (AB)A = AB = B = 1, при A=1.

• 
  Слайд 82
  

  2) Отрицательный модус (MT, modustollens) A → B,B A. По определению импликации (AB)B =AB =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) = =((ab)(ac)(bd))  (c  d) = = (a  a  b  c  d) = T, при любых интерпретациях. Пример. Есть три гипотезы: AB, A→C, B→D Предполагаемое следствие из гипотез: C D.

• 
  Слайд 86
  

  1) A→C (гипотеза); 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);

• 
  Слайд 89
  
• 
  Слайд 90
  
• 
  Слайд 91