4.55M

Category:

informatics

Лекция (1)

1.

Элементы комбинаторики,
теории множеств и
математической логики
19 октября 2024 г.

2.

КОМБИНАТОРИКА
Комбинаторика - это раздел математики, в
котором изучаются вопросы о том, сколько
различных комбинаций, подчиненных тем
или иным условиям, можно составить из
заданных объектов.

Самый простой метод решения
комбинаторных задач – перебор
всех возможных вариантов
1. Перечислить ВСЕ виды:
1) треугольников,
2) четырехугольников.
Ответ:1) 6 2) 5
2. В магазине продают бейсболки трех
цветов: синие, красные и черные.
Ваня и Андрей покупают себе по
одной. Сколько существует различных
вариантов покупки?
Ответ: 9 вариантов.

4.

Перестановка
Имеется три овоща: свекла, морковь,
баклажан. Сколькими способами можно
их расположить на столе?

5.

Перестановка
Имеется три овоща: свекла, морковь,
баклажан. Сколькими способами можно
их расположить на столе?

6.

ФОРМУЛА ПЕРЕСТАНОВОК
Комбинации из n-элементов, отличающихся
друг от друга только порядком расположения
в них элементов, называются
перестановками из n элементов.
Перестановки из n элементов обозначают Pn и
вычисляют по формуле: Pn=n!
n!=1*2*3*4*…*n (n факториал)

7.

Примеры
1. Сколькими способами можно
расставить на полке 6 книг?

8.

Примеры
1. Сколькими способами можно
расставить на полке 6 книг?
2. … а если 10 книг?

9.

3. Квартет
Проказница Мартышка
Осёл,
Козёл,
Да косолапый Мишка
Затеяли играть квартет

10.

Что такое сочетание?
Сочетаниями из n элементов по m в
каждом называются такие соединения,
которые отличаются друг от друга хотя бы
одним элементом.
Обозначают:
С
m
n
n!
C
m! (n m)!
m
n

11.

Что такое сочетание?
Сочетание из n по m – это неупорядоченное
множество, состоящее из m элементов,
которые выбраны из n элементов.
Смысловая нагрузка:
«Сколькими способами можно выбрать m
объектов их n?
0≤m≤n

12.

ПРИМЕР
• Сколько комбинаций чисел может
составить игрок, играющий в
лотереи «5 из 36», «6 из 45», «7 из
49»?

13.

Вопрос 2: Сколькими способами
можно выбрать
• а) один фрукт, б) два
фрукта, в) три фрукта?
Решение.
• а) Один фрукт можно
выбрать, очевидно,
тремя способами –
взять либо яблоко, либо
грушу, либо банан.
Формальный подсчёт
проводится по формуле
количества сочетаний
(комбинаций):

14.

Размещения
Размещением из n элементов по m
(m ≤ n) называется любое
множество, состоящее из любых m
элементов, взятых в определенном
порядке из данных n элементов.
Количество всех размещений из n элементов по m
обозначают:
n!
(n m)!
m
n

15.

Размещение
• Есть три фрукта –
груша, яблоко,
банан. Сколькими
способами можно
раздать по одному
фрукту Даше и
Наташе?

16.

Вопрос 3:
• Сколькими способами можно раздать по одному фрукту Даше
и Наташе?
• Для того чтобы раздать два фрукта, сначала нужно их выбрать.
Согласно предыдущему вопросу, сделать это можно 3
способами: 1) яблоко и груша;
2) яблоко и банан;
3) груша и банан.
• Но комбинаций сейчас будет в два раза больше. Например,
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко – Наташе. И
такая перестановка возможна для каждой пары фруктов.
• В данном случае работает формула количества размещений:

17.

• Для того чтобы раздать два фрукта, сначала нужно
их выбрать. Согласно предыдущему вопросу,
сделать это можно 3 способами: 1) яблоко и груша;
2) яблоко и банан;
3) груша и банан.
• Но комбинаций сейчас будет в два раза больше.
Например,
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко –
Наташе. И такая перестановка возможна для
каждой пары фруктов.
• В данном случае работает формула количества
размещений

18.

КАК ВЫБРАТЬ ФОРМУЛУ?

19.

ЗАДАЧА
• Сколько разных трехзначных чисел
можно записать с помощью цифр 1, 2,
3, 4, 5 при условии, что ни одна из цифр
не повторяется?
РЕШЕНИЕ
• Для числа существенным является порядок
записи цифр.

20.

