Xreferat.com » Рефераты по математике » Математическая Логика

Математическая Логика

loading="lazy" src="http://xreferat.ru/image/54/1306465210_178.gif" alt="" width="1661" height="2048" align="ABSMIDDLE" />

Лемма:

Док:


3.1.4 Теорема Дедукции.

Если из

  1. и 2а) , где по правилу m.p. , ч.т.д.

2б) - уже выводили , ч.т.д.


Базис индукции: N=1 - формальный вывод из длинного списка

(только что доказано), осуществим переход по индукции:

по индукции

и по лемме 2

Пример:

по теореме дедукции


3.2 Критерий выводимости в ИВ.

3.2.1 Формулировка теоремы.

- тавтология

при любой интерпретации алфавита (символов переменных)


3.2.2 Понятие интерпретации.

символ переменной переменную поставим в соответствие.

, где - проекция на .


; - только символ

переменных, т.к.

это заглавное слово

формативной последо-

вательности вида:


Где:


3.2.3 Доказательство теоремы.


ф
ормальный

вывод




3.3 Непротиворечивость ИВ.

3.3.1 Определение.

  1. ИВ противоречиво, если формула А выводима в нем. .

  2. формула выводима в ИВ)ИВ противоречиво.

  3. ИВ противоречиво.

ИВ непротиворечиво, если оно не является противоречивым.


Теорема: ИВ является непротиворечивым исчислением по отношению к любому из трех определений.

Док-во: (1) Если , то соответствующая ей булева функция будет тождественно равна 1.


(2) Если любая формула выводима, то выводима и А, что соответствует пункту 1.

(3) Пусть и - булева функция

- противоречие.


3.4 Формальные исчисления.

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

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

V – множество всех слов.


Вычислимая функция от нескольких натуральных переменных

( f – может быть не всюду определенной )

f – называется вычислимой, если такая машина Тьюринга, которая её вычисляет.


- разрешимое множество, если характеристическая функция

- является вычислимой.

Множество называется перечислимым, если такая вычислимая функция

М - разрешимо М и N M перечислимы.

М – перечислимо М – область определения некоторой вычислимой функции.

Множество всех формул F – некоторое разрешимое подмножество V.

Т – счетное множество, если его биективное отображение на V.

- обозначение счетного множества. ( - алеф-нуль)


Если и зафиксировано биективное и вычислимое отображение (вычис.),

то L – ансамбль.

V – ансамбль (слова лексикографически упорядочены и занумерованы)


Определение: В произвольном формальном исчислении: - множество всех аксиом – разрешимое подмножество множества всех формул.

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

,при разрешимо. Для ИВ N=2.

Пример:

(пустое слово) ,

1 и 2 – формальные выводы.

3 – не является формальным выводом.

4 Предикаты и кванторы.

4.1 Определение предиката.

- высказывание, содержащее переменную.

- предметная область предиката.


Пусть А – множество объектов произвольной природы (предметная область предиката).


-местный предикат – произвольное отображение


Множество истинности данного предиката

-

- характеристическая

функция от x на множестве

А - совпадает

с предикатами



4.2 Понятие квантора.

k – связанная переменная

n – свободная переменная


t – свободная, x – связанная.

, a,b,y – свободные переменные, x – связанная.


4.3 Геометрическая интерпретация навешивания кванторов.


- ортогональная проекция на ось x


Пронесение отрицания через кванторы

Геометрическое 'доказательство':

не обладает свойством, что прямая целиком лежит в

ч.т.д.




Курс лекций по математической логике, читаемый Андреевым Кириллом Кирилловичем

Создал Томашевич Максим Сергеевич (info@tommax.bizland)

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

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