- •1.(30) Основные понятия мЛиТа
- •2. История развития теории алгоритмов.
- •3. Роль алгоритма в науке и технике.
- •4. Понятие алгоритма.
- •5. Алгоритмический процесс.
- •6. Основные вопросы теории алгоритмов.
- •7. Классификация алгоритмов.
- •8. Свойства алгоритмов.
- •9. Понятие предиката
- •10. Интерпретация. Модель
- •12. Нормальные алгорифмы Маркова.
- •13. Гипотеза Черча.
- •14. Машина Тьюринга.
- •15. Рекурсивные функции.
- •2) Тождественные функции любого числа независимых
- •16. Алгоритмически неразрешимые проблемы
- •17. Понятие о сложности
- •18. Временная и вычислительная сложность алгоритмов.
- •19. Понятие р- и np-задач.
- •21. Темпоральные логики. Нечеткая и модальные логики.
- •22. Примеры задач np-класса.
- •24. Дедуктивные теории
- •25. Свойства дедуктивных теорий
- •26. Формальные аксиоматические теории
- •27. Свойства выводимости
- •31.(38) Логические функции
- •34. Кванторы
- •39. Алгоритм Сортировка слиянием.
- •40. Алгоритм Пузырьковая сортировка.
- •41. Алгоритм Сортировка вставками.
- •42. Алгоритм Сортировка Шейкером.
- •43. Алгоритм Быстрая сортировка.
- •44. Алгоритм Сортировка подсчетом.
- •47. Логика высказываний.
- •48. Булева алгебра и основные логические тождества.
- •49. Пропозициональные буквы, связки и формы (формулы логики
- •50. Исчисление высказываний (теория l)
10. Интерпретация. Модель
Интерпретацию будем считать заданной, если:
1. Задано непустое множество M, называемое областью интерпретации.
2. Заданы следующие соответствия:
a) предикатным буквам поставлены в соответствие некоторые n - местные
предикаты (отношения) в M; niA
b) функциональным буквам поставлены в соответствие некоторые n -
аргументные функции, отображающие M nifn в M;
c) каждой предметной постоянной поставлен в соответствие некоторый
(фиксированный) элемент из M;
d) символам , ⇒, ∀x, ∃x поставлен в соответствие их обычный смысл.
3. Считается, что предметные переменные пробегают всё множество M.
Например, чтобы задать интерпретацию для формулы ∀x(x,y,b31A1A1), нужно
задать множество M - область интерпретации (область изменения
переменных x,y). Из этой области M будем брать некоторый элемент,
соответствующий предметной постоянной b1. Далее нужно задать 3-х
местный предикат на M, соответствующей предикатной букве . Так, можно
положить, что M=[0, ∞); предметной постоянной b31 поставить в соответствие
1, а (x,y,z) поставить в соответствие предикат x + y ≥ z. Тогда формула
∀x(x,y,b31A31A1) в заданной интерпретации запишется:
∀x(x + y ≥ 1)
и означает, что для любого x (x ∈ [0, ∞)) сумма x + у больше или равна 1.
Очевидно, что это отношение истинно при некоторых у (у ≥ 1) и ложно при
других значениях у (0≤у<1). Если предметной постоянной b1 поставить в
соответствие 0, а не 1, то утверждение ∀x(x +y ≥ 0) будет истинно при любом
значении свободной переменной у.
Легко видеть, что для той же формулы ∀x(x,y,b31A1) можно построить
бесчисленное множество других интерпретаций, выбирая различные
множества M, выбирая из M, каким-то образом элемент, соответствующий b1,
и задавая различным образом на M трехместный предикат. Так, можно за M
взять множество всех студентов Казани, за b1 студента Иванова, а (x,y,z)
поставить в соответствии предикат: «x и у учатся в той же группе, что и z».
Тогда исходная формула ∀x(x,y,b31A31A1) в этой интерпретации означает
утверждение: ∀x(x и у учатся в той же группе, что и Иванов). Это утверждение
является ложным при каждом у, ибо не может быть, чтобы любой x и
некоторый у учились в той же группе, что и Иванов.
При данной интерпретации всякая формула без свободных переменных
(замкнутая формула) представляет собой высказывание, которое истинно
либо ложно, а всякая формула со свободными переменными выражает
некоторое отношение на M, которое может быть истинно для одних значений
из M и ложно для других.
15
Формула называется выполнимой в данной интерпретации, если она
принимает значение И хотя бы для одной совокупности возможных значений
её свободных переменных (если они есть). Если формула не содержит
свободных переменных, то она называется выполнимой в том случае, если
принимает значение И в этой интерпретации.
Формула называется истинной в данной интерпретации, если она принимает
значение И для всех возможных значений её свободных переменных (если
они есть). Если же свободных переменных нет, то формула называется
истинной, когда она принимает значение И в этой интерпретации.
Формула называется ложной в данной интерпретации, если она принимает
значение Л для всех возможных значений её свободных переменных (если
они есть). Если же свободных переменных нет, то формула называется
ложной, когда она принимает значение Л в этой интерпретации. Очевидно,
что формула ложна в данной интерпретации тогда и только тогда, когда она
не выполнима в этой интерпретации. Так же ясно, что формула A выполнима
в данной интерпретации тогда и только тогда, когда она не является ложной в
этой интерпретации.
Данная интерпретация называется моделью для множества формул G, если
каждая формула из G истинна в этой интерпретации.
16