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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: реферат. Добавлен: 03.07.2012. Сдан: 2011. Страниц: 7. Уникальность по antiplagiat.ru: < 30%

Описание (план):


МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
КУРГАНСКИЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Кафедра … 
 
 
 
 
 
 

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

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

Тюмень 
2009 
Содержание

    Стр.
1. История возникновения  математической логики 3
2. Основное содержание, формулы, элементы, символы 5
3. Примеры задач 16
4. Применение  математической логики 19
5. Список литературы 26
 

    История возникновения математической логики
       Математическая  логика тесно связана с логикой  и обязана ей своим возникновением. Основы логики, науки о законах и формах человеческого мышления (отсюда одно из ее названий - формальная логика), были заложены величайшим древнегреческим философом Аристотелем (384—322 гг. до н. э.), который в своих трактатах обстоятельно исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления, в том числе законы противоречия и исключения третьего. Вклад Аристотеля в логику весьма велик, недаром другое ее название - аристотелева логика. Еще сам Аристотель заметил, что между созданной им наукой и математикой (тогда она именовалась арифметикой) много общего. Он пытался соединить две эти науки, а именно свести размышление, или, вернее, умозаключение, к вычислению на основании исходных положений. В одном из своих трактатов Аристотель вплотную приблизился к одному из разделов математической логики - теории доказательств.
       В дальнейшем многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646 - 1716), указавший пути для перевода логики «из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно» . Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав . При этом в своих работах Лейбниц затрагивал и двоичную систему счисления.
       Следует отметить, что идея использования  двух символов для кодирования информации очень стара. Австралийские аборигены  считали двойками, некоторые племена охотников-сборщиков Новой Гвинеи и Южной Америки тоже пользовались двоичной системой счета. В некоторых африканских племенах передают сообщения с помощью барабанов в виде комбинаций звонких и глухих ударов. Знакомый всем пример двухсимвольного кодирования - азбука Морзе, где буквы алфавита представлены определенными сочетаниями точек и тире.
       После Лейбница исследования в этой области  вели многие выдающиеся ученые, однако настоящий успех пришел здесь  к английскому математику-самоучке Джорджу Булю (1815—1864), целеустремленность которого не знала границ. Материальное положение родителей Джорджа (отец которого был сапожным мастером) позволило ему окончить лишь начальную школу для бедняков. Спустя какое-то время Буль, сменив несколько профессий, открыл маленькую школу, где сам преподавал. Он много времени уделял самообразованию и вскоре увлекся идеями символической логики. В 1847 году Буль опубликовал статью «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений», а в 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей».
         Буль изобрел своеобразную алгебру  - систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ).
       Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в XX столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.
   Отдельные положения работ Буля в той  или иной мере затрагивались и  до, и после него другими математиками и логиками. Однако сегодня в данной области именно труды Джорджа Буля причисляются к математической классике, а сам он по праву считается основателем математической логики и тем более важнейших ее разделов - алгебры логики (булевой алгебры) и алгебры высказываний.
       Большой вклад в развитие логики внесли и  русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947).
       В XX веке огромную роль в развитии математической логики сыграл Д. Гильберт (1862-1943), предложивший программу формализации математики, связанную с разработкой оснований  самой математики. Наконец, в последние  десятилетия XX века бурное развитие математической логики было обусловлено развитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К. Клини, А. Черч, А.А Марков, П.С. Новиков и многие другие).  

       2. Основное содержание, формулы, элементы, символы
     Алгебра логики (логика высказываний) - один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях высказываний.
     Высказывание - это термин математической логики, которым обозначается предложение какого-либо языка (естественного или искусственного), рассматриваемого лишь в связи с его истинностью. Например:
«Земля  — планета солнечной системы.»  Истина 
«2+8<5»  Ложь 
«Всякий квадрат есть параллелограмм.»  Истина 
«Каждый параллелограмм есть квадрат.» Ложь 
     Приведем  примеры, предложений не являющихся высказываниями:
