Лабораторная работа 3. Логические основы алгоритмизации

 1.    Цель работы

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

2.    Теоретический материал

Конъюнкция – соединение двух (или нескольких) высказываний в одно с помощью союза И (AND) называется конъюнкцией (или операцией  логического умножения). Обозначаются Λ, &,х.  Значения логических операций определяются по правилам, задаваемым в таблице истинности.

Дизъюнкция – соединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ (OR) называется дизъюнкцией (или логического сложения). Обозначаются ||, V, +.  

Отрицание (инверсия) – присоединение частицы НЕ (NOT) к данному высказыванию называется операцией отрицания (инверсии). Ā, ¬ А – «не А»

Приоритеты:

1.     Отрицание.

2.     Конъюнкция (логическое И) – логическое умножение.

A && B, A & B, A · B, A Λ B, A AND B.

3.     Дизъюнкция (логическое или) – логическое сложение.

A || B, A | B, A V B, A + B, A OR B.

Свойства логических операций:

1.     коммутативность

А& В = В & А

А V В = В V А 

2.     закон идемпотентности

А & А= А,  А V А= А

3.     ассоциативные законы

АV (В V С)= (АV В) V С= А V  В V  С

А & (В& С)= (А& В) & С= А&В&С

4.     дистрибутивные законы

А &  (В V С)= (А& В) V (А& С)

А V (В& С)= (А V В) & (А V С)

5.     законы де Моргана

¬ (А&В)=  ¬ А V ¬ В

¬  (А V В)= ¬ А & ¬ В

6.     закон универсального множества

Х V 1= 1

Х & 1= Х

7.     закон нулевого множества

Х V О  = Х

Х &  О  = О

8.     поглощения

X v (XY) = X

X (XVY) = X

9.     склеивания

(XY) v (¬XY)=Y

(XvY) (¬XvY)=Y

10.   операция переменной с инверсией

Xv¬X=1

X¬X=0

11.   двойное отрицание

¬(¬X)=X

Логические схемы

Логические элементы (ЛЭ) – это электронные схемы с одним или несколькими входами и одним выходом, через которые проходят электрические сигналы, представляющие 0,1.

 Для реализации любой логической операции над двоичными сигналами достаточно элементов трех типов: И, ИЛИ, НЕ – функционально полная система, все остальные можно построить через них.

Задачи анализа и синтеза

Задачи, возникающие при рассмотрении переключательных схем, подразделяются на задачи анализа и задачи синтеза схем.

Этапы синтеза переключательной схемы:

1.     Составление функции проводимости по заданным условиям.

2.     Упрощение этой функции.

3.     Построение соответствующей схемы.

Этапы анализа схемы:

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

2.     Получение упрощенной формулы.

Совершенной дизъюнктивной нормальной формой (СДНФ) называют наиболее полную форму записи логического выражения. Эта форма записи представляет собой сумму, каждое слагаемое которой является произведением всех входных аргументов или их инверсий, например:

F = ¬A¬В¬С + ¬А В¬С + А В¬С + А В С.

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

Еще одной формой записи логического выражения является совершенная конъюнктивная нормальная форма (СКНФ). Это произведение сомножителей, каждый из которых является суммой всех входных аргументов или их отрицаний, например:

F = (¬А + В +¬С ) (¬А + В + С ) ( А +¬В + С ) ( А + В + С ).

В качестве примера логического синтеза вычислительных схем рассмотрим построение одноразрядного двоичного  сумматора, имеющего два входа (х₁  и х₂) и два выхода (S и P).            

Его назначение состоит в нахождении суммы двух двоичных чисел. Этот узел интересен для тем, что он лежит в основе арифметического устройства ЭВМ и иллюстрирует некоторые принципы выполнения вычислительных операций в компьютере. Для простоты изучим онаиболее важное звено сумматора – полусумматор. Полусумматор реализует сложение 2-х одноразрядных двоичных чисел x₁ и x₂. В результате получается 2-х разрядное двоичное число. Его младшую цифру обозначим S, а старшую, которая при сложении многорязрядных чисел будет перенесена в старший разряд, через P.

Зададим таблицу истинности сумматора.

Представим выходные функции S и P в виде СДНФ:

S=f1(x1,x2) = ¬ x1 х  x2 + x1 х ¬x2 = х1 хоr x2

P=f2(x1, x2) = x1 х  x2

Ниже приведены два варианта логической схемы полусумматора: с использованием лишь базовых логических элементов и с использованием логического элемента «исключающее ИЛИ». Видно, что вторая схема существенно проще.

Логическая схема полусумматора

Переключательные схемы

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

Найдем функции проводимости F некоторых переключательных схем:

a)  

Схема не содержит переключателей и проводит ток всегда, следовательно F=1;
 

б)  

Схема содержит один постоянно разомкнутый контакт, следовательно F=0;
 

в)  

Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, F(x) = x;
 

