Определение релейно-контактной схемы (РКС). Привести пример

Релейно-контактной схемой или РКС будем называть некоторое соединение, состоящее из следующих элементов:

- переключателей (это могут быть как механические устройства, так и лампы, электромагнитные реле и т. д.) Каждый переключатель может принимать значение 1 (через него пройдет ток) или 0 (через него ток не проходит). Будем считать, что любой переключатель соответствует либо логической переменной x, либо ;

- проводников, могущих соединять переключатели либо последовательно, либо параллельно (это соответствует замене ФЭ, определяющих конъюнкцию или дизъюнкцию);

- входа и выхода из системы (вход и выход называются полюсами системы).

Иначе РКС называют переключательной схемой (П-схемой).

Будем говорить, что конкретная РКС принимает значение 1 при данных значениях переключателей, если через нее проходит ток, в противном случае мы считаем, что она принимает значение 0.

Две РКС считаются равносильными,если они принимают одинаковые значения при одних и тех же значениях переключателей.

Очевидно, что любая суперпозиция функций конъюнкции, дизъюнкции и отрицания может быть изображена в виде РКС. Например, функции соответствует следующая РКС.

Следующая РКС соответствует функции (в ней 12 переключателей).

После сокращения СДНФ по правилу Блейка можно получить равносильную формулу: L = xz yz  xz , для которой РКС будет иметь 6 переключателей. Если ставить целью уменьшение числа переключателей, то последнее выражение можно преобразовать к виду L = (x y) z xy (РКС будет иметь 5 переключателей).

«Дискретный анализ»

1. Понятие множества, элементов множества, подмножество, универсальное множество, пустое множество.

2. Операции над множествами и их семействами: объединение, пересечение, дополнение, разность.

3. Понятие графа. Полный граф. Вершина, степень вершины.

4. Теорема о сумме степеней вершин графа. Теорема о числе нечетных вершин графа.

5. Цикл. Путь. Длина пути. Связность графа. Мост. Деревья, лес.

6. Плоский граф. Формула Эйлера о числе ребер и числе граней для плоского представления плоского связного графа.

7. Эйлеровы графы и Эйлеровы пути.

8. Лабиринты. Циклы.

9. Гамильтоновы графы, гамильтоновы пути и циклы.

10. Понятие алгебры логики, булевой алгебры. История создания алгебры логики.

11. Понятие высказывания. Операции над высказываниями (дизъюнкция, конъюнкция, отрицание).

12. Унарные операции, бинарные операции, n-арные операции.

13. Понятие набора. Понятие «значения функции на данном наборе».

14. Методика построения таблиц истинности логических функций.

15. Понятие дизъюнктивной нормальной формы (ДНФ).

16. Понятие конъюнктивной нормальной формы (КНФ).

17. Понятие совершенной дизъюнктивной нормальной формы (СДНФ).

18. Понятие совершенной конъюнктивной нормальной формы (СКНФ).

19. Правила приведения произвольной формы алгебры логики к СДНФ и СКНФ.

20. Методика построения СДНФ по таблице истинности логической функции.

21. Методика построения СКНФ по таблице истинности логической функции.

22. Определение полинома (многочлена) Жегалкина.

23. Эквивалентности перевода дизъюнктивных и конъюнктивных форм в полином Жегалкина.

24. Правила перевода дизъюнктивных и конъюнктивных форм в полином Жегалкина.

25. Метод неопределенных коэффициентов нахождения коэффициентов многочлена Жегалкина.

26. Суперпозиция функций. Замыкание набора функций. Замкнутые классы функций.

27. Понятие полного набора функций. Понятие базиса.

28. Пять основных классов функций.

29. Определение самодвойственной функции. Носитель функции. Мощность носителя. Лемма о мощности носителя.

30. Теорема Поста. Таблица Поста. Следствие из теоремы Поста о числе базисных функций в наборе.

31. Актуальность минимизации логических функций.

32. Минимизация СДНФ методом карт Карно.

33. Понятие функционального элемента. Определение схемы. Необходимое и достаточное условие существования схемы.

34. Определение релейно-контактной схемы (РКС). Привести пример.