68631

Логические основы ЭВМ

Лабораторная работа

Информатика, кибернетика и программирование

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

Русский

2014-09-24

28.37 KB

21 чел.

Лабораторная работа №3

Логические основы ЭВМ

(2 часа)

1 Цель и содержание

Сформировать понятия: логические высказывания и операции, логические величины; сформировать навыки построения таблиц истинности. Научить студентов приводить сложное логическое выражение к нормальной форме.

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

2 Теоретическое обоснование

2.1 Основные понятия математической логики

Математическая логика (Алгебра логики, Булева алгебра) — это раздел математики, изучающий высказывания и рассуждения, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

Логическое высказывание - это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет.

Так, например, утверждение "7 — нечетное число" следует считать высказыванием, так как оно истинное. Утверждение "Рим — столица Франции" тоже высказывание, так как оно ложное.

Очень часто трудно установить истинность высказывания. Так, например, высказывание "площадь поверхности Индийского океана равна 75 млн. кв.км" в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

Например, из элементарных высказываний "Петров – врач", "Петров – шахматист" при помощи связки "и" можно получить составное высказывание "Петров – врач и шахматист".

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им дают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В — высказывание "Тимур летом отправится в горы". Тогда составное высказывание   "Тимур летом побывает и на море,  и в горах"   можно кратко записать как А и В.  Где "и" — логическая связка, А, В — логические переменные.

Логические переменные – переменные, которые принимают только два значения — "истина" или "ложь", обозначаемые, соответственно, "1" и "0". 

Каждая логическая связка рассматривается как логическая операция над логическими высказываниями и имеет свое название и обозначение.

В основе работы  современных ЭВМ лежат три основные логические операции НЕ, ИЛИ, И. Иногда эти операции называют "тремя китами машинной логики".

Операция НЕ, выражается словом "не", называется отрицанием и обозначается знаком ¬ или чертой над логической переменной.

Операция И, выражается связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается знаком & (может также обозначаться знаками или *).

Операция ИЛИ, выражается связкой "или", называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком V или +. Высказывание А V В ложно тогда и только тогда, когда оба высказывания А и В ложны.

 Используя операции НЕ и ИЛИ можно получить операцию ЕСЛИ-ТО.

Которая выражается связками   "если ..., то",  "из ... следует",  "... влечет ...",  называется импликацией (лат. implico — тесно связаны) и обозначается знаком . А→B= ¬А V В

 Используя операции НЕ, ИЛИ, И можно получить операцию РАВНОСИЛЬНО. Которая выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком или знаком ~. Высказывание AB истинно тогда и только тогда, когда значения А и В совпадают. А↔В  = =(¬А V В)& (¬B V A).    

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

2.2 Логические функции и таблицы их истинности.

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

Логической функцией являются:

– всякая логическая переменная и символы "истина"("1") и "ложь"("0");

– составные высказывания: ¬А,   А & В,   А v В,   А →B,   А ↔В

случае если А и В являются логическими функциями).

Используя вышеописанные логические функции можно образовать более сложные функции.

Значения каждой логической функции описывается таблицей истинности.

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

Для N переменных существует 2N всевозможных наборов значений переменных.

Например функция, которая содержит две переменные, имеет четыре (22 = 4) набора  значений переменных: (0, 0), (0, 1), (1, 0), (1, 1).

Если функция содержит три переменные, то возможных наборов значений  переменных   восемь (23 = 8): (0, 0, 0),   (0, 0, 1),   (0, 1, 0),    (0, 1, 1),

