Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2021-03-18 | 111 |
5.00
из
|
Заказать работу |
Формально математическую систему можно охарактеризовать с помощью следующих основных компонентов:
Множество основных символов содержит символы для обозначения констант, операторов и т.д.
В соответствии с правилами образования из этих символов строятся утверждения, затем определяются примитивные утверждения, истинность которых принимается без доказательства (это аксиомы). Далее задаются правила, с помощью которых из справедливых утверждений можно выводить новые справедливые утверждения. Это и есть правила вывода.
Доказательство. Если нужно доказать, что некоторое утверждение в формальной системе истинно, то доказательство представляет собой последовательность утверждений, таких что:
(1) любое утверждение либо является аксиомой, либо его можно получить из одного
или более предыдущих утверждений с помощью правил вывода,
(2) последнее утверждение последовательности является утверждением, которое надо
доказать.
Утверждение, для которого существует доказательство, называется теоремой (Th) этой формальной системы.
Пример. Исчисление высказываний.
1. Алфавит: { (,),→,, а1 , а2 ,…},
2.1. Все переменные - а1,а2,…, являются утверждениями, т.е. все аi -утверждения (i=1,2,…).
2.2. Если А, В - утверждения, то А и (А→В)- тоже утверждения.
А – утверждение, В – утверждение =>
(А→В) – утверждения, А - утверждение
2.3. Никакой другой набор символов не является утверждением.
3.1. (А→(В→А));
3.2. ((А→(В→С))→((А→В)→(А→С)));
3.3. ((В→ А)→((В→А)→В));
Правилом вывода является “схема заключения” (modus ponens), т.е. из утверждений (А→В) и А можно вывести В: (А→В), А.
B
Понятие λ-исчисления.
Существует две точки зрения на понятие функции:
Функция представляется алгоритмом, который по заданному значению аргумента возвращает значение функции
Функция представляется графиком или множеством пар (аргумент - значение).
Определение:
λ-исчисление – формальнаябестиповая теория, рассматривающая функцию как правило (операционный взгляд).
Построение бестипового λ-исчисления.
мн-во мн-во
переменных констант
2. Правила построения объектов (термов):
2.1. Все переменные и константы – термы;
А - терм, В - терм => (АВ) - терм
А-терм, х- переменная, λ-абстракция => λх.А - терм
3. Никакой другой набор символов не является λ-термом.
Пример. ƒ(х)=х+1
ƒ3= ƒ(3)=3+1
ƒ: λх.х+1
ƒ3=((λх.х+1)3)=3+1.
Соглашение о скобках:
(АВ)→АВ
(((АВ)С)D) →((АВ)С)D→(АВ)СD→ABCD
Соглашение о λ-символах:
Несколько последовательных абстракций можно объединять одним символом λ:
λx. λy. A = λxy.A
3.Аксиомы λ- исчислений:
(α) λу.z= λυ.[υ/y]z (подстановка υ на место у в выражении z).
Связанные переменные в выражении можно переименовывать.
λх.х+1=(α) λу.у+1
(β) (λх.M)N=[N/x]M
(ρ) M=M
4.Правила вывода:
(μ) x=y→ ax=ay
(ν) x=y→ xa=ya
(ξ) a=b→ λx.a=λx.b
(τ) a=b, b=c→ a=c
(σ) a=b→ b=a
Постулаты λ - исчисления - все аксиомы и правила построения.
Примеры: х а @ b – не является λ-термом.
3
λх.у
λх.у→((λх.х)3)
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!