2015-05-20
425
Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении 
-го дифференциала 
было введено понятие первого дифференциала 
а затем -й дифференциал определялся как первый дифференциал от 
Определение. Пусть 
тогда:
1) каждая функция 
называется формулой над 
2) пусть 
– либо переменные, либо формулы над
3) если 
, то 
– называется формулой над 
Формулы будем обозначать заглавными буквами: 
, имея в виду функции, участвовавшие в построении формулы, или 
имея в виду переменные, вошедшие в формулу.
– формулы, участвовавшие в построении , называются подформулами.
Пример 5. Пусть 
тогда 
– формула над 
.
Сопоставим каждой формуле 
функцию 
Сопоставление будем производить в соответствии с индуктивным определением формулы.
1) Пусть 
тогда формуле 
сопоставим функцию 
2) Пусть 
– формула над 
и пусть ей по индуктивному предположению сопоставлена функция 
. Если – переменная, то есть 
, то ей сопоставим функцию 
Таким образом, каждой подформуле сопоставлена функция 
, где каждая функция зависит от своих переменных и их число может быть различным. Но 
переменных, перечисленных в формуле 
. В каждую функцию 
введем недостающие переменные (они будут фиктивными), получим, что каждой подформуле сопоставлена функция 
.
3) Тогда
Сопоставим формуле 
функцию 
следующим образом: пусть 
– произвольный набор переменных, пусть 
тогда 
Множество всех формул над M обозначим через < M >.
Определение. Две формулы N и D из <M> называются равными N=D или эквивалентными N~D, если функции, реализуемые ими, равны.
Упрощение записи формул:
1) внешние скобки можно опускать;
2) приоритет применения связок возрастает в следующем порядке: ~, 
, Ú, &;
3) связка 
над одной переменной сильнее всех связок;
4) если связка стоит над формулой, то сначала выполняется формула, затем отрицание;
5) если нет скобок, то операции ~ и 
выполняются в последнюю очередь.
Пример 6. Доказать эквивалентность формул (табл. 11).
~ (
).
Таблица 11
| x 1 | x 2 | x 3 | x 2Å x 3 | & 
| x 2 x 3
| x 3 x 2
| & | Ú x 1 | – |
