МИНОБРНАУКИ РОССИИ

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

КАФЕДРА «ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»

Авдеюк О.А.

Математическая логика и теория алгоритмов

Сборник заданий для контрольных работ

Направление: 09.03.01 «Информатика и вычислительная техника»

Профили: «Автоматизированные системы обработки информации и управления», «Высокопроизводительные вычислительные системы на базе больших ЭВМ», «Вычислительные машины, комплексы, системы и сети», «Системы автоматизированного проектирования»

Волгоград –2014

Методические указания

Семестровая работа предполагает закрепление студентом полученных знаний по разделу “ Логические основы” курса “ Математическая логика и теория алгоритмов ”. Сборник для семестровой работы содержит 30 вариантов заданий по 11 задач в каждом, тем самым предусматривается индивидуальная работа студента. Вариант задания равен сумме трех последний цифр зачетной книжки (студенченского).

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

2. СБОРНИК ЗАДАНИЙ ДЛЯ СЕМЕСТРОВОЙ РАБОТЫ № 1 ПО КУРСУ «Математическая логика и теория алгоритмов»

2.1. Пример решения и оформления

Тетрадь Для выполнения семестровой работы № 1 по курсу «Математическая логика и теория алгоритмов». Вариант 31 Выполнил: студент ФЭВТ ВолгГТУ группы ИВТ-160 Петров В.А. Дата сдачи работы: 10.12.2014 г. Проверил: Баллы:

1. Используя таблицу истинности, установить эквивалентность функций в формуле:

Решение:

Обозначим: f₁ = X₁  X₂

f₂ = f₃ = f₄ =

Составим таблицу истинности для правой и левой части функции:

х1 х2 f1	f2 f3f4
0 0 0 0 1 1 1 0 1 1 1 0	1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0

Ответ: Как видно из таблицы, значения правой и левой части равенства действительно совпадают, значит, функции в данной формуле эквивалентны.

2. Определить, какие переменные являются существенными и какие фиктивными в функции следующего вида:

f ( х₁,х₂,х₃) = ( х₁\/ х₂)  х₃.

Решение:

1.Необходимо составить таблицу истинности:

х₁ х₂ х₃ х₁ \/х₂ ( х₁\/ х₂)  х₃.

0 0 0 0 1

0 0 1 0 1

0 1 0 1 0

0 1 1 1 1

1 0 0 1 0

1 0 1 1 1

1 1 0 1 0

1. 1 1 1 1

2.Разобьем таблицу на два подмножества: наборы для 0 значений и наборы для 1 значений:

0 1

0 1 0 0 0 0

1 0 0 0 0 1

1 1 0 0 1 1

1 0 1

1 1 1

3. Определим фиктивные и существенные переменные:

1. . Вычеркнем первый столбец:

0 1 Видно, что есть

1 0 0 0 совпадающие

0 0 0 1 наборы, т. е.

1 0 1 1 х₁ – существенная

0 1 переменная.

1 1

3.2 . Вычеркнем второй столбец:

0 1 Аналогично,