Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении -го дифференциала было введено понятие первого дифференциала а затем -й дифференциал определялся как первый дифференциал от
Определение. Пусть тогда:
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 | – |