Элементы математической логики, ее символы

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУРГАНСКИЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра … 
 
 
 
 
 
 

Реферат на тему: Элементы математической логики, ее символы. 
 
 
 

Исполнитель: Бабин А.А. 
 
 
 
 
 
 

Тюмень 

2009 
Содержание

 

1. История возникновения математической логики

       Математическая  логика тесно связана с логикой  и обязана ей своим возникновением. Основы логики, науки о законах и формах человеческого мышления (отсюда одно из ее названий - формальная логика), были заложены величайшим древнегреческим философом Аристотелем (384—322 гг. до н. э.), который в своих трактатах обстоятельно исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления, в том числе законы противоречия и исключения третьего. Вклад Аристотеля в логику весьма велик, недаром другое ее название - аристотелева логика. Еще сам Аристотель заметил, что между созданной им наукой и математикой (тогда она именовалась арифметикой) много общего. Он пытался соединить две эти науки, а именно свести размышление, или, вернее, умозаключение, к вычислению на основании исходных положений. В одном из своих трактатов Аристотель вплотную приблизился к одному из разделов математической логики - теории доказательств.

       В дальнейшем многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646 - 1716), указавший пути для перевода логики «из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно» . Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав . При этом в своих работах Лейбниц затрагивал и двоичную систему счисления.

       Следует отметить, что идея использования  двух символов для кодирования информации очень стара. Австралийские аборигены  считали двойками, некоторые племена охотников-сборщиков Новой Гвинеи и Южной Америки тоже пользовались двоичной системой счета. В некоторых африканских племенах передают сообщения с помощью барабанов в виде комбинаций звонких и глухих ударов. Знакомый всем пример двухсимвольного кодирования - азбука Морзе, где буквы алфавита представлены определенными сочетаниями точек и тире.

       После Лейбница исследования в этой области  вели многие выдающиеся ученые, однако настоящий успех пришел здесь  к английскому математику-самоучке Джорджу Булю (1815—1864), целеустремленность которого не знала границ. Материальное положение родителей Джорджа (отец которого был сапожным мастером) позволило ему окончить лишь начальную школу для бедняков. Спустя какое-то время Буль, сменив несколько профессий, открыл маленькую школу, где сам преподавал. Он много времени уделял самообразованию и вскоре увлекся идеями символической логики. В 1847 году Буль опубликовал статью «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений», а в 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей».

         Буль изобрел своеобразную алгебру  - систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ).

       Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в XX столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

   Отдельные положения работ Буля в той  или иной мере затрагивались и  до, и после него другими математиками и логиками. Однако сегодня в данной области именно труды Джорджа Буля причисляются к математической классике, а сам он по праву считается основателем математической логики и тем более важнейших ее разделов - алгебры логики (булевой алгебры) и алгебры высказываний.

       Большой вклад в развитие логики внесли и  русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947).

       В XX веке огромную роль в развитии математической логики сыграл Д. Гильберт (1862-1943), предложивший программу формализации математики, связанную с разработкой оснований  самой математики. Наконец, в последние  десятилетия XX века бурное развитие математической логики было обусловлено развитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К. Клини, А. Черч, А.А Марков, П.С. Новиков и многие другие).  

       2. Основное содержание, формулы, элементы, символы

     Алгебра логики (логика высказываний) - один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях высказываний.

     Высказывание - это термин математической логики, которым обозначается предложение какого-либо языка (естественного или искусственного), рассматриваемого лишь в связи с его истинностью. Например:

     Приведем  примеры, предложений не являющихся высказываниями:

«Посмотрите в окно.» 

«Который  час?» 

«2x+7>12»

     Отличительным признаком любого высказывания является его свойство быть истинным или ложным, а этим свойством три вышеприведенных предложения не обладают.

     Используя простые высказывания, можно образовывать сложные, или составные, высказывания, в которые простые входят в качестве элементарных составляющих. В образовании сложных высказываний используются слова: и, или, тогда и только тогда, когда (в том и только в том случае), если …, то …, нет.

     Рассмотрим  несколько примеров сложных высказываний:

