Математическая логика и теория алгоритмов (Сафьянова) - Дискретная математика. Часть 2.

Дисциплина 'Математическая логика и теория алгоритмов' изучается по учебному пособию:
1. Сафьянова Е.Н. 'Дискретная математика. Часть 2.'-Томск,2000 - 99 с.

По дисциплине "Математическая логика и теория алгоритмов" в течение семестра
необходимо выполнить следующие контрольные работы:

1. 2 текстовые контрольные работы по заданиям в учебном пособии

Контрольная работа №1 состоит из 10 вариантов по 3 задания
в каждом (стр. 91-95).
Контрольная работа №2 состоит из 10 вариантов по 2 заданий
в каждом (стр. 95-98).
Номера вариантов выбираются по общим правилам.


Контрольные работы №№ 1,2 (3,4), выполняемые в третьем семестре, имеют целью закрепить теоретические знания, полученные в разделах: "Основы математической логики", "Основы теории алгоритмов", "Элементы комбинаторного анализа".

Контрольная работа № 1(3)

Тема работы - математическая логика. В работе требуется выполнить следующие задания.
1. Определить, является ли справедливой приведенная формула алгебры высказываний, не прибегая к составлению таблицы истинности, а используя только свойства соответствующих операций.
2. Для указанной функции трех переменных:
- составить таблицу истинности;
- определить, к каким классам булевых функций она отно-сится;
- записать совершенные ДНФ и КНФ;
- найти минимальную ДНФ;
- для полученной минимальной ДНФ построить логическую схему в базисах: а) { ?, } (дизъюнкция, отрицание); б) { ?, } (конъюнкция, отрицание).
3. Доказать полноту (или неполноту) приведенной системы булевых функций.
При выполнении контрольной работы затруднения может вызвать проверка линейности булевой функции.
Для исследования функции на линейность ее следует представить в общем виде с помощью полинома по модулю два, а затем, используя значения функции и значения переменных на конкретных наборах, попытаться определить коэффициенты полинома. Оставшиеся неиспользованными наборы используют для проверки пра-вильности выражения. Полученное хотя бы на одном из наборов противоречие означает некорректность выражения, а значит и нелинейность функции.

Контрольная работа № 2(4)

Эта контрольная работа включает в себя задания по теории алгоритмов и перечислительной комбинаторике. В работе требуется выполнить четыре задания.
1. Приведите три самостоятельных примера применения оператора подстановки к простейшим числовым функциям. Например,
s(С23 (I13 (3, 2, 4), I23 (5, 8, 1), I33( 5, 6, 7))) = 3.
2. Приведите два самостоятельных примера применения оператора примитивной рекурсии (аналогично примерам из конспекта лекций).
3. Напишите программу для машины Тьюринга в соответствии с Вашим вариантом.
4. Решите комбинаторную задачу в соответствии с Вашим вариантом.