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


ВВЕДЕНИЕ
Логика – это наука о законах правильного мышления. Это одна из древнейших наук. Основные ее законы были сформулированы еще древнегреческим мыслителем Аристотелем. Идеи о построении логики на математической основе, т.е. по сути математической логики, были высказаны Лейбницем в начале 18-го века.
Современная математическая логика определяется как раздел математики, посвященный изучению математических доказательств и вопросов основания математики. Одна из главных причин широкого распространения математической логики – применение аксиоматического метода в построении различных математических теорий. Важным достижением математической логики является формулировка понятия алгоритмической вычислимости, которое по своей важности приближается к понятию натурального числа. Сегодня результаты математической логики находят свое применение в других отраслях математического знания, а также в программировании, проблемах искусственного интеллекта и других науках.
Данное учебно-практическое пособие соответствует учебной программе курса «Математическая логика и теория алгоритмов» для специальностей «Информационные системы и технологии», «Вычислительные машины, комплексы и сети».
Практикум разделен на три части. В первой содержится программа курса, во второй – краткое изложение теории и решение типовых задач, в третьей – задания для контрольных работ.
Достоинство практикума состоит в том, что при наличии такого количества задач он может быть использован как задачник, как раздаточный материал для выполнения контрольных работ, а также содержит не менее 30 различных вариантов индивидуального домашнего задания.
Студенты заочной формы обучения выполняют первые 10 вариантов контрольных заданий, например, 1-10, 39-49, выбирая задачи соответственно своему шифру.
ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ
Тема 1. «Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы». Формулы АВ. Эквивалентность формул АВ. Понятия ДНФ, КНФ, СДНФ, СКНФ.
Тема 2. «Логическое следствие в алгебре высказываний». Понятия логического следствия, противоречивого множества высказываний, тождественно истинного высказывания. Связь между этими понятиями.
Тема 3. «Исчисление высказываний (ИВ). Доказуемые формулы ИВ». Понятие исчисления. Язык ИВ. Определение формулы ИВ. Аксиомы и правила вывода ИВ. Доказуемые и выводимые формулы ИВ. Примеры доказуемых и выводимых формул ИВ. Теорема о дедукции в ИВ. Эквивалентные формулы ИВ.
Тема 4. «Логика предикатов (ЛП). Алгебраические системы. Подсистемы». Понятия сигнатуры, алгебраической системы данной сигнатуры, подсистемы, подсистемы, порожденной множеством. Примеры. Понятия терма данной сигнатуры, значение терма на кортеже в алгебраической системе. Теорема о подсистеме, порожденной множеством.
Тема 5. «Формулы ЛП». Понятие формулы данной сигнатуры. Определение истинности формулы ЛП на кортеже элементов в алгебраической системе. Примеры.
Тема 6. «Истинность формулы ЛП в алгебраической системе».
Тема 7. «Логическое следствие в ЛП. Эквивалентные формулы ЛП». Понятия логического следствия, противоречивого множества формул ЛП, тождественно истинной формулы ЛП. Связь между этими понятиями. Определение эквивалентных формул ЛП. Основные эквивалентности в ЛП.
Тема 8. «Исчисление предикатов (ИП). Доказуемые формулы ИП». Язык ИП. Определение формулы ИП. Аксиомы и правила вывода ИП. Доказуемые и выводимые формулы ИП. Примеры доказуемых и выводимых формул ИП. Тавтологии. Связь между тавтологией и доказуемой формулой. Эквивалентные формулы ИП.
Тема 9. «Пренексная нормальная форма для формул ИП». Понятия ДНФ и ПНФ для формул ИП. Теорема о существовании для любой формулы ИП эквивалентной ей ПНФ.
Тема 10. «Машины Тьюринга». Определение машины Тьюринга. Понятие функций, вычислимых по Тьюрингу. Примеры таких функций.
Тема 11. «Примитивно рекурсивные функции». Понятия базисных функций, операторов суперпозиции, примитивной рекурсии, примитивно рекурсивных функций. Примеры.
Тема 12. «Частично рекурсивные функции». Понятия оператора минимизации, частично рекурсивных функций. Примеры. Эквивалентность классов функций, вычислимых по Тьюрингу, с классом частично рекурсивных функций.
2. ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ
2.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
2.1.1. Формулы алгебры высказываний
Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно.
В качестве примеров высказываний приведем предложения "Владивосток — кр упнейший город Приморья" и "Снег зеленый". Первое высказывание является истинным, а второе — ложным.
Поставим в соответствие высказыванию Р логическую переменную х, которая принимает значение 1, если Р истинно, и 0, если Р ложно.
Если имеется несколько высказываний, то из них можно образовать различные новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные — сложными. Соответственно из логических переменных можно составлять различные конструкции, которые образуют формулы алгебры высказываний.
Итак, пусть {хi│iI} — некоторое множество логических переменных. Определим по индукции понятие формулы алгебры высказываний (АВ):
любая логическая переменная является формулой АВ(называемой атомарной);
если φ и ψ — формулы АВ, то выражения ¬φ, (φ∧ψ),(φ∨ψ), (φ→ψ) являются формулами АВ;
никаких других формул АВ, кроме построенных по пп. 1 и 2, нет.
Если формула φ АВ построена из логических переменных, принадлежащих множеству {х1,х2,…,xn}, то будем писать φ(x1,…xn).
Символы ¬, ∧, ∨ →, использованные в определении, называются логическими операциями или связками и читаются соответственно: отрицание, конъюнкция, дизъюнкция и импликация.
Введенные в п. 2 формулы следующим образом интерпретируются в русском языке: ¬φ — "не φ", (φ∧ψ) — φ и ψ, (φ ψ) — φ или ψ, ( φ → ψ) —если φ, то ψ.
Вместо ¬φ часто пишут φ, вместо ( φ∧ ψ) — (φ& ψ), (φ • ψ) или (φψ).
Действия логических операций задаются таблицами истинности, каждой строке которых взаимно однозначно сопоставляется набор значений переменных, входящих в формулу, и соответствующее этому набору значение полученной формулы:
φ ¬φ
0
1 1
0
φ ψ (φ ∧ ψ) (φ ∨ ψ) (φ → ψ)
0
0
1
1 0
1
0
1 0
0
0
1 0
1
1
1 1
1
0
1
Пример 1. Построить таблицу истинности для формулы φ((x→y)∧((¬y→z)→¬x)).
Решение. Будем строить таблицу истинности последовательно в соответствии с шагами построения формулы φ:
x y z (x→y) (¬y→z) ((¬y→z)→¬x) φ
0 0 0 1 0 1 1
0 0 1 1 1 1 1
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 0 1 0
1 0 1 0 1 0 0
1 1 0 1 1 0 0
1 1 1 1 1 0 0
Легко заметить, что таблица истинности для φ совпадает с таблицей истинности для ¬x. В дальнейшем выяснится причина этого совпадения.
Как видно из примера 1, даже при составлении несложных формул возникает обилие скобок. Чтобы избежать этого, в алгебре высказываний так же, как и в арифметике, приняты некоторые соглашения относительно расстановки скобок. Перечислим эти соглашения.
Внешние скобки не пишутся. Например, вместо высказывания ((x∨ y)→z) пишется (x∨ y)→z.
На множестве {¬, ∧, ∨, →} вводится транзитивное отношение "быть более сильным" следующим образом: наиболее сильная связка – ¬, далее идут ∧ и ∨, самая слабая связка – →.
Согласно этим отношениям недостающие скобки в формуле расставляются последовательно, начиная с наиболее сильных связок и кончая наиболее слабыми, а для связок одинаковой "силы" расстановка скобок выполняется слева направо.
Пример 2. В формуле ((x∨ y)→z)→u)) все скобки можно опустить: х∨ y→z→u.
2.1.2. Эквивалентность формул АВ
Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.
Формулы φ(x1,…,xn) и ψ(x1,…,xn) называются эквивалентными (φ ≡ ψ), если совпадают их таблицы истинности, т. е. ψ(е1,…,en) = φ(e1,…,en) для любых e1,…,en{0,1}
Пример 3. Построив таблицы истинности формул x→y и ¬y→¬x, убеждаемся, что (х→y) ≡ (¬y→¬x).
Легко видеть, что отношение ≡ является отношением эквивалентности, т. е. оно рефлексивно (φ≡φ), симметрично (если φ≡ψ, то ψ≡φ), транзитивно (если φ≡ψ и ψ≡χ, то φ≡ χ).
Отметим основные эквивалентности между формулами АВ:
φ∧ φ≡φ, φ∨ φ≡φ (законы идемпотентности);
φ∧ ψ≡ψ∧ φ, φ∨ ψ≡ψ∨ φ (законы коммутативности);
(φ∧ψ)∧χ≡φ∧(ψ∧χ), (φ∨ψ)∨χ≡φ∨(ψ∨χ) (законы ассоциативности);
φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ) (законы дистрибутивности)
¬(φ∧ψ)≡¬φ∨¬ψ, ¬(φ∨ψ)≡¬φ∧¬ψ (законы де Моргана);
¬¬φ≡φ (закон двойного отрицания);
φ→ψ≡¬φ∨ψ;
φ∧(φ∨ψ)≡φ, φ∨(φ∧ψ)≡φ (законы поглощения);
φ∨(¬φ∧ψ)≡φ∨ψ, ¬φ∨(φ∧ψ)≡¬φ∨ψ;
φ∧(¬φ∨ψ)≡φ∧ψ, ¬φ∧(φ∨ψ)≡¬φ∧ψ.
Формула φ(x1,x2,…,xn) называется выполнимой (опровержимой), если существует такой набор значений переменных, на котором формула принимает значение 1 (соответственно 0) .
Пример 4. Формула х∧ у является одновременно выполнимой и опровержимой, поскольку 0∧0=0, а 1∧1=1.
Формула φ(x1,…,xn) называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) на всех наборах значений переменных.
Пример 5. Формула x∨¬x является тождественно истинной, а формула x∧¬x — тождественно ложной:
x x∨¬x x∧¬x
0
1 1
1 0
0
Утверждение 1. Если формула φ1 тождественно истинна, φ0 — тождественно ложна, то для любых формул φ и ψ справедливы следующие эквивалентности:
φ∧ φ1≡φ; φ∨ φ0≡φ;
φ∨φ1≡φ1; φ∧φ0≡φ0;
(φ∧ψ→φ)≡φ1; (φ→φ∨ψ)≡φ1.
2.1.3. Дизъюнктивные и конъюнктивные нормальные формы АВ
Если х — логическая переменная, δ{0,1}, то выражение

