Головна

Функціонально решітка поста. Замкнені класи T0, T1.

  1.  Абстрактні класи.
  2.  Найважливіші замкнуті класи.
  3.  Виготський. Теорія вищих психічних функцій.
  4.  Графічні способи функціонального опису систем
  5.  Декларація функцій.
  6.  Деталізований аналіз управлінських функцій.
  7.  дружні класи

Клас (безліч) булевих функцій функціонально замкнутий, якщо разом з функціями він містить всі їх суперпозиції. Клас всіх булевих функцій замкнутий. Клас функцій від однієї змінної замкнутий. Клас булевих функцій від двох змінних не замкнутий, так як якщо взяти дві функції від двох змінних f = x ~ y та g = t & p, то їх чотири суперпозиції: (t & p) ~ y, x ~ (t & p) , (x ~ y) & p і t & (x ~ y) будуть залежати від трьох змінних.

клас T  - Це клас функцій, що зберігають нуль. Функція належить T  , Якщо у всіх нулях вона дорівнює нулю. Наприклад, з 16 функцій від двох змінних функції: f0, ..., f7 належать T  , Так як при x = 0 і y = 0 ці функції мають значення нуль. Тоді як функції: f8, ..., f15 не належать T  , Так як при x = 0 і y = 0 ці функції мають значення одиниця.

клас T  - Це клас функцій, що зберігають одиницю. Функція належить T  , Якщо у всіх одиницях вона дорівнює одиниці. Наприклад, з 16 функцій від двох змінних вісім функцій з непарними номерами: f1, f3, ..., f13, f15 належать T  , Так як при x = 1 і y = 1 ці функції мають значення одиниця. Тоді як вісім функцій з парними номерами: f0, f2, ..., f12, f14 не належать T  , Так як при x = 1 і y = 1 ці функції мають значення нуль.

8. Теорема Поста, її необхідність. Таблиця Посту.

теорема Посту: для того, щоб система булевих функцій F = {F1, ..., Fm} була повною, необхідно і достатньо, щоб для кожного з класів T  , T  , S, L і M знайшлася функція Fj з системи F, яка не належить цьому класу.

Доведення необхідності: Класи T  , T  , S, L і M попарно різні і не збігаються з класом всіх булевих функцій. Якби всі функції системи F належали якомусь з цих класів, то в силу замкнутості цього класу система F не була б повною. Необхідність теореми доведена.

 функція T T S L M
+ + - - +
+ + - - +
- - + + -
   f0  f1  f2  f3  f4  f5  f6  f7  f8  f9  f10  f11  f12  f13  f14  f15
T + + + + + + + + - - - - - - - -
T - + - + - + - + - + - + - + - +
S - - - + - + - - - - + - + - - -
L + - - + - + + - - + + - + - - +
M + + - + - + - + - - - - - - - +



 Формули логіки висловлювань та їх еквівалентність. Правило рівносильних перетворень. |  Двоїстість. Закон подвійності. |  Нормальні форми формул. Теорема про єдиності СДНФ і СКНФ. |  Мінімізація ДНФ. Метод мінімізують карт. |  Аксіоматичні теорії. Визначення та властивості обчислення висловлювань. |  Повнота і несуперечність обчислення висловлювань. Незалежність аксіом. |  Предикати, квантори, їх область дії. Вільні і зв'язані змінні. |  Равносильность формул логіки предикатів. Правила переходу до рівносильним формулам в логіці предикатів, що збігаються з аналогічними правилами в логіці висловлювань. |  Здійснимість і общезначімость формул логіки предикатів. Теорема Черча. |  Общезначімость виведених в численні предикатів формул. |

© 2016-2022  um.co.ua - учбові матеріали та реферати