- •1.Логические исчисления 3
- •Логические исчисления
- •Логика высказываний
- •Понятие формальной теории
- •Исчисление высказываний (ив)
- •Теорема дедукции
- •Непротиворечивость и полнота исчисления высказываний
- •Методы проверки выводимости формул ив
- •X ├ (Xy)(Xz).
- •X, Xy├ Xz.
- •Понятие предиката
- •Логические эквивалентности с кванторами
- •Термы и формулы в исчислении предикатов
- •Аксиомы и правила вывода в исчислении предикатов
- •Теоремы об исчислении предикатов первого порядка
- •Метод резолюций для исчисления предикатов
- •Элементы теории алгоритмов и рекурсивных функций
- •Понятие алгоритма
- •Машина Тьюринга
- •X1 qi y1 ᅣ x2 qj y2
- •X1 qi y1ᅡx2 qj y2
- •Вычисление функций на машине Тьюринга
- •Алгоритмически неразрешимые задачи
- •Примитивно рекурсивные функции
- •Частично рекурсивные функции
- •Характеристики сложности алгоритмов
- •Классы сложности и
Понятие формальной теории
Хотя для проверки логических рассуждений можно использовать алгебру логики, сами рассуждения представляют собой цепочку утверждений, каждое из которых либо является исходной посылкой (постулатом, аксиомой, гипотезой), либо получается из предыдущих утверждений с помощью определённых правил - правил логического вывода. Эти правила вывода применяются к утверждениям формально, т.е., исходя только из их формы, структуры, а не содержания. Весь содержательный анализ происходит при формулировании аксиом.
Способ построения научной теории в виде системы аксиом (постулатов) и правил вывода, позволяющих формальным логическим путем получать утверждения (теоремы) данной теории, называется аксиоматическим методом.
Наиболее убедительным примером применения аксиоматического метода явился математический трактат "Начала" древнегреческого математика Евклида (ок. 300 г. до н.э.). По примеру Евклида нидерландский философ Бенедикт Спиноза применил аксиоматический метод в своём основном труде «Этика, доказанная в геометрическом порядке» (1675), а великий русский учёный Михаил Ломоносов аксиоматически изложил основы физической химии.
Более двух тысяч лет учёные старались выяснить, какими же правилами вывода пользуются люди в логически правильных рассуждениях. Крупные достижения были сделаны и древнегреческими философами (Аристотель), и средневековыми европейскими схоластами, и учёными-логиками конца 19 - начала 20 века.
При описании логических исчислений будем придерживаться аксиоматического метода, т.е. способа построения научной теории, при котором какие-то положения теории избираются в качестве исходных (аксиом), а все остальные выводятся из нее чисто логическим путем, посредством доказательств. Положения, доказываемые на основе аксиом, называются теоремами.
Чтобы задать формальную аксиоматическую теориюT, необходимо определить:
некоторое счётное множество символов (алфавит) – символов теории T (конечные последовательности символов теории T называются выражениями или словами теории T);
подмножество выражений теории T, называемых формулами;
подмножество формул теории T, называемых аксиомами;
конечное множество R1, R2, ..., Rm отношений между формулами, называемых правилами вывода.
Если формула A и формулы A1, A2, ..., Ai находятся в некотором отношении Rk, то A называется непосредственным следствием из формул A1, A2, ..., Ai, полученным по правилу Rk. Это обозначается так , при этом формулыA1, A2, ..., Ai называются посылками, формула A – заключением.
Выводом формулы A из формул F1, …,Fk в теории T называется всякая последовательность A1, A2, ..., Ai, …,An формул такая, что An=A и для любого i формула Ai есть либо аксиома теории T, либо одна из формул Fj, либо непосредственное следствие из ранее полученных формул. Если в теории T существует вывод формулы A из формул F1, …,Fk , то записывают это так F1, …,Fk ├T A, при этом формулы F1, …,Fk называются гипотезами вывода.
Если ├T A, то формула А называется теоремой теории T (т.е. выводима только из аксиом без гипотез). Вывод теоремы называется доказательством.