Презентация Тема 1.5

1.

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

2.

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

3.

Пример высказывания
Завтра будет идти дождь – это предложение
является высказыванием. О нем можно утверждать что
оно истинно, если завтра действительно будет идти
дождь, или же ложно, если завтра дождя не будет.
Классический пример утверждения, не являющимся
высказыванием таков:
Все, что написано в этом предложении, есть ложь.
Действительно, попытка определить истинное
значение
этого
«высказывания»
приводит
к
противоречию: если то, что написано, истинно, то это
противоречит смыслу слов в предложении. То же
противоречие возникает, если предположить, что оно
ложно.

4.

Запись высказывания
Говорят, что если высказывание истинно, то
его значение истинности равно 1, если ложно –
0.
Для удобства работы с высказываниями их
заменяют на буквы английского алфавита.
Пусть высказывание А будет означать на
улице идет дождь, а высказывание В – на улице
светит солнышко. Посмотрев через окно на
улицу, мы видим, что идет дождь. Значит
высказывание А – истинно(1), а высказывание В
– ложно(0), т.е. А=1, В=0.

5.

Простые и сложные высказывания
Высказывание называют простым (элементарным
атомарным), если оно рассматривается нами как
некое неделимое целое. Обычно к ним относятся
высказывания, не содержащие логических связок (А,
В, С, и т.п.).
Сложным называют высказывание, составленное из
простых с помощью логических связок(операций) (А˅В,
В˄Е,¬X~Y и т.п).
В логике над высказываниями производятся
следующие основные операции(логические связки):
отрицание, конъюнкция, дизъюнкция, импликация,
эквиваленция). Они рассматриваются как средство
вычисления
логического
значения
сложного
высказывания.

6.

Логические операции и приоритеты их выполнения
0. Скобки работают так же, как и в математике.
1. Инверсия(отрицание) – логическая связка «не».
2. Конъюнкция – логическое умножение.
3. Дизъюнкция – логическое сложение.
4. Импликация – логическое следование.
5.
Эквиваленция
–
логическое
тождество(равенство).
Логические операции обычно иллюстрируют
таблицей истинности – таблицы, описывающей
логическую функцию.
Логическая функция в данном случае означает
функцию, у которой значения переменных выражают
логическую истинность – «истина» или «ложь».

7.

Инверсия
А
0
1

8.

Конъюнкция
А
0
0
1
1
В
0
1
0
1

9.

Дизъюнкция
А
0
0
1
1
В
0
1
0
1

10.

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

11.

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

12.

Построить
таблицу
истинности,
описывающую
работу
логических
элементов, несложно при небольшом
количестве входных переменных. Если же
число переменных больше трех, то таблица
получается слишком большой. Так, при
наличии 4 переменных, количество наборов
в таблице будет равно 16, а уже при 6
переменных - 64! А еще нужно учитывать
скобки, приоритет и количество операций!
Очень легко совершить ошибку!

13.

Алгоритм построения таблиц истинности
1. Подсчитать n — число переменных в логическом выражении.
2. Подсчитать общее количество логических операций в выражении.
3. Установить последовательность выполнения логических операций
с учётом скобок и приоритетов.
4. Определить число столбцов в таблице: число переменных + число
операций.
5. Заполнить шапку таблицы, включив в неё переменные и операции в
соответствии с последовательностью, установленной в пункте 3.
6. Определить число строк в таблице (не считая шапки таблицы) по
формуле
m = 2n, где n — количество переменных.
7. Выписать наборы входных переменных с учётом того, что они
представляют собой целый ряд n-разрядных двоичных чисел от 0 до
2n–1.
8. Провести заполнение таблицы истинности по столбцам, выполняя
логические
операции
в
соответствии
с
установленной
последовательностью.

14.

Пример построения таблицы истинности
Построим таблицу истинности для логического выражения:
А V A & B.
В нем две переменные (n = 2), две операции, (A & B) и (А V A & B).
Причем, сначала выполняется конъюнкция - &, а затем – дизъюнкция - V .
Всего в таблице будет 4 столбца: число переменных + число операций.
Заполняем шапку таблицы, включая все переменные и операции.
Определим число строк в таблице (не считая шапки) - m = 22 = 4.
Выписываем наборы входных переменных с учетом того, что они
представляют собой целый ряд n-разрядных двоичных чисел от 0 до 2ⁿ -1
Проводим заполнение таблицы по столбцам, выполняя логические операции
в соответствии с установленной последовательностью.
A
B
A&B
AVA&B
0
0
0
0
0
1
0
0
1
0
0
1
1
1
1
1

15.

Пример построения таблицы истинности
Последний столбец (результат) совпал со столбцом A.
В этом случае говорят, что логическое выражение
А v A & B равносильно логической переменной A.
A
B
A&B
AVA&B
0
0
0
0
0
1
0
0
1
0
0
1
1
1
1
1

16.

Графический метод алгебры логики
Круги Эйлера
Позволяют наглядно представить множества и
отношения между ними, что упрощает понимание
логических операций и формулирование решений.
Некоторые особенности метода:
1. Каждое множество изображается кругом.
2. Изображаются
отношения
между
понятиями:
равнозначность,
перекрёщивание (пересечение), подчинение.
3. В сложной логической задаче иногда может
встречаться сразу несколько видов таких
схем.

17.

18.

