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).  


 

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

21555. Международные экономические организации 90 KB
  Необходимость регулирования мировой экономики на межгосударственном уровне Интернационализация хозяйственной жизни рост взаимозависимости между странами а также возникновение глобальных проблем объективно предопределяют необходимость активного сознательного регулирования мирового хозяйства. В период между двумя мировыми войнами не было широкого распространения межгосударственного регулирования мировой экономики. При голосовании принципиальных вопросов США могли контролировать принятие решений ибо обладали большим количеством голосов в...
21556. Международный рынок услуг 221 KB
  Международный рынок услуг. Международный рынок услуг. План: Сущность и сегменты международного рынка услуг. Особенности формирования и развития международного рынка услуг.
21558. Ценообразование в международной торговле 187.5 KB
  План: Определение мировой цены и объемов торговли Распределение выигрыша от международной торговли Сущность и основные виды мировых цен Условия торговли конъюнктура мирового рынка Международное ценообразование это формирование цен за пределами страны где находится предприятие производитель товара. Распределение выигрыша от международной торговли как внутри страны так и между странами в конечном итоге определяется тем на каком уровне устанавливаются цены на те товары которыми страны торгуют между собой и каковы объемы торговли....
21559. Система современных международных экономических отношений 218.5 KB
  Основы международной торговли. Основы международной торговли. Понятие объекты и субъекты международной торговли Международная торговля представляет собой одну из форм международных экономических отношений которая. Международная торговля это сфера товарноденежных отношений представляющая собой совокупность внешней торговли всех стран мира.
21560. Транснациональные корпорации. Свободные экономические зоны 121 KB
  План: ТНК СЭЗ Отличительные черты международных корпораций Эксперты ООН которая традиционно изучает деятельность международных корпораций долгое время относили к ним такие фирмы которые имели годовой оборот превышающий 100 млн долл. Самые большие заграничные активы среди ТНК кроме финансового сектора имеют англоголландский концерн Роял Датч Шелл а также четыре фирмы США: Форд Дженерал моторе Экссоц и ИБМ. Наиболее общей причиной возникновения ТНК является интернационализация производства и капитала на основе...
21561. Балансы международных расчетов 99 KB
  Методы государственного регулирования платежного баланса. Сальдо данного баланса отражает международную расчетную позицию страны: если сальдо активное то страна является неттокредитором и в будущем она должна получить валютные поступления; если сальдо пассивное то страна является неттодолжником и в будущем она должна будет осуществлять валютные платежи. Баланс международной задолженности широко используется в международной практике и отличается от расчетного баланса набором статей. В основе составления платежного баланса лежат...
21562. Внешнеторговая политика государства 384.5 KB
  Крайняя форма протекционизма – экономическая автаркия – означает стремление страны ограничить импорт только теми товарами которые в данной стране производится не могут а экспорт допускается в той мере в которой он обеспечивает необходимый импорт. P Sd Внутренняя цена с тарифом Pd А В С Д T Мировая цена Pw...
21563. Международная миграция капитала 271 KB
  Международная миграция капитала: сущность и формы вывоза капитала. На современном этапе развития мирового хозяйства одним из основных факторов развития МЭО считается вывоз капитала. Для возникновения только возможности экспорта капитала требовались достаточно значительные накопления его в стране.