Методические указания к выполнению курсовой работы по дисциплине " Дискретная математика"

Вид материала

Содержание

Нтуу «кпі»
Цели и порядок выполнения курсовой работы
Оформление пояснительной записки
2.2. Содержание разделов
Краткие теоретические сведения
Алгоритмические схемы и проблема вычислимости
Национальный технический университет украины
2. Алгоритмические схемы и проблемы вычислимости…

Подобный материал:

Министерство образования и науки Украины

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ

“КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ”

Кафедра прикладной математики

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению курсовой работы по дисциплине

" Дискретная математика"

на тему : "Доказательство логического следования

и алгоритмические схемы"

КИЕВ

2001

Таран Т.А., Темнікова О.Л.

Методичні вказівки до виконання курсової роботи по дисципліні " Дискретна математика" на тему: "Доказ логічного слідування і алгоритмічні схеми"

для студентів спеціальності «Прикладна математика».

Затверджено на засіданні кафедри
прикладної математики
НТУУ «КПІ»
протокол № від

Содержание

1. Цель и порядок выполнения курсовой работы…………………………..….4

2. Оформление пояснительной записки……………….………………….…….4

2.1. Общие положения…………………………….….………………...4

2.2. Содержание разделов……………………………………………....5

Литература…………………………………………………….…………………..6

Приложение 1. Титульный лист курсовой работы…………..…………………7

Приложение 2. Лист содержания курсовой работы………..…………………..8

Приложение 3. Варианты заданий для первой части курсовой работы: формализация и решение логических задач…………………..9

Приложение 4. Варианты заданий для второй части курсовой работы: алгоритмические схемы и проблема вычислимости…..…….14

"Своенравная и непокорная, логика отныне укрощена и обуздана."

Кэрролл Л.

ЦЕЛИ И ПОРЯДОК ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ

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

Курсовая работа состоит из двух независимых частей:

Формализация и решение логических задач - по материалам 2^го семестра изучения курса "Дискретной математики".
Алгоритмические схемы и проблема вычислимости - по материалам 3^го (текущего) семестра.

Выполнение курсовой работы разбивается на несколько этапов:

выдача задания;
изучение рекомендованной литературы и освоение методов решения задачи;
формализация логической задачи на языке теории предикатов 1-го порядка;

4. доказательство логического следования.

4.2. построение вывода в теории К.

4.1. доказательство логического следования методом редукции.

4.3. доказательство логического следования методом резолюций.

4.4. описание задачи на языке клауз.

4.5 построение дерева логического вывода.

5. выполнение второй части курсовой работы - построение алгоритмических схем;

5.1. составление программы для машины Тьюринга;

5.2. составление нормального алгоритма Маркова;

5.3. подготовка контрольных примеров для проверки работоспособности алгоритмов;

6. оформление пояснительной записки и сдача ее преподавателю;

7. защита курсовой работы перед комиссией.

Выдача задания.

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

Оформление пояснительной записки и сдача ее преподавателю.

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

Пояснительную записку необходимо сдать за несколько дней до защиты курсовой работы преподавателю для ознакомления. Примерные сроки сдачи пояснительных записок : с 1 по 15 декабря.

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

ОФОРМЛЕНИЕ ПОЯСНИТЕЛЬНОЙ ЗАПИСКИ

2.1. Общие положения

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

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

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

2.2. Содержание разделов

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

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

Подраздел "Постановка задачи" должен содержать описание индивидуальной логической задачи согласно номеру варианта и ее формализацию в теории предикатов.

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

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

Вторая часть курсовой работы - " Алгоритмические схемы и проблема вычислимости".

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

Подразделы "Машина Тьюринга" и " Нормальный алгоритм Маркова " посвящены построению двух типов алгоритмических схем. В пунктах 2.2.1. и 2.3.1. "Краткие теоретические сведения" необходимо привести основные понятия теории алгоритмов, отличительные особенности и принципы построения соответствующих типов алгоритмов. Пункты 2.2.2. и 2.3.2. должны содержать непосредственно описания программы для машины Тьюринга и нормального алгоритма Маркова для поставленной задачи. Демонстрация работы программы для машины Тьюринга и нормального алгоритма Маркова проводится на различных примерах, охватывающих всевозможные комбинации входных данных и различные варианты активизируемых состояний, в соответствующих двум алгоритмическим схемам пунктах "Пример выполнения программы".

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

В разделе "Литература" приводится список используемой литературы.

Литература

