Программа курса математическая логика и терия алгоритмов

ВВЕДЕНИЕ

Логика – это наука о законах правильного мышления. Это одна из древнейших наук. Основные ее законы были сформулированы еще древнегреческим мыслителем Аристотелем. Идеи о построении логики на математической основе, т.е. по сути математической логики, были высказаны Лейбницем в начале 18-го века.

Современная математическая логика определяется как раздел математики, посвященный изучению математических доказательств и вопросов основания математики. Одна из главных причин широкого распространения математической логики – применение аксиоматического метода в построении различных математических теорий. Важным достижением математической логики является формулировка понятия алгоритмической вычислимости, которое по своей важности приближается к понятию натурального числа. Сегодня результаты математической логики находят свое применение в других отраслях математического знания, а также в программировании, проблемах искусственного интеллекта и других науках.

Данное учебно-практическое пособие соответствует учебной программе курса «Математическая логика и теория алгоритмов» для специальностей «Информационные системы и технологии», «Вычислительные машины, комплексы и сети».

Практикум разделен на три части. В первой содержится программа курса, во второй – краткое изложение теории и решение типовых задач, в третьей – задания для контрольных работ.

Достоинство практикума состоит в том, что при наличии такого количества задач он может быть использован как задачник, как раздаточный материал для выполнения контрольных работ, а также содержит не менее 30 различных вариантов индивидуального домашнего задания.

Студенты заочной формы обучения выполняют первые 10 вариантов контрольных заданий, например, 1-10, 39-49, выбирая задачи соответственно своему шифру.

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

Тема 1. «Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы».Формулы АВ. Эквивалентность формул АВ. Понятия ДНФ, КНФ, СДНФ, СКНФ.

Тема 2. «Логическое следствие в алгебре высказываний».Понятия логического следствия, противоречивого множества высказываний, тождественно истинного высказывания. Связь между этими понятиями.

Тема 3. «Исчисление высказываний (ИВ). Доказуемые формулы ИВ». Понятие исчисления. Язык ИВ. Определение формулы ИВ. Аксиомы и правила вывода ИВ. Доказуемые и выводимые формулы ИВ. Примеры доказуемых и выводимых формул ИВ.Теорема о дедукции в ИВ. Эквивалентные формулы ИВ.

Тема 4. «Логика предикатов (ЛП). Алгебраические системы. Подсистемы».Понятия сигнатуры, алгебраической системы данной сигнатуры, подсистемы, подсистемы, порожденной множеством. Примеры. Понятия терма данной сигнатуры, значение терма на кортеже в алгебраической системе. Теорема о подсистеме, порожденной множеством.

Тема 5. «Формулы ЛП».Понятие формулы данной сигнатуры. Определение истинности формулы ЛП на кортеже элементов в алгебраической системе. Примеры.

ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ

Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы

Эквивалентность формул АВ

Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие экви­валентности формул.

Формулы φ(x₁,…,x_n) и ψ(x₁,…,x_n) называются эквивалентными (φ ≡ ψ), если совпадают их таблицы истинности, т. е. ψ(е₁,…,e_n) = φ(e₁,…,e_n) для любых e₁,…,e_n {0,1}

Пример 3. Построив таблицы истинности формул x→y и y→x, убеждаемся, что (х→y) ≡ (y→x).

Легко видеть, что отношение ≡ является отношением эк­вивалентности, т. е. оно рефлексивно (φ≡φ), симметрично (еслиφ≡ψ, тоψ≡φ),транзитивно (если φ≡ψиψ≡χ, тоφ≡χ).

Отметим основные эквивалентности между формулами АВ:

1) φ∧φ≡φ, φ∨φ≡φ (законы идемпотентности);

2) φ∧ψ≡ψ∧φ, φ∨ψ≡ψ∨φ (законы коммутативности);

3) (φ∧ψ)∧χ≡φ∧(ψ∧χ), (φ∨ψ)∨χ≡φ∨(ψ∨χ) (законы ассоциативности);

4) φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ) (законы дистрибутивности)

5) (φ∧ψ)≡φ∨ψ, (φ∨ψ)≡φ∧ψ (законы де Моргана);

6) φ≡φ (закон двойного отрицания);

7) φ→ψ≡φ∨ψ;

8) φ∧(φ∨ψ)≡φ, φ∨(φ∧ψ)≡φ (законы поглощения);

9) φ∨(φ∧ψ)≡φ∨ψ, φ∨(φ∧ψ)≡φ∨ψ;

10) φ∧(φ∨ψ)≡φ∧ψ, φ∧(φ∨ψ)≡φ∧ψ.