«Посмотрите в окно.» 
«Который  час?» 
«2x+7>12»
     Отличительным признаком любого высказывания является его свойство быть истинным или ложным, а этим свойством три вышеприведенных предложения не обладают.
     Используя простые высказывания, можно образовывать сложные, или составные, высказывания, в которые простые входят в качестве элементарных составляющих. В образовании сложных высказываний используются слова: и, или, тогда и только тогда, когда (в том и только в том случае), если …, то …, нет.
     Рассмотрим  несколько примеров сложных высказываний:
«Если идет дождь, то солнце не светит.» 
« Если ветер дует, то нет дождя.» 
     Основная  задача логики высказываний заключается  в том, чтобы на основании истинности или ложности простых высказываний определить истинность или ложность сложных высказываний.
2.1. Таблицы истинности. Логические функции. Основные логические операции
     Условимся, простые высказывания называть логическими переменными и обозначать большими буквами и, если высказывание истинно, будем писать A=1, а если ложно, то A=0.
     Использование 0 и 1 подчеркивает некоторое соответствие между значениями логических переменных и функций в алгебре логики и цифрами в двоичной системе  счисления. Это позволяет описывать работу логических схем ЭВМ и проводить их анализ и синтез с помощью математического аппарата алгебры логики.
     Любое устройство ЭВМ, выполняющее действия над двоичными числами, можно  рассмотреть как некоторый функциональный преобразователь. Причем числа на входе - значения входных логических переменных, а число на выходе - значение логической функции, которое получено в результате выполнения определенных операций. Таким образом, этот преобразователь реализует некоторую логическую функцию.
     Значения  логической функции для разных сочетаний  значений входных переменных - или, как это иначе называют, наборов входных переменных - обычно задаются специальной таблицей. Такая таблица называется таблицей истинности. Количество наборов входных переменных (Q) можно определить по формуле:
Q=2n, где n — количество входных переменных.
Простейшим  примером логической функции является функция одной переменной .


      
     Интересной  является только функция F2(X). О ней мы говорим чуть позже.
Функции двух аргументов. Их может быть 16.



     Если  у функции 3 аргумента, то число возможных  функций возрастает до 256, поэтому  более сложные логические функции  задаются с помощью простых функций  одного или двух аргументов. Для  выражения сложных логических функций используют более простые, и оказывается, что можно использовать не все элементарные функции, а только часть.
     Рассмотрим  подробнее наиболее интересные логические функции одной и двух переменных.
     Логическое  умножение. (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 – фр. равноценное) или равнозначность, соответствует оборотам речи «тогда и только тогда» и «в том и только в том случае», обозначается , или или
     Выражение истинно в том и только в том случае, когда оба исходных высказывания одновременно истинны или одновременно ложны.
     «Петя выучит уроки тогда и только тогда, когда Пете поставят хорошую отметку.» 
В русском  языке операции эквивалентности также соответствует речевой оборот «A необходимо и достаточно B».
     Представление эквивалентности  через конъюнкцию, дизъюнкцию и инверсию
     
     
     Строгая дизъюнкция или Сложение по модулю «2», соответствует оборотам речи «или…, или…» или «либо…, либо…», и обозначается

 





2.2. Законы логики. Упрощение логических выражений
     Если  у двух логических функций совпадают  таблицы истинности, то есть на всех наборах значений входных переменных они принимают одинаковое значение, то их называют равносильными или эквивалентными. Это обозначается знаком =.
     Логические  функции, истинные на всех наборах значений входных переменных, называются тождественно-истинными.
     Логические  функции, ложные на всех наборах значений входных переменных, называются тождественно-ложными.
     Среди многочисленных законов логики есть четыре основных. Для трех из них  можно найти аналогию в алгебре  чисел.


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

3. Примеры решения задач по математической логике
Пример 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?Д, так как при Х=Д, У=А и, значит, Ху =Да, что противоречит условию. Значит, Х=А, а У=Д. Поэтому истинной является формула Ка&Ад&Дф&Фк.
     Следовательно, мальчики с именами Карл, Альберт, Дитрих и Фридрих имеют фамилии  соответственно Альберт, Дитрих, Фридрих и Карл. 