ЗАДАЧА
• Сколько разных цепочек длинной 3 можно
записать из букв А, Б, В, Г, Д, Е при
условии, что буквы могут повторяться?
РЕШЕНИЕ
• На первом месте можно записать любую из данных
букв – всего 6 вариантов.
• Так как буквы могут повторяться, то на втором
месте можно так же записать одну из 6 букв.
6*6=36 вариантов.
• Так же на третьем месте – одна из 6 букв:

21.

ЗАДАЧА
• Необходимо выделить трех их пяти
учеников на дежурство в столовую.
Сколькими способами это можно
сделать?
РЕШЕНИЕ
• При выборе учеников для дежурства порядок
выбора несущественен. Нет разницы, в каком
порядке учитель вызовет дежурных: «Петров,
Иванов, Сидоров» или «Сидоров, Петров,
Иванов». По сути это одна и та же тройка
дежурных.

22.

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

23.

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

24.

Термин «логика» происходит от древнегреческого
logos – «слово, мысль, понятие, рассуждение, закон».
Логика – это наука о законах и формах
мышления.
Она
изучает
абстрактное
мышление
как
средство
познания
объективного мира.

25.

Основным объектом в логике является
высказывание.
Высказывание – это повествовательное предложение,
о котором можно сказать истинно оно или ложно.
Например,
предложение "6 — четное число" - высказывание, т.к оно
истинное.
Предложение "Рим — столица Франции«- высказывание,
т.к. оно ложное.
Высказывания могут выражаться с помощью математических,
физических, химических и прочих знаков. Например: 5>3,
H2O+SO2=H2SO4.

26.

27.

Логические основы компьютеров
27
Высказывание или нет?
1. Сейчас идет дождь.
2. Жирафы летят на север.
3. История – интересный предмет.
4. У квадрата – 10 сторон и все разные.
5. Красиво!
6. В городе N живут 2 миллиона человек.
7. Который час?
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

28.

Не всякое предложение является
логическим высказыванием.
Например, предложения "ученик
десятого класса" и "информатика —
интересный предмет". не являются
высказываниями.
Вопросительные и восклицательные
предложения также не являются
высказываниями, т.к. в них ничего не
утверждается и не отрицается.
Например:
1. Уходя, гасите свет!
2. Кто хочет быть счастливым?

29.

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

30.

Примеры:
1. Москва – столица России
2. Студент математического факультета
педагогического университета
3. Треугольник АВС подобен треугольнику А’В’С’
4. Луна есть спутник Марса
5. Кислород – газ
6. Каша – вкусное блюдо
7. Математика – интересный предмет
8. Железо тяжелее свинца
9. Треугольник называется равносторонним, если
все его стороны равны
10.Сегодня плохая погода
11.Река Ангара впадает в озеро Байкал

31.

Высказывание
простое
составное
Высказывание называется составным,
Высказывание называется простым,
если оно состоит из простых высказываний,
если никакая его часть сама
соединенных логическими связками:
не является высказыванием.
И, ИЛИ, частицей НЕ

32.

Логические основы компьютеров
32
Обозначение высказываний
A – Сейчас идет дождь.
B – Форточка открыта.
}
простые высказывания
(элементарные)
! Любое высказывание может быть ложно (0)
или истинно (1).
Составные высказывания строятся из простых с
помощью логических связок (операций) «и», «или»,
«не», «если … то», «тогда и только тогда» и др.
AиB
Сейчас идет дождь и открыта форточка.
A или не B
Сейчас идет дождь или форточка закрыта.
если A, то B
Если сейчас идет дождь, то форточка открыта.
A тогда и только
тогда, когда B
Дождь идет тогда и только тогда, когда открыта
форточка.
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

33.

Начальный раздел математической логики называют
алгеброй логики или Булевой алгеброй.
Алгебра логики возникла в
середине ХIХ века в трудах
английского математика
Джорджа Буля.
Описал теорию логики и
основу
функционирования
цифровых компьютеров в своей
работе "Исследование законов
мышления", 1854.

34.

Простые высказывания обозначают
заглавными латинскими буквами
A, B, C…X, Y, Z и называют
логическими переменными
Значения высказываний
ИСТИНА или ЛОЖЬ обозначают
соответственно цифрами 1 и 0
и называют логическими величинами
Составные высказывания называются
логическими выражениями и включают
в себя логические переменные,
операции логики и скобки для изменения
порядка действий операций

35.

Примеры:
Рассмотрим следующие
высказывания:
1. A = (7 > 3)
2. B = (7 = 3)
3. C = (7 ≠ 3)
4. D = (B ۸ C) = ((7 = 3) ۸ (7 ≠ 3))
На языке алгебры логики эти
высказывания можно записать
так:
A = ИСТИНА = 1
B = ЛОЖЬ = 0
C = ИСТИНА = 1
D = ЛОЖЬ = 0

