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

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

Логика
Наука о формах
и законах
правильного
мышления
Наука о способах
получения
новых
знаний
Наука о способах
доказательств и
опровержений

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

DVS films – Saratov - 2012

истории логики

«Органон» Аристотеля
– первые труды по
формальной логике

Развитие и подъем
средневековой
европейской логики до XIV в.

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

Схоластическая логика. Представители:
Уильям Оккама,
Альберт Саксонский и Уолтер Берли.

Конец XIX – нач.XX вв. –
заложены основы
математической
(символической) логики

Приминение математических методов для обнаружения истинного значения выражений естественного языка
Дж. Буль,
О. де Морган,
Г. Фреге, Ч. Пирс
Внесли огромный
вклад в развитие
символической
логики

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

DVS films – Saratov - 2012

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

DVS films – Saratov - 2012

т.е. деление понятия А на В и не-В (например, преступления делятся на умышленные и неумышленные)..

DVS films – Saratov - 2012

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

DVS films – Saratov - 2012

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

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

DVS films – Saratov - 2012

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

DVS films – Saratov - 2012

между категорическими и условными суждениями.

DVS films – Saratov - 2012

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

DVS films – Saratov - 2012

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

DVS films – Saratov - 2012

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

DVS films – Saratov - 2012

строил исходя из объективно-идеалистической идеи о тождестве законов мышления и бытия.

DVS films – Saratov - 2012

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

DVS films – Saratov - 2012

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

Основоположником формальной логики является Аристотель, чьи труды о логике
в дальнейшем стали основой данного течения.
В истории философии — отдельный раздел или направление логики конца XIX—начала XX века.

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

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

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

посылка

Сократ — человек
меньшая посылка

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

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

1

2

Модель аналогии (лат. modus — образец, копия, образ) — предметная,
математическая или абстрактная система, имитирующая или отображающая
принципы внутренней организации, функционирования, особенностей
исследуемого объекта (оригинала), непосредственное изучение, которого,
по разным причинам, невозможно или усложнено.

Пример: Два куба.
Одинаковая величина и форма –
основа сравнения, наиболее
явный общий признак.
Сравниваемые признаки
предметов – различные между
собой оттенки одного цвета.

DVS films – Saratov - 2012

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

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

Виды
доказательств
Прямое
(истинность обосновывается
непосредственно аргументами)
Косвенное
(доказывается ложность
утверждаемого антитезиса)
Доказательство от «противного»
Разделительное доказательство
(методом исключения)

DVS films – Saratov - 2012

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

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

Пример:
A(x) = «В городе x идет дождь.»
A — высказывательная форма, x — объект.

Виды
высказываний
Элементарные
Составные

образованны из простых
высказываний с
помощью логических
связок (операций).

DVS films – Saratov - 2012

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

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

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

— логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны.

Импликация двух логических высказываний A и B — логическое высказывание, ложное только тогда, когда B ложно, а A истинно.
Обозначается символом "следовательно" и выражается словами ЕСЛИ … , ТО …

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

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

Задача 1.1

1 ↔ 1 = 1;

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

DVS films – Saratov - 2012

и неравносторонний, то неверно, что он неравнобедренный.

Решение:

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

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

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

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

a)

б)

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

логики

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

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

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

логики

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

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

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

логики

3способ. Тождественные преобразования

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

М.: ИНФРА-М, 2001.
Гетманова А. Д. Учебник по логике. - М.: Владос, 1995.