Практикум по дисциплине «Дискретная математика с элементами математической логики»

Министерство образования и науки Самарской области

Министерство имущественных отношений Самарской области

Государственное бюджетное профессиональное образовательное учреждение Самарской области

«Чапаевский губернский колледж им. О.Колычева»

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ СТУДЕНТАМ ПО ВЫПОЛНЕНИЮ ПРАКТИКУМА ПО УЧЕБНОЙ ДИСЦИПЛИНЕ «Дискретная математика с элементами математической логики»

Специальность 09.02.07 Информационные системы и программирование

Чапаевск, 2022 год

Публикуется на основании решения

Методического совета

протокол №1 от 20.09.2022

Автор:Дикова В.Г., преподаватель общепрофессиональных и специальных дисциплин ГБПОУ СО «Чапаевский губернский колледж им. О.Колычева»

Редактор: Захарова Е.М., заместитель директора по учебно-методической работе образовательной программы среднего профессионального образования ГБПОУ СОЧГК им. О.Колычева

Рецензент: Котов А.В., технический директор ООО «Аттис»

Практикум по дисциплине «Дискретная математика с элементами математической логики» предназначен для студентов специальности 09.02.07 Информационные системы и программирование, может быть использован на других специальностях колледжа при изучении данной дисциплины. Данное пособие включает практические занятия, в каждом из которых раскрыты краткие теоретические сведения по теме практического занятия, контрольные вопросы для закрепления и задания в 10 вариантах для отработки навыков.

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

Содержание

Пояснительная записка

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

Комплект практических работ по данной учебной дисциплине составлен в соответствии с ФГОС по специальности СПО 09.02.073 Информационные системы и программирование и позволяет студентам закрепить теоретические знания:

З.1 - основные принципы математической логики, теории множеств и теории алгоритмов;

З.2 - формулы алгебры высказываний;

З.3 - методы минимизации алгебраических преобразований;

З.4 - основы языка и алгебры предикатов,

и отработать умение

У.1 - формулировать задачи логического характера и применять средства математической логики для их решения.

Каждая практическая работа содержит краткие теоретические сведения, вопросы для самопроверки по теоретической части материала, образцы решения задач, задания для самостоятельного выполнения, список источников.

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

Ход работы

1. Познакомиться с теоретическим материалом.

2. Сделать краткий конспект теоретического материала в рабочих тетрадях (основные понятия, определения, формулы).

3. Подготовиться к опросу по контрольным вопросам.

4. Выполнить в тетрадях для практических работ или на ПК, используя программное обеспечение, указанное в работе, задания, соответствующие вашему варианту. (Номер варианта выбирается по последней цифре в порядковом номере в списке группового журнала. Если последняя цифра «0», то выбирается вариант 10)

5. Сдать выполненную практическую работу преподавателю.

Критерии оценивания практических работ

В случае неудовлетворительной оценки студент получает от преподавателя указания для выполнения этого задания.

Практическая работа №1 «Составление таблиц истинности»

Цель работы: закрепить основные понятия алгебры высказываний, отработать навыки составления таблицы истинности для высказываний, сформировать умения определять равносильность формул.

Краткие теоретические сведения

Формулами алгебры логики называются выражения, полученные из переменных x,y,… посредством применения логических операций: отрицания, конъюнкции, дизъюнкции, импликации и эквивалентность, а также сами переменные, принимающие значения истинности высказываний x,y,….

Если в формулу алгебры логики вместо переменных x, y,… подставить конкретные высказывания, то получится высказывание, имеющее логическое значение «1» или «0».

Пример.

Высказывание x: «Волга впадает в Каспийское море» – истинное (x = 1), высказывание y: «Число 16 кратно 3» –ложное (y = 0), тогда формула А=xÚyбудет иметь логическое значение «1»:А =1 (см. таблицу истинности для хÚy).

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

Две формулы алгебры логики A и B называютсяравносильными, если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в них. Обозначают равносильности (тождества) знаком « ».

Формула A называетсявыполнимой, если существует такой набор высказываний, который обращает эту формулу в истинное высказывание.

Формула A называетсяопровержимой, если существует такой набор высказываний, который обращает эту формулу в ложное высказывание.

Формула Aназываетсятождественно-истинной, или тавтологией, если она принимает значение «истинно» при всех значениях переменных, входящих в нее.

Формула A называетсятождественно-ложной,если она принимает значение нуль при всех значениях переменной, входящих в нее.

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

Равносильность логических формул можно установить при помощи их таблиц истинности.

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить количество строк:

n - количество простых высказываний.

1. Определить количество столбцов:

• определить количество переменных (простых выражений);

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

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

Примеры решения заданий

Пример 1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

Решение:

1. Определить количество строк:

на входе два простых высказывания: x,y, поэтому n=2 и количество строк = 2² +1 =5.

1. Определить количество столбцов:

• простые выражения (переменные): x,y;

• промежуточные результаты (логические операции):

1. - инверсия; 

2. – инверсия;

3. – дизъюнкции, т.е. ;

4. - импликация, т.е. ;

5. - дизъюнкция, т.е. ;

6. - конъюнкция, т.е. , это окончательное значение логического выражения.

1. Заполнить столбцы с учетом таблиц истинности логических операций.

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

Пример 2. Определите, являются ли следующие формулы равносильными?

и .

Решение: Составим таблицы истинности формулы .

1. Определить количество строк: на входе два простых высказывания: x,y, поэтому n=2 и количество строк = 2² +1 =5.

2. Определить количество столбцов:

• простые выражения (переменные): x,y;

• промежуточные результаты (логические операции):

1. - инверсия; 

2. – инверсия;

3. – конъюнкции, т.е. ;

4. - импликация, т.е. , это окончательное значение логического выражения.

1. Заполнить столбцы с учетом таблиц истинности логических операций.

Составим таблицы истинности формулы

1. Определить количество строк: на входе два простых высказывания: x,y, поэтому n=2 и количество строк = 2² +1 =5.

2. Определить количество столбцов:

• простые выражения (переменные): x,y;

• промежуточные результаты (логические операции):

1. - инверсия; 

2. – дизъюнкции;

3. - инверсия, т.е. ;

4. - дизъюнкция, т.е ( ), это окончательное значение логического выражения.

1. Заполнить столбцы с учетом таблиц истинности логических операций.

Ответ: данные формулы являются равносильными.

Контрольные вопросы

1. Какие действия выполняются над высказываниями?

2. Что называют алгеброй Буля?

3. Что содержат ТИ и каков порядок их построения?

