ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ

ВВЕДЕНИЕ

Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим мыслителем Аристотелем. Идеи о построении логики на математической основе, т.е. по сути математической логики, были высказаны Лейбницем в начале 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) Если Σ={ƒ⁽³⁾, g⁽¹⁾, h⁽²⁾} ‑ функциональная сигнатура, то выражения h(ƒ(x₁, x₂, x₃), g(x₂)), g(ƒ(h(x₁, x₂), x₁, g(x₂)) – термы, а h(x₁, ƒ(x₁, x₃))термом не является.

Пусть t(x₁,…,x_k) ‑ терм из T(Σ), все переменные которого содержатся в множестве {x₁,…,x_k}, = ‑ алгебраическая система. Значение терма t на элементах a₁,…,a_k A (t(a₁,…,a_k)) определяется по индукции:

1) если t есть переменная x_i (константный символ с), то значение t есть а_i (с);

2) если tF(t₁,…, t_n), где F ⁽ⁿ⁾ Σ, t₁(x₁,…,x_k),…,t_n(x₁,…,x_k) Т(Σ) и значения термов t₁,…, t_n на элементах a₁,…,a_k равны b₁,…,b_n то значение терма t есть F(b₁,…,b_n).

Теорема 2.Если = ‑ алгебраическая система, Ø≠X B, то B(Х)={t(a₁,…,a_n) | t T(Σ), a₁,…,a_n X}.

Пример 3. Построить подсистему алгебраической системы , порожденную множеством Х:

1) = X={1/2};

2) = X={1/2};

3) = X={22;-36}.

Решение. 1) Так как Т(Σ)={x₁, x₁x₂, (x₁x₂)x₃, x₁(x₂x₃),…}, то теореме 2 имеем A(X)={1/2, 1/2∙1/2, 1/2∙1/2∙1/2,…}={1/2, 1/8, 1/16,…}={1/2ⁿ| n≥1}.

2) Из предыдущего примера следует, что {1/2ⁿ| n≥1} A(X). Так как операция деления является сигнатурной, то 1/2ⁿ1/2^m=2^m-n A(X) для любых m, n≥1. Тогда C={2ⁿ| 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.

 

Машины Тьюринга

 

Построить машину Тьюринга , вычисляющую следующую функцию.