Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Основные равносильности для предикатов




Пусть формулы А и В имеют одно и то же множество свободных переменных (в том числе и пустое).

Формулы А и В равносильны в данной интерпретации, если на любом наборе значений свободных переменных они принимают одинаковое значение (т. е. формулы выражают один и тот же предикат).

Формулы А и В равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М.

Формулы А и В равносильны (),если они равносильны на всех множествах.

· Для формул логики предикатов сохраняются все равносильности логики высказываний.

· Перенос квантора через отрицание

· Вынос квантора за скобки

  Q – не зависит от х
  Q – зависит от х
только в одну сторону!

Пусть P(x) – x пошел в театр, Q(x) – x пошел в кино, тогда

.

Но .

Аналогично, пусть P(x) – x делится на 2, Q(x) – x делится на 3, тогда

, но

.

· Перестановка одноименных кванторов

1. Перестановка разноименных кванторов

· Переименование связанных переменных

х, у принадлежат одной предметной области

· Отбрасывание квантора

 

 

Пример. Докажем общезначимость формулы . Для этого надо показать, что формула является теоремой исчисления предикатов.

Доказательство.

1. - аксиома исчисления предикатов.

2. - аксиома исчисления предикатов.

3. Для исчисления высказываний доказано правило транзитивности:

4. Из 1 и 2 по правилу транзитивности получаем:

5. Введение квантора существования (правило вывода исчисления предикатов ):

6. Введение квантора общности (правило вывода исчисления предикатов

):

7. Преобразуем связанную переменную {y/z}

8. Преобразуем связанную переменную {x/v}

Таким образом, теорема доказана.

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных