МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Данная работа использовалась при изучении раздела математическая логика. Работа состоит из пяти разделов: основные этапы развития логики, формальная логика, основные понятия логики, логические операции, законы логики. Основное внимание уделено истории развития логики, как науки, Портретная галерея ученых внесших вклад в развитие логики.

Вы уже знаете о суперспособностях современного учителя?

Тратить минимум сил на подготовку и проведение уроков.

Быстро и объективно проверять знания учащихся.

Сделать изучение нового материала максимально понятным.

Избавить себя от подбора заданий и их проверки после уроков.

Наладить дисциплину на своих уроках.

Получить возможность работать творчески.

=> ПОЛУЧИТЬ СУПЕРСПОСОБНОСТИ УЧИТЕЛЯ <=

Просмотр содержимого документа
«МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ »

DVS films – Saratov - 2012

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

DVS films – Saratov - 2012

Содержание

Основные этапы развития логики

Формальная логика

Основные понятия логики

Законы логики

DVS films – Saratov - 2012

Понятие логики

Логика (др.-греч. λογική — «наука о правильном мышлении», «искусство рассуждения» от λόγος — «речь» ) — наука о формах, методах и законах интеллектуальной познавательной деятельности, формализуемых с помощью логического языка.

Наука о способах

Логика

Наука о формах

DVS films – Saratov - 2012

Основные этапы развития логики

Логика как самостоятельная наука начала формироваться в Индии, Китае, Греции задолго до нашей эры.
Логика как самостоятельная наука начала формироваться в Индии, Китае, Греции задолго до нашей эры.

Наиболее обстоятельно теоретические проблемы логики были разработаны и систематизированы в Древней Греции.
Наиболее обстоятельно теоретические проблемы логики были разработаны и систематизированы в Древней Греции.

DVS films – Saratov - 2012

Основные этапы развития логики

Древняя Греция

Китай

Индия

Начало истории логики

«Органон» Аристотеля

– первые труды по

формальной логике

Развитие логики Аристотеля

исламскими логиками

Схоластическая логика. Представители:

Уильям Оккама,

Альберт Саксонский и Уолтер Берли.

Дж. Буль,

О. де Морган,

Г. Фреге, Ч. Пирс

Внесли огромный

вклад в развитие

символической

логики

Развитие и подъем

средневековой

европейской логики до XIV в .

Приминение математических методов для обнаружения истинного значения выражений естественного языка

Конец XIX – нач.XX вв. –

заложены основы

математической

(символической) логики

DVS films – Saratov - 2012

Древняя Греция

Демокрит

(460-370 гг. до н. э.).

Он - создатель системы логики, которая была отражена в специальном трактате «О логике, или Каноны».

DVS films – Saratov - 2012

Древняя Греция

Сократ

(около 470-399 гг. до н. э.)

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

DVS films – Saratov - 2012

Древняя Греция

Платон

(427-347 гг. до н. э.).

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

DVS films – Saratov - 2012

Древняя Греция

Аристотель

(384-322 гг. до н. э.).

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

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

DVS films – Saratov - 2012

Древняя Греция

DVS films – Saratov - 2012

Логика в средневековье

У. Оккам

(1285-1349)

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

DVS films – Saratov - 2012

Арабоязычная логика

Аль-Фараби (870-950)

Прокомментировал весь аристотелевский «Органон». Его логика направлена на анализ научного мышления. Выделяет в логике две ступени: одна охватывает представления и понятия; другая - теорию суждений, выводов и доказательств.

DVS films – Saratov - 2012

Арабоязычная логика

Ибн Сина (980-1037)

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

DVS films – Saratov - 2012

Эпоха Возрождения (XV-XVI вв.)

Ф. Бекон

(1561-1626).

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

Он предложил использовать логику в качестве эффективного орудия для осуществления научных открытий.

DVS films – Saratov - 2012

Эпоха Возрождения (XV-XVI вв.)

Р. Декарт

(1596-1650).

1) истинно лишь то, что познано, проверено и доказано; 2) расчленять сложное на простое; 3) восходить от простого к сложному, от более очевидного к менее очевидному; 4) исследовать предмет во всех деталях.

