Математическая логика и теория алгоритмов. Галуев Г.А. - 4 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 4 из 64
© 2003 Галуев Геннадий Анатольевич
2
2
.
.
Явная формулировка логических средств (правил вывода), которые допуска-
ются для последовательного построения этой теории.
3
3
.
.
Использование искусственно построенных формальных языков для изложения
всех положений (теорем) этой теории.
Основным объектом изучения математической логики являются различные ис-
числения (исчисление высказываний, исчисление предикатов), компонентами кото-
рых являются:
- язык
исчисления
- аксиомы исчисления
- правила вывода
Понятие исчисления позволяет дать строго математическое определение понятию
доказательства
и получить точные утверждения о невозможности доказательства тех
или иных предложений теории.
Математическая логика позволила дать также математическое определение дав-
но известного интуитивного понятия алгоритма, что дало возможность обнаружить
существование алгоритмически неразрешимых проблем в математике.
Математическая логика внесла значительный вклад не только в математические
науки, но и послужила объективной основой
для создания современной вычислитель-
ной техники и информатики.
Основными разделами математической логики являются исчисление высказыва-
ний и исчисление предикатов. Эти вопросы мы и будем рассматривать в данном курсе
лекций. Наряду с этим мы также рассмотрим основные положения современной тео-
рии алгоритмов, которая сформировалась в рамках математической логики и стала
самостоятельной научной
дисциплиной.
Исчисление Высказываний.
Понятие высказывания.
Пропозиционные буквы, формы (формулы) и связки.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
:
: Под высказыванием будем понимать предложение, относительно
которого в каждый данный момент времени можно сказать истинно оно или ложно.
Например: высказыванием является предложение «Сейчас в Таганроге идёт
дождь». Значение истинности этого высказывания – ложь.
Предложение «В Таганроге
ясная погода» также является высказыванием, но его значение истинности зависит от
времени.
Будем обозначать истинностные значения следующим образом: «истина» - И
(или 1), «ложь» - Л (или 0).
Математическая логика не интересуется содержательным смыслом высказыва-
ний, а только лишь правилами обращения с ними. Поэтому отдельные высказывания
будем обозначать буквами латинского
алфавита А,В,С,… и называть пропозиционны-
ми буквами (высказывательными переменными, элементарными формулами, атомами
и т.д. в разных источниках). Из таких пропозиционных букв или формул можно стро-
ить новые, более сложные высказывания. Истинность или ложность таких новых вы-
сказываний полностью определяется значениями истинности (т.е. И или Л) состав-
ляющих
их высказываний.
Для образования таких сложных высказываний используются пропозиционные
связки (логические операции), которые имеют вид:
Отрицание. Отрицание высказывания А обозначается ⎤А или
A (читается «не
А»). Значения истинности высказываний А и ⎤А связаны следующим образом:
- А И Л – истинностные значения высказывания А
- ⎤А Л И – истинностные значения высказывания ⎤А
Такая таблица называется истинностной таблицей или таблицей истинности.
Конъюнкция. Конъюнкция высказываний А и В обозначается А&В (читается «А и
В»).
Высказывание А&В истинно тогда и только тогда, когда истинны оба высказыва-
ния А и В.

Страницы