Варианты заданий практической работы

Вариант 1.

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

1. Определите, являются ли следующие формулы равносильными?

и

Вариант 2.

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

   1. 

   2. 

2. Определите, являются ли следующие формулы равносильными?

и

Вариант 3

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

1. Определите, являются ли следующие формулы равносильными?

и

Вариант 4

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

1. Определите, являются ли следующие формулы равносильными?

и

Вариант 5

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

1. 

2. )

1. Определите, являются ли следующие формулы равносильными?

и

Вариант 6

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

   1. 

   2. 

2. Определите, являются ли следующие формулы равносильными?

и

Вариант 7

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

   1. 

   2. 

2. Определите, являются ли следующие формулы равносильными?

и

Вариант 8

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

1. 

2. .

1. Определите, являются ли следующие формулы равносильными?

и

Вариант 9

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

1. Определите, являются ли следующие формулы равносильными?

и

Вариант 10

1. Определите, какой является формула - выполнимой, опровержимой, тождественно-истинной, тождественно-ложной?

1. Определите, являются ли следующие формулы равносильными?

и

Практическая работа №2 «Упрощение формул логики»

Цель работы: закрепить знание законы алгебры логики, отработать навыки преобразования формулы с помощью равносильных преобразований, сформировать умение решать булевы уравнения.

Краткие теоретические сведения

Законы алгебры логики.

Коммутативный (переместительный) закон:

xyºyx

xyºyx

Ассоциативный (сочетательный) законы:

x (yz)º (xy)z;

x (yz)º (xy)z;

Дистрибутивные законы:

x (yz)º (xy) (xz);

x (yz)º (xy) (xz);

Закон идемпотентности:

xxºx;

xÚxºx;

Законы исключения констант:

x 0 º 0;

xÚ 0 ºx;

x 1 ºx;

xÚ 1 º 1;

Закон двойного отрицания:

ºx;

Закон противоречия:

;

_{Закон исключения третьего:}

;

Законы Де Моргана:

;

;

Закон поглощения:

;

;

Закон исключения (склеивания):

;

;

Закон тождества:

;

Закон контрапозиции:

;

Закон противоположности:

;

Правило цепного заключения:

;

Правило снятия импликации и эквивалентности:

;

.

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

Примеры решения заданий

Пример 1. Упростите логическую формулу: .

Решение. Для упрощения будем использовать законы алгебры логики:

Ответ: xy.

Контрольные вопросы

1. Что называют алгеброй Буля?

2. Законы алгебры Буля.

Варианты заданий практической работы

Вариант 1.

Упростите логическую формулу:

Вариант 2.

Упростить логическую формулу:

Вариант 3

Упростить логическую формулу:

Вариант 4

Упростить логическую формулу:

Вариант 5

Упростить логическую формулу:

1. )

2. 

Вариант 6

Упростить логическую формулу:

Вариант 7

Упростить логическую формулу:

Вариант 8

Упростить логическую формулу:

Вариант 9

Упростить логическую формулу:

Вариант 10

Упростить логическую формулу:

Практическая работа №3 «Приведение формул к совершенным нормальным формам»

Цель работы: закрепить знание о ДНФ и КНФ, сформировать умение приводить формулы алгебры логики к СДНФ и СКНФ.

Краткие теоретические сведения

Существуют две разновидности нормальных форм – дизъюнктивные (ДНФ) и конъюнктивные (КНФ).

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

нормальной формой (ДНФ) называется конечного числа элементарных .

Нормальная форма называется совершенной, если в каждой ее элементарной дизъюнкции (конъюнкции) представлены все переменные, входящие в данную функцию (либо сами, либо с отрицанием).

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

• используя равносильности алгебры логики, заменить все имеющиеся операции на конъюнкцию, дизъюнкцию и отрицание;

• применяя законы де Моргана, снять отрицание с логических операций конъюнкции и дизъюнкции;

• используя распределительный и другие законы, привести функции к нормальной форме;

• используя законы идемпотентности, склеивания и др., минимизировать полученные булевы выражения;

• применяя правила операций с константами, привести минимизированные нормальные формы к совершенному виду.

Алгоритм получения СДНФ по таблице истинности:

1. Отметить те строки, в последнем столбце которых стоят 1:

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

3. Объедините дизъюнкцией все полученные элементарные конъюнкции.

Чтобы построить СКНФ по таблице истинности, надо взять дизъюнкцию элементарных конъюнкций, дающих значение 0 и сделать ее отрицание.

Примеры решения заданий

Пример 1. Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

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

Для получения СКНФ соединяем дизъюнкцией те элементарные конъюнкцией, в которых функция принимает значение 0, и делаем их отрицание:

.

Для получения СДНФ соединяем дизъюнкцией те элементарные конъюнкцией, в которых функция принимает значение 1:

Контрольные вопросы

1. Что такое ДНФ и КНФ?

2. Чем отличается ДНФ от СДНФ?

3. Как составить ДНФ по таблице истинности?

4. Как минимизировать ДНФ?

5. Как составить СКНФ по таблице истинности?

6. Как преобразовать ДНФ в СДНФ?

7. Как преобразовать КНФ в СКНФ?

Варианты заданий практической работы

Вариант 1

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 2

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 3

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 4

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 5

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 6

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 7

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 8

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 9

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Вариант 10

Постройте СДНФ и СКНФ по таблицы истинности для высказывания:

Практическая работа №4 «Упрощение формул логики до минимальной ДНФ»

Цель работы: отработать навыки минимизация СДНФ до минимальной ДНФ с помощью законов алгебры логики и карт Карно.

Краткие теоретические сведения

ДНФ называется минимальной, если она содержит наименьшее число букв среди всех ДНФ ей равносильных.

Минимизировать ДНФ можно используя метод Квайна, который основывается на применении двух основных соотношений:

1. Соотношение склеивания:

;

;

1. Соотношение поглощения:

;

;

Минимизировать нормальные формы можно различными способами, мы рассмотрим способ минимизации с помощью карт Карно.

Минимальная или сокращенная нормальная форма получается из совершенной конъюнктивной (дизъюнктивной) нормальной формы удалением некоторых элементарных дизъюнкций (конъюнкций).

Тупиковойнормальной формой называется КНФ (ДНФ), из которой нельзя удалить ни одной элементарной дизъюнкции (конъюнкции) так, чтобы сохранить неизменной заданную булеву функцию.

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

