Практическая работа № 1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

 

МНОГОПРОФИЛЬНЫЙ КОЛЛЕДЖ

  

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

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

 

ЕН.02 Элементы математической логики

Специальность – 09.02.03 Программирование в компьютерных системах

Квалификация выпускника – техник-программист

Форма обучения - очная  

 

Уровень подготовки - базовый

 

 

Пенза, 2016

Методические указания составлены в соответствии с рабочей программой по дисциплине «Элементы математической логики» и предназначены для студентов второго курса, обучающихся по специальности 09.02.03 «Программирование в компьютерных системах».

 

 

 Составитель:

 

 _________________________________________          К.М. Буданов

 

 

ОДОБРЕНО цикловой/методической комиссией

 

Протокол № ___ от «___» _____________ 20__ г.

 

Председатель комиссии         ________________         В.А. Феоктистов

 

Содержание

 

Введение	4
Практическая работа №1 «Построение таблиц истинности высказываний»	5
Практическая работа №2 «Составление таблиц истинности формул алгебры высказываний. Упрощение формул алгебры высказываний»	8
Практическая работа №3 «Упрощение формул алгебры высказываний с помощью карт Карно»	13
Практическая работа №4 «Прямая и обратная теоремы. Необходимые и достаточные условия»	17
Практическая работа №5 «Операции над множествами. Бинарные отношения. Свойства отображений и функций»	20
Практическая работа №6 «Приложение булевых функций к анализу и синтезу релейно-контактных схем»	24
Практическая работа №7 «Логические операции над предикатами»	29
Практическая работа №8 «Кванторы. Отрицание предложений с кванторами»	33
Практическая работа №9 «Применение языка логики предикатов для записи математических утверждений. Принцип математической индукции»	37
Практическая работа №10 «Применение машины Тьюринга к словам»	39
Практическая работа №11 «Примитивно рекурсивные функции»	43

 

 

Введение

Отличительной чертой современного общества является компьютеризация практически каждой области деятельности человека.

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

Алгоритмичность мышления наиболее ярко проявляется в математике. Появление компьютеров стало ещё одним подтверждением этого свойства математического мышления. 

Основы алгоритмического мышления заложены в теории алгоритмов – одном из разделов математической логики.

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

Многие языки программирования построены на базе теории алгоритмов и логики предикатов.

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

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

Выполнение практических работ по дисциплине «Элементы математической логики» позволит студентам овладеть необходимыми практическими навыками и лучше понять теоретический материал

Практические работы выполняются по группам (учебным бригадам). Каждая учебная бригада состоит из 2-3 студентов. Вариант задания определяется по номеру бригады. 

 

ПРАКТИЧЕСКАЯ РАБОТА № 1

«ПОСТРОЕНИЕ ТАБЛИЦ ИСТИННОСТИ ВЫСКАЗЫВАНИЙ»

 

Цель работы: научиться определять истинностные значения сложных высказываний с помощью таблиц истинности операций над элементарными высказываниями.

 

Ход выполнения работы:

 

1. Изучить теоретический материал.

2. Получить задание у преподавателя.

3. Выполнить задание.

4. Ответить на контрольные вопросы.

5. Защитить выполненное задание.

 

Краткие теоретические сведения

 

Высказывание – повествовательное предложение, которое либо истинно, либо ложно. Высказывание не может быть одновременно и истинным, и ложным.

Обозначим истинное высказывание символом 1, а ложное – 0, введем функцию l, заданную на совокупности всех высказываний и принимающую значения в двухэлементном множестве {0, 1}, по следующему правилу:

Функция l представляет собой функцию истинности, а значение l(Р) – логическое значение (значение истинности) высказывания Р.

Элементарное высказывание – высказывание, значение истинности которого можно установить непосредственно.

Составное высказывание – высказывание, состоящее из элементарных высказываний, соединённых логическими операциями.

