Решение задач математической логики с помощью таблиц истинности
Содержание
Введение……………………………………………………………………..2
1. Математическая логика……………………………………………...4
2. Решение задач математической логики с помощью таблиц
истинности………………………………………………………………….19
Заключение…………………………………………………………………27
Список используемой литературы………………………………………..28
Введение
Вся наша жизнь – непрерывное решение больших и маленьких логических проблем.
Есть такая наука – логика, которая учит, как нужно рассуждать, чтобы наше мышление было определенным, связным, последовательным, доказательным и непротиворечивым. Как человек, не знающи правил информатики и грамматики не может правильно считать и грамотно писать, так и человек, не знающий правил логики, не может без ошибок рассуждать и действовать.
Чтобы правильно рассуждать, надо изучить правильные способы и методы рассуждении. Научится правильно составлять высказывания, или, как говориться в математической логике, выполнять операции над высказываниями. При этом необходимо знать, вытекает ли истинность сложных высказывании из истинности составляющих их более простых предложении. Анализом методов рассуждений занимается наука логика, а исследованием и изучением математических рассуждений – математическая логика.
Решение всякой задачи – это, прежде всего, цепь рассуждении. Вычисления, преобразования, построения, которыми так часто приходится пользоваться для решения задач, невозможны без логических рассуждении: они направляются ими.
|
|
|
Математическая логика отличается тем, что пользуется языком математических и логических символов, исходя из того, что в принципе они могут совсем заменить слова обычного языка и принятые в обычных живых языках способы объединения слов в предложения. Особенности математического мышления объясняются особенностями математических абстракций и многообразием их взаимосвязей. Они отражаются в логической систематизации математики, в доказательстве математических теорем. В связи с этим современную математическую логику определяют как раздел
математики, посвященный изучению математических доказательств и вопросов оснований математики.
1. Математическая Логика.
В аксиоматическом построении математической теории предварительно выбирается некоторая система неопределяемых понятий и отношения между ними. Эти понятия и отношения называются основными. Далее без доказательства принимаются основные положения рассматриваемой теории - аксиомы. Всё дальнейшее содержание теории выводится логически из аксиом. Впервые аксиоматическое построение математической теории было предпринято Евклидом в построении геометрии. Изложение этой теории в Началах не безупречно. Евклид здесь пытается дать определение исходных понятий (точки, прямой, плоскости). В доказательстве теорем используются нигде явно не сформулированные положения, которые считаются очевидными. Таким образом, в этом построении отсутствует необходимая логическая строгость, хотя истинность всех положений теории не вызывает сомнений.[1]
|
|
|
Отметим, что такой подход к аксиоматическому построению теории оставался единственным до XIX века. Большую роль в изменении такого подхода сыграли работы Н. И. Лобачевского (1792-1856). Лобачевский впервые в явном виде высказал убеждения в невозможности доказательства пятого постулата Евклида и подкрепил это убеждение созданием новой геометрии. Позже немецкий математик Ф. Клейн (1849-1925) доказал непротиворечивость геометрии Лобачевского, чем фактически была доказана и невозможность доказательства пятого постулата Евклида. Так возникли и были решены в работах Н. И. Лобачевского и Ф. Клейна впервые в истории математики проблемы невозможности доказательства и непротиворечивости в аксиоматической теории. Непротиворечивость аксиоматической теории является одним из основных требований, предъявляемых к системе аксиом данной теории. Она означает, что из данной системы аксиом нельзя логическим путём вывести два противоречивых друг другу утверждения.
|
|
|
Доказательство непротиворечивости аксиоматических теорий можно осуществить различными методами. Одним из них является МЕТОД МОДЕЛИРОВАНИЯ или ИНТЕРПРЕТАЦИЙ. Здесь в качестве основных понятий и отношений выбираются элементы некоторого множества и отношения между ними, а затем проверяется, будут ли выполняться для выбранных понятий и отношений аксиомы данной теории, то есть строится модель для данной теории. Так, аналитическая геометрия является арифметической интерпретацией геометрии Евклида. Ясно, что метод моделирования сводит вопрос о непротиворечивости одной теории к проблеме непротиворечивости другой теории. Большинство интерпретаций для математических теорий (и, в частности, для арифметики) строится на базе теории множеств. Однако в конце XIX века в теории множеств были обнаружены противоречия (парадоксы теории множеств). Ярким примером такого парадокса является парадокс Б. Рассела. Разобьем все мыслимые множества на два класса. Назовём множество нормальным, если оно не содержит себя в качестве своего элемента и ненормальным в противном случае. Например, множество всех книг - нормальное множество, а множество всех мыслимых вещей - ненормальное множество. Пусть L - множество всех нормальных множеств. К какому классу относится множество L? Если L - нормальное множество, то L Î L, т.е. содержится в классе нормальных множеств, но тогда оно содержит себя в качестве своего элемента, и поэтому ненормально. Если L - ненормальное множество, то L Ï L, т.е. не содержится среди нормальных множеств, но тогда L не содержит себя в качестве своего элемента, и потому оно нормально. Таким образом, понятие нормального множества приводит к противоречию.[2]
|
|
|
Попытки устранить противоречия в теории множеств привели ЦЕРМЕЛО к необходимости построить аксиоматическую теорию множеств. Последующие видоизменения и усовершенствования этой теории привели к созданию современной теории множеств. Однако средства этой аксиоматической теории не позволяют доказать её непротиворечивость. Другие методы обоснования математики были развиты Д. ГИЛБЕРТОМ (1862-1943) и его школой. Они основываются на построении математических теорий как синтаксических теорий, в которых все аксиомы записываются формулами в некотором алфавите и точно указываются правила вывода одних формул из других, т.е. в теорию как составная часть входит математическая логика.
Таким образом, математическая теория, непротиворечивость которой требовалось доказать, стала предметом другой математической теории, которую Гилберт назвал МЕТАМАТЕМАТИКОЙ, или ТЕОРИЕЙ ДОКАЗАТЕЛЬСТВ. В связи с этим возникает задача построения синтаксической, т.е. формализованной аксиоматической теории самой математической логики. Выбирая по-разному системы аксиом и правила вывода одних формул из других, получают различные синтаксические логические теории. Каждую из них называют ЛОГИЧЕСКИМ ИСЧИСЛЕНИЕМ. Ъ
Предмет математической логики
Основная идея математической логики - формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания - математические. Таким образом, математическая логика, по-существу, - наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство''. Действительно, ``доказательные'' (иначе говоря, дедуктивные) рассуждения - единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим'' процессом переписывания текста (формул). Такой процесс называют выводом. Говорят еще, что математическая логика оперирует только синтаксическими понятиями. Однако обычно всё же важно, как соотносятся рассуждения с действительностью (или нашими представлениями). Поэтому, надо всё же иметь в виду некоторый смысл формул и вывода. При этом используют термин семантика (синоном слова ``смысл'') и чётко разделяют синтаксис и семантику. Когда же действительно интересуются только синтаксисом, часто используют термин ``формальная система''. Мы будем использовать синоним этого термина - ``исчисление'' (используются ещё термины ``формальная теория'' и ``аксиоматика''). Объектом формальных систем являются строки текста (последовательности символов), с помощью которых записываются формулы.
Формальная система определена, если:
Задан алфавит (множество символов, используемых для построения формул).
Определено, какие именно строки считать формулами (остальные строки считаются просто бессмысленными).
Выделено множество формул, называемых аксиомами. Это - стартовые точки в выводах.
Задано множество правил вывода, которые позволяют из некоторой формулы (или множества формул) получать новую формулу.
Основные принципы операций :
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 В, которое является истинным при истинности по крайней мере одного из двух дизъюнктивных членов: <#"justify">Импликация
Импликация двух логических высказываний A и B - логическое высказывание, ложное только тогда, когда B ложно, а A истинно (от лат. implicatio - сплетение, от implico - тесно связываю) - логическая связка, соответствующая грамматической конструкции «если.., то...», с помощью которой из двух простых высказываний образуется сложное высказывание. В импликативном высказывании различают антецедент (основание) - высказывание, идущее после слова «если», и консеквент (следствие) - высказывание, идущее за словом «то». Импликативное высказывание представляет в языке логики условное высказывание обычного языка. Последнее играет особую роль, как в повседневных, так и в научных рассуждениях, основной его функцией является обоснование одного путем ссылки на нечто другое.
Выражаемую условным высказыванием связь обосновывающего и обосновываемого трудно охарактеризовать в общем виде, и только иногда природа ее относительно ясна. Эта связь может быть, в частности, связью логического следования, имеющей место между посылками и заключением правильного умозаключения («Если все живые многоклеточные существа смертны и медуза является таким существом, то она смертна»). Связь может представлять собой закон природы («Если тело подвергнуть трению, оно начнет нагреваться») или причинную связь («Если Луна в новолуние находится в узле своей орбиты, наступает солнечное затмение»). Рассматриваемая связь может иметь также характер социальной закономерности, правила, традиции и т.п. («Если меняется экономика, меняется и политика», «Если обещание дано, оно должно быть выполнено»).
Связь, выражаемая условным высказыванием, предполагает, что консеквент с определенной необходимостью «вытекает» из антецедента и что есть некоторый общий закон, сумев сформулировать который, мы можем логически вывести консеквент из антецедента. Например, условное высказывание «Если висмут- металл, он пластичен» предполагает общий закон «Все металлы пластичны», делающий консеквент данного высказывания логическим следствием его антецедента.
В логических системах абстрагируются от особенностей обычного употребления условного высказывания, что ведет к различным импликациям. Наиболее известны из них импликация материальная, строгая импликация и релевантная (уместная) импликация.
Материальная импликация - одна из основных связок классической логики. Определяется она таким образом: импликация ложна только в случае истинности антецедента и ложности консеквента и истинна во всех остальных случаях. Условное высказывание «Если А, то В» предполагает некоторую реальную связь между тем, о чем говорится в А и В; выражение «А материально имплицирует В» такой связи не предполагает.
Строгая импликация определяется через модальное понятие (логической) невозможности: «А строго имплицирует В» означает «Невозможно, чтобы А было истинно, а В ложно».
В релевантной логике импликация понимается как условный союз в его обычном смысле. В случае релевантной импликация нельзя сказать, что истинное высказывание может быть обосновано путем ссылки на любое высказывание и что с помощью ложного высказывания можно обосновать какое угодно высказывание. [3]
Эквивалентность
Эквивалентность двух логических высказываний - логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны (от позднелат. equivalens - равноценный) - родовое наименование всевозможных отношений типа равенства, т.е. рефлексивных , симметричных и транзитивных бинарных отношений. Примеры: эквиполентность (совпадение по смыслу, значению, содержанию, выразительным и (или) дедуктивным возможностям между понятиями, концепциями, науч. теориями или формализующими их формальными системами) конгруентность или подобие геометрия, фигур; изоморфизм; равномощность множеств и другие эквивалентность каких-либо объектов означает их равенство (тождество) в каком-либо отношении(например, изоморфные множества неразличимы по своей "структуре", если под "структурой" понимать совокупность тех их свойств, относительно которых эти множества изоморфны). Всякое отношение эквивалентности порождает разбиение множества, на котором оно определено, на попарно не пересекающиеся "классы эквивалентности " в один класс относят при этом эквивалентные друг другу элементы данного множества.
Рассмотрение классов эквивалентности в качестве новых объектов представляет собой один из основных способов порождения (введения) абстрактных понятий в логико-математических (и вообще естественно-научных) теориях. Так, считая эквивалентными дроби a/b и c/d с целыми числителями и знаменателями, если ad=bc, вводят в рассмотрение рациональные числа как классы эквивалентных дробей; считая эквивалентными множества, между которыми можно установить взаимно-однозначное соответствие, вводят понятие мощности (кардинального числа) множества (как класс эквивалентных между собой множеств); считая эквивалентными два куска вещества, вступающие в равных условиях в одинаковые химических реакции, приходят к абстрактному понятию химического состава и т.п.
Термин " эквивалентность" употребляют часто не (только) как родовой, а как синоним некоторых из его частных значений ("эквивалентность теорий" вместо "эквивалентность", " эквивалентность множеств" вместо "равномощность", " эквивалентность слов" в абстрактной алгебре вместо "тождество" и т.п.).
Кванторное высказывание
Кванторное с квантором всеобщности.
Кванторное логическое высказывание с квантором всеобщности ("xA(x)) - логическое высказывание, истинное только тогда, когда для каждого объекта x из заданной совокупности высказывание A(x) истинно.
Кванторное с квантором существования.
Кванторное логическое высказывание с квантором существования ($xA(x)) - логическое высказывание, истинное только тогда, когда в заданной совокупности существует объект x, такой, что высказывание A(x) истинно.
Структура математической логики
Раздел «математическая логика» состоит из трёх частей: по неформальному аксиоматическому методу, по логике высказываний и по логике предикатов (первого порядка). Аксиоматический метод построения - первый шаг на пути к формализации теории. Большинство задач, рассматриваемых в математической логике, состоит в доказательстве некоторых утверждений. Математическая логика имеет много разветвлений. Она применяет табличное построение логики высказываний, использует специальный язык символов и формулы логики высказываний.[4]
Неформальный аксиоматический метод
Аксиоматический метод, не фиксирующий жестко применяемого языка и тем самым не фиксирующий границы содержательного понимания предмета, но требующий аксиоматического определения всех специальных для данного предмета исследования понятий. Этот термин не имеет общепринятого толкования.
История развития аксиоматического метода характеризуется все возрастающей степенью формализации. Неформальный аксиоматический метод - определенная ступень в этом процессе.
Первоначальное, данное Евклидом, аксиоматическое построение геометрии отличалось дедуктивным характером изложения, при котором в основу клались определения (пояснения) и аксиомы (очевидные утверждения). Из них, опираясь на здравый смысл и очевидность, выводились следствия. При этом в выводе неявно иногда использовались не зафиксированные в аксиомах предположения геометрия, характера, особенно относящиеся к движению в пространстве и взаимному расположению прямых и точек. Впоследствии были выявлены геометрия, понятия и регламентирующие их употребление аксиомы, неявно используемые Евклидом и его последователями. При этом возникал вопрос: действительно ли выявлены все аксиомы. Руководящий принцип для решения этого вопроса сформулировал Д. Гильберт (D. Hilbert): "Следует добиться того, чтобы с равным успехом можно было говорить вместо точек, прямых и плоскостей о столах, стульях и пивных кружках". Если доказательство не теряет доказательной силы после такой замены, то действительно все используемые в этом доказательстве специальные предположения зафиксированы в аксиомах. Достигаемая при таком подходе степень формализации представляет собой уровень формализации, характерный для неформального аксиоматического метода. Эталоном здесь может служить классический труд Д. Гильберта "Основания геометрии" .
Неформальный аксиоматический метод применяется не только для придания определенной завершенности аксиоматически излагаемой конкретной теории. Он представляет собой действенное орудие математического исследования. Поскольку при изучении системы объектов по этому методу не используется их специфика, или "природа", то доказанные утверждения переносятся на любую систему объектов, удовлетворяющую рассматриваемым аксиомам. Согласно неформальному аксиоматическому методу, аксиомы - это неявные определения первоначальных понятий (а не очевидные истины). Что представляют собой изучаемые объекты - неважно. Все, что нужно о них знать, сформулировано в аксиомах. Предметом изучения аксиоматической теории служит любая ее интерпретация.
Неформальный аксиоматический метод, кроме непременного аксиоматического определения всех специальных понятий, имеет и другую характерную особенность. Это свободное, неконтролируемое аксиомами, основанное на содержательном понимании использование идей и понятий, которые можно применить к любой мыслимой интерпретации, независимо от ее содержания. В частности, широко используются теоретико-множественные и логического понятия и принципы, а также понятия, связанные с идеей счета, и др. Проникновение в аксиоматический метод рассуждений, основанных на содержательном понимании и здравом смысле, а не на аксиомах, объясняется не фиксированностью языка, на котором формулируются и доказываются свойства аксиоматически заданной системы объектов. Фиксирование языка ведет к понятию формальной аксиоматической системы и создает материальную основу для выявления и четкого описания допустимых логических принципов, для контролируемого употребления теоретико-множественных и других общих или не специальных для исследуемой области понятий. Если в языке нет средств (слов) для передачи теоретико-множественных понятий, то этим отсеиваются все доказательства, основанные на использовании таких средств. Если в языке есть средства для выражения некоторых теоретико-множественных понятий, то их применение в доказательствах можно ограничить определенными правилами или аксиомами.[5]
Фиксируя различным образом язык, получают различные теории основного объекта рассмотрения. Например, рассматривая язык узкого исчисления предикатов для теории групп, получают элементарную теорию групп, в которой нельзя сформулировать какого-либо утверждения о подгруппах. Если перейти к языку исчисления предикатов второй ступени, то появляется возможность рассматривать свойства, в которых фигурирует понятие подгруппы. Формализацией неформальный аксиоматический метод в теории групп служит переход к языку системы Цермело - Френкеля с ее аксиоматикой.
Аксиоматический метод
Аксиоматический метод способ построения научной теории, при котором в её основу кладутся некоторые исходные положения (суждения)- аксиомы, или постулаты, из которых все остальные утверждения этой теории должны выводиться чисто логическим путём, посредством доказательств. Построение науки на основе аксиоматический метод обычно называется дедуктивным . Все понятия дедуктивной теории (кроме фиксированного числа первоначальных) вводятся посредством определений, выражающих их через ранее введённые понятия. В той или иной мере дедуктивные доказательства, характерные для аксиоматический метод , применяются во многих науках, однако главная область его приложения - математика, логика, а также некоторые разделы физики.
Идея аксиоматический метод впервые была высказана в связи с построением геометрии в Древней Греции (Пифагор, Платон, Аристотель, Евклид). Для современной стадии развития аксиоматический метод характерна выдвинутая Гильбертом концепция формального аксиоматический метод , которая ставит задачу точного описания логических средств вывода теорем из аксиом. Основная идея Гильберта - полная формализация языка науки, при которой её суждения рассматриваются как последовательности знаков (формулы), приобретающие смысл лишь при некоторой конкретной интерпретации. Для вывода теорем из аксиом(и вообще одних формул из других) формулируются спец. правила вывода. Доказательство в такой теории (исчислении, или формальной системе) - это некоторая последовательность формул, каждая из которых либо есть аксиома, либо получается из предыдущих формул последовательности по какому-либо правилу вывода. В отличие от таких формальных доказательств, свойства самой формальной системы в целом изучаются содержат. средствами метатеории. Основные требования, предъявляемые к аксиоматическим формальным системам,- непротиворечивость, полнота, независимость аксиом. Гильбертовская программа, предполагавшая возможность доказать непротиворечивость и полноту всей классической математики, в целом оказалась невыполнимой. В 1931 Гёделъ доказал невозможность полной аксиоматизации достаточно развитых научных теорий (напр., арифметики натуральных чисел), что свидетельствовало об ограниченности аксиоматического метода. Основные принципы аксиоматические методы были подвергнуты критике сторонниками интуиционизма и конструктивного направления. [6]
Решение задач математической логики с помощью таблиц истинности
Условимся, простые высказывания называть логическими переменными и обозначать большими буквами и, если высказывание истинно, будем писать A=1, а если ложно, то A=0.
Использование 0 и 1 подчеркивает некоторое соответствие между значениями логических переменных и функций в алгебре логики и цифрами в двоичной системе счисления. Это позволяет описывать работу логических схем ЭВМ и проводить их анализ и синтез с помощью математического аппарата алгебры логики.
Любое устройство ЭВМ, выполняющее действия над двоичными числами, можно рассмотреть как некоторый функциональный преобразователь. Причем числа на входе - значения входных логических переменных, а число на выходе - значение логической функции, которое получено в результате выполнения определенных операций. Таким образом, этот преобразователь реализует некоторую логическую функцию.
Значения логической функции для разных сочетаний значений входных переменных - или, как это иначе называют, наборов входных переменных - обычно задаются специальной таблицей. Такая таблица называется таблицей истинности. Количество наборов входных переменных (Q) можно определить по формуле:
Q=2n, где n -- количество входных переменных.
Простейшим примером логической функции является функция одной переменной
Интересной является только функция F2(X). О ней мы говорим чуть позже.
Функции двух аргументов. Их может быть 16.
Если у функции 3 аргумента, то число возможных функций возрастает до 256, поэтому более сложные логические функции задаются с помощью простых функций одного или двух аргументов. Для выражения сложных логических функций используют более простые, и оказывается, что можно использовать не все элементарные функции, а только часть.
Рассмотрим подробнее наиболее интересные логические функции одной и двух переменных.[7]
Логическое умножение. (conjunctio - лат. связываю) Соединение двух простых высказываний A и B в одно составное с помощью союза «и» называют логическим умножением или конъюнкцией, а результат операции -- логическим произведением.
Указание о логическом перемножении простых высказываний A и B обозначается так:
Например:
В русском языке в качестве операции «логическое умножение» помимо союза «и» используются союзы «но» и «а».
Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны.
Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. только если
Таблица истинности конъюнкции имеет следующий вид:
Следующие логические законы можно назвать свойствами конъюнкции.
Закон противоречия.
Закон равносильности (идемпотентности, idem - лат. тот же самый; potens - лат. сильный)
Закон исключения констант
Логическое сложение. (disjunctio - лат. различаю) Перед тем как привести определение этой операции, дадим некоторые разъяснения. Союз «или» в обиходе мы применяем в двух значениях: исключающем и неисключающем. Разъясним это примерами.
1. Рассмотрим повествовательное предложение: «Володя вчера в шесть часов вечера читал книгу или ехал в автобусе на стадион.» Союз «или» использован в этом предложении в неисключающем смысле -- Володя мог читать и одновременное ехать в автобусе. Одно не исключает другого.
2. Рассмотрим еще одно повествовательное предложение. «Володя вчера наблюдал за ходом матча с западной или восточной трибуны.» Здесь союз «или» имеет исключающий характер -- две описываемые ситуации исключают друг друга: нельзя наблюдать один и тот же матч одновременно с двух противоположных трибун.
Соединение двух простых высказываний A и B в одно составное с помощью союза «или», употребляемого в неисключающем смысле, называется логическим сложением или дизъюнкцией, а полученное составное высказывание -- логической суммой.
Указание о необходимости выполнить логическое сложение высказываний A и B записывается так:
Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны.
Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. А+В+С=0, только если , А=0, В=0, С=0.
Таблица истинности дизъюнкции имеет следующий вид:
Следующие логические законы можно назвать свойствами дизъюнкции.
Закон противоречия.
Закон равносильности (идемпотентности idem - лат. тот же самый; potens - лат. сильный) А+А=А
Закон исключения констант А+1=1, А+0=А
Логическое отрицание. (inversio - лат. переворачиваю) Присоединение частицы «не» к сказуемому данного простого высказывания A называется операцией логического отрицания или инверсией. Обозначается A или A.
Иногда вместо приведенного определения используют другое, ему эквивалентное: присоединение слов «Неверно, что …» ко всему данному высказыванию A называется операцией логического отрицания. В результате выполнения операции логического отрицания получается новое высказывание.
Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.
Таблица истинности инверсии имеет вид:
Закон двойного отрицания
Импликация. (implicatio - лат. тесно связываю) или логическое следование соответствует обороту «если…, то…», обозначается
A={Поезд прибывает на данный путь.}
B={Подается сигнал, что путь закрыт.}
Рассматриваемое сложное высказывание истинно, если:
1) поезд прибывает, сигнал «закрыт» (1, 1, 1);
2) поезд не прибывает, сигнал «свободен» (0, 0, 1);
3) поезд не пребывает, сигнал «закрыт» (0, 0, 1) - если поезд не пребывает, безопасен любой сигнал;
4) высказывание ложно (безопасность не обеспечивается) только в том случае, если поезд прибывает, а сигнал «свободен» (1, 0, 0).
Операция импликации в русском языке является самой «загадочной». Ей соответствую также следующие речевые обороты: «из А следует В»; «А имплицирует В»; «А достаточно для В»; «В необходимо для А».
Эквивалентность. (aequivalens - фр. равноценное) или равнозначность, соответствует оборотам речи «тогда и только тогда» и «в том и только в том случае.[8]
Выражение истинно в том и только в том случае, когда оба исходных высказывания одновременно истинны или одновременно ложны.
«Петя выучит уроки тогда и только тогда, когда Пете поставят хорошую отметку.»
В русском языке операции эквивалентности также соответствует речевой оборот «A необходимо и достаточно B».
Представление эквивалентности через конъюнкцию, дизъюнкцию и инверсию
Строгая дизъюнкция или Сложение по модулю «2», соответствует оборотам речи «или…, или…» или «либо…, либо…», и обозначается
Законы логики. Упрощение логических выражений
Если у двух логических функций совпадают таблицы истинности, то есть на всех наборах значений входных переменных они принимают одинаковое значение, то их называют равносильными или эквивалентными. Это обозначается знаком =.
Логические функции, истинные на всех наборах значений входных переменных, называются тождественно-истинными.
Логические функции, ложные на всех наборах значений входных переменных, называются тождественно-ложными.
Среди многочисленных законов логики есть четыре основных. Для трех из них можно найти аналогию в алгебре чисел.
Для упрощения логических функций удобно использовать формулы склеивания и поглощения.
Используя законы логики, формулы склеивания и поглощения и свойства логических операций, можно сложную логическую функцию заменить более простой, но равносильной ей функцией. Этот процесс называется минимизацией функции. Минимизация необходима для того, чтобы функциональные схемы не были слишком громоздкими и не использовали лишних элементов. Чем меньше в функции, получаемой при минимизации, входных переменных и используемых логических операций, тем проще логическая схема, меньше в ней логических элементов. [9]Минимизация необходима и при составлении сложных логических выражений в программах.
Примеры решения задач по математической логике
Пример 1.
Расставить скобки в формулах:
1 ) xЃЙy - z?x ; 2) xvyЃЙz ; 3) x?y) - z>x ЃИ yЃЙz .
Решение:
1 ) в формуле xЃЙy - z?x скобки расставляются следующим образом:
((xЃЙy) - (z?x));
2) т.к. операция v сильнее операции ЃЙ согласно замечанию имеем ((xvy)ЃЙz);
3) в формуле (x?y) - z>x ЃИ yЃЙz используя введенное старшинство связок, получаем, что данная формула равносильна ((x?y) - (z>((x ЃИ y)ЃЙ(z)))).
Пример 2.
Составить таблицы истинности для формул:
а) x - y > ( y ? x); б) x | (( y ЃЙ z ) v x ЃИ z ).
Решение:
а) используя введенное старшинство связок, получим, что данная формула равносильна x - (y > (y ? x)) , а таблица истинности примет вид:
б) составим таблицу истинности для формулы x | (( y ЃЙ z ) v x ЃИ z )
Формула называется тождественно истинной (ложной), если она принимает значение 1 (0) при всех значениях входящих в нее переменных.
Пример 3
Является, ли формула ((х > у) ЃИ у) > х тождественно истинной?
Формула равна 1 при всех значениях входящих в нее переменных, следовательно, она тождественно истинная (тавтология).
Пример 4
После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия:
а) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский;
б) если поедут Арбузов и Вишневский, то поедет и Брюквин.
Требуется установить, кто из перечисленных сотрудников войдет в состав экспедиции.
Решение.
Назначение в экспедицию Арбузова, Брюквина и Вишневского будем обозначать буквами А, Б, В соответственно.
Тогда условие а) можно записать в виде А>БЃЙВ, а условие б) в виде А&В> Б.
Так как оба условия должны выполняться одновременно, то они должны быть соединены
логической связью «и». Поэтому принятое решение можно записать в виде формулы
L=(А>БЃЙВ)&(А&В>Б) эта формула должна быть истинной.
Подвергнем формулу L равносильным преобразованиям, получим:
L=( А ЃЙБЃЙB)&(A & BЃЙВ)=( А ЃЙБЃЙB)&( А ЃЙ В ЃЙБ).
Применяя к последнему выражению второй закон дистрибутивности, получим
L= А ЃЙ[(БЃЙВ)&(БЃЙ В )] = А ЃЙ[БЃЙ(B&В )] = А ЃЙБ=A>Б.
Отсюда следует, что если поедет в экспедицию Арбузов, то с ним должен ехать и Брюквин.
Пример 5.
Жили четыре друга. Звали их Альберт, Карл, Дитрих и Фридрих. Фамилии друзей те же, что и имена, только так, что ни у кого из них имя и фамилия не были одинаковыми, кроме того, фамилия Дитриха не Альберт. Определите фамилию и имя каждого мальчика, если дано, что имя мальчика, у которого фамилия Фридрих, есть фамилия того мальчика, имя которого фамилия Карла.
Решение.
Будем обозначать имя и фамилию каждого мальчика двумя буквами в виде Ху, где «X» - первая буква имени, а «у» - первая буква фамилии. Из условия задачи следует, что нет мальчиков, соответствующих символам Аа, Дд, Кк, Фф, Да, то есть высказывания
Аа=Дд=Кк=Фф=Да=0. Но есть мальчик Ху такой, что есть мальчики Уф, Кх. Следовательно, истинной является формула Кх&Ху&Уф=1.
Но Х?К, так как Кк=0; Х?Ф, так как иначе будет два мальчика с фамилией Ф. Аналогично, У?К, У?Ф. Следовательно, или X=Д, или Х=А. Но X?Д, так как при Х=Д, У=А и, значит, Ху =Да, что противоречит условию. Значит, Х=А, а У=Д. Поэтому истинной является формула Ка&Ад&Дф&Фк.
Следовательно, мальчики с именами Карл, Альберт, Дитрих и Фридрих имеют фамилии соответственно Альберт, Дитрих, Фридрих и Карл.
Заключение
Объединение математико-логической установки с иными математическими подходами, прежде всего с вероятностно-статистическими идеями и методами - на фоне глубокого интереса к вычислительным приборам, - было во многом определяющим в формировании замысла кибернетики, как комплексного научного направления, имеющего своим предметом процессы.
В ряде случаев используется технический аппарат математической логики (синтез релейно-контактных схем); сверх того, что особенно важно, идеи математической логики это, конечно же, в теории алгоритмов, но также и всей науки в целом и свойственный ей стиль мышления оказали и продолжают оказывать очень большое влияние на те своеобразные области деятельности, содержанием которых является автоматическая переработка информации (информатика), использование в криптографии и автоматизация процессов управления (кибернетика).
Математическая логика облегчает механизацию умственного труда. Нынешние машины выполняют гораздо более сложные логические операции, нежели их скромные прототипы начала века.
Проблема искусственного разума сложна и многогранна. Вероятно, не ошибёмся, если скажем, что окончательные границы механизации мысли можно установить лишь экспериментальным путём. Заметим ещё, что в современной кибернетики обсуждается возможность моделирования не только формальных, но и содержательных мыслительных процессов.
Список используемой литературы
1. Клини С. К., Введение в метаматематику, пер. с англ., М., 1957 (лит.)
2. Колмогоров А. Н., Драгалин А. Г.. Введение в математическую логику - Классический университетский учебник , Изд. 3-е,стереотипное, КомКнига, 2016, с. 10.
3. Константинова Ф.В Философская Энциклопедия. В 5-х т. -- М.: Советская энциклопедия. 1960--1970.
4. Новиков П. С., Элементы математич. логики, M., 2015г.
Онлайн учебник «Математическая логика»-раздел «Введение»: http://mathlog.h11.ru/vved.htm. 2014г.
5. Панов В.Г Философский энциклопедический словарь. -- М.: Советская энциклопедия. 2015г.
6. Петухин В.А Курс «Дискретная математика» Омского Государственного Университета. http://fkn.univer.omsk.su/kursi/disc/logic.htm#0.1
Портал«Академик»: http://epistemology_of_science.academic.ru/567/отрицание#sel=4
7. Пронин Ю.А "Объединенный научный журнал" ("The integrated scientific journal"), 2010 №9 (244).
8. Садовский В. Н., А. м. построения науч. знания, в кн.: Филос. вопросы совр. формальной логики, М., 2016г.
9. Столл Р., Множества. Логика. Аксиоматич. теории, пер. с англ., М., 2017г.
10. Тимин В.А Статья по логике http://timinva.narod.ru/m0240.htm#_Toc310240290
11. Шапорев С.Д. Информатика. Теоретический курс и практические занятия. Санкт-Петербург,2008.
[1]Клини С. К., Введение в метаматематику, пер. с англ., М., 1957 (лит.)
[2]Колмогоров А. Н., Драгалин А. Г.. Введение в математическую логику - Классический университетский учебник , Изд. 3-е,стереотипное, КомКнига, 2016, с. 10.
[3]. Константинова Ф.В Философская Энциклопедия. В 5-х т. -- М.: Советская энциклопедия. 1960--1970.
[4]. Новиков П. С., Элементы математич. логики, M., 2015г.Онлайн учебник «Математическая логика»-раздел.
[5]Панов В.Г Философский энциклопедический словарь. -- М.: Советская энциклопедия. 2015г.
[6]Петухин В.А Курс «Дискретная математика» Омского Государственного Университета. http://fkn.univer.omsk.su/kursi/disc/logic.htm#0.Портал«Академик»: http://epistemology_of_science.academic.ru/567/отрицание#sel=4.
[7]Пронин Ю.А "Объединенный научный журнал" ("The integrated scientific journal"), 2010 №9 (244).
[8]Садовский В. Н., А. м. построения науч. знания, в кн.: Филос. вопросы совр. формальной логики, М., 2016г.
[9]Шапорев С.Д. Информатика. Теоретический курс и практические занятия. Санкт-Петербург,2008.
Дата добавления: 2018-02-28; просмотров: 794; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!