Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Опубликуйте свой материал в официальном Печатном сборнике методических разработок проекта «Инфоурок»

(с присвоением ISBN)

Выберите любой материал на Вашем учительском сайте или загрузите новый

Оформите заявку на публикацию в сборник(займет не более 3 минут)

+

Получите свой экземпляр сборника и свидетельство о публикации в нем

Инфоурок / Математика / Рабочие программы / Программа элективного курса по математике "Элементы математической логики"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 24 мая.

Подать заявку на курс
  • Математика

Программа элективного курса по математике "Элементы математической логики"

библиотека
материалов

hello_html_70b75490.gifhello_html_m6c8d1a7e.gifhello_html_m6c8d1a7e.gifhello_html_484ce48d.gif


ПРОГРАММА ЭЛЕКТИВНОГО КУРСА

«Элементы математической логики»

Составлена на основе авторской программы Е.А.Семенко «Элементы математической логики», - Краснодар, 2004г.






Учитель: Коновалова Марина Викторовна

Класс: 9

Общее количество часов по плану: 17 часов

Количество часов в неделю: 1 час













Пояснительная записка

Программа элективного курса по математике «Элементы математической логики» составлена на основе авторской программы Е.А.Семенко «Элементы математической логики», - Краснодар, 2004г, и рассчитана на 17 часов для учащихся 9 классов в рамках предпрофильной подготовки.

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


Цели курса:

  • формирование основных понятий математической логики: высказываний, операции над высказываниями, логических законов и др.

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

  • создать возможность для учащихся реализовать свой интерес к математике.

Задачи курса:

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

  • научить решать задачи с помощью метода математической индукции

  • научить решению логических задач с использование математической логики,

  • сформировать умение построения логических схем из базовых логических элементов.

  • сформировать умение использовать логические связки и кванторы

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

Требования к уровню подготовки учащихся 9 класса

В результате изучения курса учащиеся смогут:

  • Выбрать и применить более рациональный способ решения той или иной логической задачи;

  • Использовать свои знания при решении задач по теории множеств и математической логике;

  • научиться проводить логические операции с несложными высказываниями и высказывательными формами;

  • Сравнивать множества истинности высказываний;

  • Формулировать высказывания, обратные и противоположные данным;

  • Производить логические операции над понятиями;

  • Выполнять действия с множествами;

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

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









Содержание изучаемого курса


Тема 1. Введение. Занимательные логические задачи (1 часа)


Тема 2. Понятие. Определение.(1 час)

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

.

Тема 3. Высказывания или суждения.(2 часа)

Историческая справка: попытки создания исчислений для «вычисления истины» (Лейбниц, де Морган, Буль); высказывания: примеры высказываний, их значения истинности; Простые высказывания как основные понятия в математической логике и их свойства


Тема 4. Логические операции. Конъюнкция, дизъюнкция, импликация, отрицание.(3 часа)

.


Тема 5. Основные понятия теории множеств.(3 часа)

Основные операции над множествами ( объединение, пересечение, разность множеств). Дополнение подмножества. Формула включений и исключений для множества.


Тема 6. Использование индукции в математике ( 2 часа)

Что такое индукция? индукция при поиске математических закономерностей; примеры; индукция при поиске способа решения задачи или способа доказательства теоремы; примеры; использование предельного случая при поиске решения задачи,

сущность метода математической индукции. Принцип математической индукции;


Тема 7. Предикаты. Кванторы. Высказывательные формы, логические операции над ними.(2 часа)

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


Тема 8. Теоремы. Доказательства. ( 3 часа)

Виды теорем. Необходимость и достаточность условия. Основные принципы математических доказательств ( индукция, дедукция)

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

Учебно-тематический план

Наименование тем курса

Кол-во часов

1

Тема 1. Введение. Занимательные логические задачи.

1

2

Тема 2. Понятие. Определение.

1

3

Тема 3. Высказывания или суждения.

2

4

Тема 4. Логические операции. Конъюнкция, дизъюнкция, импликация, отрицание

3

5

Тема 5. Основные понятия теории множеств

3

6

Тема 6. Использование индукции в математике

2

7

Тема 7. Предикаты. Кванторы. Высказывательные формы, логические операции над ними.

2

8

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

3

Итого

17



















Литература

Список использованной литературы.


1. Сборник программ курсов по выбору. ККИДППО. Математика. Краснодар, 2004.

2. А.А.Ивин. Элементарная логика. М., 2009г

3. А.Д.Гетманова. Логические основы математики. 10-11 классы. Москва, 2005.

4. М.Б.Балк, Г.Д.Балк. Математика после уроков. Москва,2011 г.

5. Г.И.Саранцев. обучение математическим доказательствам. М., 2009.

6. В.А.Каймин и др. Основы информатики и вычислительной техники, 10-11, Москва,2007.

7. Л.М.Фридман. Учитесь учиться математике. Москва, 1995.

8. И.Л.Никольская. Математическая логика. Москва, 1991.

9. Рассуждая логически… Приложение к журналу Квант. Москва, 2008.

10. В.И.Курбатов. Логика в вопросах и ответах. 2011

11. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов / В.И. Игошин. – 3-е изд., стер. – М.: Издательский центр «Академия», 2007. – 304 с.

12. Математическая логика // Википедия / http:// wikipedia.org. ru

13. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. 2-е изд. – М.: Физматлит, 2007. – 128 с.

14. Фарков А.В. Методы решения олимпиадных задач. 10-11 классы. – М.: ИЛЕКСА, 2011. – 110 с. (Серия «Математика: элективный курс»).

Интернет –источники

http://www.mathege.ru

http://www.smekalka.pp.ru/

http://nsportal.ru/

www.MatBuro.ru/




Календарно-тематическое планирование



урока

Содержание ( разделы, темы)

Кол-во часов

Дата

План

Факт

1

Введение. Занимательные логические задачи.

1



2

Понятие. Определение

1



3

Высказывания или суждения.

2



4

Простые высказывания как основные понятия в математической логике и их свойства



5

Логические операции. Конъюнкция, дизъюнкция

3



6

Логические операции. Импликация, отрицание.



7

Решение задач с применением логических операций.



8

Основные понятия теории множеств.

3



9

Операции над множествами.



10

Решение задач с применением формулы включений и исключений.



11

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

2



12

Принцип математической индукции.



13

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

2



14

Высказывательные формы, логические операции над ними.



15

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

3



16

Принципы математических доказательств ( индукция, дедукция).



17

Решение задач с применением индукции, дедукции.




Итого:

17



Занимательные логические задачи

  1. Алекс говорит правду только один день в неделю. Какой это день, если известно следующее:
    1. Однажды он сказал - "Я лгу по понедельникам и вторникам"
    2. На следующий день он сказал - "Сегодня или четверг или суббота или воскресенье"
    3. Еще на следующий день он сказал - "Я лгу по средам и пятницам"

Ответ: Алекс говорит правду по вторникам. А первое высказывание было сделано в воскресенье

Начало формы

Конец формы

  1. На предприятии есть три цеха – A, B, C, договорившиеся о порядке утверждения проектов, а именно:
    1. Если цех B не участвует в утверждении проекта, то в этом утверждении не участвует и цех A.
    2. Если цех B принимает участие в утверждении проекта, то в нем принимают участие цехи A и C.
    Обязан ли при этих условиях цех C принимать участие в утверждении проекта, когда в утверждении принимает участие цех A?

Ответ: Первое утверждение можно переформулировать следующим образом: если в утверждении участвует цех A, то цех B также должен участвовать. Тогда, согласно второму утверждению, цех C должен принимать участие в утверждении проекта.



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

Ответ: Второй – абориген, третий – пришелец.

  1. Петя заметил, что у всех его 25 одноклассников различное число друзей в этом классе.
    Сколько друзей у Пети? (Укажите все решения.)

Ответ: 12 или 13. Всего в классе 26 человек, число друзей у каждого может быть от 0 до 25, т. е. всего 26 вариантов, но варианты, когда у кого-то 25 друзей, а у другого — ни одного, одновременно не выполнимы, тем самым, всего вариантов одновременно может быть не больше 25. По условию задачи, у Петиных одноклассников реализованы все 25 вариантов.
Пусть у кого-то 25 друзей. Исключим его из дальнейшего рассмотрения. Тогда получим ситуацию, когда у Пети 25 одноклассников, у всех по-прежнему разное число друзей в классе, причём нет человека, который дружит со всеми (он дружил бы и с исключённым, т. е. со всеми в первоначальном классе, что не соответствует условию задачи). Значит, найдётся человек, у которого нет друзей. Его можно исключить из дальнейшего рассмотрения. Получим ситуацию, когда у Пети 24 одноклассника, у всех разное число друзей, причём нет человека, который не дружит ни с кем.
Так, исключая по очереди тех, кто дружит со всеми (в оставшемся классе) или ни с кем, мы придём к тому, что у Пети останется один одноклассник, который с Петей дружит. При этом среди всех, которые ушли из школы, у Пети было 12 друзей, всего, стало быть у него в этом классе было 13 друзей. Случай, когда первоначально в классе есть человек, у которого нет друзей, рассматривается аналогично, и в этом случае у Пети 12 друзей.

5. Профессор загадал два последовательных натуральных числа в диапазоне от 1 до 10. Студент А знает одно число, студент Б знает другое число. Каждый студент знает, что числа соседние. Между этими студентами состоялся следующий диалог:
А: Я не знаю твоего числа
Б: Я тоже не знаю твоего числа
А: Теперь я знаю
Какие это были числа? Вариантов решения несколько

Ответ: 2-3, 3-4, 9-8, 8-7
Во-первых, среди указанных чисел не может быть 1 или 10, иначе второе число стало бы известно сразу.
Во-вторых, информация о том, что студент Б не знает первого числа, оказалась ключевой для студента А.
Предположим, что студент А знает число "2". Тогда у студента Б должно быть "1" или "3". Но "1" быть не может, поэтому первый вариант решения - пара чисел 2-3.
Предположим, что студент А знает число "3". Тогда у Б должно быть "2" или "4". Но если бы у студента Б было число "2", то он отгадал бы число первого студента. Раз он этого не смог сделать, значит, у него было число "4". Вторая пара чисел - 3-4.
Далее, пусть первому студенту известно число "4". У второго, соответственно, "3" или "5". В этой ситуации первый студент после диалога не может узнать второе число, т.е. пары 4-3 и 4-5 не являются решением.
Применяя аналогичные рассуждения, получаем еще два ответа - 9-8 и 8-7

Начало формы

Конец формы

6. Перед Вами пять коробочек: белая, черная, красная, синяя и зелёная. Также есть по два шарика для каждого из цветов. В каждой коробочке лежит по два шарика, причём цвета коробочки и шариков могут и не совпадать. Также известно, что:
1. Ни один шарик не лежит в коробочке того же цвета, что и он сам;
2. В красной коробочке нет синих шариков;
3. В коробочке нейтрального цвета (то есть белого или чёрного) лежит один красный и один зелёный шарик;
4. В чёрной коробочке лежат шарики холодных тонов (зелёный и синий цвета);
5. В одной из коробочек лежат один белый и один синий шарик;
6. В синей коробочки находится один чёрный шарик.
Какого цвета шарики лежат в каждой коробочке? 

Ответ: Белая коpобочка - кpасный и зеленый;
чеpная коpобочка - зеленый и синий;
зеленая коpобочка - белый и синий;
синяя коpобочка-  чеpный и кpасный;
кpасная коpобочка - белый и чеpный.

