Примеры. Число: -1

Код модуля числа: 0 0000001.

Обратный код числа: 1 1111110.

Число: -127.

Код модуля числа: 0 1111111.

Обратный код числа: 1 0000000.

3.Дополнительный код получается образованием обратного кода с последующим прибавлением единицы к его младшему разряду.

Примеры. Дополнительный код числа –1:

Дополнительный код числа -127:

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

Как компьютер выполняет арифметические действия над целыми числами.

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

При сложении обратных кодов чисел А и В имеют место четыре основных и два особых случая. Рассмотрим их.

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

Десятичная запись: Двоичные коды:

3 0 0000011

7 0 0000111

10 0 0001010

Получен правильный результат.

Случай 2. А положительное, В отрицательное и по абсолютной величине больше, чем А. Приведем пример.

Десятичная запись: Двоичные коды:

Обратный код числа -10

Обратный код числа -7

Получен правильный результат в обратном коде. При переводе в прямой код биты цифровой части результата инвертируется: 1 0000111 = -7 .

Случай 3. А положительное, В отрицательное и по абсолютной величине меньше, чем А. Приведем пример.

Десятичная запись: Двоичные коды:

Обратный код числа - 3

Компьютер исправляет полученный первоначально не правильный результат (6 вместо 7) переносом единицы из знакового разряда в младший разряд суммы.

Случай 4. А и В отрицательные. Приведем пример.

Обратный код числа - 3

Десятичная запись: Двоичные коды:

Обратный код числа - 10

Обратный код числа - 7

Полученный первоначально неправильный результат (обратный код числа -11 вместо обратного кода числа -10 ) компьютер исправляет переносом единицы из знакового разряда в младший разряд суммы. При переводе результате в прямой код биты цифровой части инвертируется: 1 0001010 = -10 .

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

Случай 5. А и В положительные, сумма А и В больше либо равна 2 , где n – количество разрядов формата чисел (для однобайтного формата n=8,

2 =2 =128). Приведем пример.

Десятичная запись: Двоичные коды:

_{Переполнение}

Семи разрядов цифровой части числового формата недостаточно для разрешения восьмизначной суммы (162 =10100010 ), поэтому старший разряд суммы оказывается в знаковом разряде. Это вызывает несовпадение знака и знаков слагаемых, что является свидетельством переполнения разрядной сетки.

Случай 6. А и В отрицательные, сумма абсолютных величин А и В больше либо 2 . Приведем пример.

Десятичная запись: Двоичные коды:

Переполнение

Обратный код числа - 63

Обратный код числа - 95

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

Все рассмотренные случаи имеют место и при сложении дополнительных кодов чисел.

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

1. Что понимают под системой счисления?

2. Какие существуют системы счисления?

3. Что такое позиционная система счисления?

4. Что такое основание системы счисления?

5. Сформулируйте правило перевода из одной позиционной системы счисления в другую.

6. Сформулируйте правило перевода из двоичной системы счисления в восьмеричную и шестнадцатеричную системы счисления.

7. Запишите правила выполнения арифметических действий в двоичной системе счисления.

8. Как представляются целые числа без знака в однобайтном (вдвухбайтовом ) формате?

9. Как представляются целые числа со знаком?

10. Что такое прямой код?

11. Что такое обратный код?

12. Что такое дополнительный код?

13. Как связаны прямой, обратный и дополнительный коды?

14. Какие случаи возможны при выполнении компьютером арифметических действий над целыми числами?

МНОЖЕСТВА

ЗАДАНИЕ МНОЖЕСТВ

Интуитивное определение множества. Множество – это собрание определенных и различных между собой объектов, мыслимое как единое целое. Эти объекты называются элементами множества.

В этом определении собрание предметов рассматривается как один объект, как единое целое. Примеры множеств:

1) множество студентов в данной аудитории;

2) множество целых положительных чисел меньших 10;

3) множество решений уравнения x2-1=0;

4) множество чисел Фибоначчи: 1, 2, 3,…., где k+2= k+ k+1, k≥1, 1= 2=1;

5) множество самолетов и авиапассажиров.

Если объект (элемент) х принадлежит множеству М, то записываем х М, если же х не является элементом из М, то х М. Отношение называется отношением принадлежности.

То, что множество М состоит из элементов 1, 2, … n, записывает с помощью фигурных скобок: М={ 1, 2, … n}.

Введем понятие предиката и порождающей процедуры.

ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Объединением множеств А и В называется множество А U В, каждый элемент которого является элементом множества А

или множества В:

A B={x: x А или х В}.

На рис. 1.1 множество А В заштриховано. рис 1.1

Пересечение множеств А и B называется множество

