30042001 (1109980)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

30 апреля 2001 г.

Предикаты друг в друга подставляться не будут.

Определение. Формула – это

1. – формула. - множество свободных переменных; - множество связанных переменных.

2. Если и - формулы, а и соответственно множества свободных и связанных переменных первой и и соответственно множества свободных и связанных переменных второй формулы, причем выполнены условия и , то , - тоже формулы, множества свободных и связанных переменных равны соответственно и . При этом вычисление происходит по правилам и . Также является формулой со множеством свободных переменных и множеством связанных переменных . .

3. Дальше, если - формула, а и - множества свободных и связанных переменных ее, , то навешиванием квантора общности получаем формулу (обозначим ), , . Отсюда видно, что связанные переменные возникают вследствие навешивания кванторов. Пусть . Рассмотрим все наборы , где , , фиксированы, а пробегает все множество . Если для любого , то полагаем . В противном случае, если существует такое, что , то . На формулу можно навесить квантор существования аналогичным образом. Строим формулу (обозначим ) с и , равную 1 на наборе если существует такое , что , и 0, если такого нет.

Определение. Формула истинна в модели, если для любого набора значений свободных переменных она принимает значение 1 (истину).

Примеры.

- предикаты делимости соответственно на 2, 3, 6. Тогда формула (функция) истинна в модели .

- предикаты делимости на индекс. Тогда формула не является истинной на всех .

Определение. Формула истинна на множестве, если она истинна в любой модели, заданной на этом множестве (само множество фиксировано, а формула верна для любых предикатов).

Примеры.

.

- не всегда верна (можно получить ), но эта формула верна на одноэлементном множестве.

Определение. Тождественно истинная формула – формула, истинная для любого множества.

Также есть понятие эквивалентности формул (в модели, на множестве, тождественно); рассмотрим несколько примеров.

и эквивалентные формулы.

и эквивалентны на .

и эквивалентны на любой модели.

Оказывается, что

Теорема. Существует исчисление, содержащее конечное число аксиом и правило вывода , в котором все выводимые формулы тождественно истинны, а также все тождественно истинны формулы выводимы.

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

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

Пример. и эквивалентны. Здесь в первой формуле связана , во второй - . В обеих формулах свободными являются .

Группа правил №2. Формула эквивалентна формуле .

Эта утверждение – аналог закона Де-Моргана для многих переменных: .

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

Первый случай. Для любого . Тогда , . Но если для любого , то , откуда .

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

Аналогично можно получить, что эквивалентно .

Правила №3. Рассмотрим формулу и навесим на нее квантор общности , при предположении, что входит в число свободных переменных и не входит в вообще. Тогда эта формула эквивалентна .

Доказательство. Пусть - все свободные переменные в и (каждая встречается хотя бы в одной как свободная). Возьмем произвольный набор . Возможно, . Тогда для любого , а значит, . Но в то же время . Если же , то для любого (т.к. не входит в ), откуда при любом , следовательно, на данном (произвольном) наборе равно , равное , что указывает на эквивалентность формул.

При тех же условиях эквивалентны следующие пары формул:

и

и

и .

Зная это, можно показать, что любая формула приводима к специальному виду:

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

.

Доказательство. Сначала все отрицания переносим на формулы через все кванторы (для этого у нас есть два правила аналога законов Де-Моргана), а затем делаем все кванторы по разным переменным (т.е. замену связанной переменной на новую при ее повторении в каком-нибудь еще месте).

Пример. переводим в .

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

Пример. эквивалентно эквивалентно эквивалентно .

АЛГОРИТМЫ.

Определение. Алгоритм – это процедура, которая позволяет преобразовывать информацию:

• она четко описана

• приводит к результату.

Точные формулировки алгоритмов возникли в тридцатые годы двадцатого века.

Описание любой эффективной процедуры можно найти в терминах машины Тьюринга. Возьмем автомат , образуем , получим, что автомат на ленте работает так: . В середине изображена головка, передвигающаяся по ячейкам и содержащая информацию о состоянии в данный момент. Она считывает содержимое ячейки напротив, берет его в качестве очередной входной буквы, а на его место записывает выходную букву. Обобщим несколько ленту, а именно, будем считать, что двигаться можно не только вправо, но и влево, а также можно стоять на месте (а лента бесконечна в обе стороны). После этого получится машина Тьюринга. Команды будем задавать в следующем виде: , что расшифровывается так: в состоянии подается буква , на выходе получается буква , новое состояние – , обозначает направление движения ( – сдвиг влево, – вправо, – отсутствие сдвига). У каждой машины имеется конечный набор команд. Условимся всегда обозначать начальное состояние как , конечное как (когда получается состояние , машина останавливается; если оно никогда не получается, то машина не останавливается и называется неприменимой к ).

Рассмотрим . Эта машина стоит на месте, поэтому заключительного состояния никогда не получится. А вот машина является тождественной функцией: она оставляет букву, которая до ее применения была на исходном месте на ленте, остается на месте и сразу завершает свою работу, переходя в конечное состояние.

Удобно рассматривать числовые функции. Препятствием является то, что чисел бесконечно много, а алфавит конечен. В такой ситуации применяют кодировку чисел. Число кодируется массивом длины из единиц, набор как .

Рассмотрим машину: и ее действие на массиве . Она сначала дойдет до конца единичек, обнаружив 0, поставит туда 1 и пойдет обратно, пока не найдет 0, расположенный в начале числа, когда и остановится. Таким образом машина превратит массив из 1 в массив из единички, т.е. из кода сделает код : . Если взять два числа и , то в качестве результата получим : (после работы машины количество 1 будет – код числа ). А если взять , то машина поставит одну 1 и сдвинется влево – напишет код нуля, исходя от пустого множества (на ленте оно задается сплошными нулями, нулевой лентой): .

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов лекций