68631

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

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

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

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

Русский

2014-09-24

28.37 KB

20 чел.

Лабораторная работа №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).  


 

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

63822. Показатели работы женской консультации и роддома 24 KB
  Деятельность женской консультации оценивается по следующим показателям: своевременность обращения беременных до 12 недель отношение числа женщин поступивших под наблюдение в сроки до 12 недель к общему числу беременных умноженное на 100...
63824. Медицинская документация и показатели, характеризующие деятельность поликлиники и стационара детской городской больницы 22.5 KB
  Деятельность детской поликлиники оценивается по данным отчета-вкладыша €œО медицинской помощи детям первичной медицинской документации: показатели организации патронажа дородового отношение числа детей матери...
63825. Организация санитарно-эпидемиологической службы в России 47.5 KB
  Эрисман создал первую санитарную станцию в Москве в 1891г. Первым санитарным врачом был Мадисон. После ВОВ создана единая комплексная СЭСл до этого санитарная эпидемическая.
63827. Трудоспособность, понятие. Временная нетрудоспособность 25 KB
  Виды нетрудоспособности: временная стойкая длительная инвалидность. При полной временной нетрудоспособности любая работа полностью противопоказана и больной нуждается в создании определённых условий.
63830. Выдача листка нетрудоспособности по беременности и родам, по уходу за больным членом семьи 23 KB
  Срок беременности 30 недель дородовый 70 дней до и 70 дней после. Если роды осложнённые то ещё 16 дней. Если беременность многоплодная то отпуск начинается с 28 недель дородовый 7014 послеродовый 96 дней всего 180 дней.