36.

Основные логические
операции
Три базовых логических операций –
инверсия, конъюнкция,
дизъюнкция и дополнительные –
импликация и эквиваленция
(двойная импликация).

37.

Логические основы компьютеров
37
Операция НЕ (инверсия)
Если высказывание A истинно, то «не А» ложно, и
наоборот.
A A
А
не А
0
1
1
0
также ,
not A,
,
таблица
истинности
операции НЕ
Таблица истинности логического выражения Х – это
таблица, где в левой части записываются все
возможные комбинации значений исходных данных,
а в правой – значение выражения Х для каждой
комбинации.
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

38.

Примеры:
Сформулируйте отрицания следующих
высказываний и укажите значения истинности
полученных отрицаний:
1. Волга впадает в Каспийское море.
2. Число 28 не делится на число 7.
3. 6 > 3.
4. 4 ≤ 5.
Ответ: истинными высказываниями являются: 2

39.

Логические основы компьютеров
39
Операция И (логическое умножение, конъюнкция)
A
B
АиB
0
0
1
1
0
1
0
1
0
0
0
1
также: A·B, A B,
A and B , A & B
конъюнкция – от лат. conjunctio — соединение
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

40.

Примеры:
Определить значения истинности следующих
высказываний:
1. Санкт - Петербург расположен на Неве и 2 + 3 = 5
2. 7 – простое число и 9 – простое число
3. 2 * 2 = 4 и 2 * 2 ≤ 5 и 2 * 2 ≥ 4
4. Москва – столица России и Екатеринбург –
столица Сибири
5. Книга – источник информации и 5 не больше 8
6. Девочки обычно любят играть в куклы и Не
любая машина - автомобиль
7. Все гуси – птицы и Все игрушки - машины
Ответ: истинными высказываниями являются: 1, 3, 5, 6

41.

Логические основы компьютеров
41
Операция ИЛИ (логическое сложение, дизъюнкция)
A
B
А или B
0
0
1
1
0
1
0
1
0
1
1
1
также: A+B, A B,
A or B, A || B
дизъюнкция – от лат. disjunctio — разъединение
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

42.

Примеры:
Определить значения истинности следующих
высказываний:
1. 7 – простое число или 9 – простое число
2. Число 2 четное или Это простое число
3. 2 * 2 = 4 или Белые медведи живут в Африке
4. Каша – вкусное блюдо или Математика –
интересный предмет
5. Луна – спутник Марса или Луна – спутник
Земли
6. Сегодня плохая погода или Кислород – вода
7. Microsoft Word – текстовый редактор или Paint
– графический редактор
Ответ: истинными высказываниями являются: 1, 2, 3, 5, 7

43.

Логические основы компьютеров
43
Логическое операция ИМПЛИКАЦИЯ
A
0
0
1
1
B
0
1
0
1
А =>B
1
1
0
1
также: A=>B,
Ставит в соответствие каждым двум
простым высказываниям составное
высказывание, являющееся ложным
тогда и только тогда, когда условие
(первое высказывание) истинно, а
следствие (второе высказывание)
ложно.
Соответствует обороту ЕСЛИ…, ТО…
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

44.

Примеры:
Определить значения истинности следующих
высказываний:
1. Если 12 делится на 6, то 12 делится на 3.
2. Если 11 делится на 6, то 11 делится на 3.
3. Если 15 делится на 6, то 15 делится на 3.
4. Если 15 делится на 3, то 15 делится на 6.
5. Если Саратов расположен на Неве, то белые
медведи обитают в Африке.
Ответ: истинными высказываниями являются: 1, 2, 3, 5

45.

Логические основы компьютеров
45
Логическое операция ЭКВИВАЛЕНЦИЯ
A
0
0
1
1
B
0
1
0
1
А ↔B
1
0
0
1
также: A ↔ B,
Ставит в соответствие каждым
двум простым высказываниям
составное высказывание,
являющееся истинным тогда и
только тогда, когда оба исходных
высказывания одновременно
истинны или одновременно
ложны.
Соответствует обороту ТОГДА И ТОЛЬКО
ТОГДА; В ТОМ И ТОЛЬКО В ТОМ СЛУЧАЕ
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

46.

Примеры:
Определить значения истинности следующих
высказываний:
1. 12 делится на 6 тогда и только тогда, когда 12
делится на 3.
2. 11 делится на 6 тогда и только тогда, когда 11
делится на 3.
3. 15 делится на 6 тогда и только тогда, когда 15
делится на 3.
4. 15 делится на 5 тогда и только тогда, когда 15
делится на 4.
Ответ: истинными высказываниями являются: 1, 2

