Конспект по матлогике
.pdf[¬ ] − [ ] + 1 – для отрицания нужно знать
[ & ] min{[ ], [ ]} [ ] max{[ ], [ ]}
Смешанная логика Поста: {− , … , [0, ] … , } 0 – неопределенность
[¬ ] −[ ] – не нужно знать для отрицания
[ & ] min{[ ], [ ]} [ ] max{[ ], [ ]}
40.Консервативность арифметики с большими числами
Расширим арифметику бесконечно большими числами – получим консервативную арифметику– расширение Рассматриваем константу Ω – бесконечно большое число Добавляем аксиомы:
0 < Ω, 1 < Ω, 2 < Ω, … или ( (… (0) … )) < Ω Ω + Ω = 2Ω (в то время, как ∞ + ∞ = ∞)
Теорема (о консервативности арифметики)
Утверждение, доказуемо в новой арифметике, доказуемо и в старой
□
Рассмотрим последовательность секвенции 1, 2, … , Предположим, что – максимальное число среди секвенции
Заменим во всех секвенциях Ω на + 1: [ 1, 2, … , ]Ω+1 все секвенции будут выводимы, так как + 1 < Ω
■
41.Проверка совместимости системы линейных неравенств
Имеем уравнение в КНФ ( |
… ¬ |
… ¬ )&(… )& … |
||
|
1 |
|
|
|
+ + (1 − ) + (1 − ) ≥ 1 |
где |
|||
{ 1 |
|
|
||
|
|
|
|
2 |
|
|
|
|
Решение этой системы является NP-полной задачей
42.Неразрешимость секвенциального исчисления предикатов
Теорема Исчисление предикатов алгоритмически неразрешимо
□
Сведем к равенству слов в полугруппе
=
( ( ( ( ( )))) = ( ( ))) – аксиома
Проблема равенства слов в полугруппе алгоритмически неразрешима (Взяли полугруппу, которая неразрешима относительно равенства, добавили , , , , , добавили
«=», добавили ( (… ) = (… )) )
■
43.Неполнота любого исчисления для доказательства применимости универсального алгоритма
Теорема Невозможно полное исчисление, в котором выводимы ! ( ) и ¬! ( )
□
Предположим, что оба выводимы Тогда получим проблему разрешающего алгоритма для применимости
21
■
22