Введение
Учебные вопросы:
Понятия и определения математической логики.
Основные операции алгебры высказываний.
Законы и следствия булевой алгебры.
Заключение
Введение
Теоретической основой построения ЭВМ служат специальные математические дисциплины. Одной из них является алгебра логики, или булева алгебра (Дж. Буль - английский математик XIX в., основоположник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их проектирования и оптимизации.
1. Понятия и определения математической логики.
Логика - наука, изучающая законы и формы мышления; учение о способах рассуждений и доказательств.
Математическая логика (теоретическая логика, символическая логика) - раздел математики, изучающий доказательства и вопросы оснований математики. «Предмет современной математической логики разнообразен». Согласно определению П. С. Порецкого, «математическая логика есть логика по предмету, математика по методу». Согласно определению Н. И. Кондакова, «математическая логика - вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков)». Это определение соответствует определению С. К. Клини: математическая логика - это «логика, развиваемая с помощью математических методов». Также А. А. Марков определяет современную логику «точной наукой, применяющей математические методы». Все эти определения не противоречат, а дополняют друг друга.
Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном языке. Такие точные языки имеют две стороны: синтаксис и семантику. Синтаксисом называется совокупность правил построения объектов языка (обычно называемых формулами). Семантикой называется совокупность соглашений, описывающих наше понимание формул (или некоторых из них) и позволяющих считать одни формулы верными, а другие - нет.
Математическая логика изучает логические связи и отношения, лежащие в основе логического (дедуктивного) вывода , с использованием языка математики.
Законы мира, сущность предметов, общее в них мы познаем посредством абстрактного мышления. Основными формами абстрактного мышления являются понятия, суждения и умозаключения.
Понятие - форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов. Понятия в языке выражаются словами.
Объем понятия - множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия. Выделяют понятия общие и единичные.
Выделяют следующие отношения понятий по объему:
тождество или совпадение объемов, означающее, что объем одного понятия равен объему другого понятия;
подчинение или включение объемов: объем одного из понятий полностью включен в объем другого;
исключение объемов - случай, в котором нет ни одного признака, который бы находился в двух объемах;
пересечение или частичное совпадение объемов;
соподчинение объемов - случай, когда объемы двух понятий, исключающие друг друга, входят в объем третьего.
Суждение - это форма мышления, в которой что-либо утверждается или отрицается о предметах, признаках или их отношениях.
Умозаключение - форма мышления, посредством которой из одного или нескольких суждений, называемых посылками, мы по определенным правилам вывода получаем суждение-заключение.
Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только над числами, но и над другими математическими объектами.
Алгебра логики (алгебра высказываний, булева алгебра 1 ) - раздел математической логики, в котором изучаются логические операции над высказываниями. Чаще всего предполагается (т. н. бинарная или двоичная логика, в отличие от, например, троичной логики), что высказывания могут быть только истинными или ложными.
Примеры алгебр: алгебра натуральных чисел, алгебра рациональных чисел, алгебра многочленов, алгебра векторов, алгебра матриц, алгебра множеств и т.д. Объектами алгебры логики или булевой алгебры являются высказывания.
Высказывание - это любое предложение какого-либо языка (утверждение), содержание которого можно определить как истинное или ложное.
Всякое высказывание или истинно , или ложно ; быть одновременно и тем и другим оно не может.
В естественном языке высказывания выражаются повествовательными предложениями. Восклицательные и вопросительные предложения высказываниями не являются.
Высказывания могут выражаться с помощью математических, физических, химических и прочих знаков. Из двух числовых выражений можно составить высказывания, соединив их знаками равенства или неравенства.
Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.
Высказывание, состоящее из простых высказываний, называются составным (сложным).
Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
А = {Аристотель - основоположник логики},
В = {На яблонях растут бананы}.
Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: «Сумма углов треугольника равна 180 градусов» устанавливается геометрией, причем - в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского - ложным.
Истинному высказыванию ставится в соответствие 1, ложному - 0. Таким образом, А = 1, В = 0.
Алгебра логики отвлекается от смысловой содержательности высказываний. Ее интересует только один факт - истинно или ложно данное высказывание, что дает возможность определять истинность или ложность составных высказываний алгебраическими методами.
Основная идея математической логики - формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания - математические. Таким образом, математическая логика, по-существу, - наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство"". Действительно, ``доказательные"" (иначе говоря, дедуктивные) рассуждения - единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим"" процессом переписывания текста (формул). Такой процесс называют выводом. Говорят еще, что математическая логика оперирует только синтаксическими понятиями. Однако обычно всё же важно, как соотносятся рассуждения с действительностью (или нашими представлениями). Поэтому, надо всё же иметь в виду некоторый смысл формул и вывода. При этом используют термин семантика (синоном слова ``смысл"") и чётко разделяют синтаксис и семантику. Когда же действительно интересуются только синтаксисом, часто используют термин ``формальная система"". Мы будем использовать синоним этого термина - ``исчисление"" (используются ещё термины ``формальная теория"" и ``аксиоматика""). Объектом формальных систем являются строки текста (последовательности символов), с помощью которых записываются формулы.
Формальная система определена, если:
Задан алфавит (множество символов, используемых для построения формул).
Выделено множество формул, называемых аксиомами. Это - стартовые точки в выводах.
Задано множество правил вывода, которые позволяют из некоторой формулы (или множества формул) получать новую формулу.
Основные принципы операций
Отрицание
Отрицание логического высказывания -- логическое высказывание, принимающее значение "истинно", если исходное высказывание ложно, и наоборот. Это специальная логическая операция. В зависимости от местоположения различают внешнее и внутреннее отрицание, свойства и роли которых существенно различаются.
1. Внешнее отрицание (пропозициональное) служит для образования сложного высказывания из другого (не обязательно простого) высказывания. В нем утверждается отсутствие положения дел, описываемого в отрицаемом высказывании. Традиционно отрицательное высказывание считается истинным, если, и только если, отрицаемое высказывание ложно. В естественном языке отрицание обычно выражается оборотом «неверно, что», за которым следует отрицаемое высказывание.
В языках формальных теорий отрицание называется особая унарная пропозициональная связка, используемая для образования из одной формулы другой, более сложной. Для обозначений отрицание обычно используются символы «отрицание», «-» или «-- 1». В классической логике высказываний формула -А истинна тогда и только тогда, когда формула А ложна.
Однако в неклассической логике отрицание может не обладать всеми свойствами классического отрицания. В этой связи возникает вполне закономерный вопрос о минимальном наборе свойств, которому должна удовлетворять некоторая унарная операция, чтобы ее можно было считать отрицанием, а также о принципах классификации различных отрицаниях в неклассических формальных теориях (см.: Dunn J.M. and Hardegree G.M.Algebraic Methods in Philosophical Logic. Oxford, 2001).
Фактически указанное выше традиционное понимание внешнего (пропозиционального) отрицания может быть выражено через систему следующих требований: (I) Если А -- истинно (ложно), то не-А -- ложно (истинно); (II) Если не-А -- истинно (ложно), то А -- ложно (истинно). Формально требования (I) и (II) могут быть выражены через условие (1) А р--iB=>B (= --, А, называемое «конструктивная контрапозиция». Отрицание, удовлетворяющее условию (1), принято называть минимальным отрицанием. Однако оказывается, что условие (1) можно разложить на два более слабых условия: (2) А (= В=>-,В р-Аи(3)А(= -- 1 -- А, известных, соответственно, как «контрапозиция» и «введение двойного отрицания». В результате появляется возможность выявить подминимальное отрицание, удовлетворяющее условию (2), но не удовлетворяющее условию (3). Естественно сформулировать условие, обратное (3) и формализующее принцип «снятие двойного отрицания»: (4) --. - А = А. Минимальное отрицание (т.е. удовлетворяющее условию (1) или условиям (2) и (3) вместе), для которого выполняется условие (4), называется отрицание де Моргана. Минимальное отрицание, удовлетворяющее дополнительному свойству (5): Если А -- * В, то для любого С верно, что А р С («свойство абсурдности»), -- называется интуиционистским отрицанием. Можно сформулировать принцип (6), двойственный принципу абсурдности: Если В |=Аи--S р А, то для любого С верно, что С р А. Удовлетворяющее этому принципу отрицания. представляет собой разновидность отрицания в паранепротиворечивой логике. Наконец, отрицание де Моргана (свойства (2), (3), (4)), для которого выполняется (5) или (6), называется орто-отрицание Если в соответствующем исчислении принимается аксиома дистрибутивности для конъюнкции и дизъюнкции, то орто-отрицание называется отрицание Буля, или классическим отрицанием.
2. Внутреннее отрицание входит в состав простого высказывания. Различают отрицание в составе связки (отрицательная связка) и терминное отрицание.
Отрицание в составе связки выражается с помощью частицы «не», стоящей перед глаголом-связкой (если он имеется) или перед смысловым глаголом. Оно служит для выражения суждений об отсутствии каких-то отношений («Иван не знает Петра»), или для образования отрицательной предицирующей связки в составе категорических атрибутивных суждений.
Терминное отрицание используется для образования негативных терминов. Оно выражается через приставку «не» или близкие ей по смыслу («Все неспелые яблоки -- зеленые»).
Конъюнкция
Конъюнкция двух логических высказываний -- логическое высказывание, истинное только тогда, когда они одновременно истинны (от лат. conjunctio -- союз, связь), в широком смысле -- сложное высказывание, образованное с помощью союза «и». В принципе можно говорить о конъюнкции бесконечного числа высказываний (например, о конъюнкции всех истинных предложений математики). В логике конъюнкцией называют логическую связку (операцию, функцию; обозначают: &,); образованное с её помощью сложное высказывание истинно только при условии одинаковой истинности его составляющих. В классической логике высказываний конъюнкция вместе с отрицанием составляют функционально-полную систему пропозициональных связок. Это означает, что через них можно определить любую другую пропозициональную связку. Одним из свойств конъюнкции является коммутативность (т. е. эквивалентность А & В и В & А). Однако, иногда, говорят о некоммутативной, т. е. упорядоченной конъюнкции (примером высказывания с такой конъюнкции может служить: «Ямщик свистнул, и лошади поскакали»).
Дизъюнкция
Дизъюнкция двух логических высказываний -- логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно
(от лат. disjunctio -- разобщение, обособление), в широком смысле -- сложное высказывание, образованное из двух или более предложений с помощью союза «или», выражающего альтернативность, или выбор.
В символической логике дизъюнкцией называют логическую связку (операцию, функцию), образующую из предложений А и В сложное высказывание, обозначаемое обычно как А V В, которое является истинным при истинности по крайней мере одного из двух дизъюнктивных членов: А или В.
В классической логике дизъюнкция вместе с отрицанием образует функционально-полную систему пропозициональных связок, что позволяет определить через них другие пропозициональные связки.
Традиционно принято отличать рассмотренную (нестрогую) дизъюнкцию от строгой (разделительной) дизъюнкции, для которой характерно то, что соответствующее высказывание истинно при условии, когда истинен один и только один дизъюнктивный член.
Импликация
Импликация двух логических высказываний A и B -- логическое высказывание, ложное только тогда, когда B ложно, а A истинно (от лат. implicatio -- сплетение, от implico -- тесно связываю) -- логическая связка, соответствующая грамматической конструкции «если.., то...», с помощью которой из двух простых высказываний образуется сложное высказывание. В импликативном высказывании различают антецедент (основание) -- высказывание, идущее после слова «если», и консеквент (следствие) -- высказывание, идущее за словом «то». Импликативное высказывание представляет в языке логики условное высказывание обычного языка. Последнее играет особую роль, как в повседневных, так и в научных рассуждениях, основной его функцией является обоснование одного путем ссылки на нечто другое.
Выражаемую условным высказыванием связь обосновывающего и обосновываемого трудно охарактеризовать в общем виде, и только иногда природа ее относительно ясна. Эта связь может быть, в частности, связью логического следования, имеющей место между посылками и заключением правильного умозаключения («Если все живые многоклеточные существа смертны и медуза является таким существом, то она смертна»). Связь может представлять собой закон природы («Если тело подвергнуть трению, оно начнет нагреваться») или причинную связь («Если Луна в новолуние находится в узле своей орбиты, наступает солнечное затмение»). Рассматриваемая связь может иметь также характер социальной закономерности, правила, традиции и т.п. («Если меняется экономика, меняется и политика», «Если обещание дано, оно должно быть выполнено»).
Связь, выражаемая условным высказыванием, предполагает, что консеквент с определенной необходимостью «вытекает» из антецедента и что есть некоторый общий закон, сумев сформулировать который, мы можем логически вывести консеквент из антецедента. Например, условное высказывание «Если висмут-- металл, он пластичен» предполагает общий закон «Все металлы пластичны», делающий консеквент данного высказывания логическим следствием его антецедента.
И в обычном языке, и в языке науки условное высказывание, кроме функции обоснования, может выполнять также целый ряд других задач. Оно может формулировать условие, не связанное с к.-л. подразумеваемым общим законом или правилом («Если захочу, разрежу свой плащ»), фиксировать какую-то последовательность («Если прошлое лето было сухим, то в этом году оно дождливое»), выражать в своеобразной форме неверие («Если вы решите задачу, я докажу великую теорему Ферма»), противопоставление («Если в огороде растет капуста, то в саду растет яблоня») и т.п. Многочисленность и разнородность функций условного высказывания существенно затрудняет его анализ.
В логических системах абстрагируются от особенностей обычного употребления условного высказывания, что ведет к различным импликациям. Наиболее известны из них импликация материальная, строгая импликация и релевантная (уместная) импликация.
Материальная импликация -- одна из основных связок классической логики. Определяется она таким образом: импликация ложна только в случае истинности антецедента и ложности консеквента и истинна во всех остальных случаях. Условное высказывание «Если А, то В» предполагает некоторую реальную связь между тем, о чем говорится в А и В; выражение «А материально имплицирует В» такой связи не предполагает.
Строгая импликация определяется через модальное понятие (логической) невозможности: «А строго имплицирует В» означает «Невозможно, чтобы А было истинно, а В ложно».
В релевантной логике импликация понимается как условный союз в его обычном смысле. В случае релевантной импликация нельзя сказать, что истинное высказывание может быть обосновано путем ссылки на любое высказывание и что с помощью ложного высказывания можно обосновать какое угодно высказывание.
Эквивалентность
Эквивалентность двух логических высказываний -- логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны (от позднелат. equivalens - равноценный) - родовое наименование всевозможных отношений типа равенства, т.е. рефлексивных, симметричных и транзитивных бинарных отношений. Примеры: эквиполентность (совпадение по смыслу, значению, содержанию, выразительным и (или) дедуктивным возможностям между понятиями, концепциями, науч. теориями или формализующими их формальными системами) конгруентность или подобие геометрия, фигур; изоморфизм; равномощность множеств и другие эквивалентность каких-либо объектов означает их равенство (тождество) в каком-либо отношении
(например, изоморфные множества неразличимы по своей "структуре", если под "структурой" понимать совокупность тех их свойств, относительно которых эти множества изоморфны). Всякое отношение эквивалентности порождает разбиение множества, на котором оно определено, на попарно не пересекающиеся "классы эквивалентности " в один класс относят при этом эквивалентные друг другу элементы данного множества.
Рассмотрение классов эквивалентности в качестве новых объектов представляет собой один из основных способов порождения (введения) абстрактных понятий в логико-математических (и вообще естественно-научных) теориях. Так, считая эквивалентными дроби a/b и c/d с целыми числителями и знаменателями, если ad=bc, вводят в рассмотрение рациональные числа как классы эквивалентных дробей; считая эквивалентными множества, между которыми можно установить взаимно-однозначное соответствие, вводят понятие мощности (кардинального числа) множества (как класс эквивалентных между собой множеств); считая эквивалентными два куска вещества, вступающие в равных условиях в одинаковые химических реакции, приходят к абстрактному понятию химического состава и т.п.
Термин " эквивалентность" употребляют часто не (только) как родовой, а как синоним некоторых из его частных значений ("эквивалентность теорий" вместо "эквивалентность", " эквивалентность множеств" вместо "равномощность", " эквивалентность слов" в абстрактной алгебре вместо "тождество" и т.п.).
Кванторное высказывание
Кванторное с квантором всеобщности.
Кванторное логическое высказывание с квантором всеобщности ("xA(x)) -- логическое высказывание, истинное только тогда, когда для каждого объекта x из заданной совокупности высказывание A(x) истинно.
Кванторное с квантором существования.
Кванторное логическое высказывание с квантором существования ($xA(x)) -- логическое высказывание, истинное только тогда, когда в заданной совокупности существует объект x, такой, что высказывание A(x) истинно.
Структура математической логики
Раздел «математическая логика» состоит из трёх частей: по неформальному аксиоматическому методу, по логике высказываний и по логике предикатов (первого порядка). Аксиоматический метод построения - первый шаг на пути к формализации теории. Большинство задач, рассматриваемых в математической логике, состоит в доказательстве некоторых утверждений. Математическая логика имеет много разветвлений. Она применяет табличное построение логики высказываний, использует специальный язык символов и формулы логики высказываний.
Неформальный аксиоматический метод
Аксиоматический метод, не фиксирующий жестко применяемого языка и тем самым не фиксирующий границы содержательного понимания предмета, но требующий аксиоматического определения всех специальных для данного предмета исследования понятий. Этот термин не имеет общепринятого толкования.
История развития аксиоматического метода характеризуется все возрастающей степенью формализации. Неформальный аксиоматический метод - определенная ступень в этом процессе.
Первоначальное, данное Евклидом, аксиоматическое построение геометрии отличалось дедуктивным характером изложения, при котором в основу клались определения (пояснения) и аксиомы (очевидные утверждения). Из них, опираясь на здравый смысл и очевидность, выводились следствия. При этом в выводе неявно иногда использовались не зафиксированные в аксиомах предположения геометрия, характера, особенно относящиеся к движению в пространстве и взаимному расположению прямых и точек. Впоследствии были выявлены геометрия, понятия и регламентирующие их употребление аксиомы, неявно используемые Евклидом и его последователями. При этом возникал вопрос: действительно ли выявлены все аксиомы. Руководящий принцип для решения этого вопроса сформулировал Д. Гильберт (D. Hilbert): "Следует добиться того, чтобы с равным успехом можно было говорить вместо точек, прямых и плоскостей о столах, стульях и пивных кружках". Если доказательство не теряет доказательной силы после такой замены, то действительно все используемые в этом доказательстве специальные предположения зафиксированы в аксиомах. Достигаемая при таком подходе степень формализации представляет собой уровень формализации, характерный для неформального аксиоматического метода. Эталоном здесь может служить классический труд Д. Гильберта "Основания геометрии" .
Неформальный аксиоматический метод применяется не только для придания определенной завершенности аксиоматически излагаемой конкретной теории. Он представляет собой действенное орудие математического исследования. Поскольку при изучении системы объектов по этому методу не используется их специфика, или "природа", то доказанные утверждения переносятся на любую систему объектов, удовлетворяющую рассматриваемым аксиомам. Согласно неформальному аксиоматическому методу, аксиомы - это неявные определения первоначальных понятий (а не очевидные истины). Что представляют собой изучаемые объекты - неважно. Все, что нужно о них знать, сформулировано в аксиомах. Предметом изучения аксиоматической теории служит любая ее интерпретация.
Неформальный аксиоматический метод, кроме непременного аксиоматического определения всех специальных понятий, имеет и другую характерную особенность. Это свободное, неконтролируемое аксиомами, основанное на содержательном понимании использование идей и понятий, которые можно применить к любой мыслимой интерпретации, независимо от ее содержания. В частности, широко используются теоретико-множественные и логического понятия и принципы, а также понятия, связанные с идеей счета, и др. Проникновение в аксиоматический метод рассуждений, основанных на содержательном понимании и здравом смысле, а не на аксиомах, объясняется не фиксированностью языка, на котором формулируются и доказываются свойства аксиоматически заданной системы объектов. Фиксирование языка ведет к понятию формальной аксиоматической системы и создает материальную основу для выявления и четкого описания допустимых логических принципов, для контролируемого употребления теоретико-множественных и других общих или не специальных для исследуемой области понятий. Если в языке нет средств (слов) для передачи теоретико-множественных понятий, то этим отсеиваются все доказательства, основанные на использовании таких средств. Если в языке есть средства для выражения некоторых теоретико-множественных понятий, то их применение в доказательствах можно ограничить определенными правилами или аксиомами.
Фиксируя различным образом язык, получают различные теории основного объекта рассмотрения. Например, рассматривая язык узкого исчисления предикатов для теории групп, получают элементарную теорию групп, в которой нельзя сформулировать какого-либо утверждения о подгруппах. Если перейти к языку исчисления предикатов второй ступени, то появляется возможность рассматривать свойства, в которых фигурирует понятие подгруппы. Формализацией неформальный аксиоматический метод в теории групп служит переход к языку системы Цермело - Френкеля с ее аксиоматикой.
Аксиоматический метод
Аксиоматический метод способ построения научной теории, при котором в её основу кладутся некоторые исходные положения (суждения)-- аксиомы, или постулаты, из которых все остальные утверждения этой теории должны выводиться чисто логическим путём, посредством доказательств. Построение науки на основе аксиоматический метод обычно называется дедуктивным. Все понятия дедуктивной теории (кроме фиксированного числа первоначальных) вводятся посредством определений, выражающих их через ранее введённые понятия. В той или иной мере дедуктивные доказательства, характерные для аксиоматический метод, применяются во многих науках, однако главная область его приложения -- математика, логика, а также некоторые разделы физики.
Идея аксиоматический метод впервые была высказана в связи с построением геометрии в Древней Греции (Пифагор, Платон, Аристотель, Евклид). Для современной стадии развития аксиоматический метод характерна выдвинутая Гильбертом концепция формального аксиоматический метод, которая ставит задачу точного описания логических средств вывода теорем из аксиом. Основная идея Гильберта -- полная формализация языка науки, при которой её суждения рассматриваются как последовательности знаков (формулы), приобретающие смысл лишь при некоторой конкретной интерпретации. Для вывода теорем из аксиом(и вообще одних формул из других) формулируются спец. правила вывода. Доказательство в такой теории (исчислении, или формальной системе) -- это некоторая последовательность формул, каждая из которых либо есть аксиома, либо получается из предыдущих формул последовательности по какому-либо правилу вывода. В отличие от таких формальных доказательств, свойства самой формальной системы в целом изучаются содержат. средствами метатеории. Основные требования, предъявляемые к аксиоматическим формальным системам,-- непротиворечивость, полнота, независимость аксиом. Гильбертовская программа, предполагавшая возможность доказать непротиворечивость и полноту всей классической математики, в целом оказалась невыполнимой. В 1931 Гёделъ доказал невозможность полной аксиоматизации достаточно развитых научных теорий (напр., арифметики натуральных чисел), что свидетельствовало об ограниченности аксиоматического метода. Основные принципы аксиоматические методы были подвергнуты критике сторонниками интуиционизма и конструктивного направления.
Математическая логика, как и классическая логика, исследует процессы умозаключений и позволяет из истинности одних суждений делать выводы об истинности или ложности других, независимо от их конкретного содержания. Использование в логике математических методов (алгебраизация логики и построение логических исчислений) дало начало развитию новой области математики, называемой «Математической логикой». Основная задача математической логики – формализация знаний и рассуждений. Математика является наукой, в которой все утверждения доказываются с помощью умозаключений, поэтому математическая логика, по существу, – наука о математике.
Математическая логика дала средства для построения логических теорий и вычислительный аппарат для решения задач. Математическая логика и теория алгоритмов нашли широкое применение в различных областях научных исследований и техники (например, в теории автоматов, в лингвистике, в теории релейно-контактных схем, в экономических исследованиях, в вычислительной технике, в информационных системах и др.). Основные понятия математической логики лежат в основе таких ее приложений, как базы данных, экспертные системы, системы логического программирования. Эти же понятия становятся методологической основой описания анализа и моделирования автоматизированных интегрированных производств.
Вопросы, исследуемые математической логикой, могут рассматриваться как средствами семантической (смысловой) теории, в основе которой лежит понятие алгебры, так и формально-аксиоматической (синтаксической) теории, базирующейся на понятии логического исчисления. В данном курсе рассматриваются оба этих подхода, начав с алгебры высказываний, которая затем обобщается алгеброй предикатов, и обе они служат пониманию построения логических исчислений и их частных случаев: исчисления высказываний и исчисления предикатов.
Раздел I. Алгебра высказываний
Алгебру высказываний можно рассматривать как переложение на другой (алгебраический) язык результатов, изученных в разделе «Булевы функции», использующем функциональный язык. При функциональном подходе каждой из логических операций и формул сопоставляется определённая двузначная функция. При алгебраическом подходе логические операции интерпретируют как алгебраические, действующие на множестве двух элементов.
1. Высказывания и операции над ними. Формулы
Высказыванием называется всякое утверждение, о котором можно вполне определенно и объективно сказать истинно оно или ложно.
Например, утверждение "2 > 0" является высказыванием и оно истинно, а утверждение "2 < 0" - ложно, утверждение "x 2 + y 2 = z 2 " высказыванием не является, так как оно может быть, как истинным, так и ложным при различных значениях переменных x, y, z. Высказывание полностью определяется своим истинностным значением. Условимся, значение истинности высказывания обозначать 1, если высказывание истинно, и 0, если высказывание ложно, что в точности соответствует значениям переменных булевых функций.
Различают высказывания простые и сложные, высказывание называется простым, если никакая его часть не является высказыванием. Простые высказывания будем обозначать начальными заглавными буквами латинского алфавита A, B, C или A 1 , A 2 , . . .. Сложные высказывания характеризуются тем, что образованы из нескольких простых высказываний с помощью логических операций, т.е. являются формулами алгебры высказываний.
Напомним, что алгебраической структурой или алгеброй называется структура, образованная некоторым множеством вместе с введенными на нём операциями. Определим алгебру высказываний.
Обозначим через B = {0, 1} – множество высказываний. Определим операции на множестве B .
Отрицанием высказывания A называется высказывание, которое принимает значение истина, если A ложно, и наоборот. Отрицание обозначается (А) и является унарной операцией.
Пусть А и В - некоторые высказывания, введем бинарные операции над ними.
Конъюнкцией
высказываний A
и B
называется высказывание, которое
принимает значение истина тогда и только
тогда, когда истинны оба высказывания
A
и B.
Обозначается конъюнкция - A
B
(АВ).
Дизъюнкцией
высказываний A
и B
называется высказывание, которое
принимает значение истина, если истинно
хотя бы одно из высказываний A или B.
Обозначается дизъюнкция - A
B.
Импликацией высказываний A и B называется высказывание, которое принимает значение ложь тогда и только тогда, когда A истинно, а B ложно. Обозначается АВ.
Эквиваленцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда высказывания A и B имеют одинаковые значения. Обозначение операции - АВ (АВ).
Логические операции определяются, также, с помощью таблиц, называемых таблицами истинности . Приведем сводную таблицу истинности для всех введенных логических операций.
Пропозициональной (высказывательной) переменной называется переменная, значениями которой являются простые высказывания. Обозначим высказывательные переменные через X 1 , X 2 , . . . , X n .
Понятие формулы алгебры высказываний вводится по индукции. Формулами алгебры высказываний являются:
1) логические константы 0 и 1;
2) пропозициональные переменные;
3) если А и В – формулы, то каждое из выражений (А) , (А) (В ), (А) (В ), (А) (В ), (А) ~ (В ) есть формула;
4) других формул, кроме построенных по пп. 1) - 3), нет.
Обозначим через M – множество всех формул алгебры высказываний, M является замкнутым относительно логических операций.
Для формулы
построенной по п. 3 формулы A
и B
называются подформулами. Число скобок
в формуле можно сократить, Порядок
выполнения операций в формуле определяется
их приоритетом. Список логических
операций в порядке убывания приоритета:
~. Изменение порядка выполнения операций,
как и в алгебраических операциях,
производится с помощью круглых скобок.
Пусть U – формула над высказывательными переменными X 1 , X 2 , . . . , X n , обозначается U (X 1 , X 2 , . . . , X n ). Набор конкретных значений высказывательных переменных X 1 , X 2 , . . . , X n называется интерпретацией формулы U и обозначаетсяI (U ).
Формула называется выполнимой , если существует такой набор значений переменных, при которых эта формула принимает значение 1 (существует интерпритация I (U ), на которой формула истинна).
Формула называется опровержимой , если существует такой набор значений переменных, при которых эта формула принимает значение 0 (существует интерпритация I (U ), на которой формула ложна).
Формула называется тождественно истинной (ТИ-формулой) или тавтологией , если эта формула принимает значение 1 при всех наборах значений переменных (формула истинна на всех интерпретациях).
Формула называется тождественно ложной (ТЛ-формулой) или противоречием , если эта формула принимает значение 0 при всех наборах значений переменных (формула ложна на всех интерпретациях).
Формулы А и В называются эквивалентными (обозначается А В ), если при любых значениях высказывательных переменных значение формулы А совпадает со значением формулы В .
Задачи определения эквивалентности, выполнимости, опровержимости, тождественной истинности и ложности формул могут решаться с помощью построения таблиц истинности, однако существуют менее громоздкие способы решения этих задач.
Одно из названий современной логики, пришедшей во втор. пол. 19 нач. 20 в. на смену традиционной логике. В качестве др. названия современного этапа в развитии науки логики используется также термин символическая логика. Определение… … Философская энциклопедия
математическая логика - ЛОГИКА СИМВОЛИЧЕСКАЯ, математическая логика, теоретическая логика область логики, в которой логические выводы исследуются посредством логических исчислений на основе строгого символического языка. Термин «Л. с.» был, по видимому, впервые… … Энциклопедия эпистемологии и философии науки
МАТЕМАТИЧЕСКАЯ ЛОГИКА - Ее еще называют символической логикой. М. л. это та же самая Аристотелева силлогистическая логика, но только громоздкие словесные выводы заменены в ней математической символикой. Этим достигается, во первых, краткость, во вторых, ясность, в… … Энциклопедия культурологии
МАТЕМАТИЧЕСКАЯ ЛОГИКА - МАТЕМАТИЧЕСКАЯ логика, дедуктивная логика, использующая математические методы исследования способов рассуждений (выводов); математическая теория дедуктивных способов рассуждений … Современная энциклопедия
МАТЕМАТИЧЕСКАЯ ЛОГИКА - дедуктивная логика, включающая математические методы исследования способов рассуждений (выводов); математическая теория дедуктивных способов рассуждений. Математической логикой называют также логику, которой пользуются в математике … Большой Энциклопедический словарь
МАТЕМАТИЧЕСКАЯ ЛОГИКА - (символическая логика), аналитический раздел логики, результат применения математических методов к проблемам классической логики. Рассматривает понятия, которые могут быть истинными или ложными, связь между понятиями и оперирование ими, включая… … Научно-технический энциклопедический словарь
МАТЕМАТИЧЕСКАЯ ЛОГИКА - один из ведущих разделов современной логики и математики. Сформировался в 19 20 ст. как реализация идеи о возможности записать все исходные допущения на языке знаков, аналогичных математическим и тем самым заменить рассуждения вычислениями.… … Новейший философский словарь
математическая логика - сущ., кол во синонимов: 1 логистика (9) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов
математическая логика - — Тематики электросвязь, основные понятия EN mathematical logic … Справочник технического переводчика
МАТЕМАТИЧЕСКАЯ ЛОГИКА - теоретическая логика, символическая логика, раздел математики, посвященный изучению математич. доказательств и вопросов оснований математики. Исторический очерк. Идея построения универсального языка для всей математики и формализации на базе… … Математическая энциклопедия
Книги
- Математическая логика , Ершов Юрий Леонидович, Палютин Евгений Андреевич. В книге изложены основные классические исчисления математической логики: исчисление высказываний и исчисление предикатов; имеется краткое изложение основных понятий теории множеств и теории… Купить за 1447 грн (только Украина)
- Математическая логика , Ершов Ю.Л.. В книге изложены основные классические исчисления математической логики: исчисление высказываний и исчисление предикатов; имеется краткое изложение основных понятий теории множеств и теории…
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»
Факультет физико-математических и компьютерных наук
Кафедра математики
Контрольная работа на тему:
«История развития математической логики»
Выполнила:
Студентка 2 курса
группы МФ-2
Понамарева Виктория Сергеевна
Научный руководитель:
к. ф.-м. н., доцент
Ершова Александра Алексеевна
Липецк, 2014
Введение
§1. История возникновения математической логики
§2. Применение математической логики
§3. Математическая логика в технике
§4. Математическая логика в криптографии
§5. Математическая логика в программировании
Заключение
Список используемой литературы
математическое обозначение криптография логика программирование
Введение
Логика <#"center">§1. История возникновения математической логики
Математическая логика тесно связана с логикой и обязана ей своим возникновением. Основы логики, науки о законах и формах человеческого мышления (отсюда одно из ее названий - формальная логика), были заложены величайшим древнегреческим философом Аристотелем (384-322 гг. до н. э.), который в своих трактатах обстоятельно исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления, в том числе законы противоречия и исключения третьего. Вклад Аристотеля в логику весьма велик, недаром другое ее название - Аристотелева логика. Еще сам Аристотель заметил, что между созданной им наукой и математикой (тогда она именовалась арифметикой) много общего. Он пытался соединить две эти науки, а именно свести размышление, или, вернее, умозаключение, к вычислению на основании исходных положений. В одном из своих трактатов Аристотель вплотную приблизился к одному из разделов математической логики - теории доказательств.
В дальнейшем многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646 - 1716), указавший пути для перевода логики «из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно» . Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав. При этом в своих работах Лейбниц затрагивал и двоичную систему счисления.
Следует отметить, что идея использования двух символов для кодирования информации очень стара. Австралийские аборигены считали двойками, некоторые племена охотников-сборщиков Новой Гвинеи и Южной Америки тоже пользовались двоичной системой счета. В некоторых африканских племенах передают сообщения с помощью барабанов в виде комбинаций звонких и глухих ударов. Знакомый всем пример двухсимвольного кодирования - азбука Морзе, где буквы алфавита представлены определенными сочетаниями точек и тире.
После Лейбница исследования в этой области вели многие выдающиеся ученые, однако настоящий успех пришел здесь к английскому математику-самоучке Джорджу Булю (1815-1864), целеустремленность которого не знала границ. Материальное положение родителей Джорджа (отец которого был сапожным мастером) позволило ему окончить лишь начальную школу для бедняков. Спустя какое-то время Буль, сменив несколько профессий, открыл маленькую школу, где сам преподавал. Он много времени уделял самообразованию и вскоре увлекся идеями символической логики. В 1847 году Буль опубликовал статью «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений», а в 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей».
Буль изобрел своеобразную алгебру - систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ).
Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в XX столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.
Отдельные положения работ Буля в той или иной мере затрагивались и до, и после него другими математиками и логиками. Однако сегодня в данной области именно труды Джорджа Буля причисляются к математической классике, а сам он по праву считается основателем математической логики и тем более важнейших ее разделов - алгебры логики (булевой алгебры) и алгебры высказываний.
Большой вклад в развитие логики внесли и русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947).
В XX веке огромную роль в развитии математической логики сыграл Д. Гильберт (1862-1943), предложивший программу формализации математики, связанную с разработкой оснований самой математики. Наконец, в последние десятилетия XX века бурное развитие математической логики было обусловлено развитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К. Клини, А. Черч, А.А Марков, П.С. Новиков, Гегель и многие другие).
Гегель (1770-1831) весьма иронично отзывался о законе противоречия и законе исключенного третьего. Последний он представлял, в частности, в такой форме: "Дух является зеленым или не является зеленым", и задавал "каверзный" вопрос: какое из этих двух утверждений истинно? Ответ на этот вопрос не представляет, однако, труда. Ни одно из двух утверждений: "Дух зеленый" и "Дух не зеленый" не является истинным, поскольку оба они бессмысленны. Закон исключенного третьего приложим только к осмысленным высказываниям. Только они могут быть истинными или ложными. Бессмысленное же не истинно и не ложно. Гегелевская критика логических законов опиралась, как это нередко бывает, на придание им того смысла, которого у них нет, и приписывание им тех функций, к которым они не имеют отношения. Случай с критикой закона исключенного третьего - один из примеров такого подхода. Критика закона исключенного третьего (Л.Бауэр) привела к созданию нового направления в логике - интуиционистской логики. В последней не принимается этот закон и отбрасываются все те способы рассуждения, которые с ним связаны. Среди отброшенных, например, оказывается доказательство путем приведения к противоречию, или абсурду.
Обращаю внимание на суть любой критики законов формальной логики: все сторонники концепции "расширения" формальной логики сдвигают центр тяжести логических исследований с изучения правильных способов рассуждения на разработку каких-либо конкретных проблем: теории познания, причинности, индукции и т.д. В логику вводятся темы, интересные и важные сами по себе, но не имеющие отношения к собственно формальной логике, как к набору приемов правильного мышления. Закон исключенного третьего, не рассматривая самих противоречий, запрещает признавать одновременно истинным или одновременно ложным два противоречащих друг другу суждения. В этом и состоит его смысл.
Вывод: нельзя уклоняться от признания истинным одного из двух противоречащих друг другу высказывай и искать нечто третье между ними.
Результат применения: достигается однозначность логического мышления.
Четвертый закон - закон достаточного основания
Формулировка: всякая истинная мысль имеет достаточное основание.
Комментарий: Этот закон фактически заявляет то, что все мысли которые можно объяснить, считаются истинными, а те которые объяснить нельзя - ложными. В логике высказываний этот закон формулы не имеет, так как он имеет содержательный характер. На этом стоит остановиться несколько подробней:
Достаточным, т. е. действительным, невымышленным основанием наших мыслей может являться индивидуальная практика. Действительно, истинность некоторых суждений подтверждается путем их непосредственного сопоставления с фактами действительности (Пример: "[Истинно, что]Идет дождь", "[Является ложью то, что]Я был в Акапулько"). Но личный опыт ограничен. Поэтому в реальной деятельности всегда приходится опираться на опыт других людей. Благодаря развитию научных знаний субъект использует в качестве оснований своих мыслей опыт предшественников, закрепленный в законах и аксиомах науки, в принципах и положениях, существующих в любой области человеческой деятельности. Для подтверждения какого-либо частного случая нет необходимости обращаться к его практической проверке, обосновывать его при помощи личного опыта. Если, например, мне известен закон Архимеда, то мне совсем не обязательно искать ванну с водой, чтобы, поместив туда предмет, выяснить, сколько он потерял в весе. Закон Архимеда будет достаточным основанием для подтверждения этого частного случая.
Целью науки является не только добывание знания, но и его передача. Именно поэтому недопустимы никакие логические огрехи в формальном представлении уже добытого знания. Таким образом - знание должно быть логически контролируемым. Именно это оптимально для его сохранения, передачи и развития. И именно поэтому научное знание, как совокупность уже доказанных логических предложений, может служить основанием для последующих доказательных рассуждений.
Закон достаточного основания фактически сводится к следующему требованию: "всякое суждение, прежде чем быть принятым за истину, должно быть обосновано". Таким образом из этого закона вытекает, что при правильном рассуждении ничто не должно приниматься просто так, на веру. В каждом случае каждого утверждения следует указывать основания, в силу которых оно считается истинным. Как видим - закон достаточного основания изначально выступает, как методологический принцип, обеспечивающий способность мышления поставлять основания к последующим рассуждениям. Ведь все, что уже корректно доказано, можно положить в основу последующим доказательствам.
Вывод: достаточным основанием какой либо мысли может быть любая другая, уже проверенная и признанная истинной мысль, из которой вытекает истинность рассматриваемой мысли.
Результат применения: закон обеспечивает обоснованность мышления. Во всех случаях, когда мы утверждаем что-либо, мы обязаны доказать свою правоту, т.е. привести достаточные основания, подтверждающие истинность наших мыслей.
§2. Применение математической логики
Объединение математико-логической установки с иными математическими подходами, прежде всего с вероятностно-статистическими идеями и методами - на фоне глубокого интереса к вычислительным приборам, - было во многом определяющим в формировании замысла кибернетики, как комплексного научного направления, имеющего своим предметом процессы.
В ряде случаев используется технический аппарат математической логики (синтез релейно-контактных схем); сверх того, что особенно важно, идеи математической логики это, конечно же, в теории алгоритмов, но также и всей науки в целом и свойственный ей стиль мышления оказали и продолжают оказывать очень большое влияние на те своеобразные области деятельности, содержанием которых является автоматическая переработка информации (информатика), использование в криптографии и автоматизация процессов управления (кибернетика).
Информатика - это наука, которая изучает компьютер, а также взаимодействие компьютера с человеком.
Строительство логических машин - интересная глава истории логики и кибернетики. В ней запечатлены первые проекты создания искусственного разума и первые споры о возможности этого. Идея логических машин появилась в 13 веке у испанского схоластика Раймунда Луллия, рассматривалась затем Лейбницем и получило новое развитие в 19 веке, после возникновения математической логики. В 1870 году английский философ и экономист Вильям Стэнли Джевонс построил в Манчестере логическое пианино, которое извлекало из алгебраически записанных посылок следствия, выделяя допустимые комбинации терминов. Это называют также разложением высказываний на конституанты. Важно отметить возможность практического применения логической машины для решения сложных логических задач.
Современные универсальные вычислительные машины являются вместе с тем логическими машинами. Именно введение логических операций сделало их такими гибкими; оно же позволяет им моделировать рассуждения. Таким образом, арифметическая ветвь разумных автоматов соединились с логической. В 20-е годы, однако, формальная логика представлялась слишком абстрактной о метафизической для приложения к жизни. Между тем уже тогда можно было предвидеть внедрение логических исчислений в технику.
Математическая логика облегчает механизацию умственного труда. Нынешние машины выполняют гораздо более сложные логические операции, нежели их скромные прототипы начала века.
Проблема искусственного разума сложна и многогранна. Вероятно, не ошибёмся, если скажем, что окончательные границы механизации мысли можно установить лишь экспериментальным путём. Заметим ещё, что в современной кибернетики обсуждается возможность моделирования не только формальных, но и содержательных мыслительных процессов.
§3. Математическая логика в технике
Роль логической обработки бинарных данных на современном этапе развития вычислительной техники существенно возросла. Это связано, в первую очередь, с созданием технически систем. реализующих в том или ином виде технологии получения и накопления знаний, моделированием отдельных интеллектуальных функций человека. Ядром таких систем являются мощные ЭВМ и вычислительные комплексы. Кроме того, существует большой класс прикладных задач, которые можно свести к решению логических задач, например, обработка и синтез изображений, транспортные задачи. Требуемая производительность вычислительных средств достигается путем распараллеливания и конвейеризации вычислительных процессов. Это реализуется, как правило, на основе сверхбольших интегральных, схем (СБИС). Однако технология СБИС и их структура предъявляет ряд специфических требований к алгоритмам, а именно: регулярность, параллельно - поточная организация вычислений, сверхлинейная операционная сложность (многократное использование каждого элемента входных данных), локальность связей вычислений, двумерность пространства реализации вычислений. Эти требования обусловливают необходимость решения проблемы эффективного погружения алгоритма в вычислительную среду, или, как еще принято говорить, - отображение алгоритма в архитектуру вычислительных средств. В настоящее время доказана ошибочность ранее широко распространенных взглядов, состоящих в том, что переход на параллельно -конвейерные архитектуры ЭВМ потребуют лишь небольшой модификации известных алгоритмов. Оказалось, что параллелилизм и конвейеризация вычислительных процессов требует разработки новых алгоритмов даже для тех задач, для которых существовали хорошо изученные и апробированные методы и алгоритмы решения, но ориентированные на последовательный принцип реализации. По прогнозам специалистов, в ближайшее десятилетие следует ожидать появления новых концепций построения вычислительных средств. Основанием для прогнозов являются результаты проводимых в настоящее время перспективных исследований, в частности, в области биочипов и органических переключающих элементов. Некоторые направления ставят своей целью создание схем в виде слоев органических молекул и пленок с высокоразвитой структурой. Это позволит, по мнению исследователей, выращивать компьютеры на основе генной инженерии и усилить аналогию между элементами технических систем и клетками мозга. Тем самым реальные очертания приобретают нейрокомпьютеры, которые имитируют интеллектуальные функции биологических объектов, в том числе человека. По-видимому, молекулярная электроника станет основой для создания ЭВМ шестого поколения. Все это объективно обусловливает интенсивные работы по методам синтезов алгоритмов обработки логических данных и их эффективному погружению в операционную среду бинарных элементов. Очевидно, что бинарные элементы и бинарные данные наиболее полно соответствуют друг другу в плане представления и обработки последних на таких элементах, если рассматривать их по отдельности. Действительно, положим, алгебра логики над числами (0,1) реализуется на бинарном элементе полном использовании его операционного ресурса. Другими словами, ставится вопрос об эффективности, а иногда вообще возможности реализации данного алгоритма на такой сети (структуре). В этом состоит суть погружения алгоритма в структуру.
§4. Математическая логика в криптографии
Криптография изучает методы пересылки сообщений в замаскированном виде, при которых только намеченные отправителем получатели могут удалить маскировку и прочитать сообщение. Общая схема защиты информации представлена на рисунке 2. Этап кодирования от ошибок основан на внесении в передаваемое сообщение избытка информации, достаточного для преодоления помех на линии связи. Например, допустим, передается последовательность символов типа 0 и 1. При этом в сети связи с некоторой вероятностью могут происходить ошибки приема сигнала 0 вместо сигнала 1 или наоборот, тогда кодер на каждый символ ai сообщения передает пятью импульсами 00000, если ai -0 и наоборот. На приемном конце принимаемая последовательность импульсов разбивается по пять импульсов, называемая блоками. Если в принятом блоке содержится 2 и менее импульса 0, то принимается решение о том, что передавался символ ai-1. Таким образом, исходная вероятность ошибки будет значительно снижена. Более элегантные методы кодирования, которые при достаточной надежности позволяют вносить не такой большой избыток информации. Для выражения в информации требуется ввести некоторый алфавит, из которого будет состоять сообщение (конечные упорядоченные множества из этих символов). Обозначим через A - мощность выбранного алфавита. Будем также считать, что все множества информации или, что то же самое, множество всевозможных сообщений конечно. В качестве меры информации в сообщении данной длины можно взять log2 от числа всевозможных сообщений конечно. Тогда объем информации, падающий на один символ алфавита X=log2a. Далее имеем дело со словами длинной S, тогда всего таких слов будет N=AS (декартова S- степень алфавита), а следовательно, количество информации в слове Y=Log2N=Log2As=SX. Львиную долю криптоанализа составляют методы, построенные на вероятностном анализе криптограммы и предлагаемого исходного языка. Поскольку всякий обычный язык имеет избыток информации, причем неравномерно размешенных в словах, то буквы алфавита этого языка могут иметь устойчивые частные характеристики. Например, в английском языке - это часто повторяющая буква e, кроме того, частотными характеристиками могут быть буквосочетания и их комбинации. Общая схема криптосистемы с секретным ключом изображена на рисунке 3. Здесь Х - открытый текст, Y- шифр текста, K - ключ шифра, R - рандомизирующая последовательность.
§5. Математическая логика в программировании
Функция одного аргумента - это правило, ставящее соответствие любому значению, лежащему в области изменения этого аргумента (которая будет и областью определения этой функции), другую величину, лежащую в области значений функции.
Понятие функции было перенесено в языки программирования. В языке программирования, как правило, предусмотрен ряд встроенных функций, например sin, cos, sqrt и т.д. Кроме того, программист имеет возможность определять свои собственные функции. Они могут работать не только с вещественными числами, но и с различными типами данных, включающими обычно integer (целое), real (вещественное), boolean (булевское), character (строковое). Они могут также работать со структурами. В языках Паскаль, Алгол=68 и ПЛ/1 имеются, например, типы records (записи), arrays (массивы), lists (списки), files of records (файлы, состоящие из записей), а значениями функций могут быть указатели этих структур. Все это согласовано с понятием области определения, вне которой функция не определена. В языках программирования эта область задана обычно указанием типа данных, который является некоторым множеством величин. Так, в Паскале компилятор должен следить за тем, чтобы никакая функция не применялась к величине неподходящего типа, которая могла бы выйти за пределы области определения функции.
Функция многих аргументов. Теперь нужно обобщить определение, чтобы охватить функции многих аргументов. Для этого соберем n аргументов в упорядоченный набор, который будем рассматривать как один аргумент. Возьмем функцию вычитания diff(x.y). Трактуется ее как отображение пар <х,у> в целые числа. В виде множества упорядоченных пар ее можно записать следующим образом: diff = {<<5,3>, 2>. <<6,3>, 3>, <<4,5>, -1>...} Если бы вместо этого у нас была функция четырех аргументов h(x,y,z,w), то использовали бы отображение, определенное на четверках
Заключение
Математическая логика немало способствовала бурному развитию информационных технологий в XX веке, но из ее поля зрения выпало понятие "суждение", которое появилось в логике еще во времена Аристотеля и на котором, как на фундаменте, держится логическая основа естественного языка. Такое упущение отнюдь не способствовало развитию логической культуры общества и у многих даже породило иллюзию, что компьютеры способны мыслить не хуже самого человека. Многих даже не смущает то обстоятельство, что на фоне всеобщей компьютеризации в преддверии третьего тысячелетия логические нелепости в пределах самой науки (я уж не говорю о политике, законотворческой деятельности и о псевдонауке) встречаются даже чаще, чем в конце XIX века. И для того, чтобы понять суть этих нелепостей, нет необходимости обращаться к сложным математическим структурам с многоместными отношениями и рекурсивными функциями, которые применяются в математической логике. Оказывается, для понимания и анализа этих нелепостей вполне достаточно применить намного более простую математическую структуру суждения, которая не только не противоречит математическим основам современной логики, но в чем-то дополняет и расширяет их.
Список используемой литературы
1.Игошин, В.И. Математическая логика и теория алгоритмов [Текст] / В.И. Игошин. - М.: Академия, 2008. - 448 с.; с ил.
Стяжкин, Н.И. Формирование математической логики [Текст] / Н.И. Стяжкин. - М.: Наука, 1967. - 508 с.; с ил.
Марков, А.А. Элементы математической логики [Текст] / А.А. Марков. - М.: МГУ, 2004. - 310 с.; с ил.
Карри, Х.Б. Основания математической логики [Текст]/Х.Б. Карри. - М.: Мир, 1969. - 568 с.; с ил.
Репетиторство
Нужна помощь по изучению какой-либы темы?
Наши специалисты проконсультируют или окажут репетиторские услуги по интересующей вас тематике.
Отправь заявку
с указанием темы прямо сейчас, чтобы узнать о возможности получения консультации.
