Логические операции и выражения

Логические величины – это понятия, выраженные словами ИСТИНА или ЛОЖЬ. Следовательно, истинность высказываний выражается через логические величины.

Логические константы: ИСТИНА или ЛОЖЬ.

Логическая переменная – это символическое обозначение логической величины. Например, если известно, что А, В, С – это логические переменные, то они принимают значение только ИСТИНА или ЛОЖЬ.

Логическое выражение – простое или сложное высказывание. Сложное высказывание строится из простых с помощью логических операций.

Логические операции

Конъюнкция (логическое умножение) в русском языке выражается союзом «И». Конъюнкция обозначается знаком & или . Это двухместная операция; записывается в виде А В. Значение такого выражения будет ложно, если значение хотя бы одного операнда ложно.

Дизъюнкция (логическое сложение) в русском языке выражается союзом «Или». Дизъюнкция обозначается знаком . Это двухместная операция, записывается в виде А В. Значение такого выражения будет истинным, если значение хотя бы одного операнда истинно.

Отрицание в русском языке выражается частицей «НЕ». Это унарная (одноместная) операция, которая записывается в виде ⌐ А или .

Импликация (условное высказывание) в русском языке выражается союзами «Если…то»; «Когда…тогда»; «Коль скоро…то» и т.п. Импликация обозначается знаком →. Это двухместная операция, записывается в виде А → В.

Эквивалентность в русском языке выражается союзами «Если и только если»; «Тогда и только тогда, когда». Эквивалентность обозначается знаком ↔.

Приведем таблицы истинности для рассмотренных логических операций.

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 B) → B	A B	((C B) → B) (A B)	F
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

Ответ: Формула является тождественно истинной.

Логические схемы

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

Дизъюнкция	Конъюнкция	Отрицание

Эти схемы называются вентилями.

Алгоритм построения логических схем следующий.

1. Определите число логических переменных.

2. Определите количество базовых логических операций и их порядок.

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

4. Соедините вентили в порядке выполнения логических операций.

Пример 3.3. Нарисовать логическую схему выражения А В С.

Количество логических переменных равно 3. Количество базовых логических операций равно 2. Порядок выполнения операций в соответствии с приоритетом: сначала выполняется конъюнкция , а затем дизъюнкция .

Пример 3.4. Вычислить значение выражения  с помощью логической схемы. А = 0; В = 1; С = 1; D = 0.

Количество логических переменных равно 4. Количество базовых логических операций равно 4. Порядок выполнения операций: операция дизъюнкции В ˅ С, затем первая и вторая конъюнкции, последняя операция – отрицание.

Ответ: Значение выражения равно 1.

Пример3.5. Дана логическая схема. Построить соответствующее ей логическое выражение.

Строим таблицу входов и выходов каждого вентиля в соответствии с нумерацией.

 

Вентиль	Вход	Выход
1	А, В	А В
2	В, С	В С
3	А В; В С	(А В) (В С)
4	(А В) (В С)

Ответ: логическая схема реализует функцию .

3.4. Задания для самостоятельного выполнения

Указания к выполнению задания

1. Прочитайте теоретический раздел и разберите примеры 3.1–3.5.

2. Отчет должен содержать условие задачи. Таблицы и схемы должны быть построены аккуратно с использованием линейки и карандаша. Неаккуратно оформленные задания приниматься не будут. Решение каждой задачи должно содержать необходимые пояснения.

 

Вариант 1

1. Построить таблицу истинности для  формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 2

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 3

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 4

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 5

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 6

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 7

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 8

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 9

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 10

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле

3. Определить логическую функцию, реализуемую логической схемой

Вариант 11

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 12

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 13

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 14

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 15

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 16

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 17

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 18

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 19

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 20

1. Построить таблицу истинности и для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 21

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 22

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 23

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 24

1. Построить таблицу истинности для формулы .

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

Вариант 25

1. Построить таблицу истинности для формулы

2. Построить логическую схему по формуле .

3. Определить логическую функцию, реализуемую логической схемой

 

практическое занятие 4.
Алгоритмизация

Цель занятия – научиться читать блок-схемы простых алгоритмов.

4.1. Определение алгоритма.
Основные алгоритмические конструкции

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

Графические обозначения блоков, которые используются в блок-схеме, стандартизованы. Некоторые из часто используемых блоков приведены в табл. 4.1.

Таблица 4.1

Изображение основных блоков на блок-схеме

Обозначение блока	Пояснение
	Процесс (вычислительное действие, реализованное операцией присваивания)
	Решение (проверка условия, реализующая условный переход)
	Начало, конец алгоритма
	Ввод исходных данных, вывод результатов