Формула φ(x₁,x₂,…,x_n) называется выполнимой (опровержимой), если существует такой набор значений переменных, на котором формула принимает значение 1 (соответственно 0) .

Пример 4. Формула х∧у является одновременно выполнимой и опровержимой, поскольку 0∧0=0, а 1∧1=1.

Формула φ(x₁,…,x_n)называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) на всех наборах значений переменных.

Пример 5. Формула x∨x является тождественно истинной, а формула x∧x — тождественно ложной:

x	x∨x	x∧x

Утверждение 1. Если формула φ₁тождественно истинна, φ₀ — тождественно ложна, то для любых формул φи ψсправедливы следующие эквивалентности:

1) φ∧ φ₁≡φ; φ∨φ₀≡φ;

2) φ∨φ₁≡φ₁; φ∧φ₀≡φ₀;

3) (φ∧ψ→φ)≡φ₁; (φ→φ∨ψ)≡φ₁.

Логическое следствие в АВ

Говорят, что формула ψ(х₁,...,х_п)АВ является логическим следствием формул φ₁(х₁,...,х_п),…,φ_m(х₁,...,х_п) АВ(обозначается ), если для любых из соотношений следует . Формулы называются гипотезами.

Пример 1. Доказать, что φ, φ→ψ, ψ→χ Построим таблицы истинности для каждой формулы:

φ	ψ	χ	φ→ψ	ψ→χ

Из таблицы истинности видно, что когда все гипотезы принимают значение равное 1, формулаχтоже принимает значение 1, значит, χявляется логическим следствием, что и требовалось доказать.

Теорема 1.

1. Количество гипотез можно увеличивать.

2. Гипотезы можно переставлять в любом порядке.

3. тогда и только тогда, когда

4. тогда и только тогда, когда формула тождественно истина.

5. тогда и только тогда, когдаформула φ₁∧..∧φ_m∧ψтождественно ложна.

Исчисление высказываний

Пример 2.

1) Термами сигнатуры Σ={+,∙,≤,0} будут, например, 0, x, x+y, z(x+z)+0y, а 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; =(A,Σ)‑ алгебраическая система. Значение терма tпри значениях a₁,…,a_k Aпеременных x₁,…,x_k(t(a₁,…,a_k)) определяется по индукции:

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

2) если терм tесть ƒ(t₁,…, t_n),а значения t₁,…,t_nсуть b₁,…,b_n, то значение терма tесть ƒ(b₁,…, t_n).

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

Доказательство.Индукцией по числу шагов построения терма tполучаем, что если t(x₁,x₂,…,x_n) T(Σ) и a₁,…,a_n X, то t(a₁,…,a_n) А для любой подсистемы , содержащей X. Поэтому достаточно показать, что множество Y={t(a₁,…,a_n)׀t T(Σ), a₁,…,a_n X} замкнуто относительно операций системы . Пустьƒ⁽ⁿ⁾єT(Σ), t₁,…,t_m T(Σ), b_i=t(a₁,…,a_n), i {1,…,m}. Тогдаƒ(b₁,…,b_m) Y, посколькуƒ(t₁,…,t_m) T(Σ).

Таким образом, носитель подсистемы (X) состоит из всех элементов, которые получаются при подстановке элементов из Xв термы.

Пример 3.

1) Найдем носитель подсистемы (Х) системы =(Q , ∙) для множества X={1/2}. Так как сигнатура Σ системы В есть {∙}, то Т(Σ)={x₁, x₁x₂, (x₁x₂)x₃, x₁(x₂x₃),…}. По теореме 2 получаем B(X)={1/2, 1/2∙1/2, 1/2∙1/2∙1/2,…}={1/2, 1/8, 1/16,…}={1/2ⁿ,n≥1}.

2)Если =(Q\{0}, . , : ) X={1/2}, то, поскольку по срав­нению с предыдущим примером сигнатура дополняется опе­рацией деления, множество В(Х) содержит числа 1/2ⁿ:1/2^m=2^m-n, m, n≥1, т.е. C={2ⁿ׀nєZ} B(X).Так как множество С замкнуто относительно операций умножения и деления. т.е. (C, Σ) является подсистемой системы и содержит множество X, то В(Х) С. Следовательно, B(Х)=С.

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

= Z; -

X={22;-36}.

Решение.Надо определить какую подсистему порождают

22;-36 “-“. Таке как 2=22-8 (-36)-14 22 и любое число, получаемое из чисел 22, -36 с помощью операции вычитания четное, то

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

= R\{0};:

Х={ ; }.

Решение.

={ z }.

Формулы ЛП

Большинство определений этого параграфа будут индуктивными.