Глушков В.М. Введение в кибернентику. - К.: Изд-во АН УССР, 1964.
Гжегорчик Ф. Популярная логика. - М.: Наука, 1975.
Горбатов В.А. Основы дискретной математики: Учеб. пособие для студентов ВУЗов.- М.: Высшая. школа, 1986.
Кэрролл Л. История с узелками. - М.: Мир, 1973.
Кэрролл Л. Логическая игра: Библиотечка "Квант", выпуск 73 - М. : Наука, 1991.
Мальцев А.И. Алгебраические системы. - М.: Наука, 1975.
Мендельсон Э. Введение в математическую логику. - М.: Наука, 1976.
Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: МАИ, 1992.
Новиков П.С. Элементы математической логики. - М.: Физматгиз, 1959.
Таран Т.А. Основы дискретной математики: Учебное пособие - К.: Просвіта, 1998.
Трахтенброт Б.А. Алгоритмы и вычислительные автоматы - М.: "Сов.радио", 1974.
Хювенен Э., Сеппянен Й. Мир ЛИСПА. В 2-х т. Т.2: Методы и системы программирования. - М.: Мир, 1990.
Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. / Под ред. С.Ю. Маслова. - М.: Наука, 1983.
Черч А. Введение в математическую логику. - М.: ИЛ. т.1. 1961.

Приложение 1. Титульный лист курсовой работы

Министерство образования и науки Украины

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ

“КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ”

Кафедра прикладной математики

Курсовая работа по дисциплине " Дискретная математика"

на тему : "Доказательство логического следования

и алгоритмические схемы"

Руководитель: Выполнил студент

<ФИО>

группы КМ-

№ зач.книжки

Защищен с оценкой___________

<год> - киев

Приложение 2. Лист содержания курсовой работы

СОДЕРЖАНИЕ

Введение…………………………………………………………..

1. Доказательство логического следования………………….

1.1 Постановка задачи…………………………………………

1.1.1. Индивидуальное задание……………………………

1.1.2. Формализация задачи……………………………….

1.2. Доказательство логического следования в исчислении

предикатов первого порядка……………………………

1.2.1.Краткие теоретические сведения…………………..

1.2.2. Формальный вывод в теории К………………….

1.3. Неформальное доказательство………………………….

1.3.1. Краткие теоретические сведения………………….

1.3.2. Доказательство методом редукции……………….

1.4. Доказательство методом резолюций…………………...

1.4.1. Краткие теоретические сведения…………………

1.4.2. Резолютивный метод……………………………….

1.4.3. Описание задачи на языке клауз.…………….……

1.4.4. Построение дерева логического вывода………….

2. Алгоритмические схемы и проблемы вычислимости…

2.1. Постановка задачи………………………………………

2.2. Машина Тьюринга………………………………………

2.2.1. Краткие теоретические сведения…………………..

2.2.2. Программа для машины Тьюринга………………

2.2.3. Пример выполнения программы…………………

2.3. Нормальный алгоритм Маркова……………………….

2.3.1. Краткие теоретические сведения………..………..

2.3.2. Нормальный алгоритм Маркова для поставленной задачи………………………………………………

2.3.3. Пример выполнения программы…………………

3. Выводы………………………………………………………..

Литература………………………………………………………

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

1 Область определения: животные.

1. Я люблю всех животных, которые принадлежат мне. 2. Собаки грызут кости. 3. Ни одно животное я не пускаю к себе в кабинет, если оно не "служит", когда его об этом просят. 4. Все животные во дворе принадлежат мне. 5. Всем животным, которых я люблю, разрешается входить ко мне в кабинет. 6. Единственные животные, которые "служат", если их попросить, – собаки.

Вывод: все животные в этом дворе грызут кости.

2 Область определения: дни.

1. Я не называю день "несчастливым", если Робинсон вежлив со мной. 2. Среды всегда бывают пасмурными днями. 3. Если люди берут с собой зонты, день никогда не бывает солнечным. 4. Единственный день недели, когда Робинсон невежлив со мной,– среда. 5. Всякий возьмет с собой зонт, если идет дождь. 6. Мои "счастливые" дни неизменно оказываются солнечными.

Вывод: дождливые дни пасмурны.

3 Область определения: люди.

1. Никто не забудет причесаться, если он отправляется на бал. 2. Нельзя сказать, что человек выглядит превосходно, если он неопрятен. 3. Курильщики опиума утрачивают контроль над собой. 4. Причесанный человек выглядит превосходно. 5. Никто не наденет белых лайковых перчаток, если он не отправляется на бал. 6. Человек всегда неопрятен, если он утратил контроль над собой.

