Резюме по теме. Вопросы для повторения

Вопросы для повторения

1.Что такое предикат?

2.В чем отличие булевой логики от предикатной?

3.Для чего необходимы кванторы?

4.В каком случае используется квантор существования?

5.Когда формула является выполнимой в определенной области?

6.Когда формула называется тождественно истинной в определенной области?

7.Дайте определение модели логики предикатов?

8.Приведите примеры эквивалентных соотношений?

9.Каким образом предикатную формулу приводят к префиксной нормальной форме?

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

Глава 3. Комбинаторика

Термин "комбинаторика" был введён в математический обиход знаменитым Готфрид Вильгельм Лейбницем.

В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов выводит свойства сочетаний: .

Строит таблицы сочетаний до n=k=12, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др.

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

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. Сочинение состояло из 4 частей, комбинаторике была посвящена вторая часть, в которой содержатся формулы:

для числа перестановок из n элементов,

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

для числа размещений с повторениями и без повторений.

Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая их многочисленными таблицами и примерами. В математике в XIX веке появился сначала термин "геометрическая конфигурация" в лекциях по проективной геометрии профессора университета в Страсбурге К.Т. Рейе (1882).

В 1896 году американский математик Элиаким Гастингс Мур (1862-1932) ввёл термин тактическая конфигурация в статье "Tactical memoranda", понимая под этим термином систему n множеств, содержащих, соответственно, a1, a2, …, an элементов. Тактическую конфигурацию Мур задаёт квадратной матрицей порядка n, в которой элемент a_кк, стоящий на главной диагонали, равен числу a_к (числу элементов в k -ом множестве); элемент a_ij (i¹ j) равен числу элементов i -ого множества, инцидентных j -ому множеству. К тактическим конфигурациям Мур относит сочетания, размещения, системы решений задачи Киркмана о 15 школьницах, подгруппы некоторых групп. Он демонстрирует широкий спектр задач из геометрии, теории групп, которые приводят к тактическим разложениям или используют тактические разложения. Мур обогатил список известных комбинаторных конфигураций построением новых, обобщающих системы троек Штейнера, и системы троек Киркмана.

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

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

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

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

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

Структурная комбинаторика. К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

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

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

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

Дата добавления: 2014-01-05