WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

Министерство по образованию и науке Российской Федерации

Владивостокский государственный университет

экономики и сервиса

_

А.А. СТЕПАНОВА

Т.Ю. ПЛЕШКОВА

Е.Г. ГУСЕВ

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

Практикум

Владивосток Издательство ВГУЭС 2010 ББК 22.12 С 79 Рецензенты: Г.К. Пак, канд. физ.-мат наук, проф.

каф. алгебры и логики (ДВГУ);

А.А. Ушаков, канд. физ.-мат. наук, доцент каф. математического моделирования и информатики (ДВГТУ) Степанова, А.А., Плешкова, Т.Ю., Гусев, Е.Г.

С 79 МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ

АЛГОРИТМОВ [Текст] : практикум. – Владивосток :

Изд-во ВГУЭС, 2010. – 48 с.

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

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

ББК 32. Печатается по решению РИСО ВГУЭС © Издательство Владивостокский государственный университет экономики и сервиса,

ВВЕДЕНИЕ

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

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

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

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

1. ПЕРЕЧЕНЬ ТЕМ Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)». Формулы АВ. Эквивалентность формул АВ. Понятия дизъюнктивной нормальной формы (ДНФ), конъюнктивной нормальной формы (КНФ), СДНФ, СКНФ.

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

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

Аксиомы и правила вывода ИВ. Доказуемые и выводимые формулы ИВ.

Примеры доказуемых и выводимых формул ИВ. Теорема о дедукции в ИВ. Эквивалентные формулы ИВ.

Тема 4. «Логика предикатов (ЛП). Алгебраические системы.

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

Тема 5. «Формулы ЛП». Понятие формулы данной сигнатуры.

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

Тема 6. «Истинность формулы ЛП в алгебраической системе».

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

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

Тема 9. «Пренексная нормальная форма для формул ИП». Понятия ДНФ и ПНФ для формул ИП. Теорема о существовании для любой формулы ИП эквивалентной ей ПНФ.

Тема 10. «Машины Тьюринга». Определение машины Тьюринга.

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

Тема 11. «Примитивно рекурсивные функции». Понятия базисных функций, операторов суперпозиции, примитивной рекурсии, примитивно рекурсивных функций. Примеры.

Тема 12. «Частично рекурсивные функции». Понятия оператора минимизации, частично рекурсивных функций. Примеры. Эквивалентность классов функций, вычислимых по Тьюрингу, с классом частично рекурсивных функций.

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

2.1.1. Формулы алгебры высказываний Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно.

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

Поставим в соответствие высказыванию Р логическую переменную х, которая принимает значение 1, если Р истинно, и 0, если Р ложно.

Если имеется несколько высказываний, то из них можно образовать различные новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные – сложными. Соответственно из логических переменных можно составлять различные конструкции, которые образуют формулы алгебры высказываний.

Итак, пусть {хii I} – некоторое множество логических переменных.

Определим по индукции понятие формулы алгебры высказываний (АВ):

1) любая логическая переменная является формулой АВ (называемой атомарной);

2) если и – формулы АВ, то выражения ¬, (), (), () являются формулами АВ;

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

Если формула АВ построена из логических переменных, принадлежащих множеству {х1,х2,…,xn}, то будем писать (x1,…xn).

Символы ¬,,, использованные в определении, называются логическими операциями или связками и читаются соответственно: отрицание, конъюнкция, дизъюнкция и импликация.

Эти логические операции следующим образом интерпретируются в русском языке: ¬ – «не », () – и, ( ) – или, ( ) – если, то.

Вместо ¬ часто пишут, вместо ( ) – (& ), ( • ) или ().

Действия логических операций задаются таблицами истинности, каждой строке которых взаимно однозначно сопоставляется набор значений переменных, входящих в формулу, и соответствующее этому набору значение полученной формулы:

Пример 1. Построить таблицу истинности для формулы ((xy)((¬yz)¬x)).

Решение. Будем строить таблицу истинности последовательно в соответствии с шагами построения формулы :

Легко заметить, что таблица истинности для совпадает с таблицей истинности для ¬x. В дальнейшем выяснится причина этого совпадения.

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

1. Внешние скобки не пишутся. Например, вместо высказывания ((x y)z) пишется (x y)z.

2. На множестве {¬,,, } вводится транзитивное отношение «быть более сильным» следующим образом: наиболее сильная связка – ¬, далее идут и, самая слабая связка –.

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

Пример 2. В формуле ((x y)z)u)) все скобки можно опустить:

х yzu.

2.1.2. Логическое следствие в алгебре высказываний называются гипотезами.

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

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

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

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

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

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

Множество формул 1,…,n АВ называется противоречивым или несовместным, если формула 1…n тождественно ложна.

Пример 6. Множество формул xy, ¬x, ¬y противоречиво.

Теорема 1. Пусть – 1,..,m, – формулы АВ. Следующие условия эквивалентны:

3) {1,..,m,¬} – противоречивое множество формул;

5) 1..m¬ – тождественно ложная формула.

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

Формулы и АВ называются эквивалентными (обозначается ), если или, т.е. совпадают их таблицы истинности.

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

Легко видеть, что отношение является отношением эквивалентности на множестве формул АВ, т. е. оно рефлексивно (), симметрично (если, то ), транзитивно (если и, то ), где,, – произвольные формулы АВ.

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

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

2), (законы коммутативности);

3) ()(), ()() (законы ассоциативности);

4) ()()(), ()()() (законы дистрибутивности) 5) ¬()¬¬, ¬()¬¬ (законы де Моргана);

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

8) (), () (законы поглощения);

10) (¬), ¬()¬.

К перечисленным ранее соглашениям, пользуясь законами ассоциативности, добавляем следующее: в формулах вида (), (), () и () скобки можно опускать.

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

2.1.4. Дизъюнктивные и конъюнктивные нормальные Если х — логическая переменная, {0,1}, то выражение называется литерой. Литеры х и ¬х называются контрарными.

Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.

Пример 8. Формулы x¬y¬z и xyx¬x – дизъюнкты, формулы ¬xyz и xy¬x – конъюнкты, а ¬x является одновременно и дизъюнктом, и конъюнктом.

Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).

Пример 9. Формула (x¬y)(yz) – ДНФ, формула (хz¬y)(xz)y – КНФ, а формула x¬y является одновременно КНФ и ДНФ.

Теорема 2. Для любой формулы АВ существует ДНФ (КНФ) АВ такая, что.

Опишем алгоритм приведения формулы к ДНФ.

1. Выражаем импликацию, участвующую в построении формулы, через дизъюнкцию и отрицание, используя эквивалентность 2. Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания, пользуясь законом двойного отрицания.

3. Используя закон дистрибутивности ()()(), преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

В результате применения пп. 1–3 получается ДНФ, эквивалентная исходной формуле.

Пример 10. Привести к ДНФ формулу ¬((xy)¬(yz)).

Решение. Выразим логическую операцию через и ¬:

¬((¬xy)¬(¬yz)). Воспользуемся законами де Моргана и двойного отрицания: ¬(¬xy)¬¬(¬yz)(¬¬x¬y)(¬yz)(x¬y)(¬yz).

Используя закон дистрибутивности, приводим формулу к ДНФ:

(x¬y¬y)(x¬yz)(1) (x¬y)(x¬yz)(2) x¬y (для преобразования (1) использовался закон идемпотентности, для (2) – закон поглощения). Таким образом, формула эквивалентными преобразованиями приводится к формуле x¬y, являющейся одновременно ДНФ и КНФ.

