Арифметические основы работы компьютера кратко. Лекция: Арифметические и логические основы работы компьютера. Операции над положительными и отрицательными числами

10) Особенности представления чисел в ЭВМ: прямой, обратный, дополнительный коды.

· прямого кода. Прямой код двоичного числа совпадает по изображению с записью самого числа.

· обратного кода . Обратный код для положительного числа совпадает с прямым кодом. Для отрицательного числа все цифры числа заменяются на противоположные (1 на 0, 0 на 1), а в знаковый разряд заносится единица.

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

Тема 2. ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

11) Основные логические операции: конъюнкция, дизъюнкция, инверсия:

Алгебра логика строится на основе следующих аксиом:

1) Переменная может принимать только одно из возможных значений:

x = 0, если x < >1,

x = 1, если x < >0.

2) Инверсия

3) Дизъюнкция

4) Конъюнкция

5) Во избежании побочных записей вводится преоритетность выполнения операций

Инверсия(-)

Конъюнкция(&)

Дизъюнкция (v)

Равенство(=)

РАЗДЕЛ 5. КОМПЬЮТЕРНЫЕ СЕТИ

Тема 14. КЛАССИФИКАЦИЯ СЕТЕЙ. СТРУКТУРА И ПРИНЦИПЫ РАБОТЫ ЛОКАЛЬНЫХ И ГЛОБАЛЬНЫХ СЕТЕ

46. Понятие компьютерной сети

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

47. Виды сетей: локальные, глобальные.

· К локальным сетям (Local Area Network, LAN) обычно относят сети, компьютеры которых сосредоточены на относительно небольших территориях (как правило, в радиусе до 1-2 км). Классическим примером локальных сетей является сеть одного предприятия, расположенного в одном или нескольких стоящих рядом зданиях. Небольшой размер локальных сетей позволяет использовать для их построения достаточно дорогие и высококачественные технологии, что обеспечивает высокую скорость обмена информацией между компьютерами.

· Глобальные сети (Wide Area Network, WAN) – это сети, предназначенные для объединения отдельных компьютеров и локальных сетей, расположенных на значительном удалении (сотни и тысячи километров) друг от друга. Поскольку организация специализированных высококачественных каналов связи большой протяженности является достаточно дорогой, то в глобальных сетях нередко используются уже существующие и изначально не предназначенные для построения компьютерных сетей линии (например, телефонные или телеграфные). В связи с этим скорость передачи данных в таких сетях существенно ниже, чем в локальных.

48. Локальная сеть и ее основные компоненты

Аппаратное обеспечение:

Серверы

Сетевые интерфейсные платы (NIC, Network Interface Card)

Концентраторы

Коммутаторы

Маршрутизаторы (территориально-распределенные сети)

Серверы удаленного доступа (территориально-распределенные сети)

Модемы (территориально-распределенные сети)

Программное обеспечение:

Сетевую операционную систему

Сетевое ПО управления

49. Адресация компьютера в сети

Каждый компьютер в компьютерной сети имеет имя. Для этого служит так

называемая IP (Internet Рго1осо1)-адресация.

IP-адрес - это уникальный номер компьютера в сети. IP-адрес определяет местонахождение узла в сети подобно тому, как адрес дома указывает его расположение в городе. IP-адрес может быть «статический - неизменный» или «динамический - выдается сервером». Каждый IP-адрес состоит из двух частей - идентификатора сети и идентификатора узла. Первый определяет физическую сеть. Он одинаков для всех узлов в одной сети и уникален для каждой из сетей, включенных в объединенную сеть. Идентификатор узла соответствует конкретной рабочей станции, серверу, маршрутизатору или другому TCP/IP-узлу в данной сети. Он должен иметь уникальное значение в данной сети. Каждый узел TCP/IP однозначно определяется по своему логическому IP-адресу. Такой уникальный адрес необходим всем сетевым компонентам, взаимодействующим по TCP/IP.

50. Понятие протокола передачи информации

Протокол - это набор правил и соглашений, используемых при передаче данных.

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

51. Многоуровневая модель OSI

Сетевая модель OSI (базовая эталонная модель взаимодействия открытых систем) - сетевая модель стека сетевых протоколов OSI/ISO.

Начинается OSI с 7-го уровня , на котором пользовательские приложения обращаются к сети, заканчивается 1-м уровнем, на котором определены стандарты, предъявляемые независимыми производителями к средам передачи данных.