Вывод: курильщики опиума никогда не носят белых лайковых перчаток.

4 Область определения: представленные здесь картины.

1. Ни одна из представленных здесь картин, кроме батальных, не представляет ценности. 2. Ни одна из картин, вывешенных без рам, не покрыта лаком. 3. Все батальные картины написаны маслом. 4. Все распроданные картины представляют ценность. 5. Все картины английских мастеров покрыты лаком. 6. Все картины, которые были вывешены в рамах, проданы.

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

5 Область определения: мои мысли.

1. Любая мысль, которую нельзя выразить в виде силлогизма, поистине смешна. 2. Моя мечта о сдобных булочках не стоит того, чтобы ее записывать на бумаге. 3. Ни одну мою несбыточную мечту нельзя выразить в виде силлогизма. 4. Мне не приходило в голову ни одной действительно смешной мысли, о которой бы я не сообщил своему поверенному. 5. Я только и мечтаю, что о сдобных булочках. 6. Я никогда не высказывал своему поверенному ни одной мысли, если она не стоила того, чтобы ее записать на бумагу.

Вывод: все мои мечты сбылись.

6 Область определения: предметы.

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

Вывод: радугу не стоит воспевать в стихах.

7 Область определения: авторы литературных произведений.

1. Все авторы литературных произведений, постигшие природу человека, умные люди. 2. Ни одного автора нельзя считать истинным поэтом, если он не способен волновать сердца людей. 3. Шекспир написал "Гамлета". 4. Ни один автор, не постигший природу человека, не способен волновать сердца людей. 5. Только истинный поэт мог написать "Гамлета".

Вывод: Шекспир был умным человеком.

8 Область определения: люди этого колледжа.

1. Все выпускники Итона в этом колледже играют в крикет. 2. Никто, кроме преподавателей, не обедает за верхним столом. 3. Ни один из тех, кто играет в крикет, не умеет грести. 4. Все мои друзья в этом колледже – выпускники Итона. 5. Все преподаватели – прекрасные гребцы.

Вывод: все мои друзья обедают за нижним столом.

9 Область определения: люди.

1. Те, кто нарушает свои обещания, не заслуживают доверия. 2. Любители выпить очень общительны. 3. Человек, выполняющий свои обещания, честен. 4. Ни один трезвенник не ростовщик. 5. Тому, кто очень общителен, всегда можно верить.

Вывод: ни один ростовщик не бывает нечестен.

10 Область определения: плоды на этой выставке.

1. Все плоды на этой выставке, которые не будут удостоены награды, являются собственностью организационного комитета. 2. Ни один из представленных мной персиков не удостоен награды. 3. Ни один из плодов, распроданных после закрытия выставки, не был незрелым. 4. Ни один из спелых плодов не был выращен в теплице. 5. Все плоды, принадлежащие оргкомитету выставки, были распроданы после ее закрытия.

Вывод: ни один из моих персиков не был выращен в теплице.

11 Область определения: поэмы.

1. Ни одна интересная поэма не останется непризнанной людьми с тонким вкусом. 2. Ни одна современная поэма не свободна от аффектации. 3. Все ваши поэмы написаны о мыльных пузырях. 4. Ни одна аффектированная поэма не находит признания у людей с тонким вкусом. 5. Ни одна древняя поэма не написана о мыльных пузырях.

Вывод: все ваши поэмы не интересны.

12 Область определения: книги в этой библиотеке.

1. Единственные книги в этой библиотеке, которые я не рекомендую читать, безнравственны по своему содержанию. 2. Все книги в твердых переплетах обладают выдающимися литературными достоинствами. 3. Все романы вполне нравственны по своему содержанию. 4. Я не рекомендую вам читать ни одну из книг в мягкой обложке.

Вывод: все романы в этой библиотеке обладают выдающимися литературными достоинствами.

13 Область определения: вещи.

1. Все вещи, продаваемые на улице, не имеют особой ценности. 2. Только дрянь можно купить за грош. 3. Яйца большой гагарки представляют большую ценность. 4. Лишь то, что продается на улице, и есть настоящая дрянь.

Вывод: яйцо большой гагарки за грош не купишь.

14 Область определения: мои дети.

1. Все мои сыновья стройны. 2. Никто из моих детей не здоров, если он не делает утренней зарядки. 3. Все обжоры среди моих детей страдают ожирением. 4. Ни одна из моих дочерей не делает утренней зарядки.