г)  

Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(x) = ;
 

д)  

Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(x) = x ^. y;
 

е)

Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(x)=x v y;
 

ж)  

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

 

Решение логических задач табличным способом

Пример 1. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. Известно, что:

1.     Смит самый высокий;

2.     играющий на скрипке меньше ростом играющего на флейте;

3.     играющие на скрипке и флейте и Браун любят пиццу;

4.     когда между альтистом и трубачом возникает ссора, Смит мирит их;

5.     Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

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

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов "альт" и "кларнет" заполним нулями:

Из таблицы видно, что на трубе может играть только Вессон.

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки "Вессон" можно заполнить нулями:

Из таблицы видно, что играть на флейте и на гобое может только Смит.

Ответ: Браун играет на альте и кларнете, Смит — на флейте и гобое, Вессон — на скрипке и трубе.

Пример 2. Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби.

Юра сказал, что на туризм ему не хватает времени, хотя его сестра — единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги.

Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.

Определите, кто чем любит заниматься в свободное время и у кого какая профессия.

Решение. Здесь исходные данные разбиваются на тройки (имя — профессия — увлечение).

Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист.

Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач — Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени — Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем:

Ответ. Влад — юрист и регбист, Тимур — врач и турист, Юра — физик и бегун.

3.    Порядок выполнения работы

1.     Изучить предлагаемый теоретический материал.

2.      Выполнить следующие задания:                                   

1.     Пусть a = "это утро ясное", а b = "это утро теплое". Выразите следующие формулы на обычном языке:

2.     Из трех данных высказываний a, b, c постройте составное высказывание, которое истинно, когда истинно какое-либо одно из данных высказываний, и только в этом случае.

3.     Составить таблицу истинности для  формул:

a.      XYv¬(XvY)vX.

b.     ¬(XvY)(X¬Y)

c.      ¬(X¬Y)v¬XZ

4.     Определите с помощью таблиц истинности, какие из следующих формул являются тождественно истинными или тождественно ложными:

a.     (¬aa) v b (abvb)

b.     ¬(ab) ↔ (¬a v ¬b)

c.      a (b (¬a v ¬b)))

5.     Упростите формулы, используя законы склеивания:

a.     abc v ¬abc

b.     (a v b v c) (a v ¬b v c)

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

a.     a v a b v abc v adf

b.     a (a v b) (a v c)

7.     Постройте таблицу истинности для логической формулы и упростите формулу, используя законы алгебры логики ¬(a (b v ¬c) v ¬ab)

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

a.     F=AvB&¬C, если А=1, В=1, С=1.

b.     F= ¬(AvB&C),если А=0, В=1, С=1.

9.     Построим схему, содержащую 4 переключателя x, y, z и t, такую, чтобы она проводила ток тогда и только тогда, когда замкнут контакт переключателя t и какой-нибудь из остальных трёх контактов.

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

11.     Найдите функцию проводимости схемы:

12.     Упростите переключательные схемы:

4.    Содержание отчета

В отчете следует указать:

-   Цель работы

-   Введение

-   Программно-аппаратные средства, используемые при выполнении работы.

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

-   Заключение (выводы).

-   Список используемой литературы.

5.    Литература

1.     Могилев А.В., Пак Н.И., Хенкер Е.К. Информатика. Учебное пособие. – М.: Академия, 2004, 3-е издание.

2.     Могилев А.В., Пак Н.И., Хенкер Е.К. Практикум по информатике. - М.: Академия, 2005, 2-е изд. 

3.     Шауцукова Л.З. Информатика http://book.kbsu.ru, 2002.

4.     Сырецкий Г.А. Информатика. Фундаментальный курс. В 2 томах. – БХВ-Петербург, 2007.

5.     Каймин В.А. Информатика. – М.: Инфра-М. 2001, 2-е изд., доп. и перераб.

6.     Острейковский В.А., Полякова И.В. Информатика. Теория и практика. –  М.: Оникс, 2008.

7.     Степанов А.Н. Информатика. Учебник для вузов. – СПб.: Питер, 2006, 4-е изд.

8.     Рыжиков Ю.И. Информатика. Лекции и практикум. – СПб.: Корона принт. 2000.

9.     Андреева Е., Фалина И. Информатика. Системы счисления и компьютерная арифметика. – М.: Лаборатория Базовых Знаний. 1999.

10.  Шауцукова Л.З. Информатика http://book.kbsu.ru, 2002.

11.  Казиев В.М. Введение в информатику http://www.intuit.ru/department/informatics/intinfo, 2006.

12.  Казиев В.М. Введение в информатику. Практикум http://www.intuit.ru/department/informatics/intinfopr, 2008.

13.  Роганое Е.А. Практическая информатика http://www.intuit.ru/department/se/pinform, 2006

14.  Непейвода Н.Н. Стили и методы программирования http://www.intuit.ru/department/se/progstyles, 2005