Упростить выражения используя законы алгебры множеств

Упростить выражения используя законы алгебры множеств

Вариант 8.

Решить задачу, используя диаграмму Эйлера-Венна.

В одной из студентческих групп все студенты умеют программировать. Десять человек умеют работать на Бейсеке. 10 на Паскале, 6 на Си. Два языка знают: 6 человек Бейсик и Паскаль, 4 – Паскаль и Си, 3 – Бейсик и Си. Один человек знает все три языка. Сколько студентов в группе?

Решение:

В задаче идет речь о следующих множествах:

U — – множество студентов в группе;

А – множество студентов умеющие работать на Бейсик;

В – множество студентов умеющие работать на Паскаль;

С – множество студентов умеющие работать на Си.

По условию задачи:

10 человек умеют работать на Бейсик т.е. ;

10 человек умеют работать на Паскаль, т.е.

6 человек умеют работать на Си, т.е. ;

6 человек умеют работать на Бейсик и Паскаль, т.е. ;

4 человека умеют работать на Паскаль и Си, т.е. ;

3 человека умеют работать на Бейсик и Си, т.е. ;

1 человек умеет работать на всех трех языках, т.е. .

Требуется найти число число студентов в группе, т.е. .

Перенесем эти данные на диаграмму Эйлера-Венна.

Тогда .

Ответ: .

Задано универсальное множество и множества , , . Записать булеан множества X, любое разбиение множества Y, покрытие множества Z. Выполнить действия .

Решение:

Для нахождения множества выполним операции над множествами в следующем порядке:

1) — по определению операции отрицания; 2) — по определению операции дополнения;

3) — по определению операции пересечения.

Итак, .

Для построения булеана множества X воспользуемся двоичной записью числа.

Т.к. множество Х содержит 5 элементов, то его булеан содержит подмножеств. Будем записывать номер подмножества пятиразрядным двоичным числом от 0 до 31, включая в подмножество только те элементы, которым соответствует единица в двоичном разряде. Результаты внесем в таблицу:

№ подмножества Двоичная запись номера Подмножества множества № подмножества Двоичная запись номера Подмножества множества
00000 16 10000
1 00001 17 10001
2 00010 18 10010
3 00011 19 10011
4 00100 20 10100
5 00101 21 10101
6 00110 22 10110
7 00111 23 10111
8 01000 24 11000
9 01001 25 11001
10 01010 26 11010
11 01011 27 11011
12 01100 28 11100
13 01101 29 11101
14 01110 30 11110
15 01111 31 11111

Итак, в булеан множества Х включаем пустое множество, само множество Х, все одноэлементные подмножества, все двухэлементные подмножества множества Х, все трехэлементные подмножества множества Х, все четырехэлементные подмножества множества Х:

B(X)= ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; .

Для множества Y построим разбиение, состоящее из трех блоков например, таким образом:

.

Определение разбиения выполняется: множества не пусты, не пересекаются , их объединение равно множеству Y: .

Для построения покрытия выберем подмножества и . Полученная система множеств состоит из двух блоков, объединение которых равно множеству Z: .

Упростить, используя законы и тождества алгебры множеств (перечислить используемые законы): .

Решение:

Будем считать операция пересечения имеет более высокий приоритет, чем объединение множеств.

Пользуясь этим правилом, определим порядок действий.

Читайте также:  Лучшие дешевые игры в steam

1) По закону дистрибутивности:

.

2) По закону ассоциативности:

.

Конспект урока

Информатика, 10 класс. Урок № 12.

Тема — Преобразование логических выражений

Перечень вопросов, рассматриваемых в теме: основные законы алгебры логики, преобразование логических выражений, логические функции, построение логического выражения с данной таблицей истинности и его упрощение, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ).

Глоссарий по теме: основные законы алгебры логики, логические функции, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ)

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)

Открытые электронные ресурсы по теме:

Теоретический материал для самостоятельного изучения.

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

Основные законы алгебры логики

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение

Последовательно применим дистрибутивный закон и закон исключенного третьего:

В общем случае можно предложить следующую последовательность действий:

  1. Заменить операции строгая дизъюнкция, импликация, эквиваленция на их выражения через операции конъюнкция, дизъюнкция, инверсия;
  2. Раскрыть отрицания сложных выражений по законам де Моргана.
  3. Используя законы алгебры логики, упростить выражение.

Пример 2. Упростим логическое выражение .

Здесь последовательно использованы замена операции импликация, закон де Моргана, распределительный закон, закон противоречия и операция с константой, закон идемпотентности и поглощения.

Аналогичные законы выполняются для операции объединения, пересечения и дополнения множеств. Например:

Пример 3. На числовой прямой даны отрезки B = [2;12] и C = [7;18]. Каким должен быть отрезок A, чтобы предикат становился истинным высказыванием при любых значениях x.

Преобразуем исходное выражение, избавившись от импликации:

A, B, C — множества. Для них можно записать (U — универсальное множество).

Будем считать, что.

Тогда , причем это минимально возможное множество А.

Так как множество B — это отрезок [2;12], а множество — это промежутки и, то пересечением этих множеств будет служить промежуток . В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.

Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение

тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

Перепишем исходное выражение в наших обозначениях и преобразуем его:

Рассмотрим предикат . В числе 2810=111002 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание будет ложным.

Читайте также:  Как настроить 10 полосный эквалайзер

Рассмотрим предикат . В числе 4510=1011012 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 1710=100012 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна 0, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.

По условию задачи надо, чтобы .

Запишем это выражение для рассмотренных множеств истинности:

Так как , примем .

Объединением множеств M и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством K будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т.е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.

Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной х: , и, кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 1011002 = 4410.

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