Приведение формулы к КНФ производится аналогично приведению ее к ДНФ, только вместо п. 3 применяется п. 3':

3'. Используя закон дистрибутивности ()()(), преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.

Пример 11. Привести к КНФ формулу (xy)((¬yz)¬x).

Решение. Преобразуем формулу к формуле, не содержащей :

(¬xy)(¬(¬¬yz)¬x). В полученной формуле перенесем отрицание (¬xy)((¬¬¬y¬z)¬x)(¬xy)((¬y¬z)¬x). Используя закон (¬xy)(¬x¬y)(¬x¬z). Упростим полученную формулу:

(¬xy)(¬x¬y)(¬x¬z)(1)(¬x(y¬y))(¬x¬z)(2)¬x(¬x¬z) (3)¬x (для преобразования (1) использовался закон дистрибутивности, для (2) – эквивалентность 1 утверждения 1, для (3) – закон поглощения).

Таким образом, формула эквивалентными преобразованиями приводится к формуле ¬x, являющейся одновременно ДНФ и КНФ.

2.1.5. Совершенные дизъюнктивные и конъюнктивные Пусть (х1,..., хn) – набор логических переменных, =(1,…,n) – набор нулей и единиц. Конституентой единицы набора называется конъюнкт К1(1,…,n)=x11x22…xnn. Конституентой нуля набора называется дизъюнкт К0(1,…,n)=x11-1x21-2…xn1-n.

Отметим, что K1(1,2,…,n)=1 (K0(1,2,…,n)=0) тогда и только тогда, когда x1=1, x2=2,…, xn=n.

Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых, совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная хi из набора {х1,...,хп} входит ровно один раз, причем входит либо сама хi, либо ее отрицание ¬xi.

Пример 12. Формула x1¬x2x3 есть конституента единицы K1(1,0,1), формула xy¬z есть конституента нуля K0(0,0,1), формула (x1¬x2)(¬x1x2) – СДНФ, формула (xy¬z)(¬x¬yz)(¬xyz) – СКНФ, а формула (x1¬x2x3)(¬x1x2x3)(x1¬x2x3) не является СДНФ.

Теорема 3. Для любой не тождественно ложной (не тождественно истинной) формулы АВ существует единственная СДНФ (СКНФ) АВ такая, что.

Заметим, что единственность формулы в формулировке теоремы понимается с точностью до порядка следования конъюнктивных сомножителей и дизъюнктивных слагаемых в этой формуле.

Опишем алгоритм приведения формулы к СДНФ.

1. Приводим данную формулу к ДНФ.

2. Преобразовываем ее конъюнкты в конституенты единицы с помощью следующих действий:

а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ;

б) если в конъюнкт одна и та же литера x входит несколько раз, то удаляем все литеры х, кроме одной;

в) если в конъюнкт x11…xkk не входит переменная у, то этот (x11…xkky)(x11…xkk¬y);

г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них.

В результате получается СДНФ.

Пример 13. Найти СДНФ для ДНФ (x¬x)x(yzy).

Решение. Имеем x(yz)(xy)(x¬y)(xyz)(¬xyz) (xyz)(xy¬z)(x¬yz)(x¬y¬z)(xyz)(¬xyz) (xyz)(xy¬z)(x¬yz)(x¬y¬z)(¬xyz).

Описание алгоритма приведения формулы к СКНФ аналогично вышеизложенному описанию алгоритма приведения формулы к СДНФ и оставляется читателю в качестве упражнения.

2.2.1. Определение формального исчисления Введем общее понятие формального исчисления. Будем говорить, что формальное исчисление I определено, если выполняются четыре условия.

1. Имеется некоторое множество А символов – алфавит исчисления I. Конечные последовательности символов называются словами или выражениями исчисления I. Обозначим через S множество всех слов алфавита исчисления I.

2. Задано подмножество F S, называемое множеством формул исчисления I. Элементы множества F называются формулами.

3. Выделено множество Ах F формул, называемых аксиомами исчисления I.

4. Имеется конечное множество K отношений R1,R2,…,Rn между формулами, называемых правилами вывода, причем если (1,…,m,) Ri, то называется непосредственным следствием формул 1,…,m по правилу Ri.

Итак, исчисление I есть четверка (А,F,Ах,K).

Выводом в исчислении I называется последовательность формул 1,2,…,n такая, что для любого i (1in) формула i есть либо аксиома исчисления I, либо непосредственное следствие каких-либо предыдущих формул.

Формула называется теоремой исчисления I, выводимой в I, или доказуемой в I, если существует вывод 1,…,n,, который называется выводом формулы или доказательством теоремы.

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

Исчисление называется непротиворечивым, если не все его формулы доказуемы.

2.2.2. Система аксиом и правил вывода Используя понятие формального исчисления, определим исчисление высказываний (ИВ).

Алфавит ИВ состоит из букв x,y,z,u,v, возможно с индексами (которые называются пропозициональными переменными), логических символов (связок) ¬,,,, а также вспомогательных символов (,).

Множество формул ИВ определяется индуктивно:

а) все пропозициональные переменные являются формулами ИВ;

б) если, – формулы ИВ, то ¬, (), (), ( ) – формулы ИВ;

в) выражение является формулой ИВ тогда и только тогда, когда это может быть установлено с помощью пунктов "а" и "б".

Таким образом, любая формула ИВ строится из пропозициональных переменных с помощью связок ¬,,,.

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

Подформулой формулы ИВ называется подслово, являющееся формулой ИВ.

Под длиной формулы будем понимать число символов, входящих в слово.

Аксиомами ИВ являются следующие формулы для любых формул,, ИВ:

2) ()((())());

5) ()(()(()));

8) ()((x)(()));

Указанные формулы называются схемами аксиом ИВ. При подстановке конкретных формул в какую-либо схему получается частный случай схемы аксиом.

Единственным правилом вывода в ИВ является правило заключения (modus ponens): если и – выводимые формулы, то – также выводимая формула. Символически это записывается так:

Говорят, что формула выводима в ИВ из формул 1,…,m (обозначается 1,…,m), если существует последовательность формул 1,…,k,, в которой любая формула либо является аксиомой, либо принадлежит множеству формул {1,…,m}, называемых гипотезами, либо получается из предыдущих по правилу вывода. Выводимость формулы из () равносильна тому, что – теорема ИВ или доказуемая формула ИП.

Пример 1. Покажем, что.

Решение. Построим вывод данной формулы:

1) (())(((())()) (схема аксиом 2);

2) () (схема аксиом 1);

3) ((()))() (к пп. 2 и 1 применили правило вывода);

4) (()) (схема аксиом 1);

5) (к пп. 4 и 3 применили правило вывода).

Квазивыводом в ИВ формулы из формул 1,…,m называется последовательность формул 1,…,k,, в которой любая формула, либо принадлежит множеству формул {1,…,m}, либо выводима из предыдущих.

Замечание 1. Если существует квазивывод в ИВ формулы из формул 1,…,m, то выводима в ИВ из формул 1,…,m.

Пример 2. Покажем, что,.

Решение: Построим квазивывод формул из и :

1) (гипотеза);

2) (гипотеза);

3) ()(()( )) (схема аксиом 5);

4) (теорема ИВ по примеру 1);

