68631

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

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

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

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

Русский

2014-09-24

28.37 KB

23 чел.

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


 

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

17246. Преднамеренные блокировки 122.5 KB
  Лекция №10 Преднамеренные блокировки Управление блокировками осуществляется из программного обеспечения и осуществляется на уровне пользовательского соединения. Блокировка указывает что пользователь имеет право на использование соответствующего ресурса. К ресур...
17247. Транзакции и восстановление данных 66 KB
  Лекция №11 Транзакции и восстановление данных В данной главе изучаются возможности восстановления данных после сбоев системы т.е. свойство Д долговечность транзакций. Главное требование долговечности данных транзакций состоит в том что данные зафиксированных
17248. Основы технологии OLAP 132.5 KB
  Лекция №12 Основы технологии OLAP Что такое хранилище данных Что такое OLAP Многомерные кубы Некоторые термины и понятия Заключение OLAP OnLine Analytical Processing технологии многомерного анализа данных. Что такое хранилище данных Устно. Информационные с...
17249. Облік доходів підприємства 31.5 KB
  Облік доходів підприємства. Дохід є надходженням економічних вигод які виникають в результаті діяльності підприємства у вигляді виручки від реалізації продукції товарів робіт послуг гонорарів відсотків дивідендів тощо. В обліку дохід відображається в момент надх
17250. Облік фінансових результатів та використання прибутку 35.5 KB
  Облік фінансових результатів та використання прибутку. Фінансові результати за видами діяльності внаслідок яких вони виникають поділяються на : прибутки збитки від звичайної діяльності операційна основна та інша діяльність інша звичайна інвестиційна та фінансо...
17251. Облік власного капіталу 35 KB
  Облік власного капіталу. Власний капітал підприємства це частина в активах підприємства яка залишається після вирахування усіх його зобов'язань. Власний капітал складається із статутного пайового додаткового резервного нерозподілених прибутків непокритих збитк...
17252. Облік резервного капіталу 26.5 KB
  Облік резервного капіталу. Резервний капітал це сума резервів створених відповідно до чинного законодавства і засновницьких документів за рахунок нерозподіленого прибутку підприємства. Він створюється з метою усунення можливих в майбутньому тимчасових фінансових ...
17253. Облік цільового фінансування і цільових надходжень 24.5 KB
  Облік цільового фінансування і цільових надходжень. До цільового фінансування і цільових надходжень належать кошти отримані у вигляді субсидій та асигнувань з бюджету та позабюджетних фондів цільових внесків фізичних та юридичних осіб гуманітарної допомоги тощо. К
17254. Поняття та принципи побудови звітності 54 KB
  Поняття та принципи побудови звітності Підсумкове узагальнення інформації та одержання підсумкових показників що характеризують діяльність підприємства здійснюється шляхом складання звітності за звітний період. Звітним періодом для складання фінансової звітності...