7. - Доброе утро, Ватсон! Я вижу, вы уже читаете утреннюю "Таймс"? Что пишут интересного?
- Есть кое-что. Вот например: На кольцевой автостраде произошло довольно странное ДТП. Оба водителя доставлены в больницу в тяжелом состоянии. Интересно, что их машины не получили при этом никаких повреждений.
- Ну это элементарно, Ватсон. Есть еще что-нибудь?
- Холмс, для Вас все элементарно. А как на счет этого? Шахматисты - убийцы. В квартире на журнальном столике на трех ножках стояла шахматная доска и двое играли в шахматы, а третий смотрел. На минуту погас свет, а когда включился, третий лежал на полу с ножом в горле. Прибыла полиция. Первый сказал, что когда погас свет, он напряженно обдумывал очередной ход и ничего не слышал. Второй сказал, что когда погас свет, он нагнулся подложить бумажку под ножку стола, - он качался и мешал сосредоточиться - кровь прилила к голове, и он тоже ничего не слышал. Кто же
из них убил третьего?
- Ватсон, это еще проще. Даже миссис Хадсон скажет Вам, кто убийца. Нет ли чего более интересного?
- Нет. Больше ничего нет, разве только самоубийство Джеральда Батчера, лондонский банкир, который был найден мертвым в своем кабинете.
- Ну ка, ну ка...
- Он лежал на столе, в руке пистолет, висок прострелен. Шторы были опущены, горела настольная лампа, тут же стоял магнитофон. Инспектор из Скотланд-Ярда нажал на кнопку воспроизведения и услышал последнее послание Батчера: - "Я не могу ждать банкротства, это - конец..." - а потом послышался звук выстрела. Под головой банкира было залитое кровью письмо из Налоговой полиции с извещением о проверке.
- Ну вот, Ватсон, а Вы говорите, что нет ничего интересного. А может мы займемся поисками убийцы банкира....
- Холмс, это же самоубийство...
- Это убийство Ватсон, убийство, и мы с вами займемся этим убийством...

Ну а Вы готовы проверить свои дедуктивные способности?
Тогда:
1. Опишите ДТП.
2. Укажите, кто из шахматистов убийца.
3. И почему самоубийство Джеральда Батчера на самом деле - это убийство. 

Ответ: 

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

.

8 .В семье трое детей: 2 мальчика и девочка. Их имена начинаются с букв А,В,Г. Среди А и В есть начальная буква имени одного мальчика, а среди В и Г – начальная буква имени другого мальчика. С какой буквы начинается имя девочки?

9.Четыре брата Юра, Петя, Вова, Коля учатся в 1,2,3,4 классах. Петя- отличник, младшие братья стараются брать с него пример. Вова учится в 4 классе. Юра помогает решать задачи брату. Кто в каком класе учится?

10.Три поросенка построили три домика из соломы, из прутьев, из камней. Каждый из них получил один домик: Ниф-Ниф – не из камней, и не из прутьев; Нуф-Нуф не из камней. Какой домик достался Наф-Нафу.

11.На улице, став в кружок, беседуют четыре девочки – Аня, Валя, Галя и Надя. Девочка в зелёном платье (не Аня и не Валя) стоит между девочкой в голубом платье и Надей. Девочка в белом платье стоит между девочкой в розовом и Валей. Какое платье носит каждая из девочек?

12. Ваня, Петя, Саша и Коля носят фамилии, начинающиеся на буквы В, П, С и К. Известно, что

Ваня и С. – отличники,

Петя и В. – троечники,

В. ростом выше П.,

Коля ростом ниже П.,

Саша и Петя имеют одинаковый рост.

На какую букву начинается фамилия каждого мальчика?

13. Четыре ученицы: Мария, Нина, Ольга и Полина – участвовали в лыжных соревнованиях и

заняли четыре первых места. На вопрос, кто какое место занял. Они дали три разных ответа:

- Ольга заняла первое место, Нина – второе.

- Ольга – второе, Поля- третье.

- Мария- второе, Поля- четвёртое.

Отвечавшие при этом признали, что одна часть каждого ответа верна, а другая - неверна. Какое место заняла каждая из учениц?

 

Ответы

8.Имя девочки начинается с буквы В

9.Вова – 4кл, Петя – 3кл, Юра – 2 кл., Коля – 1 кл.

10.Наф-наф из камней, Ниф-Ниф из соломы, Нуф- Нуф из прутьев

11.Аня в белом, Валя в голубом, Галя в зеленом, Надя в розовом

12.Ваня П., Петя К., Саша В., Коля С.

13.Оля -1, Мария -2, Поля – 3, Нина -4

 



Понятия . Определения в математике.

Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания.

Логика – это наука о формах и способах мышления.

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

Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются понятие, высказывание, умозаключение.

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

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

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

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

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

Определение – это предложение, которое вводит новое понятие.

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

Объем одного понятия может содержаться в объеме другого понятия. Так, например, множество все квадратов – это часть множества всех ромбов. Наглядно можно представить картину так.

ромбы

квадраты

Условно изобразим множество всех ромбов в

виде некоторого круга и множество всех

квадратов – тоже в виде круга; тогда второй

круг должен оказаться внутри первого.









Если объем одного понятия входит в объем другого понятия, то первое называется видом (или видовым понятием) второго, а второе – родом (родовым понятием) для первого. так, например, квадрат – это вид ромба; ромб – это род для квадрата (квадраты принадлежат роду ромбов).

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

Определяемое понятиерод + видовое отличие.

Например, определяя понятие «квадрат», мы указываем род («ромб») и видовое отличие («все его углы – прямые»).

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

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

1. Нельзя определять новое понятие через неизвестные ранее понятия. Еще хуже, если определение одного понятия дано через другое, а определение другого – через первое.

Например, если некто определил «угловой градус» как 1/90 часть прямого угла и затем на вопрос: «Что такое прямой угол?» - ответил: «Прямой угол – это такой угол, который содержит 90 угловых градусов», то он допустил логическую ошибку.

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

Имеется еще несколько пожеланий, которым рекомендуется следовать при построении определений.

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

Например, если начать определение так: «Квадрат – это фигура…»(и т.д.), то, по всей вероятности, определение будет плохим: слишком много надо потребовать от фигуры, чтобы она оказалась квадратом, и очень легко при этом что-то упустить. Значительно меньше шансов на ошибку, если начать так: «Квадрат – это прямоугольник…» (и т.д.).

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

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

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

Равносильные определения. Сравните два предложения: «Квадрат – это равносторонний прямоугольник»; «Квадрат – это равноугольный ромб».

Любое из этих предложений можно рассматривать как определение квадрата: ведь в каждом из них указан род и видовое отличие.

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

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

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

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

Тренировочные упражнения.

1.Выясните, правильны ли следующие определения:

а) Луч – это прямая, ограниченная с одной стороны.

б) Окружность – это фигура, все точки которой находятся на заданном расстоянии от заданной точки.

в) Биссектрисой треугольника называется прямая, делящая угол треугольника пополам.

г) Параллельными прямыми называются такие прямые, которые не пересекаются.

2. Фигура «Крест» строится следующим образом: на двух пересекающихся прямых откладываются от точки пересечения по разные стороны от нее на каждой из этих прямых равные отрезки. Сформулируйте определение фигуры «Крест».

3. В приведенных ниже определениях выделите название определяемого понятия, родовое понятие и видовые признаки:

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

б) Значение переменной, которое обращает уравнение в истинное равенство, называется корнем уравнения.

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

г) Отрезок, соединяющий середины боковых сторон трапеции, называется ее средней линией.

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

а ) б) A,B

C

D

E

A

B

C


Ответы: а) Неправильно указан род, используется понятие, не введенное ранее. б) Неполностью указано видовое отличие(под данное определение подойдет, например, полуокружность). в) не прямая, а отрезок; г) пропущена фраза «лежащие в одной плоскости».2.Крестом называется фигура, состоящая из двух пересекающихся пополам отрезков.4.

а ) б) Действ.число

рацион. число

целое число

нат.число

прямоуголь-

ник

квадрат

ромб


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

1. Объяснение слова. Если говорите, что «геометрия – это землемерие», то вы только разъясняете смысл слова, только даете дословный перевод этого слова с греческого. На самом деле геометрия не есть землемерие (и, наверное, никогда не была только землемерием).

2. Указание («вот»). Например: «Что такое куб?». «Вот это куб, и это куб, а это не куб».

3. Сравнение и противопоставление. Приведем несколько примеров: «Математика – это гимнастика ума, это поэзия мысли». «Логика – это грамматика мышления». «Физика – это драма, драма идей» (Эйнштейн). «Эллипс – это сплюснутый круг».

4. Характеристика. Отмечаются лишь некоторые наиболее важные свойства объекта, но не дается полный набор существенных признаков этого объекта, так, чтобы из них вытекали уже все остальные признаки. Например, «Математика – это одна из основ современной техники».

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


Суждение(высказывание).Алгебра высказываний.

Еще в XVII столетии знаменитый немецкий математик Лейбниц мечтал о том, чтобы создать вычислительный аппарат, который позволил бы «вычислить ответы» к различным логическим задачам.

Такое исчисление было создано, и в 1854 году было опубликовано в книге английского математика Джорджа Буля «Исследование законов мысли». Оно получило название «алгебры логики» или «исчисления высказываний». И этот математический аппарат действительно позволяет в ряде случаев «вычислить истину»!

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

Высказывания могут быть выражены с помощью не только естественных языков, но и формальных. Например, высказывание на естественном языке имеет вид «Дважды два равно четырем», а на формальном, математическом языке оно записывается в виде: «2 2 = 4».

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

Каждое высказывание будем обозначать одной буквой: А, В, С и т.п. Для алгебры логики важно только истинно ли данное высказывание, или ложно. В зависимости от этого говорят, что значение истинности данного высказывания А равно единице или, соответственно, равно нулю.

В первом случае пишут А = 1, во втором – А = 0. Например, если высказывание А означает: «равносторонний треугольник имеет равные углы», а высказывание В означает: «рост человека составляет 40 м», то можно написать: А = 1, В = 0.

Может оказаться, что два высказывания А и В одновременно истинны или одновременно ложны; тогда их назовем равносильными (эквивалентными) и условимся писать А = В. Например, высказывания А = «Этот треугольник равносторонний», В = «Этот треугольник равноугольный» будут равносильными, так что А = В.

Располагая каким-то высказыванием А, можно построить новое высказывание – отрицание высказывания А (оно обозначается так: Ā). Отрицанием высказывания А называется такое высказывание Ā, которое ложно, если А истинно, и истинно, если А ложно. Короче можно то же самое условие задать с помощью следующей таблицы.

А

Ā

1

0

0

1

Эта таблица называется таблицей истинности для отрицания. Можно также сказать, что отрицание Ā (точнее говоря, его значение истинности) – это некоторая функция от высказывания А (опять-таки имеется в виду значение истинности этого высказывания), причем эта функция задается приведенной выше таблицей.

Располагая двумя (или несколькими) высказываниями А и В, можно строить новые, более сложные высказывания, объединяя данные высказывания или их отрицания словами: «и», «или», «если…, то», «либо…, либо…» и др. Например, пусть имеются высказывания : А = «днем я приготовлю уроки», В = «Вечером я пойду в кино». Из них можно образовать новые, составные высказывания: «Днем я приготовлю уроки, и вечером я пойду в кино»; «Если днем я приготовлю уроки, то вечером я пойду в кино»; «Либо днем я приготовлю уроки, либо вечером я не пойду в кино»; и т.д.

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

Рассмотрим различные возможности образования составных высказываний из двух исходных высказываний А и В.