Любой протокол модели OSI должен взаимодействовать либо с протоколами своего уровня, либо с протоколами на единицу выше и/или ниже своего уровня. Взаимодействия с протоколами своего уровня называются горизонтальными, а с уровнями на единицу выше или ниже - вертикальными. Любой протокол модели OSI может выполнять только функции своего уровня и не может выполнять функции

Модель TCP/IP описывает функциональность протоколов, составляющих набор протоколов TCP/IP. Эти протоколы, которые выполняются как на отправляющем, так и на принимающим хостах, взаимодействуют для обеспечения доставки сообщений от одного конца к другому по сети.

TCP (Transmission Control Protocol) – протокол управления передачи данных, сокет с виртуальным каналом.

UDP (Users Datagram Protocol) – сокет дейтаграмм.

IP (Internet Protocol) – маршрутизируемый протокол сетевого уровня стека TCP/IP.

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

RIP (Routing Information Protocol) - один из самых простых протоколов маршрутизации. Применяется в небольших компьютерных сетях, позволяет маршрутизаторам динамически обновлять маршрутную информацию (направление и дальность в хопах), получая ее от соседних маршрутизаторов.

ICMP (Internet Control Messages Protocol- протокол межсетевых управляющих сообщений)- сетевой протокол, входящий в стек протоколов TCP/IP. Используется для передачи сообщения об ошибках и других исключительных ситуациях, возникших при передаче данных. Один из важнейших служебных протоколов Интернета. Как правило, используется самой операционной системой (ядром) или служебными программами.

52. Базовые технологии (архитектуры) локальных сетей: Ethernet; Token Ring; Arcnet; FDDI.

Шина (Bus)

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

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

Звезда (Star)

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

Кольцо (Ring)

Линейный алгаритм

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

Разветвляющийся алгоритм

В зависимости от поставленного условия выборочно выполняется одна или другая последовательность команды

В простей­шем случае, это ответ на вопрос «Да» или «Нет». Во всех языках программирования эта возможность реализована при помощи оператора ветвления If......EndIf.

Циклический алгоритм

В алгоритме есть последовательность команд которая выполняется несколько раз. Число повторений может быть задано заранее иди может зависеть от конкретно поставленного условия

Циклический алгоритм может иметь несколько вариантов.

«Для» (For) служит для проведения определенного количества итераций (повторов).

«Пока» (While|Until) выполняется до тех пор, пока соблюдается определенное условие.

«Неопределенный цикл» (Do) выполняется бесконечно или пока внутри его тела не выполнится команда принудительного завершения цикла. Чаще всего задается с условием.

В некоторых языках программирования могут использоваться специализированные циклы: для обхода всех элементов набора объектов (For Each) или для просмотра всех записей в таблице базы данных (Scan).

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

Алгоритмы решения типовых задач.

РАЗДЕЛ 1. АРИФМЕТИЧЕСКИЕ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

Тема 1. ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В КОМПЬЮТЕРЕ, ЕДИНИЦЫ ИЗМЕРЕНИЯ ИНФОРМАЦИИ. СИСТЕМЫ СЧИСЛЕНИЯ

1) Единица измерения информации:

Количество информации - это мера уменьшения неопределенности - это самое распространенное и разумное определение величины.

Обычно=почти всегда, дела обстоят так:

• 1 бит – такое кол-во информации, которое содержит сообщение, уменьшающее неопределенность знаний в два раза. БИТ- это наименьшая единица измерения информации
• 1байт = 8 бит - (есть 6 и 32 битовый байты тоже)
• 1Кб (килобайт) = 2 10 байт = 1024 байт = 8192 бит (не обязательно так, приставка "кило" иногда может обозначать и 10 3)
• 1Мб (мегабайт) = 2 10 Кб = 1024 Кб = 8 388 608 бит (не обязательно так, приставка "кило" иногда может обозначать и 10 6)
• 1Гб (гигабайт) = 2 10 Мб = 1024 Мб = 8 589 934 592 бит (не обязательно так, приставка "кило" иногда может обозначать и 10 9)

2) Кодирование текстовой информации:

Windows-1251 – введена компанией Microsoft; с учетом широкого распространения операционных систем (ОС) и других программных продуктов этой компании в Российской Федерации она нашла широкое распространение;

КОИ-8 (Код Обмена Информацией, восьмизначный) – другая популярная кодировка российского алфавита, распространенная в компьютерных сетях на территории Российской Федерации и в российском секторе Интернет;

