Реферат Курсовая Конспект
ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ - раздел Информатика, Введение Логика – Это Наук...
|
ВВЕДЕНИЕ
Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим мыслителем Аристотелем. Идеи о построении логики на математической основе, т.е. по сути математической логики, были высказаны Лейбницем в начале 18-го века.
Современная математическая логика определяется как раздел математики, посвященный изучению математических доказательств и вопросов основания математики. Одна из главных причин широкого распространения математической логики – применение аксиоматического метода в построении различных математических теорий. Важным достижением математической логики является формулировка понятия алгоритмической вычислимости, которое по своей важности приближается к понятию натурального числа. Сегодня результаты математической логики находят свое применение в других отраслях математического знания, а также в программировании, проблемах искусственного интеллекта и других науках.
Данное учебно-практическое пособие соответствует учебной программе курса «Математическая логика и теория алгоритмов» для специальностей «Информационные системы и технологии», «Вычислительные машины, комплексы и сети».
Практикум разделен на три части. В первой содержится программа курса, во второй – краткое изложение теории и решение типовых задач, в третьей – задания для контрольных работ. Практикум может быть использован как задачник, как раздаточный материал для выполнения контрольных работ и индивидуальных домашних заданий.
ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ
2.1. Алгебра высказываний
Исчисление высказываний
Основные эквивалентности исчисления
Полнота и непротиворечивость исчисления
Логика предикатов
Пример 2.
1) Термами сигнатуры Σ={+,∙,≤,0} будут, например, 0, x, x+y, z∙(x+z)+0∙y, а x+y≤(0+х) x термом не является.
2) Если Σ={ƒ(3), g(1), h(2)} ‑ функциональная сигнатура, то выражения h(ƒ(x1, x2, x3), g(x2)), g(ƒ(h(x1, x2), x1, g(x2)) – термы, а h(x1, ƒ(x1, x3))термом не является.
Пусть t(x1,…,xk) ‑ терм из T(Σ), все переменные которого содержатся в множестве {x1,…,xk}, = ‑ алгебраическая система. Значение терма t на элементах a1,…,ak A (t(a1,…,ak)) определяется по индукции:
1) если t есть переменная xi (константный символ с), то значение t есть аi (с);
2) если tF(t1,…, tn), где F (n) Σ, t1(x1,…,xk),…,tn(x1,…,xk) Т(Σ) и значения термов t1,…, tn на элементах a1,…,ak равны b1,…,bn то значение терма t есть F(b1,…,bn).
Теорема 2.Если = ‑ алгебраическая система, Ø≠X B, то B(Х)={t(a1,…,an) | t T(Σ), a1,…,an X}.
Пример 3. Построить подсистему алгебраической системы , порожденную множеством Х:
1) = X={1/2};
2) = X={1/2};
3) = X={22;-36}.
Решение. 1) Так как Т(Σ)={x1, x1x2, (x1x2)x3, x1(x2x3),…}, то теореме 2 имеем A(X)={1/2, 1/2∙1/2, 1/2∙1/2∙1/2,…}={1/2, 1/8, 1/16,…}={1/2n| n≥1}.
2) Из предыдущего примера следует, что {1/2n| n≥1} A(X). Так как операция деления является сигнатурной, то 1/2n1/2m=2m-n A(X) для любых m, n≥1. Тогда C={2n| n Z} A(X). Так как множество С замкнуто относительно операций умножения и деления. т.е. является подсистемой алгебраической системы и содержит множество X, то A(Х) С. Следовательно, A(Х)=С.
3) Так как 2=22-8(-36)-1422 и любое число, получаемое из чисел 22, -36 с помощью операции вычитания четное, то A(X)=2
Истинность формулы логики предикатов
Исчисление предикатов
Эквивалентные формулы исчисления
Теорема Геделя о полноте. Непротиворечивость
Элементы теории алгоритмов
ЗАДАНИЯ ДЛЯ домашних И КОНТРОЛЬНЫХ РАБОТ
Истинность формулы логики предикатов
Исчисление предикатов
Пусть - формулы исчисления предикатов. Построить вывод формулы исчисления предикатов из данного множества гипотез.
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
Пренексная нормальная форма
Пусть – атомарные формулы логики предикатов. Привести следующие формулы логики предикатов к пренексной нормальной форме.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
Машины Тьюринга
Построить машину Тьюринга , вычисляющую следующую функцию.
– Конец работы –
Используемые теги: программа, курса, Математическая, Логика, терия, алгоритмов0.104
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов