Cтраница 3
Семантическая таблица составного высказывания К строится индуктивно, исходя из семантических таблиц высказываний, составляющих К. [31]
К концу каждой непротиворечивой ветви семантической таблицы Тп мы присоединяем атомарную семантическую таблицу, имеющую корнем X. При этом вершина X становится особой вершиной. [32]
Для устранения запрещенных фигур минимальным сужением сигнатуры модели i ifj строится семантическая таблица, каждой строке которой взаимно однозначно соответствует запрещенная фигура рассматриваемого модельного преобразования, каждому столбцу-дуга графа Gfj, участвующая в образовании запрещенных фигур. Покрытие семантической таблицы представляет собой такое множество ее столбцов [ /, что при удалении на графе Gfj всех дуг, соответствующих этим столбцам, устраняются все запрещенные фигуры, причем такое свойство множества С / отсутствует при вычеркивании хотя бы одного элемента из этого множества. Устранение запрещенных фигур минимальным сужением сигнатуры сводится к поиску минимального покрытия ( покрытия, обладающего минимальной мощностью) соответствующей семантической таблицей. Очевидно, что вид семантической таблицы и способы нахождения ее покрытий зависят от типа элементной базы, на которой реализуется память автомата. [33]
Определение 1.7.6. Доказательством, или выводом по Бету высказывания К называется замкнутая противоречивая семантическая таблица, в корне которой помещена помеченная формула / К. Замкнутая противоречивая таблица, имеющая в качестве корня tK называется опровержением по Бету высказывания К. [34]
После выполнения указанных преобразований для всех вершин Si, соответствующих строкам семантической таблицы, получаем ближайшую по метрике Хэмминга к выходной функции fj функцию возбуждения элемента памяти без фиксации воздействия. [35]
Заметим, что S t A - В, поскольку в приведенной семантической таблице ветвь ж, непротиворечива. Следовательно, существует такое означивание W, что W ( A) - t и W ( B) f, которое все высказывания из 5 подтверждает, в то время как высказывание А - В опровергает. [36]
Вершина семантической таблицы называется особой, если она встречается как корень некоторой атомарной семантической таблицы. В противном случае, вершина называется обычной. [37]
Для семантической таблицы Т индукция проводится по длине Т, то есть числу атомарных семантических таблиц в ней. [38]
Аналогия между схемой индукции для высказываний ( определение 1.2.2) и схемой индукции для семантических таблиц очевидна. [39]
Тогда V согласовано с вершиной X и, следовательно, согласовано с одной из ветвей атомарной семантической таблицы с X в корне. [40]
При этом будем полагать, что построение завершается, если на нечетном шаге 2п 1 в семантической таблице все ветви противоречивы. [41]
В этом месте мы должны отметить, что невыполнимое множество основных примеров, определяемое нашим алгоритмом построенш семантических таблиц, не всегда минимально. [42]
Построение семантической таблицы составного высказывания К мы начинаем с того, что записываем помеченную формулу tK или fK в корень семантической таблицы. [43]
Фактически, теорема Эрбрана предоставляет возможность при проверке выполнимости предложения или множества дизъюнктов S использовать методы логики высказываний, например, метод семантических таблиц или метод резолюций. Если 5 невыполнимо, то существует множество основных примеров дизъюнктов множества 5, которое также будет невыполнимым. Это конечное множество состоит из высказываний PL, и его невыполнимость может быть обнаружена известными нам методами. [44]
Для осуществления модельного преобразования G - ( 7M, основанного на характеризационных принципах, необходимо выделить все запрещенные фигуры, содержащиеся в ( /, построить семантическую таблицу, столбцам которой соответствуют запрещенные фигуры, а строкам - вершины, входящие в них. На пересечении ( /, /) в таблице ставится единица, если / - я вершина входит ву - ю запрещенную фигуру. Покрытие столбцов строками дает множество вершин, расщепление которых устраняет все запрещенные фигуры. Однако на больших по мощности графах задача выделения множества запрещенных фигур является весьма трудоемкой. [45]