Пример: даны два множества: A = {1, 2, 3,
4} и B = {3, 4, 5, 6}, нужно найти
объединение A и B (A ∪ B). Решение:
рисуют два круга, один для A, другой для
B, вписывают элементы множества A в
первый круг, а элементы множества B —
во второй. Элементы 3 и 4 входят в оба
множества, поэтому их закрашивают в
области пересечения кругов. Множество A
∪ B — это все элементы, находящиеся
внутри обоих кругов.

19.

Понятие множества
Множество в информатике —
это совокупность объектов
(элементов), которые
рассматриваются как единое
целое. Объекты,
составляющие множество,
называются его элементами.

20.

Свойства множеств:
1. Уникальность: каждый элемент
неповторим.
2. Неупорядоченность: у элементов
множества нет порядкового
номера.
3. Изменяемость: можно добавлять
во множество или удалять из него
элементы.

21.

Обозначение: множества обозначают прописными
буквами латинского алфавита (A, B, C, …), элементы
— строчными латинскими буквами.

22.

Виды
Множества бывают:
1. Конечные — содержат конечное число
элементов. Например, множество дней
недели — конечное.
2. Бесконечные — в них бесконечно много
элементов. Пример — множество
натуральных чисел.
3. Пустое — множество, не содержащее ни
одного элемента. Обозначается символом ∅.

23.

Реализация
Множества могут содержать неизменяемые объекты:
целые числа, числа с плавающей точкой, строки, кортежи.
Словари, списки и другие типы данных, которые могут
перезаписываться во время работы программы, не могут
быть частью множества.
Задание множества может быть:
1. Перечислением всех элементов — внутри фигурных
скобок перечисляются все объекты, составляющие
множество. Например, запись М = {1, 3, 5, 7, 9} означает, что
множество М состоит из чисел 1, 3, 5, 7 и 9.
2. С помощью характеристического свойства элементов —
такого свойства, которым обладает каждый элемент,
принадлежащий множеству, и не обладает ни один элемент,
который ему не принадлежит.

24.

Операции
Некоторые операции над множествами:
1. Пересечение — множество, содержащее
элементы, принадлежащие и множеству X, и
множеству Y. Обозначается знаком ∩.
2. Объединение — множество, содержащее все
элементы, принадлежащие хотя бы одному из
множеств X и Y. Обозначается знаком ∪.
3. Разность — множество, содержащее все
элементы множества X, но не принадлежащие
множеству Y. Математическая запись — X\Y.

25.

Применение
Множества полезны в разных задачах, например:
1. Удаление дубликатов — например, если нужно очистить
данные от повторяющихся номеров телефонов, можно
превратить список повторяющихся номеров во множество —
после этого все копии исчезнут.
2. Проверка наличия элемента — в отличие от списков, где
поиск элемента занимает время, пропорциональное размеру
списка, проверка наличия элемента в множестве происходит
за постоянное время.
3. Поиск общих элементов между коллекциями —
множества позволяют находить пересечения между разными
наборами данных, например, чтобы выявить общих клиентов
двух магазинов или общие ключевые слова двух документов.

26.

Мощность множества
Понятие «мощность множества»
(кардинальное число) имеет
разные значения в зависимости
от контекста. Оно может
относиться к математике или
программированию.

27.

В математике
Мощность множества
— это количество
элементов в данном
множестве.
Обозначается как |A|.

28.

Особенности:
1.
2.
3.
Конечные множества — мощность равна
количеству элементов. Например, если A =
{1, 2, 3, 4, 5}, то |A| = 5.
Бесконечные множества — мощность
бесконечна, если содержит бесконечное
число элементов (например, множество
натуральных чисел).
Пустое множество — мощность равна 0.

29.

Свойства:
1. Два конечных множества
равномощны, если они состоят из
одинакового числа элементов.
2. Для бесконечных множеств
мощность может совпадать с
мощностью своего собственного (не
совпадающего с исходным
множеством) подмножества.

30.

В программировании
В программировании понятие мощности
множества может иметь ограничения,
например:
1.Для конечных множеств (которые могут
храниться в ограниченной памяти ЭВМ)
мощность сводится к числу элементов.
2.В Python можно создать функцию, которая
возвращает мощность заданного
итерируемого объекта.

31.

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

32.

1. Объединение множеств. Это множество, состоящее
из элементов, принадлежащих хотя бы одному из
объединяемых множеств. Для объединения множеств
используется символ ∪. Например, если A={1,2,3,4,5},
B={3,4,7,8,9}, то A∪B={1,2,3,4,5,7,8,9}.

33.

2. Пересечение множеств. Это множество, состоящее
из элементов, принадлежащих одновременно каждому
из пересекающихся множеств. Для пересечения
множеств используется символ ∩. Например, если
A={1,2,3,4,5}, B={3,4,7,8,9}, то A∩B={3,4}.

34.

3. Разность множеств. Это множество, в
которое входят только элементы первого
множества, не входящие во второе множество.
Для разности множеств используется символ ∖.
Например, если A={1,2,3,4,5}, B={3,4,7,8,9}, то
A∖B={1,2,5}.

35.

4. Симметричная разность множеств.
Это множество, включающее все
элементы исходных множеств, не
принадлежащие одновременно обоим
исходным множествам.
5.
Дополнение
множества.
Это
множество всех элементов, в нём не
содержащихся.
Для
операции
дополнения множества используется
символ ¬.