ISO (International Standard Organization – Международный институт стандартизации) – международный стандарт кодирования символов русского языка. На практике эта кодировка используется редко.

Система 16-разрядного кодирования символов называется универсальной – UNICODE . Шестнадцать разрядов позволяет обеспечить уникальные коды для 65 536 символов, что вполне достаточно для размещения в одной таблице символов большинства языков. (используется на данный момент)

3) Кодирование графики:

o Например, чтобы записать на запоминающем устройстве векторное изображение круга, компьютеру достаточно в двоичный код закодировать тип объекта (окружность), координаты его центра на холсте, длину радиуса, толщину и цвет линии, цвет заливки.

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

4) Кодирование звука:

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

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

5) Основные понятия системы счисления, алфавит и основные системы:

Система счисления – это способ записи чисел c помощью чисел.

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

Символы алфавита системы счисления называются цифрами системы счисления .

Системы счисления делятся на:

Непозиционные системы счисления;

Позиционные системы счисления.

6) Позиционная система счисления:

Позиционными называются системы счисления, в которых значение цифры зависит от ее места (позиции) в записи числа.

7) Непозиционная система счисления:

Непозиционными называются системы счисления, в которых значение цифры не зависит от ее места (позиции) в записи числа. (Римская (II, V, XII)).

8) Правила перевода из десятичной системы счисления в двоичную, восьмеричную, шестнадцатеричную и наоборот:

· Из десятичной в двоичную:

Делим число на 2 до того, пока частное от деления не будет 1. И записываем наоборот (101000)

Делим число на 8 до того, пока частное от деления не будет 1 или меньше 8. И записываем наоборот

· Из десятичной в восьмеричную:

Делим число на 16 до того, пока частное от деления не будет 1 или меньше 16. И записываем наоборот

ТЕПЕРЬ НАОБОРОТ!!:

· Из восьмеричной в двоичную:

· Из восьмеричной в десятичную:

9) Основные арифметические действия в двоичной, восьмеричной, шестнадцатеричной системах счисления.

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

Логика - это наука о формах и способах мышления. Это учение о способах рассуждений и доказательств. Понятие - это форма мышления, которая выделяет существенные признаки предмета или класса предметов, позволяющие отличать их от других. Пример Прямоугольник, проливной дождь, компьютер – это понятия.

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

Пример «Буква «а» - гласная» - истинное высказывание. «Компьютер был изобретён в середине 19 века» ложное высказывание.

Задание. Какие из предложений являются высказываниями? Определите их истинность. 1. Какой длины эта лента? (не является высказыванием) 2. Делайте утреннюю зарядку! (не является высказыванием) 3. Париж - столица Англии. (является ложным высказыванием) 4. Число 11 является простым. (является истинным высказыванием) 5. 4 + 5 = 10 (является ложным высказыванием) 6. Без труда не вытащишь и рыбку из пруда. (является истинным высказыванием) 7. Некоторые медведи живут на севере. (является истинным высказыванием) 8. Все медведи - бурые. (является ложным высказыванием)

Умозаключение - это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение (знание или вывод). Пример Дано высказывание: «Все углы равнобедренного треугольника равны» . Получите высказывание «Этот треугольник равносторонний» путём умозаключений.

ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ОПЕРАЦИИ Алгебра логики - это наука об общих операциях, аналогичных сложению и умножению, которые выполняются над высказываниями.

Логическая переменная - это простое высказывание, содержащее только одну мысль. Её символическое обозначение - латинская буква (например, A, B, X, Y и т. д.) Составное высказывание - логическая функция, которая содержит несколько простых мыслей, соединённых между собой с помощью логических операций. Её символическое обозначение - F(A, B, …). На основе простых высказываний могут быть построены составные высказывания.

Логические операции - логическое действие. Таблица истинности - таблица, определяющая значение сложного высказывания при всех возможных значениях простых высказываний. Рассмотрим три базовые логические операции - конъюнкцию, дизъюнкцию и отрицание и дополнительные - импликацию и эквиваленцию.

Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение, значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА. При составлении логического выражения необходимо учитывать порядок выполнения логических операций, а именно: действия в скобках; инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция.

Пример Запишите в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдёт на рыбалку» . Проанализируем составное высказывание. Оно состоит из следующих простых высказываний: «Петя поедет в деревню» , «Будет хорошая погода» , «Он пойдёт на рыбалку» . Обозначим их через логические переменные: А = Петя поедет в деревню; В = Будет хорошая погода; С = Он пойдёт на рыбалку. Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки: F = A & (B → C).

