|
|
| Лекция: Математическая Логика |
Правило одновременной подстановки.
Замечание: Если формула  выводима, то выводима и 
Возьмем формативную последовательность вывода  
и добавим в неё  ,
получившаяся последовательность является формальным выводом.
(Если выводима  то если  , то выводима  )
Теор: Если выводимая формула  , то  ( - различные символы переменных) выводима
Выберем  - символы
переменных которые различны между собой и не входят не в одну из формул 
, сделаем подстановку 
и последовательно применим 
и в новом слове делаем последовательную подстановку: 
, где  - является
формальным выводом.
3.1.3 Формальный вывод из гипотез.
Опр: Формальным выводом из гипотез 
(формулы), называется такая последовательность слов 
, каждая из которых удовлетворяет условию:
 если формулу  можно включить в некоторый формальный вывод из гипотез  .
Лемма:  ;  : то тогда 
Напишем список:
  
Лемма:
Док:   
3.1.4 Теорема Дедукции.
Если из
 
1) и 2а)  , где   по правилу m.p.  , ч.т.д.
2б)  - уже выводили  , ч.т.д.
Базис индукции: N=1  - формальный вывод из длинного списка 
 (только что доказано), осуществим переход по индукции:
 по индукции
 и по лемме 2
Пример: 
 по теореме дедукции 
3.2 Критерий выводимости в ИВ.
3.2.1 Формулировка теоремы.
 - тавтология
при любой интерпретации алфавита (символов переменных)
3.2.2 Понятие интерпретации.
символ переменной   переменную поставим в соответствие.
 , где  - проекция на  .
 
 ;  - только символ
переменных, т.к.
это заглавное слово
формативной последо-
вательности вида:
Где:
3.2.3 Доказательство теоремы.
 
 формальный
вывод 
(1) 
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
| 
|
Пронесение отрицания через кванторы
 
Геометрическое 'доказательство':
 не обладает свойством, что прямая  целиком лежит в 
 ч.т.д.
Страницы: 1, 2
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