1. Конъюнкцией двух высказываний А и В называется такое высказывание, которое истинно тогда, и только тогда, когда оба высказывания истинны. Записывается так: А В, читается «А и В».

Значение истинности конъюнкции можно задать через значения истинности составляющих ее высказываний с помощью такой таблицы:

А

В

А В

1

1

1

1

0

0

0

1

0

0

0

0

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

2. Дизъюнкцией двух высказываний А и В называется такое высказывание, которое истинно тогда, и только тогда, когда хотя бы одно из высказываний А, В истинно. Записывается так: А В, читается «А или В».

В соответствии с этим определением значения истинности дизъюнкции высказываний А, В могут быть заданы с помощью такой таблицы:


А

В

АВ

1

1

1

1

0

1

0

1

1

0

0

0

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

По таблице истинности легко определить истинность составного высказывания, образованного с помощью дизъюнкции. Рассмотрим, например, составное высказывание «22 = 4 или 33 = 10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что дизъюнкция АВ принимает значение 1, то есть данное составное высказывание истинно.

3. Импликацией двух высказываний А и В называется такое высказывание, значение истинности которого определяется следующей таблицей:

А

В

АВ

1

1

1

1

0

0

0

1

1

0

0

1

Записывается : АВ; читается «А влечет за собой В», «если А, то В».

Вот несколько примеров импликаций. Пусть истинно следующее предложение: А = «Треугольник равносторонний». Тогда, как известно, истинно высказывание В = «Треугольник равноугольный». Поэтому импликация «Если треугольник АВС равносторонний, то он равноугольный» истинна. А импликация «Если треугольник АВС равносторонний, то он прямоугольный» ложна.

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

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

Эквивалентность (двойная импликация): «АВ» («А и В одновременно истинны или ложны»):

А

В

АВ

1

1

1

1

0

0

0

1

0

0

0

1

Операция Шеффера «А/В» («А и В несовместимы», то есть А и В не являются одновременно истинными):

А

В

А/В

1

1

0

1

0

1

0

1

1

0

0

1

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

Тренировочные упражнения.

1. Пусть А = «Валерик читает книгу», а В = «Саша собирает ягоды». Прочтите словами следующие высказывания:

hello_html_m199311aa.gif

2. Пусть А = «Рука болит», В = «Голова кружится». Запишите с помощью символов алгебры логики следующие высказывания:

«Рука болит, и голова кружится»;

«Рука болит, но голова не кружится»;

«Неправда, что рука не болит и голова не кружится».

3. Сформулируйте отрицание следующего высказывания: данный треугольник АВС является прямоугольным и равнобедренным.

4. Пусть А = «Прошел дождь», В = «На улице сыро». Истинны ли следующие высказывания:

а) АВ;

б) ВА (обратное);

в) hello_html_m114e77ba.gif (противоположное);

г) hello_html_383eafbd.gif (противоположное обратному)?

5. С помощью таблиц истинности докажите следующие формулы:

hello_html_m738122b2.gif

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

Ответы: 1.Валерик не читает книгу или Саша собирает ягоды. Неверно, что Валерик читает книгу или Саша собирает ягоды (Валерик не читает книгу и Саша не собирает ягоды. Неправда, что Валерик не читает книгу и Саша не собирает ягоды (Валерик читает книгу или Саша собирает ягоды). 2. hello_html_68055637.gif 3. Данный треугольник не является прямоугольным или не является равнобедренным. 4. а)да, б),в)нет, г)да.

Логические законы.

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

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

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


А=А

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

Второй закон логики, также впервые высказанный Аристотелем, -

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

Не могут быть одновременно быть истинны утверждение и его отрицание.


А Ā = 0


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

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

Истинно либо суждение, либо его отрицание.


А Ā = 1


Пример рассуждений: «Этот треугольник правильный либо неправильный». В этой категоричной формулировке закон не допускает ничего третьего.

Закон двойного отрицания.

Отрицать отрицание какого-либо высказывания – то же, что утверждать это высказывание.

hello_html_m54737f64.gif


Например, высказывание «Неверно, что 2х24» означает то же, что и «2х2=4»; «Если неправда, что Коля этого не делал, то это сделал Коля».

Закон достаточных оснований.

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

Законы де Моргана. (отрицание конъюнкции равносильно дизъюнкции отрицаний; отрицание дизъюнкции равносильно конъюнкции отрицаний).

hello_html_783554b5.gif

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

Закон коммутативности.

коммутативность сложения коммутативность умножения

АВ=ВА АВ=ВА


Закон ассоциативности.

ассоциативность сложения ассоциативность умножения

(АВ) С= А(ВС) (АВ)С = А(ВС)


Закон дистрибутивности

дистрибутивность сложения дистрибутивность умножения

относительно умножения относительно сложения

(АВ)(А С)= А( ВС) (АВ)(АС)= А(ВС)

Закон идемпотентности (от латинских слов idem – тот же самый и potens – сильный; дословно – равносильный):

для логического сложения для логического умножения

АА=А АА=А

Законы исключения констант

для логического сложения для логического умножения

А1= 1; А0=А А1; А0=0

Закон поглощения

для логического сложения для логического умножения

А(АВ)=А А(АВ)=А

Закон исключения (склеивания)

для логического сложения для логического умножения

(АВ)(ĀВ)=В (АВ)(ĀВ)=В

Закон контрапозиции (правило перевертывания)

В)=(ВА)





Пусть А = «дождь идет», В = «зонт открыт». Рассмотрим следующие 8 утверждений:Под дождемПод зонтомПод зонтом










hello_html_24b7cefd.gifhello_html_m6025b467.gif

Солнце без зонтаСолнце и зонт












hello_html_m300f9627.gifhello_html_m114e77ba.gif


1. hello_html_24b7cefd.gif 5. hello_html_mdc716fa.gif

2. hello_html_m300f9627.gif 6. hello_html_197f4e22.gif

3. hello_html_m6025b467.gif 7. hello_html_49556c62.gif

4. hello_html_m114e77ba.gif 8. hello_html_383eafbd.gif


А

В

hello_html_m24eb6df0.gif

hello_html_1b4c48a.gif

hello_html_24b7cefd.gif

hello_html_m300f9627.gif

hello_html_m6025b467.gif

hello_html_m114e77ba.gif

hello_html_mdc716fa.gif

hello_html_197f4e22.gif

hello_html_49556c62.gif

hello_html_383eafbd.gif

1

1

0

0

1

1

0

1

1

1

0

1

1

0

0

1

0

1

1

1

1

1

1

0

0

1

1

0

1

1

1

0

0

1

1

1

0

0

1

1

1

0

1

1

1

0

1

1

Из таблицы истинности видно, что hello_html_79004855.gif (высказывание равносильно обратно-противоположному), а hello_html_mdc716fa.gif=hello_html_m114e77ba.gif ( обратное высказывание равносильно противоположному).

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

Тренировочные упражнения.

1. Как объяснить, что загадка «Хожу на голове, хотя и на ногах, хожу я без сапог, хотя и в сапогах» имеет решение-отгадку (гвоздь в подошве сапога)? Не нарушен ли здесь закон противоречия?

2. Укажите примеры двойного отрицания для утверждений:

а) «Сегодня был дождь»;

б) «х=0» или «у=0»;

в) «5 не делится на 2 и на 3».

3. Что утверждается в следующих предложениях: а) «Неверно, что квадрат – это не ромб»; б) hello_html_1e8425f1.gif (Р – множество простых чисел)?

4. Сформулируйте предложения, которые, согласно законам де Моргана, выражают то же, что и следующие предложения: а) «Неверно, что треугольник АВС – прямоугольный и равнобедренный»; б) «Неверно, что число 9 – четное или простое»; в) «Неверно, что каждое из чисел m и четно»; г) «Неверно, что хотя бы одно из чисел r и s – простое»; д) hello_html_67fe240.gif е) «Я не высплюсь или опоздаю».

5. Сформулируйте предложения, противоположные данным, применив законы де Моргана: а) «Если четырехугольник – ромб, то его диагонали взаимно перпендикулярны и делят его углы пополам»; б) «Если число делится на 2 и на 5, то оно делится на 10»; в) «Если натуральное число оканчивается нулем или пятью, то оно делится на 5»; г) «Если a*b=0, то a=0 или b=0»; д) «Если a2+ b2=0, то a=0 и b=0»; е) «Если А и В, то С или D».

6. Сформулируйте предложения, которые, согласно законам дистрибутивности, равносильны следующим: а) «Он знает математику и немецкий или французский язык»; б) «Я буду завтракать и обедать или завтракать и ужинать»; в) «Число n делится на 2 или на 3 и делится на 2 или на 5»; г) «Я посмотрю фильм и «Вести» или фильм и «Итоги».

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

8. Упростить логические выражения:

а) А(ĀВ);

б) А(ĀВ);

в) hello_html_m35cfc1bc.gif

9. Какие из следующих предложений равносильны, согласно закону контрапозиции: а) «Если х – сепулька, то х – обитатель Интеропии»; б) «Если х – не сепулька, то х – не обитает в Интеропии»; в) «Если х – житель Интеропии, то х – сепулька»; г) «Если х – сепулька, то х не обитает в Интеропии» ?

(Ответы: 1. Предложения «Хожу на голове» и «Хожу на ногах», а также предложения «Хожу без сапог» и «Хожу в сапогах» в данном случае не противоречат друг другу, так как относятся к разным объектам. 2. а) Это неправда, что сегодня не было дождя; б)Это неверно, что х0 и у0, в) Это неверно, что 5 делится на 2 или на 3; 3. б) «2 – простое число». 4. а) «Треугольник АВС – не прямоугольный или не равнобедренный»; б) «Число 9 – нечетное и не простое»; в) «Число m нечетно или число n нечетно»; г) «Число r – не простое и число s не простое»; д) «Неверно, что hello_html_m1ca5e4ec.gif , е) «Неверно, что я высплюсь и не опоздаю». 5. а) «Если четырехугольник – не ромб, то его диагонали не перпендикулярны или не делят его углы пополам»; е) «Если не А или не В, то не С и не D». 6. а) «Он знает математику и немецкий язык или математику и французский язык»; в) «Число n делится на 2 или одновременно на 3 и на 5». 8. а) АВ; б) АВ; в) hello_html_4ea07280.gif9. б) и в

Задача 1.

Решаем методом «здравых рассуждений».

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

Андреев: «Я приехал из Тольятти, а Григорьев живет в Жигулевске».

Борисов: «В Жигулевске живет Васильев. Я же прибыл из Октябрьска».

Васильев: «Я – из Тольятти, а Борисов – из Кинеля».

Григорьев: «Я приехал из Жигулевска, а Данилов из Чапаевска».

Данилов: «Да, я действительно из Чапаевска, Андреев же живет в Октябрьске».

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

Решение.

Рассмотрим первый возможный вариант. Пусть первое утверждение Андреева верное, то есть он из Тольятти. Тогда Григорьев живет не в Жигулевске. Поэтому второе утверждение Данилова – ложное, значит, он из Чапаевска. Тогда первое утверждение Григорьева – ложно.

Так как Андреев из Тольятти, то первое утверждение Васильева ложно, поэтому Борисов – из Кинеля. Так как Григорьев не из Жигулевска, то остается, что он из Октябрьска, а Васильев – из Жигулевска.

Рассмотрим второй возможный вариант. Пусть у Андреева второе утверждение – правильное, тогда Григорьев приехал из Жигулевска. Значит, Данилов приехал не из Чапаевска, а Андреев не из Тольятти. Тогда у Борисова первое утверждение ложное (в Жигулевске живет Григорьев), следовательно, Борисов прибыл из Октябрьска. Поэтому Андреев не из Октябрьска и получается, что Данилов – из Чапаевска. Получили противоречие: Данилов из Чапаевска и не из Чапаевска. Значит, второй вариант невозможен.

