- •Теория множеств Основные понятия
- •Способы задания множеств
- •Декартово произведение и векторы
- •Соответствия
- •Отношения
- •Разбиения
- •Факторизация отображения
- •Отношения порядка
- •Теория алгоритмов. Понятие алгоритма.
- •Машина Тьюринга.
- •Числовая функция
- •Кодировка машин Тьюринга.
- •Алгоритмически неразрешимые проблемы.
- •Проблема применимости.
- •Нормальные алгоритмы Маркова
- •Рекурсивные функции.
- •Операция минимизации.
- •Предикаты Основные понятия
- •Операции над предикатами
- •Предикатные формулы.
- •Основные понятия
- •Функции k-значной логики.
- •Законы Моргана:
- •Формальные теории Основные понятия
- •Свойства вывода из гипотез
- •Классическое исчисление высказываний
Предикатные формулы.
P(x1..xn) – элементарная формула (предикатное слово).
Каждая элементарная формула – предикатная форула.
Если P и Q – формулы, то P, (QP), (QP), (QP), (QP), (QP), (Q→P), "xP, xP - тоже формулы.
Приоритет: ( или ), , , , , , …
Говорят, что предикатная формула находится в приведенной форме, если кроме символов предикатов, в ней находятся значки , , , , , причем символ ‘’ относится только к предикатным буквам.
Любая предиктная формула может быть сведен к приведенной форме:
x→y= xy;
x / >
y= xy;
x+y= xy xy;
xy= xy xy;
xy= (xy);
xy= (xy).
Пример: представить предикат в
приведенной форме:
Говорят, что предикатная формула
находится в предваренной нормальной
форме, если она имеет вид:
,
где D – квантор общности
или квантор существования, А – формула,
находящаяся в приведенной форме, не
содержащая кванторов.
Пример: привести к предваренной нормальной форме предикат:
К – значные логики
Основные понятия
Ek={0,1,2…k-1}.
Функции k-значной логики:
.
- множество функций k-значной
логики для n-аргументов.
x1 |
x2 |
… |
xn-1 |
xn |
f |
0 |
0 |
… |
0 |
0 |
a1 |
0 |
0 |
… |
0 |
1 |
a2 |
0 |
0 |
… |
0 |
2 |
a3 |
… |
… |
… |
… |
… |
... |
0 |
0 |
… |
0 |
k-1 |
ak |
0 |
0 |
… |
1 |
0 |
|
… |
… |
… |
… |
… |
… |
k-1 |
k-1 |
… |
k-1 |
k-1 |
akn |
Функции k-значной логики.
Константа: f(x)C;
Отрицание Поста
:
=x+1
mod k.
Отрицание Лукасевича ~x = k-1-х;
xy- произведение по модулю k: xy =(xy) mod k;
xy – min{x,y};
Сложение по модулю k x+y=(x+y) mod k;
Характеристическая функция 1го рода
;Характеристическая функция 2го рода
(возведение в степень);Разность:
Усеченная разность:
- функция Вебба.xy=max{x,y}.
Пусть k=3.
x |
y |
|
~y |
xy |
xy |
xy |
x+y |
j1(x) |
J2(y) |
x-y |
|
V3(x,y) |
0 |
0 |
1 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
2 |
0 |
2 |
0 |
2 |
1 |
0 |
0 |
0 |
2 |
2 |
0 |
2 |
1 |
0 |
0 |
1 |
0 |
2 |
2 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
2 |
1 |
1 |
2 |
1 |
1 |
1 |
1 |
2 |
1 |
0 |
0 |
0 |
2 |
1 |
2 |
2 |
0 |
2 |
1 |
2 |
0 |
1 |
2 |
2 |
0 |
0 |
2 |
0 |
0 |
2 |
0 |
0 |
2 |
2 |
0 |
0 |
2 |
2 |
0 |
2 |
1 |
0 |
1 |
2 |
1 |
2 |
0 |
0 |
0 |
1 |
1 |
0 |
2 |
2 |
0 |
0 |
1 |
2 |
2 |
1 |
0 |
2 |
0 |
0 |
0 |
Пример: доказать:
