Элементы комбинаторики Теория множеств Математическая логика

ГПОУ «Ленинск-Кузнецкий политехнический техникум»

Информатика

Элементы комбинаторики

Теория множеств

Математическая логика

Преподаватель Щеглова Алена Александровна

Теоретическое занятие

для студентов I курса

Ленинск-Кузнецкий, 2024 г

Высказывания

Высказывание  это повествовательное предложение, относительно которого имеет смысл говорить истинно оно или ложно.

Примеры:

• Москва – столица России
• H+O=H 2 O

Классификация Высказываний

• общее начинается со слов: все, всякий, каждый, ни один;
• частное  некоторые, большинство и т.д.
• единичное остальные случаи.

Задание

Переместите высказывания к соответствующему типу

общее

Буква «А» - гласная

Все рыбы умеют плавать

единичное

Некоторые медведи бурые

частное

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

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

Виды выражений:

• Простое логическое выражение состоит из одного высказывания.
• Сложное высказывание содержит высказывания, объединяемых логическими операциями (и, или, не).

2. Марина и Оля старше Светы. Слова в этом предложении начинаются на букву «Ч» или на букву «А». X=3 или X2." width="640"

Задание

Из двух простых высказываний составьте сложное, используя логические связки «И», «ИЛИ»

• Марина старше Светы. Оля старше Светы.

• Слова в этом предложении начинаются на букву «Ч». Слова в этом предложении начинаются на букву «А».

• X=3. X2.

Марина и Оля старше Светы.

Слова в этом предложении начинаются на букву «Ч» или на букву «А».

X=3 или X2.

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

A

1

B

0

A B

0

0

0

1

1

0

0

0

1

1

Конъюнкция – в русском языке выражается союзом «И». В математи-ческой логики & или .

Например: Представьте логическое выражение в виде логической формулы:

Число 6 делится на 2 и число 6 делится на 3.

Решение

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

А

B

1

A B

0

0

1

1

0

1

1

0

1

0

1

Дизъюнкция - в русском языке выража-ется союзом «ИЛИ». В математической логики

Например: Представьте логическое выражение в виде логической формулы .

Буква «А» - первая буква в слове «аист» или «сова»

Решение

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

Отрицание – унарная операция записывается в виде или

А

0

1

1

1

В русском предложении выражена словами «не», «неверно».

Например: Неверно, что 4 делится на 3.

4 делится на 3 =А= 0

Задание

Задание: Пусть А – «я сегодня полил цветы», а В – «я сегодня дочитал книгу». Выразите следующие формулы на обычном языке:

1.

2.

3.

Я сегодня полил цветы и дочитал книгу.

Я сегодня полил цветы и не дочитал книгу.

Я сегодня не полил цветы и не дочитал книгу.

Задание

Заполните таблицу истинности

А

В

1

1

1

0

0

1

0

0

Решение

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

Если «основание», то «следствие»;

Когда «основание», тогда «следствие»;

Коль скоро «основание», то «следствие»;

Импликация – двухместная операция, обозначается

Записывается:

А

1

В

1

1

А В

1

0

0

0

0

1

1

0

1

Задание

Используя связку «если …, то…», измените высказывания:

1. Человек любящий животных , - добрый.

2. В високосном году 366 дней.

Если человек любит животных, то он – добрый.

Если год високосный, то в нем 366 дней.

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

Эквивалентность

Языковой аналог – союзы если и только если; тогда и только тогда, когда … . Обозначается или

Пример: Людоед голоден тогда и только тогда, когда он давно не ел.

Людоед голоден = А

А

1

В

1

А В

1

0

1

0

0

0

1

0

0

1

Он давно не ел = В

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

Последовательность выполнения операций:

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

Задание

Найдите все значения переменных, при которых выра-жение принимает заданное значение

А

В

1

1

1

0

0

1

0

0

Решение

Задание

Определить истинность формулы

А

0

В

0

0

С

0

0

0

1

