Главная страница

Вечернего и заочного обучения


Скачать 0.85 Mb.
НазваниеВечернего и заочного обучения
АнкорDE2AAC829C40403EA2B1245CEFB6E2D1.doc
Дата21.07.2018
Размер0.85 Mb.
Формат файлаdoc
Имя файлаDE2AAC829C40403EA2B1245CEFB6E2D1.doc
ТипКонтрольная работа
#21800
страница7 из 8
1   2   3   4   5   6   7   8

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

Программа дисциплины


  1. Логические функции.

  2. Свойства дизъюнкции, конъюнкции и отрицания.

  3. ДНФ, СДНФ, КНФ, СКНФ.

  4. Упрощение ДНФ. Карты Карно.

  5. Полином Жегалкина.

  6. Полные системы функций, базисы.

  7. Элементы кодирования.



Теоретический материал


Теорема 1. Любую функцию можно представить в виде СДНФ.

Простые конъюнкции составляются для тех наборов (x1, …, xn), где = 1; если xi = 0, берем , если xi = 1, берем xi.

Составляя дизъюнкцию простых конъюнкций, получаем СДНФ.

Теорема 2. Любую функцию можно представить в виде СКНФ. Простые дизъюнкции составляются для тех наборов (x1,…, xn), где = 0; если xi = 1, берем , если xi = 0, берем xi.

Конъюнкция простых дизъюнкций дает СКНФ.

Теорема 3 (Поста). Для того чтобы некоторый набор функций был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классов T0, T, L, M, S:

T0 – класс функций, сохраняющих 0;

T – класс функций, сохраняющих 1;

L – класс линейных функций;

M – класс монотонных функций;

S – класс самодвойственных функций.

Классы функций


T0 : f(0,0,…,0) = 0;

T1 : f(1,1,…,1) = 1;

L : f(x1,…, xn) = a0 + a1x1 +…+ anxn;

S : f(x1,…, xn) = f*( x1,…, xn) = ;

M : f(1)  f(2) при 1 < 2 (= (x1,…, xn); = (x1,…, xn);).

Логические функции двух переменных f(x1, x2)



п/п

fj(x1,x2)

f0

f1

f2

f3

f4

f5

f6

f7

x1 x2

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

1

1

1

1

2

1

0

0

0

1

1

0

0

1

1

3

1

1

0

1

0

1

0

1

0

1

Обозначения

0

x1x2

(x1x2)

x1

(x2x1)

x2

(x1+x2)

(x1x2)




п/п


fj(x1,x2)

f8

f9

f10

f11

f12

f13

f14

f15

x1 x2

0

0

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

1

1

1

1

2

1

0

0

0

1

1

0

0

1

1

3

1

0

0

1

0

1

0

1

0

1

Обозначения

(x1x2)

(x1x2)



(x2x1)



(x1x2)

(x1x2)

1
1   2   3   4   5   6   7   8


написать администратору сайта