Совокупность значений n аргументов удобно интерпретировать как строку нулей и единиц длины n. Существует ровно различных двоичных строк длины n. Так как на каждой такой строке некая функция может принимать значение 0 или 1, общее количество различных булевых функций от n аргументов равно .

Для n=2 существует 16 различных логических функций. Рассмотрим их подробнее.

Для любых множеств A, B, C справедливы следующие тождества:

а) AÈ (BÇC) = (AÈB) Ç (AÈC) (для объединения относительно пересечения);

4. Закон де Моргана.

а) = Ç (дополнение к объединению есть пересечение дополнений);

б) = È (дополнение к пересечению есть объединение дополнений).

а) A È A = A (для объединения);

б) A Ç A = A (для пересечения).

7. Расщепление (склеивание).

а) (A È B) Ç (A È ) = A;

б) (A Ç B) È (A Ç ) = A.

8. Двойное дополнение.

= A.

9. Закон исключенного третьего.

A È = U.

10. Операции с пустым и универсальным множествами.

в) A Ç U = A;

д) = U;

е) = Æ.

11. А В = A Ç .

Чтобы доказать некоторое тождество A = B, нужно доказать, что, во-первых, если xÎ А, то xÎВ и, во-вторых, если xÎВ, то xÎ А. Докажем таким образом, например, свойство дистрибутивности для объединения (тождество 3а)):

Читайте также:  Как открыть портал через зеркало

1. Сначала предположим, что некоторый элемент x принадлежит левой части тождества, т.е. xÎ AÈ (BÇC), и докажем, что x принадлежит правой части, т.е. xÎ(AÈB) Ç (AÈC).

Действительно, пусть xÎ AÈ (BÇC). Тогда либо xÎ A, либо xÎ BÇC. Рассмотрим каждую из этих возможностей.

2. Предположим, что некоторый элемент x принадлежит правой части тождества, т.е. xÎ (AÈB) Ç (AÈC), и докажем, что x принадлежит левой части, т.е. xÎ AÈ (BÇC) .

Действительно, пусть xÎ (AÈB) Ç (AÈC). Тогда xÎAÈB, и одновременно xÎ AÈC. Если xÎ AÈB, то либо xÎ A, либо xÎ B, если .xÎ AÈC, то либо xÎ A, либо xÎ C. Пусть xÎ A, Тогда xÎ AÈ (BÇC) и утверждение доказано. Если xÏ A, то одновременно должны выполняться условия xÎ B и xÎ C, т.е. xÎ BÇC. Но тогда xÎ BÇC и xÎ AÈ (BÇC), что также доказывает наше утверждение.

Доказательство тождеств можно проиллюстрировать с помощью диаграмм Венна.

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

Доказать тождество (AÈB) В = A Ç .

Преобразуем левую часть тождества, используя тождество 11:

(AÈB) В = (AÈB) Ç .

Затем используем закон дистрибутивности (тождество 3б):

(AÈB) Ç = A Ç ÈB Ç .

Используем закон исключенного третьего (тождество 9):

B Ç = Æ.

A Ç ÈB Ç = A Ç È Æ.

Используем свойство пустого множества (тождество 10б):

A Ç È Æ = A Ç .

Множества, стоящие в левой и правой частях тождества, изобразим с помощью диаграмм Эйлера – Венна (рис. 1.2).

Рис. 1.2б) и рис. 1.2д) иллюстрируют равенство множеств A (В C) и (A В)È (A Ç C).

Докажем тождество из нашего примера, воспользовавшись тождествами:

А В = A Ç , = È , = A, AÇ(BÈC) = (AÇB)È(AÇC).

A (В C) = A Ç = A Ç = A Ç ( È ) = A Ç ( ÈC) = (A Ç ) È (A Ç C) = (A В)È (A Ç C).

Основные тождества алгебры множеств можно также использовать для упрощения формул алгебры логики.

(AÈB) Ç ( ÈB) Ç (AÈ ).

Используя закон коммутативности (тождество 1б), поменяем местами вторую и третью скобки:

(AÈB) Ç ( ÈB) Ç (AÈ ) = (AÈB) Ç (AÈ ) Ç ( ÈB).

Применим закон расщепления (тождество 7а) для первой и второй скобок:

(AÈB) Ç (AÈ ) Ç ( ÈB) = A Ç ( ÈB).

Воспользуемся законом дистрибутивности (тождество 3б):

A Ç ( ÈB) = A Ç ÈA Ç B.

Используем закон исключенного третьего (тождество 9):

A Ç = Æ.

A Ç ÈA Ç B = Æ ÈA Ç B.

Используем свойство пустого множества (тождество 10б):

(AÈB) Ç ( ÈB) Ç (AÈ ) = A Ç B.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете. 8774 — | 7582 — или читать все.

Ссылка на основную публикацию
Телефонный шлюз что это
VoIP-шлюз — это межсетевой шлюз, предназначенный для перевода трафика между сетями различных типов. VoIP-шлюзы можно разделить на многоканальные и одноканальные:...
Сравнить технические характеристики rx330 и rx350
Линейка популярных люксовых SUV Lexus RX пополнилась новой модификацией – RX 350. Теперь покупателем RX быть еще приятнее – ведь...
Сравнить процессоры кирин и снапдрагон
Snapdragon 636 vs. Kirin 960: кто лучше? Результаты тестов и сравнительных таблиц, описанных в этой статье, помогут определить, какой из...
Телефонная клавиатура на компьютере
Виртуальная клавиатура выручит Вас, когда выйдет из строя основное физическое устройство ввода, полностью или частично ( поломается несколько клавиш )....
Adblock detector