Семантическое дерево

Cтраница 1

Семантическое дерево имеет 2fc висячих вершин и для проверки общезначимости необходимо пройти 2fc маршрутов от корня до этих вершин. [1]

Неполное семантическое дерево. [2]

Бесконечное семантическое дерево полно, если каждая ветвь, выходящая из корня, определяет тотальную интерпретацию. Полное семантическое дерево, соответствующее Р, является конечным тогда и только тогда, когда Р тоже конечно. В противном случае все его ветви бесконечны. [3]

Семантическим деревом для 5 называется дерево Т, удовлетворяющее следующим условиям. [4]

Пример семантического дерева изображен на рис. 1.6. Если Р конечно, то все соответствующие ему семантические деревья обязательно конечны. Если Р бесконечно, то существуют конечные и бесконечные семантические деревья. Напомним, что бесконечное бинарное дерево непременно содержит хотя бы одну бесконечную ветвь. [5]

Узел N закрытого семантического дерева называется выводящим узлом, если все непосредственно следующие за N узлы являются опровергающими. [6]

Если Е - семантическое дерево содержит только один узел, то этот узел должен быть 1 0, и все доказано. [7]

В таком контексте семантическое дерево часто изображают корнем вниз. [8]

Говорят, что семантическое дерево Т будет закрытым, тогда и только тогда, когда каждая ветвь Т оканчивается опровергающим узлом. [9]

Пусть Т - замкнутое семантическое дерево, показанное на рис. 9, а. Узел ( 2) на рис. 9, b есть выводящий узел. Два его последователя - узлы ( 4) и ( 5) - опровергающие узлы. [10]

Наоборот, если для каждого полного семантического дерева Т для S существует конечное закрытое семантическое дерево, то каждая ветвь Т содержит опровергающий узел. Это означает, что каждая интерпретация опровергает S. Это завершает доказательство второй половины теоремы. [11]

Тривиальный алгоритм требует просмотра некоторого полного семантического дерева, соответствующего конечному множеству высказываний, встречающихся в А. Этот алгоритм крайне неэффективен: если формула А содержит п различных высказываний, то нужно рассматривать 2 интерпретаций. [12]

Множество дизъюнктов 5 называется опровергаемым семантическим деревом, если существует семантическое дерево для 5, ветви которого противоречивы. [13]

Алгоритм Квайна позволяет проходить не все семантическое дерево, а только его часть. Ak), последовательно придаются значения 0 и 1 и анализируются таблицы истинности формул, содержащих меньшее число переменных. [14]

Явно или неявно различные алгоритмы используют понятие семантического дерева. [15]

Страницы: 1 2 3 4