Современная математическая логика - обширная, сложная и разнообразная область знаний. Мы рассмотрим в курсе самую простую ее часть - логику высказываний. Методы, приемы решения задач логики высказываний составляют базис всей математической логики. На примере этой логики мы познакомим вас с основными задачами математической логики: проверка истинности высказывания при конкретных значениях переменных, эквивалентность двух высказываний, проверка на логическое следствие. Для твердого математического фундамента в курсе изучается математическая модель логики высказываний - двоичные функции, операции с ними, канонические формы, минимизация двоичных функций, их эффективное представление при программировании. Также в курсе затрагиваются вопросы формализации высказываний на естественном языке.
от партнера
Математическая логика. Политехнический взгляд
Санкт-Петербургский политехнический университет Петра ВеликогоОб этом курсе
Чему вы научитесь
формализовывать инженерные проблемы
получать корректные следствия из установленных фактов
формально представлять и преобразовывать информацию об окружающем мире
проверять эквивалентность высказываний
Приобретаемые навыки
от партнера

Санкт-Петербургский политехнический университет Петра Великого
Peter the Great St. Petersburg Polytechnic University has a long-standing and successful history over 100 years where a great deal of important discoveries and inventions have been made. It was founded in 1899.
Программа курса: что вы изучите
Введение
Цель этого модуля - ознакомительная. Мы определяем здесь предмет курса - математическую логику, а также разбираем его структуру. Кроме того, в модуле разбираются задачи, которые вы сможете решать при помощи знаний, полученных в ходе обучения.
Булевы функции
Основная задача этого модуля - заложить математический фундамент для изучения математической логики. Для этого мы познакомимся с основной математической моделью, на которой строится логика высказываний - двоичной функцией. В данном курсе термины булева функция, двоичная функция, логическая функция используются как эквивалентные. В этом разделе рассматриваются две формы представления двоичных функций - в виде таблицы истинности и в виде формулы. А также решается задача построения алгоритма для перехода из одной формы в другую и обратно.
Нормальные формы представления булевых функций
Нормальная форма представления функции - это форма представления, фиксированная некоторым образом. Среди нормальных форм выделяются канонические формы. Представление функции в канонических формах единственно с точностью до порядка переменных, т. е. если зафиксировать порядок переменных, то представление будет единственным. Канонические формы позволяют эффективно решать задачу сравнения функций: не нужно сравнить функции по значениям, достаточно сравнить их представление. В модуле рассматриваются следующие нормальные формы представления двоичных функций: таблица истинности, дизъюнктивная нормальная форма (ДНФ), совершенная дизъюнктивная (СДНФ), конъюнктивная нормальная форма (КНФ), совершенная конъюнктивная (СКНФ), полином Жегалкина. Также решается задача перехода между разными формами представления. Во второй части модуля рассматривается задача, которая была особо актуальна при разработке аппаратных схем, - задача минимизации двоичных функций. Мы рассматриваем решение этой задачи с помощью карт Карно. В последней части рассматриваются несколько примеров реализации двоичных функций при решении практических задач.
Бинарные решающие диаграммы
В этом модуле рассмотрим еще одну каноническую форму представления двоичных функций - бинарные решающие диаграммы (BDD). Эту форму отличает компактное представление для многих практических задач, т. е. для них размер BDD полиномиален от числа переменных. Компактность этой формы позволяет решать многие практические задачи, определяемые через двоичные функции.
Основные понятия логики высказываний
Логика высказываний очень проста. Она выбирает в этом мире только высказывания, на которые можно ответить да или нет, и умеет их соединять самыми простыми связками. Получаемые высказывания снова отвечают на вопрос да или нет. Высказывание "Меня зовут Ирина?" является высказыванием этой логики, оно истинно или ложно, в зависимости от того, кто задает этот вопрос. А вот высказывание "Ирина" не относится к логике высказываний (оно не ставит вопроса с ответом да или нет). В этом модуле мы рассмотрим основные понятия логики высказываний: синтаксис языка этой логики, т.е. правила, определяющие, какие формулы относятся к формулам логики высказываний, семантику языка, т.е. математическую модель, на которой оценивается истинность формулы высказываний (это будут двоичные функции). Много внимания мы уделим тому, как перейти от высказывания на естественном языке к формуле логики высказываний и обратно - навык чрезвычайно полезный не только в профессии, но и в быту. Рассмотрим классические задачи логики: проверку выполнимости формулы на заданном наборе значений переменных, проверку эквивалентности двух формул. В конце этого модуля мы обратимся к наиболее простым приемам эквивалентного переформулирования утверждений математических теорем для упрощения структуры доказательства.
Часто задаваемые вопросы
Когда я получу доступ к лекциям и заданиям?
Что я получу, оплатив сертификацию?
Is financial aid available?
Остались вопросы? Посетите Центр поддержки учащихся.