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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ  НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

(НИУ «БелГУ»)

 

ФАКУЛЬТЕТ МАТЕМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

 

 

 

 

 

 

 

Реферат по дисциплине

 «Математическая логика» 

 

 

на тему: «Математическая логика в информатике»

 

 

 

 

 

 

 

 

 

 

Выполнил:

студент факультета МиИТ

группы 010804

Галайко А.И.

Преподаватель:

Витохина Н.Н.

 

 

 

 

 

 

 

 

 

 

Белгород 2013

 

Содержание:

Введение

1. Основы логики
1. Базовые логические элементы компьютера
2. Логические операции и таблицы истинности
3. Основные законы логики
2. Логика в информатике

2.1.    Логика в программировании

2.2.    Логика и искусственный интеллект

2.3.  Логика и логическое программирование

2.4.   Логика в базах данных

     Заключение

     Список используемой литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

Сущность логики - классическая логическая теория далеко не совершенна: основное её содержание формулируется  на особом, созданном специально для  своих целей языке, использует абсолютное предметное мышление. В ней не предполагается использование контроля прагматических ошибок, погрешностей нелинейностей используемых систем отсчёта, пограничных ошибок описания, релятивизма масштабирования и т. п. Вследствие чего принято считать нормальным факт наличия в её языке парадоксов и априорных утверждений, кустовых эффектов словаря и т. п. Подобно тому как умение говорить существовало ещё до возникновения науки грамматики, так и искусство правильно мыслить существовало задолго до науки логики. Логические операции: определение, классификация, доказательство, опровержение и др. нередко применяются каждым человеком в его мыслительной деятельности неосознанно и с погрешностями, некоторые склонны считать собственное мышление естественным процессом, не требующим анализа и контроля больше, чем, скажем, дыхание или движение. Реальное мышление не сводится просто к логической последовательности. В процессе решения возникающих задач важным оказывается, как правило, всё: и последовательность, и интуиция, и эмоции, и образное видение мира, и многое другое. Основная цель (функция) логики всегда оставалась неизменной: исследование того, как из одних утверждений можно выводить другие. При этом предполагается, что вывод зависит только от способа связи входящих в него утверждений и их строения, а не от их конкретного содержания.

Изучая, «что из чего следует», логика выявляет наиболее общие или, как говорят, формальные условия  правильного мышления. Сфера конкретных интересов логики существенно менялась на протяжении её истории.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Основы логики

 

Основными формами мышления являются понятие, суждение, умозаключение.

• Понятие – это форма мышления, выделяющая существенные признаки предмета или класса предметов, позволяющих отличить их от других.

Понятие имеет две  стороны: содержание и объем.

 

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

 

Объем понятия – множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятий.

• Утверждение – суждение, которое требуется доказать или опровергнуть
• Суждение (высказывание, утверждение) – это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними. Высказывание может быть либо истинным, либо ложным, и может быть либо простым, либо составным (сложным).
• Рассуждение – цепочка высказываний или утверждений, определенным образом связанных друг с другом
• Умозаключение – это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение.

 

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

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

Под высказыванием (суждением) будем понимать повествовательное  предложение, относительно которого можно  сказать, истинно или ложно.

В алгебре высказываний простым высказываниям ставятся в соответствии логические переменные, обозначаемые прописными буквами латинского алфавита.

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

• Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0)
• Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0)
• Логическая операция – способ построения сложного высказывания из данных высказываний, при котором значение истинности сложного высказывания полностью определяется значениями истинности исходных высказываний.

 

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:

• инверсия,
• конъюнкция,
• дизъюнкция,
• импликация и эквивалентность.

 

Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

 

• Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0).

 

1.1. Базовые логические элементы компьютера

 

 

                           Логический элемент И

конъюнктор

 

 

                          Логический элемент ИЛИ

дизъюнктор

 

 

 

   

Логический элемент НЕ

инвертор

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.2. Логические операции и таблицы истинности

 

Рис. 1.2.1.

 

