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

Определение. Формулой над множеством Ф функциональных символов будем называть всякое (и только такое) выражение вида:

1) 0, 1– константы;

2) x – любая переменная из множества X;

3) выражения вида (U B), где U, B – формулы, – символ любой двуместной связки (&,Ú,Å,~,®,|,¯);

4) – отрицание.

Для сокращения записи формул принимаются следующие соглашения:

а) внешние скобки опускаются;

б) считается, что операция отрицания выполняется в первую очередь;

в) следующей по старшинству считается операция конъюнкции; затем – все остальные.

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