Математическая логика и теория алгоритмов Могилев 2013. - презентация

1 Математическая логика и теория алгоритмов Могилев 2013

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

3 Характеристики Применение в информатике Алгебра логики является разделом активно развивающейся сегодня науки - дискретной математики. свойства функций, и аргументы, и значения принадлежат заданному двухэлементному множеству (например, {0, 1}). Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, {0, 1}). Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика». Алгебра логики является разделом активно развивающейся сегодня науки - дискретной математики. свойства функций, и аргументы, и значения принадлежат заданному двухэлементному множеству (например, {0, 1}). Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, {0, 1}). Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика». Математический аппарат алгебры логики широко используется в информатике, в частности, в таких ее разделах, как проектирование ЭВМ, теория автоматов, теория алгоритмов, теория информации, целочисленное программирование и т. д. Лекция 1 – основные понятия

4 Основатель алгебры логики Большой вклад в становление и развитие алгебры логики внесли знаменитые ученые-логики Это английский математик XIX столетия Джордж Буль ( ). в виде некоторой «алгебры», подобно алгебре чисел, но не сводящейся к ней. Он построил один из разделов формальной логики в виде некоторой «алгебры», подобно алгебре чисел, но не сводящейся к ней. Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только над числами, но и над другими математическими объектами. Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т. д. Это английский математик XIX столетия Джордж Буль ( ). в виде некоторой «алгебры», подобно алгебре чисел, но не сводящейся к ней. Он построил один из разделов формальной логики в виде некоторой «алгебры», подобно алгебре чисел, но не сводящейся к ней. Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только над числами, но и над другими математическими объектами. Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т. д. Андрей Андреевич Марков Андрей Николаевич Колмогоров Августус де Морган ( ), Уильям Стенли Джевонс ( ), Платон Сергеевич Порецкий ( ), Чарлз Сандерс Пирс ( ), Андрей Андреевич Марков ( ), Андрей Николаевич Колмогоров ( ) и др. Клод Шеннон функционирования релейно- контактных и электронно-ламповых схем. В 1938 году американский математик и инженер Клод Шеннон ( ) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно- контактных и электронно-ламповых схем. Андрей Андреевич Марков Андрей Николаевич Колмогоров Августус де Морган ( ), Уильям Стенли Джевонс ( ), Платон Сергеевич Порецкий ( ), Чарлз Сандерс Пирс ( ), Андрей Андреевич Марков ( ), Андрей Николаевич Колмогоров ( ) и др. Клод Шеннон функционирования релейно- контактных и электронно-ламповых схем. В 1938 году американский математик и инженер Клод Шеннон ( ) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно- контактных и электронно-ламповых схем.

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

6 Классическая логика Классическая логика раздел современной математической логики, классическую логику высказываний классическую логику предикатов. Классическая логика - раздел современной математической логики, включающий классическую логику высказываний и классическую логику предикатов. Классическая логика на принцип двузначности, Классическая логика опирается на принцип двузначности, в соответствии с которым всякое высказывание является или истинным, или ложным. Классическая логика раздел современной математической логики, классическую логику высказываний классическую логику предикатов. Классическая логика - раздел современной математической логики, включающий классическую логику высказываний и классическую логику предикатов. Классическая логика на принцип двузначности, Классическая логика опирается на принцип двузначности, в соответствии с которым всякое высказывание является или истинным, или ложным.

7 ЛОГИКА ВЫСКАЗЫВАНИЙ ЛОГИКА ВЫСКАЗЫВАНИЙ – это логических форм сложных высказываний, образованных из элементарных высказываний с помощью ОПЕРАТОРОВ-связок, аналогичных союзам И, ИЛИ, НЕ, "если..., то", "если..., и только если " и др. ЛОГИКА ВЫСКАЗЫВАНИЙ – это раздел современной (математической) логики, посвященный изучению логических форм сложных высказываний, образованных из элементарных высказываний с помощью ОПЕРАТОРОВ-связок, аналогичных союзам И, ИЛИ, НЕ, "если..., то", "если..., и только если " и др. как целые, не расчленяются на части Элементарные высказывания при этом рассматриваются как целые, т.е. не расчленяются на части (такие, как субъект и предикат). ЛОГИКА ВЫСКАЗЫВАНИЙ – это логических форм сложных высказываний, образованных из элементарных высказываний с помощью ОПЕРАТОРОВ-связок, аналогичных союзам И, ИЛИ, НЕ, "если..., то", "если..., и только если " и др. ЛОГИКА ВЫСКАЗЫВАНИЙ – это раздел современной (математической) логики, посвященный изучению логических форм сложных высказываний, образованных из элементарных высказываний с помощью ОПЕРАТОРОВ-связок, аналогичных союзам И, ИЛИ, НЕ, "если..., то", "если..., и только если " и др. как целые, не расчленяются на части Элементарные высказывания при этом рассматриваются как целые, т.е. не расчленяются на части (такие, как субъект и предикат).