Ответ. Андреев – из Тольятти, Борисов – из Кинеля, Васильев – из Жигулевска, Григорьев – из Октябрьска, Данилов – из Чапаевска.


Задача 2.

Решаем с помощью таблиц.

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

Из четырех офицеров – Александрова, Борисова, Васильева и Григорьева – два лейтенанта, один капитан и один майор. Александров и один из лейтенантов – танкисты, Борисов и капитан - артиллеристы, Александров младше по званию, чем Васильев. Определите род войск и воинское звание каждого из них.

Решение.

Составим три таблицы и отразим в них условия задачи, заполнив соответствующие клетки цифрами 1 и 0 в зависимости от того, ложно или истинно соответствующее высказывание.


Фамилия Звание


Александров


Борисов


Васильев


Григорьев

Лейтенант





Лейтенант





Капитан





Майор






Фамилия

Род войск


Александров


Борисов


Васильев


Григорьев

Танкист





Артиллерист






Звание

Род войск


Лейтенант


Лейтенант


Капитан


Майор

Танкист





Артиллерист






Используя данные задачи, поставим 1 на пересечении Борисов – артиллерист, Александров – танкист, лейтенант – танкист, капитан – артиллерист. Тогда Борисов – не танкист и не капитан. Капитан не танкист. Александров – не артиллерист и не капитан. Поставим соответственно 0 на пересечении данных слов в таблицах. Тогда получим:

Фамилия

Звание


Александров


Борисов


Васильев


Григорьев

Лейтенант





Лейтенант





Капитан

0

0



Майор






Фамилия

Род войск


Александров


Борисов


Васильев


Григорьев

Танкист

1

0



Артиллерист

0

1





Звание

Род войск


Лейтенант


Лейтенант


Капитан


Майор

Танкист



0


Артиллерист



1



Александров не капитан и не майор (так как младше по званию, чем Васильев), значит он лейтенант. Получается, что оба лейтенанта танкисты, а Борисов – артиллерист, значит он не лейтенант. Так как Борисов не лейтенант и не капитан, то он майор. Тогда Васильев – капитан, поэтому он – артиллерист. Григорьев, значит, лейтенант и танкист.

В результате постепенного заполнения получаем следующие таблицы:

Фамилия

Звание


Александров


Борисов


Васильев


Григорьев

Лейтенант

1

0

0

0

Лейтенант

0

0

0

1

Капитан

0

0

1

0

Майор

0

1

0

0


Фамилия

Род войск


Александров


Борисов


Васильев


Григорьев

Танкист

1

0

0

1

Артиллерист

0

1

1

0


Звание

Род войск


Лейтенант


Лейтенант


Капитан


Майор

Танкист

1

1

0

0

Артиллерист

0

0

1

1


Ответ: Васильев и Борисов - капитан и майор артиллерии, Александров и Григорьев – лейтенанты танковых войск.



Лабораторная работа « Основы математической логики»

Цели:

  • знать:

    1. определения основных понятий (простое и сложное высказывания, логические операции, логические выражения, логическая функция);

    2. порядок выполнения логических операций;

    3. алгоритм построения таблиц истинности;

    4. правила построения логической функции по таблице истинности;

    5. законы логики и правила преобразования логических выражений;

  • уметь:

    1. применять определения для решения задач логики;

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

    3. строить таблицы истинности и логические функции;

Задания:

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

  • "Солнце есть спутник Земли";

  • "2+3?4";

  • "сегодня отличная погода";

  • "в романе Л.Н. Толстого "Война и мир" 3 432 536 слов";

  • "Санкт-Петербург расположен на Неве";

  • "музыка Баха слишком сложна";

  • "первая космическая скорость равна 7.8 км/сек";

  • "железо — металл";

  • "если один угол в треугольнике прямой, то треугольник будет тупоугольным";

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

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

  2. Составьте таблицы истинности логических выражений:

    • А  (¬B  C) .

    • ¬ (А  B)  (A  ¬ B) .

    •   B)  (C  B) .

  3. Составьте логическую функцию F (X, Y, Z) для заданной таблицы истинности: 

     X

     Y

     Z

     F

     0

     0

     1

     0

     0

     1

     1

     0

     1

     0

     0

     1

  4. Выражение (¬(¬А)  С)  B  (¬C) равносильно: 
    а)
     A  (¬C) ; 
    б)
     (¬A)  B; 
    в)
     A  (¬C). 
     

Понятие о множестве

Множество относится к математическим объектам, для которых нет строгого определения. Другим примером неопределяемого понятия служит точка в геометрии. Такие понятия вводятся на интуитивном уровне, но зато на их основе даются строгие определения других математических объектов.

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

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

Чтобы установить взаимно однозначное соответствие, необязательно пересчитывать элементы множеств. Например, мы знаем, что американские штаты находятся во взаимно однозначном соответствии с их столицами, хотя можем оставаться в неведении относительно общего их числа. Мы могли бы утверждать: «Столиц штатов ровно столько, сколько штатов».

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

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

Мощностью конечного множества называется количество его элементов. Мощность множества A обозначается m (A).

Пример 1. Определите мощность какого из множеств A = {1, 3, 5, 7, 9} или B = {2, 4, 6, 8} больше.

Решение. Понятие мощности конечных множеств позволяет сравнивать их по количеству элементов. Так, если A = {1, 3, 5, 7, 9}, а B = {2, 4, 6, 8}, то m (A) = 5, а m (B) = 4 и потому m (A) > m (B).

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

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

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

Счётное множество – множество, элементы которого можно пронумеровать. Например, множества натуральных, чётных, нечётных чисел. Счётное множество может быть конечным (множество книг в библиотеке) или бесконечным (множество целых чисел).

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

Множества обычно обозначаются большими буквами А, В, С,…, а их элементы - малыми: а, в, с

Запись а image002 A означает, что элемент а принадлежит множеству A, то есть а является элементом множества A. В противном случае, когда а не принадлежит множеству A, пишут а image003 A.

Для задания множества следует:

  1. Перечислить его элементы, например А={2, 6, 15} (множество А состоит из трёх элементов - целых чисел 2, 6, 15).

  2. Указать свойства элементов множества, например A = {x| x2≤ 4} - множество чисел х, удовлетворяющих указанному условию x2 ≤ 4.

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

Например, множество из трех элементов a, b, c допускает шесть видов записи:

{a, b, c} = {a, c, b} = {b, a c} = {b, c, a} = {c, a, b} = {c, b, a}.

Множество B называют подмножеством множества А, если любой элемент множества В является элементом множества А. Обозначается В  А .

  

Пример. Пусть А, В, С - подмножества множества N: А={1, 2, 6, 18}; В={6, 1, 18}; С={2, 18, 6, 1}. В этом случае А = С; C  A и A  C, B  A.

Свойства включения множеств:

  1. Пустое множество является подмножеством любого множества:   А.

  2. Любое множество является подмножеством самого себя, т.е. для любого множества А справедливо включение А  А.

  3. Если А - подмножество множества B, а B - подмножество множества C, то А - подмножество множества C 

Геометрически множества обычно изображаются как некоторые подмножества точек плоскости. В любой имеющей смысл задаче обычно рассматриваются подмножества некоторого "наибольшего" множества U, которое называют универсальным множеством. Универсальное множество - это самое большее множество, содержащее в себе все множества, рассматриваемые в задаче. На диаграммах Эйлера - Венна универсальное множество обозначают в виде прямоугольника и буквы U. На рисунке 3 изображено универсальное множество U и два его подмножества - множества А и В, B  A .Картинки, представленные на рисунках 1-3 называются диаграммами Эйлера-Венна.
 

image06

        Рис. 3.   Универсальное множество U и два его подмножества А и В

Примеры.

  1. Множество детей является подмножеством всего населения.

  2. Пусть множество А - множество красных яблок, а B - множество всех яблок. Тогда А  B.

  3. Множество студентов-филологов третьего курса есть подмножество множества всех студентов университета.

Операции над множествами

Два множества A и B называются равными, если они состоят из одних и тех же элементов, т. е. если каждый элемент множества A принадлежит множеству B и, обратно, каждый элемент B принадлежит A. Следовательно, два множества равны, если каждое из них является подмножеством другого

(A = B  (A  B и В А)).

Множества не равны, если хотя бы в одном множестве существует хотя бы один элемент, не принадлежащий другому множеству.

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

Объединением множеств А и В называется множество С, состоящее из всех элементов, принадлежащих хотя бы одному из данных множеств (т. е. либо A, либо B, либо одновременно и A и B). Объединение множеств обозначается символами "+" и "U": C = A U B.

Пример. Даны множества А = {-6, -3, 0, 3, 6} и B = {0, 2, 4, 6, 8}. Тогда A U B = {-6, -3, 0, 2, 3, 4, 6, 8}.

 Пример. Объединением множества рациональных чисел с множеством иррациональных чисел является множество действительных чисел.

Пересечением множеств А и В называется множество С, состоящее из элементов, принадлежащих одновременно и множеству А, и множеству В. Если множества А и Вне имеют общих элементов, их пересечение равно пустому множеству ; в этом случае множества А и В называются непересекающимися. Пересечение множеств обозначается символами "∩" и "•" (знак умножения): С = А  В или С = АВ.

Пример. Даны множества А = {-6, -3, 0, 3, 6} и B = {0, 2, 4, 6, 8}. Тогда A  B = {0, 6}.

 Пример. Пересечением множества целых чисел с множеством положительных чисел является множество натуральных чисел.

Разностью множеств А и В называется множество А\В, содержащее те элементы множества А, которые не принадлежат множеству В.

В определении разности множеств А и В не предполагается, что В является подмножеством множества A. Если же В подмножество A, то разность А\Вназывается дополнением множества В до множества А . Для дополнения множества А до универсального множества U применяется обозначение image009

Пример. Нуль является дополнением множества натуральных чисел относительно множества неотрицательных целых чисел.

Пример. Предположим, что множество U состоит из всех букв русского алфавита, A – из всех согласных, а множество B – из букв, встречающихся в слове«энциклопедия». Тогда

  • объединение множеств A и B состоит из всех букв алфавита, кроме а, ё, у, ъ, ь, ы, ю;

  • пересечение множеств A и B – из букв д, к, л, н, п, ц;

  • дополнение множества А до универсального множества U – из всех гласных.

Свойства операций

  1. A U A = A.

  2. A U  = A;

  3. A   = ;

  4. A U B = B U A (коммутативность сложения);

  5. A  B = B  A (коммутативность умножения);

  6. A U (B U C) = (A U B) U C (ассоциативность сложения);

  7. (A  B) ∩ C = A ∩ (B  C) (ассоциативность умножения);

  8. Если В  А, то A U B = A;

  9. Если В  А, то A  B = B;

  10. A ∩ (B U C) = (A  B) U (A  C) (дистрибутивность умножения относительно сложения);

  11. A U (B  C) = (A U B) ∩(A U C) (дистрибутивность умножения относительно сложения).

Задача 1.

В классе 30 учащихся, 16 из них занимаются музыкой, 17 увлекаются теннисом, а 10 занимаются и музыкой, и теннисом. Есть ли в классе ученики, равнодушные и к музыке, и к теннису, и если есть, то сколько их?

