Лекция № 4

Тема: РЕЛЕЙНО-КОНТАКТНЫЕ СХЕМЫ

Основные вопросы, рассматриваемые на лекции:

1. Электрические схемы с двухпозиционными переключателями

2. Применение алгебры высказываний к релейно-контактным схемам

3. Применение алгебры высказываний к дизъюнктивным и конъюнктивным нормальным фопмам

Краткое содержание лекционного материала

Рассмотрим электрические схемы, в которых двухпозиционные переключатели соединяются последовательно или параллельно. По виду одной из технических реализаций такие схемы называются релейно-контактными.

Каждой релейно-контактной схеме поставим в соответствие формулу, составленную из букв и связок Ø, Ú, Ù.

Каждый переключатель обозначим некоторой буквой A. При этом считается, что A º1, если переключатель пропускает ток, и A º0, если переключатель не пропускает ток.

Переключатели, обозначенные одной и той же буквой, работают в одном и том же режиме.

Некоторые переключатели обознаются отрицанием буквы. Предполагается, что переключатель Ø A пропускает ток тогда и только тогда, когда переключатель A не пропускает ток.

Параллельному (последовательному) соединению электрических схем X и Y соответствует дизъюнкция (конъюнкция) высказываний X и Y.

Формула X, соответствующая данной схеме, истинна (ложна) тогда и только тогда, когда эта схема (не) пропускает ток.

Задача. Упростите релейно-контактную схему:

Решение. Составим формулу, соответствующую данной схеме:

(Ø A Ù C)Ú(B Ù C)Ú(A Ù B Ù C)Ú(C Ù(Ø B Ú(A ÙØ C))).

Применяя законы алгебры высказываний, полученную формулу преобразуем к более простому виду: (Ø A Ú B Ú(A Ù B))Ù C)Ú((C ÙØ B)Ú(C Ù A ÙØ C))º

º(Ø A Ú B)Ù C)Ú((C ÙØ B)Ú0)º(Ø A Ú B ÚØ B)Ù C º(Ø A Ú1)Ù C º1Ù C º C.

Ответ:

Пропозициональная переменная p или ее отрицание Ø p называется литералом от переменной p. Конъюнкция (дизъюнкция) литералов переменных p ₁, …, p_n называется конъюнктом (дизъюнктом).

Дизъюнктивной (конъюнктивной) нормальной формой от переменных p ₁, …, p_n называется дизъюнкция (конъюнкция) некоторых конъюнктов (дизъюнктов), содержащие переменные p ₁,…, p_n.

Легко увидеть из определения, что отдельные буквы, отрицания букв, дизъюнкции и конъюнкции букв и их отрицаний являются дизъюнктивными и конъюнктивными нормальными формами. Формула p Ú(q Ù r) является дизъюнктивной, но не конъюнктивной, нормальной формой. Эта формула эквивалентна формуле (p Ú q)Ù(p Ú r), являющейся конъюнктивной, но не дизъюнктивной, нормальной формой. Формула в дизъюнктивной (конъюнктивной) форме, равносильная формуле A, называется дизъюнктивной (конъюнктивной) нормальной формой формулы A.

Дизъюнктивная и конъюнктивная нормальная форме формулы A определяются неоднозначно (даже с точностью до перестановки членов и с точностью до числа одинаковых членов дизъюнкции и конъюнкции). Формулы p ÚØ q и (p Ù q)ÚØ q являются дизъюнктивными формами формулы Ø(p ÙØ q).

Задача. Приведите формулу A ºØ(p Ú(q ÙØ r)) к дизъюнктивной и конъюнктивной нормальной форме.

Решение. Применим законы де Моргана, дистрибутивности и двойного отрицания: A ºØ p ÚØ(q ÙØ r)ºØ p Ú(Ø q ÙØØ r)º(Ø p ÚØ q)Ù(Ø p Ú r).

Ответ: A ºØ p Ú(Ø q Ù r) – дизъюнктивная нормальная форма, A º(Ø p ÚØ q)Ù(Ø p Ú r) – конъюнктивная нормальная форма.