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