Карты Карно являются одним из наиболее удобных способов минимизации. Они впервые появились в одной из статей Мориса Карно в 1952г. Это специальные таблицы, дающие возможность упростить процесс поиска минимальной формы булева выражения с помощью графического представления для n≤6. Они имеют вид прямоугольника, разделенного на клеток, в каждой из которых – двоичный n-мерный набор значений функции F из таблицы истинности.

Для n=2 карта Карно имеет вид таблицы, состоящей из клеток.

При n=3 карты Карно имеют вид таблицы с клетками.

При n=4 карты Карно имеют вид таблицы с клеток.

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

Алгоритм «склеивания» с помощью карт Карно имеет следующий вид.

1. Привести булеву функцию к ДНФ.

2. Нанести единицы на карту Карно.

3. Объединить соседние единицы контурами, охватывающими клеток, где m=0,1,2,3. При этом может оказаться, что единицы попадает одновременно в два контура. Если контур охватывает более одной пары единиц одновременно, то предпочтительнее его не дробить на пары, а рассматривать как единый целый контур, например, квадрат.

4. Провести упрощение, т.е. исключить члены, дополняющие друг друга до 1 внутри контура, следя за тем, чтобы переменные внутри контура были связаны операцией конъюнкции.

5. Объединить оставшиеся члены функцией ИЛИ, т.е. дизъюнкцией.

6. Записать полученное упрощенное булево выражение в ДНФ.

При заполнении карт Карно необходимо обратить внимание на порядок заполнения строк и столбцов значениями переменных.Последовательность значений переменных должна сохраняться неизменной. При таком заполнении каждые две соседние клетки отличаются лишь значениями одной переменной.

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

Примеры решения заданий

Пример 1. Упростите высказывание (рассмотренное в примере практической работы №3) до минимальной ДНФ, используя законы алгебры логики:

Решение: В предыдущей практической работы был приведен пример построения СДНФ по таблице истинности. СДНФ получилось следующее:

Теперь используя закон склеивания, приведем СДНФ к минимальной ДНФ:

Минимальная ДНФ:

Пример 2. Минимизируем СДНФ с помощью карт Карно

Решение:

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

Если проанализировать попарно объединенные единицы, то мы увидим, что объединить их можно было как по столбцам, так и по строкам. В таких случаях удобнее рассматривать целиком весь квадрат из четырех единиц и сравнить переменные, записанные на горизонтальных и вертикальных клетках.

Ответ:

Пример 3. Минимизируем СДНФ с помощью карт Карно

Решение:

В большом контуре сохраняется , в маленьком -

Ответ: .

Контрольные вопросы

1. Как получается минимальная нормальная форма?

2. Что называется тупиковой нормальной формой?

3. Объясните алгоритм склеивания с помощью карт Карно.

Варианты заданий практической работы

Вариант 1.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	1
   0	0	1	1
   0	1	0	0
   0	1	1	0
   1	0	0	0
   1	0	1	1
   1	1	0	0
   1	1	1	1

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 2.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	0
   0	0	1	0
   0	1	0	0
   0	1	1	1
   1	0	0	1
   1	0	1	1
   1	1	0	1
   1	1	1	0

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 3.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	1
   0	0	1	1
   0	1	0	1
   0	1	1	0
   1	0	0	0
   1	0	1	1
   1	1	0	0
   1	1	1	0

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 4.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	0
   0	0	1	0
   0	1	0	1
   0	1	1	1
   1	0	0	0
   1	0	1	0
   1	1	0	1
   1	1	1	1

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 5.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	1
   0	0	1	0
   0	1	0	0
   0	1	1	0
   1	0	0	1
   1	0	1	1
   1	1	0	0
   1	1	1	1

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 6.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	0
   0	0	1	1
   0	1	0	0
   0	1	1	0
   1	0	0	1
   1	0	1	1
   1	1	0	1
   1	1	1	0

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 7.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	1
   0	0	1	0
   0	1	0	1
   0	1	1	0
   1	0	0	1
   1	0	1	0
   1	1	0	1
   1	1	1	1

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 8.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	1
   0	0	1	1
   0	1	0	1
   0	1	1	0
   1	0	0	0
   1	0	1	1
   1	1	0	1
   1	1	1	0

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 9.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	1
   0	0	1	1
   0	1	0	0
   0	1	1	1
   1	0	0	1
   1	0	1	0
   1	1	0	1
   1	1	1	0

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Вариант 10.

1. Постройте СДНФ и СКНФ по таблице истинности и минимизируйте СДНФ с помощью законов алгебры логики:

   X	Y	Z	F(XYZ)
   0	0	0	1
   0	0	1	1
   0	1	0	0
   0	1	1	0
   1	0	0	1
   1	0	1	0
   1	1	0	1
   1	1	1	1

2. По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ с помощью карт Карно:

.

Практическая работа №5 «Действия над множествами»

Цель работы: закрепить знание определений теории множеств, сформировать умение выполнять действия над множествами и обеспечить усвоение законов действий над множествами.

Краткие теоретические сведения

1 Множество. Способы задания множеств.

Одним из основных исходных понятий математики является понятие множества и его элементов. Множество состоит из элементов. Множества обозначаются большими латинскими буквами: A; B; C..., а их элементы - малыми буквами: a,b,c,…

Если a является элементом множестваA или a принадлежит множеству A, то применяют запись aA; в противном случае пишут aA.

Два множества A и Bравны (A=B), если они состоят из одних и тех же элементов. Если множестваA и B не равны, то применяется запись A  B.

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

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

аб

Рис. 1.1.

Если каждый элемент а множества В (аВ), является элементом множества А,аА, тоВ называется подмножеством множестваА (рис. 1.1, а). Этот факт записывается с помощью знака включения  следующим образом: ВА.

Свойства включения

1. АА;

2. если А В и ВС, то АС (рис. 1.1, б);

3. из двух включений ВА и А В следует, что А=В.

Принято считать, что пустое множество является подмножеством любого множества.

Если ВА и при этом ВА, то этому соответствует запись ВАи В называется собственным подмножеством А. В решении примера 1.1 все множества, кроме последнего, являются собственными подмножествами множества А.

Для описания множества A, состоящего из элементов a1,a2,...,an,... обычно применяется запись A={a1,a2,...,an,...}, причём порядок элементов в фигурных скобках не имеет значения; обычно он определяется соображениями наглядности.

Пример. В записи множества первыхn натуральных чисел Nn={1,2,...,n} удобно располагать числа в возрастающем порядке, хотя при этом надо иметь в виду, что

N3 ={1,2,3}={2,1,3}={3,2,1}.

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

A ={a/a обладает свойством P(a)}.

