Информатика -продвинутый курс
2 также имеет арность 2,
Количество аргументов у предиката называют его арностью.
Так, для наших примеров предикат «впадает» имеет арность 2 и при Х = «Волга», а Y = «Каспийское море» истинен, а при Х = «Дон», Y = «Бискайский залив» ложен. Предикат А в примере 2 также имеет арность 2, истинен при Х = 1, Y = 3 и ложен при X=3, Y=1.
Предикаты могут быть объединены в формулы с помощью логических связок (союзов): ^ («и», конъюнкция), v («или», дизъюнкция), ~ («не», отрицание), > («следует», импликация), - («тогда, и только тогда, когда», эквиваленция).
Ниже приведены таблицы истинности этих союзов, позволяющие определить, истинно или ложно значение формулы-связки при различных значениях, входящих в нее предикатов A и В.
Математически строго формулы логики предикатов определяются рекурсивно:
1) предикат есть формула;
2) если А
и В - формулы, то А, А^В,АvВ, А>B, А-В - тоже формулы;
3) других формул не бывает.
Многие формулы логики предикатов требуют использования кванторов, определяющих область значений переменных - аргументов предикатов. Используются кванторы общности (перевернутое А от английского «All» - все) и квантор существования - (перевернутое Е от английского «Exists» - «существует»). Запись "x читается «для любого х», «для каждого х»; $х - «существует х»,
«хотя бы для одного х». Кванторы связывают переменные предикатов, на которые они действуют, и превращают предикаты в высказывания.
Таблица 1.12 Истинность связок предикатов (И - истина, Л - ложь)
А | В | А^В | AvB | ~А | А>В | А-В |
И И Л Л | И Л И Л | И Л Л Л | И И И Л | Л Л И И | И Л И И | И Л Л И |
Пример.
Введем обозначения: А(х) - студент х учится отлично; В(х) - студент х получает повышенную стипендию. Теперь формула А (Иванов) > В (Иванов) означает: студент Иванов учится отлично, следовательно, студент Иванов получает повышенную стипендию, а формула с квантором общности (Vx) (A(x) —> В(х)) означает: каждый студент, который учится отлично, получает повышенную стипендию.