Введем понятие атомарной формулы сигнатуры Σ:

1) если t₁, t₂, T(Σ), то t₁=t₂‑ атомарная формула:

2) если P(n) Σ‑предикатный символ, t₁,t₂,…,t_n T(Σ), то Р(t₁,t₂,…,t_n)‑ атомарная формула;

3) никаких атомарных формул, кроме построенных по пп. 1, 2, нет.

Формула сигнатуры Σ определяется следующим образом:

1) атомарная формула есть формула;

2) если φ, ψ - формулы, то φ, (φ∧ψ), (φ∨ψ), (φ→ψ), xφ, xφ‑ формулы;

3) никаких формул, кроме построенных по пп. 1, 2, нет.

Символы , использованные в определении, называются соответственно квантором всеобщности и квантором существования и читаются "для любого"и "существует". Все соглашения относительно расстановок скобок, принятые в алгебре высказываний, остаются в силе и для формул логики предикатов. Кроме того, вместо записей x₁… x_nφи x₁… x_nφбудем использовать записи x₁,…,x_nφи x₁,…,x_nφ.

Определим подформулы формулы φсигнатуры Σ:

1) если φ‑атомарная формула, то φ‑ее единственная
подформула;

2) если φимеет вид φ₁, или xφ₁,или xφ₁, то подформула формулы φ–этолибо φ, либо подформула формулы φ₁;

3) если φимеет вид φ₁∧φ₂, или φ₁∨φ₂, или φ₁→φ₂, то подформула формулы φ‑ это либо φ, либо подформула формулы φ₁, либо подформула формулы φ₂;

4) других подформул формулы φ, кроме построенных по
пп. 1, 2, 3, нет.

Пример 1. Пусть Σ={F⁽²⁾,P⁽¹⁾}, φ= x( y(x=F(z,y))∨P(z))‑ формула сигнатуры Σ. Тогда x( y(x=F(z,y))∨P(z)), y(x=F(z,y))∨P(z), y(x=F(z,y)),x=F(z,y)),P(z)‑все подформулы формулы φ.

Говорят, что вхождение переменной х в формулу φ связано в φ, если оно находится в терме или предикате подформулы формулы φвида xψили xψ; в противном случае это вхождение называется свободным в φ. Переменная х называется свободной (связанной), если некоторое вхождение х в φсвободно (связано).

Пример 2. Пусть S={P₁⁽¹⁾,P₂⁽²⁾}. Рассмотрим формулы:

1) P₁(x);

2) Р₂(x,y)→ xP₁(x);
3) x(P₂(x,y)→P₁(x)).

Переменная х в первой формуле является свободной, во второй - и свободной, и связанной, в третьей ‑ связанной: переменная у во всех формулах свободна.

Пример 3.

Выписать все подформулы формулыφ, определить свободные и связанные вхождения переменных.

φ x z y(x y+z) ((z∙2=u)→ u(u=x+z)).

Определить все свободные и связанные переменные формулы φ.

Решение. Выпишем подформулыформулы φ.

1) x y+z,

2) y(x y+z),

3) z y(x y+z),

4) x z y(x y+z),

5) z 2=u,

6) u=x+z,

7) u(u=x+z),

8) (z 2=u)→ u(u=x+z),

9) φ.

Поскольку существуют связанные и свободные вхождения переменной х в формулу φ, то хявляется связанной и свободной переменной. Переменныеuи zтоже связанные и свободные. Переменнаяy связанная.

Предложением или замкнутой формулой сигнатуры Σ называется формула сигнатуры Σ, не имеющая свободных переменных.

Запись φ(x₁,…,x_n)будет означать, что все свободные переменные формулы φсодержатся в множестве {x₁,…, x_n}.

Пример 1.

Записать формулу φ(x), истинную в тогда и только тогда, когда х четно.

Решение.

φ(x)= y(x=y+y).

Пример 2.

Записать формулу φ'(x,y,z), истинную в тогда и только тогда, когда z‑наименьшее общее кратное чисел х и y.

Решение.

φ'(x,y,z)=ψ(x,y,z)∧χ(x,y,z),где формула ψ «говорит» о том, что z делится на xи на y, а формула χ "говорит"о том, что zделит все общие кратные х и у, т. е. является наименьшим из всех общих кратных:

ψ= u,∨(z=u∙x∧z=∨х∙y),

χ= w( u,∨(w=u∙x∧w=∨х∙y)→ w₁(w=w₁∙z)).Итак,

φ'(х,у,z)= u,∨(z=u∙x∧z=х∙y)∧ w( u,∨(w=ux∧w=хy)→ w₁(w=w₁z)).