5) (()( )) (к пп. 4 и 3 применили правило вывода);

6) () (схема аксиом);

7) (к пп. 2 и 6 применили правило вывода);

8) (к пп. 7 и 5 применили правило вывода);

9) (к пп. 1 и 8 применили правило вывода).

Пример 3. Покажем, что ¬¬.

Решение. Построим квазивывод формулы ¬¬ из формулы :

1) (гипотеза);

2) (¬)((¬¬)¬¬) (схема аксиом 9);

3) (¬) (схема аксиом 1);

4) ¬ (к пп. 1 и 3 применили правило вывода);

5) (¬¬)¬¬ (к пп. 4 и 2 применили правило вывода);

6) ¬¬ (теорема ИВ по примеру 2);

7) ¬¬ (к пп. 6 и 4 применили правило вывода).

2.2.3. Теорема о дедукции в исчислении высказываний Теорема 1 (о дедукции). Пусть 1,…,m,, – формулы ИВ. Тогда Пример 4. Покажем, что ¬¬;

Решение. По теореме о дедукции Строим вывод формулы ¬ из формул,¬:

1) (гипотеза);

2) ¬ (гипотеза);

3) ()((¬)¬) (схема аксиом 9);

4) (¬)¬ (к пп. 1 и 3 применили правило вывода);

5) ¬(¬) (схема аксиом 1);

6) ¬ (к пп. 2 и 5 применили правило вывода);

7) ¬ (к пп. 6 и 4 применили правило вывода).

Пример 5. Покажем, что ()() Решение. По теореме о дедукции Строим вывод формулы из формул (),,:

2.2.4. Теорема о замене в исчисления высказываний Формулы и назовем эквивалентными (обозначим ), если Замечание 2. Для любых формул и ИВ Утверждение 1. Отношение является отношением эквивалентности на множестве формул ИВ, т.е. для любых формул,, ИВ:

Утверждение 2. Для любых формул,, 1, 1, 2, 2 ИВ таких, что 11 и 22, имеют место эквивалентности:

Теорема 2 (о замене). Пусть – формула ИВ, – ее подформула, ' получается из заменой некоторого вхождения на формулу ' ИВ и '. Тогда '.

2.2.5. Свойства выводимых и эквивалентных формул Утверждение 3. Пусть,, – формулы ИВ. Тогда 5), (свойство транзитивности);

6) ()() (свойство перестановочности посылок);

7) () (свойство соединения и разъединения посылок);

8) ¬¬ (свойство контрапозиции).

Доказательство. Пункты 1, 4, 6, 8 доказаны в примерах 13, 14, 16, 17.

Докажем пункт 7. Покажем, что (). По теореме о дедукции Строим вывод формулы из формул (), :

1) () (гипотеза);

2) (гипотеза);

3) (схема аксиом 3);

4) (к пп. 2 и 4 применили правило вывода);

5) (схема аксиом 4);

6) (к пп. 2 и 5 применили правило вывода);

7) (к пп. 4 и 1 применили правило вывода);

8) (к пп. 6 и 7 применили правило вывода).

Покажем, что (). По теореме о дедукции Строим квазивывод формулы из формул,, :

1) (гипотеза);

2) (гипотеза);

3) (гипотеза);

4) (к п.п. 2 и 3 применили свойство 4);

5) (к пп. 4 и 1 применили правило вывода).

2.2.6. Основные эквивалентности исчисления высказываний Теорема 3. Пусть,, – формулы ИВ. Тогда имеют место следующие эквивалентности:

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

2), (законы коммутативности);

3) ()(), ()() (законы ассоциативности);

4) ()()(), ()()() (законы дистрибутивности);

5) ¬()¬¬, ¬()¬¬ (законы де Моргана);

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

Доказательство. В примере 3 показано, что ¬¬. Покажем, что ¬¬. По теореме о дедукции что выполняется, т.к. ¬¬ – частный случай схемы аксиом 10.

Докажем закон де Моргана ¬()¬¬. Строим квазивыводформулы ¬()¬¬:

1) (¬(¬¬))((¬(¬¬))(¬(¬¬))) (схема аксиом 5);

2) ¬¬¬ (схема аксиом 6);

3) ¬(¬¬)¬¬ (к п. 2 применили свойство контрапозиции);

4) ¬¬ (схема аксиом 10);

5) ¬(¬¬) (к пп. 3 и 4 применили свойство транзитивности);

6) ¬(¬¬) (получается аналогично формуле 5);

7) (¬(¬¬))(¬(¬¬)) (к пп. 5 и 1 применили правило вывода);

8) ¬(¬¬) (к пп. 6 и 7 применили правило вывода);

9) ¬()¬¬(¬¬) (к п. 7 применили свойство контрапозиции);

10) ¬¬(¬¬)(¬¬) (схема аксиом 10);

11) ¬()¬¬ (к пп. 9 и 10 применили свойство транзитивности).

Строим квазивывод формулы ¬¬¬():

1) (¬¬())((¬¬())((¬¬)¬())) (схема аксиом 8);

2) (схема аксиом 3);

3) ¬¬() (к п. 2 применили свойство транзитивности);

4) (схема аксиом 4);

5) ¬¬() (к п. 4 применили свойство транзитивности);

6) (¬¬())((¬¬)¬()) (к пп. 3 и 1 применили правило вывода);

7) (¬)¬() (к пп. 5 и 6 применили правило вывода).

Таким образом, закон де Моргана ¬()¬¬ доказан.

Формула ИВ, получаемая из ДНФ (КНФ) АВ заменой логических переменных на переменные ИВ, называется ДНФ (КНФ) ИВ.

Теорема 2. Для любой формулы ИВ существует ДНФ (КНФ) ИВ такая, что.

2.2.7. Полнота и непротиворечивость Формула (x1,…,xn) ИВ называется тождественно истинной (обозначается ), если (x1,…,xn) – тождественно истинная формула как формула алгебры высказываний.

Теорема 4 (о полноте). Формула ИВ доказуема тогда и только тогда, когда тождественно истинна:

Таким образом, для того чтобы установить, доказуема ли формула ИВ, достаточно составить ее таблицу истинности. Как известно, существует эффективный алгоритм построения таблицы истинности, и, значит, ИВ разрешимо. Кроме того, из теоремы о дедукции и теоремы о полноте легко следует, что отношение эквивалентности в АВ и ИВ совпадают.

Теорема 5 (о непротиворечивости). ИВ непротиворечиво.

Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула х¬х. Следовательно, ИВ непротиворечиво.

Схема аксиом называется независимой в исчислении, если хотя бы один ее частный случай не доказуем в исчислении без этой схемы.

Теорема 6. Схемы аксиом ИВ независимы.

Часто объектом изучения в математике служит множество вместе с определенной на нем структурой. Например, поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь геометрических объектов с операциями над числами, множества с выделенными на них бинарными отношениями. Все эти структуры образуют алгебраические системы, представляющие собой некоторые миры с определенными на них законами. Перейдем к точному определению алгебраической системы.

Напомним, что п-местным предикатом (отношением) на множестве А называется любое подмножество множества Аn; п-местной алгебраической операцией на множестве А называется функция F:AnA, А. Отметим, что поскольку операция F является функцией, для любого набора (x1,…,xn) An результат применения операции F(x1,…,xn) однозначно определен. Так как область значений операции F лежит в множестве А, то будем говорить, что операция F замкнута на множестве А.

