Дискретная математика

100 a)x=^y=z; 6)xvy; в) (xvy)<&(]zvt); т)х=у<&1х; д) (x=>y)v(]xi&z)\ e) (x=>y)&y=i>x. 36. Покажите, что: a) Ix равносильно xir, Ъ)х\/у равносильно (x Ix) l(y ty)\ в) 7x равносильно xlx\ r) x&y равносильно (xix)-l(yiy). Ъ1. Для каждой из следующих формул найдите равносильные формулы, содержащие 1) только связку/, 2) только связку к b)х=>у, б) Ix&y&lx&x-, vi)xvx&lyvlxvy&x\ Y)x&yvxvy&yvy; д) (х jy) vlx\ е) (x&y) 4(1х). 38. Сколько существует различных способов возможного заполнения последнего столбца таблицы истинности для булевой фyнкцш^ от п аргументов? Сколько существует различных булевых функций от п аргументов которые обладают следующим свойством;/(D,0,...,0j=/(1,1,...,1^? 39. Считая, что последний столбец таблицы истинности функции f(x,y,z) есть двоичное представление числа 185, найдите формулу, поронадающую эту функцию. 40. Булева функция f(x,y,z), зависящая от трех переменных, принимает значение 1 тогда и только тогда, когда все ее аргументы приняли одинаковые значения. Найдите формулу, порождающую эту функцию. 41. Если с.д.н.ф. для некоторой булевой функции от четырех переменных содержит дизъюнкцию пяти элементарных произведений, то конъюнкцию скольких элемент-арных сумм содержит с.к.н.ф. этой же функции? 42. Последний столбец таблицы истинности булевой функции имеет вид 10100100. Постройте полином Жегалкина для этой функции. 43. Булева функция, зависящая от пяти переменных, принимает значение 1 тогда и только тогда, когда каждая переменная принимает значение, отличное от значения соседней переменной. Найти формулу, порождающую эту функцию. 44. Булева функция от четырех переменных принимают значение О тогда и только тогда, когда какие-нибудь две соседние переменные, и только они, принимают значение 1. Найдите формулу для этой футсции. 45. Формула дана в одной из своих совершенных нормальных форм. Получите для нее вторую совершенную нормальную форму: а) x^i&z VX& 1у& ]z vlx&ly&zvlx& ly&lz vlx&y&z\ б) (x vy vz)&(x vlyvlz)&(lxvy vz)&(Ixvly vz)&(lx vlyvlz); в) ]x^'\<K&ly\ r) (x-^,y)&(lxyy)&(xvly). 46. Для каждой булевой функции от двух переменных найдите двойственные ей функции. 47. Каким характерным свойством обладает таблица истинности самодвойственной булевой функции?