Математическая логика и теория алгоритмов. Стенюшкина В.А. - 19 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

щейся теоремой, либо лает ответ «нет», либо не дает никакого ответа (то есть
алгоритм применим (может быть, не ко всем формулам).
4.3 Интерпретация формальных теорий
Интерпретацией I формальной теории Т в область интерпретации Ω на-
зывается отображение всех множеств и отношений на них формальной теории
Т в множество объектов и связей между ними области
Ω.
Это отображение должно удовлетворять условию: каждой формуле в Т
соответствует высказывание в
Ω. Если соответствующее высказывание в Ω яв-
ляется истинным, то говорят, что формула теории Т истинна в данной интерп-
ретации.
Интерпретация I называется моделью формальной теории Т, если все те-
оремы этой теории выполняются в интерпретации I (то есть для всех выводи-
мых из аксиом формул теории Т соответствующие высказывания в области
Ω
истинны).
Формула формальной теории называется тождественно истинной, или
тавтологией, если она истинна в любой интерпретации.
Формула формальной теории называется тождественно ложной, или
противоречием, если она ложна в любой интерпретации.
Формула называется выполнимой, если она истинна в некоторой интер-
претации.
4.4 Непротиворечивость. Полнота. Независимость
Формальная теория называется непротиворечивой, если в ней не являю-
тся одновременно выводимыми формула F и
F.
Формальная теория называется полной, если каждому истинному выска-
зыванию в
Ω соответствует теорема теории Т.
Система аксиом непротиворечивой теории Г называется независимой, ес
ли никакая из аксиом не выводима из остальных по правилам вывода теории Т.
5 Исчисление высказываний
Задача исчисления высказываний (ИВ) - описание всех тождественно
истинных формул.
5.1 Определение ИВ
Классическое ИВ - это формальная теория L, в которой:
- алфавит есть множество символов:
1
) а, b, ..., а
1
, b
1
, ...- (пропозициональные) переменные;
2
)
,
→
- связки;
3)
( , ) - служебные символы;
- множество формул есть множество цепочек символов, задаваемых син-
таксическими правилами: 
щейся теоремой, либо лает ответ «нет», либо не дает никакого ответа (то есть
алгоритм применим (может быть, не ко всем формулам).
      4.3 Интерпретация формальных теорий
       Интерпретацией I формальной теории Т в область интерпретации Ω на-
зывается отображение всех множеств и отношений на них формальной теории
Т в множество объектов и связей между ними области Ω.
       Это отображение должно удовлетворять условию: каждой формуле в Т
соответствует высказывание в Ω. Если соответствующее высказывание в Ω яв-
ляется истинным, то говорят, что формула теории Т истинна в данной интерп-
ретации.
       Интерпретация I называется моделью формальной теории Т, если все те-
оремы этой теории выполняются в интерпретации I (то есть для всех выводи-
мых из аксиом формул теории Т соответствующие высказывания в области Ω
истинны).
       Формула формальной теории называется тождественно истинной, или
тавтологией, если она истинна в любой интерпретации.
       Формула формальной теории называется тождественно ложной, или
противоречием, если она ложна в любой интерпретации.
       Формула называется выполнимой, если она истинна в некоторой интер-
претации.
      4.4 Непротиворечивость. Полнота. Независимость
       Формальная теория называется непротиворечивой, если в ней не являю-
тся одновременно выводимыми формула F и  F.
       Формальная теория называется полной, если каждому истинному выска-
зыванию в Ω соответствует теорема теории Т.
       Система аксиом непротиворечивой теории Г называется независимой, ес
ли никакая из аксиом не выводима из остальных по правилам вывода теории Т.

      5 Исчисление высказываний
      Задача исчисления высказываний (ИВ) - описание всех тождественно
истинных формул.

      5.1 Определение ИВ

      Классическое ИВ - это формальная теория L, в которой:
      - алфавит есть множество символов:
      1) а, b, ..., а1 , b1 , ...- (пропозициональные) переменные;
      2) , → - связки;
      3) ( , ) - служебные символы;
      - множество формул есть множество цепочек символов, задаваемых син-
таксическими правилами:

Страницы