Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Равносильные формулы в исчислении предикатов.
Исчисление предикатов это расширение исчисления высказываний. Все идет по аналогии. В исчислении предикатов мы говорили, что формулы φ 1 и φ 2 являются равносильными, если они принимают одинаковые значения при одинаковых значениях переменных. 2 формулы Ф1 и Ф2 в исчислении предикатов являются равносильными, если они принимают одинаковые значения при одних и тех же значениях логических переменных (типа ), связанных (типа и ), свободных переменных и при одних и тех же значениях кванторов, т.е. при (равносильных кванторах) одноименных кванторах. P(x, y)↔ [x> y] – здесь x – связанная, а y – свободная переменные. . Поскольку в определении равносильности функции в ИП вложено понятие равносильности функции в ИВ, то равносильные формулы, рассмотренные в ИВ, автоматически входят в равносильные формулы в ИП. (ИВ), т.е. φ 1↔ φ 2. (ИП). Все остальные формулы переносятся аналогично. За счет кванторов мы расширяем тот список в ИП. 1) 2) рассмотрим формулы Де Моргана в исчислении предикатов.
Запишем полученные формулы. 3)
4) – это аналоги функций Де Моргана в алгебре исчисления предикатов. Для того, чтобы получить отрицание выражения начинающегося с квантора общности или существования необходимо сделать следующее: 1. над всеми связанными переменными необходимо поменять кванторы ( и наоборот). 2. знак отрицания вынести перед предикатом. Пример: Пример: {a1, a2,...an,...} 1. Но часто последовательность не имеет предела |=> наше условие не выполняется, отрицается. 2. {по свойству , то } тогда получим выражение: 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) , У – удаление квантора обязность. 15) 16) В предыдущих 13 формулах знак (↔) можно заменить на знак (~), получим отдельную формулу, которая является тождественно-истинной.
1. любое целое число есть рациональное 2. 1 – целое число. => 1 – рациональное число.
1-ое выражение перепишется 1. C–целые, R–рациональные. 2. С(1) R(1)=? Заключение в том, что имеющееся свойство P(x) конкретизуется для определенного значения y. 1. 2. C(1) 3. C(1)→ R(1) 4. R(1) {ПО: 2, 3}
|