Praktika_II_Logika

4.ПОСТРОЕНИЕ ЛОГИЧЕСКОЙ ФУНКЦИИ ПО ЗАДАННОЙ ТАБЛИЦЕ ИСТИННОСТИ

Правила построения логической функции по заданной таблице истинности:

-Для каждой строки таблицы истинности с единичным (истинным) значением функции строится логическое произведение, в котором каждая переменная встречается только один раз – либо с отрицанием, либо без него. Переменные, имеющие нулевые (ложные) значения в строке, входят в конъюнкцию с отрицанием, а переменные со

единичным значением – без отрицания.

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

Примечание. Логическую функцию можно построить и в виде произведения сумм логических переменных и их отрицаний:

Для каждой строки таблицы истинности с нулевым значением функции стро- ится логическая сумма, в которой каждая переменная встречается только один раз – либо с отрицанием, либо без него. Переменные, имеющие значения 1 в строке, входят в эту сумму с отрицанием, а переменные со значением 0 – без отрицания:

Все полученные логические суммы (дизъюнкции) объединяются операциями конъюнкции, в результате получается конъюктивно-нормальная форма.

Выбор способа построения логической функции зависит от количества 0 и 1: если в ней значительно меньше 1, чем 0, то лучше строить дизъюнктивно- нормальную форму.

Пример 4.1. Требуется восстановить логическую функцию трех переменных, если F (0,0,1) = F (0,1,0) = F (1,0,1) = True , а на остальных наборах переменных значение функции равно False.

Решение:

Вначале строим таблицу истинности по заданным условиям, далее находим строки, в которых F=1. Это вторая, третья и шестая строки. Для них строим логические произведения, которые объединяем операцией логического сложения:

11

В результате получаем искомую логическую функцию:

F ( X1, X 2 , X 3 ) = X1 × X 2 × X 3 + X1 × X 2 × X 3 + X1 × X 2 × X 3

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

Задачи

1.Восстановить логическую функцию по заданной таблице истинности:

12

2. Восстановить логическую функцию по заданной таблице истинности:

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

5.ПОСТРОЕНИЕ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ ПО УСЛОВИЯМ, ЗАДАННЫМ В ВИДЕ ТЕКСТА

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

заменить логической формулой.

Пример 5.1. Заменить текст логического высказывания соответствующей логической формулой:

13

Задачи и упражнения

1.Составить логические выражения, которые являются истинными, если точка с координатами x, y принадлежит заштрихованным областям:

2.Составить логические выражения, которые являются истинными при выполнении условий:

-числа x, y, z равны между собой;

-цифра 5 входит в десятичную запись числа k;

-из чисел x, y, z только два равны между собой.

6. РЕШЕНИЕ ТЕКСТОВЫХ ЛОГИЧЕСКИХ ЗАДАЧ

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

Один из алгоритмов решения текстовой логической задачи может быть таким:

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

2.Записать условия задачи в виде логических выражений, значения которых равно 1.

3.Образовать конъюнкции полученных логических выражений и приравнять их к единице. Привести левую часть полученного уравнения к ДНФ.

4.Приравнять каждый сомножитель к ДНФ, независимо от других, единице и извлечь из уравнений значения переменных. Каждый их набор является решением задачи.

15

Пример 6.1. На вопрос, какая завтра будет погода, синоптик ответил:

1.Если будет мороз, то будет ясная погода без снега.

2.Если не будет мороза, то погода будет пасмурной.

3.Не будет снега, если небо будет ясным.

4.Будет ясная погода без снега.

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

Решение: Обозначим буквами простые высказывания:

Запишем каждое из утверждений синоптика в виде логических выражений:

1.M ® Я ×С ;

2.М ® Я ;

3.Я ® С ;

4.Я ×С.

Избавимся от операций импликации в каждом из утверждений:

1.M + Я ×С ;

2.М + Я ;

3.Я + С ;

4.Я ×С.

Поскольку каждое из утверждений синоптика верно, то объединяем их логической операцией конъюнкции, затем раскроем скобки и упростим, в результате получим ДНФ:

