InformatikaMetodicheskieUkazania
.pdfВариант 24
1.Мощность алфавита равна 256. Сколько Кбайт памяти потребуется для сохранения 160 страниц текста, содержащего в среднем 192 символа на каждой странице?
2.Для кодирования нотной записи используется 7 значков-нот. Каждая нота кодируется одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения, состоящего из 180 нот?
3. Объем видеопамяти равен 1 Мб. Разрешающая способность дисплея 800 × 600 пикселей. Какое максимальное количество цветов можно использовать при условии, что видеопамять делится на две страницы?
4. Два сообщения содержат одинаковое количество символов. Количество информации в первом сообщении в 1,5 раза больше, чем во втором. Какова мощность алфавита, если известно, что количество символов в каждом алфавите не превышает 10 и информационная емкость символов равна целому числу?
Вариант 25
1.Объем сообщения равен 11 Кбайт. Сообщение содержит 11364 символа. Какова мощность алфавита, с помощью которого записано данное сообщение?
2.Для кодирования секретного сообщения используется 12 специальных значков-символов. При этом символы кодируются одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения длиной в 256 символов?
3.Видеопамять имеет объем, в котором может храниться 4-х цветное изображение размером 300 × 200, Какого размера изображение можно хранить в том же объеме видеопамяти, если оно будет использовать 16-цветную палитру?
4.Какое количество информации содержит сообщение о выигрыше в лотерею 4 из 32?
31
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 3 ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ
Цель занятия – научиться строить таблицы истинности логических формул, а также научиться представлять логические выражения с помощью логических схем.
3.1. Высказывание
Высказывание – это повествовательное предложение, в котором что-либо утверждается или отрицается. По поводу любого высказывания можно сказать истинно оно или ложно.
Пример. 3.1. Определить значение истинности для высказываний.
Лед – твердое состояние воды |
Истинное высказывание |
Треугольник – это геометрическая фигура |
Истинное высказывание |
Париж – столица Китая |
Ложное высказывание |
3.2. Логические операции и выражения
Логические величины – это понятия, выраженные словами ИСТИНА или ЛОЖЬ. Следовательно, истинность высказываний выражается через логические величины.
Логические константы: ИСТИНА или ЛОЖЬ.
Логическая переменная – это символическое обозначение логической величины. Например, если известно, что А, В, С – это логические переменные, то они принимают значение только ИСТИНА или ЛОЖЬ.
Логическое выражение – простое или сложное высказывание. Сложное высказывание строится из простых с помощью логических операций.
Логические операции
Конъюнкция (логическое умножение) в русском языке выражается союзом «И». Конъюнкция обозначается знаком & или . Это двухместная операция; записывается в виде А В. Значение такого выражения будет ложно, если значение хотя бы одного операнда ложно.
Дизъюнкция (логическое сложение) в русском языке выражается союзом «Или». Дизъюнкция обозначается знаком . Это двухместная операция, записывается в виде А В. Значение такого выражения будет истинным, если значение хотя бы одного операнда истинно.
Отрицание в русском языке выражается частицей «НЕ». Это унарная (одноместная) операция, которая записывается в виде ⌐А или А .
Импликация (условное высказывание) в русском языке выражается союзами «Если…то»; «Когда…тогда»; «Коль скоро…то» и т.п. Импликация обозначается знаком →. Это двухместная операция, записывается в виде А → В.
Эквивалентность в русском языке выражается союзами «Если и только если»; «Тогда и только тогда, когда». Эквивалентность обозначается знаком ↔.
Приведем таблицы истинности для рассмотренных логических операций.
32
A |
B |
A B |
A B |
A |
A B |
A B |
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
|
В таблице значение ИСТИНА обозначено через 1, а значение ЛОЖЬ – 0. Порядок всех пяти логических операций по убыванию старшинства сле-
дующий: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Логическая формула (логическое выражение) – формула, содержащая лишь
логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА или ЛОЖЬ.
Пример 3.2. Определите истинность формулы
F = ((C B) → B) (A B) → B.
Для решения задачи построим таблицу истинности этой формулы, перебрав все варианты значений логических переменных. Определим правила построения этих таблиц.
1.В заголовок таблицы выносятся все переменные в порядке их следования
вформуле.
2.Если n –количество переменных, то строк в таблице будет 2 × n.
3.Первая колонка заполняется наполовину значением 1 (истина), наполовину 0 (ложь).
4.Последующие столбцы заполняются по правилу: первая половина значений 1 предыдущего столбца заполняется 1, вторая 0, так же и для 0.
5.В последнем столбце значения 1 и 0 чередуются.
C |
B |
A |
C B |
(C |
A B |
((C B) → B) (A B) |
F |
|
|
|
|
B) → B |
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Ответ: Формула является тождественно истинной.
3.3. Логические схемы
Удобным способом представления логических выражений являются логические схемы. Вот как изображаются на таких схемах три основные логические операции:
Дизъюнкция Конъюнкция Отрицание
33
Эти схемы называются вентилями.
Алгоритм построения логических схем следующий.
1.Определите число логических переменных.
2.Определите количество базовых логических операций и их порядок.
3.Изобразите для каждой логической операции соответствующий ей вен-
тиль.
4.Соедините вентили в порядке выполнения логических операций.
Пример 3.3. Нарисовать логическую схему выражения А В С. Количество логических переменных равно 3. Количество базовых логиче-
ских операций равно 2. Порядок выполнения операций в соответствии с приоритетом: сначала выполняется конъюнкция , а затем дизъюнкция .
Пример 3.4. Вычислить значение выражения ( А (В С) D) с помощью логической схемы. А = 0; В = 1; С = 1; D = 0.
Количество логических переменных равно 4. Количество базовых логических операций равно 4. Порядок выполнения операций: операция дизъюнкции В ˅ С , затем первая и вторая конъюнкции, последняя операция – отрицание.
Ответ: Значение выражения равно 1.
Пример3.5. Дана логическая схема. Построить соответствующее ей логическое выражение.
Строим таблицу входов и выходов каждого вентиля в соответствии с нумерацией.
Вентиль |
Вход |
|
Выход |
|
1 |
А, В |
А В |
||
2 |
В, С |
В С |
||
3 |
А В; В С |
(А В) (В С) |
||
4 |
(А В) (В С) |
|
|
|
|
А В) (В С) |
|||
|
|
|
|
|
Ответ: логическая схема реализует функцию А В) (В С) .
34
3.4. Задания для самостоятельного выполнения
Указания к выполнению задания
1.Прочитайте теоретический раздел и разберите примеры 3.1–3.5.
2.Отчет должен содержать условие задачи. Таблицы и схемы должны быть построены аккуратно с использованием линейки и карандаша. Неаккуратно оформленные задания приниматься не будут. Решение каждой задачи должно содержать необходимые пояснения.
Вариант 1
1.Построить таблицу истинности для формулы Х ((X Y ) (X Y )) .
2.Построить логическую схему по формуле A B C A.
3.Определить логическую функцию, реализуемую логической схемой
Вариант 2
1.Построить таблицу истинности для формулы ( X Y X ) (Y X ) .
2.Построить логическую схему по формуле (A B) (C D) .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 3
1.Построить таблицу истинности для формулы ((X Y ) Y ) (X Y ) .
2.Построить логическую схему по формуле (A B) (C B) .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 4
1.Построить таблицу истинности для формулы ((X Y ) Y ) (X Y ) .
2.Построить логическую схему по формуле (A B) (C D) .
3.Определить логическую функцию, реализуемую логической схемой
35
Вариант 5
1.Построить таблицу истинности для формулы ( X Y ) (X Y ) .
2.Построить логическую схему по формуле A B C A B C .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 6
1.Построить таблицу истинности для формулы ((X Y ) Y ) ( X Y ) .
2.Построить логическую схему по формуле A B C A.
3.Определить логическую функцию, реализуемую логической схемой
Вариант 7
1.Построить таблицу истинности для формулы ( X Y ) (X Y ) .
2.Построить логическую схему по формуле A B C A B C .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 8
1.Построить таблицу истинности для формулы ( X Y ) (X Y ) .
2.Построить логическую схему по формуле B C A B .
3.Определить логическую функцию, реализуемую логической схемой
36
Вариант 9
1.Построить таблицу истинности для формулы (X Y Y ) (X Y ) .
2.Построить логическую схему по формуле ( A B) ( A B) .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 10
1.Построить таблицу истинности для формулы ( X Y ) ( X Y ) .
2.Построить логическую схему по формуле A B A B.
3.Определить логическую функцию, реализуемую логической схемой
Вариант 11
1.Построить таблицу истинности для формулы ( X Y ) ( X Y ) .
2.Построить логическую схему по формуле ( A B) ( A B) .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 12
1.Построить таблицу истинности для формулы ( X Y ) ( X Y ) .
2.Построить логическую схему по формуле A B B C .
3.Определить логическую функцию, реализуемую логической схемой
37
Вариант 13
1.Построить таблицу истинности для формулы А В (С А С) .
2.Построить логическую схему по формуле (A C) (B C) .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 14
1.Построить таблицу истинности для формулы А В (С А С) В .
2.Построить логическую схему по формуле ( A D) (B D) .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 15
1.Построить таблицу истинности для формулы А В (С А С) В .
2.Построить логическую схему по формуле A B C D .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 16
1.Построить таблицу истинности для формулы А В (С А С) В .
2.Построить логическую схему по формуле ( A B) ( A B) .
3.Определить логическую функцию, реализуемую логической схемой
38
Вариант 17
1.Построить таблицу истинности для формулы А В (С А С) В .
2.Построить логическую схему по формуле A B C D .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 18
1.Построить таблицу истинности для формулы А В (С А А С) В .
2.Построить логическую схему по формуле A B C A.
3.Определить логическую функцию, реализуемую логической схемой
Вариант 19
1.Построить таблицу истинности для формулы А В (С А А С) .
2.Построить логическую схему по формуле (A B) (C D) .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 20
1.Построить таблицу истинности и для формулы А В (С А А С) В .
2.Построить логическую схему по формуле A B C A B C .
3.Определить логическую функцию, реализуемую логической схемой
39
Вариант 21
1.Построить таблицу истинности для формулы В (С А А С) .
2.Построить логическую схему по формуле A B C A.
3.Определить логическую функцию, реализуемую логической схемой
Вариант 22
1.Построить таблицу истинности для формулы В А (С А С) .
2.Построить логическую схему по формуле A B A B .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 23
1.Построить таблицу истинности для формулы А (С А А С) В .
2.Построить логическую схему по формуле ( A B) ( А B) .
3.Определить логическую функцию, реализуемую логической схемой
Вариант 24
1.Построить таблицу истинности для формулы А В (С А А) А .
2.Построить логическую схему по формуле (A B) C D .
3.Определить логическую функцию, реализуемую логической схемой
40