Вывод: все мои дети-обжоры не здоровы.

15 Области определения: люди и литературные произведения.

1. Шекспир писал только стихи. 2. Только те, кто пишет только стихи, – поэты. 3. Все поэты любят читать стихи. 4. Каждый, кто любит читать стихи, любит читать стихи Шекспира.

Следовательно, Шекспир любил почитывать свои произведения.

16 Область определения: птицы.

1. Ни одна птица, кроме страуса, не достигает 9 футов роста. 2. В этом птичнике нет птиц, которые принадлежали бы кому-нибудь, кроме меня. 3. Ни один страус не питается пирогами с начинкой. 4. У меня нет птиц, которые достигали бы 9 футов роста.

Вывод: ни одна птица в этом птичнике не питается пирогами с начинкою.

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

1. Ни у одной продаваемой здесь книги, кроме тех книг, которые выставлены на витрине, нет золоченного обреза. 2. Все авторские издания снабжены красным ярлычком. 3. Все книги с авторскими ярлычками продаются по цене 5 шиллингов и выше. 4. Лишь авторские издания выставляются на витрине.

Вывод: ни одна продаваемая здесь книга не имеет золоченного обреза, если она идет по цене 5 шиллингов и выше.

18 Область определения: животные.

1. Животные, которые не брыкаются, всегда невозмутимы. 2. У осла нет рогов. 3. Буйвол всегда может перебросить вас через ограду. 4. Животных, которые не брыкаются, не легко проглотить. 5. Животное, у которого нет рогов, не может перебросить вас через ограду. 6. Все животные, кроме буйвола, легко переходят в ярость.

Вывод: проглотить осла - дело нелегкое.

19 Область определения: котята.

1. Котенок, который любит рыбу, поддается дрессировке. 2. Котенок без хвоста не станет играть с гориллой. 3. Котята с усами всегда любят рыбу. 4. У котенка, поддающегося дрессировке, не бывает зеленых глаз. 5. Если у котенка нет хвоста, то у него нет и усов.

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

20 Область определения: рыбы .

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

Вывод: ни одна большая рыба не бывает недоброй по отношению к детям.

21 Область определения: вещи .

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

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

22 Область определения: живые существа .

1. Всякий, кто танцует на канате не пользуется почтением. 2. Не танцуют на канате только старики. 3. Смешной вид имеют только те, кто ест пирожки на улице. 4. Всякий, кто ест пирожки на улице, молод душой. 5. Свинка с зонтиком имеет смешной вид.

Вывод: свинка с зонтиком не пользуется почтением.

23 Область определения: мужья .

1. Ни один муж, дарящий жене новые платья, не может быть несговорчивым. 2.Аккуратный муж всегда возвращается домой к чаю. 3. Жене нелегко содержать в порядке одежду мужа, если он имеет обыкновение вешать свою шляпу на газовый рожок. 4. Хороший муж всегда дарит своей жене новые платья. 5. Ни один муж не может не быть несговорчивым, если жена не следит за его одеждой. 6. Неаккуратный муж всегда вешает свою шляпу на газовый рожок.

Вывод: хороший муж всегда возвращается домой к чаю.

24 Область определения: логические задачи, которые я решаю.

1. Если я решаю логическую задачу без ворчания, то можно быть уверенным, что она мне понятна. 2. Посылки в этих соритах расположены не в том порядке, как в привычных мне задачах. 3. Ни одна легкая задача не вызывает у меня головной боли. 4. Я не могу понять задач, в котрорых посылки стоят не в том порядке, к которому я привык. 5. Я никогда не ворчу на задачу, если от нее у меня болит голова.

Вывод:эти сориты очень трудные.

25 Области определений: животные и люди (или живые существа).

1. Ни один дракон, который живет в зоопарке, не является счастливым. 2. Любой зверь, который встречает добрых людей, является счастливым. 3. Люди, которые встречаются в зоопарке – добрые. 4. Звери, которые живут в зоопарке, встречают людей, которые посещают зоопарк.

Следствие: ни один дракон не живет в зоопарке.

26 Область определения: некоторые математические объекты.

1. Для любого множества Х существует множество У большей мощности. 2. Если Х содержится в У, то мощность Х не превышает мощности У. 3. Каждое множество содержится в Z.

Следствие: Z не является множеством.

27 Область определения: живые существа .