Решение. Если сложить число учащихся, интересующихся музыкой, с числом учащихся, занимающихся теннисом, т. е. 16 + 17 = 33, то учащиеся, интересующиеся и музыкой, и теннисом, окажутся учтенными дважды. Поэтому, чтобы определить число учащихся, интересующихся музыкой или теннисом, нужно из суммы 16 + 17 вычесть число учащихся, учтенных дважды, т. е. тех, кто интересуется и музыкой, и теннисом. По условию их 10. Таким образом, число интересующихся теннисом или музыкой равно 16 + 17 – 10 = 23 ученика. А так как в классе всего 30 учащихся, то 30 – 23 = 7 учащихся равнодушны и к музыке, и к теннису.

Задача 1 решена по следующему алгоритму. Пусть имеется два конечных множества A и B. Тогда

n(A B) = n(A) + n(B) – n(A ∩ B). (1)

В нашем случае A – множество учащихся, интересующихся музыкой, и n(A) = 16, B – множество учащихся, интересующихся теннисом, и n(B) = 17, n(A ∩ B) = 10, и тогда по формуле (1) n(A B) = 16 + 17 – 10 = 23.

Усложним задачу: пусть к тем, кто интересуется в классе музыкой, – множеству A и к тем, кто увлекается теннисом, – множество B добавляются еще и те, кто интересуется театром, – множество C. Сколько учеников увлекается или музыкой, или теннисом, или театром, т. е. чему равно число n(A B C)?
Если множества A, B и C пересекаются лишь попарно, т. е. A ∩ B ∩ C =
, то подсчет можно вести, как и прежде: сначала сложить n(A) + n(B) + n(C), а затем вычесть число тех элементов, которые подсчитаны дважды, т. е. вычесть число n(A ∩ B) + n(A ∩ C) + n(B ∩ C). Таким образом, число

n(A) + n(B) + n(C) – n(A ∩ B) – n(A ∩ C) – n(B ∩ C)

меньше истинного результата ровно на число элементов в пересечении множеств A ∩ B ∩ C, которое и следует добавить для получения верного результата

n(A B C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(A ∩ C) – n(B ∩ C) + n( A ∩ B ∩ C). (2)

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

В формулах (1) и (2) подсчитывается, сколько раз каждый элемент включается и исключается, поэтому их называют формулами включений и исключений. (Формулы включений и исключений часто называют формулами Грасмана в честь немецкого математика Г. Грассмана (1809 – 1887).)

Задача 2. 
На вступительном экзамене по математике были предложены три задачи: по алгебре, планиметрии и стереометрии. Из 1000 абитуриентов задачу по алгебре решили 800, по планиметрии – 700, а по стереометрии – 600 абитуриентов. При этом задачи по алгебре и планиметрии решили 600 абитуриентов, по алгебре и стереометрии – 500, по планиметрии и стереометрии – 400. Все три задачи решили 300 абитуриентов. Существуют ли абитуриенты, не решившие ни одной задачи, и если да, то сколько их?

Решение. Пусть U – множество всех абитуриентов, A – множество абитуриентов, решивших задачу по алгебре, B – множество абитуриентов, решивших задачу по планиметрии, C – множество абитуриентов, решивших задачу по стереометрии. По условию n(U) = 1000, n(A) = 800, n(B) = 700, n(C) = 600, n(A ∩ C) = 500, n(B ∩ C) = 400, n(A ∩ B ∩ C) = 300. В множество A B C включены все абитуриенты, решившие хотя бы одну задачу. По формуле (2) имеем n(A B C) = 800 + 700 + 600 – 600 – 500 – 400 + 300 = 900. Отсюда следует, что не все поступающие решили хотя бы одну задачу. Ни одной задачи не решили

n(U) – n(A B C) = 1000 – 900 = 100 (абитуриентов).

Задача 3.
Социологи опросили 45 учащихся девятых классов, среди которых 25 юношей. При этом выяснилось: 30 человек имеют за полугодие оценки «4» и «5», из них 16 юношей, спортом занимаются 28 учеников, среди них 18 юношей, и 17 учеников, успевающих на «хорошо» и «отлично», 15 юношей учатся на «хорошо» и «отлично» и занимаются спортом.

Первый математик класса взглянул на результаты и заявил, что здесь есть ошибки. Как это ему удалось выяснить?

Решение. Обозначим через A множество юношей, через B множество учеников, успевающих на «4» и «5», через C множество спортсменов. По условию задачи n(A) = 25, n(B) = 30, n(C) = 28, n(A ∩ B) = 16, n(A ∩ C) = 18, n(B ∩ C) = 17, n(A ∩ B ∩ C) = 15. Найдем общее число учащихся, которые или являются юношами, или занимаются спортом, или успевают на «4» и «5». По формуле (2) получаем

n(A B C) = 25 + 30 + 28 – 16 – 17 + 15 = 47.

Этого быть не может, так как обследовалось всего 45 учеников! Значит, в данных сведениях есть ошибки.

На рисунке 17 это решение проиллюстрировано с помощью диаграммы Эйлера – Венна. В пересечении множеств A, B и C запишем число 15, так как по условию n(A ∩ B ∩ C) = 15. В множестве (A ∩ B) \ C запишем 16 – 15 = 1, в множестве (A ∩ C) \ B – число 18 – 15 = 3, в множестве (B ∩ C) \ A – число 17 – 15 = 2, в множестве A \ (B C) – число 25 – (1 + 15 + 3) = 6, в множестве B \ (A C) – число 30 – (1 + 15 + 2) = 12, в множестве C \ (A B) – число 28 – (3 + 15 + 2) = 8. Чтобы найти n(A B C), достаточно сложить записанные числа. Получим число 47 > 45, что невозможно по условию задачи.Пример пересечения множеств

Лабораторная работа: « Операции над множествами»

  • знать:

    1. понятия (множество, конечное и бесконечное множество, мощность, подмножество);

    2. диаграммы Эйлера-Венна;

    3. операции над множествами;

    4. правила комбинаторики;

  • уметь:

    1. задавать множество, определять его мощность, сравнивать множества;

    2. решать задачи, используя операции над множествами;

    3. решать задачи, используя правила комбинаторики;

Задания:

  1. Пусть А и В – множества, изображенные на рисунке:

mn

укажите объединение, пересечение и разность этих множеств.

  1. Заданы множества А = {3, 7, 8, 9, 2}, B = {1, 5, 6, 7, 8, 9} и C = {1, 7, 18, 19, 12}. Какое из множеств имеет наибольшую мощность.

  2. Заданы множества А = {-3, 2, 5, 9, 12} и B = {1, 5, 6, 7, 8, 9}. Задайте объединение, пересечение и разность множеств А и В.

  3. На факультете филологии и журналистики учатся студенты, получающие стипендию, и студенты, не получающие стипендию. Пусть А – множество всех студентов факультета; В – множество студентов факультета, получающих стипендию. Укажите, что собой представляет объединение, пересечение и разность множеств А иВ.

  4. Пусть А – множество всех студентов-филологов университета; В – множество студентов первокурсников. Укажите, какие студенты содержатся во множестве А\В.

  5. Сколькими способами можно отобрать 12 книг из 20 и расставить их в ряд на полке?

  6. 20 человек знают английский и 10 - немецкий, из них 5 знают и английский, и немецкий. Сколько Человек всего?

  7. Переплетчик должен переплести 14 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

  8. Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?

  9. У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

  10. В кондитерском магазине продавались 4 сорта пирожных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пирожных.

  11. Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?




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

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

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

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

Приведем пример. Обозначим через Sn наибольшее число областей, на которые можно разбить плоскость n окружностями. Легко проверить, что S1=2, S2=4, S3=8. Возникает предположение, что при любом натуральном n будет Sn=2n. Однако можно показать, что это заключение ошибочно, например, S4= 14, а не 16 (см.рис.)










14



1 2 3


11

8 9 10 4

13

12



7 6 5




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

Практические задания.

1. 1 + 3 = 4, то есть сумма первых двух нечетных чисел равна 22. Для суммы трех первых нечетных чисел имеем: 1+3+5=9. Какую гипотезу подсказывают эти примеры?

2. Проверьте эту гипотезу еще на нескольких примерах.

3. Докажите или опровергните вашу гипотезу.

4. В задании 1 речь шла о том, что число 22 представимо в виде суммы двух последовательных нечетных чисел. Какое аналогичное предложение верно для числа 23? Для 33 ?

5. Какая закономерность кажется в данном случае правдоподобной?

6. Проверьте ее для нескольких точных кубов.

7. Докажите ее в общем случае (для числа n3).

(Ответы: 1. Сумма n первых нечетных чисел равна n2 2. при n = 4: 1+3+5+7= 42, при n = 5: 1+3+5+7+9 = 52 3. Докажем с помощью арифметической прогрессии, в которой а1 = 1, d = 2: hello_html_18f375a9.gif, гипотеза доказана. 4. 23 = 3 + 5, 33 = 7+9+11 ; 5. Для каждого натурального n существует n последовательных нечетных чисел, сумма которых равна n3) 6. 43 = 13+15+17+19, 53 = 21+23+ 25+27+29; 7. 1 случай: п – нечетное, тогда п2 – тоже нечетное. Возьмем такие п последовательных нечетных чисел: …+( п2–4)+( п2–2)+ п2+( п2+2)+( п2+4)+…=п· п2 =п3 ; 2 случай: п – четное, тогда п2 – тоже четное. Возьмем такие п последовательных нечетных чисел: …+( п2–3)+

( п2–1)+ ( п2+1)+( п2+3)+…=п· п2 =п3; гипотеза доказана для общего случая.

2.Индукция при поиске способа решения задачи.

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

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

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

Способ решения этой задачи легко найти, если последовательно рассмотреть такие случаи: а) Точка М – вершина треугольника, тогда ясно, что сумма ее расстояний от сторон треугольника равна его высоте; б) Точка М – на стороне треугольника (скажем, М – на ВС). Этот случай сводится к предыдущему, если через М провести прямую MN АС и обозначить А1= MN ∩ АВ; (тогда М – вершина правильного треугольника А1ВМ; в) (общий случай) М – произвольная точка, лежащая внутри треугольника АВС, этот случай сводится к случаю б), если провести прямую MN АС, рассмотреть точки

А1= MN ∩ АВ, С1= MN ∩ ВС, и треугольник А1ВС1.

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

Практическое задание.

В двух ящиках имеются шары: в одном – m, в другом – n, mn. Двое играющих поочередно вынимают шары из ящика. Каждый раз игроку разрешается взять любое число шаров, но только из одного ящика. Выигравшим считается тот, кто вынимает последний шар. Как должен играть первый (тот, кто начинает игру), чтобы выиграть?

Решение. 1. Рассмотрим случай, когда п = 0, m = 1. В этом случае первый игрок начинает и выигрывает. 2. аналогично, если п = 0, m – любое число. 3. если п = 1, m – любое число: первый игрок из первого ящика(где m шаров) вынимает все шары, оставив в ящике только один шар, второй игрок вынимает единственный шар из любого ящика, задача сводится к случаю 1; 4. если п = 2, m – любое число: первый игрок из первого ящика(где m шаров) вынимает все шары, кроме 2-х. Если второй игрок вынимает из любого ящика 1 шар, то первый из другого ящика вынимает тоже 1 шар, после этого второму ничего не остается, как вытащить из любого ящика последний шар, первый вынимает из другого ящика тоже последний шар и выигрывает. Если второй игрок вынимает из любого ящика 2 шара, то первый из другого ящика вынимает тоже 2 шара и выигрывает. 5. п – любое число, m – любое число, mn. Тогда первый игрок вынимает из первого ящика m – п шаров. В двух ящиках остается поровну, и затем первый игрок каждым своим ходом уравнивает количество шаров в ящиках. Ситуация сведена к случаю 4.




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

