lec09_2
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Часть 3.
k-значные логики.
k-значные логики вводятся как обобщения двузначной логики.
!!! В k-значных логиках сохраняются многие свойства и результаты двузначной логики. Однако наблюдаются явления, обнаруживающее их принципиальное отличие от БА.
Пусть k≥3, Ek= {0,1,…,k–1}.
Функция (x1, … xn) называется функцией k-значной логики, или k-значной функцией, если
задает отображение : Ek x Ek x … x Ek Ek.
n
Множество всех таких функций обозначается через Pk.
При k=2 получаем БА P2.
4
Существенные и фиктивные переменные.
Пусть задана (x1, x2, … xi, … xn) Pk. xi называется фиктивной переменной, если вариация его значения не влияет на значение функции, т.е.
(x1, … xi-1, xi+1 … xn); (aj,al): xi = a1,…ak, (1≤j,l≤k) :
(x1, … xi-1, aj, xi+1 … xn-1) = (x1, … xi-1, al, xi+1 … xn).
xi - существенная переменная, если минимум два xi Ek (xi=a1, xi=a2):
(x1, … xi-1, a1, xi+1 … xn-1) ≠ (x1, … xi-1, a2, xi+1 … xn).
k-значные функции задаются лексикографически (аналогично БА) и формулами (отличается от БА).
Равенство k-значных функций рассматриваем с точностью до фиктивных переменных (или до значений в лексикографической таблице).
5
Утверждение 9.3. (о числе k-значных функций от n-переменных).k k n различных k-значных функций от n-переменных.
Доказательство: аналогично доказательству теоремы 2.5. (о числе БФ от n- переменных).
«Элементарные» функции k-значной логики.
n=0.
Константы: 0, 1, . . . , k−1. n=1.
1)≡x: тождественная функция x;
2)x = x+1: отрицание Поста x;
3)x = (k−1)−x: отрицание Лукашевича x;
4)−x = k−x: минус x.
Характеристические функции Ji(x), ji(x), i Ek:
x |
≡x |
x |
x |
−x |
|
|
|
|
|
0 |
0 |
1 |
k−1 |
0 |
|
|
|
|
|
1 |
1 |
2 |
k−2 |
k−1 |
|
|
|
|
|
… |
… |
… |
… |
… |
|
|
|
|
|
k−2 |
k−2 k−1 |
1 |
2 |
|
|
|
|
|
|
k−1 |
k−1 |
0 |
0 |
1 |
|
|
|
|
|
Ji(x)= |
k−1, |
если = i |
ji(x)= |
1, |
если = i |
|
|
0, |
если ≠ i |
|
0, |
если ≠ i |
6 |
|
|
|
|
|
|
n=2.
1)x+y (mod k) – сложение по модулю k;
2)x−y (mod k) – вычитание по модулю k;
3)x·y (mod k) – умножение по модулю k; 4,5) минимум и максимум.
min(x,y)= |
x, |
если ≤ |
max(x,y)= |
y, |
если > |
6) x − y - усеченная разность (или x y).
x, если ≥ y, если <
− = |
x−y, |
если ≥ y |
|
|
|
0, если < y |
|
7) x y - импликация. |
|
k−1, |
если ≤ |
→ = |
|
||
(k−1)−(x−y), если > |
|||
8) υk(x,y) = (max(x,y)+1) mod k – функция Вебба.
7
Значения некоторых «элементарных» функций при k=3.
x |
y |
max(x,y) |
min(x,y) |
x+y xy |
x−y |
x y x−y υk(x,y) |
|||
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
2 |
2 |
2 |
|
|
|
|
|
|
|
|
|
|
0 |
2 |
2 |
0 |
2 |
0 |
0 |
2 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
2 |
1 |
0 |
2 |
0 |
2 |
|
|
|
|
|
|
|
|
|
|
1 |
2 |
2 |
1 |
0 |
2 |
0 |
2 |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
2 |
0 |
2 |
0 |
2 |
0 |
2 |
0 |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
2 |
1 |
2 |
1 |
0 |
2 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
2 |
2 |
2 |
2 |
1 |
1 |
0 |
2 |
0 |
2 |
|
|
|
|
|
|
|
|
|
|
8
Функции обобщения.
min(x1, x2, … xn) = min(x1, min(x2, … xn)); max(x1, x2, … xn) = max(x1, max(x2, … xn)).
xs = x · x · … ·
s
x. – степень x.
Обобщение функций БА на k-значные функции.
n= |
P2 |
Pk, k≥3 |
обобщение |
|
0 |
0, 1 |
0, 1, . . . , k−1 |
константы |
|
|
|
|
|
|
1 |
x |
x |
тождество, |
|
|
x |
x, x |
отрицание |
|
|
|
|
|
|
2 |
x y |
min(x,y) |
конъюнкция или минимум |
|
|
x y |
max(x,y) |
дизъюнкция или максимум |
|
|
x y x + y (mod k) |
сложение по модулю k |
|
|
|
x y |
x y |
импликация |
9 |
|
|
|
|
|
|
|
|
|
|
Задание формулы k-значной логики.
Пусть множество A Pk, причем в A каждая функция имеет свое, отличное от других функций, обозначение. Формула над A определяется по индукции.
Базис индукции: Если x - переменная, то выражение x – формула.
Индуктивный переход: Если f - обозначение m-местной функции из A и F1, … , Fm – уже построенные формулы или переменные (не обязательно различные), то выражение f (F1, … , Fm) – формула.
Пример 9.6. Построение формул над множеством А в P4. |
|||
A = {0, 1, 2, 3, x2, x, x, x·y } P . |
|
|
|
|
4 |
|
|
Формула по базису индукции для переменной x: F1 = x. |
|||
F2=x2 |
формула по индуктивному |
F4=2·x2 |
формула по индуктивному |
|
переходу для функции x2 A и уже |
|
переходу для функции x·y A и |
|
построенной формулы F1; |
|
уже построенных формул F3, F2; |
F3=2 |
формула по индуктивному |
F5= (2·x2) |
формула по индуктивному |
|
переходу для функции 2 A; |
|
переходу для функции x A и |
|
|
|
уже построенной формулы F4. |
10