(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Составим таблицу истинности основных логических функций двух переменных (таблица 5.1).

Таблица 5.1 –  Таблица истинности элементарных логических функций

X

Y

X

X & Y

X V Y

X  Y

X  Y

0

0

1

0

0

1

1

0

1

1

0

1

1

0

1

0

0

0

1

0

0

1

1

0

1

1

1

1

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

Пример 5.1 Составить таблицу истинности для функции, которая содержит две переменные x и y,  ¬x&y v ¬(x v y) v x  (таблица 21.2.2).

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

Из таблицы 5.2 видно, что при всех наборах значений переменных x и y,  функция ¬x&y v ¬( x v y ) v x принимает значение 1.

Функция, которая принимает значение "истина" для всех наборов значений переменных, называется тождественно истинной функцией или тавтологией.

Функция, которая принимает значение "ложь" для всех наборов значений переменных, называется тождественно ложной функцией или противоречием.

Таблица  5.2 – Таблица истинности для функции ¬x&y v ¬(x v y) v x.

Переменные

Промежуточные логические функции

Результат

X

y

¬x

¬x&y 

x v y

¬( x v y)

¬(x v y)vx

¬x&y v ¬(x v y)v x

0

0

1

0

0

1

1

1

0

1

1

1

1

0

0

1

1

0

0

0

1

0

1

1

1

1

0

0

1

0

1

1

Функция, которая принимает для некоторых наборов значений переменных значение "истина", а для других – значение "ложь", называется выполнимой логической функцией.

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

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

2.3Основные законы математической логики

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

переместительный закон:  X V Y = Y V X,

   X & Y = Y & X;

 

– сочетательный закон: ( X V Y ) V Z = X V (  Y  V  Z ),

       ( X & Y ) & Z = X & (  Y &  Z );

– распределительный закон: ( X V Y ) & Z = ( X & Z ) V (  Y  &  Z ),

    ( X & Y ) V Z = ( X V Z ) & (  Y  V  Z );

 – законы де Моргана: ¬ ( X V Y ) = ¬  X  &  ¬ Y,

          ¬ ( X & Y ) = ¬  X  V  ¬ Y;

– закон идемпотенции:  X V X =  X,

               X & X =  X;

– закон поглощения: ( X & Y ) V X = X,

       ( X V Y ) & X = X;

– закон cклеивания: (  X & Y  ) V  ( ¬  X & Y )  =  Y,

            (  X V Y  ) &  ( ¬  X V Y )  =  Y;

– правило операции переменной с ее инверсией: ¬  X V X = 1,

¬  X & X = 0;

– правило операции с константами:    X V 0 =  X,

              X V 1 = 1,

 X & 0 =  0,

X & 1 =  X;

– закон двойного отрицания: ¬ ¬  X  =  X.

2.4 Преобразование логических функций

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

 Пример 5.2  Упростите логическую функцию ¬(x v y)&(xy).

а) Применяем закон де Моргана: ¬(x v y)&(xy)= ¬xy&(xy).

б) Применяем сочетательный закон: ¬xy&(xy) = ¬x&xyy.

в) Применяем правило операций переменной с её инверсией: 

¬x&xyy = 0&¬yy.

г) Применяем два раза правило операций с константами: 0&¬yy = 0&¬y=0.

 Пример 5.3  Упростите логическую функцию xy v ¬x&y&z v x&z).

а) Вводим вспомогательный логический сомножитель y v y):

x&¬y v ¬x&y & z v x & z = x & ¬y v ¬x & y & z v x & z & (¬y v y).

б) Применяем распределительный закон к последнему слагаемому:

x&¬y v ¬x&y&z v x&z&(¬y v y) = x&¬y v ¬x&y&z v x&y&z v x&¬y&z.

в) комбинируем два крайних и два средних логических слагаемых:

xy v ¬x&y&z v x&y&z v xy&z = (xy v xy&z) vx&y&z v x&y&z).

г) используем закон поглощения:

(xy v xy& z) vx&y&z v x&y&z)= (xy v y&z)

3 Задания

1. Какое из предложений является высказыванием:

а) Не можете ли вы передать мне соль?  

б) Некоторые лекарства опаснее самих болезней.   

в) Сегодня солнечно.

2. Составьте отрицания к данным высказываниям:

а) Все дни в августе были солнечными  

б) Не все птицы летают

в) Все растения съедобные

3. Переведите данные высказывания на язык логики.

а) Дождь неожиданно начался и быстро закончился.

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