называется литерой. Литеры х и ¬х называются контрарными.
Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.
Пример 6. Формулы x∨¬y∨¬z и x∨y∨x∨¬x — дизъюнкты.
формулы ¬x∧y∧z и x∧y∧¬x — конъюнкты, а ¬x является одновременно и дизъюнктом, и конъюнктом.
Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).
Пример 7. Формула (x∧¬y)∨(y∧z) — ДНФ, формула (х∨z∨¬y)∧(x∨z)∧y — КНФ, а формула x∧¬y является одновременно КНФ и ДНФ.
Теорема 1.
1) Любая формула эквивалентна некоторой ДНФ.
2) Любая формула эквивалентна некоторой КНФ.
Опишем алгоритм приведения формулы к ДНФ.
Выражаем импликацию, участвующую в построении формулы, через дизъюнкцию и отрицание, используя эквивалентность φ→ψ≡¬φ∨ψ.
Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания по правилу ¬¬x≡x.
3.Используя закон дистрибутивности φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.
В результате применения пп. 1-3 получается ДНФ, эквивалентная исходной формуле.
Пример 8. Привести к ДНФ формулу φ¬((x→y)∨¬(y→z)).
Решение. Выразим логическую операцию → через ∨ и ¬: φ≡¬((¬x∨y)∨¬(¬y∨z)). Воспользуемся законами де Моргана и двойного отрицания: φ≡¬(¬x∨y)∧¬¬(¬y∨z)≡(¬¬x∧¬y)∧(¬y∨z)≡(x∧¬y)∧(¬y∨z). Используя закон дистрибутивности, приводим формулу к ДНФ: φ≡(x∧¬y∧¬y)∨(x∧¬y∧z).
Приведение формулы к КНФ производится аналогично приведению ее к ДНФ, только вместо п. 3 применяется п. 3':
3'. Используя закон дистрибутивности φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ), преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.
Пример 9. Привести к КНФ формулу φ(x→y)∧((¬y→z)→¬x).
Решение. Преобразуем формулу φ к формуле, не содержащей →: φ≡(¬x∨y)∧(¬(¬¬y∨z)∨¬x). В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания: φ≡(¬x∨y)∧((¬¬¬y∧¬z)∨¬x)≡(¬x∨y)∧((¬y∧¬z)∨¬x). Используя закон дистрибутивности, приводим формулу к КНФ φ≡(¬x∨y)∧(¬x∨¬y)∧(¬x∨¬z). Упростим полученную формулу: (¬x∨y)∧(¬x∨¬y)∧(¬x∨¬z)≡(1)(¬x∨(y∧¬y))∧(¬x∨¬z)≡(2)¬x∧(¬x∨¬z)≡ ≡(3)¬x (для преобразования (1) использовался закон дистрибутивности, для (2) – эквивалентность 1 утверждения 1, для (3) — закон поглощения). Таким образом, формула φ эквивалентными преобразованиями приводится к формуле ¬x, являющейся одновременно ДНФ и КНФ.
2.1.4. Совершенные дизъюнктивные и конъюнктивные нормальные формы
Пусть (х1,..., хn) — набор логических переменных, Δ=(δ1,…,δn) — набор нулей и единиц. Конституентой единицы набора Δ называется конъюнкт К1(δ1,…,δn)=x1δ1∧x2δ2∧…∧xnδn. Конституентой нуля набора Δ называется дизъюнкт К0(δ1,…,δn)=x11-δ1∨x21-δ2∨…∨xn1-δn.
Отметим, что K1(δ1,δ2,…,δn)=1 (K0(δ1,δ2,…,δn)=0) тогда и только тогда, когда x1=δ1, x2=δ2,…, xn=δn.
Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых, а совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная хi из набора {х1,...,хп} входит ровно один раз, причем входит либо сама хi, либо ее отрицание ¬xi.
Пример 10. Формула x1∧¬x2∧x3 есть конституента единицы K1(1,0,1), формула x∨y∨¬z есть конституента нуля K0(0,0,1), формула (x1∧¬x2)∨(¬x1∧x2) – СДНФ, формула (x∨y∨¬z)∧(¬x∨¬y∨z)∧(¬x∨y∨z) – СКНФ, а формула (x1∧¬x2∧x3)∨(¬x1∧x2∧x3)∨(x1∧¬x2∧x3) не является СДНФ.
Опишем алгоритм приведения формулы к СДНФ.
Приводим данную формулу к ДНФ.
Преобразовываем ее конъюнкты в конституенты единицы с помощью следующих действий:
а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ;
б) если в конъюнкт одна и та же литера xδ входит несколько раз, то удаляем все литеры хδ, кроме одной;
в) если в некоторый конъюнкт x1δ1∧…∧xkδk не входит переменная у, то этот конъюнкт заменяем на эквивалентную формулу x1δ1∧…∧xkδk∧(y∨¬y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида у∨¬y;
г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.
Пример 11. Найти СДНФ для ДНФ φ(x∧¬x)∨x∨(y∧z∧y).
Решение. Имеем φ≡x∨(y∧z)≡(x∧(y∨¬y))∨(y∧z∧(x∨¬x))≡ ≡(x∧y)∨(x∧¬y)∨(x∧y∧z)∨(¬x∧y∧z)≡
≡(x∧y∧(z∨¬z))∨(x∧¬y∧(z∨¬z))∨(x∧y∧z)∨(¬x∧y∧z)≡
≡(x∧y∧z)∨(x∧y∧¬z)∨(x∧¬y∧z)∨(x∧¬y∧¬z)∨(x∧y∧z)∨(¬x∧y∧z)≡
≡(x∧y∧z)∨(x∧y∧¬z)∨(x∧¬y∧z)∨(x∧¬y∧¬z)∨(¬x∧y∧z).
Описание алгоритма приведения формулы к СКНФ аналогично вышеизложенному описанию алгоритма приведения формулы к СДНФ и оставляется читателю в качестве упражнения.
Логическое следствие в АВ
Говорят, что формула ψ(х1,...,хп) АВ является логическим следствием формул φ1(х1,...,хп),…,φm(х1,...,хп) АВ (обозначается ⊨ψ), если для любых из соотношений следует . Формулы называются гипотезами.
Пример 1. Доказать, что φ, φ→ψ, ψ→χ⊨χ. Построим таблицы истинности для каждой формулы:
φ ψ χ φ→ψ ψ→χ
0 0 0 1 1
0 0 1 1 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1
Из таблицы истинности видно, что когда все гипотезы принимают значение равное 1, формула χ тоже принимает значение 1, значит, χ является логическим следствием, что и требовалось доказать.
Теорема 1.
1. Количество гипотез можно увеличивать.
2. Гипотезы можно переставлять в любом порядке.
3. ⊨ψ тогда и только тогда, когда ⊨φm→ψ.4. ⊨ψ тогда и только тогда, когда формула →ψ тождественно истина.
5. ⊨ψ тогда и только тогда, когда формула φ1∧..∧φm∧¬ψ тождественно ложна.
Исчисление высказываний
Определение формального исчисленияВведем общее понятие формального исчисления. Будем говорить, что формальное исчисление I определено, если выполняются следующие четыре условия:
Имеется некоторое множество А символов – алфавит исчисления I. Конечные последовательности символов называются словами или выражениями исчисления I. Обозначим через S множество всех слов алфавита исчисления I.
Задано подмножество FS, называемое множеством формул исчисления I. Элементы множества F называются формулами.
Выделено множество АхF формул, называемых аксиомами исчисления I.
Имеется конечное множество K отношений R1,R2,…,Rn между формулами, называемых правилами вывода, причем если (φ1,…,φm,φ)Ri, то φ называется непосредственным следствием формул φ1,…,φm по правилу Ri.
Итак, исчисление I есть четверка (А,F,Ах,K).
Выводом в исчислении I называется последовательность формул φ1,φ2,…,φn такая, что для любого i (1≤i≤n) формула φi есть либо аксиома исчисления I, либо непосредственное следствие каких-либо предыдущих формул.
Формула φ называется теоремой исчисления I, выводимой в I, или доказуемой в I если существует вывод φ1,…,φn,φ, который называется выводом формулы φ или доказательством теоремы φ.
Вообще говоря, может не существовать алгоритма, с помощью которого для произвольной формулы φ через конечное число шагов можно определить, является ли φ выводимой в исчислении I или нет. Если такой алгоритм существует, то исчисление называется разрешимым. Исчисление называется непротиворечивым, если не все его формулы доказуемы.
Система аксиом и правил выводаИспользуя понятие формального исчисления, определим исчисление высказываний (ИВ).
Алфавит ИВ состоит из букв А,В,Q,R,Р и других, возможно с индексами (которые называются пропозициональными переменными), логических символов (связок) ¬, ∧, ∨, →, а также вспомогательных символов (, ).
Множество формул ИВ определяется индуктивно:
а)все пропозициональные переменные являются формулами ИВ;
б)если φ, ψ формулы ИВ, то ¬φ, (φ∧ψ), (φ∨ψ), (φ → ψ) – формулы ИВ;
в)выражение является формулой ИВ тогда и только тогда, когда это может быть установлено с помощью пунктов "а" и "б".
Таким образом, любая формула ИВ строится из пропозициональных переменных с помощью связок ¬, ∧, ∨, →.
В дальнейшем при записи формул будем опускать некоторые скобки, используя те же соглашения, что и в предыдущей главе.
Подформулой ψ формулы φ ИВ называется подслово φ, являющееся формулой ИВ.
Под длиной формулы будем понимать число символов, входящих в слово φ.
Аксиомами ИВ являются следующие формулы для любых формул φ, ψ, χ:
1) φ→(ψ→φ);
2) (φ→ψ)→((φ→(ψ→χ))→(φ→χ));
(φ∧ψ)→φ;
(φ∧ψ)→ψ;
(φ→ψ)→((φ→χ)→(φ→(ψ∧χ)));
φ→(φ∨ψ);
φ→(ψ∨φ);
(φ→χ)→((ψ→x)→((φ∨ψ)→χ));
(φ→ψ)→((φ→¬ψ)→¬φ);
¬¬φ→φ.
Указанные формулы называются схемами аксиом ИВ. При подстановке конкретных формул в какую-либо схему получается частный случай схемы аксиом.
Единственным правилом вывода в ИВ является правило заключения (modus ponens): если φ и φ→ψ выводимые формулы, то ψ также выводимая формула. Символически это записывается так:
φ, φ→ψ
ψ
Говорят, что формула φ выводима в ИВ из формул φ1,…,φm (обозначается φ1,…,φm├φ), если существует последовательность формул ψ1,…,ψk,φ, в которой любая формула либо является аксиомой, либо принадлежит списку формул φ1,…,φm, называемых гипотезами, либо получается из предыдущих по правилу вывода. Выводимость формулы φ из ∅ (├φ) равносильна тому, что φ теорема ИВ.
Пример 1. Покажем, что ├φ→φ.
Решение. Построим вывод данной формулы:
1) в схеме аксиом 2 ψ заменим на φ→φ,χ на φ. Получаем аксиому (φ→(φ→φ))→((φ→((φ→φ)→φ)→(φ→φ));
2) в схеме аксиом 1 ψ заменим на φ. Получаем φ→(φ→φ);
3) из 1 и 2 по правилу вывода заключаем (φ→((φ→φ)→φ))→(φ→φ);
4) в схеме аксиом 1 заменяем ψ на φ→φ. Получаем φ→((φ→φ)→φ);
5) из пп. 3 и 4 по правилу вывода справедливо ├φ→φ.
Пример 2. Покажем, что φ,ψ├φψ
Решение: Построим вывод формул φψ из φ и ψ
1) φ (гипотеза);
2) ψ (гипотеза);
3) (φ→φ)→((φ→φ)→(φ→φψ)) (схема аксиом);
4) φ→φ (используем формулу из примера 13);
5) ((φ→ψ)→(φ→φψ)) (применим правило вывода к пунктам 4,3);
6) ψ→(φ→ψ) (схема аксиом);
7) φ→ψ (применим правило вывода к пунктам 2,6);
8) φ→φψ (применим правило вывода к п.п. 7,5);
9) φψ (применим правило вывода к п.п. 1,8).
Квазивыводом в ИВ формулы φ из формул φ1,…,φm называется последовательность формул ψ1,…,ψk,φ, в которой любая формула выводима из предыдущих.
Замечание 1. Если существует квазивывод в ИВ формулы φ из формул φ1,…,φm, то φ выводима в ИВ из формул φ1,…,φm.
Пример 3. Покажем, что φ├¬¬φ.
Решение. Построим квазивывод формулы ¬¬φ из формулы φ:
φ (гипотеза);
(¬φ→φ)→((¬φ→¬φ)→¬¬φ) (схема аксиом 9);
φ→(¬φ→φ) (схема аксиом 1);
¬φ→φ (к пп. 1 и 3 применили правило вывода);
(¬φ→¬φ)→¬¬φ (к пп. 4 и 2 применили правило вывода);
¬φ→¬φ (по примеру 2 выводимая формула);
¬¬φ (к пп. 6 и 4 применили правило вывода).
Теорема о дедукции в исчислении высказываний
Теорема 1 (о дедукции). Пусть Г – множество формул ИВ, φ,ψ – формулы ИВ. Тогда Г,φ├ψ, Г├φ→ψ.
Пример 4. Покажем, что φ→ψ├¬ψ→¬φ;
Решение. По теореме о дедукции
φ→ψ├¬ψ→¬φ φ→ψ, ¬ψ├¬φ.
Строим квазивывод формулы ¬φ из формул φ→ψ,¬ψ:
1) φ→ψ (гипотеза);
2) ¬ψ гипотеза;
(φ→ψ)→((φ→¬ψ)→¬ψ) (схема аксиом 9);
(φ→¬ψ)→¬φ (к пп. 1 и 3 применили правило вывода);
¬ψ→(φ→¬ψ) (схема аксиом 1);
¬φ.
Пример 5. Покажем, что φ→(ψ→χ)├ψ→(φ→χ)
Решение. По теореме о дедукции
φ→(ψ→χ)├ψ→(φ→χ)φ→(ψ→χ),ψ├(φ→χ)φ→(ψ→χ),ψ,φ├χ.
Строим вывод формулы χ из формул φ→(ψ→χ),ψ,φ:
1) φ→(ψ→χ) (гипотеза);
2) φ (гипотеза);
3) ψ (гипотеза);
4) ψ→χ (применим правило вывода к п.п. 2 и 1);
5) χ (применим правило вывода к п.п. 3 и 4).
Эквивалентные формулы исчисления высказываний
Формулы φ и ψ назовем эквивалентными (обозначим φ≡ψ), если
φ├ψ и ψ├φ.
Замечание 2. Для любых формул φ и ψ ИВ
φ≡ψ├φ→ψ и ├ ψ→φ.
Утверждение 1. Отношение φ≡ψ является отношением эквивалентности, т.е. для любых формул φ, ψ, χ ИВ справедливы следующие утверждения:
а) φ≡φ;
b) φ≡ψψ≡φ;
с) φ≡ψ, ψ≡xφ≡x.
Утверждение 2. а) Если φ≡ψ, то├φ├ψ.
b) если φ1≡ψ1 и φ2≡ψ2, то φ1∧φ2≡ψ1∧ψ2, φ1∨φ2≡ψ1∨ψ2, φ1→φ2≡ψ1→ψ2, ¬φ1≡¬ψ1.
Утверждение 3. Пусть φ,ψ, χ – формулы ИВ. Тогда
├φ→φ;
φ∧ψ→φ;
φ∧ψ→ψ;
φ,ψ├φψ;
φ→ψ, ψ→χ├φ→χ (свойство транзитивности);
φ→(ψ→χ)≡ψ→(φ→χ) (свойство перестановочности посылок);
φ→(ψ→χ)≡φ∧ψ→χ (свойство соединения и разъединения посылок);
φ→ψ≡¬ψ→¬φ (свойство контрапозиции).
Доказательство. Пункты 1, 4, 6, 8 доказаны в примерах 13, 14, 16, 17.
Докажем пункт 7. Покажем, что φ→(ψ→χ)├φψ→χ По теореме о дедукции φ→(ψ→χ)├φψ→χφ→(ψ→χ), φψ├χ.
Строим вывод формулы χ из формул φ→(ψ→χ), φψ
φ→(ψ→χ) (гипотеза);
φψ (гипотеза);
φψ→φ (схема аксиом 3);
φ (применим п.в.к п.п. 2,3);
φψ→ψ (схема аксиом 4);
ψ (применим п.в. к п.п. 2,5);
ψ→χ (применим п.в. к п.п. 4,1);
χ (применим п.в. к п.п. 6,7).
Покажем, что φψ→χ├φ→(ψ→χ). По теореме о дедукции
φψ→χ├φ→(ψ→χ)φψ→χ, φ├φ→χφψ→χ, φ, ψ├χ.
Строим вывод формулы χ из формул φψ→χ, φ, ψ.
φψ→χ (гипотеза);
φ (гипотеза);
ψ (гипотеза);
φψ (применим св-во 4 к п.п. 2 и 3);
χ (применим п.в. к п.п. 4,1).
Теорема 2. (Теорема о замене). Пусть φ формула ИВ, ψ ее подформула. Пусть φ' получается из φ путем замены некоторого вхождения ψ на формулу ψ'. Тогда если ψ ≡ ψ', то φ ≡ φ'.
Основные эквивалентности исчисления высказываний
Теорема 3. Пусть φ, ψ, χ формулы ИВ. Тогда имеют место эквивалентности:
φ∧ φ≡φ, φ∨ φ≡φ (законы идемпотентности);
φ∧ ψ≡ψ∧ φ, φ∨ ψ≡ψ∨ φ (законы коммутативности);
(φ∧ψ)∧χ≡φ∧(ψ∧χ), (φ∨ψ)∨χ≡φ∨(ψ∨χ) (законы ассоциативности);
φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ) (законы дистрибутивности)
¬(φ∧ψ)≡¬φ∨¬ψ, ¬(φ∨ψ)≡¬φ∧¬ψ (законы де Моргана);
¬¬φ≡φ (закон двойного отрицания);
φ→ψ≡¬φ∨ψ;
φ∧(φ∨ψ)≡φ, φ∨(φ∧ψ)≡φ (законы поглощения);
φ∨(¬φ∧ψ)≡φ∨ψ, ¬φ∨(φ∧ψ)≡¬φ∨ψ;
φ∧(¬φ∨ψ)≡φ∧ψ, ¬φ∧(φ∨ψ)≡¬φ∧ψ.
├φ∨¬φ.
Доказательство. В примере 15 показано, что φ├¬¬φ, покажем, что ¬¬φ├ φ. По теореме о дедукции ¬¬φ├ φ¬¬φ→ φ(аксиома), значит, ¬¬φ├ φ.
Докажем закон де Моргана ¬(φ∧ψ)≡¬φ∨¬ψ. Строим квазивывод формулы ¬(φ∧ψ)→¬φ∨¬ψ:
1) (¬(¬φ∨¬ψ)→φ)→((¬(¬φ∨¬ψ)→ψ)→(¬(¬φ∨¬ψ)→φ∧ψ)) (схема аксиом 5);
¬φ→¬φ∨¬ψ (схема аксиом 6);
¬(¬φ∨¬ψ)→¬¬φ (к п. 2 применили пример 15);
¬¬φ→φ (схема аксиом 10);
¬(¬φ∨¬ψ)→φ (к пп. 3 и 4 применили пример 13);
¬(¬φ∨¬ψ)→ψ (получается аналогично формуле 5);
(¬(¬φ∨¬ψ)→ψ)→(¬(¬φ∨¬ψ)→φ∧ψ) (к пп.5 и 1 применили правило вывода);
¬(¬φ∨¬ψ)→φ∧ψ (к пп. 6 и 7 применили правило вывода);
¬(φ∧ψ)→¬¬(¬φ∨¬ψ) (к п. 7 применили пример 15);
¬¬(¬φ∨¬ψ)→(¬φ∨¬ψ) (схема аксиом 10);
¬(φ∧ψ)→¬φ∨¬ψ (к пп. 9 и 10 применили пример 13).Строим квазивывод формулы ¬φ∨¬ψ→¬(φ∧ψ):
(¬φ→¬(φ∧ψ))→((¬ψ→¬(φ∧ψ))→((¬φ∨¬ψ)→¬(φ∧ψ))) (схема аксиом 8);
φ∧ψ→φ (схема аксиом 3);
¬φ→¬(φ∧ψ) (к п. 2 применили пример 15);
φ∧ψ→ψ (схема аксиом 4);
¬ψ→¬(φ∧ψ) (к п. 4 применили пример 15);
(¬ψ→¬(φ∧ψ))→((¬φ∨¬ψ)→¬(φ∧ψ)) (к пп. 3 и 1 применили правило вывода);
7) (¬φ∨ψ)→¬(φ∧ψ) (к 5 и 6 применили правило вывода).
Таким образом, закон де Моргана ¬(φ∧ψ)≡¬φ∨¬ψ доказан.
Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ╞φ), если φ(x1,…,xn) – тождественно истинная формула как формула алгебры высказываний.
Теорема 4 (о полноте). Формула φ ИВ доказуема тогда и только тогда, когда φ тождественно истинна:
├φ╞φ.
Таким образом, для того чтобы установить, доказуема ли формула ИВ, достаточно составить ее таблицу истинности. Как известно, существует эффективный алгоритм построения таблицы истинности, и, значит, ИВ разрешимо. Кроме того, из теоремы о дедукции и теоремы о полноте легко следует, что отношение эквивалентности ≡ в АВ и ИВ совпадают.
Пример 6. Доказать, что φ├φ.
По теореме о дедукции это равносильно тому, что ├φ→φ. В свою очередь, по теореме о полноте, достаточно доказать, что ╞φ→φ. Составляя таблицу истинности для формулы φ→φ, убеждаемся, что φ→φ тождественно истинна и, следовательно, доказуема.
Исчисление называется противоречивым, если любая формула данного исчисления доказуема в этом исчислении.
Исчисление называется непротиворечивым, если оно не является противоречивым
Теорема 5 (о непротиворечивости). ИВ непротиворечиво.
Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула х∧¬х. Следовательно, ИВ непротиворечиво.
Множество формул Г называется противоречивым, если Г├x∧¬x. Если Г противоречивое множество формул, то будем обозначать этот факт через Г К Множество формул Г называется непротиворечивым, если Г не является противоречивым множеством.
Утверждение 3. Формула φ выводима из множества формул Г тогда и только тогда, когда множество Г∨{¬φ} противоречиво:
Г├φГ,¬φ├.
Доказательство. Поскольку отношение эквивалентности ≡ в АВ и ИВ совпадают, то φ≡¬φ→x∧¬x в ИВ. Пусть Г={φ0,…, φn}. Тогда, пользуясь утверждением 2, следствием 1 и теоремой о замене, получаем
Г├φφ0∧…∧φn├φ├φ0∧…∧φn→φ├φ0∧…∧φn→(¬φ→x∧¬x)
φ0∧…∧φn,¬φ├x∧¬xГ∨{¬φ}├x∧¬x,
что и доказывает утверждение.
Схема аксиом называется независимой в исчислении, если хотя бы один ее частный случай не доказуем в исчислении без этой схемы. Доказательство следующей теоремы не приводится в виду его громоздкости.
Теорема 6. Схемы аксиом ИВ независимы.
2.4. Логика предикатов. Алгебраические системы
Часто объектом изучения в математике служит множество вместе с определенной на нем структурой. Например, поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь геометрических объектов с операциями над числами, множества с выделенными на них бинарными отношениями. Все эти структуры образуют алгебраические системы, представляющие собой некоторые миры с определенными на них законами. Перейдем к точному определению алгебраической системы.
Напомним, что п-местпным предикатом (отношением) на множестве А называется любое подмножество множества Аn; п-местной алгебраической операцией на множестве А называется функция ƒ:An→A, где Аn – n-я декартова степень множества А. Отметим, что поскольку операция ƒ является функцией, для любого набора (x1,…,xn)єAn результат применения операции ƒ(x1,…,xn) однозначно определен. Так как область значений операции ƒ лежит в множестве А, то будем говорить, что операция ƒ замкнута на множестве А.
Сигнатурой Σ называется совокупность предикатных и функциональных символов с указанием их местности. 0-местный функциональный символ называется константным символом или просто константой. Если α функциональный или предикатный символ, то его местность обозначается через μ(α) п-местные предикатные и функциональные символы часто будем обозначать соответственно через Р(n) и ƒ(n). Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, ≤ для отношения порядка, | для отношения делимости, 0 для константного символа и другие, то мы просто пишем Σ={≤}, Σ={≤,+, . , 0} и т.д.
Алгебраической системой A = А, Σ сигнатуры Σ называется непустое множество А, где каждому n-местному предикатному (функциональному) символу из Σ поставлен в соответствие n-местный предикат (соответственно операция) на А. Множество А называется носителем, или универсумом алгебраической системы А,Σ. Предикаты и функции, соответствующие символам из Σ, называются их интерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры. Заметим, что интерпретацией любого константного символа является некоторый элемент из А.
Пример 1. 1) Набор N, + , ∙ является алгебраической системой с двумя двухместными операциями.
Набор N,+, ∙ ,‘, 1,≤ является алгебраической системой с бинарным отношением ≤, двухместными операциями +, ∙, одноместной операцией ' : п→n+1 и нуль-местной операций 1.
Набор Z, +, : , не является алгебраической системой, поскольку деление не является операцией на множестве Z, а элемент не принадлежит Z.
Набор PU,∪,∩,,U является алгебраической системой, где PU –булеан множества U, т.е. множество всех подмножеств множества U.Алгебраическая система A=(A,Σ) называется подсистемой системы B=(В, Σ) (обозначается A B), если выполняются следующие условия:
а) АВ;
б) для любого функционального символа ƒ(n) Σ соответствующих функций ƒA и ƒ ß и любых элементов a1,a2,…,anA выполняется равенство ƒA(a1,a2,…,an)=ƒß (a1,a2,…,an), т.е. интерпретации символа ƒ действуют одинаково на элементах из А;
в) для любого предикатного символа Р(n)Σ, соответствующих предикатов PA и PB справедливо равенство P =PB∩An, т.е. предикат PA содержит в точности те кортежи предиката PB, которые состоят из элементов множества А.
Теорема 1. Если B алгебраическая система, XВ, X≠Ø, то существует единственная подсистема B(Х)B с носителем В(Х) такая, что XВ(Х) и B(Х) A для любой подсистемы A B, для которой XА.
Доказательство. В качестве В(Х) рассмотрим пересечение носителей А всех подсистем A B, содержащих X. Так как XВ(Х), то В(Х)≠Ø. Единственность подсистемы B(Х) очевидна.
Подсистема B(Х) из теоремы 1 называется подсистемой, порожденной множеством X в В.
Для описания устройства подсистемы B(Х) определим индукцией по построению понятие терма сигнатуры Σ:
переменные и константные символы из Σ суть термы;
если ƒΣ n-местный функциональный символ, t1,t2,…,tn термы, то ƒ(t1,t2,…,tn) терм;
никаких термов, кроме построенных по пп. 1,2, нет.Множество всех термов сигнатуры Σ обозначается через Т(Σ).
Пример 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; A=(A,Σ) алгебраическая система. Значение терма t при значениях a1,…,akA переменных x1,…,xk(t(a1,…,ak)) определяется по индукции:
если t есть переменная xi (константный символ с), то значение t есть аi(с):
если терм t есть ƒ(t1,…, tn), а значения t1,…,tn суть b1,…,bn, то значение терма t есть ƒ(b1,…, tn).
Теорема 2. Если B=(B,Σ) алгебраическая система, Ø≠xB, то носитель подсистемы B(Х) равен {t(a1,…,an)׀tT(Σ), a1,…,anX}.
Доказательство. Индукцией по числу шагов построения терма t получаем, что если t(x1,x2,…,xn)T(Σ) и a1,…,anX, то t(a1,…,an)А для любой подсистемы A B, содержащей X. Поэтому достаточно показать, что множество Y={t(a1,…,an)׀tT(Σ), a1,…,anX} замкнуто относительно операций системы B. Пусть ƒ(n)єT(Σ), t1,…,tmT(Σ), bi=t(a1,…,an), i{1,…,m}. Тогда ƒ(b1,…,bm)Y, поскольку ƒ(t1,…,tm)T(Σ).
Таким образом, носитель подсистемы B(X) состоит из всех элементов, которые получаются при подстановке элементов из X в термы.
Пример 3.
1) Найдем носитель подсистемы B(Х) системы B=(Q , ∙) для множества X={1/2}. Так как сигнатура Σ системы В есть {∙}, то Т(Σ)={x1, x1x2, (x1x2)x3, x1(x2x3),…}. По теореме 2 получаем B(X)={1/2, 1/2∙1/2, 1/2∙1/2∙1/2,…}={1/2, 1/8, 1/16,…}={1/2n, n≥1}.
2)Если B=(Q\{0}, . , : ) X={1/2}, то, поскольку по сравнению с предыдущим примером сигнатура дополняется операцией деления, множество В(Х) содержит числа 1/2n:1/2m=2m-n, m, n≥1, т.е. C={2n׀nєZ}B(X). Так как множество С замкнуто относительно операций умножения и деления. т.е. (C, Σ) является подсистемой системы B и содержит множество X, то В(Х)С. Следовательно, B(Х)=С.
Пример 4. Построить подсистему алгебраической системы А, порожденную множеством Х.
A=Z; -
X={22;-36}.
Решение. Надо определить какую подсистему порождают
22;-36 “-“. Таке как 2=22-8∙(-36)-14∙22 и любое число, получаемое из чисел 22, -36 с помощью операции вычитания четное, то
AХ=2ZПример 5. Построить подсистему алгебраической системы A, порожденную множеством Х.
A= R\{0};:
Х={;}.
Решение.
AХ={ z}.
Формулы ЛП
Большинство определений этого параграфа будут индуктивными.
Введем понятие атомарной формулы сигнатуры Σ:
если t1, t2,T(Σ), то t1=t2 атомарная формула:
если P(n)Σпредикатный символ, t1,t2,…,tnT(Σ), то Р(t1,t2,…,tn) атомарная формула;
никаких атомарных формул, кроме построенных по пп. 1, 2, нет.
Формула сигнатуры Σ определяется следующим образом:
1) атомарная формула есть формула;
если φ, ψ - формулы, то ¬φ, (φ∧ψ), (φ∨ψ), (φ→ψ), xφ, xφ формулы;
никаких формул, кроме построенных по пп. 1, 2, нет.
Символы , использованные в определении, называются соответственно квантором всеобщности и квантором существования и читаются "для любого"и "существует". Все соглашения относительно расстановок скобок, принятые в алгебре высказываний, остаются в силе и для формул логики предикатов. Кроме того, вместо записей x1…xnφ и x1…xnφ будем использовать записи x1,…,xnφ и x1,…,xnφ.
Определим подформулы формулы φ сигнатуры Σ:
если φ атомарная формула, то φ ее единственнаяподформула;
если φ имеет вид ¬φ1, или xφ1, или xφ1, то подформула формулы φ – это либо φ, либо подформула формулы φ1;
если φ имеет вид φ1∧φ2, или φ1∨φ2, или φ1→φ2, то подформула формулы φ это либо φ, либо подформула формулы φ1, либо подформула формулы φ2;
других подформул формулы φ, кроме построенных попп. 1, 2, 3, нет.
Пример 1. Пусть Σ={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ψ; в противном случае это вхождение называется свободным в φ. Переменная х называется свободной (связанной), если некоторое вхождение х в φ свободно (связано).
Пример 2. Пусть S={P1(1),P2(2)}. Рассмотрим формулы:
P1(x);
Р2(x,y)→xP1(x);3)x(P2(x,y)→P1(x)).
Переменная х в первой формуле является свободной, во второй - и свободной, и связанной, в третьей связанной: переменная у во всех формулах свободна.
Пример 3.
Выписать все подформулы формулы φ, определить свободные и связанные вхождения переменных.
φ⇋xzy(xy+z)((z∙2=u)→u(u=x+z)).
Определить все свободные и связанные переменные формулы φ.
Решение. Выпишем подформулы формулы φ.
xy+z,
y(xy+z),
zy(xy+z),
xzy(xy+z),
z2=u,
u=x+z,
u(u=x+z),
(z2=u)→u(u=x+z),
φ.
Поскольку существуют связанные и свободные вхождения переменной х в формулу φ, то х является связанной и свободной переменной. Переменные u и z тоже связанные и свободные. Переменная y связанная.
Предложением или замкнутой формулой сигнатуры Σ называется формула сигнатуры Σ, не имеющая свободных переменных.
Запись φ(x1,…,xn) будет означать, что все свободные переменные формулы φ содержатся в множестве {x1,…, xn}.
2.6. Истинность формулы ЛП в алгебраической системе.
Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатуры Σ на элементах a1,…,anА в алгебраической системе A=А,Σ.
Запись A╞φ(a1,…,an) будет означать, что формула φ истинна на элементах a1,…,anА в системе A.
1) A╞t1(a1,…,an)=t2(a1,…,an), где t1,t2T(Σ), значения термов t1,t2 в системе Ã на элементах a1,…,anА совпадают;
2) A╞P(t1(a1,…,an),….,tk(a1,…,an)), где P(k)Σ,t1,…,tkT(Σ),↔ (t1(a1,…,an),…, tk(a1,…,an))P;
3) A╞ψ(a1,…,an)∧χ(a1,…,an) A╞ψ(a1,…,an) и A╞χ(a1,…,an);
A╞ψ(a1,…,an)∨χ(a1,…,an) A╞ψ(a1,…,an) или A╞χ(a1,…,an);
A╞ ψ(a1,…,an) → χ(a1,…,an) если A╞ ψ(a1,…,an), то A╞ χ(a1,…,an);
A╞¬ψ(a1,…,an)неверно, что A╞ψ(a1,…,an);
A╞xψ(x,a1,…,an) A╞ψ(a,a1,…,an) для любого аA;
A╞xψ(x,a1,…,an) A╞ψ(a,a1,…,an) для некоторого аА.
Если не выполняется A╞φ(a1,…,an), то будем говорить, что формула φ(a1,…,an) ложна в системе A.
Пример 1.
Записать формулу φ(x), истинную в N,+, тогда и только тогда, когда х четно.
Решение.
φ(x)=y(x=y+y).
Пример 2.
Записать формулу φ'(x,y,z), истинную в N,+,∙ тогда и только тогда, когда 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)→w1(w=w1∙z)). Итак,
φ'(х,у,z)=u,∨(z=u∙x∧z=х∙y)∧w(u,∨(w=ux∧w=хy)→w1(w=w1z)).
2.7. Логическое следствие в ЛП
Через обозначим кортеж переменных ; через .
Определение. Пусть φ1(),…,φn(), ψ() – формулы сигнатуры ∑. Формула ψ называется логическим следствием формул φ1,…,φn (обозначается φ1,…,φn╞ ψ), если для любой алгебраической системы A сигнатуры ∑
A╞( φ1()…φn()→ψ()).
Пример 1.
Доказать, что φ1()→φ2(),φ2()→φ3()╞φ1()→φ3() (1)
где φ1(),φ2(),φ3() – формулы сигнатуры ∑.
Пусть A=‹А, ∑› произвольная система сигнатуры ∑. Необходимо указать, что A╞((φ1()→φ2())((φ2()→φ3())→(φ1()→φ3())).
Пусть и A╞ ((φ1()→φ2())((φ2()→φ3()).
Покажем, что A╞(φ1()→φ3() (2)
Предположим, что A╞φ1(). Так как A╞(φ1()→φ2(), то A╞φ2().
Так как A╞φ2()→φ3(), то A╞φ3().
Таким образом (2), а, следовательно, и (1), доказано.
2.8. Исчисление предикатов
Зафиксируем некоторую произвольную сигнатуру Σ и определим исчисление предикатов сигнатуры Σ (ИПΣ).
Формулами ИПΣ будут формулы сигнатуры Σ.
Примем следующие соглашения. Пусть x1,…,xn переменные, t1,…,tn термы сигнатуры Σ и φ формула сигнатуры Σ. Запись будет обозначать результат подстановки термов t1,…,tn вместо всех свободных вхождений в φ переменных x1,…,xn соответственно, причем, если в тексте встречается запись , то предполагается, что для всех i={1,...,n} ни одно свободное вхождение в φ переменной xi не входит в подформулу φ вида yψ или yψ, где у - переменная, входящая в ti.
Аксиомами ИПΣ являются аксиомы вида 1-10 ИВ, а также аксиомы
11) xφ→(φ)tx;
12) (φ)tx→xφ;
13) x=x;
14) x=y→((φ)xz→(φ)yz).
Формулы 1-14 называются схемами аксиом ИПΣ.
Правила вывода ИПΣ:
1. φ, φ → ψ , ψ
2. ψ → φ ,
ψ→xφ
3. φ → ψ , xφ → ψ
где в правилах 2 и 3 переменная x не входит свободно в ψ.
Доказательством в ИПΣ формулы φ называется такая последовательность φ0,…,φn формул ИПΣ, что φn⇌φ и для каждого i≤n формула φi удовлетворяет одному из следующих условий:
φi аксиома ИПΣ;
φi получается из некоторых φ1,…, φi-1 , по одному из правил вывода 1-3.
Если существует доказательство в ИПΣ формулы φ, то φ называется доказуемой в ИПΣ или теоремой ИПΣ (обозначаем ├φ).
Выводом в ИПΣ формулы φ из множества формул φ1,…, φm называется такая последовательность ψ1,…, ψk формул ИПΣ, что φn⇌φ и для каждого i≤n формула φi удовлетворяет одному из следующих условий:
φi аксиома ИПΣ;
φi принадлежит Г;
φi получается из некоторых ψ1,…, ψi-1j<i, по одному из правил вывода 1-3, причем при применении правил 2 и 3 переменная х не должна входить ни в одну формулу из Г свободно.
Если существует вывод в ИПΣ формулы φ из множества формул φ1,…, φn, то φ называется выводимой в ИПΣ из Г (обозначаем Г├φ). При этом Г называется множеством гипотез. Очевидно, что доказуемость формулы эквивалентна ее выводимости из пустого множества гипотез. Так же, как в исчислении высказываний, определяется понятие квазивывода. Если Г={ψ1,…,ψn}, то вместо Г├φ пишем ψ1,…,ψn├φ.
Формула ψ сигнатуры Σ называется тавтологией, если она получается из формулы φ исчисления высказываний, доказуемой в исчислении высказываний, путем замены всех ее пропозициональных переменных x1,…,xn на формулы ψ1,…,ψn сигнатуры Σ соответственно. Формулу φ при этом называют основой тавтологии.
Утверждение 1. Любая тавтология φ сигнатуры Σ доказуема в ИПΣ.
Следствие 1. Если φ и ψ пропозиционально эквивалентные формулы сигнатуры Σ, то φ и ψ эквивалентные формулы сигнатуры Σ.
В исчислении предикатов ИПΣ справедлива теорема о дедукции.
Теорема 1. (о дедукции). Пусть Г – множество формул ИПΣ, φ,ψ – формулы ИПΣ. Тогда Г,φ├ψ, Г├φ→ψ.
2.8.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¬φ из Ø:
φ→xφ аксиома 12;
¬xφ→¬φ к п.1 применили утверждение 3:
¬xφ→x¬φ к п.2 применили правило вывода 2.Построим квазивывод формулы x¬φ→¬xφ из Ø:
x¬φ→¬φ аксиома 11;
φ→¬x¬φ к п.1 применили утверждение 3;
xφ→¬x¬φ к п. 2 применили правило вывода 3;
x¬φ→¬xφ к п.З применили утверждение 3.
Пример. 2. Докажем эквивалентность г). Построим квазивывод формулы x(φ∧ψ)→xφ∧ψ из Ø:
x(φ∧ψ)→φ∧ψ аксиома 11;
φ∧ψ→φ утверждение 1;
x(φ∧ψ)→φ к пп.1,2 применили утверждение 1;
x(φ∧ψ)→xφ к п.4 применили правило вывода 2;
φ∧ψ→ψ утверждение 1;
x(φ∧ψ)→ψ к пп.1,5 применили утверждение 1;
(x(φ∧ψ)→xφ)→((x(φ∧ψ)→ψ)→(x(φ∧ψ)→xφ∧ψ)) аксиома 5;
8. x(φ∧ψ)→ xφ∧ψ к пп.4.6.7 применили правило вывода 1.
Построим квазивывод формулы x φ ∧ ψ → x (φ ∧ ψ) из Ø:
xφ∧ψ→xφ аксиома 3;
xφ→φ аксиома 11;
xφ∧ψ→φ к пп.1,2 применили утверждение 1;
xφ∧ψ→ψ аксиома 4;
(xφ∧ψ→φ)→((xφ∧ψ→ψ)→(xφ∧ψ→φ∧ψ)) аксиома 5;
xφ∧ψ→φ∧ψ к пп.3,4,5 применили правило вывода 1;
xφ∧ψ→x(φ∧ψ) к п.6 применили правило вывода 2.
Теорема 1. (теорема о замене). Если формула φ сигнатуры Σ получается из формулы ψ сигнатуры Σ заменой некоторого вхождения подформулы ψ' на формулу φ' сигнатуры Σ и φ'≡ψ', то φ≡ψ.
Пренексная нормальная форма для формул ИП
Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Говорят, что бескванторная формула φ находится в дизъюнктивной (конъюнктивной) нормальной форме, если она получается из некоторой формулы ψ исчисления АВ, находящейся в ДНФ (КНФ) заменой всех пропозициональных переменных x1,…,xn на некоторые атомарные формулы φ1,…,φn сигнатуры Σ соответственно.
Говорят, что формула φ сигнатуры Σ находится в пренексной нормальной форме (ПНФ), если она имеет вид Q1x1…Qnxnψ, где Qi, кванторы 1≤i≤n, а ψ бескванторная формула, находящаяся в ДНФ.
Теорема 1. Для любой формулы φ сигнатуры Σ существует формула ψ сигнатуры Σ, находящаяся в ПНФ и эквивалентная формуле φ.
Пример 1. Формулу χ⇌=xyφ(x,y)→xyψ(x,y) привести к пренексной нормальной форме. считая формулы φ и ψ атомарными.
Решение. Избавившись от импликации, получаем χ≡¬(xyφ(x,y))∨xyψ(x,y). Используя утверждение 3, пп. а, б утверждения 4 и теорему о замене, получаем χ≡xy¬φ(x,y)∨xyψ(x,y). Так как в формуле xyψ(x,y) переменные х, у являются связанными, то по пп. д, е утверждения 4 имеем χ≡xy(¬φ(x,y)∨xyψ(x,y)). Пусть u, ∨ некоторые новые переменные. Тогда по пунктам ж, з утверждения 4 получаем χ≡xy(¬φ(x,y)∨uv ψ(u,v)), откуда по пунктам ж, з утверждения 4 χ≡xyuv(¬φ(x,y)∨ψ(u,v)). Формула ¬φ(x,y)∨ψ(u,v) находится в ДНФ, а значит, формула xyuv(¬φ(x,y)∨ψ(u,v)) находится в ПНФ.
Теорема 2. Все доказуемые в ИПΣ формулы являются тождественно истинными.
Доказательство проводим индукцией по длине вывода формулы. Очевидно, что аксиомы ИПΣ являются тождественно истинными. Проверку того, что правила вывода 1-3 сохраняют тождественную истинность, мы оставляем читателю в качестве упражнения.
Следствие 1. Исчисление ИПΣ непротиворечиво, т.е. не все формулы ИПΣ доказуемы в ИПΣ.
В ИПΣ справедлив аналог теоремы о полноте в исчислении высказываний:
Теорема 3 (теорема Геделя о полноте). Формула φ исчисления ИПΣ доказуема тогда и только тогда, когда φ тождественно истинна.
Таким образом, проверка доказуемости формулы φ сводится к проверке ее тождественной истинности. Однако в отличие от ИВ в общем случае не существует алгоритма распознавания доказуемости формул ИПΣ, т. е. ИПΣ неразрешимо. Тем не менее если в формуле φ "записать", что каждая переменная может принимать конечное число значений, то перебором всех возможных систем можно установить, является ли формула тождественно истинной или нет.
2.10. Машины Тьюринга
Машина Тьюринга – это система, работающая в дискретные моменты времени и состоящая из следующих частей:
конечная лента, разбитая на конечное число ячеек. В каждый момент времени в ячейках записаны буквы из некоторого алфавита (где , ), называемого внешним алфавитом машины. Ячейка, в которой записан символ , называется пустой. Если в какой–то момент времени лента имеет ячеек, то состояние ленты полностью описывается словом , где – состояние первой (слева) ячейки, – состояние второй ячейки и т.д.
Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и имеет некоторое состояние из конечного множества внутренних состояний , . Состояние называется заключительным и означает завершение работы машины. Состояние называется начальным и означает начало работы машины.
Программа Π, т.е. совокупность выражений (где ), называемых командами, каждое из которых имеет один из следующих видов:

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

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

