научная работа. Шаг в будущее. Использование элементов математической логики при решении задач
 Скачать 89.54 Kb.
|
|
«Шаг в будущее» Исследовательская работа на тему «Использование элементов математической логики при решении задач» Секция: Математика Автор: Лохова Алина Сергеевна ученица 9 класса МБОУ «Озёрная СОШ» Научный руководитель: Хрипко Мария Николаевна, учитель МБОУ «Озёрная СОШ» 2014 год Содержание Введение Глава 1. История возникновения математической логики. Глава 2. Элементы логики высказываний. 2.1.Операция отрицания 2.2.Импликация 2.3.Эквиваленция Глава 3. Решение задач Заключение Литература Введение Логика – это Бог мыслящих. Л. Фейхтвангер Умение правильно рассуждать необходимо в любой области человеческой деятельности: науке и технике, юстиции и дипломатии, планировании экономики и военном деле. И это умение восходит к древнейшем временам, логика, т.е. наука о том, какие формы рассуждений правильны, возникла лишь немногим более двух тысяч лет тому назад. Она была развита в VI в. до н.э. в работах великого древнегреческого философа Аристотеля, его учеников и последователей. В какой-то момент математики задали вопрос: «В чем, собственно, состоит математика, математическая деятельность?» Простой ответ заключается в том, что математики доказывают теоремы, то есть выясняют некоторые истины о реальном мире и «идеальном математическом мире». Попытка ответить на вопрос что такое математическая теорема, математическая истина и что такое математическое утверждение истинно или доказуемо, это и сеть исходная точка математической логики. Мы должны в школе научиться анализировать, сравнивать, выделять главное, обобщать и систематизировать, доказывать и опровергать, определять и объяснять понятии, ставить и решать проблемы. Овладение этими методами и означает умение мыслить.Всё вышеизложенное являктся актуальностью данной темы. Второй исходной точкой наших рассмотрений является выяснение того, что значит, что математическая функция вычислима и ее можно вычислить с помощью некоторого алгоритма, формального правила, точно описанной процедуры. У этих двух исходных постановок есть много общего, они естественно объединяются под общим названием «математическая логика», где под математической логикой понимается прежде всего логика математических рассуждений и математических действий. Я выбрала именно эту тему, потому что владение элементами математической логики поможет мне в моей будущей экономической профессии. Ведь маркетолог анализирует тенденции рынка, цены, объём оборота. Для этого нужно использовать знание логики. Цель работы: изучить и использовать возможности математической логики в решении проблем в различных областях и деятельности человека. Задачи: 1. Проанализировать литературу о сущности и возникновении математической логики. 2. Изучить элементы математической логики. 3. Подобрать и решить задачи с элементами математической логики. Методы: анализ литературы, понятий, метод аналогий в решении задач, самонаблюдение. 1. Из истории возникновения математической логики Математическая логика тесно связана с логикой и обязана ей своим возникновением. Основы логики, науки о законах и формах человеческого мышления были заложены величайшим древнегреческим философом Аристотелем (384—322 гг. до н. э.), который в своих трактатах обстоятельно исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления, в том числе законы противоречия и исключения третьего. Вклад Аристотеля в логику весьма велик, недаром другое ее название - аристотелева логика. В одном из своих трактатов Аристотель вплотную приблизился к одному из разделов математической логики - теории доказательств. Но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646 - 1716), указавший пути для перевода логики «из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно». При этом в своих работах Лейбниц затрагивал и двоичную систему счисления. После Лейбница исследования в этой области вели многие выдающиеся ученые, однако настоящий успех пришел здесь к английскому математику-самоучке Джорджу Булю (1815—1864) В 1847 году Буль опубликовал статью «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений», а в 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей». Буль изобрел своеобразную алгебру - систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключательных схем. Большой вклад в развитие логики внесли и русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947). Наконец, в последние десятилетия XX века бурное развитие математической логики было обусловлено развитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К. Клини, А. Черч, А.А Марков, П.С. Новиков и многие другие). В середине XX века развитие вычислительной техники привело к появлению логических элементов, логических блоков и устройств вычислительной техники, что было связано с дополнительной разработкой таких областей логики, как проблемы логического синтеза, логическое проектирование и логического моделирования логических устройств и средств вычислительной техники. В 80-х годах XX века начались исследования в области искусственного интеллекта на базе языков и систем логического программирования. Началось и создание экспертных систем с использованием и развитием автоматического доказательства теорем, а также методов доказательного программирования для верификации алгоритмов и программ для ЭВМ. В 80-ые годы начались также изменения в образовании. Появление персональных компьютеров в средних школах привело к созданию учебников информатики с изучением элементов математической логики для объяснения логических принципов работы логических схем и устройств вычислительной техники. Одним из основных разделов математической логики, лежащим в основе других ее разделов, является логика высказываний. 2. Элементы логики высказываний Алгебра логики (логика высказываний) - один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях высказываний. Высказывание - это термин математической логики, которым обозначается предложение какого-либо языка (естественного искусственного), рассматриваемого лишь в связи с его истинностью. Отличительным признаком любого высказывания является его свойство быть истинным или ложным. Используя простые высказывания, можно образовывать сложные, или составные, высказывания, в которые простые входят в качестве элементарных составляющих. Таким образом, в отличие от сложного, простое высказывание не поддается расчленению на высказывания. При первоначальном изучении логики высказываний обращают внимание не на содержание, а на истинность или ложность высказываний. Основная задача логики высказываний заключается в том, чтобы на основании истинности или ложности простых высказываний определить истинность или ложность сложных высказываний. Среди сложных высказываний можно выделить соединительные, разделительные, условные, эквивалентные и высказывания с внешним отрицанием. 1. Операция отрицания (иногда называют операцией инверсии) является простейшей операцией логики высказываний. Если А – истинное высказывание, то ¬А является ложным высказыванием, и наоборот, если А – ложно, то ¬А – истинно. Операция отрицания выражается словосочетанием «неверно, что» и определяется следующей таблицей истинности:
Операция конъюнкции (логического умножения). Соединение двух простых высказываний A и B в одно составное с помощью союза «и» называют логическим умножением или конъюнкцией, а результат операции — логическим произведением. Конъюнктивное (соединительное) высказывание АΛВ – это высказывание, в котором утверждается наличие двух ситуаций. Например, «солнце светит и нет дождя». Операция конъюнкции определяется с помощью следующей таблицы истинности:
Например, пусть высказывание А – число 100 делится на 5, а высказывание В – число 100 больше 5. Тогда сложное высказывание АΛВ будет истинным. Операция дизъюнкции (логическое сложение), соответствующая союзу «или» имеет два различных значения. Следует различать исключающее «или» и неисключающее «или». Логическая операция, соответствующая неисключающему «или» называется дизъюнкцией и обозначается AVB, а полученное составное высказывание — логической суммой. Дизъюнкция определяется следующей таблицей истинности:
2 Импликация (логическое следование) – это одна из самых важных операций логики высказываний. Эта операция соответствует обороту «если…, то…». По определению импликация А→ В истинна всегда за исключением случая, когда А истинно, а В ложно. Таблица истинности для операции импликация имеет следующий вид: Импликация (логика). Екі А мен В тұжырымдарының импликациясы деп А–ақиқат, В жалған болғанда мәні жалған, ал қалған жағдайда ақиқат болатын тұжырымды айтамыз.Операция (Егер… онда) белгімен белгіленеді. А В, А В ( егер А болса, онда В) (А дан В) болып оқылады.Мұнда А– тұжырымының алғы шарты деп ал В қорытындысы деп аталады. Импликация операциясының ақиқат кестесі келесі түрде болады:
Последние две строки таблицы следуют из того, что из ложного высказывания можно получить как истинное, так и ложное высказывание. Кестенің соңғы екі жолы жалған мәлімдемеден шынайы және жалған мәлімдемені алуға болатындығына байланысты. Например,Мысалы, а) если 2+3=6, то 2*2=4 б) если 2+3=6, то 2*2=5 а) егер 2+3=6 болса, онда 2*2=4 б) егер 2+3=6 болса, онда 2*2=5 Очень часто высказывание после слова «если» называется основанием, а после слова «то» следствием. Например, «если идет дождь, то земля мокрая». Здесь простое суждение «идет дождь» - основание, а следствие – «земля мокрая». Көбінесе "егер" сөзінен кейін тұжырым негіз деп аталады, ал" содан кейін " сөзінен кейін нәтиже болады. Мысалы, "егер жаңбыр жауып тұрса, онда жер ылғалды болады". Мұнда "жаңбыр жауады" деген қарапайым пікір бар - негіз, ал нәтижесі – "жер ылғалды". 3. Эквиваленция. Высказывание «А тогда и только тогда, когда В» называют эквиваленцией высказываний А и В и обозначают А ↔ В. Сложное высказывание А ↔ В (читается А эквивалентно В) истинно тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны. В остальных случаях А ↔ В ложно. Операция эквиваленции задается следующей таблицей истинности: Эквиваленция А мен В тұжырымының ақиқаттық мәндері бірдей болғанда, мәндері ақиқат, әр түрлі болғанда (А,В) жалған болатын тұжырым эквивалентті тұжырым деп аталады. Белгілеулері: А В; А В; А В; А эквивалентті В-ға ; Егер тек В болғанда А ; А мен В бір мәнді, А мен В сонда ғана ақиқат, егер А,В түжырымдары ның екеуі де не ақиқат, не жалған болса. болып оқылады.
Таким образом, сложное высказывание А↔В – это высказывание, в котором утверждается одновременное наличие или отсутствие двух ситуаций. Сонымен, А В В күрделі тұжырымы дегеніміз-бір уақытта екі жағдайдың болуы немесе болмауы туралы мәлімдеме
Скобки указывают последовательность выполнения операций (как и в элементарной алгебре). При отсутствии скобок первой всегда выполняется операция отрицания, затем операция конъюнкциии (логическое умножение), операция дизъюнкции (логическое сложение), затем импликация и эквиваленция. Жақшалар операциялардың реттілігін көрсетеді (Қарапайым алгебрадағыдай). Бірінші жақша болмаған кезде әрдайым теріске шығару операциясы жасалады, содан кейін конъюнкция операциясы (логикалық көбейту), ажырату операциясы (логикалық қосу), содан кейін импликация және эквивалент. 3. Задачи и их решение Задача 1. Решаем методом «здравых рассуждений». Пять десятиклассников приехали из пяти различных городов Самарской области в Самару на областную олимпиаду по экономике. «Откуда вы, ребята?» – спросили их организаторы олимпиады. Вот что ответил каждый из них. Андреев: «Я приехал из Тольятти, а Григорьев живет в Жигулевске». Борисов: «В Жигулевске живет Васильев. Я же прибыл из Октябрьска». Васильев: «Я – из Тольятти, а Борисов – из Кинеля». Григорьев: «Я приехал из Жигулевска, а Данилов из Чапаевска». Данилов: «Да, я действительно из Чапаевска, Андреев же живет в Октябрьске». Организаторов очень удивили противоречивые ответы приехавших гостей. Ребята объяснили, что каждый из них высказал одно правильное утверждение, а другое – ложное. Но по их ответам можно установить, кто откуда приехал. Определите, откуда приехал каждый школьник. Решение. Рассмотрим первый возможный вариант. Пусть первое утверждение Андреева верное, то есть он из Тольятти. Тогда Григорьев живет не в Жигулевске. Поэтому второе утверждение Данилова – ложное, значит, он из Чапаевска. Тогда первое утверждение Григорьева – ложно. Так как Андреев из Тольятти, то первое утверждение Васильева ложно, поэтому Борисов – из Кинеля. Так как Григорьев не из Жигулевска, то остается, что он из Октябрьска, а Васильев – из Жигулевска. Рассмотрим второй возможный вариант. Пусть у Андреева второе утверждение – правильное, тогда Григорьев приехал из Жигулевска. Значит, Данилов приехал не из Чапаевска, а Андреев не из Тольятти. Тогда у Борисова первое утверждение ложное (в Жигулевске живет Григорьев), следовательно, Борисов прибыл из Октябрьска. Поэтому Андреев не из Октябрьска и получается, что Данилов – из Чапаевска. Получили противоречие: Данилов из Чапаевска и не из Чапаевска. Значит, второй вариант невозможен. Ответ. Андреев – из Тольятти, Борисов – из Кинеля, Васильев – из Жигулевска, Григорьев – из Октябрьска, Данилов – из Чапаевска. 3. Есептерді және олардың шешімі. Есеп 1. Біз "дұрыс ойлау" әдісімен шешеміз. Он сынып оқушылары Самара облысының бес түрлі қаласынан Самараға экономика бойынша облыстық олимпиадаға келді. "Сіз қайдан, балалар?"- деп сұрады олимпиаданы ұйымдастырушылар. Міне, олардың әрқайсысы жауап берді. Андреев:"мен Тольяттиден келдім, Григорьев Жигулевскіде тұрады". Борисов: "Васильев Жигулевскіде тұрады. Мен Октябрьскіден келдім". Васильев:"мен Тольяттиден, ал Борисов Кинельденмін". Григорьев:"мен Жигулевскіден, ал Данилов Чапаевскіден келдім". Данилов:"Ия, мен шынымен Чапаевскіден келемін, Андреев Октябрьскіде тұрады". Ұйымдастырушылар келген қонақтардың қарама-қайшы жауаптарын таң қалдырды. Балалар олардың әрқайсысы бір дұрыс мәлімдеме, ал екіншісі жалған мәлімдеме жасағанын түсіндірді. Бірақ олардың жауаптары бойынша кімнің қайдан келгенін анықтауға болады. Әр оқушының қайдан келгенін анықтаңыз. Шешімі. Бірінші мүмкін нұсқаны қарастырыңыз. Андреевтің алғашқы тұжырымы рас болсын, яғни ол Тольяттиден. Содан кейін Григорьев Жигулевскіде тұрмайды. Сондықтан Даниловтың екінші тұжырымы жалған, демек ол Чапаевскіден шыққан. Содан кейін Григорьевтің алғашқы тұжырымы жалған. Андреев Тольяттиден болғандықтан, Васильевтің алғашқы тұжырымы жалған, сондықтан Борисов Кинельден шыққан. Григорьев Жигулевскіден емес болғандықтан, ол Октябрьск қаласынан, ал Васильев Жигулевскіден қалады. Екінші мүмкін нұсқаны қарастырыңыз. Андреевтің екінші тұжырымы дұрыс болсын, содан кейін Григорьев Жигулевскіден келді. Сонымен, Данилов Чапаевскіден емес, Андреев Тольяттиден келген жоқ. Содан кейін Борисовтың алғашқы тұжырымы жалған (Григорьев Жигулевскіде тұрады), сондықтан Борисов Октябрьскіден келді. Сондықтан Андреев Октябрьск қаласынан емес, Данилов Чапаевскіден шыққан. Қарама-қайшылық болды: Данилов Чапаевскіден және Чапаевскіден емес. Сонымен, екінші нұсқа мүмкін емес. Жауабы бар. Андреев-Тольяттиден, Борисов – Кинельден, Васильев – Жигулевскіден, Григорьев – Октябрьскіден, Данилов – Чапаевскіден. Задача 2. Решаем с помощью таблиц. При использовании этого способа условия, которые содержит задача, и результаты рассуждений фиксируются с помощью специально составленных таблиц. Из четырех офицеров – Александрова, Борисова, Васильева и Григорьева – два лейтенанта, один капитан и один майор. Александров и один из лейтенантов – танкисты, Борисов и капитан - артиллеристы, Александров младше по званию, чем Васильев. Определите род войск и воинское звание каждого из них. Есеп 2. Біз кестелерді қолдана отырып шешеміз. Бұл әдісті қолданған кезде тапсырмадан тұратын шарттар мен ойлау нәтижелері арнайы жасалған кестелердің көмегімен жазылады. Төрт офицердің ішінде – Александров, Борисов, Васильев және Григорьев – екі лейтенант, бір капитан және бір майор. Александров және лейтенанттардың бірі – танкистер, Борисов және артиллериялық капитан, Александров Васильевке қарағанда кіші. Әскер түрін және олардың әрқайсысының әскери атағын анықтаңыз. Решение. Составим три таблицы и отразим в них условия задачи, заполнив соответствующие клетки цифрами 1 и 0 в зависимости от того, ложно или истинно соответствующее высказывание. Шешімі. Біз үш кесте құрамыз және онда есептің шарттарын көрсетіп, тиісті ұяшықтарды жалған немесе шынайы сәйкес мәлімдемеге байланысты 1 және 0 сандарымен толтырамыз.
Используя данные задачи, поставим 1 на пересечении Борисов – артиллерист, Александров – танкист, лейтенант – танкист, капитан – артиллерист. Тогда Борисов – не танкист и не капитан. Капитан не танкист. Александров – не артиллерист и не капитан. Тогда получим: Осы тапсырмаларды қолдана отырып, біз Борисов – артиллерист, Александров – танкист, лейтенант – танкист, капитан – артиллеристің қиылысына 1 қоямыз. Содан кейін Борисов танкист немесе капитан емес. Капитан танкист емес. Александров артиллерияшы да, капитан да емес. Сонда біз аламыз:
Александров не капитан и не майор (так как младше по званию, чем Васильев), значит он лейтенант. Получается, что оба лейтенанта танкисты, а Борисов – артиллерист, значит он не лейтенант. Так как Борисов не лейтенант и не капитан, то он майор. Тогда Васильев – капитан, поэтому он – артиллерист. Григорьев, значит, лейтенант и танкист. В результате постепенного заполнения получаем следующие таблицы: Александров капитан да, майор да емес (өйткені ол Васильевтен кіші), сондықтан ол лейтенант. Екі лейтенант танкист екендігі белгілі болды, ал Борисов артиллериялық, сондықтан ол лейтенант емес. Борисов лейтенант немесе капитан емес болғандықтан, ол майор. Содан кейін Васильев капитан, сондықтан ол артиллерияшы. Григорьев, демек, лейтенант және танкер. Біртіндеп толтыру нәтижесінде біз келесі кестелерді аламыз:
Ответ: Васильев и Борисов - капитан и майор артиллерии, Александров и Григорьев – лейтенанты танковых войск. Жауап: Васильев пен Борисов-артиллерия капитаны және майоры, Александров пен Григорьев – танк әскерлерінің лейтенанттары. Задачи на принцип Дирихле. Принцип Дирихле выражает соотношение между двумя множествами. Рассмотрим его применение на нашей задаче. Дирихле принципі бойынша есептер. Дирихле принципі екі жиынның арақатынасын білдіреді. Оны біздің тапсырмада қолдануды қарастырамыз. Есеп 3. Он маркетолог 35 тауардың тұтынушылық қасиеттеріне талдау жасады. Олардың арасында бір, екі немесе үш өнімге талдау жасаған бір маркетолог болғандығы белгілі. Олардың арасында кемінде бес өнімге талдау жасаған кем дегенде бір маркетолог бар екенін дәлелдеңіз. Дәлелдеме. Үш маркетолог бірге 6 (1+2+3), қалған 29 тауарға талдауды 7 маркетолог жүргізді. "Қояндар" үшін тауарларды қабылдап, "жасушалар" үшін маркетологтар, бізде 29 = 4*7 + 1. Содан кейін, Дирихлеттің жалпыланған принципіне сәйкес, кем дегенде бес өнімге талдау жасаған бір маркетолог бар. Ескерту. Мәселені қайшылықты әдісті қолдану арқылы шешуге болады Задача 3. Десять маркетологов провели анализ потребительских свойств 35 товаров. Известно, что среди них было по одному маркетологу, которые провели анализ одного, двух или трех товаров. Докажите, что среди них найдется хотя бы один маркетолог, который провел анализ не менее пяти товаров. Доказательство. Так как трое маркетологов вместе провели анализ 6 (1+2+3) товаров, то анализ оставшихся 29 товаров провели 7 маркетологов. Приняв товары за «зайцев», а маркетологов за «клетки», имеем 29 = 4*7 + 1. Тогда, по обобщенному принципу Дирихле, найдется как минимум один маркетолог, который провел анализ не менее пяти товаров. Замечание. Задачу можно решить, применяя метод от противного. Қорытынды Осы жұмыста мен болашықта экономикалық мамандыққа бағдарланған болғандықтан мен үшін қызықты және өзекті тақырып қарастырылады. Жұмыс барысында көптеген теориялық көздер зерттелді, бұл тақырып бойынша білімді жүйелеуге ықпал етті. Берілген есептер мен олардың шешімдері математика пәнінен емтихан тапсыратын оқушылар үшін маңызды. Заключение В настоящей работе рассмотрена тема, интересная и актуальная для меня, как будущей выпускницы, ориентирующейся на экономическую профессию. При работе над работой было изучено большое количество теоретических источников, что способствовало систематизации знаний по этой теме. Приведенные задачи и их решения имеют актуальность для школьников, которые будут сдавать ЕГЭ по математике. Результаты эксперимента:  Вывод: Использование элементов математической логики позволяет учащимся гораздо быстрее найти нужные решения задач. Класс логических задач является самым разнообразным, как по типам, так и по методам решения. Освоение основных элементов математической логики пригодится в будущей профессиональной деятельности как в сфере экономики, так и в других сферах жизни общества. Қорытынды: * Математикалық логика элементтерін қолдану студенттерге қажетті есептерді тезірек табуға мүмкіндік береді. * Логикалық есептер класы түрлері бойынша да, шешу әдістері бойынша да алуан түрлі болып табылады. * Математикалық логиканың негізгі элементтерін игеру экономика саласында да, қоғам өмірінің басқа салаларында да болашақ кәсіби қызметте пайдалы болады. Литература 1. Виленкин Н.Я., В.В. Фирсов и др. Факультативный курс. Избранные вопросы математики. М.: Просвещение 1998 – 192 с. 2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов / В.И. Игошин. – 3-е изд., стер. – М.: Издательский центр «Академия», 2007. – 304 с. 3. Математическая логика // Википедия / http://ru.wikipedia.org 4. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. 2-е изд. – М.: Физматлит, 2002. – 128 с. 5. Фарков А.В. Методы решения олимпиадных задач. 10-11 классы. – М.: ИЛЕКСА, 2011. – 110 с. (Серия «Математика: элективный курс»). |
В, ẠВ