Пример. Множество чётных чисел M может быть задано так:

M={i / i - целое число, которое делится на 2 без остатка}.

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

Возможно также рекурсивное задание множества, при котором осуществляется последовательное описание элементов через предыдущие. Например, множество натуральных чисел рекурсивно можно задать так: N={i / если целое iN, то i+1N, i  1}.

2. Операции над множествами. Законы действий над множествами.

Объединением двух множеств А и В называется множество вида:

AB ={a / aAили a B}(рис. 1.2, а).

Пересечением двух множеств А и В называется множество вида:

AB={a / aAи a B} (рис. 1.2, б).

Если множества А и В не имеют общих элементов, то AB=.

а б

Рис. 1.2.

Свойства операций объединения и пересечения

1. коммутативность

AB = ВА,

AB = ВА ();

1. ассоциативность

(AB)С = A(BС),

(AB)С = A(BС) ().

Объединение и пересечение связаны законами дистрибутивности:

A(BC)= (AB)  (AС);

A(BC)= (AB)  (AС).

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

Рис. 1.3.

Разность множеств А и В определяется следующим образом:

A\B ={a / aAи aB} (рис. 1.3, а).

Разность не обладает свойством коммутативности; эта операция также не является и ассоциативной.

Пользуясь понятием универсального множества, можно определить дополнение к множеству А, как разность вида: = U \ A (рис. 1.3, б).

Пример. Пусть в качестве универсального множества выступает множество целых чисел Z и пусть А - это множество всех чётных чисел. Тогда - это множество всех нечётных чисел.

Операции объединения, пересечения и дополнения множеств связаны между собой законами де Моргана:

,

.

Если a  , то a AB. Это значит, что или a , или a , т.е. a . Следовательно, .

С другой стороны, если a , то или a , или a . Это значит, что aA B , т.е. a  . Таким образом .

Из этих двух включений следует первый закон де Моргана.

Второй закон доказывается аналогичным образом.

Примеры решения заданий

Пример1. Найдите при А={7;8;9} и В={7;8;10}

Решение:

Пример2. Докажите равенство и запишите равенство двойственное данному:

Решение:

Преобразуем левую часть:

Таким образом, левая часть равна правой части, т.е. равенство верно.

Для того чтобы составить равенство, двойственное данному, пользуемся принципом двойственности. Заменим в данном равенстве знак на и наоборот. Чтобы не поменялся порядок действий, по другому поставим скобки. Получим двойственное равенство:

Контрольные вопросы

1. Что понимают под множеством?

2. Способы задания множеств.

3. Какое множество называют пустым? Универсальным?

4. Действия над множествами.

5. Законы действий над множествами.

Варианты заданий практической работы

Задание 1.

Принято обозначать:

N – множество натуральных чисел; Q– множество рациональных чисел;

Z – множество целых чисел; R – множество действительных чисел.

Тогда верным утверждением будут…

Вариант 1. a) , b) , c) , d) .

Вариант 2. a) , b) , c) , d) .

Вариант 3. a) , b) , c) , d) .

Вариант 4. a) , b) , c) , d) .

Вариант 5. a) , b) , c) , d) .

Вариант 6. a) , b) , c) , d) .

Вариант 7. a) , b) , c) , d) .

Вариант 8. a) , b) , c) , d) .

Вариант 9. a) , b) , c) , d) .

Вариант 10. a) , b) , c) , d) .

Задание 2.

Заданы множества А, В, С. Какие из утверждений будут верными?

1. Множества A и C не содержат одинаковых элементов.

2. Множества A и C равны ( A=C).

3. Множества В и C равны ( B=C ).

4. Множество А является подмножеством множества В. ( )

5. Множество С является подмножеством множества А. (CA)

6. Множество С является подмножеством множества B. (CB)

7. Пустое множество является подмножеством множества А.

8. Множество А конечно.

9. Множество В является бесконечным.

10. Множество В является подмножеством пустого множества

Вариант 1. A = {2,3,4, f}, B = {3,4}, C = {4,3}.

Вариант 2. A = {7,9,a}, B = {a,9,7}, C = {7,8,9,a,b}.

Вариант 3. A ={5,6,t}, B = {4,5,6,e,t}, C = {6,t,5}.

Вариант 4. A = {3,4,o}, B = {1,3,4,i,o}, C = {o,1,3,i,4}.

Вариант 5. A = {9,10,h,l}, B = {h,l,9,10}, C = {10,h}.

Вариант 6. A = {3,6,9,u}, B = {6,u,9}, C = {6,u,3,9}.

Вариант 7. A = {6,8,10}, B = {4,6,8,10, k}, C = {8,6, k,4,10}.

Вариант 8.A = {-5,5,t}, B = {5,-5,t}, C = {-5,k,t,5}.

Вариант 9.A = {-1,t,r}, B = {-2,-1,0,t,r}, C = {t,-1,r}.

Вариант 10.A = {3,7,11,d}, B = {7,11,d}, C = {11,d,7}.

Задание 3.

Вариант 1.

1. Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

1. Даны множества M, P,T. Каким будет множество , если

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества . Расположите множества: , , , , в таком порядке, чтобы каждое из них было подмножеством следующего за ним.

Вариант 2.

1. А=,B=Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

.

1. Даны множества M, P,T. Каким будет множество , если

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества . Расположите множества: в таком порядке, чтобы каждое из них включало в себя предыдущее множество.

Вариант 3.

1. . Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

1. Даны множества M, P,T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества Расположите множества: в таком порядке, чтобы каждое из них включало в себя множество, следующее за ним.

Вариант 4.

1. А=,В=Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

.

1. Даны множества M, P,T. Каким будет множество , если

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества . Расположите множества: в таком порядке, чтобы каждое из них было подмножеством предыдущего множества.

Вариант 5.

1. А=, В= . Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

.

1. Даны множества M, P,T. Каким будет множество , если

; .

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества Расположите множества: , в таком порядке, чтобы каждое из них являлось подмножеством следующего за ним.

Вариант 6.

1. Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

.

1. Даны множества M, P,T. Каким будет множество , если

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества Расположите множества: в таком порядке, чтобы каждое из них было подмножеством предыдущего за ним.

Вариант 7.

1. А=,В= . Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

.

1. Даны множества M, P,T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов Эйлера.

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

Вариант 8.

1. Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

.

1. Даны множества M, P,T. Каким будет множество , если

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества . Расположите множества: в таком порядке, чтобы каждое из них содержало множество, следующее за ним.

Вариант 9.

1. Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

