23042001 (1109977)

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

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

23 апреля 2001 г.

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

Логика занимается высказываниями, которые либо истинные, либо ложные (других в ней не бывает).

Пример. “23. 04. 2001 г. – понедельник” – истинное высказывание. “23. 04. 2001 г. – вторник” – ложное высказывание. “Среда ли 23. 04. 2001 г.?” – не высказывание.

Истинность высказывания будем обозначать 1, ложность - 0. В литературе еще встречаются обозначения И и Л (начальные буквы соответствующих слов), а в некоторых странах и . Будем иметь дело с логическими операциями , , , . Напомним определение импликации, а также отметим одно из ее основных свойств: , . Еще одно полезное свойство ее – это , коль скоро или и ни в каких других случаях (т.е. ).

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

Рассмотрим сначала систему аксиом и правил вывода под названием исчисления высказываний.

Аксиомы ИВ состоят из 4 групп:

I аксиомы, содержащие только импликацию:

1. ,

2. ;

II аксиомы, содержащие конъюнкцию:

3. ;

III аксиомы, содержащие дизъюнкцию:

3. ;

IV аксиомы, содержащие отрицание:

3. .

В этих аксиомах при их применении любую букву можно заменить на любую формулу

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

Также нам понадобится правило вывода .

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

Теорема. Любая выводимая формула тождественно равна 1.

Доказательство. Состоит из 2 шагов. На первом будет доказано, что все аксиомы тождественно равны единице, а на втором -, что если и , то , факт, следующий из свойств импликации. Отсюда, по определению вывода, будет следовать утверждение теоремы.

Остался первый шаг. Проведем его для первых двух аксиом, а для остальных оставляем читателю в качестве упражнения (там проще).

Итак, рассмотрим формулу . Если , то . Если , то , почему .

Рассмотрим . Если , то , а значит, , откуда . Если , то рассмотрим два случая относительно . Если , то , , следовательно, . Если , то имеем две возможности для . Если , то , , . Если , то, учитывая , получаем (все единицы).

Пример вывода. Формула .

По I.2 (вторая аксиома первой группы), имеем , где выступает в роли , - в роли , еще раз в роли . Эта формула имеет вид , где , а . По I.1 имеем (при ), т.е. как аксиому. Значит, можно вывести , а именно, , или , где и . Дальше, если положить , будем, по I.1, иметь , то бишь . Следовательно, имея и , выводимо , оно же .

Теорема. Любая формула, тождественно равная 1, выводима (иными словами, этот набор аксиом полон).

Здесь не будем приводит доказательства этой теоремы, ввиду того, что оно очень длинно, но не очень содержательно. Между прочим, когда А. Н. Колмогоров читал лекции по математической логике на этом факультете, он тоже не доказывал полноту системы ИВ. Тем не менее, можно указать идею доказательства: любая тождественно равная 1 формула приводится к СДНФ и переписывается в терминах этой системы аксиом, из чего получается ее выводимость.

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

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

Определение. Система аксиом называется независимой, если не содержит аксиомы, которую можно вывести из всех аксиом системы, кроме ее самой.

Предикаты –, грубо, это высказывания, зависящие от параметров.

Пример. « четное». - предикат делимости на .

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

Определение. Полная система предикатов на конечном множестве – такая система, что любой предикат над выражается через предикаты системы (с помощью четырех основных операций, приведенных выше).

Очевидно, всего предикатов на .

Теорема. - полная система для любых и из , таких что , найдется предикат, который принимает разные значения на и : .

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

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

Построим аналог СДНФ. Если , то . Если и - все элементы , на которых равно 1 ( ), то . Конец доказательства.

Рассмотрим еще некоторые логические конструкции: навешивание кванторов.

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

Навешивание квантора существования – операция получения предиката , который равен 1 в точке в том и только в том случае, если существует такая пара , что .

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

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

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

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

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

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

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