DVS films – Saratov - 2012

Немецкая классическая философия

И. Кант

(1724-1804)

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

DVS films – Saratov - 2012

Немецкая классическая философия

Г. Гегель

(1770-1831)

Свое отношение к этой науке, как «метафизической», он строил исходя из объективно-идеалистической идеи о тождестве законов мышления и бытия.

DVS films – Saratov - 2012

Российская школа логики

М.И. Каринский

(1840-1917)

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

DVS films – Saratov - 2012

Цели и задачи логики

Основная цель (функция) логики - исследование того, как из одних утверждений можно выводить другие.

Цель

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

Задача

Логика служит одним из инструментов почти любой науки

Вывод

DVS films – Saratov - 2012

Формальная логика

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

Основоположником формальной логики является Аристотель , чьи труды о логике

в дальнейшем стали основой данного течения.

В истории философии — отдельный раздел или направление логики конца XIX—начала XX века.

DVS films – Saratov - 2012

Основные понятия логики

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

Утверждение – суждение, которое требуется доказать или опровергнуть.

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

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

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

DVS films – Saratov - 2012

Логические законы

Закон противоречия — «не противоречь сам себе». Два несовместимых суждения не могут быть одновременно истинными.
Закон исключенного третьего — «А или не-А истинно, третьего не дано». Два противоположных суждения не могут быть одновременно ложными (либо истинными), одно из них необходимо истинно (либо ложно).
Зако́н то́ждества —«Если А, то А, или А ≡ А». Предмет суждения должен оставаться тождественным самому себе в этом суждении.

Простой категорический силлоги́зм (греч. συλλογισμός) — рассуждение, состоящее из трёх простых атрибутивных высказываний: двух посылок и одного заключения .

Посылки силлогизма разделяются на бо́льшую (которая содержит предикат заключения) и меньшую (которая содержит субъект заключения).

DVS films – Saratov - 2012

Простой категорический силлогизм

В силлогизм входит три термина:

S — меньший термин: субъект заключения (входит также в меньшую посылку);

P — больший термин: предикат заключения (входит также в большую посылку);

M — средний термин: входит в обе посылки, но не входит в заключение.

Всякий человек смертен

бо́льшая посылка

Сократ смертен

заключение

Сократ — человек

меньшая посылка

DVS films – Saratov - 2012

Аналогия

Анало́гия (др.-греч. ἀναλογἰα — соответствие, сходство) — подобие, равенство отношений; сходство предметов (явлений, процессов) в каких-либо свойствах, а также познание путём сравнения .

Между сравниваемыми вещами должно иметься как различие, так и подобие; то, что является основой сравнения, должно быть более знакомым, чем то, что подлежит сравнению.

Пример: Два куба.

Одинаковая величина и форма –

основа сравнения , наиболее

явный общий признак.

Сравниваемые признаки

предметов – различные между

собой оттенки одного цвета.

Модель аналогии (лат. modus — образец, копия, образ) — предметная,

математическая или абстрактная система, имитирующая или отображающая

принципы внутренней организации, функционирования, особенностей

исследуемого объекта (оригинала), непосредственное изучение, которого,

по разным причинам, невозможно или усложнено.

DVS films – Saratov - 2012

Доказательство

Доказательство — это совокупность логических приемов обоснования истинности какого-либо суждения с помощью других истинных и связанных с ним суждений.

Структура доказательства:

Тезис — утверждение, истинность которого надо доказать

Аргументы и факты — это те истинные суждения, которыми пользуются при доказательстве тезиса

Демонстрация (форма доказательства) — способ обоснованной логической связи между утверждаемым тезисом и аргументами

Виды

Прямое

Виды

Прямое

образованны из простых

высказываний с

помощью логических

связок (операций).

DVS films – Saratov - 2012

Высказывания

Высказыванием является повествовательное предложение, которое формализует некоторое выражение мысли.

Это утверждение, которому всегда можно поставить в соответствие одно из двух логических значений: истина или ложь.

