Формальные системы

Москва 2019

МИНИС ТЕРС ТВО НАУКИ И ВЫСШ ЕГО О Б РА З О ВА Н И Я РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ 
ВЫСШЕГО ОБРАЗОВАНИЯ 
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ «МИСиС»

Институт информационных технологий и автоматизированных систем управления 
 
Кафедра автоматизированных систем управления

Е.В. Зайцева

ФОРМАЛЬНЫЕ СИСТЕМЫ

Практикум

Рекомендовано редакционно-издательским 
советом университета

№ 3355

УДК 004 
 
3-17

Р е ц е н з е н т 
канд. техн. наук, доц. Л.П. Волкова

Зайцева Е.В.
3-17  
Формальные системы : практикум / Е.В. Зайцева. – М. : Изд. 
Дом НИТУ «МИСиС», 2019. – 36 с.

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

УДК 004

 Е.В. Зайцева, 2019
 НИТУ «МИСиС», 2019

СОДЕРЖАНИЕ

Введение ....................................................................................................4

Практическое занятие 1. Исчисление высказываний ............................... 5
1.1. Теоретическая часть .......................................................................... 5
1.2. Задачи  ................................................................................................ 8

Практическое занятие 2. Предикаты и отношения ..................................11
2.1. Теоретическая часть .........................................................................11
2.2. Задачи и упражнения .......................................................................11

Практическое занятие 3. Алгебра предикатов ........................................ 15
3.1. Теоретическая часть ........................................................................ 15
3.2. Задачи ............................................................................................... 20

Практическое занятие 4. Исчисление предикатов .................................. 30
4.1. Теоретическая часть ........................................................................ 30
4.2. Задачи ............................................................................................... 32

Библиографический список ...................................................................35

ВВЕДЕНИЕ

Формальные системы в АСУ являются наукой о логических рассуждениях, использующей математические методы, при которых из 
верных исходных умозаключений путем применения законов человеческого мышления получают достоверные результаты.
Применение формальных систем позволило представить логические теории в новой совершенной форме с использованием аксиоматического метода в построении формализованных математических 
теорий.
Формальные системы для АСУ включают: исследование различных логических вычислений, таких как классическое исчисление высказываний и предикатов, и изучение взаимосвязанных синтаксических (информационных) и семантических (реальных) объектов.
Использование формальных систем позволяет проводить и исследовать аксиоматизацию классов алгебраических объектов и на основании аксиоматизации судить о свойствах самих классов, используя 
механизм логического рассуждения и доказательства.
Бурное развитие теории множеств, классического исчисления высказываний и предикатов во многом обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и 
передачи информации, а также представления математических моделей в АСУ.
В настоящем практикуме обобщены и использованы материалы 
многих авторов, занимающихся проблемами аппроксимации формальных систем, однако впервые сделана попытка систематически 
изложить основные понятия, относящиеся к систематике формализованных логико-математических языков, к элементам теории множеств, основам классической логики, исчислениям высказываний и 
предикатов в едином учебном пособии.