Основы информатики_Савельев А.Я_Учебник_2001

2 Автомат как основной элемент информационных систем

Математики Ч. Пирс и Д. Вебб, независимо друг от друга изучавшие свойства этой функции, создали алгебру, названную алгеброй Пирса (Вебба).

Импликация — функция /,з(^{, ^2)» которая ложна тогда и только югда, когда д:, истинной Xj ложно. Условное обозначение: J\->.{x^,X2) = х^ —>• .YJ .

Все логические функции, приведенные в таблице 2.2, — элеме^ггарные функции.

Две функции равносильны друг другу, если принимают на всех воз­ можных наборах переменных одни и те же значения:

/,(:г,,д:з,...,д:„) = Уз(д:,,д:2'---'^Л- Булевы переменные могут быть действительными или фиктивными.

Переменная х, Эе«с/пбы/пельна, если значение функции /{х,,..., ж,,...,-v,,) изменяется при изменении л,. Переменная х, фиктивна, если значение

лить количество функций iV от любого числа переменных «; Л^ - 2 .

23 Основные понятия алгебры логики

Рассмотрим некоторые практические примеры использования алгебры логики.

Пример 2.2. В школе произошла неприятная история: разбито окно в одном из классов. Подозревают четырех учеников: Леню, Диму, Толю и Мишу. При опросе каждый из детей сделал по три заявления:

Леия:

1)я не виноват— Л,;

2)я не подходил к окну — Л ; ;

3)Миша uiaei. кю разбил, — Л, , Дима:

1)стекло разбил не я — Д, ;

2)с Ми!пеГ1 я не был знаком до 1юс-|ур|ления в школу — Д^; 3)')10 сделал 1оля— Д^ , Толя:

1)я не виповаг— Г, ;

2)-Jto сделал Миша — Г;:

3)Дима говорит неправду, утверждая, что я разбил окно, — T j . Миша:

i) я не впмопаг — М, :

2)сгекло разбил Леия— М;;

3)Дима может поручиться замени, так как знает меня со дня рождения,— Mj.

В дальнейшем все признали, что одно нз трех заявлений является неверным. Это приго­ дится при посгроепин более сложных формул, поскольку показания каждого ученика в це­ лом исгиниы только при условии, что два заявления истинны, а одно ложно. Используя элемеигарные логические-<|)ункции, можно описать показания всех учеников в таком виде:

Л = П^П^И^ + Л,Л2Лз + Л.Л^Л,;

д= Д1Д2Д3 + Д Д з Д ^ + Д1Д2Дз;

Т= Т|ТДз+Т|Т2Тз + Т,ТзТз;

и= MiMjM, + M,MjM3 + М,МзМ, .

lenepb ociaeicfl решить эту систему уравнений и определить, какие показания истинны. Для эюги надо упростить выражения, используя аксиомы.

Рассмотрим третье уравнение. По условию, Т, =Тз, а значит, Т, =Тз, но Т,?, = 0 ,

Т | 1 | = 1', или Г = Т|Т2. Поэтому оно верно тогда, когда Т, = 1 ; Тг = 0 . Значит, Толя не

виноват и Миша не виноват. Отсюда следует, что Д, ложно, т. е. Дз = О (Дз = 1). Следо-

вате1п,н(>, Д = J\i)\2)\% • Отсюда Д, = I; Дз = i . Дима не виноват.

Д, противоположно Mj, т. е. Дз = Мз. Значит. М^ = О или М = МрМ^Мз. Оно верно

только гогда, когда М, = I; М, = 1 • Ответ стекло разбил Леня.

2 Автомат как основной элемент информационных систем

Пример 2.3. Предположим, что имеется система кондиционирования воздуха для помешенич, где установлена ЭВМ, состоящая из двух кондиционеров малой и большой моипюсчи и работающая при таких условиях: кондиционер малой мошности аключаося. если icMiieparypa воздуха в помещении достигает 19° С ; конди[[ионср большой мошносги включается, ecjrn температура воздуха достигает 22° С (малый кондиционер при этом от- К]ночас1СЯ), оба кондиционера включаются при температуре воздуха 30° С

ilycib информация о температуре воздуха поступает ог датчиков, когорыс сраба­ тывают ори достижении темпера г уры соответственно 19, 22, 30° С , Каждый из них датчиков выдает входную ин(|)ормаии10 для устройства управления коидиииопсрамч Первые три датчика определяют рабочие режимы, и их можно Г1релстави1ь как входы управляющею автомата. Используя двоичный алфавит для задания состояний да пика (О — нет сигнала о достижении заданного уровня тем11ерат>ры, 1 — ectb сигнал), (|(ункниопиронамис системы управления кондиционерами можно описать следующим oGpajoM

коилициоиер выключен, w= I —-кондиционер включен).

!<1блииа описр>1вает функционирование системы управле1шя без нарушений работы.

Впервые теория Дж. Ьуля была применена П. С. Эренфесюм к ппшииу контактных цепей (1910 г.). Возможность описания переключательных схем с помощью логических формул оказалась весьма ценной гю двум при­ чинам. Во-первых, с помощью формул удобнее проверять работу схем. Вовторых, задание условий работы любой переключательной схемы в виде формул упрощает процесс построения самой переключательной схемы, так как оказалось, что существует ряд эквивалентных преобразований, в ре­ зультате которых логические формулы упрощаются. При описании irepeключательных схем замкнутое состояние контакта принимается за истин­ ное высказывание, а разомкнутое — за ложное, поэтому последовагельиое соединение контактов можно рассматривать как функцию И, а параллель­ ное — как функцию ИЛИ.

2- Автомат как основной элемент информационных систем

функции и, и л и , НЕ через импликацию вь!ражаются так;

Эти аксиомы позволяют сформулировать следующие прайила преобразования:

Для функции Шеффера справедливо свойство коммутативности для двух переменных xjx2 ^Xjjx^ , что легко проверяется. Для трех и более

как непонятно, в какой очередности применять операцию Шеффера в этом

2.4. Свойства элементарных функций алгебры логики

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

((xjx^)lx,)lx^ или (X|/Xj)/(X3/*4)-

Э1И выводы подтверждаются также тем, что свойства ассоциативности и дистрибутивности для функции Шеффера несправедливы. В самом деле, справедливость свойства ассоциативности ведет к тому, что должны быть

Проверка равнозначности этих выражений представлена в таблице 2.7.

Следовательно, функции (х,/х2)/х, и xJ(x2Xi) не равны, значит, функция Шеффера не обладает свойством ассоциативности в случае трех переменных, что можно распространить и на «и» переменных.

/1ля функции Шеффера свойство дистрибутивиости означает, что