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

Тема 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. никаких других формул АВ, кроме построенных по пп. 1 и 2, нет.

Если формула φ АВ построена из логических переменных, принадлежащих множеству {х₁,х₂,…,x_n}, то будем писать φ(x₁,…x_n).

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

Эти логические операции следующим образом интерпретируются в русском языке: ¬φ — "не φ", (φ∧ψ) — φ и ψ, (φ ψ) — φили ψ, ( φ → ψ) — если φ, то ψ.

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

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

Пример 1. Построить таблицу истинности для формулы φ((x→y)∧((¬y→z)→¬x)).

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

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

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

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

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

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

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