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

ВВЕДЕНИЕ

Логика – это наука о законах правильного мышления. Это одна из древнейших наук. Основные ее законы были сформулированы еще древнегреческим мыслителем Аристотелем. Идеи о построении логики на математической основе, т.е. по сути математической логики, были высказаны Лейбницем в начале 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-1 j<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. (теорема о замене). Если формула φ сигнатуры Σ получается из формулы ψ сигнатуры Σ заменой некоторого вхождения подформулы ψ' на формулу φ' сигнатуры Σ и φ'≡ψ', то φ≡ψ.

 

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

 

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

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

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