Классы т0, т1.

Т0 — класс функций, сохраняющих 0 fT0 <=>f(0,0,...,0,0)=0

T0 – x, &,V,|+|^2,0

T0 - x,≡,→,|,↓,1

Число наборов определяющих значение функции из класса Т0 равно 2^n-1

Т0 — замкнутый клас. Для того, чтобы показать это, достаточно показать, что элементарная суперпозиция функции, принадлежащей Т0, так же принадлежит класу Т0.

f0,f1,...fkT0

ФТ0?

Ф=(y1,...,yn)=f0(f(x11^0,...,x1k^0),...,fk(xk1^0,...,xkk^0))=f0(0,...0)

Т1 — класс функций сохраняющий 1

fT1 <=>f(1,1,...,1,1)=1

Т1 — x,1,&,V,≡,→

T1 - x,0,|+|^2,|,↓

Число булевых функций 2^n-1.[T1]=T1

19. Содержание

    • Множества. Основные понятия.
    • Операции над множествами и их свойства.
    • Декартово произведение. Разбиение множеств.
    • Алгебра множеств
    • Отношение. Бинарное отношение
    • Алгебра бинарных отношений
    • Отображение. Виды отображений
    • Отношение порядка. Изоморфизм упорядоченных множеств.
    • Алгебраические системы. Изоморфизм алгебраических систем.
    • Функции алгебры логики.
    • Формулы. Реализация функций формулами.
    • Эквивалентность формул. Свойства элементарных булевых функций.
    • Двойственные функции. Принцип двойственности
    • Разложение булевых функций по переменным. Сднф.
    • Полнота и замкнутость.
    • Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
    • Классы т0, т1.
    • Класс s.
    • Класс м.
    • Класс l
    • Теорема о функциональной полноте. Проверка системы функций на полноту.
    • Задача минимизации булевых функций.
    • Задача минимизации булевых функций в геометрической постановке.
    • Сокращенные днф.
    • Тупиковые днф и решение задачи минимизации.
    • Графы. Основные понятия.
    • Орграфы. Основные понятия.
    • Маршруты. Цепи. Циклы. Связность.
    • Операции над графами