47.

Объединенная таблица истинности
А ۸ В А ۷ В А => В А ↔ В
А
В
Ā
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
При вычислении значения логического выражения (формулы) логические
операции вычисляются в определенном порядке, согласно их приоритету:
1. инверсия,
2. конъюнкция,
3. дизъюнкция,
4. импликация и эквивалентность.

48.

Логические основы компьютеров
48
Задачи
В таблице приведены запросы к поисковому серверу.
Расположите номера запросов в порядке возрастания
количества страниц, которые найдет поисковый сервер по
каждому запросу. Для обозначения логической операции
«ИЛИ» в запросе используется символ |, а для логической
операции «И» – &.
1) принтеры & сканеры & продажа
2) принтеры & продажа
3) принтеры | продажа
4) принтеры | сканеры | продажа
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

49.

Примеры:

50.

Логические основы компьютеров
50
Логика и компьютер
Двоичное кодирование – все виды
информации кодируются с помощью 0 и 1.
Задача – разработать оптимальные правила
обработки таких данных.
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

51.

Логические основы компьютеров
51
Логика и компьютер
Почему «логика»?
Результат выполнения операции можно
представить как истинность (1) или
ложность (0) некоторого высказывания.
Джордж Буль разработал основы алгебры,
в которой используются только 0 и 1
(алгебра логики, булева алгебра).
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

52.

Логические элементы ПК
В электронных устройствах компьютера двоичные единицы
чаще всего кодируются более высоким уровнем
напряжения, чем двоичные нули (или наоборот),
например:

53.

Логические элементы ПК
Логический элемент компьютера — это часть
электронной логической схемы, которая
реализует элементарную логическую
функцию.
Логическими элементами компьютеров
являются электронные схемы И, ИЛИ, НЕ,
И—НЕ, ИЛИ—НЕ и другие (называемые также
вентилями).

54.

Логические элементы ПК

55.

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

56.

Коньюнктор
2. Логический элемент «И» (конъюнктор) реализует конъюнкцию
двух или более логических значений.
X
&
X&Y
Y
X
Y
X&Y
0
0
0
0
1
0
1
0
0
1
1
1

57.

Логические основы компьютеров
57
Операция И
Высказывание «A и B» истинно тогда и только тогда,
когда А и B истинны одновременно.
AиB
A
B
220 В
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

58.

Дизъюнктор
3. Логический элемент «ИЛИ» (дизъюнктор) реализует дизъюнкцию
двух или более логических значений.
X
1
X+Y
Y
X
Y
X+Y
0
0
0
0
1
1
1
0
1
1
1
1

59.

Логические основы компьютеров
59
Операция ИЛИ (логическое сложение, дизъюнкция)
Высказывание «A или B» истинно тогда, когда
истинно А или B, или оба вместе.
A или B
A
B
220 В
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

60.

Логические элементы ПК
Логический элемент «И-НЕ» реализует отрицание конъюнкции двух
или более логических значений.
X
&
X&Y
Y
X
Y
X&Y
0
0
1
0
1
1
1
0
1
1
1
0

61.

Логические элементы ПК
Логический элемент «ИЛИ-НЕ» реализует отрицание дизъюнкции
двух или более логических значений.
X
1
X+Y
Y
X
Y
X+Y
0
0
1
0
1
0
1
0
0
1
1
0

62.

Логические элементы ПК
Задание №1: Записать логическую функцию, которую реализует
следующая схема и таблицу истинности .
X
X
X & (Y+Z)
&
F=X & (Y + Z)
Y
1
Z
Y+Z

63.

Логические элементы ПК
Таблица истинности:
X
Y
Z
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
X
Y+Z
F

64.

А
В
&
F1
1
F2
V
F3
A&BvB
Функциональная схема логического
устройства
Структурная формула
ЛУ
Зная функциональную схему, можно составить данного
ЛУ.
Анализирструктурную формулу уя структурную формулу,
можно создать функциональную схему и понять, как 64
работает данное ЛУ.

65.

A
B
P
S
Так как все многообразие операций в ПК сводится
к сложению двоичных чисел,
то главной частью процессора (АЛУ) является сумматор.
65

66.

Рассмотрим сложение одноразрядных двоичных чисел:
Слагаемые Перенос Сумма
А
В
Р
S
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0

67.