Основные алгоритмические конструкции – следование, ветвление и цикл.

Алгоритм, в котором действия выполняются последовательно, одно за другим, называется линейным (рис. 4.1).

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

Рис. 4.1. Блок-схема и пример линейного алгоритма

Запись на псевдокоде линейного алгоритма
Действие 1 Действие 2	a = 5; i = 1; S = a * (i + 1)

Если условие выполняется, то выполнение алгоритма происходит по ветке «да», если условие не выполняется, то выполнение алгоритма происходит по ветке «нет» (рис. 4.2). Ветвление может быть неполным, тогда по выходу «Нет» никакие действия не выполняются.

Рис. 4.2. Блок-схема и пример разветвляющегося алгоритма

Запись на псевдокоде разветвляющегося алгоритма
Полное ветвление		Неполное ветвление
Если условие То Действия 1 Иначе Действия 2 Все если	Если (a>0) То а=а-1 Иначе а=а+1 Все если	Если (a>0) То а=а-1 Все если

Алгоритм, при выполнении которого отдельные команды или несколько команд выполняются неоднократно, называют циклическим. Существует несколько видов циклов.

1. Цикл с предусловием, или цикл «пока». Цикл работает следующим образом. Сначала проверяется условие. Если оно истинно, то выполняется последовательность команд, которая идет по ветке «да». После выполнения этих действий алгоритм вновь возвращается на проверку условия. Если на каком-либо шаге оно станет ложным, то выполняются те действия, которые записаны по ветке «нет». Цикл заканчивается. Блок-схема такого цикла показана на рис. 4.3.

Рис. 4.3. Блок-схема и пример цикла с предусловием

Запись на псевдокоде цикла с предусловием
нц Пока условие повторять Серия действий кц	нц Пока (a<5)повторять b=b-k кц

2. Цикл с постусловием (или цикл «до») работает следующим образом. Сначала выполняются действия, которые стоят перед проверкой условия. Затем проверяется условие выхода из цикла. Если условие «ложно», то серия команд опять выполняется. Выполнение цикла продолжается до тех пор, пока условие не станет истинным. Тогда выполняются те действия, которые стоят по ветке «да». Блок-схема такого цикла показана на рис. 4.4.

Рис. 4.4. Блок-схема и пример цикла с постусловием

Запись на псевдокоде цикла с постусловием
нц До Серия действий Пока (условие) кц	нц До b=b-k Пока(a<5) кц

 

Чтение алгоритма

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

Пример 4.1. Определите значение переменной c после выполнения фрагмента алгоритма (рис. 4.6).

b=0; c=0; нц Пока (b=11) повторять c=c+b; b=b+1; кц

Рис. 4.6. Блок-схема и псевдокод примера 4.1

Составим таблицу выполнения алгоритма (табл. 4.2).

Таблица 4.2

c= с +b	b=b + 1	b = 11?	c= с +b	b=b + 1	b = 11?
0	0	0 = 11? Нет	10 + 5 = 15	5 + 1 = 6	6 = 11? Нет
0 + 0 = 0	0 + 1 = 1	1 = 11? Нет	15 + 6 = 21	6 + 1 = 7	7 = 11? Нет
0 + 1 = 1	1 + 1 = 2	2 = 11? Нет	21 + 7 = 28	7 + 1 = 8	8 = 11? Нет
1 + 2 = 3	2 + 1 = 3	3 = 11? Нет	28 + 8 = 36	8 + 1 = 9	9 = 11? Нет
3 + 3 = 6	3 + 1 = 4	4 = 11? Нет	36 + 9 = 45	9 + 1 = 10	10 = 11? Нет
6 + 4 = 10	4 + 1 = 5	5 = 11? Нет	45 + 10 = 55	10 + 1 = 11	11 = 11? Да

Ответ: с = 55

Пример 4.2. Определите значение переменной m после выполнения фрагмента алгоритма, изображенного на рис. 4.7.

m=54; n=16; нц Пока (m=n) повторять   Если (m>n)      То n=n-m   Иначе m=m-n кц

Рис. 4.7. Блок-схема и псевдокод примера 4.2

Составим таблицу выполнения алгоритма (табл. 4.3).

Таблица 4.3

m = n?	m > n?	m = m – n	n = n – m
		54	16