Логическое следствие в ЛП

Через обозначим кортеж переменных ; через ‑ .

Определение. Пусть φ₁( ),…,φ_n( ), ψ( )– формулы сигнатуры ∑. Формула ψназывается логическим следствием формул φ₁,…,φ_n (обозначается φ₁,…,φ_n╞ ψ), если для любой алгебраической системы сигнатуры ∑

╞ ( φ₁( ) … φ_n( )→ψ( )).

Пример 1.

Доказать, что φ₁( )→φ₂( ),φ₂( )→φ₃( )╞φ₁( )→φ₃( )(1)

гдеφ₁( ),φ₂( ),φ₃( ) – формулы сигнатуры ∑.

Пусть =‹А, ∑› ‑ произвольная система сигнатуры ∑. Необходимо указать, что ╞ ((φ₁( )→φ₂( )) ((φ₂( )→φ₃( ))→(φ₁( )→φ₃( ))).

Пусть и ╞ ((φ₁( )→φ₂( )) ((φ₂( )→φ₃( )).

Покажем, что ╞(φ₁( )→φ₃( ) (2)

Предположим, что ╞φ₁( ). Так как ╞(φ₁( )→φ₂( ), то ╞φ₂( ).

Так как ╞φ₂( )→φ₃( ), то ╞φ₃( ).

Таким образом (2), а, следовательно, и (1), доказано.

Исчисление предикатов

Зафиксируем некоторую произвольную сигнатуру Σ и определим исчисление предикатов сигнатуры Σ (ИП^Σ).

Формулами ИП^Σбудут формулы сигнатуры Σ.

Примем следующие соглашения. Пусть x₁,…,x_n‑ переменные, t₁,…,t_n‑ термы сигнатуры Σ и φ‑ формула сигнатуры Σ. Запись будет обозначать результат подстановки термов t₁,…,t_nвместо всех свободных вхождений в φпеременных x₁,…,x_n соответственно, причем, если в тексте встречается запись , то предполагается, что для всех i={1,...,n} ни одно свободное вхождение в φпеременной x_i не входит в подформулу φвида y или y , где у - переменная, входящая в t_i.

Аксиомами ИП^Σ являются аксиомы вида 1-10 ИВ, а также аксиомы

11) xφ→(φ)_t^x;

12) (φ)_t^x→ xφ;

13)x=x;

14)x=y→((φ)_x^z→(φ)_y^z).

Формулы 1-14 называются схемами аксиом ИП^Σ.

Правила вывода ИП^Σ:

1. φ, φ → ψ ,

ψ

2. ψ →φ ,

ψ→ xφ

3. φ → ψ ,

xφ → ψ

где в правилах 2 и 3 переменная x не входит свободно в ψ.

Доказательством в ИП^Σформулы φназывается такая последовательность φ₀,…,φ_nформул ИП^Σ, что φ_n φи для каждого i≤n формула φ_i удовлетворяет одному из следующих условий:

1) φ_i‑аксиома ИП^Σ;

2) φ_i получается из некоторых φ₁,…, φ_i-1, по одному из правил вывода 1-3.

Если существует доказательство в ИП^Σ формулы φ, то φназывается доказуемой в ИП^Σ или теоремой ИП^Σ (обозначаем ├φ).

Выводом в ИП^Σформулы φ из множества формул φ₁,…, φ_m называется такая последовательность ψ₁,…,ψ_kформул ИП^Σ, что φ_n φ и для каждого i≤n формула φ_i удовлетворяет одному из следующих условий:

1) φ_i‑аксиома ИП^Σ;

2) φ_i принадлежит Г;

3) φ_iполучается из некоторых ψ₁,…,ψ_i-1j<i, по одному из правил вывода 1-3, причем при применении правил 2 и 3 переменная х не должна входить ни в одну формулу из Г свободно.

Если существует вывод в ИП^Σ формулы φиз множества формул φ₁,…, φ_n, то φназывается выводимой в ИП^Σ из Г (обозначаем Г├φ). При этом Г называется множеством гипотез. Очевидно, что доказуемость формулы эквивалентна ее выводимости из пустого множества гипотез. Так же, как в исчислении высказываний, определяется понятие квазивывода. Если Г={ψ₁,…,ψ_n}, то вместо Г├φпишем ψ₁,…,ψ_n├φ.

Формула ψсигнатуры Σ называется тавтологией, если она получается из формулы φисчисления высказываний, доказуемой в исчислении высказываний, путем замены всех ее пропозициональных переменных x₁,…,x_nна формулы ψ₁,…,ψ_nсигнатуры Σ соответственно. Формулу φпри этом называют основой тавтологии.