Основные действия над числами - это сложение и вычитание.

• 1. Сложение двоичных чисел
• 0 + 0 = 0 0+1 = 1 1+0=1
• 1 + 1=0 + единица переноса в старший разряд, т.е. 1 + 1=10 2 .

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

Пример 1. Сложить в двоичной системе

• 2. Вычитание двоичных чисел осуществляется в соответствии со следующими правилами:
• 0-0 = 0 1-0=1 1-1=0 10 2 -1 = 1

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

Операции над положительными и отрицательными числами

Распространенными формами представления чисел со знаками является их представление в прямом, обратном и дополнительном коде.

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

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

Пример 1. Представьте положительное число 127ю=1111111 2 в прямом коде: 0 1111111

Пример 2. Представьте отрицательное число - 1)0 в прямом коде:

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

Пример 3. Представьте отоинательное число - 1 ш в обратном коде:

Пример 4. Представьте отпиттятетткнпе хшг.тто - 1 77 10 в обратном коде:

Код модуля числа Обратный код числа

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

Пример 5. Представьте отрицательное число - 1ю в дополнительном коде: 11111111

Пример 6. Представьте отрицательное число -127ю в дополнительном коде:

Сложение чисел в дополнительном коде

Пример 1. Выполните следующую арифметическую операцию «-5+3».

Наши действия в этом случае таковы:

3. Осуществим сложение чисел.

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

Ответ: - 2, следовательно, все действия выполнены верно.

Пример 2. Выполните следующую арифметическую операцию «5 - 3». Выполняя операцию вычитания и представляя отрицательное число в дополнительном коде, можно операцию вычитания заменить сложением.

1. Представим числа в двоичном коде:

2. Отрицательное число следует представить в дополнительном коде. Для этого инвертируем все разряды числа, кроме знакового, и в младший разряд результата добавим единицу.

3. Осуществим сложение чисел.

• 4. Если результат получился положительным, то единицу переноса из знакового разряда отбрасывают.
• 5. Полученное число следует перевести в десятичную систему счисления. Ответ: + 2, следовательно, все действия выполнены верно.

Связь между алгеброй логики и двоичным кодированием

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

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

Так, например, предложение «8 - четное число» следует считать высказыванием, так как оно истинное. Предложение «Москва - столица Бельгии» тоже высказывание, так как оно ложное.

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения «студент первого курса» и «мороженое - вкусное». Первое предложение ничего не утверждает о студенте, а второе использует слишком неопределенное понятие «вкусное». Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла. Предложения типа «в городе А более миллиона жителей », «у нее голубые глаза » не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь.

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

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

Из этого следует:

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

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

Логический элемент компьютера - это часть электронной логической схемы, которая реализует элементарную логическую функцию.

Простейшими логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-HE». Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем.

Работу логических элементов, как и логических функций, описывают с помощью таблиц истинности. Таблица истинности - это таблица, в которую записаны значения логической функции для каждого из 2 П наборов аргументов на входе. Например, полная таблица истинности выражения с тремя переменными содержит 2 3 =8 строчек, если заданы только 6 из них, то можно найти 2 8 " 6 =2 2 =4 разных логических выражения, удовлетворяющие этим 6 строчкам. Для того чтобы полностью определить логическую функцию, достаточно перечислить либо все наборы, при которых эта функция принимает значения, равные 1, либо все наборы, при которых эта функция принимает значения, равные 0.

Элементарные логические функции и логические элементы

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

Функция отрицания - это логическая функция от одного аргумента, которая принимает значение 1, если аргумент равен 0, и принимает значение 0, если аргумент равен 1, и называется отрицанием (инверсией) или логической функцией «НЕ».

В обыденной речи мы часто пользуемся словом «НЕ», или словами «НЕВЕРНО, ЧТО», когда хотим что-то отрицать. Пусть, например, кто-то сказал: «На улице холодно». (Обозначим это высказывание А.) Если вы не согласны, вы скажете: «На улице НЕ холодно». Или: «Неверно, что на улице холодно». (Ваше высказывание обозначим В.) Нетрудно заметить, что значения истинности высказываний А и В находятся в определенной связи: если А истинно, то В ложно, и наоборот.