.

1. Даны множества M, P,T. Каким будет множество , если

; .

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества . Расположите множества: , в таком порядке ,чтобы каждое из них было подмножеством следующего за ним.

Вариант 10.

1. Найдите .

2. Докажите равенство и запишите равенство двойственное данному:

.

1. Даны множества M, P,T. Каким будет множество , если

Найдите его. Изобразите его с помощью кругов Эйлера.

1. Заданы произвольные множества . Расположите множества: , в таком порядке, чтобы каждое из них включало в себя предыдущее множество.

Практическая работа №6 «Мощность конечного множества»

Цель работы: сформировать умение решать задачи с помощью кругов Эйлера.

Краткие теоретические сведения

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

Графически это выглядит так

Два множества называются равными, если они являются взаимными подмножествами.

Рассмотрим операции над множествами и их графическую иллюстрацию

1. Объединение множеств А и В изображаем:

1. Пресечение двух множеств А и В изображаем:

1. Дополнение к множеству А изображаем

В любой имеющей смысл задаче обычно рассматриваются подмножества некоторого "наибольшего" множества U, которое называют универсальным множеством. Универсальное множество - это самое большее множество, содержащее в себе все множества, рассматриваемые в задаче.

Множество всех элементов универсального множества U, не принадлежащих множеству А называется дополнением множества А до U и обозначается Ā

1. Симметрическую разностьизображением

1. Разность множеств изображаем

Мощностью конечного множества называется количество его элементов.

Для конечного множества А через m(A) обозначим число элементов в множестве А.

Из определения следуют свойства:

m (A) + m (Ā) = m (E)

А=В m(A)=m(B)

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

m( )=m(A) + m(В) – m(А∩В)

m ( )= m(A) + m(В) + m(С)– m(А∩В)- m(А∩С)– m(В∩С)– m(А∩В∩С).

Примеры решения заданий

Пример. В олимпиаде по математике приняло участие 40 учащихся, им было предложено решить одну задачу по алгебре, одну по геометрии и одну по тригонометрии. По алгебре решили задачу 20 человек, по геометрии – 18 человек, по тригонометрии – 18 человек. По алгебре и геометрии решили 7 человек, по алгебре и тригонометрии – 9 человек. Ни одной задачи не решили 3 человека. Сколько учащихся решили все задачи? Сколько учащихся решили только две задачи? Сколько учащихся решили только одну задачу?

Решение: Запишем коротко условие и покажем решение:

m (Е) = 40; m (А) = 20; m (В) = 18; m (С) = 18; m (А∩В) = 7; m (А∩С) = 8; m (В∩С) = 9; m (АВС) = 3 m (АВС) =40 – 3 = 37.

Изобразим множества А, В, С (рис.5).

1. множество учеников, решивших только одну задачу по алгебре;

2. множество учеников, решивших только две задачи по алгебре и геометрии;

3. множество учеников, решивших только задачу по геометрии;

4. множество учеников, решивших только две задачи по алгебре и тригонометрии;

5. множество всех учеников, решивших все три задачи;

6. множество всех учеников, решивших только две задачи, по геометрии и тригонометрии;

7. множество всех учеников, решивших только задачу по тригонометрии;

8. множество всех учеников, не решивших ни одной задачи.

Используя свойство мощности множеств и рисунок можно выполнить вычисления:

m (К5) = m (А∩В∩С)= m (АВС) - m (А) - m (В) - m (С) + m (А∩В) + m (А∩С) + m (В∩С);

m (К5) = 37-20-18-18+7+8+9=5;

m (К2) = m (А∩В) - m (К5) = 7-5=2

m (К4) = m (А∩С) - m (К5) = 8-5=3;

m (К6) = m (В∩С) - m (К5) = 9-5=4

m (К1) = m (А) - m (К2) - m (К4) - m (К5) = 20-2-3-5=10;

m (К3) = m (В) - m (К2) - m (К6) - m (К5) = 18-2-4-5=7;

m (К7) = m (С) - m (К4) - m (К6) - m (К5) = 18-3-4-5 =6

m (К2) + m (К4) + m (К6) = 2+3+4=9 – число учеников решивших только две задачи;

m (К1) + m (К3) + m (К7) = 10+7+6=23 – число учеников решивших только одну задачу.

Ответ: 5 учеников решили три задачи; 9 учеников решили только по две задачи; 23 ученика решили только по одной задаче.

Варианты заданий практической работы

Распределение задач по вариантам

Задачи практической работы

Задача № 1.

В группе 35 студентов. Каждый из них пользуется хотя бы одним из видов городского транспорта: метро, автобусом и троллейбусом. Всеми тремя видами транспорта пользуются 6 студентов, метро и автобусом – 15 студентов, метро и троллейбусом – 13 студентов, троллейбусом и автобусом – 9 студентов. Сколько студентов пользуются только одним видом транспорта?

Задача № 2.

Первую или вторую контрольные работы по математике успешно написали 33 студента, первую или третью – 31 студент, вторую или третью – 32 студента. Не менее двух контрольных работ выполнили 20 студентов. Сколько студентов успешно решили только одну контрольную работу?

Задача № 3.

Из сотрудников фирмы 16 побывали во Франции,10 - в Италии,6 - в Англии; в Англии и Италии - 5; в Англии и Франции - 6; во всех трех странах - 5 сотрудников. Сколько человек посетили и Италию, и Францию, если всего в фирме работают 19 человек, и каждый из них побывал хотя бы в одной из названных стран?

Задача №4.

В трёх группах 70студентов. Из них 27 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются спортом. В драмкружке 10 студентов из хора, в хоре 6 спортсменов, в драмкружке 8 спортсменов; 3 спортсмена посещают и драмкружок и хор. Сколько студентов не поют в хоре, не увлекаются спортом и не занимаются в драмкружке? Сколько студентов заняты только спортом?

Задача №5.

В группе переводчиков 15 человек владеют английским языком, 19 – французским, 8 – немецким. 9 переводчиков владеют английским и французским языками, 7 – английским и немецким, 6 – французским и немецким. 4 переводчика владеют всеми тремя языками. Сколько переводчиков в группе?

Задача №6.

Каждый студент группы программистов занимается в свободное время либо творчеством, либо спортом. Сколько студентов в группе, если 23 увлекаются спортом, 12 – дизайном, а 7 совмещают занятия дизайном и увлечение спортом?

Задача №7.