1.С теми, кто временами испытывает головокружение, обращаются почтительно. 2. Разумное существо всегда носит с собой зонтик. 3. К неразумным существам относятся без почтения. 4. Ни одно существо не станет брать с собой зонтик, собираясь путешествовать на воздушном шаре.

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

28 Область определения: нечто

1. Нечто, несущее в себе черты чего–то хорошего, хорошо само по себе. 2 . Нечто, несущее в себе черты чего–то плохого, плохо само по себе.3. Война несет в себе черты мира и страдания. 4.Мир хорош, а страдание плохо.

Следствие: некоторые вещи и хороши и плохи.

29 Область определения: люди.

1. Все полисмены в этой округе ужинают у нашей кухарки. 2. Человек с длинными волосами не может не быть поэтом. 3. Амос Джадд никогда не сидел в тюрьме. 4. Все кузены нашей кухарки любят холодную баранину. 5. В этом округе нет других поэтов, кроме полисменов. 6. С нашей кухаркой не ужинает никто, кроме ее кузенов. 7. Все люди с короткими волосами сидели в тюрьме.

Вывод : Амос Джадд любит холодную баранину.

30 Область определения: люди.

1. Ни один прилежный студент не пропускает занятий. 2.Студенты, которые плохо учатся обычно пропускают занятия. 3. Преподаватели любят студентов, которые хорошо учаться. 4.Студент Том - прилежен. Любит ли профессор Смит студента Тома?

31 Область определения: человеческие существа.

1. Все человечество, за исключением моих лакеев, обладает известной долей здравого смысла.. 2. Лишь дети могут питаться одними сладостями. 3. Лишь тот, кто играет в "классы", знает, что такое настоящее счастье. 4. Ни у одного ребенка нет ни доли здравого смысла. 5. Ни один машинист не играет в "классы". 6. Ни об одном моем лакее нельзя сказать, что он не знает, в чем заключается настоящее счастье.

Следствие: ни один машинист не питается одними сладостями.

32 Область определения: небесные тела

1. Каждое небесное тело является либо звездой, либо кометой, либо планетой. Венера – небесное тело, не являющаяся звездой. 2. У комет, расположенных недалеко от солнца, есть хвосты. 3. Венера недалеко от Солнца, но у нее нет хвоста.

Следствие: Венера - планета.

33 Область определения: люди.

1.Таможенные чиновники обыскивают всех въезжающих в нашу страну, кроме высокопоставленных лиц. 2. Никто из высокопоставленных лиц не провозит наркотики. 3. Но, тем не менее, существуют лица, которые при въезде в страну имели при себе наркотики, и, как видно были обысканы своими сообщниками.

Вывод: некоторые таможенники подкупленны наркомафией.

34 Область определения: письма в этой комнате.

1. Все письма в этой комнате, на которых проставлена дата отправления , написаны на голубой бумаге. 2. Ни одно из писем, кроме тех, которые составлены в третьем лице, не написаны черными чернилами. 3. Я регистрирую те письма, которые не могу прочитать. 4. Ни в одном из писем, написанных на одной странице не пропущена дата. 5. Все неперечеркнутые письма написаны черными чернилами. 6. Все письма, написанные Брауном, начинаются со слов "Уважаемый сэр!". 7. Ни одно из писем, написанных более чем на одной странице, не перечеркнуто. 8. Ни одно из писем, начинающихся со слов "Уважаемый сэр!", не написано в третьем лице. 9. Все письма, написанные на голубой бумаге, зарегистрированы мной.

Вывод: я не могу прочитать ни одно из писем, написанных Брауном.

35 Область определения: животные.

1. Животные всегда испытывают смертельную обиду, если я не обращаю на них внимания. 2. Те животные, которые принадлежат мне, находятся на той площадке. 3. Ни одно животное не сможет отгадать загадку, если оно не получило соответствующего образования в школе-интернате. 4. Нт одно животное на той площадке ни барсук. 5. Если животное испытывает смертельную обиду, оно носится с бешенной скоростью и воет. 6. Я никогда не обращаю внимания на животных, которые не принадлежат мне. 7. Ни одно животное, получившее соответствующее образование в школе-интернате, не станет носится с бешенной скоростью и выть.

Вывод: ни один барсук не может отгадать загадки.

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

