24. Реализация б.Ф. Любая б.Ф отличная от тождевственного 0(тожд.1) представима однозначно в виде сднф(скнф)

Алгоритм СДНФ: а) Задать таблицу. б) Выделить в таблице те строки знач.кот=1,

в) Для кажд.из выдел строк,выписать конституенты 1 г) Для кажд констит 1 составить элементар.конъюнкию если 1-сама по себе, 0-своим отрицанием. К альфа=()

25) тоже, только нули подчеркиваем, 0-сама по себе, 1-отрицанием.

26) Свойства Суммы по модулю 2: а) Коммутативна х+у=у+х б) ассоциативна (х+у)+z=х+(у+z)

в) Конъюнкция дистрибутивна относит. Сумм по мод 2 X(y+z)=XY+XZ

г) Х+Х=0 д) Х+0=Х е)Х+1=отриц.Х д)Х+отрХ=1 ж)х+у+ху=х v у

27) Многочлен Жегалкина! Многочлен жегалкина представляет собой композицию трехбулев.функций(конъюн,+,тожд1)!

Теорема:Любая Б.Ф представима причем однозначно многочленом Жегалкина(через конъюн,+,тожд1)

28) Функционлано замкнутые классы: Функционально замкнутым классом Б.Ф назыв.класс(подмножества)Б.Ф, таких что композиция любого числа Б.Ф из данного класса-этому-же классу и принадлежит.

Классы: Т0-сохраняющей константу 0 (тождевст.0,дизъюнкция); Т1-сохран.константу 1(тожд.1, конъюнкция); L-класс линейных Б.Ф(имплицакия)

S-класс самодвойственной Б.Ф. М-класс монотонных Б.Ф.

29) Б,Ф n-переменных называется сохран.константу 0,если на нулевом наборе знач переменных Б.Ф принимает значения=0. F(x,y)=X v Y: F(00)=0 v 0=0, FэT0

Если Б.Ф задана булевым вектором и первая координата вект=0, то б.ф сохран.конст0 в противном случае перв.координата=1, не сохран.конст0.

30) Б,Ф n-переменных называется сохраняющей конст.1 если на единичном знач наборе знач.переменных б.ф будет принимать значения=1. F(X*Y)=X*Y: F(11)=1*1=1 значит FэT1

31) Б,Ф n-переменных называется линейной, если она представима многочленом Жегалкина, степени не выше первой(0 или1) (х+у).

32) Монотонной б.Ф n-переменных назыв.б.ф для кот, для каждых двух сравнимых между собой ее аргументов из того, что первый арг.предш.второму, значение б.ф на первом арг.предшест.знач.б.ф на второй. (0*0)<(0*1) (0*0)<(1*0) (1*1)не меньше!(00)

32)Б.Ф –переменных называются двойственными,если на противоположных значениях,они принимают противополож.Значения.

Б.Ф n-переменных назыв.самодвойственной если она двойственна сама себе.

34)Система Б.Ф называется функционально полной если любую б.ф можно представить в виде композиции определенного набора б.ф этой системы.(СНФ) {*, V,-}, {+,*,1}

35) Теорема ПОСТА: Для того чтобы система б.ф была функционально полной необходимо и достаточно чтобы для каждого из классов Поста в сисеме нашлась функция не принадлежащая ему. (используем таблицу ПОСТА). Число столбцов=5,число строк-количество б.ф!

Система б.ф будет ФП когда в каждом столбце критериальной таблицы ПОСТА найдется хотябы один минус.

40) Два целых числа а и в назыв.сравнимыми по натуральному модулю m, если их разность нацело делится на m. а=d(modm)

Два целых числа а и в сравнимы по натур.модулю m, когда а представимо: а=в+mq, где q-некот.целое число.

1 группа свойст сравнения: Любое число сравнимо с собой по натуральному модулю m.

Если превое целое число сравнимо по натуральному модулю m то и второе целое число сравнимо с первым по натуральному модулю m. доказательство: а=d(modm) a=b+mq b=a-mq b=a+mq1, b=a

Два целых числа сравнимые с третим по натуральному модулю m-сравнимы между собой.

41) R4={(a,b)| (a,b) э Z(в квадрате), а=b(mod4)} (16,4)эR4:16=4(mod4): 16-4=12, 12:4(верно)

42) Функция Эйлера называется функция определ-я на множестве N и сопоставляющая каждому натуральному числу количество натуральных чисел меньших его и взаимно простых с ним.

Свойства: а) ℓ(P)=p-1 ℓ(5)=5-1=4 б) ℓ(8)= ℓ( )= *(1- =

в) Мультипликативна: ℓ(m*n)= ℓ(m)* ℓ(n), где (m,n)=1. ℓ(21)= ℓ(3*7)= ℓ(3)* ℓ(7)=(3-1)*(7-1)=2*6=12

43)Класс эквивалентности множества целых чисел по Б/О эквивалентности а именно-сравнимости по натуральному модулю m называется вычетом по натур. модулю m.

Операции: а) При сложении вычитов нужно взять представитель первого и второго вычетов, их сложить и определить к какому вычету явля-я сумма. Тоже самое и для вычитания и умножения.

44) Вычет называется обратимым,если для него во множестве вычетов найдется обратный вычет,такой, что их произведение дает вычет 1. (3*3=1.)

Нулевой вычет из множества вычетов по натуральному модулю m называется делитель нуля, если в этом множестве вычетов для него найдется,такой ненулевой вычет, что их произведение будет=вычету 0. (2*2=0) .