Файл: Учебника по курсу Основы дискретной математики и логики.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.10.2023
Просмотров: 235
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
В[бэ] является частью множества А[а], то и замыкание В[бэ] содержится в замыкании А[а].
Смысл третьего свойства в том, что повторное применение операции замыкания к множеству А[а] не выводит за пределы замыкания А[а].
Слайд 144
Используя понятие замыкания, можно другим способом записать определение полной системы. Мы говорили, что система является полной, если любая булева функция выражается с помощью функций этой системы.
Но множество функций, выражаемых с помощью функций данной системы, есть замыкание этой системы. Получаем, что если замыкание системы А[а] совпадает с множеством всех булевых функций, то система полная.
Если же замыкание класса совпадает с самим классом, то такой класс называется замкнутым. Рассмотрим примеры замкнутых классов.
Одним из замкнутых классов является класс функций, сохраняющих нуль. Он обозначается T
0
[тэ нулевое]. Функции этого класса на наборе, состоящем из одних нулей, принимают значение нуль. Любая суперпозиция функций данного класса дает функцию, принимающую значение нуль на наборе, состоящем из одних нулей. Это говорит о замкнутости класса.
Аналогично определяется класс функций, сохраняющих единицу.
Слайд 145
Еще одним примером замкнутого класса является класс линейных функций, который обозначается через L[эль]. В класс линейных функций входят функции, полином Жегалкина которых не содержит конъюнкций.
Можно провести аналогию с понятием линейной функции, известной нам из
Слайд 147
Покажем на примере, как определяется двойственная функция для данной функции. Согласно определению для нахождения значения двойственной функции на некотором наборе надо взять противоположный набор и отрицание значения исходной функции на этом наборе.
Первый набор – 0-0-0[ноль ноль ноль], противоположный к нему – 1-1-
1[один один один], значение исходной функции на нем равно единице, значит, двойственная функция на первом наборе принимает значение нуль.
Для набора 0-0-1[ноль ноль один] противоположным является набор 1-
1-0[один один ноль]. Функция f[эф] на этом наборе принимает значение ноль.
Следовательно, значение двойственной функции на наборе 0-0-1[ноль ноль один] равно единице.
Аналогичными рассуждениями найдем все значения двойственной функции. Отметим, что противоположными будут первый набор с восьмым, второй – с седьмым, третий – с шестым, четвертый – с пятым.
Слайд 148
Из алгоритма нахождения двойственной функции мы получаем алгоритм проверки функции на самодвойственность.
Функция является самодвойственной, если она принимает противоположные значения на противоположных наборах.
Обратимся к примеру, представленному на слайде. Запишем значения функции f[эф] в виде вектор-строки. Соединим линиями значения, принимаемые данной функцией на противоположных наборах. Если на первой позиции стоит ноль, то на восьмом месте должна быть единица.
Вторую позицию занимает единица, значит, седьмым должен быть ноль.
Третье по счету значение функции нулевое, следовательно, на шестом месте должна стоять единица. Четвертую позицию занимает единица, значит, следующим должен быть ноль. Непосредственной проверкой убеждаемся в
Таким образом, функция с требуемым свойством построена.
Слайд 152
Перейдем к построению функции g[жэ]. По условию задачи она должна быть линейной. Согласно определению линейной функции ее полином
Жегалкина может содержать только линейные слагаемые. Нам известны значения функции на четырех наборах значений переменных. Это позволяет нам записать четыре уравнения с четырьмя неизвестными. Указанные уравнения представлены на слайде.
Сравнивая первое и четвертое уравнения, получаем, что а
1
[а первое] равно единице. Подставляем найденное значение в третье уравнение и, сопоставляя полученный результат с первым уравнением, делаем вывод, что
а
3
[а третье] равно единице. Найденные коэффициенты позволяют нам из второго и третьего уравнений определить оставшиеся два коэффициента. Мы получаем, что а
0
[а нулевое] и а
2
[а второе] равны нулю.
Теперь мы можем записать выражение для функции g[жэ] и найти недостающие значения функции.
Слайд 153
Теперь нам осталось доопределить функцию h[аш] так, чтобы она была самодвойственной. Самодвойственная функция на противоположных наборах значений переменных должна принимать противоположные значения. В таблице истинности функции h[аш] соединим линиями противоположные наборы. На наборе 0-0-0[ноль ноль ноль] функция принимает значение один. Значит, на наборе 1-1-1[один один один] она должна обращаться в ноль. На наборе 0-1-0[ноль один ноль] значение функции также равно единице. Следовательно, на противоположном ему наборе 1-0-1[один ноль один] она обязана принимать нулевое значение. На наборе 0-1-1[ноль один один] функция обращается в ноль. Значит, на наборе
1-0-0[один ноль ноль] она принимает значение один. На наборе 1-1-0[один
Для проверки на принадлежность классу L[эль] построим полином
Жегалкина. Так как в полиноме Жегалкина функции f[эф] присутствуют конъюнкции, то f ∉ L[эф не принадлежит классу L].
Таким образом, функция f[эф] не принадлежит ни одному из классов
Поста. Значит, данная система является функционально полной и с помощью суперпозиций из f[эф] можно получить любую булеву функцию, в частности, функцию g[жэ].
Слайд 156
Тема 5.1. Понятие предиката. Логические и кванторные операции над предикатами. Формулы логики предикатов
Для анализа многих математических рассуждений важна структура высказываний, а также их содержание. Поэтому для получения заключений в научных исследованиях очень часто средств алгебры высказываний недостаточно.
Рассмотрим, например, следующие предложения.
1.
Из дифференцируемости функции следует непрерывность.
2.
Показательная функция является дифференцируемой функцией.
3.
Показательная функция является непрерывной функцией.
Ясно, что из первых двух предложений следует третье, но даже такое простое утверждение на языке алгебры высказываний невозможно доказать.
Символика алгебры высказываний недостаточна для выражения существенных связей между предложениями.
Алгебра предикатов обладает более широкими возможностями, она позволяет строить формализованную теорию и включает в себя алгебру высказываний как частный случай.
Рассмотрим непустое множество М[эм]. Выражение, содержащее n[эн] переменных и обращающееся в высказывание при замене переменных элементами множества М[эм], называется n[эн]-местным предикатом на
В формулах (5.9) и (5.10) навешивание кванторов привело к тому, что двуместные предикаты превратились в высказывания, то есть 0[нуль]- местные предикаты. Если применить квантор к n[эн]-местному предикату, то получится (n − 1)[эн минус один]-местный предикат. Переменную, к которой относится квантор, называют связанной. Остальные переменные называются свободными.
Слайд 158
Приведем примеры записей на языке алгебры предикатов. Рассмотрим одноместные предикаты, представленные на слайде.
Предикат N(х)[эн от икс]выражает свойство числа х[икс] быть натуральным. Предикат R(х)[эр от икс] выражает свойство числа х[икс] быть действительным.
Из предикатов N(х)[эн от икс] и R(х)[эр от икс] путем навешивания кванторов составим высказывания, полученные высказывания запишем на языке алгебры предикатов.
Высказывание
«Все натуральные числа
– действительные» представлено формулой (5.11).
Высказывание
«Ни одно натуральное число не является действительным» представлено формулой (5.12).
Высказывание «Некоторые натуральные числа действительные» представлено формулой (5.13).
Слайд 159
Предикат называется выполнимым, если при некоторой подстановке вместо переменных конкретных элементов из соответствующих множеств он обращается в истинное высказывание.
Предикат называется опровержимым, если при некоторой подстановке вместо переменных конкретных элементов из соответствующих множеств он обращается в ложное высказывание.
Множество, на котором предикат обращается в истинное высказывание, называется множеством истинности предиката.
Смысл третьего свойства в том, что повторное применение операции замыкания к множеству А[а] не выводит за пределы замыкания А[а].
Слайд 144
Используя понятие замыкания, можно другим способом записать определение полной системы. Мы говорили, что система является полной, если любая булева функция выражается с помощью функций этой системы.
Но множество функций, выражаемых с помощью функций данной системы, есть замыкание этой системы. Получаем, что если замыкание системы А[а] совпадает с множеством всех булевых функций, то система полная.
Если же замыкание класса совпадает с самим классом, то такой класс называется замкнутым. Рассмотрим примеры замкнутых классов.
Одним из замкнутых классов является класс функций, сохраняющих нуль. Он обозначается T
0
[тэ нулевое]. Функции этого класса на наборе, состоящем из одних нулей, принимают значение нуль. Любая суперпозиция функций данного класса дает функцию, принимающую значение нуль на наборе, состоящем из одних нулей. Это говорит о замкнутости класса.
Аналогично определяется класс функций, сохраняющих единицу.
Слайд 145
Еще одним примером замкнутого класса является класс линейных функций, который обозначается через L[эль]. В класс линейных функций входят функции, полином Жегалкина которых не содержит конъюнкций.
Можно провести аналогию с понятием линейной функции, известной нам из
курса математического анализа. У линейной функции все переменные имеют степень не больше первой.
Для доказательства того, что функция является линейной, нужно построить ее полином Жегалкина и убедиться в том, что степень полученного полинома не больше первой.
Рассмотрим пример проверки функции на линейность.
Обратимся к функции, представленной на слайде. Сначала упростим выражение, склеивая первую конъюнкцию с третьей, а вторую – с четвертой.
Затем заменим операцию дизъюнкции на сумму по модулю два. Выразим отрицание через сумму по модулю два и единицу, раскроем скобки, приведем подобные слагаемые. В результате получим полином Жегалкина, который не содержит конъюнкций, а следовательно, функция является линейной.
Слайд 146
Во многих задачах используется функция, двойственная к заданной булевой функции. Если исходная функция выражается формулой, содержащей переменные x
1
[икс один], x
2
[икс два] и т. д., x
n
[икс эн], то для получения двойственной функции нужно поставить знак отрицания над каждой переменной и над всей формулой. Обозначение и формульное определение двойственной функции представлены на слайде.
Функция алгебры логики называется самодвойственной, если она совпадает с двойственной к ней функцией. Другими словами, самодвойственная функция на противоположных наборах значений переменных принимает противоположные значения. Множество всех самодвойственных функций обозначается буквой S[эс]. Класс, образованный самодвойственными функциями, дает нам еще один пример замкнутого класса.
На слайде представлены примеры функций, принадлежащих классу
S[эс], и функций, не являющихся самодвойственными.
Для доказательства того, что функция является линейной, нужно построить ее полином Жегалкина и убедиться в том, что степень полученного полинома не больше первой.
Рассмотрим пример проверки функции на линейность.
Обратимся к функции, представленной на слайде. Сначала упростим выражение, склеивая первую конъюнкцию с третьей, а вторую – с четвертой.
Затем заменим операцию дизъюнкции на сумму по модулю два. Выразим отрицание через сумму по модулю два и единицу, раскроем скобки, приведем подобные слагаемые. В результате получим полином Жегалкина, который не содержит конъюнкций, а следовательно, функция является линейной.
Слайд 146
Во многих задачах используется функция, двойственная к заданной булевой функции. Если исходная функция выражается формулой, содержащей переменные x
1
[икс один], x
2
[икс два] и т. д., x
n
[икс эн], то для получения двойственной функции нужно поставить знак отрицания над каждой переменной и над всей формулой. Обозначение и формульное определение двойственной функции представлены на слайде.
Функция алгебры логики называется самодвойственной, если она совпадает с двойственной к ней функцией. Другими словами, самодвойственная функция на противоположных наборах значений переменных принимает противоположные значения. Множество всех самодвойственных функций обозначается буквой S[эс]. Класс, образованный самодвойственными функциями, дает нам еще один пример замкнутого класса.
На слайде представлены примеры функций, принадлежащих классу
S[эс], и функций, не являющихся самодвойственными.
Слайд 147
Покажем на примере, как определяется двойственная функция для данной функции. Согласно определению для нахождения значения двойственной функции на некотором наборе надо взять противоположный набор и отрицание значения исходной функции на этом наборе.
Первый набор – 0-0-0[ноль ноль ноль], противоположный к нему – 1-1-
1[один один один], значение исходной функции на нем равно единице, значит, двойственная функция на первом наборе принимает значение нуль.
Для набора 0-0-1[ноль ноль один] противоположным является набор 1-
1-0[один один ноль]. Функция f[эф] на этом наборе принимает значение ноль.
Следовательно, значение двойственной функции на наборе 0-0-1[ноль ноль один] равно единице.
Аналогичными рассуждениями найдем все значения двойственной функции. Отметим, что противоположными будут первый набор с восьмым, второй – с седьмым, третий – с шестым, четвертый – с пятым.
Слайд 148
Из алгоритма нахождения двойственной функции мы получаем алгоритм проверки функции на самодвойственность.
Функция является самодвойственной, если она принимает противоположные значения на противоположных наборах.
Обратимся к примеру, представленному на слайде. Запишем значения функции f[эф] в виде вектор-строки. Соединим линиями значения, принимаемые данной функцией на противоположных наборах. Если на первой позиции стоит ноль, то на восьмом месте должна быть единица.
Вторую позицию занимает единица, значит, седьмым должен быть ноль.
Третье по счету значение функции нулевое, следовательно, на шестом месте должна стоять единица. Четвертую позицию занимает единица, значит, следующим должен быть ноль. Непосредственной проверкой убеждаемся в
том, что все необходимые требования выполняются. Итак, f[эф] – самодвойственная функция.
Слайд 149
Последним замкнутым классом, который мы рассмотрим, является класс монотонных функций. Он обозначается буквой М[эм].
Понятие монотонно возрастающей функции нам известно из математического анализа: функция монотонно возрастает, если с увеличением аргумента значение функции не убывает.
Так как булевы функции заданы на множестве наборов значений переменных, прежде чем дать определение монотонной функции, мы должны определить операцию сравнения наборов. Говорят, что набор альфа предшествует набору бета, если на каждой позиции набора альфа значение не больше значения на той же позиции в наборе бета.
Существуют наборы, к которым неприменимо отношение упорядоченности, определенное выше. Например, наборы 0-0-1[ноль ноль один] и 0-1-0[ноль один ноль] не сравнимы.
Определение монотонной функции представлено на слайде.
Слайд 150
Для проверки монотонности функции можно воспользоваться ее таблицей истинности. Стоит отметить, что набор 0-0-0[ноль ноль ноль] сравним со всеми наборами и является предшествующим для них, для набора
1-1-1[один один один] все другие наборы являются предшествующими.
Поэтому на наборе 0-0-0[ноль ноль ноль] монотонная непостоянная функция принимает значение нуль, а на наборе 1-1-1[один один один] – значение единица. Т. е. монотонная функция, не являющаяся константой, принадлежит классу функций, сохраняющих нуль, и классу функций, сохраняющих единицу.
Обратимся к примеру, представленному на слайде. Проверим, является ли данная функция монотонной. Условие, которое было описано выше,
Слайд 149
Последним замкнутым классом, который мы рассмотрим, является класс монотонных функций. Он обозначается буквой М[эм].
Понятие монотонно возрастающей функции нам известно из математического анализа: функция монотонно возрастает, если с увеличением аргумента значение функции не убывает.
Так как булевы функции заданы на множестве наборов значений переменных, прежде чем дать определение монотонной функции, мы должны определить операцию сравнения наборов. Говорят, что набор альфа предшествует набору бета, если на каждой позиции набора альфа значение не больше значения на той же позиции в наборе бета.
Существуют наборы, к которым неприменимо отношение упорядоченности, определенное выше. Например, наборы 0-0-1[ноль ноль один] и 0-1-0[ноль один ноль] не сравнимы.
Определение монотонной функции представлено на слайде.
Слайд 150
Для проверки монотонности функции можно воспользоваться ее таблицей истинности. Стоит отметить, что набор 0-0-0[ноль ноль ноль] сравним со всеми наборами и является предшествующим для них, для набора
1-1-1[один один один] все другие наборы являются предшествующими.
Поэтому на наборе 0-0-0[ноль ноль ноль] монотонная непостоянная функция принимает значение нуль, а на наборе 1-1-1[один один один] – значение единица. Т. е. монотонная функция, не являющаяся константой, принадлежит классу функций, сохраняющих нуль, и классу функций, сохраняющих единицу.
Обратимся к примеру, представленному на слайде. Проверим, является ли данная функция монотонной. Условие, которое было описано выше,
выполняется. Проанализируем значения функции на других наборах. При этом нас не будут интересовать наборы, на которых функция принимает нулевое значение. Так как в этом случае на всех последующих наборах функция принимает значение, большее или равное данному. Возьмем второй набор 0-0-1[ноль ноль один], функция на нем равна единице, следовательно, на всех последующих для него наборах функция должна принимать то же значение. Последующими для второго набора будут наборы 0-1-1[ноль один один], 1-0-1[один ноль один] и 1-1-1[один один один], на каждом из них функция равна единице.
Далее рассматриваем четвертый набор 0-1-1[ноль один один], для него последующим является только восьмой набор 1-1-1[один один один], то же касается и шестого набора 1-0-1[один ноль один]. Мы видим, что для всех пар сравнимых наборов значение функции на большем наборе больше или равно значения функции на меньшем наборе. Следовательно, функция является монотонной.
Слайд 151
Рассмотрим задачу построения булевых функций с требуемыми свойствами.
Обратимся к примеру, представленному на слайде. Требуется построить монотонную функцию f[эф], линейную функцию g[жэ] и самодвойственную функцию h[аш]. Доопределим функцию f[эф], используя определение монотонной функции. На наборе 1-1-0[один один ноль] функция принимает значение 0. Этому набору предшествуют наборы 0-0-0[ноль ноль ноль] и 1-0-0[один ноль ноль]. Значит, на них функция должна принимать значение ноль.
На наборе 0-0-1[ноль ноль один] функция обращается в единицу. Этот набор предшествует наборам 1-0-1[один ноль один] и 1-1-1[один один один].
Следовательно, на указанных наборах функция должна принимать значение один.
Далее рассматриваем четвертый набор 0-1-1[ноль один один], для него последующим является только восьмой набор 1-1-1[один один один], то же касается и шестого набора 1-0-1[один ноль один]. Мы видим, что для всех пар сравнимых наборов значение функции на большем наборе больше или равно значения функции на меньшем наборе. Следовательно, функция является монотонной.
Слайд 151
Рассмотрим задачу построения булевых функций с требуемыми свойствами.
Обратимся к примеру, представленному на слайде. Требуется построить монотонную функцию f[эф], линейную функцию g[жэ] и самодвойственную функцию h[аш]. Доопределим функцию f[эф], используя определение монотонной функции. На наборе 1-1-0[один один ноль] функция принимает значение 0. Этому набору предшествуют наборы 0-0-0[ноль ноль ноль] и 1-0-0[один ноль ноль]. Значит, на них функция должна принимать значение ноль.
На наборе 0-0-1[ноль ноль один] функция обращается в единицу. Этот набор предшествует наборам 1-0-1[один ноль один] и 1-1-1[один один один].
Следовательно, на указанных наборах функция должна принимать значение один.
Таким образом, функция с требуемым свойством построена.
Слайд 152
Перейдем к построению функции g[жэ]. По условию задачи она должна быть линейной. Согласно определению линейной функции ее полином
Жегалкина может содержать только линейные слагаемые. Нам известны значения функции на четырех наборах значений переменных. Это позволяет нам записать четыре уравнения с четырьмя неизвестными. Указанные уравнения представлены на слайде.
Сравнивая первое и четвертое уравнения, получаем, что а
1
[а первое] равно единице. Подставляем найденное значение в третье уравнение и, сопоставляя полученный результат с первым уравнением, делаем вывод, что
а
3
[а третье] равно единице. Найденные коэффициенты позволяют нам из второго и третьего уравнений определить оставшиеся два коэффициента. Мы получаем, что а
0
[а нулевое] и а
2
[а второе] равны нулю.
Теперь мы можем записать выражение для функции g[жэ] и найти недостающие значения функции.
Слайд 153
Теперь нам осталось доопределить функцию h[аш] так, чтобы она была самодвойственной. Самодвойственная функция на противоположных наборах значений переменных должна принимать противоположные значения. В таблице истинности функции h[аш] соединим линиями противоположные наборы. На наборе 0-0-0[ноль ноль ноль] функция принимает значение один. Значит, на наборе 1-1-1[один один один] она должна обращаться в ноль. На наборе 0-1-0[ноль один ноль] значение функции также равно единице. Следовательно, на противоположном ему наборе 1-0-1[один ноль один] она обязана принимать нулевое значение. На наборе 0-1-1[ноль один один] функция обращается в ноль. Значит, на наборе
1-0-0[один ноль ноль] она принимает значение один. На наборе 1-1-0[один
один ноль] значение функции равно единице. Следовательно, на наборе 0-0-
1[ноль ноль один] она обращается в ноль.
Итак, мы определили все значения функции h[аш], а значит, задача решена.
Слайд 154
Мы рассмотрели пять замкнутых классов функций алгебры логики.
Вспомним, что это классы линейных, монотонных, самодвойственных функций, функций, сохраняющих ноль, и функций, сохраняющих единицу.
Указанные классы функций называются классами Пóста. С помощью функций этих классов определяется полнота некоторой системы А[а] булевых функций. Для полноты системы А[а] необходимо и достаточно, чтобы для каждого класса Пóста в ней нашлась хотя бы одна функция, не принадлежащая этому классу.
Система А[а], состоящая из конъюнкции, дизъюнкции и отрицания, является полной по теореме Пóста. В самом деле, функция отрицания не сохраняет ноль и единицу и не является монотонной функцией. Конъюнкция не является ни линейной, ни самодвойственной функцией. Дизъюнкция также не принадлежит классу самодвойственных функций. Все это позволяет сделать вывод о полноте рассматриваемой системы.
Слайд 155
Рассмотрим пример, представленный на слайде. Если система функций является полной, то с помощью этой системы можно выразить любую булеву функцию, в том числе и функцию g[жэ]
В нашем случае система состоит из одной функции f[эф]. Согласно теореме Поста проверим f[эф] на принадлежность классам Поста. Мы видим, что эта функция не принадлежит классам Т
0
, Т
1
, M и S[тэ нулевое, тэ первое, эм и эс].
1[ноль ноль один] она обращается в ноль.
Итак, мы определили все значения функции h[аш], а значит, задача решена.
Слайд 154
Мы рассмотрели пять замкнутых классов функций алгебры логики.
Вспомним, что это классы линейных, монотонных, самодвойственных функций, функций, сохраняющих ноль, и функций, сохраняющих единицу.
Указанные классы функций называются классами Пóста. С помощью функций этих классов определяется полнота некоторой системы А[а] булевых функций. Для полноты системы А[а] необходимо и достаточно, чтобы для каждого класса Пóста в ней нашлась хотя бы одна функция, не принадлежащая этому классу.
Система А[а], состоящая из конъюнкции, дизъюнкции и отрицания, является полной по теореме Пóста. В самом деле, функция отрицания не сохраняет ноль и единицу и не является монотонной функцией. Конъюнкция не является ни линейной, ни самодвойственной функцией. Дизъюнкция также не принадлежит классу самодвойственных функций. Все это позволяет сделать вывод о полноте рассматриваемой системы.
Слайд 155
Рассмотрим пример, представленный на слайде. Если система функций является полной, то с помощью этой системы можно выразить любую булеву функцию, в том числе и функцию g[жэ]
В нашем случае система состоит из одной функции f[эф]. Согласно теореме Поста проверим f[эф] на принадлежность классам Поста. Мы видим, что эта функция не принадлежит классам Т
0
, Т
1
, M и S[тэ нулевое, тэ первое, эм и эс].
Для проверки на принадлежность классу L[эль] построим полином
Жегалкина. Так как в полиноме Жегалкина функции f[эф] присутствуют конъюнкции, то f ∉ L[эф не принадлежит классу L].
Таким образом, функция f[эф] не принадлежит ни одному из классов
Поста. Значит, данная система является функционально полной и с помощью суперпозиций из f[эф] можно получить любую булеву функцию, в частности, функцию g[жэ].
Слайд 156
Тема 5.1. Понятие предиката. Логические и кванторные операции над предикатами. Формулы логики предикатов
Для анализа многих математических рассуждений важна структура высказываний, а также их содержание. Поэтому для получения заключений в научных исследованиях очень часто средств алгебры высказываний недостаточно.
Рассмотрим, например, следующие предложения.
1.
Из дифференцируемости функции следует непрерывность.
2.
Показательная функция является дифференцируемой функцией.
3.
Показательная функция является непрерывной функцией.
Ясно, что из первых двух предложений следует третье, но даже такое простое утверждение на языке алгебры высказываний невозможно доказать.
Символика алгебры высказываний недостаточна для выражения существенных связей между предложениями.
Алгебра предикатов обладает более широкими возможностями, она позволяет строить формализованную теорию и включает в себя алгебру высказываний как частный случай.
Рассмотрим непустое множество М[эм]. Выражение, содержащее n[эн] переменных и обращающееся в высказывание при замене переменных элементами множества М[эм], называется n[эн]-местным предикатом на
множестве М[эм]. Формула (5.1) задает обозначение n[эн]-местного предиката. Высказывание будем считать 0[нуль]-местным предикатом.
Переменные в алгебре предикатов называются предметными переменными.
Рассмотрим примеры. Формула (5.2) – высказывание или 0[нуль]- местный предикат. Формула (5.3) – 1-местный предикат на множестве натуральных чисел. Формула (5.4) – 2-местный предикат на множестве действительных чисел. Формула (5.5) – 3-местный предикат на множестве действительных чисел. Формула (5.6) – n[эн]-местный предикат на множестве действительных чисел.
Слайд 157
На предикаты переносятся все логические операции, которые выполняются над высказываниями: отрицание, дизъюнкция, конъюнкция, импликация, эквиваленция. Но, в отличие от высказываний, для предикатов определены еще две операции, называемые операциями квантификации, или навешивания кванторов. Различают два вида кванторов – квантор общности и квантор существования.
Квантор общности, стоящий перед предикатом, вместе с самим предикатом читается: «Для всех х[икс] имеет место Р(х)[пэ от икс]».
Соответствующая запись представлена формулой (5.7).
Квантор существования, стоящий перед предикатом, вместе с самим предикатом читается: «Существует х[икс], для которого имеет место Р(х)[пэ от икс]». Соответствующая запись представлена формулой (5.8).
Пусть все переменные пробегают множество действительных чисел.
Формула (5.9) читается следующим образом: «Для любого действительного числа х[икс] найдется действительное число y[игрек], такое, что сумма чисел х[икс] и y[игрек] будет равна 25».
Утверждение, задаваемое формулой (5.10), можно выразить словами:
«Найдется действительное число y[игрек] такое, что сумма любого действительного числа х[икс] и числа y[игрек] будет равна 25».
Переменные в алгебре предикатов называются предметными переменными.
Рассмотрим примеры. Формула (5.2) – высказывание или 0[нуль]- местный предикат. Формула (5.3) – 1-местный предикат на множестве натуральных чисел. Формула (5.4) – 2-местный предикат на множестве действительных чисел. Формула (5.5) – 3-местный предикат на множестве действительных чисел. Формула (5.6) – n[эн]-местный предикат на множестве действительных чисел.
Слайд 157
На предикаты переносятся все логические операции, которые выполняются над высказываниями: отрицание, дизъюнкция, конъюнкция, импликация, эквиваленция. Но, в отличие от высказываний, для предикатов определены еще две операции, называемые операциями квантификации, или навешивания кванторов. Различают два вида кванторов – квантор общности и квантор существования.
Квантор общности, стоящий перед предикатом, вместе с самим предикатом читается: «Для всех х[икс] имеет место Р(х)[пэ от икс]».
Соответствующая запись представлена формулой (5.7).
Квантор существования, стоящий перед предикатом, вместе с самим предикатом читается: «Существует х[икс], для которого имеет место Р(х)[пэ от икс]». Соответствующая запись представлена формулой (5.8).
Пусть все переменные пробегают множество действительных чисел.
Формула (5.9) читается следующим образом: «Для любого действительного числа х[икс] найдется действительное число y[игрек], такое, что сумма чисел х[икс] и y[игрек] будет равна 25».
Утверждение, задаваемое формулой (5.10), можно выразить словами:
«Найдется действительное число y[игрек] такое, что сумма любого действительного числа х[икс] и числа y[игрек] будет равна 25».
В формулах (5.9) и (5.10) навешивание кванторов привело к тому, что двуместные предикаты превратились в высказывания, то есть 0[нуль]- местные предикаты. Если применить квантор к n[эн]-местному предикату, то получится (n − 1)[эн минус один]-местный предикат. Переменную, к которой относится квантор, называют связанной. Остальные переменные называются свободными.
Слайд 158
Приведем примеры записей на языке алгебры предикатов. Рассмотрим одноместные предикаты, представленные на слайде.
Предикат N(х)[эн от икс]выражает свойство числа х[икс] быть натуральным. Предикат R(х)[эр от икс] выражает свойство числа х[икс] быть действительным.
Из предикатов N(х)[эн от икс] и R(х)[эр от икс] путем навешивания кванторов составим высказывания, полученные высказывания запишем на языке алгебры предикатов.
Высказывание
«Все натуральные числа
– действительные» представлено формулой (5.11).
Высказывание
«Ни одно натуральное число не является действительным» представлено формулой (5.12).
Высказывание «Некоторые натуральные числа действительные» представлено формулой (5.13).
Слайд 159
Предикат называется выполнимым, если при некоторой подстановке вместо переменных конкретных элементов из соответствующих множеств он обращается в истинное высказывание.
Предикат называется опровержимым, если при некоторой подстановке вместо переменных конкретных элементов из соответствующих множеств он обращается в ложное высказывание.
Множество, на котором предикат обращается в истинное высказывание, называется множеством истинности предиката.