№ варианта	Построить алгоритм (для) …	в алфавите А={…,…}	Дополнительные сведения и примеры
	вычисления функции f(x)=3x	\|,*	\|\| -> \|\|*\|\|\|\|\|\|
	вычисления функции f(x)= х²	\|,*	\|\|\| ->\|\|\|*\|\|\|\|\|\|\|\|\|
	нахождения наибольшего общего делителя (НОД) двух чисел в унарной системе счисления	\|,*	можно сохранить только результат
	вычисления функции f(x,n)=mod(x-y)	\|,-,=	например, \|\|-\|\|\|=\|, \|\|\|\|\|-\|\|=\|\|\|
	вычисления функции f(x,n)=n*x	*\|,,=**	например, \|\|*\|\|\|=\|\|\|\|\|\|
	получения остатка от деления двух чисел (большего на меньшее)	\|,*	можно сохранить только результат
	получения целого от деления двух чисел (большего на меньшее)	\|,*	можно сохранить только результат
	перевода чисел из унарной системы счисления в десятичную		можно сохранить только результат
	вычисления функции сложения в двоичной системе счисления f(x,y)=x+y (с переносом 1)	1,0,=,+	на вход подаётся слово в виде =x+y , где x и y двоичные числа одинаковой длины. Результат записывается слева.
	вычисления функции f(x,y)=x+y (сложение по модулю 2)	1,0,=,+	на вход подаётся слово в виде x+y= , где x и y двоичные числа одинаковой длины. Результат записывается справа.
	вычисляющий предикат P(x,y)=T, если x>y , и P(x,y)=F , если x<=y	1,0,*	x,y - двоичные числа с одинаковым количеством разрядов. Результат - да/нет.
	вычисления конъюнкции двух двоичных чисел (поразрядная)	1,0,&,=	числа x и y имеют одинаковую длину
	вычисления дизъюнкции двух двоичных чисел (поразрядная)	1,0,,=	числа x и y имеют одинаковую длину
	найти двоичное отрицательное слово	1,0,*	0110 -> 1010
	сдвига влево (на один разряд) числа в двоичной системе счисления	1,0,*	можно сохранить только результат
	циклического сдвига (на один разряд) числа в двоичной системе счисления - вправо	1,0,*	можно сохранить только результат
	циклического сдвига (на один разряд) числа в двоичной системе счисления - влево	1,0,*	можно сохранить только результат
	сдвига вправо (на один разряд) числа в двоичной системе счисления	1,0,*	можно сохранить только результат
	сдвига влево числа в двоичной системе счисления на заданное число разрядов	1,0,*	вход <к-во разрядов>*<число> можно сохранить только результат
	сдвига вправо числа в двоичной системе счисления на заданное число разрядов	1,0,*	можно сохранить только результат
	циклического сдвига числа в двоичной системе счисления вправо на заданное число разрядов	1,0,*	можно сохранить только результат
	циклического сдвига числа в двоичной системе счисления влево на заданное число разрядов	1,0,*	можно сохранить только результат
	определение максимума из двух чисел в двоичной системе счисления	*1,0,,=**	111*01=111
	определение минимума из двух чисел в двоичной системе счисления	*1,0,,=**	111*001=001
	определение равенства (эквива-лентности) двух чисел двоичной системы счисления	*1,0,,=**	например, 101101-> ДА, 101110->НЕТ
	осуществляющий копирование слова	a,b,с,*	например, babbс -> babbс* babbс
	упорядочение слов	a,b,c	например, bacbcab -> aabbbcc
	осуществляющий замену первого вхождения подслова P на подслово Q в слове W	*a,b,,=**	Слова P (bab) и Q (aba) имеют одинаковую длину. bababababaaaba=abaaaaba
	подсчитывающий количество вхождений подслова P в слове W	*a,b,,\|,=**	P*W=<количество> Результат записывается в унарной системе счисления
	подсчитывающий количество букв в исходном слове	*a,b,,\|**	например, abb -> abb*\|\|\|
	подсчитывающий количество вхождений буквы a в слове W	*a,b,,\|**	например, abb -> abb*\|
	распознающий слово, являющееся палиндромом	a,b	например, abba,aa,aba -ДА abab,ba - НЕТ
	выделения подслова ab в слове W	a,b,*	baabaabb -> baabaabb или -> baab
	подсчитывающий количество вхождений упорядоченной пары ab в словo W	a,b,\|,=	например, abbababa -> abbababa*\|\|\|
	прочитать слово в обратном порядке	a,b,с,*	baсbaa -> baсbaa*aabсab или -> aabсab

Blog

Методические указания к выполнению курсовой работы по дисциплине " Дискретная математика"

Содержание