Утверждение 1.Любая тавтология φсигнатуры Σ доказуема в ИП^Σ.

Следствие 1. Если φи ψ‑ пропозиционально эквивалентные формулы сигнатуры Σ, то φи ψ‑эквивалентные формулы сигнатуры Σ.

В исчислении предикатов ИП^Σ справедлива теорема о дедукции.

Теорема 1.(о дедукции).ПустьГ – множество формул ИП^Σ,φ,ψ – формулы ИП^Σ. Тогда Г,φ├ψ, Г├φ→ψ.

Эквивалентные формулыИП

Определение эквивалентных формул, утверждения 3,4 при замене формул φ, ψ, χИВ на формулы ИП^Σ имеют место.

Утверждение 1.В ИП^Σ выполнимы все эквивалентности ИВ из теоремы 5.

Доказательство.Выполнимость в ИП^Σ всех эквивалентностей исчисления высказываний следует из следствия 3.

Утверждение 2. В ИП^Σ выполнимы следующие эквивалентности, в которых предполагается, что переменная ж не входит свободно в формулу ψ, а переменная у не входит в формулу φ:

1) xφ≡ xφ,1^\) xφ≡ xφ,

2) x(φ∧ψ)≡ xφ∧ψ, 2^\) x(φ∨ψ)≡ xφ∨ψ

3) x(φ∧ψ)≡ xφ∧ψ,3^\) x(φ∨ψ)≡ xφ∨ψ,

4) xφ≡ .4^\) xφ≡

Пример. 1.Докажем эквивалентность а). Построим квазивывод формулы xφ→ xφ из Ø:

1. φ→ xφ‑ аксиома 12;

2. xφ→φ‑ к п.1 применили утверждение 3:

3. xφ→ xφ‑ к п.2 применили правило вывода 2.
Построим квазивывод формулы xφ→ xφиз Ø:

1. xφ→φ‑ аксиома 11;

2. φ→ xφ‑ к п.1 применили утверждение 3;

3. xφ→ xφ‑ к п. 2 применили правило вывода 3;

4. xφ→ xφ‑ к п.З применили утверждение 3.

Пример. 2. Докажем эквивалентность г). Построим квазивывод формулы x(φ∧ψ)→ xφ∧ψиз Ø:

1. x(φ∧ψ)→φ∧ψ‑ аксиома 11;

2. φ∧ψ→φ‑ утверждение 1;

3. x(φ∧ψ)→φ‑ к пп.1,2 применили утверждение 1;

4. x(φ∧ψ)→ xφ‑ к п.4 применили правило вывода 2;

5. φ∧ψ→ψ‑ утверждение 1;

6. x(φ∧ψ)→ψ‑ к пп.1,5 применили утверждение 1;

7. ( x(φ∧ψ)→ xφ)→(( x(φ∧ψ)→ψ)→( x(φ∧ψ)→ xφ∧ψ))‑ аксиома 5;

8. x(φ∧ψ)→ xφ∧ψ‑ к пп.4.6.7 применили правило вывода 1.

Построим квазивывод формулы xφ∧ψ → x (φ∧ψ) из Ø:

1. xφ∧ψ→ xφ‑ аксиома 3;

2. xφ→φ‑аксиома 11;

3. xφ∧ψ→φ‑ к пп.1,2 применили утверждение 1;

4. xφ∧ψ→ψ‑аксиома 4;

5. ( xφ∧ψ→φ)→(( xφ∧ψ→ψ)→( xφ∧ψ→φ∧ψ))‑ аксиома 5;

6. xφ∧ψ→φ∧ψ‑ к пп.3,4,5 применили правило вывода 1;

7. xφ∧ψ→ x(φ∧ψ)‑к п.6 применили правило вывода 2.

Теорема 1. (теорема о замене). Если формула φсигнатуры Σ получается из формулы ψсигнатуры Σ заменой некоторого вхождения подформулы ψ'на формулу φ' сигнатуры Σ и φ'≡ψ', то φ≡ψ.

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

Машина Тьюринга – это система, работающая в дискретные моменты времени и состоящая из следующих частей:

конечная лента,разбитая на конечное число ячеек.В каждый момент времени в ячейках записаны буквы из некоторого алфавита (где , ), называемого внешним алфавитом машины.Ячейка, в которой записан символ , называется пустой.Если в какой–то момент времени лента имеет ячеек, то состояние ленты полностью описывается словом , где ­– состояние первой (слева) ячейки, – состояние второй ячейки и т.д.

Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и имеет некоторое состояние из конечного множества внутренних состояний , .Состояние