Аналитический способ задания.
В таблице истинности, рассмотренных ранее, приведены элементарные функции одного и двух переменных
Логика предикатов. Кванторы.
Рассмотрим ряд высказываний: «1 есть простое число», «2 есть простое число», «3 есть простое число»;«4 есть простое число» и т.д. Одни из этих высказываний истинны, другие – ложны, но все они получаются из выражения «n есть простое число», если вместо n подставлять те или иные натуральные числа. Обозначим это выражение через P(n). Само P(n) не является высказыванием, т. к. нельзя сказать истинно оно или ложно, но оно превращается в высказывание при каждом n N. Выражение такого типа называется одноместным предикатом, определенным на множестве N.
Аналогично, примером двухместного предиката является выражение «x дружит с y», где x и y принадлежат , например, множеству студентов второго курса..
Определение. Пусть x1, x2, ..., xn - символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (x1, x2, ..., xn) принадлежат некоторому множеству Ω, которое будем называть предметной областью. Тогда n – местным предикатом, определенным на предметной области Ω , называется отображение Ω во множество высказываний.
Квазиопределение. Связное повествовательное предложение, содержащее n переменных и обладающее следующим свойством: при фиксации значений всех переменных о предложении можно сказать истинно оно или ложно.
Для n – местного предиката существует обозначение P(x1, x2, ..., xn ), где P - имя предиката.
Определение. Характеристической функцией предиката P(x1, x2, ..., xn), определенного на предметной области Ω, называется
П р и м е р 1 .Пусть Ω = {2, 3, ..., 8}. Р(x) означает «х – простое число». Таблица истинности этого предиката имеет вид
x P(x)
2 1
3 1
4 0
5 1
6 0
7 1
8 0
П р и м е р 2. Пусть Ω = {1, 2, 3, 4}2 и P(x, y) означает «х является делителем у». Тогда этот предикат можно задать матрицей смежности, которая является фактически таблицей истинности, записанной в более удобном виде
x y
Определение. Если характеристическая функция предиката тождественно равна единице, то такой предикат называется тождественно истинным.
Если характеристическая функция предиката тождественно равна нулю, то такой предикат называется тождественно ложным.
Пример тождественно истинного предиката: .
Пример тождественно ложного предиката: .
Все операции над высказываниями имеют смысл и для предикатов. Но имеются две важные логические операции, которые имеют именно для предикатов.
Пусть P(x) – одноместный предикат, определенный на области Ω. Поставим ему в соответствие высказывание: «для каждого х Ω Р(х) – истинно». Такое высказывание обозначается и читается «для каждого х имеет место P(x)». Это высказывание истинно тогда и только тогда, когда Р(х) – тождественно истинный предикат.
Определение. Значок называется квантором всеобщности. Говорят, что высказывание получается из предиката Р(х) навешиванием квантора всеобщности.
Составим еще одно высказывание о предикате Р(х) «существует х Ω, для которого Р(х) истинно».Такое высказывание обозначается и читается «существует x, для которого имеет место Р(х). Это высказывание ложно тогда и только тогда, когда Р(х) тождественно ложный предикат.
Определение. Значок называется квантором существования. Говорят, что высказывание получается из предиката Р(х) навешиванием квантора существования.
Обозначения и для кванторов – это перевернутые латинские буквы А и Е, которые являются первыми буквами английских слов «All» и «Exist».
Если предметная область Ω конечна Ω ={a1, a2, ..., ak}, то высказывание равносильно конъюнкции
При этом справедливы обобщенные законы де Моргана
П р и м е р . Ω = N2, а Р(х, у) означает «х является делителем у», тогда
На языке предикатов можно записать многие математические понятия.
Например. Пусть a является пределом последовательности {xn}. Это означает:
каково бы ни было ε, найдется такое натуральное число N. что для всех n > N выполняется соотношение |xn – a| < ε. Это высказывание. Существование предела равно истинности этого высказывания. Итак.
- Дискретная математика.
- Множества.
- П римеры
- Или по другому
- Операции над множествами.
- Основные свойства операций над множествами.
- Алгебра высказываний.
- Логические операции над высказываниями.
- Отрицание.
- Конъюнкция.
- Эквиваленция
- Импликация.
- Формулы алгебры высказываний.
- Элементарные высказывания, символы логических переменных – формулы;
- Если f1 и f2 – формулы алгебры высказываний, то
- Других формул алгебры высказываний нет.
- Равносильность формул.
- Совершенная дизъюнктивная нормальная форма.
- Приведение формулы к сднф.
- Совершенная конъюнктивная нормальная форма.
- Приведение формулы к скнф.
- Полнота и замкнутость.
- Минимизация днф.
- Способы задания булевых функций.
- Табличный способ задания.
- Графический способ задания.
- Аналитический способ задания.
- Элементы теории графов.
- Матрицы графов.
- Некоторые общие понятия теории графов.
- Взвешенные графы и алгоритмы поиска кратчайшего пути.
- Задача о кратчайших путях.
- Элементы теории алгоритмов.
- Понятие автомата.
- Машина Тьюринга.
- Автомат Мили.
- Правило суммы.
- Правило прямого произведения.
- Размещения с повторениями.
- Размещения без повторений.
- Перестановки.
- Сочетания.
- Сочетания с повторениями.