4. Применение математической логики
     Объединение математико-логической установки с  иными математическими подходами, прежде всего с вероятностно-статистическими  идеями и методами - на фоне глубокого интереса к вычислительным приборам, - было во многом определяющим в формировании замысла кибернетики, как комплексного научного направления, имеющего своим предметом процессы.
     В ряде случаев используется технический аппарат математической логики (синтез релейно-контактных схем); сверх того, что особенно важно, идеи математической логики это, конечно же, в теории алгоритмов, но также и всей науки в целом и свойственный ей стиль мышления оказали и продолжают оказывать очень большое влияние на те своеобразные области деятельности, содержанием которых является автоматическая переработка информации (информатика), использование в криптографии и   автоматизация процессов управления (кибернетика).
     Информатика - это наука, которая изучает компьютер, а также взаимодействие компьютера с человеком.
     Строительство логических машин – интересная глава  истории логики и кибернетики. В  ней запечатлены первые проекты  создания искусственного разума и первые споры о возможности этого.
     Идея  логических машин появилась в 13 веке у испанского схоластика Раймунда Луллия, рассматривалась затем Лейбницем и получило новое развитие в 19 веке, после возникновения математической логики. В 1870 году английский философ и экономист Вильям Стэнли Джевонс построил в Манчестере “логическое пианино”, которое извлекало из алгебраически записанных посылок следствия, выделяя допустимые комбинации терминов. Это называют также разложением высказываний на конституанты. Важно отметить возможность практического применения логической машины для решения сложных логических задач.
     Современные универсальные вычислительные машины являются вместе с тем логическими машинами. Именно введение логических операций сделало их такими гибкими; оно же позволяет им моделировать рассуждения. Таким образом, арифметическая ветвь “разумных автоматов” соединились с логической. В 20-е годы, однако, формальная логика представлялась слишком абстрактной о метафизической для приложения к жизни. Между тем уже тогда можно было предвидеть внедрение логических исчислений в технику.
     Математическая  логика облегчает механизацию умственного труда. Нынешние машины выполняют гораздо более сложные логические операции, нежели их скромные прототипы начала века.
     Проблема  искусственного разума сложна и многогранна. Вероятно, не ошибёмся, если скажем, что  окончательные границы механизации мысли можно установить лишь экспериментальным путём. Заметим ещё, что в современной кибернетики обсуждается возможность моделирования не только формальных, но и содержательных мыслительных процессов.                                                                                              
     4.1 Математическая логика в технике.
     Роль  логической обработки бинарных данных на современном этапе развития вычислительной техники существенно возросла. Это  связано, в первую очередь, с созданием  технически систем. реализующих в том или ином виде технологии  получения и  накопления знаний, моделированием отдельных  интеллектуальных функций человека. Ядром таких систем являются мощные ЭВМ и вычислительные комплексы.  Кроме того, существует  большой класс прикладных задач, которые можно свести к решению логических задач, например, обработка и синтез изображений, транспортные задачи. Требуемая производительность вычислительных средств достигается путем распараллеливания и конвейеризации вычислительных процессов. Это реализуется, как правило, на основе сверхбольших интегральных, схем (СБИС). Однако технология СБИС и их структура предъявляет ряд специфических  требований к алгоритмам, а именно: регулярность, параллельно - поточная организация вычислений, сверхлинейная операционная сложность (многократное использование каждого элемента входных данных), локальность связей вычислений, двумерность  пространства реализации вычислений. Эти требования обусловливают необходимость решения проблемы эффективного  “погружения” алгоритма в вычислительную среду, или, как еще принято говорить, - отображение алгоритма в архитектуру вычислительных средств. В настоящее время доказана ошибочность ранее широко распространенных взглядов, состоящих в том, что переход на параллельно -конвейерные  архитектуры ЭВМ потребуют лишь н
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.