Определение формулы и суперпозиции. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Пусть Имеется Счетное Множество ...
Пусть имеется счетное множество переменных , где . Рассмотрим конечную или счетную систему функций алгебры логики над этим множеством:
. (*)
Введем понятие формулы над этой системой функций.
Определение 1 (интуитивное):
1. Выражение называется формулой над рассматриваемой системой функций.
2. Выражение называется формулой над системой функций (*), если – формула или переменная из множества , а – произвольная функция из системы (*).
Сопоставим каждой формуле функцию алгебры логики.
Определение 2 (индуктивное):
1. Формуле , где поставим в соответствие функцию , где .
2. Формуле , где выражения при являются либо формулами, либо переменными из множества , а – функция системы (*), поставим в соответствие функцию . Здесь, если – переменная, то совпадает с ; если – формула, то – функция, сопоставленная этой формуле.
Полученные в соответствии с этим определением функции называются суперпозициями функций системы (*).
Очевидно, функция , является суперпозицией функций рассмотренной системы (*).
Будем говорить, что функция получена из функции путем переименования переменных.
Например, функция получена из функции путем переименования переменных.
Нетрудно видеть, что при переименовании переменных возможно появление новых переменных, исчезновение старых переменных, перестановка переменных местами и отождествление переменных.
Пусть формула построена из функций . Можно считать, что функции зависят от одних и тех же переменных.
Определение 3: Две формулы называются эквивалентными, если им сопоставлены равные функции.
Эквивалентные формулы будем соединять знаком равенства.
Например, формулы и реализуют каждая функцию . Поэтому . Аналогично: .
Формулы, в построении которых участвуют операции , в силу специфики записи этих формул, содержат скобки. Как и в элементарной алгебре, можно ввести сокращенную запись формулы, вводя порядок действий, считая, что вначале выполняется , далее и затем .
Ниже будет рассмотрена очень важная теорема, называемая теоремой о разложении. Для её формулировки примем следующие обозначения: , . Легко заметить, что если , то если , то , где .
Теорема 1 (о разложении): Пусть – произвольная функция алгебры логики. Тогда ее можно представить в следующей форме:
. (**)
(Здесь мы употребляем сокращенную запись ).
Доказательство: Заметим сначала, что и что тогда и только тогда, когда , ,..., . Рассмотрим теперь произвольные и пусть . Тогда в левой части соотношения получим . Правая часть в силу сделанного замечания также дает . Теорема доказана.
Большое практическое значение имеют следствия из этой теоремы.
Следствие 1: Если , то представление (**) принимает следующий вид:
.
Следствие 2: Если , то представление (**) превращается в следующее равенство:
.
Это разложение называется совершенной дизъюнктивной нормальной формой (С.Д.Н.Ф.) функции . Оно определено для любой функции из множества булевых функций , не равной константе .
Пример: Пусть функция задана таблицей:
Рассмотрим наборы, на которых функция принимает значение : , , , . По этим наборам строим СДНФ для функции :
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Фесенко Т Н...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Определение формулы и суперпозиции.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Представление бинарных отношений графами.
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов