2.Виды множества. Способы задания. Мощность множества.

СМ. Билет №2 1 вопрос

Билет №13

1.Великие учёные, которые внесли вклад в развитие математической логики ( не менее 5 перечислить; о двоих по выбору рассказать подробно.)

См. Билет №3 вопрос 2

2.Машина Тьюринга

См. Билет №1 Вопрос 2

Билет №14

1. Декартово произведение множеств.

См. Билет №8 1 вопрос

2. См. билет №8 2 вопрос

Билет №15

1.Высказывание, свойство, отношение, тернарное отношение. Запись с помощью предикатов.

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

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

Тернарное отношение — то же, что трёхместное отношение (трёхчленное отношение).

p, q, r, s, p₁... – пропозициональные переменные (символы для обозначения целых повествовательных предложений);

a, b, c, d, a₁... – предметные константы (символы для обозначения единичных имен);

x, y, z, x₁... – предметные переменные (символы для обозначения общих имен);

P, Q, R, S, P₁... – предикатные символы (символы для обозначения свойств и отношений);

ù - логическое отрицание («не» или «неверно, что»);

Ù - конъюнкция («и»);

Ú - дизъюнкция («или»);

Ú - строгая дизъюнкция («либо…, либо…»);

É - импликация («если…, то…»);

º - тождество (эквивалентность) («тогда и только тогда, когда…»);

" - квантор всеобщности («все», «каждый»);

$ - квантор существования («некоторые», «существуют»);

Помимо этого в записи используются технические знаки: скобки и запятая.

Выражения языка логики предикатов называются формулами. Определению правильно построенной формулы предшествует определение терма.

2.Дедукция и индукция в широком смысле.

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

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

Пример простейшего дедуктивного умозаключения:

1. Все люди смертны.

2. Сократ — человек.

3. Следовательно, Сократ смертен.

Индукция (из лат. inductio «выведение, наведение») — широко используемый в науке термин.

В логике

• Индуктивное умозаключение — метод рассуждения от частного к общему.

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

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

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

Билет №16

1.Понятие алгоритма. Алгоритм Евклида.

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

Ранее в русском языке писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место исключение (нормальный алгорифм Маркова).

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

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

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

Частичная формализация понятия алгоритма началась с попыток решения проблемы разрешения (нем. Entscheidungsproblem), которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации были необходимы для определения эффективных вычислений^[1] или «эффективного метода»^[2]; среди таких формализаций — рекурсивные функции Геделя — Эрбрана — Клини 1930, 1934 и 1935 гг., λ-исчисление Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга. В методологии алгоритм является базисным понятием и получает качественно новое понятие как оптимальности по мере приближения к прогнозируемому абсолюту. В современном мире алгоритм в формализованном выражении составляет основу образования на примерах, по подобию.

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

Первое описание алгоритма находится в «Началах» Евклида (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Однако в XIX веке он был обобщён на другие типы чисел, такие как целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида также был обобщён на другие математические структуры, такие как узлы и многомерные полиномы.

Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA^[4], широко распространённого вэлектронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений^[5], при построении непрерывных дробей, в методе Штурма. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких кактеорема Лагранжа о сумме четырёх квадратов и основная теорема арифметики.

2.Бинарные отношения, их виды и свойства. Связь с графами.

Билет №6 вопрос 2

Билет №17

1.Конъюнкция, дизъюнкция, импликация, отрицание.

Билет 8 Вопрос 2

Отрицание в логике — унарная операция над суждениями, результатом которой является суждение (в известном смысле) «противоположное» исходному. Обозначается знаком ¬ перед или чертой --над суждением. Синоним: логическое "НЕ".

Как в классической, так и в интуиционистской логике «двойное отрицание» ¬¬A является следствием суждения A, то есть имеет место тавтология:  .

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

Основная статья: Логические элементы — отрицание

0	1
1	0

Мнемоническое правило для отрицания звучит так: На выходе будет:

• «1» тогда и только тогда, когда на входе «0»,

• «0» тогда и только тогда, когда на входе «1».

2.Кванторные операции.

Пусть имеется предикат P(x), определенный на множестве M и  . Подставим a вместоx в предикат P(x), получим высказывание P(a), которое называется единичным. Наряду с образованием из предикатов единичных высказываний рассмотрим еще две операции, которые преобразуют одноместный предикат в высказывание.