Запись логической функции «НЕ» можно обозначить как F = X, где черта над переменной - признак инверсии, либо как -iX. Логическая функция «НЕ» от одного аргумента описывается таблицей истинности (табл. 8).

Таблица 8. Таблица истинности для логической функции «НЕ»

Логический элемент «НЕ» (инвертор) реализует операцию отрицания. Если на входе этого логического элемента 0, то на выходе 1, а когда на входе 1, на выходе 0.

Условное обозначение инвертора на структурных схемах приведено на рис. 12.

Рис. 12.

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

Высказывая конъюнкцию, мы утверждаем, что выполняются оба события, о которых идет речь в высказывании. Например, сообщая: «Петровы взяли отпуск за свой счет и уехали в Крым», мы выражаем в своем высказывании свое убеждение в том, что произошли оба этих события.

Функцию логического умножения называют также конъюнкцией или функцией «И». Элементарная функция логического умножения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 9).

Таблица 9. Таблица истинности для логической функции «И»

При записи логической функции «И» возможны следующие варианты: F=X AY;

F=XY, где знаки «Л», «&», « » - знаки, обозначающие операцию логического умножения. Все варианты записи равнозначны.

Рис. 13.

Логический элемент «И» реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах конъюнкции с двумя входами представлено на рис. 13.

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

Функцию логического сложения называют также дизъюнкцией или логической функцией «ИЛИ». Сообщая: «Петров смотрит телевизор или смотрит в окно», мы имеем в виду, что хотя бы одно Петров делает. При этом Петров может одновременно смотреть телевизор и смотреть в окно. И в этом случае дизъюнкция будет истинна.

Элементарная дизъюнкция зависит от двух аргументов и описывается следующей таблицей истинности (табл. 10).

Таблица 10. Таблица истинности для логической функции «ИЛИ»

Рис. 14.

При записи логической функции «ИЛИ» возможны следующие варианты:

где знаки «V», «+» обозначают операцию логического сложения.

Логический элемент «ИЛИ» реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе элемента «ИЛИ» будет единица, на ее выходе также будет единица. Условное обозначение на структурных схемах логического элемента «ИЛИ» с двумя входами представлено на рис. 14.

Функция отрицания от логического умножения «И-НЕ» принимает значение 0, когда все аргументы равны 1, и 1 - во всех остальных случаях. Функция отрицания от логического умножения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 11).

Таблица 11. Таблица истинности для функции отрицания от логического умножения

При записи функции отрицания от логического умножения возможны следующие варианты:

Рис. 15.

Логический элемент «И-НЕ» состоит из элемента «И» и инвертора и осуществляет отрицание результата функции И. Условное обозначение на структурных схемах логического элемента «И-НЕ» с двумя входами представлено на рис. 15.

Функция отрицания от логического сложения принимает значение 1, когда все аргументы равны 0, и значение 0 - во всех остальных случаях.

Функция отрицания от логического сложения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 12).

Таблица 12. Таблица истинности для функции отрицания от логического сложения

При записи функции отрицания от логического сложения возможны следующие варианты:

Рис. 16.

Логический элемент «ИЛИ-HE» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата логической функции «ИЛИ». Условное обозначение на структурных схемах логического элемента «ИЛИ-HE» с двумя входами представлено на рис. 16.

В сложных выражениях с использованием логических операций «И», «ИЛИ», «НЕ» сначала выполняется операция отрицания «НЕ», затем операция конъюнкции «И». В последнюю очередь выполняется операция дизъюнкции «ИЛИ». Для того чтобы изменить указанную последовательность выполнения операций, в выражениях следует использовать скобки. Кроме перечисленных функций, одной из важнейших операций является импликация (следование), которая обозначается -> и описывается соответствующей таблицей (табл. 13).

Таблица 13. Таблица истинности для функции импликации

Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

Рассмотрим высказывание: «Если завтра будет хорошая погода, то я пойду гулять». Здесь А= Завтра будет хорошая погода и В= Я пойду гулять. Ясно, что человек окажется лжецом лишь в том случае, если погода действительно окажется хорошей, а гулять он не пойдет. Если же погода будет плохой, то независимо от того, пойдет он гулять или нет, во лжи его нельзя обвинить: обещание пойти гулять он давал лишь при условии, что погода будет хорошей.

В обычной речи связка «если..., то» описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться «бессмысленностью» импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: «если на Луне есть вода, то в зоопарке живут тигры», «если клубника - ягода, то в магазине есть хлеб».

