Разбор формул

2.7 Каждая формула

• является атомом или
• имеет вид ¬F (для некоторой формулы F) или
• имеет вид (F Д G) (для некоторых формул F и G и некоторой бинарной связки Д).

Представляя формулу в одной из этих форм, мы начинаем ``разбирать'' её. Ясно, что ни одна формула не принадлежит более чем одной из трёх групп, и что ни одна формула не может быть представлена в виде ¬F более чем одним способом. Задача 2.9 ниже показывает, более того, что ни одна формула не может быть представлена в виде (F Д G) более чем одним способом. Эти факты, взятые вместе, показывают, что любая формула может быть разобрана в точности одним способом.

2.8 Любой префикс формулы F

• является строкой отрицаний (возможно пустой) или
• имеет больше левых чем правых скобок или
• равен F.

2.9 Ни одна формула не может быть представлена в виде (F Д G), где F и G – формулы и Д – бинарная связка, более чем одним способом.^*

Ниже, до конца части ``логика высказываний'', когда мы пишем формулы, мы будем обычно опускать некоторые скобки, включая пару самых внешних в формулах, которые имеют вид (F Д G). Для любых формул F1, F2,..., F_n (n і 1),

F1 & F2 & ··· & F_n означает (··· (F1 & F2) & ··· & F_n) Сокращение F1 Ъ F2 Ъ ··· Ъ F_n понимается схожим способом. Для любых формул F и G сокращение F є G означает (F Й G) & (G Й F).

---

Назад