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