Значение истинности составного высказывания зависит от значений истинности входящих в него элементарных высказываний.

Логические операции (операции над высказываниями) – отрицание (), конъюнкция (Ù), дизъюнкция (Ú), импликация (®), эквиваленция («).

Таблица истинности логических операций имеет вид

 

0	0	0	0	0	1	1
0	1		0	1	1	0
1	0	1	0	1	0	0
1	1		1	1	1	1

 

Образец выполнения

 

1. Определить логическое значение последнего высказывания, если известны логические значения всех предыдущих высказываний.

,  

Решение.

 

Из таблицы истинности операции эквиваленции следует, что , если l(A) = 0 и l(B) = 1 или l(A) = 1 и l(B) = 0.

Если l(B) = 1, то из таблицы истинности операции отрицания следует, что l(ØB) = 0 и тогда, исходя из таблицы истинности операции импликации следует, что l(ØB®A) = 0®0 = 1.

Если l(B) = 0, то из таблицы истинности операции отрицания следует, что l(ØB) = 1 и тогда, исходя из таблицы истинности операции импликации следует, что l(ØB®A) = 1®1 = 1.

Отсюда .

 

2. Существуют ли высказывания A, B, C такие, что для них одновременно выполняются следующие условия.

 

Решение

 

Из таблицы истинности операции дизъюнкция следует, что l(AÚB) = 0, если l(A) = l(B) = 0. Из таблицы истинности операции отрицания следует, что если l(B) = 0, то l(ØB) = 1. Из таблицы истинности операции конъюнкция следует, что 1Ùl(С) = 1, если l(С) = 1. Из таблицы истинности операции отрицания следует, что если l(С) = 1, то l(ØС) = 0. Отсюда l(AÚØC) = 0Ú0 = 0. l(ØB«ØC) = 1«0 = 0.  = 0«0 = 1.

Следовательно, высказывания, удовлетворяющие одновременно всем трём условиям существуют. 

 

3. Для заданного высказывания определить, достаточно ли приведённых данных, чтобы определить его логическое значение. Если достаточно, то указать это значение. В противном случае показать на конкретных примерах, что возможны различные истинностные значения.

, если

 

Решение.

 

Если l(A) = 1, то из таблицы истинности операции отрицания следует, что l(ØA) = 0. Из таблицы истинности операции дизъюнкции следует, что l(AÚB) = 1ÚB = 1. Из таблицы истинности операции отрицания следует, что l(Ø(AÚB)) = 0.  Из таблицы истинности операции конъюнкции следует, что l(ØBÙØA) = ØBÙ0 = 0.

Отсюда .

Таким образом, приведённых сведений достаточно, чтобы определить логическое значение заданного высказывания. Логическое значение равно 1 (высказывание истинное)

 

Задания:

 

1. Определить логическое значение последнего высказывания, если известны логические значения всех предыдущих высказываний.

1) ,   ,     

2) , ,       

3) ,   ,     

4) ,   ,      ,                             

5) ,   ,   ,               

6) ,   ,       ,                             

7) ,                        

8) ,              ,                             

9) ,                        

 

2. Существуют ли высказывания A, B, C такие, что для них одновременно выполняются следующие условия.

1)

2)

3)

4)

5)

6)

7)

8)

9)

 

3. Для заданного высказывания определить, достаточно ли приведённых данных, чтобы определить его логическое значение. Если достаточно, то указать это значение. В противном случае показать на конкретных примерах, что возможны различные истинностные значения.

1) ,                     если

2) ,                            если

3) ,                     если  

4) ,                            если

5) ,           если

6) , если

7) ,                                     если

8) ,                        если

9)      если   

 

Контрольные вопросы.

 

1. Что такое элементарное высказывание.

2. Что такое составное высказывание.

3. Что такое функция истинности и логическое значение высказывания.

4. Перечислить основные операции над высказываниями.

5. Охарактеризовать таблицы истинности операций над высказываниями.