Логические основы компьютеров
67
Триггер (англ. trigger – защёлка)
Триггер – это логическая схема, способная хранить
1 бит информации (1 или 0). Строится на 2-х
элементах ИЛИ-НЕ или на 2-х элементах И-НЕ.
set, установка
S
1
1
R
вспомогательный
выход
Q
S R Q Q
режим
0 0 Q Q
хранение
обратные связи
0 1
0
1
сброс
Q
1 0
1 1
1
0
0
0
установка 1
основной
выход
запрещен
reset, сброс
К. Поляков, 2007-2012
http://kpolyakov.narod.ru

68.

Несколько триггеров можно
объединить в группы - регистры
И использовать в качестве
запоминающих устройств (ЗУ).
68
Если в регистр входит N
триггеров, то при таком ЗУ
можно запоминать N-разрядные
двоичные слова.
ОЗУ ЭВМ часто конструируется
в виде набора регистров.
Один регистр образует одну
ячейку памяти, каждая из
которых имеет свой номер
Таким образом, ЭВМ
состоит из огромного числа
Отдельных логических элементов,
образующих все ее узлы и память.
т
т
т
т

69.

Логические элементы ПК
Задание №2: Построить схему реализующую логическую
функцию
A
&
F=(A + B)&(A & B)
A&B
B
F1=A & B
A&B
&
1
A+B
F=(A + B)&(A & B)

70.

Логические элементы ПК
Таблица истинности:
A
B
0
0
0
1
1
0
1
1
A+B
A&B
A&B
F
Домашнее задание: § 3.3, заполнить таблицы истинности.

71.

Логические элементы компьютера
1
0
0
1
1
1
0
0
0
&
0
0
1
1
1
1
1
0
0
1
1
0
0
1

72.

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

73.

F=X &(Y+Z)
&
1

74.

Триггер
1
1

75.

Триггер
1
1

76.

Триггер
1
1

77.

Полусумматор
Cуммирование одноразрядных двоичных чисел без
учета переноса из младшего разряда
&
1
&

78.

Одноразрядный двоичный сумматор
ai
bi
Pi
pi
Ci

79.

A0
A1
В0
В1
A2
В2
С0
С1
А=(а0+ а1+ а1)
Результат А+В=С
А=(а0+ а1+ а1)
В=(в0+ в1+ в1)
С=(с0+ с1+ с1)
С2 С3

80.

Задача: в звене 12 человек, требуется выбрать
звеньевого, санитара и командира.
Сколькими способами это можно сделать?
Решение:

81.

Решение задач по теме «Перестановки»
1.Курьер должен разнести пакеты в 7 различных учреждений.
Сколько маршрутов он может выбрать?
2.Сколькими способами 9 человек могут встать в очередь в
театральную кассу?
3.Ольга помнит, что телефон подруги оканчивается цифрами
5,7,8, но забыла, в каком порядке эти цифры следуют. Укажите
наибольшее число вариантов, которые ей придётся
перебрать, чтобы дозвониться подруге.
4.Сколько шестизначных чисел, в записи которых каждая цифра
используется только один раз, можно составить из цифр:
а)1,2,5,6,7,8;
б)0,2,5,6,7,8?
5.Сколько существует перестановок букв слова «конус», в
котором буквы «к», «о», «н» стоят рядом в указанном
порядке?

82.

Задачи по теме «Размещения»
1
Из 30 участников собрания надо выбрать председателя и
секретаря. Сколькими способами это можно сделать?
2
На станции 7 запасных путей Сколькими способами можно
расставить на них 4 поезда?
3
На странице альбома 6 свободных мест для фотографий.
Сколькими способами можно вложить в свободные места:
а) 2 фотографии; б) 4 фотографии; в) 6 фотографий?
4
Сколько четырёхзначных чисел, в которых нет
одинаковых цифр, можно составить из цифр: а) 1, 3, 5, 7, 9,;
б) 0, 2. 4, 6, 8?
5
Сколько существует семизначных телефонных номеров, в
которых все цифры различные и первая цифра отлична от
нуля?

83.

а) В конкурсе участвуют 8 школьников. Сколькими способами
могут быть распределены места между ними? (Решение. 8! =
40 320).
б) Сколькими способами можно составить маршрут
путешествия, проходящего через 7 городов? (Решение. 7! = 5
040).
в) Сколькими способами можно расставить на полке 10
различных книг? (Решение. 10! = 3 628 800).
доп. № 619 ( представить, что всего 4 книги одного автора;
подумать,сколькими способами можно их расставить; затем
считать эти 4 книги одной книгой и добавить к ним оставшиеся
книги; продолжить аналогичные рассуждения).
Сколькими способами можно расставить на полке 10 книг, из
которых 4 книги одного автора, а остальные – разных авторов,
так, чобы книги одного автора стояли рядом? (Решение. 7! * 4!).

English Русский Rules