Формулы. Алфавит исчисления предикатов содержит следующие символы

Алфавит исчисления предикатов содержит следующие символы:

· х₁,х₂,…х_n – предметные переменные;

· P^t_1, P^t_2,…, P^t_n – предикаты, где t – количество мест;

· - операции;

· - кванторы;

· () – скобки.

Последовательность перечисленных символов называется формулой.

При логической интерпретации формул логики предикатов возможны две основные ситуации:

1. Если в области М для формулы F существует такая подстановка констант вместо всех переменных, что F становится истинным высказыванием, то формула f называется выполнимой в области М. Если существует область М, где f выполнима, то f называется просто выполнимой.

Пример: .

2. Если формула f выполнима в М при любых подстановках констант, то она называется тождественно истинной в М. Формула f тождественно истинная в любых М называется тождественно истинной или общезначимой.

Пример: формула тождественно истинна для всех М, состоящих из одного элемента, а формула тождественно истинна.

Две (или более) формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения. В частности все тождественно истинные (тождественно ложные) формулы эквивалентны. Отметим, что если F₁ и F₂ эквивалентны, то формула F1 F₂, - тождественно истинна.

Пример (Задание №8):

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

Всякое натуральное число, делящееся на 12 делиться на 2, 4, 6.

Решение:

Введем на натуральном ряде предикаты:

А(х) – делиться на 12 (т. е. А(х)=1 тогда и только тогда, когда х делиться на 12),

В(х) – делиться на 2 (т. е. В(х)=1 тогда и только тогда, когда х делиться на 2),

С(х) – делиться на 4 (т. е. С(х)=1 тогда и только тогда, когда х делиться на 4),

D(х) – делиться на 6 (т. е. D(х)=1 тогда и только тогда, когда х делиться на 6).

.