Импликация заведомо истинна, если условие А ложно. Другими словами, из неверного условия может следовать все, что угодно. Например, высказывание «Если 2>3, то крокодилы летают» является истинным.

Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно» называется эквиваленцией или двойной импликацией и обозначается знаками, =. Эквиваленция описывается соответствующей таблицей

Таблица 14. Таблица истинности для функции эквиваленции

Например, сообщая: «Я получу паспорт тогда и только тогда, когда мне исполнится 14 лет», человек утверждает не только то, что после того, как ему исполнится 14 лет, он получит паспорт, но и то, что паспорт он сможет получить только после того, как ему исполнится 14 лет.

Таким образом, высказывание XY истинно тогда и только тогда, когда значения X и Y совпадают. Следует учитывать, что рассмотренную нами операцию - импликацию можно выразить через дизъюнкцию и отрицание:

а эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

Каким выражением может быть F?

Построим таблицу истинности для всех предложенных в ответе выражений:

Вычислим логические выражения для четырех предложенных ответов. Видим, что совпали значения логических выражений в столбцах X v Y v Z и F, следовательно, правильный ответ 3.

Пример 2. Для какого из указанных значений X истинно высказывание

Видно, что высказывание представляет собой отрицание выражения ((Х>2) -> -> (Х>3)). Оно истинно, когда ((Х>2) -> (Х>3)) ложно. Импликация ложна в единственном случае: левое высказывание истинно (в нашем случае Х>2 истинно для Х=3 и Х=4), а правое ложно (это справедливо для Х=1, Х=2 и Х=3). Поэтому единственный вариант, когда эта импликация ложна (следовательно, исходное выражение истинно), - третий.

Основные законы алгебры логики

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

Таблица 15. Правила преобразования логических выражений

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

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

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

• - либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул;
• - либо содержит меньшее число вхождений переменных.

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул.

Пример 1.

(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с ее инверсией и правило операций с константами).

Пример 2.

(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с ее инверсией).

Пример 3. Какое логическое выражение равносильно выражению

По правилу де Моргана выполним преобразование

Пользуясь правилом двойного отрицания, в итоге получаем: , следовательно, правильный ответ 2.

Контрольные вопросы и задания

• 1. Расскажите о правилах двоичной арифметики.
• 2. Прямой, обратный и дополнительный коды числа - поясните разницу между ними.
• 3. Какая связь существует между двоичным кодированием и алгеброй логики?
• 4. Какие элементарные логические функции и логические элементы вы знаете? Приведите в качестве примеров их таблицы истинности.
• 5. Выполните сложение следующих чисел:

6. Выполните вычитание следующих чисел:

• 7. Опишите связь между алгеброй логики и двоичным кодированием. Приведите примеры логических высказываний.
• 8. Что такое таблица истинности?
• 9. Дайте характеристику логической функции НЕ. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции НЕ.
• 10. Дайте характеристику логической функции И. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции И.
• 11. Дайте характеристику логической функции ИЛИ. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции ИЛИ.
• 12. Расскажите о логической операции «импликация». Приведите ее таблицу истинности.
• 13. Какое логическое высказывание эквивалентно выражению -i (A v -iB д С)?

14. Дан фрагмент таблицы истинности выражения F.

Представление информации в компьютере .

Для автоматизации работы с данными, которые относятся к разным типам, унифицируют их форму представления. Это можно сделать с помощью кодирования данных на единой основе. В быту используют такие системы кодировки, как азбука Морзе, Брайля, коды морских сигналов. Основное понятие арифметики это число . Число – абстрактное выражение количества. Компьютер обрабатывает информацию, представленную только в числовой форме. Он оперирует с кодами и числами, представленными в некоторой системе счисления.

Система счисления – способ представления чисел(правило записи и получения чисел), с помощью фиксированного набора символов, обозначающих цифры. По способу представления чисел системы счисления разделяются на позиционные и непозиционные.

Непозиционные системы для записи числа используют множество символов. Значение символа не зависит от местоположения его в числе(римская СС ).

Позиционная система счисления – когда от позиции цифры в числе зависит ее вес(555 –единицы, десятки, сотни). Всякая позиционная СС характеризуется основанием , т.е. количеством цифр, используемых для записи числа. За основание СС можно принять любое натуральное число.

10 ая – использует 10 цифр → 0, 1… 9

2 ая – 2 цифры → 0, 1

