ВУЗ:
Составители:
Рубрика:
Как видно из определения, каждая формула, если это не атом,
начинается и заканчивается скобкой, причем внутри формулы должен
соблюдаться баланс открывающих и закрывающих скобок. Это можно
проиллюстрировать на нашем примере, сопоставив каждой паре соот-
ветствующих друг другу скобок один и тот же номер:
(
1
(
2
A ∧ (
3
¬B )
3
)
2
∨C )
1
или выделив каждую подформулу (не являющуюся атомом) подчерки-
ванием — от скобки до скобки:
((A ∧ (¬B)) ∨ C).
m
∨
¡
¡
@
@
m
∧
m
C
¡
¡
@
@
m
A
m
¬
m
B
Структура формулы, ее конструкция из связок и подформул еще
более явно выражена в дереве формулы F
1
. В каждой вершине тако-
го дерева находится логическая связка, и из
нее выходит две (для бинарных связок) или
одна (для отрицания) ветвь, ведущая к де-
реву соответствующей подформулы. В кон-
цевых вершинах (листьях дерева) находятся
атомы.
Часто принимается соглашение о приоритетах логических связок:
¬, ∧, ∨, ⇒, ⇔ (в порядке убывания приоритета),
позволяющее сократить число скобок. Мы тогда можем записать: F
1
=
A ∧ ¬B ∨ C.
При заданной интерпретации нетрудно определить истинностное
значение любой формулы. Для этого можно использовать таблицы зна-
чений.
Пример 2. Построим таблицу значений для формулы F
2
= ¬A ∨
B ⇒ C:
A B C ¬A ¬A ∨ B F
0 0 0 1 1 0
0 0 1 1 1 1
0 1 0 1 1 0
0 1 1 1 1 1
1 0 0 0 0 1
1 0 1 0 0 1
1 1 0 0 1 0
1 1 1 0 1 1
9
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
