9957

210

B(х1, х2 ,…, xn ) ≡ B* (х1, х2 ,…, xn ) .

Из равносильностей (1) и (2) получаем:

A* (х1, х2 ,…, xn ) ≡ В* (х1, х2 ,…, xn ) , значит, А* (х1, х2 ,…, xn ) ≡ В* (х1, х2 ,…, xn ) ■

Пример 4.7. Система классификации получает на вход устройство,

данные о котором заносит в таблицу «Оборудование» для дальнейшей обработки информации. Таблица содержит поля «Устройство», «Назначение» и «Год выпуска» с символьными именами А, В и С,

соответственно. Система формирует запросы в виде переключательных

(логических) функций.

Найдем двойственные запросы к следующим запросам:

1)( А ="monitor") (С = 2016)

2)( А ="monitor") С = 2016)

3)( А ="monitor") → (С = 2016)

4)( А ="monitor") ↓ (С = 2016)

Решение: Применяя определение обратных запросов и правила де

Моргана, получим:

1)( А ="monitor") (С = 2016) = ( А ="monitor") (С = 2016)

2)( А ="monitor") (С = 2016) = ( А ="monitor") (С = 2016)

3)( А ="monitor") → (С = 2016) = ( А ="monitor") (С = 2016) =

( А ="monitor")

4)( А ="monitor") ↓ (С = 2016) = ( А ="monitor") (С = 2016) = = ( А ="monitor") С = 2016

211

Задачи.

1. Докажите равносильности:

7)x ≡ (x y z) (x y z) (x y z) (x y z) ;

8)(x y) (z t) ≡ x z y z x t y t ;

9)x y z t ≡ (x z) ( y z) (x t) ( y t) ;

10)x1 x2 ... xn → y ≡ x1 → (x2 → (... → (xn → y)...)) .

2.Докажите тождественную истинность или тождественную ложность формул:

9)(x → ( y → z)) → (x y → z) ; 10) (x y → z) → (x → ( y → z)) ;

11)(z → x) → ((z → y) → (z → x y))

12)(x → z) → (( y → z) → ((x y) → z)) .

3.Используя основные равносильности, нужно доказать или опровергнуть:

1)(х → у) → z ≡ x → ( y → z) ; 2) (х у → z) → (x → z) ≡ x y z ;

7 ) (x → y) (x → z) → (x → ( y → z)) ≡ x y z ;

8)(x y → z) → (z → x y) ≡ (z → x) (z → y) ;

9)x z → y t ≡ (x → y) (z → t) ;

212

10)х → ( у → z) ≡ (x → y) → (x → z) .

4.Пусть F – тождественно ложная формула.

Докажите, что х у → F ≡ x → y .

5.Найдите х, если x a x a ≡ b .

6.Используя основные равносильности, упростите следующие формулы:

7.Последовательность высказываний ( an ) определяется следующим рекуррентным выражением: an = an−1 (an−2 an−3 ) , n>3.

Высказывания а1 , a2 , a3 заданы, причем a1 и a3 истинны, а a2

ложно. Истинно или ложно высказывание an ? Как выражается an через а1 ,

а2 , а3 ?

8.Выразите все основные операции:

1)через операции дизъюнкцию, конъюнкцию и отрицание;

2)через конъюнкцию и отрицание;

3)через импликацию и отрицание.

9.Автоматическая прропускная система регистрирует работников предприятия на проходной и заносит данные в таблицу «Рабочее время» для дальнейшей обработки информации. Таблица содержит поля «Код сотрудника», «Отдел», «Время прихода» и «Пропуск» с

символьными именами В, В, С и D, соответственно. Система формирует запросы в виде переключательных (логических) функций.

Нужно установить соответствие между запросами к данным из таблицы и двойственными запросами.

Запросы к данным из таблицы:

213

1)((( А =1618) « (В = R22)) ® (C ¹"08 : 55")) Ù (D =1)

2)(( А =1618) Å (В = R22)) Ú ((C ¹"08 : 55") « (D =1))

3)( А ¹ 1618) Å (В ¹ R22) Å (C ="08 : 55") Å (D =1)

Двойственные запросы:

(( А ¹ 1618) « (В ¹ R22)) Ù ((C ="08 : 55") Å (D ¹ 1))

(( А =1618) Å (В = R22)) « ((C ¹"08 : 55") Å (D ¹ 1))

((( А ¹ 1618) « (В ¹ R22)) Ù (C ¹"08 : 55")) Ú (D =1)

( А =1618) « (В ¹ R22) « (C ¹"08 : 55") Å (D ¹ 1)

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

схемам (РКС).

Релейно-контактные схемы (их часто называют переключательными схемами) широко используются в технике автоматного управления.

Определение 4.5. Под переключательной схемой понимают схематическое изображение некоторого устройства, состоящее из следующих элементов:

1) переключателей, которыми могут быть механические устройства,

электромагнитные реле, полупроводники и т.д.;

2)соединяющие их проводники;

3)входы в схему и выходы из нее (клеммы, на которые подается электрическое напряжение). Они называются полюсами.

Простейшая схема содержит один переключатель Р и имеет один вход

А и один выход В. Переключателю Р поставим в соответствие высказывание

р: «Переключатель Р замкнут». Если р истинно, то импульс, поступающий на полюс А, может быть снят на полюсе В без потери напряжения, т. е. схема пропускает ток. Если p ложно, то переключатель разомкнут, и схема тока не проводит. Таким образом, если принять во внимание не смысл высказывания,

а только его значение, то можно считать, что любому высказыванию может

214

быть поставлена в соответствие переключательная схема с двумя полюсами

(двухполюсная схема).

Формулам, включающим основные логические операции, также могут быть поставлены в соответствие переключательные схемы.

Так, конъюнкции двух высказываний p q ставится в соответствие схема:

а дизъюнкции p q схема:

P

A B

Q

Так как любая формула алгебры логики может быть записана в виде ДНФ или КНФ, то ясно, что каждой формуле алгебры логики можно поставить в соответствие некоторую РКС, а каждой РКС можно поставить в соответствие некоторую формулу алгебры логики. Поэтому возможности схемы можно выявить, изучая соответствующую ей формулу, а упрощение схемы можно свести к упрощению формулы.

Пример 4.8. Составить РКС для формулы (х у) → (z x) .

Решение. Упростим данную формулу с помощью равносильных преобразований: (х у) → (z x) ≡ x y z x ≡ x y z x ≡ x y z .

Тогда РКС для данной формулы имеет вид:

215

Пример 4.9. Упростить РКС:

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

и упростим ее: (х у) z (x y) z ≡ x y z .

(к последним двум слагаемым применили закон поглощения).

Тогда упрощенная схема выглядит так:

спортивного соревнования тремя судьями при следующих условиях: судья,

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

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

Решение. Ясно, что работа нужной РКС описывается булевой функцией трех переменных F(x,y,z), где переменные высказывания x, y, z

216

СКНФ формулы (функции) F(x,y,z) запишется в виде:

F (x, y, z) ≡ x y z x y z x y z x y z .

Этой формуле соответствует РКС с двенадцатью переключателями:

Упростим формулу F (x, y, z) ≡ x y z x y z x y z x y z ≡

≡(x y z x y z) (х у z x y z) (x y z x y z) ≡

≡х у (z z) x z ( y y) y z (x x) ≡ x y x z y z ≡

≡x y z (x y) .

Полученной формуле соответствует схема, содержащая пять

переключателей.

217

2.Построить РКС для F (x, y, z), если известно, что: 1) F (0,1,0) = F (1,0,1) = F (1,1,1) = 1;

2) F (1,0,1) = F (1,1,0) = 1;

3) F (0,0,1) = F (0,1,1) = F (1,0,1) = F (1,1,1) = 1; 4) F (1,1,0) = F (1,1,1) = 1;

5) F (0,0,1) = F (1,0,1) = F (1,0,0) = 1;

6) F (0,0,1) = F (0,1,0) = F (0,1,1) = F (1,0,1) = 1,

аостальные значения функции F равны нулю.

3.Упростить РКС:

хy

y a

ху а

b

y

218

y

z a

z

4.По данной схеме найдите функцию проводимости ( СДНФ) и

условия работы:

1)