Люди предпочитают 10 ую (это удобно, видимо потому, что с древних времен считали по пальцам).

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

Для ее реализации нужны устройства всего с двумя устойчивыми состояниями (есть ток, нет тока). Это надежнее, чем, например, 10 ая ;

возможно применение аппарата булевой алгебры;

двоичная арифметика проще десятичной;

представление информации с помощью 2-х состояний более надежно.

Недостаток : - быстрый рост разрядов.

В компьютере используются также 8 ая и 16 ая системы.

Перевод чисел из 10 ой в 2 ую и наоборот выполняет машина.

При вводе информация кодируется, при выводе декодируется.

Обозначение цифр в 2 ой системе: 0, 1, 10, 11(3), 100(4), 101(5), 110(6), 111(7), 1000(8), 1001(9), 1010(10) и т.д.

Обозначение цифр в 8-ой системе: 0, 1, 2 … 7, 10(8), 11(9), 12(10)……17(15), 20(16), 21(17) и т.д.

Обозначение цифр в 16 ой системе: 0, 1, 2 … 9, A (10), B (11), C (12) ... F (15), 10(16), 11(17) и т. д.

Целое число в позиционной СС может быть представлено в виде:

A q =a n-1 q n-1 +a n-2 q n-2+…+ a 0 q 0 , где

A – само число;

q – основание системы счисления;

a i – цифры, принадлежащие алфавиту данной системы счисления;

n – число целых разрядов числа.

Пусть в десятичной системе задано число 375 10 .

Каждая позиция, занимаемая цифрами, называется разрядом числа . Разряды имеют названия и номера: разряд единиц (0), разряд десятков (1), разряд сотен (2). Названия определяют вес (012) . Число в позиционной системе счисления представляет собой сумму степеней основания, умноженную на соответствующий коэффициент, который должен быть одной из цифр данной системы счисления. Достаточно просуммировать веса единичных разрядов.

А 10 =375

375 10 =5*10 0 +7*10 1 +3*10 2 = 5+70+300=375

Это называется разложением числа по степеням основания.

Номера разрядов совпадают с показателем степени.

101101 2 =1*2 0 +0*2 1 +1*2 2 +1*2 3 +0*2 4 +1*2 5 =1+0+4+8+0+32=45 10

10110 2 =0*2 0 +1*2 1 +1*2 2 +0*2 3 +1*2 4 =0+2+4+0+16=22 10

100001 2 =1*2 0 +0*2 1 +0*2 2 +0*2 3 +0*2 4 +1*2 5 =1+32=33 10

17 8 =1*8 1 +7*8 0 = 8+1=15 10

7764 8 = 7*8 3 +7*8 2 +6*8 1 +4*8 0 = 3584+448+48+4 =4084 10

17 16 = 1*16 1 +7*16 0 = 16+7 = 23 10

3 AF 16 =3*16 2 +10*16 1 +15*16 0 =768+160+15=943 10

1 A 16 = 1*16 1 +10*16 0 = 16+10 = 26 10

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

33 10 = ? 2

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

33 10 = 100001 2

Двоичная система счисления является стандартом при конструировании компьютеров.

Десятичная система счисления используется для организации ввода / вывода информации. Двоичная СС – для организации машинных операций по преобразованию информации. 8-миричная и 16-тиричная системы используются для более короткой и удобной записи, т. к. требует меньше разрядов(для записи программ в машинных кодах).

Система счисления - это способ записи чисел с помощью заданного набора специальных знаков (цифр).

Существуют позиционные и непозиционные системы счисления.

В непозиционных системах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.

В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая – 7 единиц, а третья – 7 десятых долей единицы.

Сама же запись числа 757,7 означает сокращенную запись выражения

700 + 50 + 7 + 0,7 = 7 10 2 + 5 10 1 + 7 10 0 + 7 10 -1 = 757,7.

Любая позиционная система счисления характеризуется своим основанием.

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

За основание системы можно принять любое натуральное число - два, три, четыре и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д. Запись чисел в каждой из систем счисления с основанием q означает сокращенную запись выражения

a n-1 q n-1 + a n-2 q n-2 + ... + a 1 q 1 + a 0 q 0 + a -1 q -1 + ... + a -m q -m ,

где a i – цифры системы счисления; n и m – число целых и дробных разрядов, соответственно.

В каждой системе счисления цифры упорядочены в соответствии с их значениями: 1 больше 0, 2 больше 1 и т.д.

