Игошин математическая логика упражнения

Задачи и упражнения по математической логике и теории алгоритмов, Игошин В.И., 2007

Задачи и упражнения по математической логике и теории алгоритмов, Игошин В.И., 2007.

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

Примеры.
Определите значения истинности следующих высказываний:
а) Если 9 делится на 3, то 4 делится на 2;
б) Если 11 делится на 6, то 11 делится на 3;
в) Если 15 делится на 6, то 15 делится на 3;
г) Если 15 делится на 3, то 15 делится на 6;
д) Если Саратов расположен на Неве, то слоны — насекомые;
е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3;
ж) 4 > 5 тогда и только тогда, когда -4 > -5;
з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3;
и) 15 делится на 5 тогда и только тогда, когда 15 делится на 4;
к) Если 12 делится на 6, то 12 делится на 3;
л) 11 делится на 6 тогда и только тогда, когда 11 делится на 3.

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

ОГЛАВЛЕНИЕ.
Предисловие.
Глава I. АЛГЕБРА ВЫСКАЗЫВАНИЙ.
§1. Основные понятия алгебры высказываний.
Высказывания и операции над ними (6). Формулы алгебры высказываний (15). Тавтологии алгебры высказываний (20). Логическое следование (24). Равносильность формул (33). Упрощение систем высказываний (39).
§2. Нормальные формы для формул алгебры высказываний и их применение.
Отыскание нормальных форм (41). Применение нормальных форм (47). Нахождение следствий из посылок (57). Нахождение посылок для данных следствий (62).
§3. Приложение алгебры высказываний к логико-математической практике.
Обратная и противоположная теоремы (68). Принцип полной дизъюнкции (75). Необходимые и достаточные условия (76). Упрощение систем высказываний (81). Правильные и неправильные рассуждения (82). Нахождение всех следствий из посылок (85). Нахождение посылок для следствий (87). «Логические» задачи (88).
Глава II. БУЛЕВЫ ФУНКЦИИ.
§4. Понятие булевой функции и свойства булевых функций.
Число булевых функций (93). Равенство булевых функций (96). Свойства булевых функций (98).
§5. Специальные классы булевых функций.
Полиномы Жегалкина и линейные булевы функции (101). Двойственность и самодвойственные булевы функции (107). Монотонные булевы функции (113). Булевы функции, сохраняющие нуль и сохраняющие единицу (120).
§6. Полные системы и функционально замкнутые классы булевых функций.
Полные и неполные системы булевых функций (123). Применение теоремы Поста (125). Функционально замкнутые классы булевых функций (127). Базисы булевых функций (128).
§7. Применение булевых функций к релейно-контактным схемам.
Анализ релейно-контактных схем (130). Синтез релейно-контактных схем (138).
Глава III. ФОРМАЛИЗОВАННОЕ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ.
§8. Построение формализованного исчисления высказываний и исследование системы аксиом на независимость.
Построение выводов из аксиом (144). Построение выводов из гипотез (146). Теорема о дедукции и ее применение (150). Производные правила вывода и их применение (154). Независимость системы аксиом (157).
Глава IV. ЛОГИКА ПРЕДИКАТОВ.
§9. Основные понятия логики предикатов.
Понятие предиката и операции нал предикатами (162). Множество истинности предиката (167). Равносильность и следование предикатов (179). Формулы лотки предикатов, их интерпретация и классификация (182). Равносильность формул логики предикатов (188). Тавтологии лотки предикатов (191). Равносильные преобразования формул (195). Проблемы разрешимости для общезначимости и выполнимости формул (197). Логическое следование формул лотки предикатов (200).
§10. Применение логики предикатов к логико-математической практике.
Записи на языке лотки предикатов (204). Правильные и неправильные рассуждения (208). Лотка предикатов и алгебра множеств (210). Равносильные преобразования неравенств и уравнений при их решении (212).
§11. Формализованное исчисление предикатов.
Построение выводов из аксиом (214). Построение выводов из гипотез (217). Теорема о дедукции и ее применение (218).
Глава V. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.
§12. Машины Тьюринга.
Применение машин Тьюринга к словам (222). Конструирование машин Тьюринга (229). Вычислимые по Тьюрингу функции (237).
§13. Рекурсивные функции.
Примитивно рекурсивные функции (240). Примитивно рекурсивные предикаты (246). Оператор минимизации. Общерекурсивные и частично рекурсивные функции (247).
§14. Нормальные алгоритмы Маркова.
Марковские подстановки (249). Нормальные алгоритмы и их применение к словам (250). Нормально вычислимые функции (253).
Ответы.
Список литературы.

Читайте также:  Внимательность как улучшить упражнения

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Задачи и упражнения по математической логике и теории алгоритмов, Игошин В.И., 2007 — fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России. Купить эту книгу

Источник

Сборник задач по математической логике и теории алгоритмов, Игошин В.И., 2019

Сборник задач по математической логике и теории алгоритмов, Игошин В.И., 2019.