В футбольной команде «Спартак» 30 игроков, среди них 18 нападающих. 11 полузащитников, 17 защитников и вратари. Известно, что трое могут быть нападающими и защитниками, 10 защитниками и полузащитниками, 6 нападающими и защитниками, а 1 и нападающим, и защитником, и полузащитником. Вратари не заменимы. Сколько в команде «Спартак» вратарей?

Задача №8.

В магазине побывало 65 человек. Известно, что они купили 35 холодильников, 36 микроволновок, 37 телевизоров. 20 из них купили и холодильник и микроволновку, 19 - и микроволновку, и телевизор, 15-холодильник и телевизор, а все три покупки совершили три человека. Был ли среди них посетитель, не купивший ничего?

Задача №9

В группе 20 студентов. После медицинского осмотра 14 студентов были направлены на дополнительное обследование к терапевту, 6 – к окулисту, 5 – к ортопеду. К терапевту и окулисту были направлены 3 студента, к терапевту и ортопеду – 3, к окулисту и ортопеду – 2. Сколько студентов было направлено к терапевту, окулисту и ортопеду?

Задача №10

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

Задача №11

Группе студентов предложены спецкурсы по мультимедиа, искусственному интеллекту и имитационному моделированию. 22 студента записались на спецкурс по мультимедиа, 18 – на спецкурс по искусственному интеллекту, 15 – на спецкурс по имитационному моделированию, 8 – на спецкурсы по мультимедиа и искусственному интеллекту, 10 – на спецкурсы по мультимедиа и имитационному моделированию, 7 – на спецкурсы по искусственному интеллекту и имитационному моделированию. 5 студентов записались на все три спецкурса. Сколько студентов в группе?

Задача №12

В студенческой группе 25 человек. Чтобы получить допуск на экзамен по данному курсу, необходимо защитить курсовую работу, выполнить лабораторную работу и сдать зачет. 15 студентов защитили курсовую работу, 20 — выполнили лабораторную работу, 17 — сдали зачет. Защитили курсовую работу и выполнили лабораторную работу 12 человек. Защитили курсовую работу и сдали зачет 13 человек. Выполнили лабораторную работу и сдали зачет 16 человек. Сколько студентов допущено к экзамену?

Задача №13

В спортивной группе обучаются 24 человека. Каждый учащийся занимается хотя бы одним видом спорта (баскетболом или волейболом), из них баскетболом и волейболом занимаются 12 человек. Сколько человек занимается только волейболом, если их в 3 раза больше, чем тех, кто занимается только волейболом, если их в 3 раза больше, чем тех, кто занимается только баскетболом?

Задача №14

Во время сессии 24 студента группы должны сдать три зачета: по физике, математике и программированию. 20 студентов сдали зачет по физике, 10 – по математике, 5 – по программированию, 7 – по физике и математике, 3 – по физике и программированию, 2 – по математике и программированию. Сколько студентов сдали все три зачета?

Задача №15

Из 35 студентов, побывавших на каникулах в Москве, все, кроме двоих, делились впечатлениями. О посещении Большого театра с восторгом вспоминали 12 человек, Кремля – 14, а 16 – о концерте, по три студента запомнили посещение театра и Кремля, а также театра и концерта, а четверо – концерта и пребывания в Кремле. Сколько студентов сохранили воспоминания одновременно о театре, концерте и Кремле?

Практическая работа №7 «Представление булевых функций в виде многочлена Жегалкина»

Цель работы: сформировать умение представлять булеву функцию в виде многочлена Жегалкина, используя преобразования выражений по законам алгебры логики, научиться определять является ли данная функция линейной

Краткие теоретические сведения

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

Заменив в СДНФ на и используя распределительный закон для конъюнкции относительно сложения по модулю два, имеем . Тогда, учитывая, что , а , булеву функцию f можно представить в виде , причем

Такое представление булевой функции называется каноническим полиномом Жегалкина.

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

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

Функция является линейной, если многочлен Жегалкина не содержит конъюнкции переменных.

Алгоритм построения многочлена Жегалкина:

1. Находим множество тех двоичных наборов, на которых функция принимает значение 1.

2. Составляем СДНФ.

3. В СДНФ каждый знак дизъюнкции меняем на знак суммы Жегалкина.

4. Упрощаем, если можно, полученное выражение, используя тождество .

5. В полученной формуле каждое отрицаниезаменяем на .

6. Раскрываем скобка в полученной формуле, содержащей только функции и константу 1.

7. Приводим подобные члены, используя тождество .

Примеры решения заданий

Пример 1. Записать булеву функцию в виде многочлена Жегалкина. Определить является ли функция линейной.

Решение: Преобразуем равенство, используя формулы алгебры логики.

Функция не является линейной, т.к. многочлен Жегалкина содержит конъюнкции переменных.

Ответ: функция не является линейной; многочлен Жегалкина, соответствующий данной функции:

Контрольные вопросы

1. Определение многочлена Жегалкина.

2. Какой многочлен Жегалкина называется линейным?

Варианты заданий практической работы

Вариант 1.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 2.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 3.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 4.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 5.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 6.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 7.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 8.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 9.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Вариант 10.

1. Выясните, верны ли следующие равенства, отыскав полиномы Жегалкина, представляющие булевы функции в обеих частях этого равенства:

1. Отыскав для каждой из следующих булевых функций представляющий ее полином Жегалкина ,установите, какие из функций тождественно равны 1,а какие-0:

1. Докажите, что все следующие булевы функции линейны:

Практическая работа №8 «Классы Поста»

Цель работы: закрепить знание определения классов Поста, теорему о функциональной полноте системы булевых функций, сформировать умение определять к какому классу Поста относится данная булева функция.

Краткие теоретические сведения

Система булевых функций называется полной, если всякая булева функция является суперпозицией функций из этой системы.

Следующие системы булевых функций являются полными: 1) ; 2) ; 3) ; 4) ; 5) ; 6) ; 7) .

Обозначим через множество всех функций алгебры логики.

Класс функций называется функционально замкнутым, если любая суперпозиция функций этого класса R принадлежит этому же классу.

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

• функции, сохраняющие константу 0 или 1;

• самодвойственные функции;

• монотонные функции;

• линейные функция.

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

-Хотя бы одна функция, не сохраняющая 0.

-Хотя бы одна функция, не сохраняющая 1.

-Хотя бы одна нелинейная функция.

-Хотя бы одна немонотонная функция.

-Хотя бы одна не самодвойственная функция.

Важнейшие замкнутые классы

Класс функций, сохраняющих константу0 (P₀)

