ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.01.2024
Просмотров: 295
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
.(y))( P1 (z)(P3.(y));
M=(P1.(z)P2.(w)P2.(х)P3.(y))(P1.(z)P2.(w)P1.(z) P3.(y));
M =(P1.(z)P2.(x)P3.(y))( P2.(w)P2.(x)P3.(y))
(P1.(z)P1.(z)P3.(y))(P2.(w)P1.(z)P3.(y));
M=(P1.(z)P2.(x)P3.(y))(P2.(w)P2.(x)P3.(y))
( P2.(w)P1.(z)P3.(y)).
Матрица содержит три элементарных дизъюнкта:
K={(P1.(z)P2.(x)P3.(y)); (P2.(w)P2.(x)P3.(y)); ( P2.(w)P1.(z)P3.(y))}.
Дизъюнкты матрицы содержат контрарные атомы P1.(z) и P1.(z), P2.(x) и P2.(w), свободные переменные которых могут быть одинаковыми или разными.
2.1.5 Сколемовская стандартная форма
Наличие разноименных кванторов усложняет вывод заключения. Поэтому рассмотрим класс формул, содержащих только кванторы всеобщности. Формула F называется - формулой, если она представлена в ПНФ и содержит только кванторы всеобщности, т.е.
F = x1x2 xn (M).
Для устранения кванторов существования из префикса формулы разработан алгоритм Сколема, вводящий сколемовскую функцию для связывания предметной переменной квантора существования с другими предметными переменными.
2.1.5.1 Алгоритм Сколема
Шаг 1. Представить формулу F в виде ПНФ, т.е.
F=x1x2xn(M), где i{; }Шаг 2. Найти в префиксе самый левый квантор существования:
a) если квантор находится на первом месте префикса, то вместо переменной, связанной квантором существования, подставить всюду предметную постоянную a , отличную от встречающихся предметных постоянных в матрице формулы, а квантор существования удалить
;
б) если квантор находится не на первом месте префикса, т.е. x1x2xi-1xi .., то выбрать (i-1)-местный функциональный символ, отличный от функциональных символов матрицы М и выполнить замену предметной переменной xi, связанной квантором существования, на функцию f(x1;x2 ; xi-1 ) и квантор существования удалить.
Шаг 3. Найти следующий справа квантор существования и перейти к исполнению шага 2, иначе конец.
Формулу ПНФ, полученную в результате введения сколемовской функции называют сколемовской стандартной формой формулы (ССФ).
Пример:
F=x1x2x3x4x5x6 ((P21 (x1; x2) P32(x3; x4; x5))P 23(x4; x6)).
1) заменить предметную переменную x1 на постоянную a:
F=x2x3x4x5x6 ((P21. (a; x2)P32.(x3; x4; x5))P23 (x4; x6));
2) заменить предметную переменную x4 на функцию f2 1.(x2;x3):
F=x2x3x5x6 ((P21.(a; x2)P32 (x3; f 21(x2; x3); x5))P23 (f21(x2; x3); x6));
f32(x2; x3 ; x5 ):
F=x2x3x5((P21(a; x2)P32(x3; f21(x2; x3); x5))
P23(f21(x2; x3);f32(x2; x3 ; x5 ))).
К={(P21(a; x2)P32(x3; f21(x2; x3); x5)); P23(f21(x2; x3);f32(x2; x3 ; x5 ))}.
2.2. Исчисление предикатов
Все методы и результаты исчисления высказываний можно перенести на исчисление предикатов, т. е. каждая теорема и любой вывод исчисления высказываний становятся теоремой и выводом исчисления предикатов, если пропозициональные переменные заменить формулами языка предикатов, причем все вхождения одной и той же переменной везде заменить одной и той же формулой. Каждая схема теоремы и каждая схема вывода также сохраняются, если под знаками пропозициональных переменных принимать формулы языка предикатов.
Для того, чтобы формализовать процесс рассуждения в исчислении предикатов, необходимо выделить класс формул, определяющих их эквивалентные преобразования при наличии кванторов, и класс отношений между формулами формирующих последовательную цепь формул от посылок до заключения. Следует отметить, что правила, аксиомы и законы исчисления высказываний есть подмножество правил, аксиом и законов исчисления предикатов. Дополнительные правила, аксиомы и законы определяют возможности введения и удаления кванторов, подстановки и cмeны кванторов.
2.2.1 Интерпретация формул
Под интерпретацией следует понимать систему, состоящую из непустого множества V, называемом универсумом, и однозначного отображения на двухэлементное множество {и; л}, которое каждому предикатному символу Pn (t1; t2; tn ) ставит в соответствие n - местное отношение на множестве V, каждому функциональному символу f ni (t1; t2; tn ) - n-местную операцию на множестве V, каждой предметной постоянной - элемент множества V.
При заданной интерпретации предметные переменные рассматриваются как переменные, пробегающие область универсума V, а символам логических и кванторных операций придается их обычный смысл.
Например, если универсум задан множеством целых чисел, то для x y z (P2 (+(x, y); z)):= “существуют числа x, y, z, для которых z больше суммы чисел х и у", то при х=2, у=3, z=10 имеем двухместную операцию =5 и двухместное отношение между целым числом 10 и значением операции +(2,3)=5. Отображение P2(5;10) на двухэлементное множество дает значение “и”. При х=2, у=3, z=4 имеем +(2,3)=5 и P2 (5; 4)=л.
На рис. 10 приведена графическая интерпретация этой задачи.
P2 (5; 4)
Рис.10 Интерпретация x y z (P2 (+(x, y); z)) для x=2, y=3, z=10 или z=4.
Другими словами, интерпретация функциональных символов определяется по значениям функции на универсуме, заданном на множестве термов, входящих аргументами в эту функцию, а интерпретация предикатных символов по отображению на двухэлементное множество {и; л}.
Особо следует рассмотреть влияние свободных переменных на интерпретацию формул исчисления предикатов.
Формула, не содержащая свободных переменных, называется
замкнутой и представляет собой высказывание об элементах, функциях и отношениях, которое принимает значение и или л. На рис. 10 рассмотрен случай замкнутой формулы.
Формула, содержащая свободные переменные, называется открытой и представляет собой отношений, заданное на множестве V,
Это отношение может быть истинным для одних значений из области интепретации и ложным для других.
При такой интерпретации выделяют три класса формул, тождественно истинные, тождественно ложные и выполнимые.
Тождественно истинные формулы (или тавтологии) -это особый класс формул исчисления предикатов, которые принимают значение “истины” для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов; эти формулы играют роль законов и аксиом исчисления предикатов; любые подстановки и замещения в тождественно истинной формуле не изменяют ее значения.
Например,
для предиката P2(x, y):=”число x меньше числа y” формула xy(P2(x, y)):=”для любого целого числа x найдется число y, большее числа x” является тождественно истинной;
для любой F(x) формула x(F(x))x(F(x)):=“формула ”существуют x, для которых F(x)=и”, эквивалентна формуле “не для всех x F(x)=л”” является тождественно истинной.
Тождественно ложные формулы (или противоречие)-это особый класс формул исчисления предикатов, которые принимают значение “ложь” для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов; любые подстановки и замещения в тождественно ложной формуле не изменяют ее значения.
Например, для предиката P2(x, y):=”число x меньше числа y” формула xy(P2(x, y)):=”существует целое число x, которое меньше любого целого числа y” является тождественно ложной;
для любой F(x) формула x(F(x))x(F(x)):=”“существует x, для которой F(x)=и”, и “для всех x F(x)=л ”” является тождественно ложной.
Выполнимые формулы- это особый класс формул исчисления предикатов, которые принимают значение “истина”в некоторой области, т.е. не для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов.
-
по закону дистрибутивности:
M=(P1.(z)P2.(w)P2.(х)P3.(y))(P1.(z)P2.(w)P1.(z) P3.(y));
-
по закону дистрибутивности:
M =(P1.(z)P2.(x)P3.(y))( P2.(w)P2.(x)P3.(y))
(P1.(z)P1.(z)P3.(y))(P2.(w)P1.(z)P3.(y));
-
по закону исключенного третьего:
M=(P1.(z)P2.(x)P3.(y))(P2.(w)P2.(x)P3.(y))
( P2.(w)P1.(z)P3.(y)).
Матрица содержит три элементарных дизъюнкта:
K={(P1.(z)P2.(x)P3.(y)); (P2.(w)P2.(x)P3.(y)); ( P2.(w)P1.(z)P3.(y))}.
Дизъюнкты матрицы содержат контрарные атомы P1.(z) и P1.(z), P2.(x) и P2.(w), свободные переменные которых могут быть одинаковыми или разными.
2.1.5 Сколемовская стандартная форма
Наличие разноименных кванторов усложняет вывод заключения. Поэтому рассмотрим класс формул, содержащих только кванторы всеобщности. Формула F называется - формулой, если она представлена в ПНФ и содержит только кванторы всеобщности, т.е.
F = x1x2 xn (M).
Для устранения кванторов существования из префикса формулы разработан алгоритм Сколема, вводящий сколемовскую функцию для связывания предметной переменной квантора существования с другими предметными переменными.
2.1.5.1 Алгоритм Сколема
Шаг 1. Представить формулу F в виде ПНФ, т.е.
F=x1x2xn(M), где i{; }Шаг 2. Найти в префиксе самый левый квантор существования:
a) если квантор находится на первом месте префикса, то вместо переменной, связанной квантором существования, подставить всюду предметную постоянную a , отличную от встречающихся предметных постоянных в матрице формулы, а квантор существования удалить
;
б) если квантор находится не на первом месте префикса, т.е. x1x2xi-1xi .., то выбрать (i-1)-местный функциональный символ, отличный от функциональных символов матрицы М и выполнить замену предметной переменной xi, связанной квантором существования, на функцию f(x1;x2 ; xi-1 ) и квантор существования удалить.
Шаг 3. Найти следующий справа квантор существования и перейти к исполнению шага 2, иначе конец.
Формулу ПНФ, полученную в результате введения сколемовской функции называют сколемовской стандартной формой формулы (ССФ).
Пример:
F=x1x2x3x4x5x6 ((P21 (x1; x2) P32(x3; x4; x5))P 23(x4; x6)).
1) заменить предметную переменную x1 на постоянную a:
F=x2x3x4x5x6 ((P21. (a; x2)P32.(x3; x4; x5))P23 (x4; x6));
2) заменить предметную переменную x4 на функцию f2 1.(x2;x3):
F=x2x3x5x6 ((P21.(a; x2)P32 (x3; f 21(x2; x3); x5))P23 (f21(x2; x3); x6));
-
заменить предметную переменную x6 на функцию
f32(x2; x3 ; x5 ):
F=x2x3x5((P21(a; x2)P32(x3; f21(x2; x3); x5))
P23(f21(x2; x3);f32(x2; x3 ; x5 ))).
К={(P21(a; x2)P32(x3; f21(x2; x3); x5)); P23(f21(x2; x3);f32(x2; x3 ; x5 ))}.
2.2. Исчисление предикатов
Все методы и результаты исчисления высказываний можно перенести на исчисление предикатов, т. е. каждая теорема и любой вывод исчисления высказываний становятся теоремой и выводом исчисления предикатов, если пропозициональные переменные заменить формулами языка предикатов, причем все вхождения одной и той же переменной везде заменить одной и той же формулой. Каждая схема теоремы и каждая схема вывода также сохраняются, если под знаками пропозициональных переменных принимать формулы языка предикатов.
Для того, чтобы формализовать процесс рассуждения в исчислении предикатов, необходимо выделить класс формул, определяющих их эквивалентные преобразования при наличии кванторов, и класс отношений между формулами формирующих последовательную цепь формул от посылок до заключения. Следует отметить, что правила, аксиомы и законы исчисления высказываний есть подмножество правил, аксиом и законов исчисления предикатов. Дополнительные правила, аксиомы и законы определяют возможности введения и удаления кванторов, подстановки и cмeны кванторов.
2.2.1 Интерпретация формул
Под интерпретацией следует понимать систему, состоящую из непустого множества V, называемом универсумом, и однозначного отображения на двухэлементное множество {и; л}, которое каждому предикатному символу Pn (t1; t2; tn ) ставит в соответствие n - местное отношение на множестве V, каждому функциональному символу f ni (t1; t2; tn ) - n-местную операцию на множестве V, каждой предметной постоянной - элемент множества V.
При заданной интерпретации предметные переменные рассматриваются как переменные, пробегающие область универсума V, а символам логических и кванторных операций придается их обычный смысл.
Например, если универсум задан множеством целых чисел, то для x y z (P2 (+(x, y); z)):= “существуют числа x, y, z, для которых z больше суммы чисел х и у", то при х=2, у=3, z=10 имеем двухместную операцию =5 и двухместное отношение между целым числом 10 и значением операции +(2,3)=5. Отображение P2(5;10) на двухэлементное множество дает значение “и”. При х=2, у=3, z=4 имеем +(2,3)=5 и P2 (5; 4)=л.
На рис. 10 приведена графическая интерпретация этой задачи.
P2 (5; 4)
Рис.10 Интерпретация x y z (P2 (+(x, y); z)) для x=2, y=3, z=10 или z=4.
Другими словами, интерпретация функциональных символов определяется по значениям функции на универсуме, заданном на множестве термов, входящих аргументами в эту функцию, а интерпретация предикатных символов по отображению на двухэлементное множество {и; л}.
Особо следует рассмотреть влияние свободных переменных на интерпретацию формул исчисления предикатов.
Формула, не содержащая свободных переменных, называется
замкнутой и представляет собой высказывание об элементах, функциях и отношениях, которое принимает значение и или л. На рис. 10 рассмотрен случай замкнутой формулы.
Формула, содержащая свободные переменные, называется открытой и представляет собой отношений, заданное на множестве V,
Это отношение может быть истинным для одних значений из области интепретации и ложным для других.
При такой интерпретации выделяют три класса формул, тождественно истинные, тождественно ложные и выполнимые.
Тождественно истинные формулы (или тавтологии) -это особый класс формул исчисления предикатов, которые принимают значение “истины” для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов; эти формулы играют роль законов и аксиом исчисления предикатов; любые подстановки и замещения в тождественно истинной формуле не изменяют ее значения.
Например,
для предиката P2(x, y):=”число x меньше числа y” формула xy(P2(x, y)):=”для любого целого числа x найдется число y, большее числа x” является тождественно истинной;
для любой F(x) формула x(F(x))x(F(x)):=“формула ”существуют x, для которых F(x)=и”, эквивалентна формуле “не для всех x F(x)=л”” является тождественно истинной.
Тождественно ложные формулы (или противоречие)-это особый класс формул исчисления предикатов, которые принимают значение “ложь” для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов; любые подстановки и замещения в тождественно ложной формуле не изменяют ее значения.
Например, для предиката P2(x, y):=”число x меньше числа y” формула xy(P2(x, y)):=”существует целое число x, которое меньше любого целого числа y” является тождественно ложной;
для любой F(x) формула x(F(x))x(F(x)):=”“существует x, для которой F(x)=и”, и “для всех x F(x)=л ”” является тождественно ложной.
Выполнимые формулы- это особый класс формул исчисления предикатов, которые принимают значение “истина”в некоторой области, т.е. не для всех интерпретаций входящих в нее предметных постоянных, функциональных и предикатных символов.