- •Понятие вектора. Понятие прямого произведения множеств. Теорема о мощности прямого произведения множеств.
- •Понятие соответствия между множествами. Всюду определенное, сюръективное, функциональное, взаимно однозначное соответствие.
- •Счетное множество
- •Понятие отношения. Свойства отношений. Отношение эквивалентности, отношение строгого порядка, отношение нестрогого порядка.
- •Понятие операции, ассоциативной операции, дистрибутивной операции. Понятие алгебры, алгебраической системы, модели. Понятие группоида, полугруппы, коммутативной полугруппы.
- •Понятие композиции. Теорема о числе композиций n.
- •Понятие сильной связности. Анализ сильной связности с помощью алгоритмов поиска на графах.
- •Связность графа. Отыскание компонент связности при графическом задании графа.
- •Связность графа. Отыскание компонент связности при графическом задании графа.
- •Булева алгебра. Основные свойства операций булевой алгебры. Понятие двойственной и самодвойственной логической функции.
- •Двойственность. Принцип двойственности.
- •Разложение логической функции по переменным. Понятие совершенной дизъюнктивной нормальной формы логической функции. Понятие совершенной конъюнктивной нормальной формы логической функции.
- •Понятие полинома логической функции(полинома Жегалкина). Понятие линейной логической функции.
- •Второй этап(табличный) (получение минимальной формы)
- •Важнейшие замкнутые классы.
Второй этап(табличный) (получение минимальной формы)
Как и на первом этапе, в полученном равенстве могут содержаться члены, устранение которых никаким образом не повлияет на конечный результат. Следующий этап минимизации — удаление таких переменных. Таблица, представленная ниже, содержит значения истинности функции. По ней будет собрана следующая СДНФ.
Понятие функционально-полной системы логических функций.
Функционально полная система логических функций представляет собой набор логических функций, с помощью которых можно записать любую, сколь угодно сложную функцию. В этом случае говорят, что этот набор образует базис. Функционально полными являются 3 базиса:
1) "И-ИЛИ-НЕ" (базис конъюнкци, дизъюнкции, инверсии)
2) "И-НЕ" (базис Шеффера)
3) "ИЛИ-НЕ" (базис Пирса или функция Вебба).
Понятие замкнутого класса. Класс монотонных логических функций. Понятие замкнутого класса. Класс линейный логических функций.Понятие замкнутого класса. Класс функций сохраняющих 0. Класс функций сохраняющих 1.Понятие замкнутого класса. Класс самодвойственных функций.
Важнейшие замкнутые классы.
В теории булевых функций особую роль играют 5 замкнутых классов. Пусть имеем систему R БФ, назовем эту систему функционально замкнутым классом, если вместе с функциями системы R он содержит все булевы функции, полученные суперпозицией функций системы R (т.е. как угодно сложную функцию, полученную из функций системы R).
1) класс Т0={ f(xn)| f(0)=0} – множество функций, которые на нулевом наборе равны 0. 2) класс Т1={ f(xn)| f(1)=1}. 3) класс S (класс самодвойственных функций). S={ f(xn)| f=f*}, где f*- двойственная функция. 4) класс монотонных функций M={ f(xn)| (α1…αn) (1…n)} (если набор αi предшествует набору i ). Если функция не принадлежит к классам Т0 и Т1, то она не может быть монотонна. 5) класс линейных функций L={ f(xn)| α1x1α2x2…αnxnαn+1xn+1…=f }, где αi={0,1}.
Теорема о функциональной полноте. Теорема о функциональной полноте в слабом смысле.
Теорема о функциональной полноте: чтобы система R была полной в Р2, необходимо и достаточно, чтобы для каждого класса T0,Т1,S,M,L нашлась бы функция из система R, не принадлежащая этому классу.