Булева функция f(x₁,x₂,...,x_n)сохраняет 0, если f(0,0,...,0)=0. Обозначим P₀ - класс всех булевых функций, сохраняющих 0.

Очевидно, что функции , т.к. .

Для n аргументов имеется функций от n аргументов, охраняющих константу, поскольку на одном из двоичных наборов, а именно на , значение f фиксировано, и для функции с n аргументами возможно подобрать лишь 2ⁿ-1 произвольных наборов аргументов.

Такой класс функционально замкнут по определению, поскольку если и , то .

Класс функций, сохраняющих константу1(P₁)

Обозначим через P₁ класс всех булевых функций f(x₁,x₂,...,x_n), сохраняющих константу 1, то есть функций, для которых выполнено равенствоf(1,1,...,1)=1.

Очевидно, что функции , т.к. .

Для P₀ справедливо все то же, что и для P₀.

Класс самодвойственных функций (S)

Функция , удовлетворяющая условию , называется двойственной по отношению к функции . Очевидно, что . Таким образом, если , то , т.е. множество булевых функций разбивается на пары взаимно-двойственных функций.

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

Функция называется самодвойственной, если .

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

Множество самодвойственных функций образует функционально замкнутый класс.

Составим двойственную к h функцию h* и преобразуем ее:

h*(x₁,x₂,x₃) = (x₁x₂) & (x₁x₃) & (x₂x₃) = (x₁x₂x₃) & (x₂x₃) = x₁x₂x₁x₃x₂x₃ = h(x₁,x₂,x₃).

Для самодвойственной функции имеет место тождество: ; иначе говоря, на наборах (₁,...,_n) и которые называются противоположными, самодвойственная функция принимает противоположные значения.

Класс монотонных функций (M)

На множестве B введем полный порядок: по аналогии с отношением на множестве целых чисел . На множестве Bⁿ введем частичный порядок, означающий, что неравенства выполняется тогда и только тогда, когда . Например, .

Два элемента и называются сравнимыми между собой, если или . Частичным такой порядок является потому, что не все элементы Bⁿ сравнимы.

Функция называется монотонной, если для любых двух элементов , сравнимых между собой, из следует, что .

Например, функции 0, 1, x, x₁x₂,x₁ x₂ монотонные, а функции , x₁ x₂, x₁x₂ монотонными не являются.

Обозначим через M множество всех монотонных функций. Монотонные функции также образуют функционально замкнутый класс.

Следует отметить свойство монотонных булевых функций одного и двух аргументов. Поскольку B и B² сравнимы лишь и соответственно, а значения получаются , то такие монотонные функции будут сохраняющими 0 и 1, т.е. пересечением этих двух классов.

Класс L линейных функций (L)

Функция алгебры логики вида называется линейной, если ее канонический полином Жегалкина имеет вид многочлена первой степени: , аналогично обычному алгебраическому многочлену первой степени, но с коэффициентами в виде 0 или 1.

Число таких линейных функций от nаргументов равно , приn=2 их восемь из шестнадцати. Они образуют функционально замкнутый класс.

Система функций {f₁, f₂,...,f_k} называется функционально полной, если любую функцию алгебры логики можно записать с помощью суперпозиции некоторого набора булевых функций f₁, f₂,...,f_k.

Функционально полная система функций называется базисом в пространствеP₂, если удаление хотя бы одной из функций, входящих в нее, превращает эту систему в функционально неполную.

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

Теорема о функциональной полноте. Для того чтобы система S функций f₁ f₂...,f_n была функционально полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классовP₀,P₁, S, M иL.

Каждая функция из P₂ может быть выражена при помощи полинома по модулю 2. Таким образом, существует целый ряд полных систем. Каждая из них может быть принята за множество элементарных функций. Какая из систем является более удобной, зависит от характера рассматриваемой задачи.

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

Примеры решения заданий

Пример 1. Определим, к каким классам Поста относится булева функция .

Решение: Так как , а , то и . Поскольку , то . Так как , то . Полином Жегалкина для функции имеет вид в силу равенства . Поэтому данная функция нелинейна. Таким образом, можно составить следующую таблицу:

Контрольные вопросы

1. Какие существуют классы Поста?

2. Определения функций, принадлежащих различным классам Поста.

Варианты заданий практической работы

Вариант 1.

Определить к каким классам Поста относятся булевы функции:

Вариант 2.

Определить к каким классам Поста относятся булевы функции:

Вариант 3.

Определить к каким классам Поста относятся булевы функции:

Вариант 4.

Определить к каким классам Поста относятся булевы функции:

Вариант 5.

Определить к каким классам Поста относятся булевы функции:

Вариант 6.

Определить к каким классам Поста относятся булевы функции:

Вариант 7.

Определить к каким классам Поста относятся булевы функции:

Вариант 8.

Определить к каким классам Поста относятся булевы функции:

Вариант 9.

Определить к каким классам Поста относятся булевы функции:

Вариант 10.

Определить к каким классам Поста относятся булевы функции:

Практическая работа №9 «Применение булевых функций к релейно-контактным схемам»

Цель работы: закрепить знание законов алгебры Буля, сформировать умение составлять РКС для высказываний, записывать высказывания по данным РКС.

Краткие теоретические сведения

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

• переключателей (контактов, реле, ламп и др.);

• соединительных проводников;

• входов-выходов (полюсов РКС).

Рассмотрим простейшую РКС, содержащую один переключатель Р. Если переключателюР поставить в соответствие высказываниех: «Переключатель Р замкнут», то истинному значению х (х = 1) будет соответствовать замкнутое состояние переключателя, при котором РКС проводит ток, т.е. импульс, поступающий на вход, может быть снят на выходе. Значению х = 0 будет соответствовать разомкнутое состояние РКС (ток не проводится). Каждой РКС, состоящей из нескольких переключателей, можно поставить в соответствие высказывание, выраженное некоторой формулой А, таким образом, что истинному значению формулы (А = 1) будет соответствовать замкнутое состояние РКС, а значению А = 0 – разомкнутое состояние. Примеры таких соответствий приведены в таблице.

Простейшие РКС и соответствующие им формулы логики.

Из простейших РКС путем их последовательного и параллельного соединения могут быть построены более сложные переключательные схемы.

Доказано, что любая формула алгебры логики может быть преобразована к виду, содержащему только операции отрицания, конъюнкции и дизъюнкции. Это позволяет изображать логические формулы при помощи РКС, а РКС задавать формулами.

Например, согласно формулам основных равносильностей и , следовательно, логическим операциям импликации и эквивалентности соответствуют РКС, изображенные рис. 1.

