ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ
ВВЕДЕНИЕ
Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим мыслителем Аристотелем. Идеи о построении логики на математической основе, т.е. по сути математической логики, были высказаны Лейбницем в начале 18-го века.
Современная математическая логика определяется как раздел математики, посвященный изучению математических доказательств и вопросов основания математики. Одна из главных причин широкого распространения математической логики – применение аксиоматического метода в построении различных математических теорий. Важным достижением математической логики является формулировка понятия алгоритмической вычислимости, которое по своей важности приближается к понятию натурального числа. Сегодня результаты математической логики находят свое применение в других отраслях математического знания, а также в программировании, проблемах искусственного интеллекта и других науках.
Данное учебно-практическое пособие соответствует учебной программе курса «Математическая логика и теория алгоритмов» для специальностей «Информационные системы и технологии», «Вычислительные машины, комплексы и сети».
Практикум разделен на три части. В первой содержится программа курса, во второй – краткое изложение теории и решение типовых задач, в третьей – задания для контрольных работ. Практикум может быть использован как задачник, как раздаточный материал для выполнения контрольных работ и индивидуальных домашних заданий.
Тема 2. «Логическое следствие в алгебре высказываний». Понятия логического следствия. Связь между понятиями логического следствия, противоречивого… Тема 3. «Исчисление высказываний (ИВ). Доказуемые формулы ИВ». Понятие… Тема 4. «Логика предикатов (ЛП). Алгебраические системы. Подсистемы».Понятия сигнатуры, алгебраической системы данной…
ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ
2.1. Алгебра высказываний
В качестве примеров высказываний приведем предложения "Владивосток — крупнейший город Приморья" и "Снег зеленый". Первое… Поставим в соответствие высказыванию Р логическую переменную х, которая… Если имеется несколько высказываний, то из них можно образовать различные новые высказывания. При этом исходные…
Формулы φ и ψ АВ называются эквивалентными (обозначается φ ≡ ψ), если φ ψ или ψ , т.е. совпадают их… Примαр 7. Построив таблицы истинности формул x→y и ¬y→¬x,… Легко видеть, что отношение ≡ является отношением эквивалентности на множестве формул АВ, т. е. оно рефлексивно…
называется литерой. Литеры х и ¬х называются контрарными.
Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом…
Исчисление высказываний
Введем общее понятие формального исчисления. Будем говорить, что формальное исчисление I определено, если выполняются четыре условия.
1. Имеется некоторое множество А символов – алфавит исчисления I. Конечные… 2. Задано подмножество F S, называемое множеством формул исчисления I. Элементы множества F называются формулами.
…
Алфавит ИВ состоит из букв x,y,z,u,v, возможно с индексами (которые называются пропозициональными переменными), логических символов (связок) ¬,… Множество формул ИВ определяется индуктивно:
а) все пропозициональные переменные являются формулами ИВ;
Пример 4. Покажем, что φ→ψ⊢¬ψ→¬φ;
Решение.По теореме о дедукции
φ→ψ⊢¬ψ→¬φ φ→ψ, ¬ψ⊢¬φ.
φ⊢ψ и ψ⊢φ.
Замечание 2.Для любых формул φ и ψ ИВ
φ≡ψ ⊢φ→ψ и ⊢ ψ→φ.
Утверждение 3.Пусть φ,ψ, χ – формулы ИВ. Тогда
1) ⊢φ→φ;
2) φ∧ψ⊢φ;
Основные эквивалентности исчисления
1) φ∧ φ≡φ, φ∨ φ≡φ (законы идемпотентности);
2) φ∧ ψ≡ψ∧ φ, φ∨… 3) (φ∧ψ)∧χ≡φ∧(ψ∧χ),…
Полнота и непротиворечивость исчисления
Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ⊨φ), если φ(x1,…,xn) – тождественно истинная формула как… Теорема 4(о полноте). Формула φ ИВ доказуема тогда и только тогда, когда… φ ⊨φ.
Логика предикатов
Напомним, что п-местным предикатом (отношением) на множестве А называется любое подмножество множества Аn; п-местной алгебраической операцией на… Сигнатурой Σ называется совокупность предикатных и функциональных… Алгебраической системой сигнатуры Σ называется пара = где А – непустое множество и каждому n-местному…
Пример 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) если t1, t2, T(Σ), то t1=t2 ‑ атомарная формула;
2) если P(n) Σ ‑ предикатный символ, t1,t2,…,tn T(Σ), то Р(t1,t2,…,tn) ‑ атомарная…
Истинность формулы логики предикатов
Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатуры Σ на элементах a1,…,an А в алгебраической системе = … 1) ⊨t1(a1,…,an)=t2(a1,…,an), где t1,t2 T(Σ), значения… 2) ⊨P(t1(a1,…,an),….,tk(a1,…,an)), где P(k) Σ, t1,…,tk T(Σ), (t1(a1,…,an),…, tk(a1,…,an)) …
Через обозначим кортеж переменных ; через ‑ .
Пусть φ1( ),…,φn( ), ψ( ) – формулы сигнатуры .… ⊨ (φ1( ) … φn( )→ψ( )).
Утверждение 1.В логике предикатов выполнимы все эквивалентности ИВ из теоремы 3.
Утверждение 2. Пусть φ, ψ – формулы сигнатуры переменная x не… 1) ¬ xφ≡ x¬φ, 1΄) ¬ xφ≡ x¬φ,
Говорят, что формула φ сигнатуры Σ находится в пренексной нормальной форме (ПНФ), если она имеет вид Q1x1…Qnxnψ, где Qi, ‑… Теорема 1. Для любой формулы φ сигнатуры Σ существует ПНФ ψ,… Опишим алгоритм приведения формулы к ПНФ:
Исчисление предикатов
Зафиксируем некоторую произвольную сигнатуру Σ и определим исчисление предикатов сигнатуры Σ (ИПΣ).
Формулами ИПΣ будут формулы сигнатуры Σ.
Примем следующие соглашения. Пусть x1,…,xn ‑ переменные, t1,…,tn ‑ термы сигнатуры Σ и φ ‑…
Эквивалентные формулы исчисления
Утверждение 2.В ИПΣ выполнимы все эквивалентности ИВ из теоремы 3.
Утверждение 3. Пусть φ, ψ – формулы ИПΣ переменная x не… 1) ¬ xφ≡ x¬φ, 1΄) ¬ xφ≡ x¬φ,
Теорема Геделя о полноте. Непротиворечивость
Доказательство проводим индукцией по длине вывода формулы. Очевидно, что аксиомы ИПΣ являются тождественно истинными. Проверку того, что… Следствие 3. ИПΣ непротиворечиво, т.е. не все формулы ИПΣ доказуемы… В ИПΣ справедлив аналог теоремы о полноте в исчислении высказываний.
Элементы теории алгоритмов
Машина Тьюринга – это система, работающая в дискретные моменты времени и состоящая из следующих частей:
конечная лента, разбитая на конечное число ячеек. В каждый момент времени в… Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый…
Базисными функциями называются следующие функции: – нулевая функция; – функция следования; – функция выбора.
Оператор суперпозиции (подстановки) ставит в соответствие m-местной…
Оператор минимизации ставит в соответствие n+1-местной частичной функции n-местную частичную функцию так, что
и
или определены и не равны 0,
ЗАДАНИЯ ДЛЯ домашних И КОНТРОЛЬНЫХ РАБОТ
1. ;
2. ;
3. ;
Пусть - формулы исчисления высказываний. Построить вывод формулы исчисления высказываний из данного множества гипотез.
1. ;
2. ;
1.
2.
3.
Выписать все подформулы данной формулы сигнатуры
и определить свободные и связанные переменные формулы:
1.
Истинность формулы логики предикатов
Написать формулу Ф(х), истинную в алгебраической системе тогда и только тогда, когда
1. х=1;
2. х=2n для некоторого натурального n;
1. ;
2. ;
3.
Исчисление предикатов
Пусть - формулы исчисления предикатов. Построить вывод формулы исчисления предикатов из данного множества гипотез.
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
Пренексная нормальная форма
Пусть – атомарные формулы логики предикатов. Привести следующие формулы логики предикатов к пренексной нормальной форме.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
Машины Тьюринга
Построить машину Тьюринга , вычисляющую следующую функцию.