Алфавит - любое непустое множество, состоит из символов.
Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего упоминают:
- Квантор всеобщности (обозначение:
, читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»). - Квантор существования (обозначение:
, читается: «существует…» или «найдётся…»).
Формула - слово для моделирования высказывания.
Правила построения:
1) Каждая нульместная предикатная переменная есть формула;
2) если — n-местная предикатная переменная, то
есть формула, в которой все предметные переменные
свободны;
3) если — формула, то
— также формула. Свободные (связанные) предметные переменные в формуле
те и только те, которые являются свободными (связанными) в
;
4) если — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения
также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул , называются свободными (связанными) и в новых формулах;
5) если — формула и
— предметная переменная, входящая в
свободно, то выражения
и
также являются формулами, в которых переменная
связанная, а все остальные предметные переменные, входящие в формулу
свободно или связанно, остаются и в новых формулах соответственно такими же;
Правила перехода к равносильным формулам:
1) перенос квантора через отрицание
2) вынос квантора за скобки
3) перестановка одноименных кванторов
4) переименование связанных переменных
Интерпретацией формулы F называют приписывание значений И или Л входящим в нее переменным.
Формула F называется противоречивой тогда и только тогда, когда она ложна при всех интерпретациях (в противном случае непротиворечива).
Формула F называется общезначимой тогда и только тогда, когда она истинна при всех интерпретациях (необщезначима в противном случае).
