Математическая логика. Политехнический взгляд

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

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

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

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