Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Исчисление предикатовИсчисление предикатов определяется следующим образом. 1. Символы исчисления предикатов включают в себя: а) символы предметных переменных x 1, x 2,…, xn, …; б) символы предметных констант a 1, a 2,…, an, …; в) символы или имена предикатов A , A ,… A , …; г) символы или имена функций f , f ,… f , …; д) знаки логических операций Ø, É; е) символы кванторов ", $; ж) скобки и запятую – (,),. Верхние индексы указывают число аргументов, а нижние индексы служат для обычной нумерации. 2. Понятие формулы исчисления предикатов определяется в два этапа [4]. 1) Термы: а) предметные переменные x 1, x 2,…, xn,... и константы a 1, a 2,…, an, …; б) если fn – имя функции, а t 1, t 2,…, tn – термы, то fn (t 1, t 2,…, tn) – тоже терм. 2) Формулы: а) если An – имя предиката, а t 1, t 2,…, tn – термы, то An (t 1, t 2,…, tn) – формула; все вхождения переменных в формулу An (t 1, t 2,…, tn) являются свободными; б) если A (x) – формула, содержащая свободное вхождение переменной x, то выражения с кванторами " xA (x), $ xA (x) – формулы; в) если A и B – формулы, то Ø A, A É B – формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными. Так же, как и в исчислении высказываний, можно ввести знаки других логических операций (&, Ú, ~), используя соответствующие равносильности. Введение в исчисление предикатов термов расширяет правила образования формул, так как предметные переменные в элементарных предикатах могут быть заменены термами. Подстановка терма y в формулу A (x) называется правильной, если и только если: а) y является предметной константой; б) у является предметной переменной, и все вхождения y, полученные в результате подстановки, оказываются свободными в полученной в результате подстановки формуле. Например, в формулу " y (P (x, y) É Q (x)) вместо x можно подставить либо константу a: " y (P (a, y) É Q (a)), либо переменную z: " y (P (z, y) É Q (z)), но нельзя подставить переменную y, так как после подстановки получим формулу: " y (P (y, y) É Q (y)), в которой переменная y оказывается связанной. 3. Аксиомы исчисления предикатов. А1. A É (B É A). А2. (A É (B É C)) É ((A É B) É (A É C)). А3. (Ø B É Ø A) É ((Ø B É Ø A) É B). А4. " xA (x) É A (y), где формула A (x) не содержит переменной y. А5. A (x) É $ yA (y), где формула A (x) не содержит переменной y. 4. Правил вывода в исчислении предикатов четыре: П1 – modus ponens (m. p.) – правило заключения: ; П2 – правило связывания квантором общности: , где формула B не содержит переменной x; П3– правило связывания квантором существования: , где формула B не содержит переменной x; П4 – правило переименования связанной переменной. Связанную переменную в формуле A можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в A. Например, для формулы " xF (x) É $ xG (x) применяя правило переименования, получим формулу " yF (y) É $ zG (z). Для правил П2 и П3 условие, что формула B не содержит переменной x, является существенным. Это подтверждает следующий пример. Пример 3.4. Даны два предиката: B (x) = " x делится на 6"; A (x) = " x делится на 3". Тогда B (x) É A (x) = "Если x делится на 6, то x делится на 3" = И для всех x. Однако B (x) É " xA (x) = "Если x делится на 6, то все x делятся на 3" не всегда истинно. Таким образом, применение правила П2 неправомерно, если B зависит от x. Если же к формуле B (x) É A (x) применить правило П3, то получим $ xB (x) É A (x). После применения правила П2 получим $ xB (x) É " xA (x) = "Если некоторые x делится на 6, то все x делятся на 3" = Л. Таким образом, применение правила П3 также неправомерно, если B зависит от x. Для исчисления предикатов верны правила вывода 1 – 14 исчисления высказываний (раздел 3.2). Дополнительные правила вывода для исчисления предикатов следующие: 1. Введение квантора общности: , где A (y) – результат правильной подстановки переменной y вместо x в A (x).
2. Удаление квантора общности: , где A (y) – результат правильной подстановки терма y вместо x в A (x). 3. Отрицание квантора общности: . 4. Введение квантора существования: , где A (y) – результат правильной подстановки терма y вместо x в A (x). 5. Удаление квантора существования: , где A (x) – результат правильной подстановки переменной x вместо y в A (y). 6. Отрицание квантора существования: . Верна также теорема дедукции. Если Г – множество формул, A и B – формулы, и Г, A B. Тогда Г A É B. Сформулируем без доказательства важные утверждения для исчисления предикатов Теорема 3.1. Аксиомы исчисления предикатов – общезначимые формулы. Теорема 3.2. Любая выводимая в исчислении предикатов формула является общезначимой. Пример 3.5. Обосновать правильность рассуждения, построив вывод. а) Всякое нечетное натуральное число является разностью квадратов двух натуральных чисел. 5 – натуральное число. Следовательно, 5 – разность квадратов двух натуральных чисел Пусть M – множество натуральных чисел. Введем предикаты: A (x) = “ x – нечетное число”. B (x) – “ x – разность квадратов двух чисел”. Требуется построить вывод: " x (A (x) É B (x)), A (5) ├ B (5). Построим вывод. (1) " x (A (x) É B (x)) – гипотеза; (2) A (5) – гипотеза; (3) A (5) É B (5) – из (1) и удаления "; (4) B (5) – из (2) и (3) по m. p. б) Все словари полезны. Все полезные книги высоко ценятся. Следовательно, все словари высоко ценятся. Сначала формализуем наше рассуждение, введя следующие предикаты: A (x) = “ x – словарь”. B (x) = “ x – полезен”. C (x) = “ x высоко ценится”. Требуется построить следующий вывод: " x (A (x) É B (x)), " x (B (x) É C (x)) ├ " x (A (x) É C (x)). Построим этот вывод. (1) " x (A (x) É B (x)) – гипотеза; (2) " x (B (x) É C (x)) - гипотеза; (3) A (y) É B (y) – из (1) и удаления "; (4) B (y) É C (y) – из (2) и удаления "; (5) A (y) É C (y) – из (3) и (4) по правилу силлогизма; (6) " x (A (x) É C (x)) – из (5) и введения ". в) Всякий совершеннолетний человек, находящийся в здравом уме, допускается к голосованию. Джон не допущен к голосованию. Значит, он либо несовершеннолетний, либо не находится в здравом уме. Формализуем наше рассуждение, введя следующие предикаты: A (x) = “ x – совершеннолетний”. B (x) = “ x находится в здравом уме”. C (x) = “ x допущен к голосованию”. Введем константу d, обозначающую имя "Джон". Требуется построить следующий вывод: " x (A (x)& B (x) É C (x)), Ø C (d)) ├ Ø A (d) Ú Ø B (d). Построим этот вывод. (1) " x (A (x)& B (x) É C (x)) - гипотеза; (2) Ø C (d)) - гипотеза; (3) A (d)& B (d) É C (d) - из (1) и удаления "; (4) Ø C (d)) É Ø(A (d)& B (d)) – из (3) и правила контрапозиции; (5) Ø C (d)) É Ø A (d) Ú Ø B (d) – из (4) и отрицания конъюнкции; (7) Ø A (d) Ú Ø B (d) – из (2) и (5) по m. p. (8)
|