в) Если завтра будет холодно, я не пойду гулять.

4. Построить таблицу истинности и определить является функция выполнимой, тавтологией или противоречием: (ВА)   (АВ)  (А v В).

5. Упростите выражение: (ВА)   (АВ)  (А v В).

4.Контрольные вопросы

  1.  Что такое математическая логика, высказывание? Приведите примеры.
  2.  Дайте определения логической переменной, логической операции, логическому выражению.
  3.  Назовите логические операции, их обозначение и приведите примеры.
  4.  Приведите таблицу истинности для логических операций.
  5.  Какие правила и законы логики Вы знаете?

5 Домашняя работа

1. Какие из предложений являются высказываниями? Определите их истинность или ложность:

1) Петербург – столица нашей Родины.

2) Собака – хищное животное.

3) Я поступил в университет.

4) Как твои дела?

5) Мы сегодня встретимся?

6) Летом я отдыхал на море.

2. Есть два простых высказывания:

A – «Число 10 – четное»;

B – «Волк – травоядное животное».

Составить из них все возможные составные высказывания и определите их истинность или ложность. Результаты сведите в таблицу:

A & B

A V B

¬A

¬B

 B

B

3. Постройте   таблицу    истинности    для     логического    выражения  

A & B V ¬A & ¬B.

4.  Упростите выражение: F = ¬(A & B) V ¬(B V C).  


 

А также другие работы, которые могут Вас заинтересовать

719. Проектування програмних засобів на мові Assembler та в інтерпретаторі Shell 106 KB
  Системне програмування в shell інтерпретаторі. Операційна система Windows. Системне програмування в MASM. Операційна система Linux (Ubuntu). Засоби підготування текстів.
720. Причины и условия преступности 382.5 KB
  Понятие и классификация причин и условий преступности. Сущность детерминации преступности. Основные криминологические концепции причин и условий преступности.
721. Анализ маркетинговой деятельности рекламно выставочной компании Доминанта 127 KB
  Углубление теоретических знаний по специальности Международная информация и их практическая реализация. Изучение структуры предприятия, организации и технологии производства, основных функций подразделений. Оценка социальной эффективности производственной и управленческой деятельности
722. Закон всемирного тяготения. Гравитация. Инертная и гравитационная масса 54 KB
  Согласно законам Ньютона, движение тела с ускорением возможно только под действием силы. Зависимость силы притяжения тел к Земле от расстояний между телами и от масс взаимодействующих тел.
723. Причины возникновения и суть монополии, ее суть, виды и типы 136 KB
  Определение понятия МОНОПОЛИЯ. Виды монополии и их характеристика. Факторы, способствующие возникновению монополии. Теоретическая сущность монополизма. Монополистическая конкуренция. Антимонопольное регулирование в условиях рынка.
724. Равномерное движение тела по окружности 53.5 KB
  Направление скорости при равномерном движении по окружности. Ускорение при равномерном движении тел по окружности (центростремительное ускорение).
725. Интертипные взаимодействия различных социотипов 75.5 KB
  Анализ и выработка подхода работы с приказами. Анализ каждого участника тренинга с точки зрения информационного обмена между структурами модели А. Сложные отношения со сходными жизненными установками и противоположными программами их реализации. Отношения мирного сосуществования при совпадении сильных и слабых сторон и несовпадении ценностей и интересов.
726. Определение теплопроводности твёрдого тела (пластина). 133.5 KB
  Определить коэффициент теплопроводности твёрдых тел методом сравнения с теплопроводностью эталонного материала. Физическая величина, характеризующая состояние термодинамического равновесия макроскопической системы. Коэффициент теплопроводности алюминия методом сравнения с теплопроводностью эталонного материала (латуни).
727. Системи числення 1.27 MB
  Аналіз сучасного стану розвитку систем числення. Подання чисел у формі з фіксованою та плаваючою комою. Лістинг програми на Microsoft Visual Studio 2010. Позиційною системою числення є звичайна десяткова система числення. Переведення з однієї системи числення в іншу.