ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.12.2023
Просмотров: 14
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Лекция 12. Логика предикатов
Логика высказываний изучает истинность или ложность сложных высказываний, исходя из элементарных высказываний, считая их единым целым. Это является ее недостатком. Поэтому необходима такая логическая система, с помощью которой можно было бы исследовать и структуру высказываний, т.к. истинность или ложность заключения зависит не только от истинности посылок.
Такой системой является логика предикатов.
Предикат – свойства объектов или отношения между объектами. Для каждого конкретного предиката можно рассматривать объекты вполне определенного смысла. Их называют предметными переменными; при подстановке значений переменных предикат обращается в высказывание. n-местный предикат обозначается P(x1, x2, …, xn); предполагается, что x1 M1, x2 M2, …, xn Mn.
Например, рассмотрим 3 высказывания:
A – «Рубль – валюта России»;
B – «Доллар – валюта России»;
C – «Доллар – валюта США»
A, C – истинны, B – ложно. Если вместо конкретных наименований валюты в выражениях A, B подставить предметную переменную x {рубль, доллар, фунт, …}, то получим одноместный предикат P(x) – «x – валюта России». Если в выражениях A, B, C вместо наименований валюты и государств подставить предметные переменные x и y, где y {Россия, США, Германия, …} то получим двуместный предикат P(x, y) – «x – валюта y».
n-местный предикат – это функция P(x1, x2, …, xn) от n переменных, принимающая значения истина или ложь. P: M1 M2 … Mn B, где M1… Mn – предметные области предиката; x1, x2, …, xn – предметные переменные предиката, B = {истина, ложь}.
Вся совокупность возможных объектов – область определения предиката M(P).
Предикат, заданный на некотором множестве М, называется тождественно-истинным, если для любого набора значений аргументов его значение равно 1.
Предикат, заданный на некотором множестве М, называется тождественно-ложным, если для любого набора значений аргументов его значение равно 0.
Предикат, заданный на некотором множестве М, называется выполнимым, если существует хотя бы один набор значений аргументов, для которых его значение равно 1.
Два предиката Р(х) и Q(x), заданные на множестве М, называются равносильными, если их значения для любого набора значений переменных совпадают.
Над предикатами можно производить логические операции и в результате получать новые предикаты.
Над предикатами разрешены основные логические операции:
, &, .Предикат Q(x) называется следствием Р(х), если любой набор значений переменных, удовлетворяющий Р(х), удовлетворяет Q(x).
Теоретико-множественный смысл и геометрическое изображение предикатов
М – универсальное множество – область значений предметной переменной для одноместного предиката.
Множество n-местных предикатов образуют булеву алгебру предикатов, т.е. для них справедливы 19 основных равносильностей булевой алгебры.
Законы 0 и 1:
Р1=1; 1 – обозначение тождественно-истинного предиката.
Р&0=0; 0 – обозначение тождественно-ложного предиката.
Р0=Р; Р&1=Р.
Кванторы
Подстановка в предикат определенного набора предметных переменных обращает его в истинное высказывание. Таких наборов может быть несколько, а может не быть совсем. Это свойство предиката коротко записывают с помощью квантора.
Кванторы – связки логики предикатов.
Пусть P(x) – предикат, определенный на M.
Высказывание «для всех x из M истинно P(x)» обозначается x P(x). - квантор всеобщности.
Высказывание «существует x из M, что истинно P(x)» обозначается x P(x). - квантор существования.
Переменная x в этом случае называется связанной. Говорят, что на нее навешан квантор. Остальные переменные – свободные.
Выражение, на которое навешивается квантор x или x называется областью действия квантора. Все вхождения переменной x в это выражение являются связанными.
Пример. Пусть M – множество людей. P(x) – «x – смертен» задан на множестве M. Озвучить x P(x): «Все люди смертны». Выражение не зависит от переменной x, а характеризует всех людей в целом.
Пример.
x P(x) – «x – четное число» на множестве M = {1, 3, 9, 13} – ложен; на множестве M = {1, 2, 3, 9, 13} – истинен.
Равносильность логических высказываний
Все соотношения равносильности алгебры высказываний распространяются и на логику предикатов. Но кроме этого в логике предикатов применяются соотношения равносильности, относящиеся к перестановке кванторов и отрицанию кванторов.
1. Перенос через отрицание. При отрицании формулы, содержащей квантор, знак квантора меняется на двойственный, а отрицание переносится на область действия квантора.
x P(x). Отрицание высказывания: x P(x) x P(x)
x P(x). Отрицание высказывания: x P(x) x P(x)
Например, P(x) – делится на 3.
Отрицание высказывания x P(x) («все x M делятся на 3») звучит как «не все элементы множества M делятся на 3» или «в множестве M существуют элементы, которые не делятся на 3».
Отрицание высказывания x P(x) («в M есть по крайней мере один элемент, который делится на 3») звучит как «в множестве M не существует элементов, которые делятся на 3» или «в M все элементы не делятся на 3»
2. Вынос квантора за скобки
x (A(x) & B) x A(x) & B; x (A(x) B) x A(x) B
x (A(x) & B) x A(x) & B; x (A(x) B) x A(x) B
(x P1(x) & x P2(x)) x (P1(x) & P2(x)) (x P1(x) x P2(x)) x (P1(x) P2(x))
3. Перестановка (коммутация) одноименных кванторов
(x)(y) A(x, y) (y)(x) A(x, y)
(x)( y) A(x, y) (y)( x) A(x, y)
4. Переименование связанных переменных: заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, всюду в области действия квантора получаем формулу, равносильную исходной формуле A.
Префиксная нормальная форма
Для каждой формулы логики предикатов существует равносильная ей формула, в которой имеются лишь операции отрицания, конъюнкции и дизъюнкции.
Префиксная нормальная форма (ПНФ) – это формула, имеющая вид Q1x1 Q2x2 … Qnxn P(x1, x2 … xn), гдеQ1x1 Q2x2 … Qnxn – кванторы; P(x1, x2 … xn) – формула, не имеющая кванторов, с операциями {&, , }. В логике предикатов у любой формы существует эквивалентная ей ПНФ.
Например, (x y P1(x, y) & x y P2(x, y)) x y P1(x, y) x y P2(x, y) xy P1(x, y) x y P2(x, y) x y P1(x, y) x y P2(x, y) x y P1(x, y) z y P2(z, y) xz (y P1(x, y) y P2(x, y)) x z y ( P1(x, y) P2(x, y))