Учебники 80131

c0 , во втором – за c1 и т.д. Значит, коэффициент c0 можно найти из первого уравнения и подставить его в остальные. Тогда c1 можно получить из второго уравнения и т.д.

В общем случае для функции n аргументов получается система треугольного вида из 2n линейных уравнений с 2n неизвестными – коэффициентами многочлена Жегалкина.

Пример 12. Найдем многочлен Жегалкина булевой функции, заданной таблицей истинности, последовательно вычисляя коэффициенты многочлена и подставляя их в остальные уравнения.

c3YZ в остальных уравнениях. Аналогично получаем: c4 0 ,

19

9. РЕЛЕЙНО-КОНТАКТНЫЕ СХЕМЫ

Рассмотрим одно из приложений логики высказываний

– применение ее к теории электрических цепей, а именно к контактным схемам.

Релейно-контактной схемой называется схематическое изображение некоторого дискретного устройства из проводников и контактов, связывающих полюса источника тока.

Пусть x1, x2 ,..., xn – набор контактов в электрической

схеме. Контакты могут быть размыкающими и замыкающими. Контакт называется размыкающим, если он размыкается при подаче напряжения на обмотку реле, к которому он подключен, а когда напряжение не подается, контакт замкнут. Контакт называется замыкающим, если он замыкается при подаче напряжения на обмотку реле, к которому он подключен, а когда напряжение не подается, контакт разомкнут. В схеме один и тот же контакт может неоднократно быть как

Основные булевы функции можно интерпретировать с помощью простейших релейно-контактных схем. Каждый контакт xi моделирует одночлен Xi , последовательное со-

единение релейных контактов – конъюнкцию Xi X j , а параллельное соединение – дизъюнкцию Xi X j .

20

меньшего числа элементов, что упрощает и удешевляет конструкцию. С математической точки зрения эта основная задача сводится к процедуре минимизации булевых функций, т.е. к такому их представлению, в котором формулы содержат минимальное число вхождений переменных.

Пример 13. Составить релейно-контактную схему для

Решение. Исключая логическую связку эквиваленции и переходя к тесным отрицаниям, получим:

Следовательно, релейно-контактная схема имеет вид:

X

X Y

Y

Z

Z

Пример 14. Упростить релейно-контактную схему:

22

X

Y

Решение. Запишем функцию проводимости и упростим

ее:

Тогда эквивалентная схема будет иметь вид:

Z

X

Y

Упражнения

1. Определить, является ли данная последовательность формулой и построить для формул таблицы истинности.

23

г) ((X1 X 2 ) X3 ) X1;

д) (X1 X2 ) (X2 X3 ) .

2. Являются ли формулы тавтологией? Выполнимыми? Опровержимыми? Тождественно-ложными?

4.Для равносильностей а) и б) из задачи 3 выписать равносильности для двойственных формул.

5.Построить таблицу истинности для формул, двойственных к данным:

6. Привести к ДНФ или КНФ формулы:

24

з) (X Z) (X Y) ;

и) (X (Y Z)) ((X Y) Z) ;

к) ((X Y) (Y X)) .

7. Найти СДНФ и СКНФ для формул:

а) (X Y) Z ;

б) X ( Y Z);

в) X (Y Z);

г) ( X Y) ( X Z).

8. Построить многочлен Жегалкина для следующих

25

8.

а) X + Y + 1;

б) XYZ + XY + 1; в) XY + 1;

г) X + Y + Z + 1;

д) XZ + YZ + Z + X + Y;

е) XYZ + YZ + XZ + YX + X + Y .

26

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1.Леденева, Т.М. Специальные главы математики. Дискретная математика / Т.М. Леденева. – Воронеж: Воронеж.

гос. техн. ун-т, 1997. – 130 с.

2.Мендельсон, Э. Введение в дискретную математику / Э. Мендельсон. – М.: Наука, 1976. – 320 с.

3.Мощенский, А.М. Лекции по математической логике / А.М. Мощенский. – Минск: Изд-во БГУ, 1973. – 160 с.

4.Нефедов, В.Н. Курс дискретной математики / Нефедов В.Н., Осипова В.А. – М.: Изд-во МАИ, 1992. – 262 с.

5.Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. – М.: Наука, 1979. – 272 с.

СОДЕРЖАНИЕ

Введение…………………………………………………………1

1. Формулы логики высказываний……………………………..1

2. Булевы функции………………………………………………6

3.Равносильные формулы……………………………………...7

4.Двойственность……………………………………………….9

5.Нормальные виды формул………………………………….11

6.Совершенные нормальные формы…………………………12

7.Многочлены Жегалкина…………………………………….15

8.Алгоритмы построения многочлена Жегалкина……….....17

9.Релейно-контактные схемы………………………………...20

Упражнения…………………………………………………….23 Ответы…………………………………………………………..26

Библиографический список…………………………………...27

27

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ для организации самостоятельной работы по дисциплине

«Математика» для студентов направления 11.03.01 «Радиотехника», профиля «Радиотехнические средства передачи, приема и обработки сигналов», специальности 11.05.01 «Радиоэлектронные системы и комплексы», специализации «Радиоэлектронные системы передачи информации», направления 11.03.03 «Конструирование и технология электронных средств», профиля «Проектирование и технология радиоэлектронных средств», направления 12.03.01 «Приборостроение», профиля «Приборостроение» очной формы обучения

Составители: Ускова Наталья Борисовна

Бондарев Алексей Владимирович Пашуева Ирина Михайловна Ряжских Александр Викторович

В авторской редакции

Подписано к изданию 03.10.2017 Уч.-изд. л. 1,6.

ФГБОУ ВО «Воронежский государственный технический университет»

394026 Воронеж, Московский просп., 14

28