Сигнатурой называется совокупность предикатных и функциональных символов с указанием их местности. Константным символом или просто константой называется 0-местный функциональный символ. Если – функциональный или предикатный символ, то его местность обозначается через (). Часто п-местные предикатные и функциональные символы будем обозначать соответственно через Р(n) и F(n), возможно с индексами.

Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, для отношения порядка, | для отношения делимости, 0 для константного символа и другие, то мы просто пишем ={}, ={,+,..., 0} и т.д.

Алгебраической системой сигнатуры называется пара = где А – непустое множество и каждому n-местному предикатному (функциональному) символу из поставлен в соответствие n-местный предикат (соответственно операция) на А. Множество А называется носителем, или универсумом алгебраической системы. Предикаты и функции, соответствующие символам из, называются их интерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры, возможно с индексом A. Заметим, что интерпретацией любого константного символа является некоторый элемент из А. Если ={1,…, n} – конечная сигнатура, то в записи Пример 1. 1) Набор является алгебраической системой с двумя двухместными операциями.

2) Набор является алгебраической системой с бинарным отношением, двухместными операциями +,, одноместной операцией ': пn+1 и нуль-местной операций 1.

3) Набор не является алгебраической системой, поскольку деление не является операцией на множестве, а элемент не принадлежит.

Алгебраическая система = называется подсистемой системы (обозначается ), если выполняются следующие условия:

б) для любого функционального символа F (n) и любых элементов a1,a2,…,an A выполняется равенство FA(a1,a2,…,an)=FB(a1,a2,…,an), т.е. интерпретации символа F действуют одинаково на элементах из А;

в) для любого предикатного символа Р(n) справедливо равенство P = An, т.е. предикат содержит в точности те кортежи предиката, которые состоят из элементов множества А.

то существует единственная подсистема (Х)= алгебраической системы такая, что X В(Х) и (Х) для любой подсистемы алгебраической системы, для которой X А.

Подсистема (Х) из теоремы 1 называется подсистемой алгебраической системы, порожденной множеством X.

Для описания элементов подсистемы (Х) определим индукцией по построению понятие терма сигнатуры :

1) переменные и константные символы из суть термы;

2) если F – n-местный функциональный символ, t1,t2,…,tn – термы, то F(t1,t2,…,tn) – терм;

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

Множество всех термов сигнатуры обозначается через Т().

Под сложностью терма будем понимать число символов, входящих в терм.

1) Термами сигнатуры ={+,,,0} будут, например, 0, x, x+y, z(x+z)+0y, а 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) если t F(t1,…, tn), где F (n), t1(x1,…,xk),…,tn(x1,…,xk) Т() и значения термов t1,…, tn на элементах a1,…,ak равны b1,…,bn то значение терма t есть F(b1,…,bn).

B(Х)={t(a1,…,an) | t T(), a1,…,an X}.

порожденную множеством Х:

Решение. 1) Так как Т()={x1, x1x2, (x1x2)x3, x1(x2x3),…}, то теореме имеем A(X)={1/2, 1/21/2, 1/21/21/2,…}={1/2, 1/8, 1/16,…}={1/2n| n1}.

2) Из предыдущего примера следует, что {1/2n| n1} A(X). Так как операция деления является сигнатурной, то 1/2n 1/2m=2m-n A(X) для любых m, n1. Тогда C={2n| n Z} A(X). Так как множество С замкнуто относительно операций умножения и деления. т.е. является подсистемой алгебраической системы и содержит множество X, то A(Х) С. Следовательно, A(Х)=С.

3) Так как 2=22-8 (-36)-14 22 и любое число, получаемое из чисел 22, -36 с помощью операции вычитания четное, то A(X)= Большинство определений этого параграфа будут индуктивными.

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

1) если t1, t2, T(), то t1=t2 – атомарная формула;

2) если P(n) – предикатный символ, t1,t2,…,tn T(), то Р(t1,t2,…,tn) – атомарная формула;

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

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

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

2) если, – формулы сигнатуры, то ¬, (), (), (), x, x – формулы сигнатуры ;

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

Символы,, использованные в определении, называются соответственно квантором всеобщности и квантором существования и читаются «для любого» и «существует». Все соглашения относительно расстановок скобок, принятые в алгебре высказываний, остаются в силе и для формул логики предикатов. Кроме того, вместо записей x1… xn и x1… xn будем часто использовать записи x1,…,xn и x1,…,xn.

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

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

2) если имеет вид ¬1, или x1, или x1, то подформула формулы – это либо, либо подформула формулы 1;

3) если имеет вид 12, или 12, или 12, то подформула формулы – это либо, либо подформула формулы 1, либо подформула формулы 2;

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

Пример 4. Пусть ={F(2),P(1)}, = 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; в противном случае это вхождение называется свободным в. Переменная х называется свободной (связанной), если некоторое вхождение х в свободно (связано).

Пример 5. Пусть S={P1(1),P2(2)}. Рассмотрим формулы:

2) Р2(x,y) xP1(x);

3) 3) x(P2(x,y)P1(x)).

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

Пример 6. Выписать все подформулы формулы, определить все свободные и связанные переменные этой формулы:

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

2) y(xy+z), 8) (z 2=u) u(u=x+z), Поскольку существуют связанные и свободные вхождения переменных х, u и z в формулу, то х, u и z являются связанными и свободными переменными. Переменная y связанная.

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

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

2.3.3. Истинность формулы логики предикатов Дадим индуктивное определение истинности формулы (x1,…,xn) сигнатуры на элементах a1,…,an А в алгебраической системе 1) t1(a1,…,an)=t2(a1,…,an), где t1,t2 T(), значения термов t1,t2 в алгебраической системе на элементах a1,…,an А совпадают;

2) P(t1(a1,…,an),….,tk(a1,…,an)), где P(k), t1,…,tk T(), (t1(a1,…,an),…, tk(a1,…,an)) P;

3) (a1,…,an)(a1,…,an) (a1,…,an) и (a1,…,an);

4) (a1,…,an)(a1,…,an) (a1,…,an) или (a1,…,an);

(a1,…,an);

6) ¬(a1,…,an) неверно, что (a1,…,an);

8) x(x,a1,…,an) (a,a1,…,an) для некоторого а А.

Если не выполняется (a1,…,an), то будем говорить, что формула (x1,…,xn) сигнатуры ложна в системе на элементах a1,…,an А.

a тогда и только тогда, когда a четно.

Пример 8. Записать формулу (x,y,z), истинную в на кортеже a тогда и только тогда, когда c – наименьшее общее кратное чисел a и b.

где формула «говорит» о том, что z делится на x и на y, а формула «говорит» о том, что z делит все общие кратные х и у, т. е. является наименьшим из всех общих кратных:

Таким образом, (х,у,z) uv(z=x uz=х y) w( uv(w=x uw=х y) w1(w=w1 z)).

2.3.4. Логическое следствие в логике предикатов Пусть 1( ),…,n( ), ( ) – формулы сигнатуры. Формула называется логическим следствием формул 1,…,n (обозначается 1,…,n), если для любой алгебраической системы сигнатуры Пример 9. Доказать, что где 1( ),2( ),3( ) – формулы сигнатуры.

Решение. Пусть = – произвольная алгебраическая система сигнатуры. Необходимо показать, что (1( )2( )) (2( )3( )).