8 ЛОГИКА ВЫСКАЗЫВАНИЙ ЛОГИКА ВЫСКАЗЫВАНИЙ высказывания (пропозиции, предложения) ЛОГИКА ВЫСКАЗЫВАНИЙ рассматривает высказывания (пропозиции, предложения) только с точки зрения их истинности или ложности. ЛОГИКА ВЫСКАЗЫВАНИЙ = ЛОГИКА СУЖДЕНИЙ = ПРОПОЗИЦИОНАЛЬНАЯ ЛОГИКА = = ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ = =ИСЧИСЛЕНИЕ ПРЕДЛОЖЕНИЙ = =ПРОПОЗИЦИОНАЛЬНОЕ ИСЧИСЛЕНИЕ ЛОГИКА ВЫСКАЗЫВАНИЙ высказывания (пропозиции, предложения) ЛОГИКА ВЫСКАЗЫВАНИЙ рассматривает высказывания (пропозиции, предложения) только с точки зрения их истинности или ложности. ЛОГИКА ВЫСКАЗЫВАНИЙ = ЛОГИКА СУЖДЕНИЙ = ПРОПОЗИЦИОНАЛЬНАЯ ЛОГИКА = = ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ = =ИСЧИСЛЕНИЕ ПРЕДЛОЖЕНИЙ = =ПРОПОЗИЦИОНАЛЬНОЕ ИСЧИСЛЕНИЕ

9 Основной объект логики высказываний высказывание. ВЫСКАЗЫВАНИЕ предложение в УТВЕРДИТЕЛЬНОЙ ФОРМЕ, что оно истинно или ложно. ВЫСКАЗЫВАНИЕ это предложение в УТВЕРДИТЕЛЬНОЙ ФОРМЕ, о котором имеет смысл говорить, что оно истинно или ложно. Цепочка высказываний: Основной объект логики высказываний высказывание. ВЫСКАЗЫВАНИЕ предложение в УТВЕРДИТЕЛЬНОЙ ФОРМЕ, что оно истинно или ложно. ВЫСКАЗЫВАНИЕ это предложение в УТВЕРДИТЕЛЬНОЙ ФОРМЕ, о котором имеет смысл говорить, что оно истинно или ложно. Цепочка высказываний: ВЫСКАЗЫВАНИЕ- ПОСЫЛКА ВЫСКАЗЫВАНИЕ- СЛЕДСТВИЕ ПОСЫЛКА 1 ПОСЫЛКА 2 СЛЕДСТВИЕ

10 Из элементарных высказываний, для которых вопрос о присвоении им одного из значений «ИСТИНА» или «ЛОЖЬ» считается заранее решённым,с помощью логических операций строятся сложные высказывания (аналоги сложносочинённых и сложноподчинённых предложений),значения истинности которых однозначно определяются значениями истинности исходных высказываний примененными логическими операциями. Из элементарных высказываний, для которых вопрос о присвоении им одного из значений «ИСТИНА» или «ЛОЖЬ» считается заранее решённым, с помощью логических операций строятся сложные высказывания (аналоги сложносочинённых и сложноподчинённых предложений), значения истинности которых однозначно определяются значениями истинности исходных высказываний и примененными логическими операциями.

11 Высказывания-тавтологии Высказывания-тавтологии с «естественной» интерпретацией высказываний свойствами логич. операций, тождественно-истинными истинными при всех распределениях истинностных значений исходных элементарных формул); тавтологиями Высказывания-тавтологии В соответствии с «естественной» интерпретацией высказываний и свойствами логич. операций, посредством которых они построены, некоторые из полученных высказываний оказываются тождественно-истинными (т. е. истинными при всех распределениях истинностных значений исходных элементарных формул); их называют тавтологиями. Высказывания-тавтологии выражают логические законы; их выявление одна из основных задач Логики высказываний.

12 ЗадачиЛОГИКИ ВЫСКАЗЫВАНИЙ Задачи ЛОГИКИ ВЫСКАЗЫВАНИЙ ЛОГИКИ ВЫСКАЗЫВАНИЙ приведение сложных высказываний к такой форме, стало возможным алгоритмическое решение вопросов логического характера в конкретной предметной области применение автоматических методов решения. Задачей ЛОГИКИ ВЫСКАЗЫВАНИЙ является приведение сложных высказываний к такой форме, чтобы для них стало возможным алгоритмическое решение вопросов логического характера в конкретной предметной области и применение автоматических методов решения. вывода логических следствий из данных посылокпоиска доказательства выражений, выразимых в этой специальной уточненной форме; К числу таких вопросов относятся прежде всего вопросы вывода логических следствий из данных посылок или поиска доказательства выражений, выразимых в этой специальной уточненной форме; можно ли упростить форму выражения данного высказывания, и мн. др. ЛОГИКИ ВЫСКАЗЫВАНИЙ приведение сложных высказываний к такой форме, стало возможным алгоритмическое решение вопросов логического характера в конкретной предметной области применение автоматических методов решения. Задачей ЛОГИКИ ВЫСКАЗЫВАНИЙ является приведение сложных высказываний к такой форме, чтобы для них стало возможным алгоритмическое решение вопросов логического характера в конкретной предметной области и применение автоматических методов решения. вывода логических следствий из данных посылокпоиска доказательства выражений, выразимых в этой специальной уточненной форме; К числу таких вопросов относятся прежде всего вопросы вывода логических следствий из данных посылок или поиска доказательства выражений, выразимых в этой специальной уточненной форме; можно ли упростить форму выражения данного высказывания, и мн. др.