Логическое  умножение - КОНЪЮНКЦИЯ  - это новое  сложное выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И. (Рис.1.2.1)

 

 

Рис. 1.2.2.

 

Логическое  сложение – ДИЗЪЮНКЦИЯ - это новое сложное выражение будет истинным тогда и только тогда, когда  истинно хотя бы одно из исходных (простых) выражений. Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ. (Рис.1.2.2)

 

 

 

 

 

Рис. 1.2.3.

 

Логическое  отрицание - ИНВЕРСИЯ - если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО. (Рис.1.2.3)

 

Рис. 1.2.4.

 

Логическое следование - ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом  "следовательно"  и  выражается словами ЕСЛИ … , ТО …( Рис.1.2.4).

 

 

Рис. 1.2.5.

 

 

Логическая  равнозначность - ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности"

Порядок выполнения логических операций в сложном логическом выражении:

1. инверсия

2. конъюнкция

3. дизъюнкция

4. импликация

5. эквивалентность

 

  Для изменения указанного порядка выполнения операций используются скобки.

 

 

 

 

 

 

 

 

 

 

 

 

3. Основные законы логики

 

Основные законы логики: А = А  – закон тождества

А & = 0 – закон непротиворечия

A Ú = 1 – закон исключенного третьего

= А – закон двойного отрицания

 

----------------------------------------------------------------------------------------------------

Свойства констант:    = 1                = 0

А Ú 0 = А        А & 0 = 0

А Ú 1 = 1         А & 1 = 1

----------------------------------------------------------------------------------------------------

Законы идемпотентности: А Ú А = А

          А & А = A

----------------------------------------------------------------------------------------------------

Законы коммутативности: А Ú В = В Ú А

          А & В = В & А

----------------------------------------------------------------------------------------------------

Законы ассоциативности: А Ú (В Ú С) = (АÚ В) Ú С

          А & (В & С) = (А & В) & С

----------------------------------------------------------------------------------------------------

Законы дистрибутивности: А Ú (В & С) = (АÚ В) & (А Ú С)

          А & (В Ú С) = (А & В) Ú (А& С)

----------------------------------------------------------------------------------------------------

Законы поглощения:  А Ú (А & В) = А

          А & (А Ú В) = А

----------------------------------------------------------------------------------------------------

Законы де Моргана:  

        

----------------------------------------------------------------------------------------------------

 

 

2. Логика в информатике

 

Логика в информатике  — это направления исследований и отрасли знания, где логика применяется  в информатике и искусственном  интеллекте. Логика оказалась гораздо  более эффективной в информатике, чем это было в математике.

Включаются следующие  основные применения:

• исследования в логике, вызванные развитием компьютерных наук. Например, аппликативные вычислительные системы, теория вычислений и модели вычислений;
• формальные методы и логика рассуждения о понятиях. Например, семантическая сеть, семантическая Web;
• булева логика и алгебра для разработки аппаратного обеспечения компьютеров;
• решение задач и структурное программирование для разработки прикладных программ и создания сложных систем программного обеспечения
• доказательное программирование - технология разработки алгоритмов и программ с доказательствами правильности алгоритмов;
• фундаментальные понятия и представления для компьютерных наук, которые являются естественной областью для формальной логики. Например, семантика языков программирования;
• логика знания и предположения. Например, искусственный интеллект;
• Язык Пролог и логическое программирование для создания баз знаний и экспертных систем и исследований в сфере искусственного интеллекта;
• логическое программирование для описания логических моделей баз знаний и логических процедур вывода и принятия решений;
• логика для описания пространственного положения и перемещения;
• логика в информационных технологиях. Например, реляционная модель данных. реляционные СУБД, реляционная алгебра, реляционное исчисление;
• логика вычислений с объектами. Например, комбинаторная логика, суперкомбинаторы;
• логика для компилирования программного кода и его оптимизации. Например, категориальная абстрактная машина;
• логика для эквивалентного преобразования объектов. Например, λ-исчисление;
• переизложение логики и математики в терминах, понятных специалистам в компьютинге и компьютерных науках.