Покажем, что Предположим, что 1( ). Так как (1( )2( ), то 2( ).

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

Формула (x1,…,xn) сигнатуры называется тождественно истинной, если для любой алгебраической системы сигнатуры x1 хn (x1,…,xn). Формула (x1,…,xn) сигнатуры называется тождественно ложной, если формула ¬(x1,…,xn) тождественно истина. Множество формул 1,…,n сигнатуры называется противоречивым или несовместным, если формула 1…n тождественно ложна.

Теорема 3. Пусть 1,..,m, – формулы сигнатуры Следующие условия эквивалентны:

8) {1,..,m,¬} – противоречивое множество формул;

10) 1..m¬ – тождественно ложная формула.

2.3.5. Эквивалентные формулы логики предикатов Формулы и сигнатуры называются эквивалентными (обозначается ), если или.

Утверждение 1. В логике предикатов выполнимы все эквивалентности ИВ из теоремы 3.

Утверждение 2. Пусть, – формулы сигнатуры переменная x не является свободной переменной формулы, переменная у не является свободной переменной формулы. Тогда здесь запись () x обозначает результат подстановки y вместо всех своy бодных вхождений в переменной x.

2.3.6. Пренексная нормальная форма в логике предикатов Формула сигнатуры называется бескванторной, если она не содержит кванторов. Бескванторная формула является дизъюнктивной (конъюнктивной) нормальной формой, если она получается из некоторой формулы АВ, находящейся в ДНФ (КНФ), заменой всех пропозициональных переменных x1,…,xn на некоторые атомарные формулы 1,…,n сигнатуры соответственно.

Говорят, что формула сигнатуры находится в пренексной нормальной форме (ПНФ), если она имеет вид Q1x1…Qnxn, где Qi, – кванторы (1in), n – дизъюнктивная нормальная форма.

Теорема 1. Для любой формулы сигнатуры существует ПНФ, эквивалентная формуле.

Опишем алгоритм приведения формулы к ПНФ:

1) выражаем импликацию, участвующую в построении формулы, через дизъюнкцию и отрицание, используя эквивалентность 2) используя законы де Моргана 3) и эквивалентности переносим все отрицания к атомарным подформулам и сокращаем двойные отрицания по правилу ¬¬;

4) приводим формулу к виду Q1x1…Qnxn, где Qi, – кванторы (1in), – бескванторная формула, пользуясь эквивалентностями 5) используя закон дистрибутивности преобразуем формулу к дизъюнктивной нормальной форме.

Пример 10. Формулу x y(x,y) x y(x,y) привести к ПНФ, считая формулы и атомарными.

Решение. Избавившись от импликации, получаем Переносим отрицание к атомарной подформуле (x,y):

Так как в формуле x y(x,y) переменные х, у являются связанными, то по пп. 2, 3 утверждения 2 имеем Пусть u, v – некоторые новые переменные. Тогда по пп. 4, 4 утверждения 2 получаем откуда по по пп. 2, 3 утверждения Формула ¬(x,y)(u,v) является дизъюнктивной нормальной формой, а значит, формула x y u v(¬(x,y)(u,v)) является ПНФ.

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

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

Примем следующие соглашения. Пусть x1,…,xn – переменные, t1,…,tn – обозначать результат подстановки термов t1,…,tn вместо всех свободных вхождений в переменных x1,…,xn соответственно, причем, если в тексте встречается запись, то предполагается, что для всех i {1,...,n} ни одно свободное вхождение в переменной xi не входит в подформулу вида y или y, где у – переменная, входящая в ti.

Аксиомами ИП являются следующие формулы для любых формул,, ИП, любых переменных x,y,z и любого терма t:

2) ()((())());

5) ()(()(()));

8) ()((x)(()));

9) ()((¬)¬);

14) x=y(()xz()yz).

Указанные формулы называются схемами аксиом ИП. При подстановке конкретных формул в какую-либо схему получается частный случай схемы аксиом.

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

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

Говорят, что формула выводима в ИП из формул 1,…,m (обозначается 1,…,m), если существует последовательность формул 1,…,k,, в которой любая формула либо является аксиомой, либо принадлежит множеству формул {1,…,m}, называемых гипотезами, либо получается из некоторых 1,…, i-1 по одному из правил вывода 1–3?

Причем при применении правил 2 и 3 переменная x не должна входить ни в одну гипотезу свободно. Выводимость формулы из () равносильна тому, что – теорема ИП или доказуемая формула ИП.

Так же, как в исчислении высказываний, определяется понятие квазивывода.

Формула ИП называется тавтологией в ИП, если она получается из формулы исчисления высказываний, доказуемой в исчислении высказываний, путем замены всех ее пропозициональных переменных x1,…,xn на формулы 1,…,n ИП соответственно. Формулу при этом называют основой тавтологии.

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

Формулы и ИП называются пропозиционально эквивалентными, если и – тавтологии. Формулы и ИП называются эквивалентными (обозначаем ), если и.

Следствие 1. Если и – пропозиционально эквивалентные формулы ИП, то и – эквивалентные формулы ИП.

Теорема 1 (о дедукции). Пусть 1,…,m,, – формулы ИП. Тогда 1,…,m, 1,…,m,.

Следствие 2. Пусть и – формулы ИП. Следующие условия эквивалентны:

2.4.2. Эквивалентные формулы исчисления предикатов Утверждение 2. В ИП выполнимы все эквивалентности ИВ из теоремы 3.

Утверждение 3. Пусть, – формулы ИП переменная x не является свободной переменной формулы, переменная у не является свободной переменной формулы. Тогда Доказательство. Докажем эквивалентность 1). Построим квазивывод формулы ¬ x x¬ из :

1) x (схема аксиом 12);

2) ¬ x¬ (к п.1 применили свойство контрапозиции);

3) ¬ x x¬ (к п.2 применили правило вывода 2).

Построим квазивывод формулы x¬¬ x из :

2) ¬¬¬ x¬ (к п.1 применили свойство контрапозиции);

3) ¬¬ (тавтология);

4) ¬ x¬ (к пп.3 и 2 применили свойство транзитивности);

5) x¬ x¬ (к п. 4 применили правило вывода 3);

6) ¬¬ x¬¬ x (к п.5 применили свойство контрапозиции);

x¬¬ x (к пп.7 и 6 применили свойство транзитивности).

Докажем эквивалентность 3). Построим квазивывод формулы 2) (схема аксиом 3);

x() (к пп.1 и 2 применили свойство транзитивности);

x() x (к п.3 применили правило вывода 2);

5) (схема аксиом 4);

x() (к пп.1 и 5 применили свойство транзитивности);

7) ( x() x)(( x())( x() x)) (схема аксиом 5);

8) ( x())( x() x) (к пп. 4 и 7 применили правило вывода 1);

x() x (к пп. 6 и 8 применили правило вывода 1).

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

1. x x (схема аксиом 3);

2. x (схема аксиом 11);

3. x (к пп. 1 и 2 применили свойство транзитивности);

4. x (схема аксиом 4);

5. ( x)(( x)( x)) (схема аксиом 5);

6. ( x)( x) (к пп. 3 и 5 применили правило вывода 1);

7. x (к пп. 4 и 5 применили правило вывода 1);

8. x x() (к п. 6 применили правило вывода 2).

Теорема 2 (о замене). Пусть – формула ИП, – ее подформула, ' получается из заменой некоторого вхождения на формулу ' ИП и '. Тогда '.