замена буквы в текущей ячейке на букву , а также замена состояния головки на состояние
Замечание 1.1) Команды не могут начинаться со слов .
2) .
Таким образом, машина Тьюринга – это пятерка .
Машинным словом называется слово , где – состояние ленты, – состояние головки, находящейся напротив ячейки с состоянием , занимающей то же положение среди других ячеек, что и буква в слове .
Пустое слово обозначим через .
Опишем преобразование машинного слова в машинное слово за один шаг работы машины :
если , то при и при ;
если , то при и при ;
если , то .
Машинное слово получается из машинного слова с помощью машины Тьринга , если существует последовательность преобразований , , для которой , .
Пусть – множество натуральных чисел с нулем, .
Частичная функция – это отображение , где . Если , то частичная функция называется всюду определенной. Если , то частичная функция называется нигде ен определенной.
Для любого числа через обозначим слово, состоящее из числа единиц: . Для любой –ки слово называется записью этой –ки.
Частичная функция , где , называется вычислимой по Тьюрингу, если существует машина Тьюринга такая, что
1) ;
2) машина применима к записи –ки ;
3) для и .
Пример 1. Построим машину Тьюринга , вычисляющую функцию . Пусть , где , , программа Π состоит из команд:



2.11. Примитивно вычислимые функции
Базисными функциями называются следующие функции: – нулевая функция; – функция следования; – функция выбора.
Оператор суперпозиции (подстановки) ставит в соответствие – местной операции и – местным операциям –местную операцию h⇋, удовлетворяющую тождеству:

