81. Логика предикатов. Предикаты, формулы, кванторы, отрицание кванторов. Приведенные и нормальные формулы. Проблема разрешения.

Определение. Определенным на -местным предикатом называется предложение, содержащее переменных, превращающееся в высказывание при подстановке вместо этих переменных конкретных элементов множеств соответственно.

Определение. Кванторы: (квантор общности) называют правило, которое переводит -предикат в высказывание , которое истинно тождественно истинно; (квантор существования) называют правило, которое переводит -предикат в высказывание , которое ложно тождественно ложно.

Формулы логики предикатов:

1) - формула;

2) -формулы , , , - формулы;

3) - предикат, - переменная и - формулы.

Законы Де Моргана

1)

2)

Определение. Формулы и называются равносильными на множестве , если при подстановке множества , формулы превращаются в равносильные предикаты.

Определение. Приведенной формулой называется равносильная ей формула, в которой из операций алгебры высказываний имеется только , причем относится лишь к предикатным переменным и к высказываниям.

Определение. Нормальной формулой называется формула вида: , где - кванторы или , - приведенная формула без кванторов.

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

Было показано, что общего алгоритма не существует.

82. Исчисление предикатов. Формулы, аксиомы, правила вывода. Производное правило связывания квантором. Эквивалентность формул. Закон двойственности.

Определение. Исчисление предикатов – формальная аксиоматическая теория логики предикатов.

- логико-математический язык.

Аксиомами исчисления предикатов в называются формулы следующих видов:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

Правила вывода: , .

Принцип двойственности.

Определение. Пусть -формула, не содержащая . называется двойственной, если она может быть получена из заменой каждого вхождения символов , , , двойственной им операциям, т. е. , , , .

, где - предикатная формула, не содержит .

Законы Де Моргана:

- предикатная формула

1)

2)

83. Основная теорема о потоке (Теорема о max и min разрезе).

Определение. Ориентированный граф называется сетью, если все его вершины разбиты на 3 класса: источники, стоки и внутренние вершины.

, ,

Пусть , .

Определение. называется потоком, если - внутренней вершины .

Утверждение. Для .

Пусть и - источники и стоки сети соответственно.

Определение. Мощность потока называется число .

Далее рассмотрим сети с 1 источником и стоком .

Определение. , , а : . Тогда называется разрезом. Пусть , , .

Утверждение. Для и - разреза выполнена . , пусть задана пропускная способность . Будем говорить, что - поток является допустимым, если .

Определение. Пропускная способность разреза - это число .

Допустимый поток, который имеет максимально возможную мощность в данной сети, называется максимальным.

Теорема. Максимальная величина потока равна минимальной пропускной способности разрезов.