Сборник содержит задачи и упражнения по всем традиционным разделам курса математической логики и теории алгоритмов: 1. Содержательная логика высказываний; II. Булевы функции; III. Содержательная логика предикатов; IV. Формальные логические теории; V. Элементы теории алгоритмов. В каждом параграфе подробно рассматриваются разнообразные типовые примеры и даются многочисленные задачи разного уровня сложности для самостоятельного решения. Теоретический материал изложен в учебниках: Игошин В.И. Математическая логика: Учеб, пособие. М.: ИНФРА-М, 2012. 399 с. + CD-R. (Высшее образование); Игошин В.И. Теория алгоритмов: Учеб, пособие. М.: ИНФРА-М, 2012. 318 с. (Высшее образование).
Для студентов университетов, технических и педагогических вузов, обучающихся как на уровне бакалавриата, так и на уровне магистратуры по направлениям «Математика», «Информатика», «Прикладная математика и информатика», «Математика и компьютерные науки», «Бизнес-информатика», «Математик-педагог», «Учитель математики».

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

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

ОГЛАВЛЕНИЕ.
ПРЕДИСЛОВИЕ.
Глава I СОДЕРЖАТЕЛЬНАЯ ЛОГИКА ВЫСКАЗЫВАНИЙ.
§1. Основные понятия алгебры высказываний.
Формулы алгебры высказываний.
Тавтологии алгебры высказываний.
Равносильность формул алгебры высказываний.
Упрощение систем высказываний.
Логическое следование формул алгебры высказываний.
§2. Нормальные формы для формул алгебры высказываний и их применение.
Отыскание нормальных форм.
Применение нормальных форм.
Нахождение следствий из посылок.
Нахождение посылок для данных следствий.
§3. Приложения алгебры высказываний к логико-математической практике.
Обратная и противоположная теоремы.
Принцип полной дизъюнкции.
Упрощение систем высказываний.
Правильные и неправильные рассуждения.
Задачи Льюиса Кэрола.
Нахождение всех следствий из посылок.
Нахождение посылок для следствий.
«Логические» задачи.
Глава II БУЛЕВЫ ФУНКЦИИ.
§4. Понятие булевой функции и свойства булевых функций.
Число булевых функций.
Равенство и сравнение булевых функций.
Существенные и несущественные аргументы булевых функций.
Симметрия булевых функций.
Некоторые соотношения для булевых функций.
Свойства булевых функций.
§5. Специальные классы булевых функций.
Полиномы Жегалкина и линейные булевы функции.
Двойственность и самодвойственные булевы функции.
Монотонные булевы функции.
Булевы функции, сохраняющие нуль и сохраняющие единицу.
§6. Полные системы и функционально замкнутые классы булевых функций.
Полные и неполные системы булевых функций.
Применение теоремы Поста.
Функционально замкнутые классы булевых функций.
Базисы булевых функций.
§7. Применение булевых функций к релейно-контактным схемам.
Анализ релейно-контактных схем.
Синтез релейно-контактных схем.
§8. Применение булевых функций к логическим схемам из функциональных элементов (функциональным схемам).
Анализ функциональных схем.
Синтез функциональных схем.
Глава III СОДЕРЖАТЕЛЬНАЯ ЛОГИКА ПРЕДИКАТОВ.
§9. Основные понятия логики предикатов.
Понятие предиката и операции над предикатами.
Множество истинности предиката.
Равносильность и следование предикатов.
Формулы логики предикатов, их интерпретация и классификация.
Равносильность формул логики предикатов.
Тавтологии логики предикатов.
Равносильные преобразования формул.
Проблемы разрешимости для общезначимости и выполнимости формул.
Логическое следование формул логики предикатов.
§10. Применение логики предикатов к логико-математической практике.
Записи на языке логики предикатов.
Правильные и неправильные рассуждения.
Логика предикатов и алгебра множеств.
Равносильные преобразования неравенств и уравнений при их решении.
Глава IV ФОРМАЛЬНЫЕ ЛОГИЧЕСКИЕ ТЕОРИИ.
§11. Формализованное исчисление высказываний.
Построение выводов из аксиом.
Построение выводов из гипотез.
Теорема о дедукции и ее применение.
Производные правила вывода.
Независимость системы аксиом Генцена—Клини.
Полнота, непротиворечивость и разрешимость исчисления высказываний, построенного на базе системы аксиом Генцена—Клини.
§12. Формализованное исчисление предикатов.
Построение выводов из аксиом.
Построение выводов из гипотез.
Теорема о дедукции и ее применение.
Глава V ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.
§13. Машины Тьюринга и вычислимые по Тьюрингу функции.
§14. Рекурсивные функции.
Примитивно рекурсивные функции.
Примитивно рекурсивные предикаты.
Оператор минимизации. Общерекурсивные и частично рекурсивные функции.
§15. Нормальные алгоритмы Маркова и нормально вычислимые функции.
Марковские подстановки.
Нормальные алгоритмы и их применение к словам.
Нормально вычислимые функции.
ОТВЕТЫ.
СПИСОК ЛИТЕРАТУРЫ.

Читайте также:  Интересные упражнения для команды

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Сборник задач по математической логике и теории алгоритмов, Игошин В.И., 2019 — fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России. Купить эту книгу

Источник