Продвижением цифры называют замену её следующей по величине.

Продвинуть цифру 1 значит заменить её на 2, продвинуть цифру 2 значит заменить её на 3 и т.д. Продвижение старшей цифры (например, цифры 9 в десятичной системе) означает замену её на 0. В двоичной системе, использующей только две цифры – 0 и 1, продвижение 0 означает замену его на 1, а продвижение 1 – замену её на 0.

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

Применяя это правило, запишем первые десять целых чисел

в двоичной системе: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001;

в троичной системе: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100;

в пятеричной системе: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14;

восьмеричной системе: 0, 1, 2, 3, 4, 5, 6, 7, 10, 11.

Кроме десятичной широко используются системы с основанием, являющимся целойстепенью числа 2, а именно:

двоичная (используются цифры 0, 1);

восьмеричная (используются цифры 0, 1, ..., 7);

шестнадцатеричная (для первых целых чисел от нуля до девяти используются цифры 0, 1, ..., 9, а для следующих чисел - от десяти до пятнадцати – в качестве цифр используются символы A, B, C, D, E, F).

Из всех систем счисления особенно проста и поэтому интересна для технической реализации в компьютерах двоичная система счисления.

Компьютеры используют двоичную систему потому, что она имеет ряд преимуществ перед другими системами:

· для ее реализации нужны технические устройства с двумя устойчивыми состояниями (есть ток - нет тока, намагничен - не намагничен и т.п.), а не, например, с десятью, - как в десятичной;

· представление информации посредством только двух состояний надежно и помехоустойчиво;

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

· двоичная арифметика намного проще десятичной.

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

Например:

Чтобы перевести число из двоичной системы в восьмеричную или шестнадцатеричную, его нужно разбить влево и вправо от запятой на триады (для восьмеричной) или тетрады (для шестнадцатеричной) и каждую такую группу заменить соответствующей восьмеричной (шестнадцатеричной) цифрой.

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

Пример: Перевести число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:

Ответ: 75 10 = 1 001 011 2 = 113 8 = 4B 16 .

Пpи переводе правильной десятичной дpоби в систему счисления с основанием q необходимо сначала саму дробь, а затем дробные части всех последующих произведений последовательно умножать на q, отделяя после каждого умножения целую часть пpоизведения. Число в новой системе счисления записывается как последовательность полученных целых частей пpоизведения.

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

Пример: Перевести число 0,35 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:

Ответ: 0,35 10 = 0,01011 2 = 0,263 8 = 0,59 16 .

При переводе числа из двоичной (восьмеричной, шестнадцатеричной) системы в десятичную надо это число представить в виде суммы степеней основания его системы счисления.

Рассмотрим основные арифметические операции: сложение, вычитание, умножение и деление. Правила выполнения этих операций в десятичной системе хорошо известны - это сложение, вычитание, умножение столбиком и деление углом. Эти правила применимы и ко всем другим позиционным системам счисления. Только таблицами сложения и умножения надо пользоваться особыми для каждой системы.

Сложение в шестнадцатеричной системе

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

Пример 1. Сложим числа 15 и 6 в различных системах счисления.

Пример 2. Сложим числа 15, 7 и 3.

Умножение

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

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

Деление

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

Литература

1. Александров П.С. Введение в теорию множеств и общую топологию. – М.: «Наука», Главная редакция физико-математической литературы, 1977.

2. Стол Роберт Р. Множества. Логика. Аксиоматические теории. / Под ред. Шихановича. М.: «Просвещение», 1969.

3. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. – М.: МЦНМО, 1999.

4. Новиков П.С. Элементы математической логики. – М.: Наука, 1973. 400с.

5. Клини С. Математическая логика. – М.: Мир, 1973, 480с.

6. Краткий словарь по логике / Д.П. Горский, А.А. Ивин, А.Л. Никифоров;

7. Королев В.Т., Ловцов Д.А., Радионов В.В. Учебно-методический комплекс. Информационные технологии в юридической деятельности – М.: РАП, 2013.

8. Королев В.Т., Ловцов Д.А., Радионов В.В. Информационные технологии в юридиче-ской деятельности / Под ред. Д.А. Ловцова. – М.: РАП, 2011.

9. Королев В. Т. Информационные технологии в юридической деятельности. Учебно-методические материалы для практических занятий. - М.: РАП, 2012. (имеется в классе персо-нальных компьютеров и на сайте академии).