Математическая логика и теория алгоритмов

Введение Логика обычно понимается как наука о способах доказательств и опровержений. Математическая логика - это логика, развиваемая с помощью математических методов. Изучая методы доказательств и опровержений, логика интересу­ ется в первую очередь формой получения истинных выводов, а не содержанием посылок и заключений в том или ином рассужде­ нии. Рассмотрим, например, следующие два вывода: 1. Все люди смертны. Сократ - человек. Следовательно, Сократ - смертен. 2. Все котята любят играть. Мурка - котенок. Следовательно, Мурка любит играть. Оба эти вывода имеют одну и ту же форму: Все А суть 5 ; С есть А\ следовательно, С есть В. Эти выводы верны в силу своей формы, независимо от содержания и от того, истинны или лолсны взятые сами по себе посылки и заключения. Систематическая формализация и ка­ талогизация правильных способов рассуждений - одна из основных задач логики. Если при этом применяется математический аппарат и исследования посвящены в первую очередь изучению математиче­ ских рассуждений, то эта логика является математической логикой (формальной логикой). Данное определение не является строгим (точ­ ным) определением. Чтобы понять предмет и метод математической логики, лучше всего приняться за ее изучение. Математическая логика начала формироваться давно. Зароаде- ние ее идей и методов происходило в Древней Греции, Древней Индии и Древнем Китае примерно с VI в. до н. э. Уже в этот период 8