1

0

0

1

1

0

1

1

1

0

0

1

1

1

0

1

1

Решение

Задание

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

Решение

Задание

Встретились три подруги - Белова, Краснова и Чернова. На одной из них было черное платье, на другой красное, а на третьей белое. Девочка в белом платье говорит Черновой: «Нам надо поменяться платьями, а то у нас платья не соответствуют фамилиям». Кто в какое платье одет?

Решение

Задание

Перед началом турнира четыре болельщика высказали предположения по поводу своих кумиров:

• Максим победит, Сергей - 2
• Сергей – 3, Андрей – 1.
• Максим последний, Денис -1.

Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из прогнозов. Какое место заняли Максим, Сергей, Андрей и Денис

Решение

Задание

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

(Первая буква гласная вторая буква гласная) последняя буква гласная?

• Ирина
• Максим
• Артем
• Мария

Решение

Решение:

Число 6 делится на 2 =А=1

Число 6 делится на 3 = В=1

А&В=1

Решение:

Буква «А» - первая буква в слове «аист»=А=1

Буква «А» - первая буква в слове «сова»=В=0

Решение:

А

1

В

1

1

1

0

0

0

0

0

1

0

0

1

1

0

1

Решение:

А

В

1

1

1

0

0

0

1

1

1

0

0

0

1

1

0

1

Ответ: А=0, В=1, С=0

Решение:

А

В

0

0

0

С

0

0

0

1

0

1

0

0

1

1

1

1

0

1

0

1

0

1

0

0

1

1

1

F

0

0

0

0

1

1

1

1

0

1

0

1

1

1

0

1

0

0

1

1

0

1

0

1

0

0

1

1

1

1

1

0

1

1

1

1

1

1

Решение:

1

химия

2

география

география

3

физика

физика

химия

Да, можно. Два варианта.

Решение:

черное

Чернова

-

белое

Белова

Краснова

+

-

красное

-

+

-

+

-

-

Чернова - красное, Белова – черное, Краснова - белое

Решение:

Обозначим:

Из условия задачи:

Из второй таблицы видно, что Сергей-2, Андрей -1, Максим -4, а Денис -3.

1

болельщик

2

М1

болельщик

3

болельщик

С2

С3

М4

А1

Д1

М1

М1

С3

С3

С2

С2

М4

М4

А1

А1

Д1

Д1

Решение:

Обозначим:

Обозначим:

- отрицание по условию задачи

- отрицание по предположению

- верное предположение

М:

М

К:

С:

М

К

С

С

М

Решение:

Рассмотрим разные варианты

М:

М

К:

К

М

С:

С

С

М

Виноват Миша

М:

К:

М

К

М

С:

С

С

М

Виноват Коля

М:

К:

М

М

К

С:

С

С

М

Виноват Сергей

По условию задачи должна получиться схема:

из разбора вариантов видно, что подходит вариант №1, значит окно разбил Миша

Решение:

Первая буква гласная=А

Вторая буква гласная=В

Последняя буква гласная=С

А

Ирина

В

Максим

1

С

0

Артем

0

Мария

1

1

1

0

0

0

0

1

0

1

1

0

1

0

1

1

1

0

0

0

0

Список литературы:

• Информатика. Задачник-практикум в 2 т. Том 1/ Л.А.Залогова, С.В. Русаков и др.: под.ред. И.Г. Семакина, Е.К.Хеннера. – 5-е изд. – М.: БИНОМ. Лаборатория знаний. 2008. 309 с.: ил.
• Информатика. Основы логики. Готовимся к ЕГЭ. С.С.Крылов – М. Интеллект-Центр, 2010. – 48 с.
• Тестирование по информатике в формате ЕГЭ: рекомендации по решению заданий / авт.-сост. М.В. Зорин, Е.М. Зорина, - Волгоград: Учитель, 2009. – 223с.
• http://znanija.com/task/2279492
• http://otvet.mail.ru/question/37618163
• http://yandex.ru/clck/jsredir?from=yandex.ua%3Byandsearch%3Bweb%3B%3B&text=%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8%20%D0%BF%D0%BE%20%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B5%20%D0%BF%D1%80%D0%B8%20%D1%81%D0%BE%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B8%20%D1%80%D0%B0%D1%81%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D1%8F%20%D0%BD%D0%B0%20%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D1%83&uuid=&state=AiuY0DBWFJ4ePaEse6rgeAjgs2pI3DW99KUdgowt9Xtp0tflN7kEeHG_aaf4QjHbpjJ4oBNo_CAL0Odr6KX5dq6r6y3xBkNm_zdKNX_U_Bvrgi2KM0vg0gD6noaZyN524hHSek8Lgz0hvm4J6tRfWL2UvAURdTa1PdwkSsbkjX5ML6tsl1OhV8tH5Tf0soVEBGucuFFWj2w&data=UlNrNmk5WktYejR0eWJFYk1LdmtxaVEzcTA0eUF3MEZSOEMwOFEtbjlhZFFENk80dXBTakdVUWdyTTdHTEJqN0NUazdQbmVKT1lXVVZrN0s4TnYyUm5XNzlNTGRFTUsxaUt2SGxYa3dQUVRCNjNpT19IQlRWYWw1b3BSM09PUWRWOXRaUFRtNTM0bnY4bFdKNTBmY0VKMURfLWRWUGZJQ21jMmZSS09uYkZN&b64e=2&sign=56fdefd1988a62ac7fe7dcd0e0858bec&keyno=0&l10n=ru&mc=4.439218467495729

Схема Логических операций

Дизъюнкция

Конъюнкция

Отрицание

Задание

Составить схему:

2)

Решение

Решение:

Множество

Объекты множества, называются его элементами

Примерами множества могут быть следующие высказывания:

• множество кулинарных сайтов;
• множество кулинарных рецептов;
• множество кулинарных полуфабрикатов.

Множество

Множества обозначаются заглавными буквами: A, B, ….Z, а элементы строчными: a, b,…,z.

Утверждение: «элемент а принадлежит множеству А» символически записывается так: a  A.

Множество, которое не содержит ни одного элемента, называется пустым и обозначается  .

Множество В является подмножеством множества А, если каждый элемент множества В является также элементом множества, обозначается .

Задание

Укажите и запишите с помощью перечисления одно из непустых конечных подмножеств для данного множества:

A= {столовая посуда}

Решение

Решение:

A= {столовая посуда}

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

Пусть множество В= {тарелка, супница, солонка, хлебница, перечница, масленка, салатница, соусница, нож, вилка, ложка}

Следовательно, .

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

Множества A и B находятся в общем положении пересечения, если существует элемент, принадлежащий исключительно множеству A, элемент, принадлежащий исключительно множеству B, а также элемент, принадлежащий обоим множествам.

Обозначение пересечения: A  B.

Задание

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

Решение

Решение:

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

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

куриные яйца, майонез

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

Объединением множеств А и В называется множество, содержащее все элементы, которые принадлежат множеству А или множеству В. Обозначение пересечения: A  B.

Задание

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

Решение

Решение:

сметана, куриные яйца, сахар, масло сливочное, мука, сахар ванильный

кокосовая

стружка

Ответ: A  B ={сметана, куриные яйца, сахар, масло сливочное, мука, сахар ванильный, кокосовая стружка}

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

Разностью множеств А и В называется множество, содержащее все элементы, которые принадлежат множеству А и не принадлежат множеству В.

Обозначается A\ B.

Задание

Даны два множества A – множество однозначных натуральных чисел, кратных 3 и B = {1, 3, 5, 9, 11}

Решение

Решение:

А={3, 6, 9} и B = {1, 3, 5, 9, 11}.

Следовательно, А\В={6}, В\А={1, 5, 11}.

Ответ: А\В={6}, В\А={1, 5, 11}.