Вариант ср

Данную функцию f(x,y,z)=(00010101)

1. Представить всеми способами.

2. Представить в виде СДНФ и СКНФ.

3. Представить в виде полинома Жегалкина двумя способами.

4. Найти существенные и фиктивные переменные двумя способами.

5. Разложить по переменным x и z.

6. Выяснить, является ли данная функция шефферовой. Если нет, то какую одну функцию надо добавить к ней, чтобы получить полную систему. Единственным ли образом это можно сделать?

Подготовка к контрольным работам: КР-IДМ (контрольная работа за 1 семестр курса ДМ), КР-IIДМ (контрольная работа за 2 семестр курса ДМ). Типовые варианты этих контрольных работ приводятся ниже.

КР-IДМ

Вариант 1

1. Найти число функций из L(n)T₀(n)S(n).

2. Выразима ли xy через x  ?

3. Найти все полные подсистемы в Р₂ заданной системы

{xyz1, (x→y)z, xy, x, xxyxz}.

4. Построить СДНФ, СКНФ для f(x₁,x₂,x₃)=((x₁→x₂)x₃)x₂→x₁.

5. Найти полином Жегалкина для функции

f(x,y,z)=(((x↑y) →z)↑y)+y.

6. Разложить функцию

f(x₁,x₂,x₃,x₄) =((x₁↑x₂)↓((x₁↓x₄)↑(x₃↓x₄)))↑((x₂↑x₃)↑x₁)

по переменным x₁ и x₃, определить табличное значение разложенной функции.

6. Проверить, что xy  [{xy → (xz→yz), }].

Вариант 2

1. Проверить эквивалентность ((x→y) →z)=(xy)(z+x).

2. Выделить все полные в Р₂ подсистемы данной системы

{(xy)(  ),x+y+z+x(y+z)+yz,xyz, x↓z}.

3. Построить СДНФ, СКНФ для f(x₁,x₂,x₃)=(1+x₁x₂+x₂x₃+x₃x₁)↑x₃.

4. Найти полином Жегалкина для функции f(x,y,z)=((x→y)↑z) → (y+z).

5. Проверить справедливость соотношения О [{x+xy+xz, ,1}].

6. Найти число функций, существенно зависящих от трех переменных.

7. Какие переменные у функции f(x₁,x₂,x₃,x₄)=(0101010101010110)

являются существенными?

Вариант 3

1. Выделить все полные в Р₂ подсистемы данной системы

{x(x+y)z,x+y+z,x(yz)x(  ) ,x↑y}.

2. Построить СДНФ, СКНФ для функции f(x,y,z)=((x→y)(y→z)(z→x))↓z.

3. Построить полином Жегалкина для функции f(x₁,x₂,x₃,x₄):

f(а₁,а₂,а₃,а₄)=1  а₁=а₂=а₃=а₄.

4. Проверить x(yz) yz  ML?

5. Найти число функций из L(n)T₁(n)S(n).

6. Решить систему

.

7. Какие переменные у функции f(x₁,x₂,x₃,x₄) = (1010101010101001) являются существенными?

Вариант 4

1. Построить СДНФ, СКНФ для функции f(x₁,x₂,x₃)=((x₁→x₂)+x₃)(x₂→x₁).

2. Построить полином Жегалкина для функции f(x,y,z)=( →(zy))+ .

3. Верно ли, что L  (T₀T₁S)? Доказать.

4. Решить систему:

.

5. Найти все полные в Р₂ подсистемы данной системы {(x→y)z,xy,x+xy+yz}.

6. Какие переменные у функции f(x₁,x₂,x₃,x₄) = (0011001100110100) являются существенными?

7. Проверить, что xz[ {xyxzyz, } ].

КР-IIДМ

Вариант 1

1. Показать, что ├ АВ→ВА.

2. Найти примитивно-рекурсивную функцию (п.р.ф.) (если она ), из которой однократным применением  можно получить частично рекурсивную функцию (ч.р.ф.) f(x)=2-x.

3. Найти вес о.-д.ф.

y (t)= (t)q₁(t-1)x(t) ₂(t-1)

q₁(t)= x(t) ₁(t-1) (t) ₂(t-1)

q₂(t)= (t) ₁(t-1) ₂(t-1))

q₁(0)=1, q₂(0)=0

4. Является ли код С однозначно декодируемым, где С={01,011,100,2100,101210,001210}. Найти неприводимое слово.

5. Применяя Пр к g(x) и h(x,y,z) по y, построить f(x,y)=R(g,h), записав её в аналитической форме, где g(x)=x, h(x,y,z)=x+z.