A B, элемент которого являются элементами обоих множеств

А и В: A B ={x: x А или х В}.

Рис. 1.2

На рис. 1.2 множество А В заштриховано.

Разность множеств А и В: - А\В

А\В={x: x А и х В}.

Рис. 1.3

На рис. 1.3 множество А\В заштриховано.

Симметричная разность множеств А и В: - А В

А В=(А В)\(А В) ={x: (x А и х В) или (x В и х А)}. Рис. 1.4

На рис 1.4 множество А В заштриховано

U

Дополнение множества А: - =СА{х: х А}

Предполагается, что существует (универсальное)

множество U, такое, что А U. На рис 1.5

множество заштриховано.

рис 1.5

СВОЙСТВА ОПЕРАЦИЙ НАД МНОЖЕСТВАМИ

1. =А – свойство инволютивности;

2.

- законы коммутативности;

А В=В А

3. А В=В А

4.

- законы ассоциативности;

А (В С)=(А В) С

5. А (В С)=(А В) С

6.

- законы дистрибутивности;

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

7. А (В С)=(А В) (А С)

8.

- законы поглощения;

А (А В)=А

9. А (А В)=А

10.

- свойства операций с Ø и с U;

Ø=A

11. A U=U

12. A Ø= Ø

13. A U=A

14.

- законы де Моргана;

15.

16.

- свойства дополнения;

17. A =Ø

18.

- законы идемпотентности;

A A=A

19. A A=A

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

1. Перечислите операции над множествами.

2. Запишите закон коммутативности.

3. Запишите закон ассоциативности.

4. Запишите закон идемпотентности.

5. Запишите закон да Моргана.

6. Запишите закон поглощения.

7. Запишите закон ассоциативности.

8. Запишите закон дистрибутивности.

9. Что представляет собой объединение множеств?

10. Что представляет собой пересечение множеств?

11. Что представляет собой дополнение множества?

Логические основы компьютера

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

Пример:

Петров – врач

Петров – шахматист

Петров – врач и шахматист

Логические высказывания обозначаются буквами латинского алфавита A,B,…,Z и называются логическими переменными.

Истина обозначается – И, 1.

Ложь обозначается – Л, 0.

Употребляемые в обычной речи слова и словосочетания “не”, “и”, “или”, “если … то”, “тогда и только тогда” позволяют из уже заданных высказываний строить новые высказывания. Эти слова и словосочетания называются логическими связками (логическими операциями).

Операция, выраженная словом “не” называется отрицанием и обозначается: , .

Таблица истинности (одноместная операция):

A

Операция, выражаемая словом “и”, называется конъюнкцией или логическим умножением и обозначается: /\.

Таблица истинности (двухместная операция):

A	B

Операция, выражаемая словом “или”, называется дизъюнкцией или логическим сложением и обозначается: \/.

Таблица истинности (двухместная операция):

A	B

Операция, выражаемая связками “если … то” называется импликацией (тесно связанной) и обозначается: .

Таблица истинности (двухместная операция):

A	B

Операция, выражаемая связками “тогда и только тогда” называется эквивалентностью или

двойной импликацией, обозначается: .

Таблица истинности (двухместная операция):

A	B

Импликацию можно выразить через \/ и :

A B= A\/B.

Эквивалентность можно выразить через ,\/,&:

A B=(A B)&(A B)=( A\/B)&( B\/A).

Логическая формула – это:

1.Всякая логическая переменная и символы “истина” и “ложь”.

2.Если А и В формулы, то A, A&B, A\/B, A B, A B - формулы.

3.Никаких других формул в алгебре логики нет.

Если формулы принимают значения при одних наборах букв “истина” при других “ложь”, то эти формулы называются выполнимыми.

Если формула при любых значениях принимает значение “истина”, то она называется тавтологией.

Пример:

A\/ A.

Если формулы при любых значениях, входящих в нее переменных принимает значение “ложь”, то она называется противоречием.

Пример:

A& A.

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры “1” и “0”, а значений логических переменных тоже два: “1” и “0”.

ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон	для ИЛИ	для И
Перместительный
Сочитательный
Распределительный
Правило де Моргана
Идемпотенции
Двойного отрицания
Поглощения
Склеивания
Операция переменной с ее инверсией
Операции с константами

ТАБЛИЦЫ ИСТИННОСТИ

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

x	y						*

УПРОЩЕНИЕ ЛОГИЧЕСКИХ ФОРМУЛ

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

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

1) .

2) .

3) .

4)

5) .

6) .

7) .

РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач: средствами алгебры логики; табличный; с помощью рассуждений. Познакомимся с ними поочередно.