Для доказательства формул и теорем, справедливых для всех натуральных чисел, часто применяется метод математической индукции. Впервые это метод встречается в одном трактате французского математика, физика и философа Блэза Паскаля (1623 – 1662). После Паскаля им пользовались многие математики. Для школьников этот метод может оказаться довольно трудным. По словам академика А.Н.Колмогорова: «По-видимому, наибольшую трудность в отношении понимания логической структуры математического утверждения для школьников часто представляет принцип математической индукции. Здесь уже самое понимание смысла высказывания для многих тонет в чрезмерном нагромождении всяких «если», «то» и т.д. Понимание и умение применять принцип математической индукции является хорошим критерием логической зрелости, которая совершенно необходима математику».

Предварительные задачи.

Прежде чем перейти к методу математической индукции, рассмотрим несколько предварительных задач.

1. Дано, что hello_html_7d6d8d86.gif

Чему равно S1, S2, S5 ?

2. Проверьте справедливость равенства:

hello_html_m634217c0.gif

при n = 2, при n = 1.

3. Были заданы три числа a, b, c. Пусть a + c = 2b. Докажите, что тогда

hello_html_m2a2cd7a2.gif

4. а) Проверьте справедливость формулы

hello_html_m16acd65d.gif(1)

при n = 3.

б) Как проще всего проверить справедливость формулы (1) при n = 4 ?

в) Кто-то доказал, что формула (1) верна при n = 50. Пользуясь этим, докажите, что формула (1) верна при n = 51, при n = 52.

г) Докажите, что если при n = k формула (1) верна, то она верна и при

n = k + 1.

5. а) Проверьте, что hello_html_1f400d49.gif (1) при n = 66 является целым числом. Как теперь докажете, что выражение (1) также является целым числом при n = 67 ? n = 68 ?

б) Докажите, что если число k такое, что при n = k выражение (1) является целым числом, то это выражение является целым числом также для следующего натурального числа, то есть при n = k + 1. в) Докажите, что выражение (1) является целым числом при любом натуральном n от 1 до 30.

Ответы и решения: 1. hello_html_m6cacfa07.gif

2. при n = 2: hello_html_m62a00377.gif hello_html_m5eb0d4f6.gif

при n = 1:

3. hello_html_5410ab51.gif

4. а) hello_html_m25258509.gif

б) так как hello_html_m273bc194.gif




в) так как

hello_html_1eccd5e5.gif

hello_html_1611d37b.gif

г) так как hello_html_m5345670c.gif

5. а) так как 66 кратно 6, то 662 кратно 2 и кратно 3, так что (1) при п=66 – целое число.

hello_html_m66ad550a.gif

Аналогично, при п=68 пользуемся равенством:

hello_html_m20e88709.gif

б) по условию hello_html_m7c9934c8.gif - целое число. Поэтому

hello_html_m29680fc5.gifhello_html_39664414.gifhello_html_m699bdbb3.gif-

целое число;

в) при п = 1 (1) – целое число. В силу пункта б) (при k=1)получаем, что (1) – целое число при п=2 и т.д., пока не доберемся до п=30.


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

1) Формула hello_html_6d08402c.gif

верна при n = 1, 2, 3, 4, 5, 6, но не верна при n = 7.

2) Число вида hello_html_6c594577.gif называется «n-м числом Ферма». При n = 1, 2, 3, 4 получим числа 5; 17; 257; 65537. Эти числа простые. П.Ферма (1601-1665) высказал теорему: «Всякое число вида hello_html_6c594577.gif является простым». Оказалось, что эта теорема неверна: при n = 5 получим 4294967297, это составное число, оно делится на 641.

Сущность метода.

Пусть требуется доказать какую-либо формулу (теорему).

I. Показываем, что эта формула (теорема) верна при n = 1 (или более в общем случае: при n = n0, где n0 – фиксированное целое число, например n0 = 0; n0 = 8).

II. Доказываем следующее предложение: «Если k – такое число, что при n = k формула (теорема) верна, то она верна и для следующего натурального числа (то есть при n = k + 1).

Отсюда из (I и II) делаем вывод, что формула (теорема) верна для всех натуральных чисел n(или, соответственно, для всех n n0). Утверждение, что такой вывод можно сделать, называется принципом математической индукции. Это утверждение (или равносильное ему ) принимается без доказательства, является аксиомой.

Практические задания.

6. Докажите, что для всех натуральных n справедлива формула:

hello_html_m16acd65d.gif.

7. Докажите, что для всех натуральных n справедливо равенство:

hello_html_m634217c0.gif.

8. Докажите, что для всех натуральных n число hello_html_1f400d49.gif является целым.

9. Один ученик, доказывая формулу методом математической индукции, начал с того, что проверил ее при n = 1, 2, 3, 4. Что он сделал лишнего?

10. а) Другой ученик, доказывая одну формулу методом математической индукции, сначала проверил ее при n = 1, а затем рассуждал так: «Допустим, что формула верна при n = k. Но k – любое натуральное число; следовательно, можно вместо k подставить k + 1; тогда получим, что формула верна при n = k + 1. А так как при n = 1 формула верна, то она верна для всех натуральных чисел. В чем его ошибка?

б) Его товарищ рассуждал так: «Решая задачу методом математической индукции, допускаем, что формула верна при n = k, и доказываем, что она верна при

n = k + 1. Но что такое k ? Любое натуральное число. А если так, то что же нам еще остается доказать, если мы уже знаем, что формула верна для любого натурального номера?» В чем ошибка этого рассуждения?

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

12. Докажите, что при натуральном n 5 справедливо неравенство 2n n2.

13. Докажите, что при натуральном n 1 число hello_html_6c594577.gif оканчивается цифрой 7.

14. Докажите формулы для n-го члена и для суммы n первых членов геометрической прогрессии.

Ответы и решения:

6. При п = 1 формула верна. Учитывая пункт г) из задачи 4 и принцип математической индукции, заключаем, что формула справедлива для любого натурального п.

7. При п = 1 равенство (1) принимает вид hello_html_6b36e0b0.gifОно справедливо. Пусть k – такой номер, при котором рассматриваемое равенство справедливо, то есть hello_html_744b4c93.gif (А) Докажем, что равенство (1) справедливо и для следующего номера k + 1 (то есть, если положить п= k + 1):

hello_html_m7bdd8647.gif(В) Действительно, учитывая (А), имеем: hello_html_m586f379f.gif

hello_html_m69dbc53b.gifhello_html_64db8aa4.gif

Итак, из справедливости (А) следует (В). В силу принципа индукции доказываемое равенство верно для всех номеров п.

8. При п = 1 утверждение верно hello_html_67f8dead.gif - целое число. В силу пункта б) из задачи 5 и принципа математической индукции, заключаем, что утверждение верно для любого натурального п.

9. В начале доказательства надо проверить формулу только для п = 1.

10. Предполагаем, что k – не любое натуральное число, а такое значение п, при котором формула верна.

11. При п =8 утверждение верно: 8 рублей можно уплатить, отдав трехрублевую и одну пятирублевую купюру. Пусть теперь уже установлено, что k рублей возможно уплатить без сдачи лишь тройками и пятерками, то есть k=3t + 5p (здесь t и p – целые неотрицательные числа). Докажем, что в таком случае возможно k + 1 руб. уплатить без сдачи только тройками и пятерками. Действительно, k + 1=3t + 5p+1.

Возможны два случая. 1) р=0. Тогда t 3, k + 1=3(t-3) + 5·2, и k + 1 руб. можно уплатить без сдачи только тройками и пятерками (t-3 тройки и две пятерки); 2) р0. Тогда р 1 и k + 1=3(t+2) + 5-1), опять видно, что k + 1 руб. можно уплатить лишь тройками и пятерками (t+2 тройки и р-1 пятерок). Итак, утверждение верно при п=8 и из справедливости его при п=k следует его справедливость при п=k+1. Поэтому, оно верно для всех номеров п, которые не меньше 8.

12. При п = 5 неравенство 2n n2 (1) справедливо: 25 52. Пусть k – такой номер, что при п=k неравенство (1) справедливо, то есть 2k k2. Докажем, что (1) верно и для следующего номера, то есть при п=k+1. Действительно, 2k+1 = 2·2k k2= (k+1)2+ +k2- 2k – 1 = (k+1)2+ (k -1)2-2 (k+1)2 если k 5.

13. При п = 2 утверждение легко проверяется. Пусть k – такой номер, что hello_html_m4de59498.gif оканчивается цифрой 7. Тогда hello_html_42e30e7c.gif оканчивается цифрой 6. hello_html_6a2fcea.gif тоже оканчивается цифрой 6 (так как если число оканчивается шестеркой, то и его квадрат оканчивается шестеркой). Но тогда hello_html_m66721ab5.gif оканчивается цифрой 7. Итак, из справедливости теоремы при п=k следует ее справедливость при п=k+1. В силу принципа индукции теорема верна для всех номеров п 2.

14. Пусть а1, а2, ... ап – данная прогрессия, q – ее знаменатель.

По определению при любом п: ап+1= ап· q, Sn = а1+ а2+ ... +ап, S1 = а1. (1)

Докажем формулы: ап= а1· qп-1, hello_html_m59dd02f0.gif(2)

Ясно, что при п =1, обе формулы (2) верны. Из равенств аk= а1· qk-1

и hello_html_547ca248.gif и (1) следует, что аk+1= аk· q= а1· qk-1· q= а1· qk, и

hello_html_19691eb5.gif

Иначе говоря, из справедливости формул (2) для номера k (то есть при п=k) следует их справедливость для следующего номера k+1 (то есть при п=k+1). Так как (2) верны еще и при п=1, то в силу принципа индукции формулы (2) справедливы для всех номеров п.

Применение метода математической индукции к суммированию рядов.

Задача 3. Доказать формулу

hello_html_m7f0c6171.gif, n – натуральное число.

Решение.

При n=1 обе части равенства обращаются в единицу и, следовательно, первое условие принципа математической индукции выполнено.

Предположим, что формула верна при n=k, т.е.

hello_html_5687300b.gif.

Прибавим к обеим частям этого равенства hello_html_m534b333d.gif и преобразуем правую часть. Тогда получим

hello_html_m7e8458f1.gif

Таким образом, из того, что формула верна при n=k, следует, что она верна и при n=k+1. Это утверждение справедливо при любом натуральном значении k. Итак, второе условие принципа математической индукции тоже выполнено. Формула доказана.


Задача 4. На доске написаны два числа: 1,1. Вписав между числами их сумму, мы получим числа 1, 2, 1. Повторив эту операцию еще раз, получим числа 1, 3, 2, 3, 1. После трех операций будут числа 1, 4, 3, 5, 2, 5, 3, 4, 1. Какова будет сумма всех чисел на доске после 100 операций?

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


п

Shello_html_m3cabfa0d.gif

0

2

1

4

2

10

3

28

Заметили ли вы здесь какую-нибудь закономерность? Если нет, можно сделать еще один шаг: после четырех операций будут числа

1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1,

сумма которых S4 равна 82.

В действительности можно не выписывать числа, а сразу сказать, как изменится сумма после добавления новых чисел. Пусть сумма была равна 5. Какой она станет, когда добавятся новые числа? Разобьем каждое новое число в сумму двух старых. Например, от 1, 3, 2, 3, 1 мы переходим к 1,

1 + 3, 3, 3 + 2, 2, 2 + 3, 3, 3 + 1, 1.

