Дискретная математика и логика – это разделы математики, занимающиеся изучением дискретных математических структур (в частности, графов и утверждений в логике).
В рамках дискретной математики и логики можно выделить следующие базовые разделы (перечень не является исчерпывающим):
Высказыванием называют повествовательное предложение, для которого можно определить истинность или ложность.
Высказывания могут записываться как на естественном словесном языке, так и на специальных языках (химическом, математическом и т. д.).
Не являются высказываниями:
Но не всякое из повествовательных предложений может считаться высказыванием.
Логика высказываний не исследует причины истинности и ложности высказываний – она просто рассматривает их как величины, принимающие одно из двух допустимых значений (0 или 1).
Из простых высказываний с помощью логических связок (операций) могут быть получены сложные высказывания. Базовые логические операции:
Логика высказываний – самый просто раздел математической логики. Однако рассмотрение высказываний как целостных, неделимых величин накладывает ограничения на методологические возможности. Более глубоко исследовать высказывания за счет рассмотрения их внутренней структуры позволяет логика предикатов.
Предикат – это повествовательное предложение, имеющее одну или несколько переменных, превращающееся в высказывание путем подстановки конкретных значений вместо переменных.
Например, предикат: «x > y». В таком виде невозможно определить его истинность. Но если подставить x = 5, y = 8, получится ложное высказывание: «5 > 8».
Предикат позволяет поставить в соответствие каждому набору переменных истинное или ложное высказывание. Поэтому можно сказать, что предикат представляет собой функцию, множество значений которой ограничено истинностными значениями 0 и 1. Множества допустимых значений для переменных зависит от содержания предиката.
Предикаты бывают:
Важную роль в логике предикатов играют кванторы (квантор существования, квантор всеобщности).
Дискретная математика работает с дискретными объектами, поэтому одним из важных разделов ее является комбинаторика, занимающаяся пересчетом и перечислением элементов в конечных множествах.
Пересчетом называют определение количества элементов конечного множества, обладающих заданным свойством (или группой свойств).
Перечислением называют выделение всех элементов конечного множества, обладающих заданным свойством (или группой свойств).
Основополагающими в комбинаторике являются следующие правила:
Комбинаторика оперирует следующими значимыми понятиями:
Функцию называют булевой, если ее аргументы и она сама принимают значения из множества {0; 1}.
Альтернативные названия булевых функции – функции алгебры логики, истинностные функции.
Булевы функции часто записывают в виде таблицы, где первые столбцы отведены под всевозможные наборы значений аргументов, а в последнем столбце записывается соответствующее название функции. Если переменная влияет на значение функции (существует такая пара наборов значений, которая отличается на значение только этой переменной и соответствует разным значениям функции), она считается существенной, в противном случае – несущественной (фиктивной). Для упрощения схемы фиктивную переменную можно исключить из рассмотрения. Но иногда фиктивные переменные добавляют специально, чтобы обеспечить равенство числа аргументов в нескольких функциях.
Под графом в общем смысле понимают множество вершин (точек, узлов), соединенных множеством ребер или дуг (линий).
Теория графов имеет выраженный прикладной характер, она универсальна и незаменима при проектировании сетей коммуникаций. Теория графов широко применяется во многих науках, в том числе связанных с изучением поведения (теории игр, теории информации).
Итак, граф задается двумя конечными непересекающимися множествами:
При этом каждый элемент множества ребер (дуг) представим как двухэлементное подмножества множества вершин: для ориентированных графов задается вершина, из которой исходит дуга, и вершина, в которую она входит. В неориентированных графах направление не задается, поэтому ребро представляется парой вершин, которые оно соединяет (порядок вершин не важен). Ребро и его концевая вершина инцидентны, или одно находится при другом.
Вершины, инцидентные одному общему ребру, называются смежными (соседними).
Ребра, имеющие общую концевую вершину, называются смежными.
Особую роль в различных научных сферах играют деревья – разновидность связных (имеющих маршрут, соединяющий любую пару вершин) ациклических графов. В деревьях определяют корень (для ориентированных деревьев – вершина, в которую не входит ни одна дуга) и листья (для ориентированных деревьев – вершины, из которых не исходит ни одной дуги; для неориентированных – вершины, инцидентные единственному ребру).