13 Роль логики высказываний разнообразные технические применения в современном автоматостроении, в т.ч. и при построении (имитирующих работу нервных сетей мозга) надежных схем из не вполне надежных элементов, которым занимается новая наука – бионика; В логике высказываний такие задачи являются разрешимыми, и поэтому именно она особенно часто находит разнообразные технические применения в современном автоматостроении, в т.ч. и при построении (имитирующих работу нервных сетей мозга) надежных схем из не вполне надежных элементов, которым занимается новая наука – бионика; именно к логике высказываний обычно производится (непосредственно или опосредованно) сведéние проблем из более сложных частей логики в тех случаях, когда они допускают алгоритмическое решение. Несмотря на ее элементарный характер логика высказываний играет поэтому важную роль в современной логике. разнообразные технические применения в современном автоматостроении, в т.ч. и при построении (имитирующих работу нервных сетей мозга) надежных схем из не вполне надежных элементов, которым занимается новая наука – бионика; В логике высказываний такие задачи являются разрешимыми, и поэтому именно она особенно часто находит разнообразные технические применения в современном автоматостроении, в т.ч. и при построении (имитирующих работу нервных сетей мозга) надежных схем из не вполне надежных элементов, которым занимается новая наука – бионика; именно к логике высказываний обычно производится (непосредственно или опосредованно) сведéние проблем из более сложных частей логики в тех случаях, когда они допускают алгоритмическое решение. Несмотря на ее элементарный характер логика высказываний играет поэтому важную роль в современной логике.

14 Язык логики высказываний Рассмотрим язык логики высказываний, состоящий из алфавита "букв" этого "языка" и правил написания "слов" (формул, т.е. сложных логических выражений) в этом алфавите. Алфавит может выбираться при этом по-разному, но он обычно содержит: 1) "буквы", называемые "пропозициональными переменными" (число которых предполагается неограниченным); 2) в алфавит должны входить символы, являющиеся знаками для логич. связок, таких, как конъюнкция, дизъюнкция, импликация, отрицание (+ эквиваленция); 3) большинство алфавитов Логики высказываний содержит также вспомогательные знаки: обычно скобки или точки. Рассмотрим язык логики высказываний, состоящий из алфавита "букв" этого "языка" и правил написания "слов" (формул, т.е. сложных логических выражений) в этом алфавите. Алфавит может выбираться при этом по-разному, но он обычно содержит: 1) "буквы", называемые "пропозициональными переменными" (число которых предполагается неограниченным); 2) в алфавит должны входить символы, являющиеся знаками для логич. связок, таких, как конъюнкция, дизъюнкция, импликация, отрицание (+ эквиваленция); 3) большинство алфавитов Логики высказываний содержит также вспомогательные знаки: обычно скобки или точки.

15 Язык логики высказываний В алфавит вводятся иногда и знаки для постоянных: "истины" и "лжи" (1, 0 или 2, 0, или др.) Понятие формулы Логики высказываний легче всего определяется для алфавитов, в состав которых входят и скобки. Пусть алфавит состоит из пропозициональных переменных, знаков конъюнкции (&), дизъюнкции (/), импликации ( ), отрицания ( ) и скобок, тогда понятие формулы можно определить так: (1)Всякая пропозициональная переменная есть формула; (2)Если А и В – формулы, то (А & В), (А / В), (A B) – формулы; (3)если А есть формула, то А – тоже формула. В алфавит вводятся иногда и знаки для постоянных: "истины" и "лжи" (1, 0 или 2, 0, или др.) Понятие формулы Логики высказываний легче всего определяется для алфавитов, в состав которых входят и скобки. Пусть алфавит состоит из пропозициональных переменных, знаков конъюнкции (&), дизъюнкции (/), импликации ( ), отрицания ( ) и скобок, тогда понятие формулы можно определить так: (1)Всякая пропозициональная переменная есть формула; (2)Если А и В – формулы, то (А & В), (А / В), (A B) – формулы; (3)если А есть формула, то А – тоже формула.