Теорема 3. Для любой формулы ИП существует ПНФ, эквивалентная в ИП формуле.

2.4.3. Теорема Геделя о полноте. Непротиворечивость Теорема 4. Все доказуемые в ИП формулы являются тождественно истинными.

Доказательство проводим индукцией по длине вывода формулы.

Очевидно, что аксиомы ИП являются тождественно истинными. Проверку того, что правила вывода 1-3 сохраняют тождественную истинность, мы оставляем читателю в качестве упражнения.

Следствие 3. ИП непротиворечиво, т.е. не все формулы ИП доказуемы в ИП.

В ИП справедлив аналог теоремы о полноте в исчислении высказываний.

Теорема 5 (Геделя о полноте). Формула исчисления ИП доказуема тогда и только тогда, когда тождественно истинна.

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

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

конечная лента, разбитая на конечное число ячеек. В каждый момент времени t в ячейках записаны буквы из некоторого алфавита A = {a0, a1,, qm } (где a0 = 0, a1 = 1, m 1 ), называемого внешним алфавитом машины. Ячейка, в которой записан символ 0, называется пустой. Если в какой–то момент времени лента имеет r ячеек, то состояние ленты полностью описывается словом ai ai ai, где a i – состояние первой (слева) ячейки, a i – состояние второй ячейки и т.д.

Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и имеет некоторое состояние q j из конечного множества внутренних состояний Q = {q0, q1,, qn }, Q A =. Состояние q 0 называется заключительным и означает завершение работы машины. Состояние q называется начальным и означает начало работы машины.

Программа, т.е. совокупность выражений T (i, j ) (где i = 0,, m, j = 1,, n ), называемых командами, каждое из которых имеет один из следующих видов:

сдвиг головки, находящейся в состоянии q j напротив ячейки с буквой ai, на одну ячейку влево с заменой состояния q j на q k ;

сдвиг головки, находящейся в состоянии q j напротив ячейки с буквой ai, на одну ячейку вправо с заменой состояния q j на q k ;

замена буквы ai в текущей ячейке на букву al, а также замена состояния q j головки на состояние q k Замечание 1. 1) Команды не могут начинаться со слов ai q0.

Таким образом, машина Тьюринга – это пятерка A, Q,, q0, q1.

Машинным словом называется слово M = qi ai, где ai – состояние ленты, qi – состояние головки, находящейся напротив ячейки с состоянием ai, занимающей то же положение среди других ячеек, что и буква ai в слове qi ai.

Опишем преобразование M T M машинного слова M в машинное слово M за один шаг работы машины T :

Машинное слово M получается из машинного слова M с помощью машины Тьринга T ( M = T ( M )), если существует последовательность преобразований M i T M i 1, i = 0,, k 1, для которой M 0 = M, M k = M.

Пусть = {0,1,2, } – множество натуральных чисел с нулем, частичной функцией. Если X = n, то частичная функция f называется всюду определенной. Если X =, то частичная функция f называется нигде не определенной.

Для любого числа k через n обозначим слово, состоящее из k 1 числа единиц: 111. Для любой n -ки k1,, k n n слово k1 0k 2 0 k n называется записью этой n –ки.

вычислимой по Тьюрингу, если существует машина Тьюринга T = A, Q,, q0, q1 такая, что 2) машина T применима к записnи n-ки a a X;

Пример 1. Построим машину Тьюринга T, вычисляющую функцию f (n) = 2n. Пусть T = A, Q,, q0, q1, где A = {0,1, a}, Q = {q0, q1, q2, q3, q4 }, программа состоит из команд:

2.5.2. Примитивно рекурсивные функции Базисными функциями называются следующие функции: O (x) – (1 m n) – функция выбора.

Оператор суперпозиции (подстановки) S ставит в соответствие mместной частичной функции f и n-местным частичным функциям удовлетворяющую тождеству:

Оператор примитивной рекурсии R ставит в соответствие n+2местной частичной функции f и n-местной частичной функции g n+1-местную частичную функцию R( f, q), удовлетворяющую схеме примитивной рекурсии:

Частична функция f называется примитивно рекурсивной (ПРФ), если существует последовательность частичных функций f 0,, f n, в которой f n = f и всякая f i является либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозиции S или примитивной рекурсии R.

Пример 2. Функция сложения x y является ПРФ:

Пример 3. Функция умножения x y является ПРФ:

Оператор минимизации M ставит в соответствие n+1-местной частичной функции f n-местную частичную функцию M ( f ) так, что В этом случае введем обозначение: h( x1,, xn ) = yf ( x1,, xn, y).

Частичная функция f называется частично рекурсивной (ЧРФ), если существует последовательность частичных функций f 0,, f n, в которой f n = f и всякая f i является либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозиции S, примитивной рекурсии R или минимизации M.

Пример 4. Нигде не определенная функция ( x) является ЧРФ:

Пример 5. Функция является ЧРФ:

3. ЗАДАНИЯ ДЛЯ ДОМАШНИХ

И КОНТРОЛЬНЫХ РАБОТ

3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные Построить таблицы истинности для следующих формул алгебры высказываний и привести эти формулы к СДНФ и СКНФ.

6. ((xz)¬y)¬(yz);

7. ((x(z¬y)¬y)¬z);

9. (((xy)¬z)¬y)z;

11) ((xz)¬y)¬(yz);

12) (xy)¬z¬(y¬z);

13) x¬(yz)(zx);

16) x¬(zy)¬(¬yz);

17) ((xzy)¬z)¬z;

21) ((xy)¬z)(¬yz);

22) (¬xy)¬(zy)z;

23) ((¬(xy)¬z)¬y)z;

25) ((x¬z)¬y)z¬(xy).