Рис. 1

Примеры решения заданий

Пример 1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

Решение:

Схема состоит из трех параллельных ветвей. Первая ветвь, в свою очередь, состоит из двух параллельных ветвей, в одной из которых последовательно соединены два контакта x и z’, а в другой есть лишь один контакт y. Поэтому первая из трех параллельных ветвей имеет следующую функцию проводимости: .

Вторая параллельная ветвь состоит из двух последовательно соединенных контактов xи y и поэтому имеет следующую функцию проводимости: xy.

Наконец третья параллельная ветвь схемы состоит из двух параллельных ветвей, в одной из которых единственный контакт , а в другой последовательно соединены контакты y и z. Поэтому функция проводимости третьей ветви схемы есть .

Итак, поскольку данная схема состоит из трех параллельно соединенных ветвей, функции проводимости которых мы нашли, то для нахождения функции проводимости всей схемы нужно рассмотреть дизъюнкцию найденных функций: .

Ответ: .

Пример 2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

Решение:

Сначала необходимо выразить функцию через функции , причем так, чтобы знак стоял бы лишь на переменных и не стоял на скобках:

.

Соответствующая схема имеет вид:

Пример 3. Проверьте равносильность следующих релейно-контактных схем:

Решение:

Сначала составим функцию проводимости первой из двух данных схем, а затем преобразуем ее:

.

Ясно, что полученная функция (булева функция, конечно, осталась той же самой, а изменилась лишь ее аналитической записи) является функцией проводимости второй из двух данных схем.

Контрольные вопросы:

1. Что называется релейно-контактной схемой.

2. Простейшие РКС и соответствующие им формулы логики.

Варианты заданий практической работы.

Вариант 1.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 2.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 3.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 4.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 5.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 6.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 7.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 8.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 9.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Вариант 10.

1. По данной релейно-контактной схеме найдите ее функцию проводимости и условия работы:

2. Постройте релейно-контактную схему с заданной функцией проводимости:

.

1. Проверьте равносильность следующих релейно-контактных схем:

Практическая работа №10 «Вычислимые по Тьюрингу функции»

Цель работы: закрепить теоретические сведения о таком методе алгоритмов, как машина Тьюринга, на практике.

Краткие теоретические сведения.

Модель алгоритма Машина Тьюринга была впервые предложена А.М. Тьюрингом в 1936 г.

Машина Тьюринга имеет 3 алфавита:

1. внешний алфавит с пустым символом (в роли данных – слова в некотором конечном алфавите - внешнем алфавите);

2. внутренний алфавит, или алфавит состояний . Состояние называется заключительным, - начальным, а состояния - рабочими состояниями.

3. Алфавит сдвигов .

В конструкции машины имеются:

1. бесконечная лента (разбитая на ячейки), предназначенная для размещения бесконечных записей конечных слов над алфавитом А. В каждой ячейке м.б. записан 1 из символов алфавита А. Пустая ячейка – такая ячейка, в которую помещен некоторый фиксированный символ (пробел, ноль,…). Следовательно, в каждый данный момент времени лента полностью заполнена.

2. механизм – это считывающе-записывающее устройство (СЗУ), называемое также читающей/пишущей головкой. СЗУ обладает способностью обозревать одну ячейку ленты, считывать букву, записанную в ячейке, заносить на место считываемой любую другую букву внешнего алфавита; за один такт работы головка может переместиться на 1 ячейку вправо (П) или на 1 ячейку влево (Л) и воспринимать новую ячейку или остаться на месте (С).

3. устройство управления (УУ), которое управляет с помощью программы работой машины.

4. программа машины, определяющая переходы машины от одной конфигурации к другой.

Правила работы машины (правила обращения УУ с программой и СЗУ )

Машина работает дискретно (пошагово). На каждом шаге происходит переход от одной конфигурации к другой.

Перед налом работы машина находится в начальной конфигурации: СЗУ обозревает первую букву слова, а машина находится в начальном состоянии . СЗУ считывает букву, находящуюся в обозреваемой ячейке. УУ обращается к программе машины: находит клетку, соответствующую считанной букве и состоянию машины. Пусть в этой клетке находится тройка , тогда буква а заносится обозреваемую ячейку, машина переводится в состояниеq, а СЗУ совершает сдвиг на 1 ячейку влево, если , вправо – при , и остается на месте, если . На этом завершена работа машины на первом шаге и она готова к выполнению следующего аналогичного шага. Работа машины продолжается до тех пор, пока на каком-то из шагов машины не придет в состояние . УУ в этом случае останавливает машину. Возникшая конфигурация называется заключительной, а полученное слово – результатом применения машины к исходному слову.

Итак, правила работы машины:

Если u – исходное слово, Т – машина, то через Т(u) обозначают результат.

Говорят, что МТ неприменима к слову u, если в процессе применения ее к слову она ни на каком из шагов не приходит в заключительное состояние.

Примеры решения заданий

Пример. Дана машина Тьюринга с внешним алфавитом A={a₀, 1}, алфавитом внутренних состоянийQ={q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇} и со следующей функциональной схемой (программой):

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

Решение: Выписываем последовательность конфигураций машины при переработке ею слова 111 из начального стандартного положения:

Итак, слово 111 из начального стандартного положения перерабатывается машиной в слово 1.

Контрольные вопросы

1. Перечислите алфавиты машины Тьюринга.

2. Объясните назначение элементов в конструкции машины Тьюринга.

3. Расскажите правила работы машины Тьюринга .

Варианты заданий практической работы

Задание.

Дана машина Тьюринга с внешним алфавитомA={a₀, 1}, алфавитом внутренних состоянийQ={q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇} и со следующей функциональной схемой (программой):

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

Вариант 1. 11111

Вариант 2. 111111

Вариант 3. 1111

Вариант 4. 1111111

Вариант 5. 1a₀111a₀a₀1111

Вариант 6. 11 a₀a₀111111

Вариант 7. 11 a₀111

Вариант 8. 111 a₀11

Вариант 9. 11 a₀a₀111

Вариант 10. 1 a₀1a₀111

Список используемой литературы

1. Гиндикин С.Г. «Алгебра логики в задачах» - М.: «ЕЕ Медиа», 2020г.

2. Игошин В.И. «Задачи и упражнения по математической логике и теории алгоритмов» - М.: «Академия», 2019г.

3. Игошин В.И. «Математическая логика и теория алгоритмов» - М.: «Академия», 2019г.

4. Спирин М.С., Спирина П.А. «Дискретная математика» - М.: «Академия», 2018г.