«Если идет дождь, то солнце не светит.» 

« Если ветер дует, то нет дождя.» 

     Основная  задача логики высказываний заключается  в том, чтобы на основании истинности или ложности простых высказываний определить истинность или ложность сложных высказываний.

2.1. Таблицы истинности. Логические функции. Основные логические операции

     Условимся, простые высказывания называть логическими переменными и обозначать большими буквами и, если высказывание истинно, будем писать A=1, а если ложно, то A=0.

     Использование 0 и 1 подчеркивает некоторое соответствие между значениями логических переменных и функций в алгебре логики и цифрами в двоичной системе  счисления. Это позволяет описывать работу логических схем ЭВМ и проводить их анализ и синтез с помощью математического аппарата алгебры логики.

     Любое устройство ЭВМ, выполняющее действия над двоичными числами, можно  рассмотреть как некоторый функциональный преобразователь. Причем числа на входе - значения входных логических переменных, а число на выходе - значение логической функции, которое получено в результате выполнения определенных операций. Таким образом, этот преобразователь реализует некоторую логическую функцию.

     Значения  логической функции для разных сочетаний  значений входных переменных - или, как это иначе называют, наборов входных переменных - обычно задаются специальной таблицей. Такая таблица называется таблицей истинности. Количество наборов входных переменных (Q) можно определить по формуле:

Q=2ⁿ, где n — количество входных переменных.

Простейшим  примером логической функции является функция одной переменной .

      

     Интересной  является только функция F₂(X). О ней мы говорим чуть позже.

Функции двух аргументов. Их может быть 16.

     Если  у функции 3 аргумента, то число возможных  функций возрастает до 256, поэтому  более сложные логические функции  задаются с помощью простых функций  одного или двух аргументов. Для  выражения сложных логических функций используют более простые, и оказывается, что можно использовать не все элементарные функции, а только часть.

     Рассмотрим  подробнее наиболее интересные логические функции одной и двух переменных.

     Логическое  умножение. (conjunctio - лат. связываю) Соединение двух простых высказываний A и B в одно составное с помощью союза «и» называют логическим умножением или конъюнкцией, а результат операции — логическим произведением.

Указание  о логическом перемножении простых  высказываний A и B обозначается так:

     Например:

     В русском языке в качестве операции «логическое умножение» помимо союза  «и» используются союзы «но» и  «а».

     Конъюнкция  двух логических переменных истинна тогда  и только тогда, когда  оба высказывания истинны.

     Это определение можно обобщить для  любого количества логических переменных, объединенных конъюнкцией. только если

     Таблица истинности конъюнкции имеет следующий  вид:

      

Следующие логические законы можно назвать  свойствами конъюнкции.

Закон противоречия.

Закон равносильности (идемпотентности, idem – лат. тот же самый; potens – лат. сильный)

Закон исключения констант

     Логическое  сложение. (disjunctio – лат. различаю) Перед тем как привести определение этой операции, дадим некоторые разъяснения. Союз «или» в обиходе мы применяем в двух значениях: исключающем и неисключающем. Разъясним это примерами.

1. Рассмотрим  повествовательное предложение:  «Володя вчера в шесть часов  вечера читал книгу или ехал  в автобусе на стадион.» Союз  «или» использован в этом предложении  в неисключающем смысле — Володя мог читать и одновременное ехать в автобусе. Одно не исключает другого.

2. Рассмотрим  еще одно повествовательное предложение.  «Володя вчера наблюдал за  ходом матча с западной или  восточной трибуны.» Здесь союз  «или» имеет исключающий характер  — две описываемые ситуации исключают друг друга: нельзя наблюдать один и тот же матч одновременно с двух противоположных трибун.

     Соединение  двух простых высказываний A и B в одно составное с помощью союза «или», употребляемого в неисключающем смысле, называется логическим сложением или дизъюнкцией, а полученное составное высказывание — логической суммой.