русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Понятие формулы логики предикатов. Эквивалентные соотношения. Префиксная нормальная форма


Дата добавления: 2013-12-24; просмотров: 5770; Нарушение авторских прав


Предикатная формула (формула логики предикатов) – формула, содержащая знаки булевых операций и кванторов.

Более точно, в формулах участвуют:

· символы предметных переменных X, Y, Z…;

· символы предикатов;

· логические символы ¬, &, , →, ~;

· символы кванторов и .

Предикатной формулой (одновременно определяются понятия свободных и связанных переменных) называется выражение, построенное по следующим правилам.

1) Если P – символ предиката, X1, X2,…,Xt – символы переменных (не обязательно различных), то P(X1, X2,…,Xt) – предикатная формула; все её переменные свободные.

2) Если А – формула, то ¬А – тоже формула с теми же свободными и связанными переменными.

3) Если А, В – формулы и нет переменных, свободных в одной из них и связанных в другой, то А&В, А В, А→В, А ~В – тоже формулы с теми же свободными и связанными переменными.

4) Если А – формула, содержащая свободную переменную Х (и, быть может, другие переменные – свободные и связанные), то выражения : А(Х : А(Х) – предикатные формулы; в каждой из них переменная Х переходит из множества свободных в множество связанных, т. е. число свободных переменных уменьшается, а число связанных увеличивается на 1. При этом формула А называется областью действия квантора.

В формуле должны быть правильным образом расставлены скобки, определяющие области действия кванторов и порядок выполнения логических и кванторных операций. Однако для сокращения записи могут быть удалены излишние скобки (считается, что знак квантора связывает сильнее, чем знак логической операции), также можно записывать кванторные формулы без знака “:”.

Пример 9.11.

Пусть Р(Х,Y) = Х ≤ Y для действительных чисел Х, Y R.

Это двухместный предикат с предметной областью на числовой плоскости. Область истинности – полуплоскость, ограниченная биссектрисой I и III координатных углов, включающая точки границы (на рис. показано серым цветом).



Формулы Р(Х,Y) и Р(Х,Y) – одноместные предикаты со свободными переменными Y и, соответственно, Х. Область истинности – пустое множество, т.к. не существует ни наибольшего, ни наименьшего среди действительных чисел.

Предикат Р(Х,Y) – одноместный со свободной переменной Y. Его область истинности – вся числовая ось, т. к. какое бы ни было Y, существует меньшее число Х.

Рассмотрим тот же предикат Р(Х,Y) = Х ≤ Y на предметной области натуральных чисел: Х, YN = . Область истинности предиката – целочисленные точки I координатного угла (включая точки оси координат), расположенные над биссектрисой и на ней (на рис. показано выделенными точками).

Область истинности для предиката Р(Х,Y) – пустое множество, а для : Р(Х,Y) область истинности состоит из одного числа 0. Отсюда можно заключить, что предикат есть истинное высказывание (обе переменных связанные), поскольку существует наименьшее натуральное число 0.

Формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения. В частности, все ТИ-формулы и ТЛ-формулы – эквивалентны.

Пример 9.12.

Если Р(Х,Y) = Х >Y , Q(X,Y) = XY, то (Х,Y) и Q (X,Y) – равносильные формулы; при других интерпретациях P и Q эти формулы могут не быть равносильными.

Пример 9.13.

Х Р(Х) и Х Р(Х) равносильны на одноэлементном множестве М: если существует подходящий Х, то, поскольку других значений нет, истинно и второе суждение. На множестве, содержащем более одного элемента, это уже не так.

Целью логики предикатов является исследование множества ТИ-формул, входящих в любую теорию. При этом выделяются две проблемы:

1) получение ТИ-формул (проблема построения порождающей процедуры);

2) проверка формулы на истинность (проблема разрешающей процедуры).

В логике предикатов используются различные приёмы, в том числе эквивалентные соотношения, позволяющие выполнять корректные преобразования предикатных формул. В логике (алгебре) предикатов справедливы все эквивалентные соотношения алгебры высказываний, а так же собственные эквивалентные соотношения, включающие связки .

1. Перенос квантора через отрицание (законы де Моргана для предикатов):

¬ x A(x) ≡ x ¬A(x);

¬ x A(x) ≡ x ¬A(x).

2. Вынесение квантора за скобки

Если формула А(Х) содержит свободную переменную Х, а формула В не содержит Х и в них нет переменных, свободных в одной из формул и связанных в другой, то:

Х (А(x) & В) ≡ ( x А(x)) & В;

Х (А(x) & В) ≡ ( x А (x)) & В;

Х (А(x) В) ≡ ( x А(x)) В;

Х (А(x) В) ≡ ( x А (x)) В.

3. Законы коммутативности для одноименных кванторов:

x( y A (x,y)) ≡ y( x А(x,y));

x ( y А (x, y)) ≡ y ( x А (x,y)).

Коммутативность дает возможность использовать более короткую запись:

Х, Y, Z : P(X,Y,Z) или Х,Y : Q(X,Y,Z) и т. п.

4. Законы дистрибутивности кванторов:

X : (P(X)&Q(X)) ≡ X : P(X) & X : Q(X)

X : (P(X) Q(X)) ≡ X : P(X) X : Q(X)

Предикатная формула находится в приведённой форме, если в ней используются операции квантефикации, отрицания, конъюнкции, дизъюнкции, причём отрицание относится лишь к предикатным буквам.

Пример 9.14.

Представить в приведённой форме предикат .

Решение.

Воспользуемся формулой замены операции импликации: .

.

Воспользуемся теоремами об отрицании кванторов. Получим:

. Так как кроме кванторов , символов конъюнкции, дизъюнкции и отрицания в формуле не используются другие символы предикатных операций, а отрицание относится только к предикатным буквам, то приведённая форма получена.



<== предыдущая лекция | следующая лекция ==>
Выполнимость и истинность | Вопросы и упражнения


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.