Пример:

A(x) = «В городе x идет дождь.»

A — высказывательная форма, x — объект.

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

При подстановке вместо переменной какого-либо значения высказывательная форма превращается в высказывание.

Виды

Элементарные

Виды

DVS films – Saratov - 2012

Логические операции

Основные операции над логическими высказываниями:

Дизъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно.

Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ

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

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

DVS films – Saratov - 2012

Логические операции

Отрицание логического высказывания — логическое высказывание, принимающее значение «истинно», если исходное высказывание ложно, и наоборот.

Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

неА

Импликация двух логических высказываний A и B — логическое высказывание, ложное только тогда, когда B ложно, а A истинно.

Обозначается символом "следовательно" и выражается словами ЕСЛИ … , ТО …

Равносильность (эквивалентность) двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны.

www.themegallery.com

Операции над высказываниями

РАЗМИНКА

www.themegallery.com

Операции над высказываниями

Формула является тождественно истинной (тождественно ложной) , если она истинна (ложна) при любых значениях входящих в неё переменных.

Задача 1.1

Показать, что операция

есть тождественно истинная, а

- тождественная ложь.

не А

www.themegallery.com

Операции над высказываниями

⌐ А

⌐ В

⌐ В→⌐А

А → В

DVS films – Saratov - 2012

Операции над высказываниями

А ≈ В

А→В

В→А

(А→В)и(В→А)

DVS films – Saratov - 2012

Операции над высказываниями

б)

Решение:

а) А=1, В = 0. 1 ↔ ┐0 = 1 ↔ 1 = 1;

б) А=1, В = 0. ┐0 ↔ ┐1 = 1 ↔ 0 = 0;

DVS films – Saratov - 2012

Операции над высказываниями

Решение:

Если треугольник равнобедренный и неравносторонний, то неверно, что он неравнобедренный.

DVS films – Saratov - 2012

Операции над высказываниями

Решение:

Это число либо целое и простое, либо положительное и делящееся на 3.

DVS films – Saratov - 2012

Операции над высказываниями

Если в треугольнике любая его медиана не является высотой и биссектрисой, то этот треугольник не равнобедренный и не равносторонний.

Решение:

А: «В треугольнике некоторая его медиана является высотой»;

В: «В треугольнике некоторая его медиана является биссектрисой»;

С: «Этот треугольник равнобедренный»;

D: «Этот треугольник равносторонний».

DVS films – Saratov - 2012

Операции над высказываниями

б)

Решение:

а) По определению дизъюнкция двух высказываний истинна тогда и только тогда, когда по меньшей мере одно из этих высказываний истинно. Следовательно, высказывание A v 1 истинно, независимо от логического значения высказывания А.

б) Ясно, что высказывания А и ┐А имеют противоположные логические значения (т.е. О и 1 или 1 и 0). Поскольку эквивалентность двух высказываний истинна тогда и только тогда, когда эти высказывания имеют одинаковые значения истинности, то эквивалентность А↔┐А высказываний А и ┐A ложна, независимо от значения истинности высказывания А.

DVS films – Saratov - 2012

Законы логики

DVS films – Saratov - 2012

Законы логики

Методы доказательства законов алгебры логики

1 способ . Логические рассуждения

Докажем путем логических рассуждений первый закон поглощения:

Покажем, что если правая часть данного выражения истинна, то и левая часть тоже истинна. Пусть правая часть истинна, то есть х = 1, тогда в левой части получаем дизъюнкцию, один из аргументов которой – истина. Тогда по определению дизъюнкции и вся левая часть истинна. Покажем теперь, что если левая часть истинна, то и правая часть тоже истинна. Пусть левая часть истинна. Тогда по определению дизъюнкции истинна или формула x , или формула x & y, или обе эти формулы одновременно. Если x ложна, тогда по определению конъюнкции x & y тоже ложна. Значит, x может быть только истиной.

DVS films – Saratov - 2012

Законы логики

Методы доказательства законов алгебры логики

2 способ . Построение таблицы истинности

Докажем первый закон де Моргана:

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