(M + Я ×С) ×(М + Я) ×( Я + С) × Я ×С =

= (M + Я ×С × М + Я ×С × Я) ×( Я ×С × Я ×С + Я ×С) = M × Я ×С.

Значение полученного логического выражения M × Я ×С равно истине:

16

M × Я × С = 1

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

M = 1, следовательно, «Будет мороз» Я = 1, следовательно, «Будет ясно»

C = 0, следовательно, «Не будет снега»

Таким образом, выражение синоптика можно расшифровать однозначно: «Будет мороз» и «Будет ясно» и «Не будет снега».

Ответ: Синоптик должен был сказать: «Будет морозно и ясно, а снега не будет».

Часто бывает, что текстовую задачу легче решить, составив таблицу истинности, соответствующую условиям задачи.

Пример 6.2. Преподаватель информатики выясняет, кто из трех студентов Иванов, Петров или Сидоров, выполняющих лабораторную работу на компьютере, изменил настройки и поставил пароль. Каждый из студентов сделал два заявления:

Иванов: «Это сделал не я, а Сидоров»; Петров: «Это сделал не Сидоров, а Иванов»; Сидоров: «Ни я, ни Петров этого не делали»;

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

Решение: Составим таблицу, в которой рассмотрены три версии: «Иванов изменил настройки» или «Петров изменил настройки» или «Сидоров изменил настройки». По каждой версии запишем значения высказываний каждого студента.

17

Проанализировав три версии, можно сделать вывод о том, что только версия «Сидоров изменил настройки» удовлетворяет условию задачи: Иванов дважды сказал правду, Петров дважды солгал, Сидоров один раз солгал, один раз сказал правду.

Ответ: Сидоров изменил настройки.

Задачи и упражнения

1.Алексей, Роман и Виктор увидели красивую девушку, и каждый их них сделал по два предположения:

Алексей: Эта девушка манекенщица и ей 23 года; Роман: Эта девушка студентка и ей 21 год;

Виктор: Этой девушке всего 19 лет и она не манекенщица. Девушка услышала их спор и заметила, что каждый из них прав только в одном из двух предположений. Кто эта девушка и сколько ей лет?

2.Студенты Алексей, Роман, Виктор и Игорь живут в одном доме. Когда их спросили, на каком этаже живет каждый их них, они дали три ответа:

Игорь живет на первом этаже, а Роман на втором; Виктор живет на втором этаже, а Алексей на четвертом; Игорь живет на втором этаже, а Алексей на третьем.

Оказалось, что в каждом ответе только одно утверждение верно. На каком этаже живет каждый студент?

3.Кто из студентов A, B, C , D не играет в шахматы, если известно, что:

«если A или B играет, то C не играет»; «если B не играет, то играют C и D»;

«C – играет».

4.В нарушении правил обмена валюты подозреваются четыре работника банка A, B, C, D. Кто нарушил правила, если известно, что:

«если A нарушил, то и B нарушил правила обмена валюты»; «если B нарушил, то и C нарушил или A не нарушал»; «если D не нарушил, то A нарушил, а С не нарушал»; «если D нарушил, то и A нарушил».

18

Любой, пусть даже очень сложной, логической функции или совокупности логических функций можно поставить в соответствие некоторую функциональную схему и наоборот. Построение логических схем по заданной логической функции (синтез) является задачей про-

ектирования функциональных схем. Построение логической функции по заданной логической схеме (анализ) является задачей анализа функциональных схем. Задача проектирования функциональных схем возникает, например, при проектировании отдельных узлов компьютера, если имеется лишь описание алгоритма его работы. Анализ функциональных схем дает возможность понять, как работает логическое устройство, т.е. дать ответ на вопрос: какую функцию она выполняет.

Построение логических схем по заданной логической функ-

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

1.формируется таблица истинности, которую должна будет реализовать проектируемая функциональная схема;

2.по таблице истинности составляется логическая функция, состоящая только из базовых логических операций;

3.полученная логическая функция упрощается;

4.по упрощенной логической функции строится функциональная логическая схема.

20