Интерпретация формул в теорий граф

Теория граф часто используется как математическая модель для различных приложений. Мы можем ее использовать и в области предикат. Граф определяется как множество вершин (или узлов) и множество ребер.

G = (V, И); V = {1,2,3... } вершины (узлы); И = {(x,y)}; x,yÎV; (x,y)ÎVxV

Для некоторой области D; D = V

И: принадлежащее И пары чисел (х,у) интерпретируют предикат (р(х,у)); х,уÎD

D	V
x	y	X	y
a	в

По существу, это просто кодирование.

Определим &,Ú,ù,® c предикатами интерпретируются теоретико-множественными операциями над графами: Ç,È,É,~.

Пример: 1) р(х) & q(x) ~ G₁ Ç G₂

2) p(x) Ú q(x) ~ G₁ Ú G₂

3) ùp(x) ® ~G

дополнение – это дополнение до полного графа

Интерпретация, где граф является моделью используется для решения задач на графах и для доказательства свойств графов.

Задача: «Сравнение графов на эквивалентность» (изоморфизм)

Пример:

- эти графы эквивалентны