То есть каждое старое число (кроме двух крайних единиц) входит теперь в сумму три раза, поэтому новая сумма равна 3S - 2 (вычитаем 2, чтобы учесть недостающие единицы). Поэтому S5 = 3S4 - 2 = 244, и вообще

hello_html_3445a8ef.gif

Какова же общая формула? Если бы не вычитание двух единиц, то каждый раз сумма увеличивалась бы в три раза, как в степенях тройки (1, 3, 9, 27, 81, 243, ... ). А наши числа, как теперь видно, на единицу больше. Таким образом, можно предположить, что hello_html_m24845c29.gif

Попробуем теперь доказать это по индукции.

База индукции. Смотри таблицу (для п = 0, 1, 2, 3).

Шаг индукции. Предположим, что

hello_html_m12597de3.gif, докажем тогда, что Sк + 1 = Зк + 1 + 1.

Действительно,

hello_html_m71f15d09.gif

Итак, наша формула доказана. Из нее видно, что после ста операций сумма всех чисел на доске будет равна З100 + 1.

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


Задача 5. Доказать, что если hello_html_m4333738d.gif = 2, х2 = 3 и для всякого натурального п > 3 имеет место соотношение

хп = Зхп-1 - 2хп-2,

то

hello_html_169e9d30.gif = 2п-1 + 1, п = 1, 2, 3, ...

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

База индукции. Она состоит из проверки двух утверждений: при п = 1 и п = 2.В обоих случаях утверждение справедливо по условию.

Шаг индукции. Предположим, что для п = к - 1 и п = к утверждение выполнено, то есть

hello_html_m21274a69.gif

Докажем тогда справедливость утверждения для п = к + 1. Имеем:

хhello_html_7428960d.gif1 = 3(2hello_html_5ef749b9.gif + 1)- 2(2hello_html_1f00cf0b.gif + 1) = 2hello_html_42de2c30.gif+1, что и требовалось доказать.

Примеры применения метода математической индукции к доказательству неравенств.


Задача 6. (Неравенство Бернулли.) Докажите, что при х > -1, хhello_html_7eeb9f88.gif 0, и при целом п > 2 справедливо неравенство

(1 + х)п > 1 + хп.

Решение. Доказательство снова будем проводить по индукции.

1. База индукции. Убедимся в справедливости неравенства при п = 2. Действительно,

(1 + х)2 = 1 + + х2 > 1 + 2х.

2. Шаг индукции. Предположим, что для номера п = к утверждение справедливо, то есть

(1 + х)к > 1 + хк,

где к > 2. Докажем его при п = к + 1. Имеем: (1 + х)к + 1 = (1 + х)к(1 + х)>(1 + кх){1 + х) =

= 1 + + 1)х + кх2 > 1 + + 1)х.

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

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


Задача 7. Доказать, что

1+hello_html_m7b113ad4.gif


при любом натуральном п > 1.

Решение, Попробуем доказать это неравенство методом математической индукции.

Базис индукции проверяется без труда:1+hello_html_mb3c7543.gif

По предположению индукции hello_html_m47f3f40f.gif и нам остается доказать, что hello_html_m15770033.gif

Если воспользоваться индуктивным предположением, то мы будем утверждать, что hello_html_1d623552.gif

Хотя это равенство на самом деле верно, оно не дает нам решения задачи.

Попробуем доказать более сильное утверждение, чем это требуется в исходной задаче. А именно, докажем, что hello_html_m7ea17a1.gif

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

Однако при п = 1 имеем:hello_html_m4165a161.gif утверждение верно. Для обоснования индуктивного шага предположим, что hello_html_m3c5fa3a6.gif

и докажем тогда, что hello_html_4e4198e9.gif

Действительно,

hello_html_m13495e55.gif

Таким образом, нами доказано более сильное утверждение, из которого сразу же следует утверждение, содержащееся в условии задачи.



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

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

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

Сейчас остановимся на других таких возможностях. Прежде всего дадим понятие о предикате.

Бывает, что высказывание зависит от каких-то переменных (которые могут быть самой разнообразной природы), и значение истинности высказывания зависит от значений этих переменных.

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

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

В первом примере мы имели дело с двумя независимыми переменными, во втором – с одним (в нем «переменное» - это город).

Можно себе представить высказывание, истинность или ложность которого зависит от n переменных, где n – какое угодно заданное натуральное число. При этом известно, каковы множества возможных значений переменных. Так, в первом примере х и у могли «пробегать» всевозможные натуральные значения.

Высказывание, истинность или ложность которого зависит от одного или нескольких переменных, называют предикатом.

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

Пусть Р(х) означает «Рациональное число х является корнем уравнения х2 – 5х + 6 = 0». Легко проверить, что Р(2) = 1 (истина), Р(0) = 0 (ложь). Вот другой пример. Пусть Р(х,у) означает: «Целое число х меньше целого числа у». Тогда Р(5,3) = 0 (ложь), Р(3,5) = 1 (истина).

Из предикатов можно образовать новые предикаты, употребив логические связки «и», «или», «не», «если…, то…». Например, пусть х может быть любым натуральным числом, Р(х) означает: «Число х делится на 3», а Q(х) означает: «Число х делится на 5». Тогда Р(х) Q(х) означает: «Число х делится и на 3 и на 5» (иными словами: «Число х делится на 15»); hello_html_6152c149.gif означает: «Число х не делится на 3», и т.д.

Кванторы. Располагая каким-либо предикатом, можно строить новые предикаты, привлекая так называемые кванторы – приставки, которые ставятся перед предикатом. Употребляются два вида кванторов: квантор существования и квантор всеобщности.

Пусть Р(х,у) – какой-нибудь предикат (для определенности – двучленный, то есть зависящий от двух переменных). Запись хР(х,у) расшифровывается так: «Существует такой х, что имеет место Р(х,у)». Приставка х и называется квантором существования. Например, пусть х и у – натуральные числа. Пусть Р(х,у) означает: х у. Запись хР(х,у) выражает следующий предикат: «Существует такое натуральное число х (хотя бы одно), что х у». В частности, хР(х,1) = 0 (ложно), хР(х,5) = 1 (истинно). Говорят, что предикат хР(х,у) образуется из предиката Р(х,у) путем навешивания квантора х.

Второй вид кванторов – это квантор всеобщности. Запись хР(х,у) расшифровывается так: «Для каждого х имеет место Р(х,у)». Приставка х и называется квантором всеобщности.

Например, если Р(х,у) означает х у ( х и у – натуральные числа), то хР(х,у) означает: «Для каждого х имеет место неравенство х у». Очевидно, что хР(х,1)=1 (истинно); хР(х,20)=0 (ложно).

Пользуясь логическими связками и кванторами, можно компактно записать громоздкие словесные формулировки. Например, предложение: «Если точка В лежит между точками А и С, а точка С – между точками В и D, то точка С лежит между точками А и D» - можно записать короче если ввести предикат (Х, Y, Z), который означает: «Точка Y лежит между точками Х и Z». Предложение принимает такой компактный вид: (А,В,С)(В,С,D) (А,С,D).

Тренировочные упражнения.

1. Пусть предикат Т(n) означает: «Теорема верна для натурального числа n». Запишите с помощью кванторов и логических связок («и», «или», «не», «если…, то…») следующее предложение («принцип математической индукции»): «Если теорема верна при n = 1 и если для каждого k из справедливости теоремы при n=k следует ее справедливость при n=k + 1, то для каждого натурального n теорема верна».

2. Пусть буквы А, В, С … обозначают точки некоторой плоскости; a, b, c …- прямые той же плоскости; предикат «А а» означает: «Точка А принадлежит прямой а». Запишите с помощью кванторов и логических связок такую аксиому: «Через любые две точки плоскости проходит прямая».

3. Пусть х может оказаться любым параллелограммом и пусть предикаты Р(х) и Q(х) означают:

Р(х) – «х является прямоугольником»;

Q(х)- «х имеет равные диагонали».

Используя эти предикаты, запишите теорему: если параллелограмм является прямоугольником, то его диагонали равны.

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

а) «Через точку М, лежащую вне данной прямой а, проходит прямая, параллельная данной»;

б) «Через точку М вне данной прямой проходит не более чем одна прямая, параллельная данной».

5. Будем точки обозначать латинскими буквами А, В, С, D, …, а плоскости – греческими α, β, γ, … . Предикат «Аα» означает: «Точка А принадлежит плоскости α». Пользуясь этим предикатом, логическими связками и кванторами, запишите такие два утверждения:

1. «Существуют четыре точки, не принадлежащие одной и той же плоскости»;

2. « Не существуют четыре точки, принадлежащие одной и той же плоскости».

Ответы: 1. {T(1)k[T(k)T(k+1]}nT(n). 2. ABa[(Aa)(Ba)]. 3. x[P(x)Q(x)]. 4. Пусть M,N…обозначают точки, a,b,c…- прямые. Введем такие предикаты: b a –« Прямая b параллельна прямой а», b a- «Прямые b и а совпадают», М а- «Точка М лежит на прямой а», М а – «Точка М не лежит на прямой а». Тогда предложения а) и б) можно записать так: а) Ma{(Ma)b[(Mb)(b a)]}. б) Mabc{[(Ma)(Mb)(Mc)(b a)(b c)] b c}.

5. 1.ABCDα{[(Aα)(Bα)(Cα)](Dα)}. (истинно)

2. ABCDα{[(Aα)(Bα)(Cα)](Dα)}. (ложно).


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

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

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

Прежде всего заметим, как строится отрицание высказывания вида хР(х). Запись hello_html_7c0a3b64.gif означает «Неверно, что для каждого х истинно Р(х)», то есть высказывание hello_html_7c0a3b64.gif означает, что хотя бы для одного х ложно Р(х); иными словами, хотя бы для одного х истинно hello_html_6152c149.gif. А это можно записать так: hello_html_m60905070.gif.

Итак, мы видим, что hello_html_7c0a3b64.gif= hello_html_m60905070.gif.

Аналогично можно убедиться, что справедливо соотношение

hello_html_m259a1a26.gif

Сходные формулы верны и для предикатов от нескольких переменных, например:

hello_html_m4ac37b68.gif

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

hello_html_m23845382.gif

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

Пример. Построим отрицание высказывания А: «Каждый четырехугольник с равными и взаимно перпендикулярными диагоналями есть квадрат».

Введем обозначения: х – произвольный четырехугольник; D(x) – предикат «Диагонали четырехугольника х взаимно перпендикулярны и равны»; Q(х) – предикат «х является квадратом».

А запишется так: А = х[D(x) Q(x)], тогда

hello_html_6a5d9087.gif

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


Тренировочные упражнения.

6. Кто-то нарисовал на листке клетчатой бумаги 100 концентрических окружностей. Каждый круг, чьей границей служит такая окружность, обозначим буквой . Кроме того, рассматриваем на листе всевозможные узлы (точки пересечения линий, образующих сеть клеток); такие точки обозначим через х. Введем предикат: « х» (Круг содержит узел х»). Используя его, а также кванторы и логические связки, запишите следующие предложения:

А: «Каждый круг содержит хотя бы один узел».

В: «Существует круг, который содержит хотя бы один узел».

С: «Ни один круг не содержит ни одного узла».

Сформулируйте отрицания этих высказываний.

Ответы: А: х(х); В: х(х); С: hello_html_m44362b38.gif

Ā: hello_html_39505407.gif; hello_html_66f5a55.gif

Решение логических задач.

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

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

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

А = «В первой аудитории находится кабинет информатики»;

В = «Во второй аудитории находится кабинет информатики».

Отрицания этих высказываний:

Ā = «В первой аудитории находится кабинет физики»;

hello_html_1b4c48a.gif= «Во второй аудитории находится кабинет физики».