54 = 17? Нет	54 > 16? Да	54 – 16 = 38
38 = 17? Нет	38 > 16? Да	38 – 16 = 22
22 = 17? Нет	22 > 16? Да	22 – 16 = 6
6 = 17? Нет	6 > 16? Нет		16 – 6 = 10
6 = 10? Нет	6 > 10? Нет		10 – 6 = 4
6 = 4? Нет	6 > 4? Да	6 – 4 = 2
2 = 4? Нет	2 > 4? Нет		4 – 2 = 2
2 = 2? Да

Ответ: m = 2

4.3. Задания для самостоятельного выполнения

Указания к выполнению задания

1. Прочитайте теоретический раздел и разберите примеры 4.1–4.2.

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

3. Неаккуратно оформленные задания приниматься не будут.

 

Вариант 1	Вариант 2
Дано n = 10. Вычислить n -е значение переменной b.	Дано n = 12. Вычислить n -ое значение переменной d.
Вариант 3	Вариант 4
Дано n = 8. Вычислить n -е значение переменной z.	Дано n = 12. Вычислить n -ое значение переменной c.
Вариант 5	Вариант 6
Дано n = 8. Вычислить n -е значение переменных z и w.	Дано n = 10. Вычислить n -ое значение переменных c и d.
Вариант 7	Вариант 8
Дано n = 12. Вычислить n -е значение переменной с.	Дано n = 14. Вычислить n -ое значение переменной y2  при х = 4.
Вариант 9	Вариант 10
Дано n = 10. Вычислить n -е значение переменной х.	Дано n = 12. Вычислить n -ое значение переменной y  при х = 6.
Вариант 11	Вариант 12
Дано n = 10. Вычислить n-е значение переменных х и y.	Дано n = 11. Вычислить n -ое значение переменной с.
Вариант 13	Вариант 14
Дано n = 11. Вычислить n -е значение переменной z.	Дано n = 10. Вычислить n -ое значение переменной y.
Вариант 15	Вариант 16
Дано n = 5. Определить значение целочисленной переменной S после выполнения алгоритма.	Определить значение целочисленной переменной S после выполнения алгоритма.
Вариант 17	Вариант 18
Определить значение целочисленной переменной S после выполнения алгоритма.	Определить значение целочисленной переменной S после выполнения алгоритма.
Вариант 19	Вариант 20
Определить значение целочисленной переменной S после выполнения алгоритма.	Определить значение целочисленной переменной S после выполнения алгоритма.
Вариант 21	Вариант 22
Определить значение целочисленной переменной S после выполнения алгоритма.	Определить значение целочисленной переменной S после выполнения алгоритма.
Вариант 23	Вариант 24
Определить значение целочисленной переменной S после выполнения алгоритма.	Определить значение целочисленной переменной S после выполнения алгоритма.

Библиографический список

1. Абрамов, С.А. Задачи по программированию / С.А. Абрамов, Г.Г. Гнездилова, Е.Н. Капустина. – М.: Наука, гл. ред. физ.-мат. лит., 1988. – 204 с.

2. Гагарина, Л.Г. Алгоритмы и структуры данных: учеб. пос. / Л.Г. Гагарина, В.Д. Колдаев. – М.: Финансы и статистика: ИНФРА-М, 2009. – 302 с.

3. Гуденко, Д.А, Сборник задач по программированию / Д.А. Гуденко, Д.В. Петроченко. – СПб.: Питер, 2003. – 475 с.

4. Дергачева, Л.М. Решение задач по теме «Измерение информации» / Л.М. Дергачева //Информатика и образование. – 2010. – №7. – С. 49–52.

5. Могилев, А.В. Практикум по информатике: учеб. пособие для студ. высш. учеб. заведений / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; под ред. Е.К. Хенера. – 5-е изд. – М.: Издательский центр «Академия», 2009. – 608 с.

Оглавление

Введение. 3

практическое занятие 1. Системы счисления

1.1. Основные понятия и определения. 4

1.2. Перевод чисел из одной системы счисления в другую.. 5

1.3. Арифметика в позиционных системах счисления. 9

1.4. Задания для самостоятельного выполнения. 12

практическое занятие 2. Измерение информации

2.1. Способы измерения информации. 18

2.2. Измерение графической информации. 19

2.3. Задания для самостоятельного выполнения. 20

практическое занятие 3. логические основы ЭВМ

3.1. Высказывание. 30

3.2. Логические операции и выражения. 30

3.3. Логические схемы.. 32

3.4. Задания для самостоятельного выполнения. 33

практическое занятие 4. Алгоритмизация

4.1. Определение алгоритма. Основные алгоритмические конструкции. 40

4.2. Чтение алгоритма. 42

4.3. Задания для самостоятельного выполнения. 44

Библиографический список.. 49