Составление легенд и клауз в логике

ПОСТРОЕНИЕ ДОКАЗАТЕЛЬСТВ В ЛОГИКЕ

ПРИМЕНЕНИЕ АЛГЕБРЫ ЛОГИКИ К РЕШЕНИЮ

ПРИМЕНЕНИЕ АЛГЕБРЫ ЛОГИКИ К РЕЛЕЙНО-

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ. СОВЕРШЕННЫЕ

ФОРМУЛЫ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ.

АЛГЕБРА ВЫСКАЗЫВАНИЙ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Моисеев, Н. Г.

Г.А. Шишкин.

И ТЕОРИЯ АЛГОРИТМОВ

Лабораторный практикум

Йошкар-Ола

МарГТУ

УДК 510.6(075.8)

ББК 22

М 74

Рецензенты:

канд.техн.наук, профессор кафедры ПиП ЭВС МарГТУ Ю.В.Захаров;

канд.техн.наук, доцент, руководитель Управления федеральной службы по надзору в сфере массовых коммуникаций, связи и охране культурного наследия по Республике Марий Эл,

Печатается по решению

редакционно-издательского совета МарГТУ

М74

Математическая логика и теория алгоритмов: лабораторный

практикум / Н. Г. Моисеев – Йошкар-Ола: Марийский государственный технический университет, 2011. – 212 с.

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

Для студентов специальностей 230100, 230101, 230105 направления 654600 «Информатика и вычислительная техника».

УДК 510.6(075.8)

ББК 22

ÓМоисеев Н. Г., 2011

ÓМарийский государственный

технический университет, 2011

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ …………………………………………….…………….. 5

ВВЕДЕНИЕ ………………………………………………………..….…… 6

ТЕХНИКА БЕЗОПАСНОСТИ ПРИ ВЫПОЛНЕНИИ

ЛАБОРАТОРНЫХ РАБОТ ………………………………………………..7

Лабораторная работа № 1

НАД НИМИ ………………………………………………………...…….10

1.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ …………………………….……..10

1.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ ……………...…….19

1.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….………………………………25

Учебно-методическое обеспечение ………………………………..25

Лабораторная работа № 2

РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ……………………..…….26

2.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ……………………………….…..26

2.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ ……………...…….32

2.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….……………………….………35

Учебно-методическое обеспечение ………………………………..36

Лабораторная работа № 3

НОРМАЛЬНЫЕ ФОРМЫ………………………………………..….….37

3.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ …………………………………...37

3.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ ……………...…….54

3.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….………………………….……57

Учебно-методическое обеспечение ………………………………..58

Лабораторная работа № 4

КОНТАКТНЫМ СХЕМАМ.……………………………………...…….59

4.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ……………………………….…..59

4.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ ……………...…….67

4.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….………………………………70

Учебно-методическое обеспечение ………………………………..70

Лабораторная работа № 5

ЛОГИЧЕСКИХ ЗАДАЧ…………………………………………...…….71

5.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ………………………….………..71

5.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ ……………...…….80

5.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….………………………………82

Учебно-методическое обеспечение ………………………………..83

Лабораторная работа № 6

ВЫСКАЗЫВАНИЙ………………………………………………...…….84

6.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ……………………………….…..84

6.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ..…………...…….108

6.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….…………………….………..111

Учебно-методическое обеспечение ……………………………....112

Лабораторная работа № 7

ВЫСКАЗЫВАНИЙ …..…………………………………………......….113

7.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ …………………………….…….113

7.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ ……………..........120

7.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….……………………………..130

Учебно-методическое обеспечение ………………………………130

Лабораторная работа № 8

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ …………………………......…131

8.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ………………………….………131

8.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ ……………..……150

8.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….………………………..….…159

Учебно-методическое обеспечение ……………………..…….….160

Лабораторная работа № 9

ЛОГИКА ПРЕДИКАТОВ ………………………………………..……161

9.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ …………………………….…….161

9.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ ……………..……177

9.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….……………..……….………186

Учебно-методическое обеспечение …………………….…..…….187

Лабораторная работа № 10

АЛГОРИТМЫ И ИХ ПРИМЕНЕНИЕ.………………………...……188

10.1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ……………………………..…..188

10.2. ЗАДАНИЯ К ВЫПОЛНЕНИЮ РАБОТЫ …………...….….206

10.3. КОНТРОЛЬНЫЕ ВОПРОСЫ….………….…………………209

Учебно-методическое обеспечение ……………………………....209

ЗАКЛЮЧЕНИЕ …………………………………………………………. 210

ПРЕДИСЛОВИЕ

Данный лабораторный практикум включает в себя 10 лабораторных работ, каждая из которых начинается с теоретической части, где кратко изучаются основные положения темы с примерами. Затем даны задания к выполнению работы, далее следуют контрольные вопросы, указывается учебно-методическое обеспечение.

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

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

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

Десятая работа посвящена элементам теории алгоритмов. Рассматриваются машина Тьюринга, способы ее построения и применения к решению конкретных задач.

Лабораторный практикум адресован студентам, обучающимся по направлению подготовки 654600 – Информатика и вычислительная техника, по специальностям: 230101 – «Вычислительные машины, комплексы, системы и сети», 230105 – «Программное обеспечение вычислительной техники и автоматизированных систем», 230100.62 – «Бакалавр техники и технологии».

Дата добавления: 2017-02-01