Тема 1.2. Отношения и функции

Тема 1.1. Множества и основные операции над ними

Планы практических (семинарских) занятий

Практические (семинарские) занятия

Задача отыскания частных минимальных форм при минимизации булевых функций.

Предположим что задана в виде конъюнкции дизъюнкций некоторая булева функция f = (a11, V a12 … V a1i..n)… (Am1vam2v…vamim), где ai,j принадлежит A = {a11,…an} (I =1,..m), (j = 1,…li)

UAij=Ai,j = 1…li, UAi = A, i=1..,m \

Тестом А* называется подмножество элементов из А, такое что в каждой скобке существует по крайней мере 1 элемент, принадлежащий А*. Минимальным тестом называется подмножество A*min содержащее минимальное число элементов из А. Булева функция f определена на всех 2 ^n наборов логических переменных а1 … аn и принимает значение 1 на всех наборах из А являющихся тестом для f(). Здесь предполагается, что в выражении для f произведены все упрощения с помощью аксиом алгебры логики. Задача нахождения минимальных тестов может быть сформулирована как задача нахождения простых импликант минимальной длины. Записав инверсию для функции f(), получим ДНФ этой функции и если учесть что все упрощения функции f были осуществлены, то это может быть минимальная ДНФ. !f= !a11 * !a12… !a1l1 v…V!am1* !am2 … !amlm

Импликантами функции f являются все возможные выборки A* элементов из А такие что А* && Ai != A*, где Ai’ = {ai1’ , aip’}, Ai’ = A|Ai,

Ai = {ai1,..aili}(I = 1,..m) следовательно минимальной простой импликантой (минимальным тестом) является выборка содержащая наименьшее число элементов из А и не входящее полностью не в одно из подмножеств Ai’ при I = 1 to n Если среди подмножеств Аi со штрихом содержит подмножество Aj’ при j принадлежит (1..m), Pj = min Pi (так как f!=0, то Pj < n)

То для функции f () существует по крайней мере n-pj тестов содержащих не более pj+1 членов. Таким образом, процесс нахождения минимальных простых импликант (минимальных тестов) следует начинать с рассмотрения выборок по Pj элементов.

Раздел 1. Введение в теорию множеств и отношений

Практическое (семинарское) занятие № 1:

Задание множеств и их основные свойства.

1. Рассмотреть способы задания множеств и основные операции над ними.

2. Научиться устанавливать тождества в алгебре множеств.

Вопросы самоконтроля:

а) Как задать конечное множество?

б) Каковы способы задания бесконечного множества?

Практическое (семинарское) занятие № 2:

Задание и свойства отношений и функций. Метод математической индукции.

1. Рассмотреть способы задания и основные типы отношений и функций.

2. Изучить метод математической индукции.

Вопросы самоконтроля:

а) Чем отличается отношение от функции?

б) Что такое инъективное отображение?

в) Что такое сюръективное отображение?

г) Что такое биективное отображение?