3.2. Логическое следствие в алгебре высказываний Проверить истинность соотношений тремя способами (используя определение логического следствия и пп. 3,4 теоремы 2.

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

Построить подсистему алгебраической системы, порожденную множеством X (через P(B) обозначен булеан множества B, т.е. множество всех подмножеств множества B):

22. = P({a, b, c});, X = {{a, b},{b, c}};

23. = P({a, b, c});, X = {{a, b},{b, c}};

27. = P({a, b, c, d});,{a, d}, X = {{a, b, d},{b, c}};

28. = P({a, b, c, d});,\, {b}, X = {{a, c},{b, d}};

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

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

3.6. Истинность формулы логики предикатов Написать формулу Ф(х), истинную в алгебраической системе N;,, тогда и только тогда, когда 2. х=2n для некоторого натурального n;

4. х – нечетное число;

5. х – простое число.

Написать формулу Ф(х,y), истинную в алгебраической системе N;,, тогда и только тогда, когда 5. x y p, где p – простое число.

Написать формулу Ф(х,y,z), истинную в алгебраической системе N;,, тогда и только тогда, когда 1. x делится на y с остатком 2;

2. x+3y2z;

3. z – общий делитель y и z;

4. z = НОК (x,y);

5. z = НОД (x,y).

Написать формулу Ф(х,y,z), истинную в алгебраической системе Z;,, тогда и только тогда, когда 2. x=-1;

3. 2x-3y – четное число;

4. 3z=4x-5y;

5. z-2y делится на 3x.

Пусть M P(B) – булеан множества B, т.е. множество всех подмножеств множества B.Написать формулу Ф(х,y,z), истинную в алгебраической системе P(B);, тогда и только тогда, когда 1. x есть пересечение y и z ;

2. x есть объединение y и z ;

5. x есть дополнение y.

Пусть M P(B) – булеан множества B, т.е. множество всех подмножеств множества B.Написать формулу Ф(х,y,z), истинную в алгебраической системе P(B);, тогда и только тогда, когда 3. x есть одноэлементное множество;

3.7. Логическое следствие в логике предикатов x1,, xn. Доказать следующие соотношения.

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

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

Пусть,, – атомарные формулы логики предикатов. Привести следующие формулы логики предикатов к пренексной нормальной форме.

функцию.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

Доказать, что следующие функции примитивно рекурсивны.

1. x+1;

2. x+y;

7. |x-y|;

8. max(x,y);

9. min(x,y);

10.

11.

12.

– частное от деления x на y (здесь 14. rest(x,y) – остаток от деления x на y (здесь rest(x,0)=x);

15. (x) – число делителей числа x, где (0)=0;

16. (x) – сумма делителей числа x, где (0)=0;

17. lh(x) – число простых делителей числа x, где lh(0)=0;

18. (x) – число простых чисел, не превосходящих x;

19. k(x,y) – наименьшее общее кратное чисе x и y, где k(x,0)=k(0,y)=0;

20. d(x,y) – наибольший общий делитель чисе x и y, где d(0,0)=0.

Доказать, что следующие функции частично рекурсивны.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

Ершов, Ю.Л. Математическая логика / Ю.Л. Ершов, Е.А. Палютин. – М.: Наука, 1987.

Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. – М.: Наука, 1981.

Новиков, П.С. Элементы математической логики / П.С. Максимов. – М.: Наука, 1973.

Степанова, А.А. Математическая логика и теория алгоритмов: учеб.

пособие / А.А. Степанова. – Находка: Институт технологии и бизнеса, 2003. – 56 с.

Судоплатов, С.В. Математическая логика и теория алгоритмов / С.В. Судоплатов, Е.В. Овчинникова. – М.: ИНФРА-М; Новосибирск:

Изд-во НГТУ, 2004.

Лихтарников, Л.М. Математическая логика / Л.М. Лихтарников, Т.Г. Сукачева. – СПб.: «Лань», 1998.

Мендельсон, Э. Введение в математическую логику / Э. Мендельсон. – М.: Наука, 1976.

Черч, А. Введение в математическую логику / А. Черч. – М.: Наука.

1960.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ПЕРЕЧЕНЬ ТЕМ

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

2.1. Алгебра высказываний

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

2.3. Логика предикатов

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

2.5. Элементы теории алгоритмов

3. ЗАДАНИЯ ДЛЯ ДОМАШНИХ И КОНТРОЛЬНЫХ РАБОТ............ 3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы

3.2. Логическое следствие в алгебре высказываний

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

3.4. Алгебраические системы

3.5. Формулы логики предикатов

3.6. Истинность формулы логики предикатов в алгебраической системе.... 3.7. Логическое следствие в логике предикатов

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

3.9. Пренексная нормальная форма

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

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

Лицензия на издательскую деятельность ИД № 03816 от 22.01. Бумага писчая. Печать офсетная. Усл. печ. л..

_ Издательство Владивостокский государственный университет Отпечатано: множительный участок ВГУЭС

 


Похожие работы:

«И.Ф. Астахова А.П. Толстобров В.М. Мельников В ПРИМЕРАХ И ЗАДАЧАХ УДК 004.655.3(075.8) ББК 32.973.26-018.1я73 Оглавление А91 Рецензенты: Введение 8 доцент кафедры АСИТ Московского государственного университета Н.Д. Васюкова; Воронежское научно-производственное предприятие РЕЛЭКС; 1. Основные понятия и определения 10 кафедра информатики и МПМ Воронежского 1.1. Основные понятия реляционных баз данных государственного педагогического университета; 1.2. Отличие SQL от процедурных языков...»

«Новые поступления. Январь 2012 - Общая методология. Научные и технические методы исследований Савельева, И.М. 1 001.8 С-128 Классическое наследие [Текст] / И. М. Савельева, А. В. Полетаев. - М. : ГУ ВШЭ, 2010. - 336 с. - (Социальная теория). экз. - ISBN 978-5-7598-0724-7 : 101-35. 1чз В монографии представлен науковедческий, социологический, библиометрический и семиотический анализ статуса классики в общественных науках XX века - экономике, социологии, психологии и истории. Синтез этих подходов...»

«Министерство образования и науки РФ Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Тобольский государственный педагогический институт им. Д. И. Менделеева Кафедра зоологии, экологии и природопользования Утверждена на заседании кафедры протокол № 1 от 30.09 2008 года УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ БИОЛОГИЯ С ОСНОВАМИ ЭКОЛОГИИ Специальность 050201.65- Математика Профиль Алгебра и геометрия Программу составила: к....»

«Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики Евразийский открытый институт С.А. Орехов В.А. Селезнев Теория корпоративного управления Учебно-методический комплекс (издание 4-е, переработанное и дополненное) Москва 2008 1 УДК 65 ББК 65.290-2 О 654 Орехов С.А., Селезнев В.А. ТЕОРИЯ КОРПОРАТИВНОГО УПРАВЛЕНИЯ: Учебно-методический комплекс. – М.: Изд. центр ЕАОИ, 2008. – 216 с. ISBN 978-5-374-00139-6 © Орехов С.А., 2008 ©...»

«Серия ЕстЕствЕнныЕ науки № 2 (4) Издается с 2008 года Выходит 2 раза в год Москва 2009 Scientific Journal natural ScienceS № 2 (4) Published since 2008 Appears Twice a Year Moscow 2009 редакционный совет: Рябов В.В. доктор исторических наук, профессор, Председатель ректор МГПУ Атанасян С.Л. кандидат физико-математических наук, профессор, проректор по учебной работе МГПУ Геворкян Е.Н. доктор экономических наук, профессор, проректор по научной работе МГПУ Русецкая М.Н. кандидат педагогических...»

«МЕЖДУНАРОДНЫЙ МОЗМ D 1 ДОКУМЕНТ 2012 г. (изд. англ.) ОСНОВНЫЕ ПОЛОЖЕНИЯ ДЛЯ ЗАКОНА ПО МЕТРОЛОГИИ Considerations for a Law on Metrology Международная Организация Законодательной Метрологии (МОЗМ) 1 Содержание Предисловие Часть 1 – Введение Часть 2 – Обоснование Часть 3 – Руководящие указания по созданию структур в метрологии и предлагаемые статьи для Закона Часть 4 – Предложения по нормативным документам Часть 5 – Предложения по структуре Закона по метрологии Часть 6 – Библиография Предисловие...»

«Направление подготовки: 010300.68 Фундаментальная информатика и информационные технологии (очная, очно-заочная) Объектами профессиональной деятельности магистра фундаментальной информатики и информационных технологий являются научно-исследовательские и опытноконструкторские проекты, математические, информационные, имитационные модели систем и процессов; программное и информационное обеспечение компьютерных средств, информационных систем; языки программирования, языки описания информационных...»

«Некоммерческая организация Ассоциация московских вузов ГОУ ВПО Московский автомобильно-дорожный государственный технический университет (МАДИ) Полное название вуза Научно-информационный материал Научные итоги Информационно-образовательного форума для учащихся и специалистов г. Москвы, посвященного совершенствованию автотранспортной и дорожной отрасли. Полное название НИМ Состав научно-образовательного коллектива: Поспелов П.И. - первый проректор, д.т.н., профессор, Татаринов В.В. - нач....»

«РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ГЕОФИЗИКИ ИЗ ИСТОРИИ КИБЕРНЕТИКИ Ответственный редактор академик А.С. Алексеев Редактор-составитель д.т.н. Я.И. Фет НОВОСИБИРСК 2006 УДК 681.3 ББК 22.18 И32 Из истории кибернетики / Редактор-составитель Я.И. Фет. – Новосибирск: Академическое издательство Гео, 2006.– 339 с. – ISBN 5-9747-0038-4 Герои и авторы публикуемых очерков – выдающиеся ученые разных стран, пионеры кибернетики. Они делятся...»

«Научное обоснование развития сети особо охраняемых природных территорий в Республике Карелия Карельский научный центр Российской академии наук Научное обоснование развития сети особо охраняемых природных территорий в Республике Карелия Петрозаводск 2009 УДК 502.172 (470.22) ББК 20.18 (2Рос. Кар.) Н 34 Научное обоснование развития сети особо охраняемых природных территорий в Республике Карелия. Петрозаводск: Карельский научный центр РАН, 2009. 112 с.: ил. 14, табл. 6. Библиограф. 96 назв. ISBN...»

«Министерство образования Республики Башкортостан ГАОУ СПО Стерлитамакский колледж строительства, экономики и права Учебно-методический комплекс по дисциплине ЕН 03. ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА основной профессиональной образовательной программы (ОПОП) по специальности СПО 230115 Программирование в компьютерных системах базовой подготовки Разработала : ДОЛГИХ Е.А. 2013 Одобрено на заседании предметно- УТВЕРЖДАЮ цикловой комиссии специальности 230115 Программирование в Зав....»

«Администрация города Соликамска Соликамское краеведческое общество Cоликамский ежегодник 2010 Соликамск, 2011 ББК 63.3 Б 73 Сергей Девятков, глава города Соликамск Рад Вас приветствовать, уважаемые читатели ежегодника! Соликамский ежегодник — 2010. — Соликамск, 2011. — 176 стр. 2010 год для Соликамска был насыщенным и интересным. Празднуя свое 580-летие, город закрепил исторический бренд Соляной столицы России, изменился внешне и подрос в Информационно-краеведческий справочник по городу...»

«УСТАНОВОЧНАЯ СЕССИЯ I КУРСА ЗАОЧНОГО ОТДЕЛЕНИЯ Институт информационных коммуникаций и библиотек ДИСЦИПЛИНА, МАТЕРИАЛЫ К СЕССИИ СПЕЦИАЛИЗАЦИЯ Вопросы Отечественная История как наука. Отечественные научно-исторические школы и их представители. 1. история Исторические источники и их виды. • библиотечноФормационный и цивилизационный подходы к периодизации истории. Западная и 2. информационная восточная цивилизации. деятельность (зачет) Восточные славяне в древности, этапы образования государства....»

«ДОКЛАДЫ БГУИР № 2 (14) АПРЕЛЬ–ИЮНЬ 2006 ЭКОНОМИКА И УПРАВЛЕНИЕ УДК 608. (075) ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ НЕМАТЕРИАЛЬНЫХ АКТИВОВ Т.Е. НАГАНОВА Белорусский государственный университет информатики и радиоэлектроники П. Бровки, 6, Минск, 220013, Беларусь Поступила в редакцию 28 ноября 2005 Рассматриваются теоретические составляющие интеллектуальной собственности с целью формулировки подходов к совершенствованию патентно-лицензионной работы в Республике Беларусь. Ключевые слова: интеллектуальная...»

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА ХИМИЧЕСКИЙ ФАКУЛЬТЕТ КАФЕДРА ОРГАНИЧЕСКОЙ ХИМИИ И.Э.НИФАНТЬЕВ, П.В.ИВЧЕНКО ПРАКТИКУМ ПО ОРГАНИЧЕСКОЙ ХИМИИ Методическая разработка для студентов факультета биоинженерии и биоинформатики Москва 2006 г. Введение Настоящее пособи предназначено для изучающих органическую химию студентов второго курса факультета биоинженерии и биоинформатики МГУ им. М.В.Ломоносова. Оно состоит из двух частей. Первая часть знакомит студентов с основными...»

«министерство образования российской федерации государственное образовательное учреждение московский государственный индустриальный университет информационно-вычислительный центр Информационные технологии и программирование Межвузовский сборник статей Выпуск 3 (8) Москва 2003 ББК 22.18 УДК 681.3 И74 Информационные технологии и программирование: Межвузов ский сборник статей. Вып. 3 (8) М.: МГИУ, 2003. 52 с. Редакционная коллегия: д.ф.-м.н. профессор В.А. Васенин, д.ф.-м.н. профессор А.А. Пярнпуу,...»

«НГМА № 9 (136) октябрь 2009 г. РЕктоР НижГМА – Во ГЛАВЕ Наши юбиляры ЗАкоНотВоРЧЕСкоГо СоВЕтА В октябре отмечают юбилейный день рождения: При законодательном собрании нижегородской области С.Г. Габинет – заведующий учебной ла­ создан научно­координационный совет для рецензирова­ бораторией кафедры медицинской ния проектов законов нижегородской области. Совет яв­ физики и информатики (03.10). ляется консультативным органом, цель его работы – улуч­ Е.Н. Звонилова – уборщик служебных шать качество...»

«А. Н. Горский БИОЭНЕРГОИНФОРМАТИКА Второе издание (Эзотерика, начальный курс) Санкт-Петербург 2012 УДК 615.8 ББК 53.59 Г67 Горский А.Н. Биоэнергоинформатика (Эзотерика, начальный курс)/ А.Н.Горский. – СПб.: Петербургский гос.ун-т путей сообщения, 2012. – 327с. ISBN 978-5-7641-0196-5 Книга содержит начальные знания по эзотерике. Рассмотрена энергоинформационная структура человека, дается описание тонких тел человека, такие вопросы как душа и Дух, аура, чакры, карма. С позиции эзотерики...»

«Институт водных и экологических проблем СО РАН Институт вычислительных технологий СО РАН Геоинформационные технологии и математические модели для мониторинга и управления экологическими и социально-экономическими системами Барнаул 2011 УДК 004.5+528.9 ББК 32.97+26.1 Г35 Утверждено к печати Ученым советом Института водных и экологических проблем СО РАН Руководители авторского коллектива: Ю.И. Шокин, Ю.И. Винокуров Ответственный редактор: И.Н. Ротанова Рецензенты: Белов В.В., Бычков И.В., Гордов...»

«Заведующий кафедрой Информатики и компьютерных технологий Украинской инженерно-педагогической академии, доктор технических наук, профессор АШЕРОВ АКИВА ТОВИЕВИЧ Министерство образования и науки Украины Украинская инженерно-педагогическая академия АКИВА ТОВИЕВИЧ АШЕРОВ К 70-летию со дня рождения БИОБИБЛИОГРАФИЧЕСКИЙ УКАЗАТЕЛЬ Харьков УИПА, 2008 ББК 74.580.42я1 А 98 Составители: Ерёмина Е. И., Онуфриева Е. Н., Рыбальченко Е. Н., Сажко Г. И. Ответственный редактор Н. Н. Николаенко Акива Товиевич...»




 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.