В.И. Игошин — Задачи и упражнения по математической логике и теории алгоритмов — 2007

Описание файла

DJVU-файл из архива «В.И. Игошин — Задачи и упражнения по математической логике и теории алгоритмов — 2007″, который расположен в категории » «. Всё это находится в предмете «математическая логика» из раздела «», которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе «книги и методические указания», в предмете «математическая логика» в общих файлах.

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла

ВБ!СШЕЕ ПРОФЕССИОНАПБНОЕ ОБРАЗОВАНИЕ В. И. ИГОШИН ЗАДАЧИ И УПРАЖНЕНИЯ ПО МАТЕМАТИЧЕСКОИ ЛОГИКЕ И ТЕОРИИ АЛГОРИТМОВ Допущено Министерством образования Российской Федерации в кочеопве учебного пособия дяя студентов высшик учебнык заведений, обучающикся по специальности Оз2100 еМатематина э 3-е издание, стереотипное Мосина т1здатепиский центр «гькадетик. 2007 УДК 510.6(076.5) ББК 22.12я73 И269 Рецензенты: декан факультета «Прикладная математика » Московского государственного открытого университета, д-р физ.-мат.

наук, проф. В.Х Кулиев; зав. кафедрой «Теоретические основы компьютерной безопасности и криптографии » Саратовского госуларственного университета, проф. В.Н. Салий Игошин В.И. И269 Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. вмсш. учеб. заведений / В.И. Игошин. — 3-е изд., стер.

— М.: Издательский центр «Академия » , 2007. — 304 с. 18ВХ 5-7695-3728-0 Сборник содержит задачи и упражнения по всем традиционным разделам курса математической логики и теории алгоритмов. В кюкдом параграфе подробно рассмотрены разнообразные типовые примеры и приведены многочисленные задачи разного уровня сложности для самостоятельного решения. Теоретический материал изложен в учебном пособии: Игошин В.И. Математическая логика и теория алгоритмов.

— М.: Издательский центр «Академия » , 2004. Для студентов университетов, технических и педагогических вузов, обучаюшихся по специальностям «Математика » , «Прикладная математика*. УДК 510.6(076.5) ББК 22.12я73 Оригинал-макет данного издания является собственностью Издательского центра «Академия » , и его воспроизведение любым способом без согласия правообладателя заврещается © Игошин В.И.„2005 © Издательский центр «Академия » , 2005 !ВВГ4 5-7855-3728-0 ПРЕДИСЛОВИЕ Обучение математике немыслимо без решения задач.

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

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

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

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

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

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

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

Читайте также:  К динамическим упражнениям аэробного характера не относятся

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

Сборник задач призван осуществить практическую поддержку теоретических курсов математической логики и теории алгоритмов, изучаемых по учебному пособию’ (в дальнейшем будем называть его «Учебник » ), Настоящий сборник представляет собой существенно переработанный и расширенный вариант ранее изданного задачника: Игошин В.И. Задачник-практикум по математической логике. — М., 1986. Сборник состоит из четырнадцати параграфов, сгруппированных в пять глав: 1. Алгебра высказываний; П.

Булевы функции; П1. Формализованное исчисление высказываний; 1Ч. Логика предикатов; Ч. Элементы теории алгоритмов. Каждый параграф разбит на тематические пункты (без нумерации). Весь параграф или некоторые его пункты предваряются краткими сведениями теоретического характера, в которых приводится система понятий и обозначений, используемых в параграфе.

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

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

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

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

1, если высказывание Р истинно, 10, если высказывание Р ложно.

Значение А(Р) называется логическим значением или значением истинности высказывания Р. Над высказываниями определяются следующие основные операции (логические связки), которые позволяют из имеющихся высказываний строить новые: 1) отрицание: -зР(читается «не Р » ); 2) конъюнкция: Р к 0 (читается «Р и Д » , используется также иное обозначение: Р&. Д); 3) диэъюнкция: Р ч 0 (читается «Р или 0 » ); 4) импликацил: Р » 0 (читается «если Р, то Д » , или «из Р следует Д » , или «Р достаточно для Д » , или «Д необходимо для Р » ); 5) эквивалентность: Р++ 0 (читается «Р равносильно Д » , или «Р тогда и только тогда, когда Д » , или «Р необходимо и достаточно для Д » ).

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

0= 1; 1 ч 1= 1;0-+0= 1; 0-+ 1=1; 1-+ 0=0; 1-+ 1= 1. 1.1. Какие из следующих предложений являются высказываниями: а) Москва — столица России; б) Студент механико-математического факультета университета; в) Треугольник АВС подобен треугольнику А’В’С’; г) Луна есть спугник Марса; д) 2+2 — 5; е) Кислород — газ; ж) Каша — вкусное блюдо; з) Математика — интересный предмет; и) Картины Пикассо слишком абстрактны; к) Железо тяжелее свинца; л) «Да здравствуют музы! » ; м) Треугольник называется равносторонним, если все его стороны равны; н) Если в треугольнике все углы’равны, то он равносторонний; о) Сегодня плохая погода; п) В романе А.С.

Источник

Поделиться с друзьями
Упражнения в нажей жизни