Запитання до екзамену з курсу "Основи дискретної математики" (Розділи: Математичні основи побудови ЦОМ. Основи теорії множин. Математична логіка. Основи теорії графів)

Отношение r симметрично, если (y,x) Î r для любых x,y Î A, таких что (x,y) Î r.

·  Антисимметричность. Отношение r антисимметрично, если (y,x) Ï r для любых x,y Î A, таких что (x,y) Î r.

·  Транзитивность. Отношение r транзитивно, если (x,z) Î r для любых x,y,z Î A, таких что (x,y),(y,z) Î r.

·  Отношение эквивалентности. Если отношение рефлексивно, симметрично и транзитивно, его называют отношением эквивалентности.

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

·  Отношение, в котором находятся любые два элемента множества A совпадает с декартовым квадратом множества A.

Вопрос:

Відношення еквівалентності та порядку.

Ответ:

Вопрос:

Від­повідності.

Ответ:

Вопрос:

Відповідність і потужність множин.

Ответ:

Вопрос:

Відображення та функції.

Ответ:

Розділ 3. Математична логіка

Вопрос:

Вступ до математичної логіки. Поняття, судження, умовиводи.

Ответ:

Основная идея математической логики – формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания – математические. Таким образом, математическая логика, посуществу, – наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство''. Действительно, ``доказательные'' (иначе говоря, дедуктивные) рассуждения – единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим'' процессом переписывания текста ( формул). Такой процесс называют выводом. Говорят еще, что математическая логика оперирует только синтаксическими понятиями.

Однако обычно всё же важно, как соотносятся рассуждения с действительностью (или нашими представлениями). Поэтому, надо всё же иметь в виду некоторый смысл формул и вывода. При этом используют термин семантика (синоном слова ``смысл'') и чётко разделяют синтаксис и семантику.

Когда же действительно интересуются только синтаксисом, часто используют термин ``формальная система''. Мы будем использовать синоним этого термина – ``исчисление'' (используются ещё термины ``формальная теория'' и ``аксиоматика'').

Объектом формальных систем являются строки текста (последовательности символов), с помощью которых записываются формулы.

Формальная система определена, если:

1. Задан алфавит (множество символов, используемых для построения формул).
2. Определено, какие именно строки считать формулами (остальные строки считаются просто бессмысленными).
3. Выделено множество формул, называемых аксиомами. Это – стартовые точки в выводах.

4. Задано множество правил вывода, которые позволяют из некоторой формулы (или множества формул) получать новую формулу.

Вопрос:

Операції математичної логіки.Основні операції алгебри логіки та їхні таблиці істинності.

Ответ:

Логические операции.

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

Пусть даны 2 произвольных высказывания А и В:

1. Коньюкция – называется высказывание А^В=А&B, которое истинно тогда и только тогда, когда  А и В – истина.
2. Дизъюнкция – называется высказывание АvB, которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний А или В.
3. Импликация А → В – это высказывание, которое ложно тогда и только тогда, когда А истина, В ложь. При этом А называется посылкой, а В - следствием.
4. Эквиваленция – А ~ В – это высказывание, которое истинно тогда и только тогда, когда А и В либо оба истины, либо оба ложны..
5. Отрицание (инверсия) А(и черточка сверху) – это высказывание, которое истинно тогда и только тогда. Когда А ложь.

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