Оператор примитивной рекурсии ставит в соответствие – местной операции и – местной операции – местную операцию h⇋, удовлетворяющую схеме примитивной рекурсии:


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


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



2.12. Частично рекурсивные функции
Оператор минимизации ставит в соответствие – местной операции –местную операцию h⇋ так, что



В этом случае введем обозначение:
Функция называется частично рекурсивной (ЧРФ), если существует последовательность функций , в которой и всякая является либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозиции , примитивной рекурсии или минимизации .
Пример 1. Нигде не определенная функция является ЧРФ:
.
Пример 2. Функция
fx,y=x-y, если x≥y , не определена в остальных случаяхявляется ЧРФ:

ЗАДАНИЯ ДЛЯ домашних И КОНТРОЛЬНЫХ РАБОТ
3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
Построить таблицы истинности для следующих формул алгебры высказываний и привести эти формулы к СДНФ и СКНФ.
1.(x∧¬y)→(y∧z);
2.(x→¬y)→(¬y∧z);
3.((x∧¬y)→x)→z;
4.(x∧¬(y→z)→x∨(y∧z);
5.z→(x∧¬y)∨(y∧z);
6.((x∨z)∧¬y)→¬(y→z);
7.(x∧(z→¬y)→¬y)∨¬z);
8.(¬(x∧¬y)→z∨(y∧z);
9.(((x→y)→¬z)∨¬y)∧z;
x∧(z→y)→¬z∨¬y;
((x∨z)∧¬y)→¬(y→z);
(x→y)→¬z∨¬(y∧¬z);
x→¬(y→z)∧(z∨x);
¬((¬x∧z)→y)∨¬z;
(¬(x→y)∧z→¬z)∨¬y;
x∨¬(z→y)→¬(¬y∧z);
((x∧z→y)→¬z)∨¬z;
(x∧z →y)→¬z∨¬y;
(x→y∧¬z)∨¬y→z;
¬x→¬(y→z)∨(y∧z);
((x∨y)→¬z)→(¬y∧z);
(¬x→y)→¬(z∨y)∧z;
(¬(x→y)∧¬z)∨¬y)→z;
(¬z→y)→x∧(¬z∨¬y)∧z;
((x∧¬z)∨¬y)→z∧¬(x→y).
3.2. Логическое следствие в алгебре высказываний
Проверить истинность соотношений тремя способами (используя определение логического следствия и пп. 3,4 теоремы 2.
;
;
3.;
4.;
5.;
6.;
7.;
8.;
9.;
10.;
11.;
12.;
13.;
14.;
15.;
16.;
17.;
18.;
19.;
20.;
21.
22.
23.;
24.;
25.
3.3. Исчисление высказываний
Пусть - формулы исчисления высказываний. Построить вывод формулы исчисления высказываний из данного множества гипотез.
;
;
;
;
;
;


;
;
;
;
;
















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























Ø,

Ø,


Ø,
Формулы ЛП
Выписать все подформулы данной формулы сигнатуры Σ={+,∙,≤,0} и определить свободные и связанные переменные формулы:




















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














,





Истинность формулы ЛП
в алгебраической системе
Написать формулу Ф(х), истинную в алгебраической системе тогда и только тогда, когда
х=1;
х=2n для некоторого натурального n;
х>4;
х – нечетное число;
х – простое число.
Написать формулу Ф(х,y), истинную в алгебраической системе тогда и только тогда, когда
;
;
х делит ;
;
, где p - простое число.
Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда
x делится на y с остатком 2;
x+3y>2z;
z – общий делитель y и z;
z = НОК (x,y);
z = НОД (x,y).
Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда
x=0;
x=-1;
2x-3y – четное число;
3z=4x-5y;
z-2y делится на 3x.
Пусть – булеан множества B, т.е. множество всех подмножеств множества B.Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда
есть пересечение и ;
есть объединение и ;
Ø;
;
есть дополнение .
Пусть – булеан множества B, т.е. множество всех подмножеств множества B.Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда
;
Ø;
есть одноэлементное множество;


Написать формулу , такую что







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








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




















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














,





3.10. Машины Тьюринга
Построить машину Тьюринга , вычисляющую следующую функцию.
x+1;
x+y;
sgx=0, если x=0,1, если x>0;sgx=0, если x>0,1, если x=0;x-1=0, если x=0, x-1, если x>0;x-y=0, если x≤y, x-y, если x>y;x2;x2. Примитивно рекурсивные функции
Доказать, что следующие функции примитивно рекурсивны.
x+1;
x+y;
sgx=0, если x=0,1, если x>0;sgx=0, если x>0,1, если x=0;x-1=0, если x=0, x-1, если x>0;x-y=0, если x≤y, x-y, если x>y;|x-y|;
max(x,y);
min(x,y);
sgx=0, если x=0,1, если x>0;xy – частное от деления x на y (здесь xy=x);
rest(x,y) – остаток от деления x на y ( здесь rest(x,0)=x);
τ(x) – число делителей числа x, где τ(0)=0;
σ(x) – сумма делителей числа x, где σ(0)=0;
lh(x) – число простых делителей числа x, где lh(0)=0;
π(x) – число простых чисел, не превосходящих x;
k(x,y) – наименьшее общее кратное чисе x и y, где k(x,0)=k(0,y)=0.
d(x,y) – наибольший общий делитель чисе x и y, где d(0,0)=0.
. Частично рекурсивные функции
Доказать, что следующие функции частично рекурсивны.
fx,y=xy, если x делится на y , не определена в остальных случаях;fx,y=z, если zy=x, не определена в остальных случаях;fx,y=xy, если x делится на y , не определена в остальных случаях;fx,y=xy, если x делится на y , не определена в остальных случаях;fx,y=xy, если x делится на y , не определена в остальных случаях;fx,y=xy, если x делится на y , не определена в остальных случаях;fx,y=xy, если x делится на y , не определена в остальных случаях;fx,y=xy, если x делится на y , не определена в остальных случаях;СПИСОК ЛИТЕРАТУРЫ
4.1. Основная литература
Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1987.
Судоплатов С.В., Овчинникова Е.В. …………….
Новиков П.С. Элементы математической логики. – М.: Наука,1973.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука,1981.
Степанова А.А. Математическая логика и теория алгоритмов. Учеб.пособие.- Находка: Институт технологии и бизнеса, 2003.-56 с.
Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. М.: Инфра-М, 2004.
4.2. Дополнительная литература
Мендельсон Э. Введение в математическую логику. – М.: Наука,1976.
Лихтарников Л.М., Сукачева Т.Г. Математическая логика. С.П.:Лань,1998.
Черч А. Введение в математическую логику. – М.: Наука. 1960.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………………………………………………………………….3 1.ПРОГРАММА КУРСА ………………………………………..................4 2. ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ……………………………………….6 2.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы………………….……...…….…..….6 2.2. Логическое следствие в алгебре высказываний…….....…..……..11 2.3. Исчисление высказываний……………………………………....…...12 2.4. Логика предикатов. Алгебраические системы………………..…...19 2.5. Формулы ЛП………….………………………………….……...…….22 2.6. Истинность формулы ЛП в алгебраической системе ..…………23 2.7. Логическое следствие в ЛП…………………….……….…..……....24 2.8. Исчисление предикатов……….…………..………………………… 25 2.9. Пренексная нормальная форма для формул ИП…….………..…...28 2.10. Машины Тьюринга…………………………………………….....….29 2.11 Примтивно екурсвные функци…………………………………...…31 2.12. Частичо рекурсивные функции…………………………………......32 3. ЗАДАНИЯ ДЛЯ КОНТРОЛЬНЫХ РАБОТ……………..……….…...33 3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы………………….……...…….…..33 3.2. Логическое следствие в алгебре высказываний…….....…..……..33 3.3. Исчисление высказываний……………………………………....…...34 3.4. Логика предикатов. Алгебраические системы………………..…...36 3.5. Формулы ЛП………….………………………………….……...…….37 3.6. Истинность формулы ЛП в алгебраической системе ..…………38 3.7. Логическое следствие в ЛП…………………….……….…..……....40 3.8. Исчисление предикатов…………………..………………………… 41 3.9. Пренексная нормальная форма для формул ИП…….………..…...42 3.10. Машины Тьюринга…………………………………………….....….43 3.11 Примтивно екурсвные функци…………………………………...…43 3.12. Частичо рекурсивные функции…………………………………......44 4. СПИСОК ЛИТЕРАТУРЫ…………………………………………...….45

Приложенные файлы

  • docx 8821076
    Размер файла: 825 kB Загрузок: 0

Добавить комментарий