Высказывание, содержащееся на табличке на двери первой аудитории, соответствует логическому выражению: Х = А Ú В.

Высказывание, содержащееся на табличке на двери второй аудитории, соответствует логическому выражению: Y = Ā.

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

hello_html_m2be29995.gif

Подставим вместо Х и Y соответствующие формулы:

hello_html_7ab09a65.gif

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

hello_html_m38966006.gif

В соответствии с законом непротиворечия:

hello_html_1d3e1adb.gif

Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

hello_html_m1951b0f7.gif

В соответствии с законом непротиворечия:

hello_html_m38b4af8.gif

В результате получаем:

hello_html_m5ec67238.gif

Полученное логическое выражение оказалось простым, и потому его можно проанализировать без построения таблицы истинности. Для того, чтобы выполнялось равенство hello_html_76a07d46.gif должны быть равны 1, то есть соответствующие им высказывания истинны.

Ответ: В первой аудитории находится кабинет физики, а во второй – кабинет информатики.

Задача 2. Полиция задержала четырех гангстеров, подозреваемых в краже автомобиля: Анри, Луи, Жоржа и Тома. При допросе они дали следующие показания: Анри: «Это был Луи». Луи: « Это сделал Том». Жорж: «Это не я». Том: «Луи лжет, говоря, что это сделал я». Дополнительное расследование показало, что правду сказал только один из них. Кто украл машину?

Решение. Введем обозначения:

А= «Анри украл машину»;

Л= «Луи украл машину»;

Ж= «Жорж украл машину»;

Т= «Том украл машину».

Тогда результаты допроса и дополнительного расследования можно выразить так: hello_html_ma60537e.gif Согласно закону исключенного третьего, hello_html_m9bbfaa1.gifтогда Л = 0 и hello_html_m67910473.gif откуда следует, что Ж = 1.

Ответ: машину украл Жорж.

Задача 3. При составлении расписания на понедельник были высказаны пожелания, чтобы математика была первым или втором уроком, физика – первым или третьим, литература – вторым или третьим. Можно ли удовлетворить одновременно все высказанные пожелания?

Решение. Обозначим: М1 = «1-й урок – математика», М2 = «второй урок – математика», Ф1 = «1-й урок – физика», Ф2 = «2-й урок – физика», Л2 = «второй урок – литература», Л3 = «третий урок – литература». По условию задачи:

(М1 Ú М2) Ù (Ф1 Ú Ф3) Ù (Л2 Ú Л3) = 1.

Преобразуем данное логическое выражение (перемножим первые две скобки):

((М1 Ù Ф1) Ú (М1 Ù Ф3) Ú (М2 Ù Ф1) Ú (М2 Ù Ф3)) Ù (Л2 Ú Л3) = 1.

М1 Ù Ф1=0 (не может быть первый урок математикой и физикой одновременно), М2 Ù Ф3 = 0 (если второй урок – математика, а третий – физика, тогда первый урок – литература, что противоречит условию. Имеем:

(0 Ú (М1 Ù Ф3) Ú (М2 Ù Ф1) Ú 0) Ù (Л2 Ú Л3) = 1;

((М1 Ù Ф3) Ú (М2 Ù Ф1) ) Ù (Л2 Ú Л3) = 1.

Из этого логического выражения видно, что можно составить два варианта расписания: 1 вариант. 2 вариант.

1. Математика 1. Физика

2. Литература или 2. Математика

3. Физика 3. Литература.

Задача 4. Один из пяти братьев испек маме пирог. Андрей сказал: « Это Витя или Толя». Витя сказал : « Это сделал не я и не Юра». Толя сказал : «Вы оба шутите». Дима сказал: «Нет, один из них сказал правду, а другой – нет». Юра сказал: «Нет, Дима, ты не прав». Мама знает, что трое из ее сыновей всегда говорят правду. Кто испек пирог?

Решение. Обозначим высказывание Андрея через А, высказывание Вити – через В. Тогда высказывание Толи: hello_html_1127aef5.gif (оба шутят). Высказывание Димы: hello_html_m51c99587.gif (отрицание эквивалентности – истинно, когда истинно только одно из двух высказываний). Высказывание Юры отрицает высказывание Димы, то есть hello_html_58fa392f.gif Составим таблицу истинности:

Андрей

Витя

Толя

Дима

Юра

А

В

hello_html_1127aef5.gif

hello_html_m51c99587.gif

hello_html_m414a8135.gif

0

0

1

0

1

0

1

0

1

0

1

0

0

1

0

1

1

0

0

1

Из таблицы видно, что три истинных высказывания есть только в последней строке ( в других – по два), значит правду сказали Андрей, Витя и Юра. Так как Андрей сказал, что это сделал Витя или Толя, а Витя сказал, что не он, следовательно, по закону исключенного третьего, это сделал Толя.

Ответ: пирог испек Толя.

Решение логических задач методом неравенств.

Задача 5. В соревновании по бегу участвовали три бегуна: Авдеев, Васильев и Семенов. Перед забегом один зритель сказал, что первым придет Авдеев, второй – что Семенов не будет последним, а третий – что Васильев не придет первым. После забега оказалось, что один зритель угадал, а два другие ошиблись. Как закончились соревнования?

Решение. Обозначим место, занятое Авдеевым, через а, Васильевым – через b, Семеновым – через с. Бегунов было трое, значит, а, b и с могут быть равны лишь 1, 2 или 3. Запишем систему неравенств:

hello_html_42c9796f.gif

Составим таблицу противоположных высказываний:

Прямое высказывание

Противоположное высказывание

а = 1

2 £ a £ 3

с £2

c = 3

2 £ b £ 3

b = 1

Если I зритель угадал, а II и III ошиблись:

hello_html_1c5f189a.gifневерно, так как Авдеев и Васильев не могли занять одинаковые места. Если II зритель угадал, а I и III ошиблись:

hello_html_m40b369af.gifэтот случай не противоречит условию.

Если III зритель угадал, а I и II ошиблись:

hello_html_a1703b0.gifневерно, так как никто не занял первого места.

Следовательно, угадал II зритель, соревнования закончились со следующим результатом: Васильев занял первое место, Семенов – второе место, Авдеев – 3 место.

Задача 6. Аня, Варя и Клава гуляли в парке. Одна из них была в красном платье, другая – в белом, третья – в синем. На вопрос, какое на каждой девушке было платье, они дали ответ: Аня была в красном, Варя – не в красном, Клава – не в синем. В этом ответе одно из утверждений – верное, два – неверные. В каком платье была каждая из девушек?

Решение. Занумеруем цвета: красный цвет – 1, белый – 2, синий – 3. Обозначим через а цвет платья Ани, через b – цвет платья Вари, и через с – цвет платья Клавы. Запишем условие задачи с помощью неравенств:

hello_html_m2232e7aa.gifПолучилась та же самая система, что и в предыдущей задаче. Рассмотрев три случая, в которых одно утверждение верно, а два других неверны, можно сразу сказать, что а = 3, b = 1, с = 2. Значит, Аня была в синем платье, Варя – в красном, а Клава – в белом.

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

Задача 7. Разбирается дело Брауна, Джонса и Смита. Один из них совершил преступление. В ходе следствия каждый из них сделал по два заявления. Браун: «Я не делал этого. Джонс не делал этого». Смит: «Я не делал этого. Это сделал Браун». Джонс: «Браун не делал этого. Это сделал Смит». Потом оказалось, что один из них дважды сказал правду, другой – дважды солгал, третий – раз сказал правду, раз солгал. Кто совершил преступление ? (Ответ: Браун.)

Задача 7. Команды А, Б, В, Г и Д участвовали в эстафете. До соревнований пять болельщиков высказали следующие прогнозы:

1) Команда Д займет 1 место, команда В – 2;

2) Команда А займет 2 место, команда Г – 4;

3) Команда В займет 3 место, команда Д – 5;

4) Команда В займет 1 место, команда Г – 4;

5) Команда А займет 2 место, команда В – 3.

В каждом прогнозе одна часть подтвердилась, а другая – нет. Какое место заняла каждая из команд? (Ответ: Д – 1, Б – 2, В – 3, Г – 4, А – 5).

Задача 8. В финал чемпионата Европы выходили две команды. До соревнований пять болельщиков высказали прогнозы, что в финал выйдут команды: 1) Франции и Голландии, 2) Бельгии и Италии, 3) Бельгии и Франции, 4) Англии и Голландии, 5) Голландии и Италии. Один прогноз оказался полностью неверным, а в остальных была правильно названа только одна из команд-финалисток. Какие команды вышли в финал? (Ответ: Италия, Франция).

Задача 9. Волейбольные команды А, Б, В, Г, Д, и Е разыгрывали первенство. известно, что команда А отстала от Б на три места, команда В оказалась между Г и Д, команда Е опередила Б, но отстала от Д. Какое место заняла каждая из команд? (Ответ: Д – 1, Е – 2, Б – 3, В – 4, Г – 5, А - 6).

Задача 10. В семье четверо детей. Им 15, 8, 13 и 15 лет. Детей зовут Аня, Боря, Вера и Галя. Сколько лет каждому ребенку, если одна девочка ходит в детский сад, Аня старше Бори и сумма лет Ани и Веры делится на три? (Ответ: Вере – 5, Боре – 8, Ане – 13, Гале – 15).

Задача 11. Марина, Лариса, Жанна и Катя умеют играть на разных инструментах (пианино, виолончели, гитаре, скрипке), но каждая только на одном. Они же знают иностранные языки (английский, французский, немецкий, испанский), но каждая только один. Девушка, которая играет на гитаре, говорит по-испански. Лариса не играет ни на скрипке, ни на виолончели, и не знает английского языка. Марина не играет ни на скрипке, ни на виолончели, и не знает ни немецкого, ни английского языка. Девушка, которая говорит по-немецки, не играет на виолончели. Жанна знает французский язык, но не играет на скрипке. Кто на каком инструменте играет? Кто какой знает язык? (Ответ: Лариса – пианино, немецкий; Жанна – виолончель, французский; Марина – гитара, испанский; Катя – скрипка, английский).

Задача 12. О некотором числе высказаны следующие утверждения:

- это число простое;

- это число 9;

- это число четное;

- это число 15.

Попробуйте узнать, что это за число, если два из этих утверждений истинны, а два других – ложны.

Задача 13. «Одни лишь А и Б».(из книги «Игра и логика», Д.Бизам, Я.Герцег, перевод с венгерского Ю.А.Данилова). Познакомим читателя с тремя людьми: Аладаром, Белой и Балашом. Один из них аптекарь, другой – бухгалтер, третий – агроном. Один живет в Будапеште, другой – в Бекешчабе, третий – в Асоде. Требуется выяснить, кто где живет и у кого какая профессия. Известно лишь, что:

1) Балаш бывает в Будапеште лишь наездами, и то весьма редко, хотя все его родственники постоянно живут в столице;

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

3) жена аптекаря доводится Балашу младшей сестрой.

(Ответ: Балаш – бухгалтер, Бекешчаба; Бела – аптекарь, Будапешт; Аладар – агроном, Асод).








Краткое описание документа:

      Программа элективного курса  по математике «Элементы математической логики»  составлена на основе авторской программы Е.А.Семенко «Элементы математической логики», - Краснодар, 2004г, и рассчитана на 17 часов для учащихся 9 классов в рамках предпрофильной подготовки.

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

Автор
Дата добавления 21.01.2015
Раздел Математика
Подраздел Рабочие программы
Просмотров739
Номер материала 326677
Получить свидетельство о публикации

Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Похожие материалы

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