Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Матлог_лекции.doc
Скачиваний:
3
Добавлен:
01.03.2025
Размер:
731 Кб
Скачать
☆

Предикатные формулы.

P(x1..xn) – элементарная формула (предикатное слово).

  1. Каждая элементарная формула – предикатная форула.

  2. Если P и Q – формулы, то P, (QP), (QP), (QP), (QP), (QP), (Q→P), "xP, xP - тоже формулы.

Приоритет: ( или ), , , , , , …

Говорят, что предикатная формула находится в приведенной форме, если кроме символов предикатов, в ней находятся значки , , , , , причем символ ‘’ относится только к предикатным буквам.

Любая предиктная формула может быть сведен к приведенной форме:

x→y= xy;

x / > y= xy;

x+y= xy  xy;

xy= xy  xy;

xy= (xy);

xy= (xy).

Пример: представить предикат в приведенной форме:

Говорят, что предикатная формула находится в предваренной нормальной форме, если она имеет вид: , где 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-значной логики.

  1. Константа: f(x)C;

  2. Отрицание Поста : =x+1 mod k.

  3. Отрицание Лукасевича ~x = k-1-х;

  4. xy- произведение по модулю k: xy =(xy) mod k;

  5. xy – min{x,y};

  6. Сложение по модулю k x+y=(x+y) mod k;

  7. Характеристическая функция 1го рода ;

  8. Характеристическая функция 2го рода (возведение в степень);

  9. Разность:

  10. Усеченная разность:

  11. - функция Вебба.

  12. xy=max{x,y}.

Пусть k=3.

x

y

~y

xy

xy

xy

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

Пример: доказать: