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

Методические рекомендации по проведению практических занятий

Скачать материал

Министерство науки и высшего образования и Российской Федерации

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

университет им. Н.И. Лобачевского»

 

Арзамасский филиал

 

отделение среднего профессионального образования

(Арзамасский политехнический колледж им. В.А. Новикова)

 

 

Методические рекомендации

для организации практических занятий

по учебной дисциплине

ЕН.02 ДИСКРЕТНАЯ МАТЕМАТИКА С ЭЛЕМЕНТАМИ

МАТЕМАТИЧЕСКОЙ ЛОГИКИ

 

Специальность среднего профессионального образования

09.02.07 ИНФОРМАЦИОННЫЕ СИСТЕМЫ И ПРОГРАММИРОВАНИЕ

 

 

 

 

 

 

 

 

 

Арзамас, 2018

Разработчик(и):

 

 

АФ ННГУ отделение СПО

«Арзамасский политехнический

колледж им. В.А. Новикова»             преподаватель                        С.В. Копьёва_________

    (место работы)                        (занимаемая должность)                (и.о., фамилия)

 

 

 

 

 

 

 

 

 

 

 

Одобрено на заседании  методической комиссии

_естественнонаучного и гуманитарного циклов___

Протокол №_______ от «_____» _________ 20____г.

Председатель МК ________________ /Н.Г. Кузнецова/

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

                                                                                                                                  

Введение………………………………………………………………………………………4

Практическое занятие 1: Упрощение формул логики с помощью равносильных преобразований……………………………………………………………………………….7

Практическое занятие 2: Представление булевой функции в виде СКНФ, СДНФ…..11

Практическое занятие 3: Представление булевой функции в виде многочлена  Жегалкина……………………………………………………………………………………22

Практическое занятие 4: Операции над множествами………………………………….24

Практическое занятие 5: Кванторные операции над предикатами…………………42

Практическое занятие 6: Операции над графами………………………………………..51

Практическое занятие 7: Конструирование машин Тьюринга…………………….........53

Литература...............................................................................................................................58

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Методические рекомендации предназначены для проведения практических занятий по дисциплине Дискретная математика с элементами математической логики  специальности СПО 09.02.07  Информационные системы и программирование, составлены в соответствии с Федеральным государственным образовательным стандартом, рабочим учебным планом, рабочей программой и календарно-тематическим планом учебной дисциплины ЕН.02 Дискретная математика с элементами математической логики  специальности среднего профессионального образования 09.02.07 Информационные системы и программирование.

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

Задачи: развитие у студентов современных форм математического мышления и умения ставить, исследовать и решать  задачи программирования.

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

Критериями оценки результатов практической работы обучающихся являются:

- уровень освоения обучающимся учебного материала;

-умение обучающегося использовать теоретические знания при выполнении практических задач;

- сформированность общеучебных умений;

- обоснованность и четкость изложения ответа;

- оформление материала в соответствии с требованиями.

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

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

Оценка «удовлетворительно» ставится, если работа выполнена не в полном объеме и  если в ходе работы были допущены и исправлены с помощью преподавателя существенные ошибки.

Оценка «неудовлетворительно» ставится, если при выполнении практической работы и подведении её результатов допущены и не исправлены существенные ошибки.

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

ОК.01. Выбирать способы решения задач профессиональной деятельности, применительно к различным контекстам.

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

ОК.04. Работать в коллективе и команде, эффективно взаимодействовать с коллегами, руководством, клиентами.

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

ОК.09. Использовать информационные технологии в профессиональной деятельности.

ОК.10. Пользоваться профессиональной документацией на государственном и иностранном языке.

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

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

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

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

- уровень освоения обучающимся учебного материала;

-умение обучающегося использовать теоретические знания при выполнении практических задач;

- сформированность общеучебных умений;

- обоснованность и четкость изложения ответа;

- оформление материала в соответствии с требованиями.

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

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

Оценка «удовлетворительно» ставится, если работа выполнена не в полном объеме и  если в ходе работы были допущены и исправлены с помощью преподавателя существенные ошибки.

Оценка «неудовлетворительно» ставится, если при выполнении практической работы и подведении её результатов допущены и не исправлены существенные ошибки.

Обучающиеся получают распечатанный или электронный вид с описанием этапов выполнения работы.

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

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

1.      Записать в тетради дату, тему и цель работы.

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

3.      Повторить теоретические основы, необходимые для выполнения работы и других практических действий, понять решения примеров, приведённых в методических рекомендациях к данному занятию.

4.      Выполнить работу по предложенному алгоритму действий.

 

 

 

 

 

 

 

 

 

Практическая работа 1: Упрощение формул логики с помощью

равносильных преобразований.

 

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

Время выполнения:  2 часа.

Теоретические основы

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

1.                        (   )

2.                        инверсия (отрицание)    

3.                        конъюнкция( логическое умножение)  , в остальных случаях=0)

4.                        а) дизъюнкция (логическое сложение)  , в остальных случаях=1)

    б) неравнозначность (либо…  либо)   в остальных случаях=0)

5. а) импликация (если…., то), , в остальных случаях=1)

б)      эквивалентность (тогда и только тогда)  в остальных случаях=0)

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

1. Закон тождества

A=A

2. Вторая форма закона не противоречия

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

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

5.      Вытекает из 2 закона

6. Свойства констант

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

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

9. Законы ассоциативности (сочетательный закон)

10. Закон дистрибутивности (распределительный закон)

11.   Законы поглощения

12 .Законы де Моргана

  1. Правила замены операции импликации

14.   Правила замены операции эквивалентности

15. Формула склеивания

16. Правила замены операции неравнозначности

·         ПРИМЕРЫ УПРОЩЕНИЯ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

(списать, подписывая номера законов, разобраться в решении)

Упрощение логических выражений

Закон 11 (поглощения)

Примеры

 

Примеры

 

 

Упростить выражение

 

a) 

b)

c)

d) 

e)

 

 

 

 

 

 

 

 

 

 

Практические задания

Упростить выражения и проверить результат по таблице истинности:

Задание 1(30 вариантов)

 

 

Задание 2 (30 вариантов)

 

Контрольные вопросы: 1. Какие преобразования называются равносильными?

2. Перечислите  логические законы.

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

Практическое занятие 2: Представление булевых функций в СКНФ,СДНФ.

 

 

Цель работы: отработать навыки в приведении формул к  совершенных нормальных форм; научиться применять и разрабатывать алгоритм построения совершенных нормальных форм.

Время выполнения: 2 часа.

Теоретические основы

Элементы математической логики

Логика высказываний

Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. Истинность или ложность предложения есть истинное значение высказывания. Сопоставим каждому высказыванию переменную равную 1, если оно истинно и равную 0 если оно ложно. Если P и Q – некоторые высказывания, то можно образовать высказывания  “P или Q”, “P и Q”, “не P”, введя операции дизъюнкции (), конъюнкции(&) и отрицания. Действия этих операций задаются таблицами истинности (таб. 1-3), каждой строке которых взаимно однозначно соответствуют набор значений составляющих высказываний и соответствующее значение составного высказывания.

           Таблица 1                         Таблица 2                        Таблица 3

P

Q

PQ

 

P

Q

P&Q

 

P

0

0

0

 

0

0

0

 

0

1

0

1

1

 

0

1

0

 

1

0

1

0

1

 

1

0

0

 

 

 

1

1

1

 

1

1

1

 

 

 

Операции дизъюнкции, конъюнкции и отрицания читаются как «или», «и» и «не».

Приведем основные законы, определяющие эти операции:

закон идемпотентности дизъюнкции и конъюнкции

                                          (1)

закон коммутативности  дизъюнкции и конъюнкции

                              (2)

закон ассоциативности дизъюнкции и конъюнкции

                                       (3)

закон дистрибутивности конъюнкции относительно  дизъюнкции и дизъюнкции относительно конъюнкции

                                  (4)

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

                                                                        (5)

законы де Моргана

                              (6)

законы склеивания

            (7)

законы поглощения

                            (8)

законы Порецкого

               (9)

Законы, определяющие действия с константой

                     (10)

Всякое высказывание, построенное с помощью операций «и», «или», «не», имеет некоторое истинное значение, зависящее от значений составляющих высказываний. Любое высказывание f может быть задано в виде таблицы истинности. Если значение высказывания зависит от n составляющих высказываний x1,x2,x3,…xn, то таблица истинности содержит 2n строк. Составляющие высказывания xi будем называть атомарными высказываниями или просто  переменными xi, рассматривая при этом сложное высказывание как функцию f от n переменных.

Построение совершенных нормальных форм.

Исчисление высказываний можно построить используя соответствующие таблицы истинности. Алгебра Буля простейшая в классе булевых алгебр; она является двухэлементной булевой алгеброй. Одним из элементов двухэлементной булевой алгебры является 0, так как булева алгебра является решеткой с дополнениями, поэтому вторым элементом этой алгебры является 1.

 Каждое высказывание и соответствующую ему булеву функцию f (x1,x2,…xn) можно представить в виде дизъюнкции конституент  , где

.

Пример 1. Рассмотрим пример высказывания f(x1,x2,x3), заданное таблицей истинности (таб. 4)

Таблица 4.

x1

х2

x3

f(x1,x2,x3)

 

x1

x2

x3

f(x1,x2,x3)

0

0

0

0

 

1

0

0

0

0

0

1

0

 

1

0

1

1

0

1

0

0

 

1

1

0

1

0

1

1

1

 

1

1

1

1

 

Согласно предыдущему утверждению функция  f(x1,x2,x3) может быть представлена в виде:

f(x1,x2,x3)= .

В дальнейшем представление булевой функции f(x1,x2xn) в виде дизъюнкции конституент будем называть совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x1,x2xn).

Переменную или ее отрицание будем называть первичным термом. Количество первичных термов, которые  образуют форму, называют сложностью L(f) этой формы.

Сложность СДНФ функции из примера равна 12. Для уменьшения сложности этой функции используют основные тождества алгебры Буля (законы 1-8). Согласно свойству идемпотентности дизъюнкции имеем:

f(x1,x2,x3)= .

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

f(x1,x2,x3)=

Окончательно имеем

f(x1,x2,x3)=

В результате получаем сложность L(f) функции f(x1,x2,x3) равную 5.

Аналогично можно каждое высказывание и соответствующую ему булеву функцию f (x1,x2,…xn)  представить в виде конъюнкции конституент  , где

.

В дальнейшем представление булевой функции f(x1,x2xn) в виде конъюнкции дизъюнкций будем называть совершенной конъюнктивной нормальной формой (СКНФ) функции f(x1,x2xn).

Для примера 1 функция  f(x1,x2,x3) может быть представлена в виде:

f(x1,x2,x3)=

ТОЖДЕСТВЕННО-ИСТИННЫЕ И ТОЖДЕСТВЕННО-ЛОЖНЫЕ ФОРМУЛЫ.

Определение. Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И.

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

В алгебре высказываний используют две нормальные формы: дизъюнктивную  и конъюнктивную нормальные формы формулы (ДНФ и КНФ).

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

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

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

Каждая формула, не равная тождественно И, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов.

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

 

1. Каждое логическое слагаемое формулы содержит все высказывания, входящие в формулу.

2. Все логические слагаемые формулы различны

3. Ни одно логическое слагаемое не содержит высказывание и его отрицание

4. Ни одно логическое слагаемое формулы не содержит одно и то же высказывание дважды.

 

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

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

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

3)Все полученные дизъюнкции связать в конъюнкцию.

 

1)     Образцы  решения

 

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

 Решение.

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

x

y

z

 

1

1

1

0

1

0

0

1

0

1

1

0

1

1

1

1

0

0

1

1

1

1

0

0

1

0

0

1

0

1

1

0

1

0

0

0

0

1

1

1

1

1

0

1

0

0

1

1

1

0

0

0

1

1

0

0

По таблице составляем дизъюнктивную нормальную форму (ДНФ). ДНФ в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции нескольких конъюнктов.

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

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

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

3)Все полученные конъюнкции связать в дизъюнкцию:

Выбираем в таблице строки, в которых булева функция принимает значение 1. В данном случае – это 2-ая, 3-ая, 4-ая, 6-ая и 7-ая строки.

Для каждой строки составляем конъюнкцию: если значение переменной равно 0. то берем ее отрицание, а  если  1, то берем саму переменную. Затем  составляем дизъюнкцию полученных конъюнкций:

 

.

Выбираем в таблице строки, в которых булева функция принимает значение 0. В данном случае – это 1-ая, 5-ая,  и 8-ая строки:

 

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

Метод Квайна основывается на применении двух основных соотношений.

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

;     

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

  

Используя соотношение склеивания получаем:

=,

=. Отсюда,

=()()- сокращенная ДНФ.

Булевы функции двух переменных

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

Суперпозицией системы

 называется любая функция f, полученная:

а) из переименованием переменных, ;

б) подстановкой вместо некоторых переменных функции  функций , ;

в) с помощью многократно применения пунктов а) и б).

Система S называется полной в Pk, если любая функция fPk представима в виде суперпозиции этой системы; система S называется базисом, если полнота S теряется при удалении хотя бы одной функции, где Pkk-значная логика.

Построим все булевы функции от двух переменных (таб.5)

Таблица5

переменные

Булевы функции

x1

x2

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Индекс i функциональной переменной fi , i=0,1,2,….,15, равен десятичному эквивалентному набору значений этой функции, читаемой сверху вниз. Приведем эти булевы функции:

f0(x1,x2)=0 – константа 0;

f1(x1,x2)=конъюнкция;

f2(x1,x2)= - левая коимпликация (читается «не если x1, то  x2 );

f3(x1,x2)= ;

f4(x1,x2)= - правая коимпликация;

f5(x1,x2)=

f6(x1,x2)= -  сложение по модулю 2 или функция неравнозначности, неэквивалентности;

f7(x1,x2)= - дизъюнкция;

f8(x1,x2)= - функция Вебба;

f9(x1,x2)=  - функция эквивалентности, равнозначности;

f10(x1,x2)= - отрицание;

f11(x1,x2)= - правая импликация (читается « если x2, то  x1 );

f12(x1,x2)= - отрицание;

f13(x1,x2)=  левая импликация (читается « если x1, то  x2 );

f14(x1,x2)=  - функция Шеффера;

f15(x1,x2)=1– константа 1

Практическое задание..

Задание 1.

 

1. Изучить теоретический материал по теме практического занятия

2. По заданной таблице истинности построить совершенную   дизъюнктивную  нормальную форму.

 

x1

х2

x3

F(f(x1,x2,x3))

 

x1

x2

x3

F(f(x1,x2,x3))

0

0

0

 

 

1

0

0

 

0

0

1

 

 

1

0

1

 

0

1

0

 

 

1

1

0

 

0

1

1

 

 

1

1

1

 

F(f(x1,x2,x3))- двоичная форма булевой функции.

1. F= 10010001

2. F= 00110101

3. F= 10100100

4. F= 01001000

5. F= 00100110

6. F= 00010111

7. F= 11001010

8. F= 11011000

9. F= 01011001

10.F= 10011001

11.F= 01000111

12.F= 11101000

13.F= 00100100

14.F= 10001110

15.F= 00101001

 

3. По заданной таблице истинности построить совершенную   конъюнктивную нормальную форму.

4.  Объясните полученные результаты

Задание 2

Построить таблицу истинности, найти СДНФ, СКНФ:

1в.

1.

2.   

3. 

     2в.

 1.

2. 

3.

 3в

1.

2.

3.

4в.

1.    

 

Построить таблицу истинности, найти СДНФ, СКНФ:

1

2. 3.

1     

2.   

3.

7в.

1.

2.  

3.

8в.

1.

2.  

3.

1 .

2. 

3.

 10в.

1.

2.

3.

11в.

1 .

2.

3.

12в.

1.

2.

3.

13в.

1.

2.

3.

14в

1.

2.

3.

15в

 

2.   

3. 

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

1. Что называется булевой функцией?

2. Докажите с помощью таблиц истинности основные законы алгебры Буля.

3. Что называют совершенной дизъюнктивной нормальной формой? Как выполняется ее построение?

4. Что называют совершенной конъюнктивной нормальной формой? Как выполняется ее построение?

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

 

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

Время выполнения: 2 часа.

Теоретические основы.

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

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

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

Решение:

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

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

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

Практические задания

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

 =;  ; ;

; .

2. Выбрать правило исключения альтернативной дизъюнкции :

Ответы:

3. Найти среди многочленов Жегалкина линейный:

 Ответы:

Ответы:

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

2. Построить таблицу истинности для функции , найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.

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

2. Построить таблицу истинности для функции, найти СДНФ,  упростить ее. Представить функцию в виде многочлена Жегалкина.

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

2. Построить таблицу истинности для функции, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.

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

2. Построить таблицу истинности для функции, найти СДНФ. Представить функцию в виде многочлена Жегалкина.

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

2. Построить таблицу истинности для функции, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.

Контрольные вопросы: 1.Определение многочлена Жегалкина.

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

Практическое занятие 4: Операции над множествами.

 

Цель работы: научиться выполнять операции над множествами.

Время выполнения: 2 часа

Теоретические основы

Основные понятия множества

Определение 1.1. Множеством называется совокупность каких-либо объектов, обладающим общим для всех характеристическим свойством. Это определение нельзя считать строгим, так как понятие множества является исходным понятием математики и не может быть определено через другие математические объекты. Один из основателей теории множеств Г. Кантор определял множество так: "Множество есть многое, мыслимое как целое".

Пример 1.1.

Следующие совокупности объектов являются множествами: множество деревьев в лесу, множество целых чисел, множество корней уравнения exsinx = 0.5.

Всякое множество состоит из элементов. Множества обозначают большими буквами, например А. В, С, а элементы  –  маленькими буквами, например, а, b, c.

Множество и его элементы обозначаются следующим образом:

А = {a1, a2, a3} – множество, состоящее из трех элементов;

А = {a1, a2, …} – множество, состоящее из бесконечного числа элементов.

Множество может состоять из элементов, которые сами являются множествами. Нужно различать элемент a и множество, состоящее из единственного элемента a.

Пример 1.2.

Множество А = {1, 2} состоит из двух элементов 1, 2; но множество  {А} состоит из одного элемента А

Если элемент a принадлежит множеству А, это записывается следующим образом:

a Î А. Если элемент a не принадлежит множеству А, то записывают так: a Ï А.

Пример 1.3.

Пусть А1 – множество простых чисел, А2 – множество целых чисел, a = 4. Тогда

a Î А2, a Ï А1.

Если все элементы множества А являются элементами множества В и наоборот, т. е. множества А и В совпадают, то говорят, что А = В.

Если каждый элемент множества А является элементом множества В, говорят, что множество А является подмножеством множества В, и записывают А Í В или  В Ê А. Отметим, что по определению само множество А является своим подмножеством, т.е. А Í А.

Если А Í В и В Í А, то по ранее введенному определению А = В.

Если А Í В и А ¹ В, то А есть собственное подмножество В, А Ì В. Если А не является собственным подмножеством В, то записывают А Ë В.

Пример 1.4.

Пусть А – множество четных чисел, В  – множество целых чисел, С множество нечетных чисел. Тогда

А Ì В, С Ì В, А Ë С, В Ë А.

Не надо смешивать отношение принадлежности (Î) и отношение включения (Í).

Пример 1.5.

Пусть А = {2}  – множество, состоящее из одного элемента, В = {{2}, {4}} – множество, состоящее из двух элементов, каждое из которых является одноэлементным множеством. Тогда имеют место следующие соотношения:

2 Î {2};

{2} Ì {{2}, {4}};

2 Ï {{2}, {4}}.

Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается Æ.Принято считать, что пустое множество является подмножеством любого множества, Æ Í А, где  А – любое множество. Таким образом, всякое множество содержит в качестве своих подмножеств пустое множество и само себя.

Пример 1.6.

Множество корней уравнения sinx = 2 является пустым.

Множество всех подмножеств данного множества А называется множеством-степенью и обозначается P(A). Множество P(A) состоит из 2n элементов (доказать самостоятельно).

Пример 1.7.

Пусть множество А = {1, 2} состоит из двух элементов 1, 2. Тогда множество P(A) включает в себя пустое множество Æ, два одноэлементных множества {1} и {2} и само множество А = {1, 2}, т. е.

P(A) = {Æ, {1}, {2}, {1, 2}}.

Мы видим, что множество P(A)  состоит из четырех элементов (4 = 22).

Существуют следующие способы задания множеств.

1. Перечислением элементов множества. Например:

A = {1, 3, 5, 7, 9} – конечное множество;

B = {1, 2, …, n, …} – бесконечное множество.

2. Указанием свойств элементов множества. Для этого способа пользуются следующим форматом записи: A = {açуказание свойства элементов}. Здесь a является элементом множества  A, a Î А.  Например:

A = {a ça – простое число} – множество простых чисел;

B = {b çb2 – 1 = 0,  b – действительное число} – множество, состоящее из двух элементов, B = {– 1, 1};

Z = {x ç = 1}– множество, состоящее из одного числа, x = 0.

Операции над множествами

Рассмотрим основные операции над множествами.

Объединением множеств А и В называется множество АÈВ, все элементы которого являются элементами хотя бы одного из множеств А или В:

АÈВ = {x ç xÎ А или  xÎВ}.

Из определения следует, что А Í АÈВ и В Í АÈВ.

Аналогично определяется объединение нескольких  множеств

Пример 1.8.

а) Пусть А = {4, 5, 6}, В = {2, 4, 6}.

Тогда АÈВ = {2, 4, 5, 6}.

б) Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3:

 А = {2, 4, 6, …}, В = {3, 6, 9, …}.

Тогда АÈВ множество чисел, которые делятся на 2 или на 3:

 АÈВ = {2, 3, 4, 6, 8, 9, 10, …}.

Пересечением множеств А и В называется множество АÇВ, все элементы которого являются элементами обоих множеств А и В:

АÇВ = {x ç xÎ А и xÎВ}.

Из определения следует, что АÇВ Í ААÇВ Í В и АÇВ Í АÈВ.

Аналогично определяется пересечение нескольких  множеств.

Пример 1.9.

Рассмотрим данные из примера 1.8.

а) Пусть А = {4, 5, 6}, В = {2, 4, 6}.

Тогда АÇВ  = {4, 6}.

б) Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3:

 А = {2, 4, 6, …}, В = {3, 6, 9, …}.

Тогда АÇВ  множество чисел, которые делятся и на 2 и на 3:

 АÈВ = {6, 12, 18, …}.

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

Пример 1.10.

Пусть А = {1, 2}, В = {2, 3}, C = {3, 4}.

Тогда АÇВÇC =Æ.

Относительным дополнением множества В до множества А называется множество А \ В, все элементы которого являются элементами  множества А, но не являются элементами  множества В:

А \ В = {x ç xÎ А и xÏВ}.

Пример 1.11.

Рассмотрим данные из примера 1.8.

а)  А = {4, 5, 6}, В = {2, 4, 6}.

 А \ В   = {4, 5}, В \ А= {2}.

б)  А = {2, 4, 6, …}, В = {3, 6, 9, …}.

Тогда А \ В  множество чисел, которые делятся  на 2, но не делятся на 3, а  В \ А – множество чисел, которые делятся  на 3, но не делятся на 2:

А \ В = {2, 4, 8, 10, 14, …}.

В \ А= {3, 9, 15, 21, 27, …}.

Симметрической разностью множеств А и В  называется множество А + В:

А + В = (А \ В) È (В \ А).

Пример 1.12.

Рассмотрим данные из примера 1.11.

а)  А = {4, 5, 6}, В = {2, 4, 6}.

 А \ В   = {4, 5}, В \ А= {2}, А + В = {2, 4, 5}.

б)  А = {2, 4, 6, …}, В = {3, 6, 9, …}, А \ В = {2, 4, 8, 10, 14, …}.

В \ А= {3, 9, 15, 21, 27, …}, А + В = {2, 3, 4, 8, 9, …}.

Универсальным множеством  называется такое множество U, что все рассматриваемые в данной задаче множества являются его подмножествами.

Абсолютным дополнением множества А  называется множество всех таких элементов x Î U, которые не принадлежат множеству А: = \ A.

Пример 1.13.

Пусть  А – множество положительных четных чисел.

Тогда U – множество всех натуральных чисел и  - множество положительных нечетных чисел.

Счетные множества

Определение 1.3. Множество, эквивалентное множеству натуральных чисел N = {1, 2, 3, …, n,…}, называется счетным.

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

Пример 1.20.

Следующие множества являются счетными.:

1. A1 = {–1, –2, …, – n, …};

2. A2 = {2,  22, …, 2n,…};

3. A3 = {2, 4, …, 2n,…};

4. A4 = {…, – n, …, – 1, 0, 1, …, n,…};

Чтобы установить счетность некоторого множества, достаточно указать взаимно однозначное соответствие между элементами данного множества и множества натуральных чисел. Для примера 1.19 взаимно однозначное соответствие устанавливается по следующим правилам: для множества A1: –n «  n; для множества A2: 2n «  n; для множества A3: 2n «  n; счетность множества A4 установлена в примере 1.19; 

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

Теорема 1. Всякое бесконечное подмножество счетного множества счетно.

Пример 1.21.

Множество A = {3, 6, …, 3n,…} счетно, т.к. A – бесконечное подмножество множества натуральных чисел, A Ì N.

Теорема 2. Объединение конечной или счетной совокупности счетных множеств счетно.

Пример 1.22.

Множество A = {0, 1, …, n,…} неотрицательных целых чисел счетно, множество B = {0, –1, …, –n,…} неположительных целых чисел  тоже счетно, поэтому множество всех целых чисел С = АÈB = {…, –n, …– 2, –1, 0, 1, 2, …, n, …} тоже счетно.

Теорема 3. Множество всех рациональных чисел, т.е. чисел вида , где  p и q целые числа, счетно.

Теорема 4. Если А = {a1, a2, …} и B = {b1, b2, …} – счетные множества, то множество всех пар С = {(ak, bn), k = 1, 2,…; n = 1, 2, …} счетно.

Пример 1.23.

Геометрический смысл пары (ak, bn) – точка на плоскости с рациональными координатами (ak, bn). Поэтому можно утверждать, что множество всех точек плоскости с рациональными координатами счетно.

Теорема 5. Множество всех многочленов P(x) = a0 + a1x + a2x2 + … + anxn любых степеней с рациональными коэффициентами  a0, a1, a2,  … an  счетно.

Теорема 6. Множество всех корней многочленов любых степеней с рациональными коэффициентами  счетно.

Множества мощности континуума

 

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

Теорема Кантора. Множество всех точек отрезка [0, 1] несчетно.

Доказательство.

Пусть множество точек отрезка [0, 1] счетно. Значит, эти точки можно перенумеровать, т. е. расположить в виде последовательности x1, x2  … xn, … .

 

ris7

Рис. 1.7

 

Разобьем отрезок [0, 1] на три равные части. Где бы ни находилась точка x1, она не может принадлежать всем отрезкам , , . Поэтому среди них есть отрезок D1, не содержащий точку x1 (рис. 1.7). Возьмем этот отрезок D1 и разделим его на три равные части. Среди них всегда есть отрезок D2, не содержащий точку x2. Разделим  этот отрезок на три равные части и т. д. Получим последовательность отрезков D1 É D2 É D3 ÉÉDn É… . В силу аксиомы Кантора сходится к некоторой точке x при n ® ¥. По построению эта точка x принадлежит каждому отрезку D1, D2,  D3,…, Dn, …, т. е. она не может совпадать ни с одной из точек  x1, x2,  … xn, …, т. е. последовательность x1, x2  … xn, …не исчерпывает всех точек отрезка [0, 1], что противоречит первоначальному предположению. Теорема доказана.

Множество, эквивалентное множеству всех точек отрезка [0, 1] называется множеством мощности континуума.

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

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

Пример 1.24.

Из рис. 1.8 следует, что множество точек параболы y = x2 эквивалентно множеству точек  прямой  –¥ < x < ¥ и, следовательно, имеет мощность континуума.

ris8

Рис.1.8

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

Теорема 1. Множество всех подмножеств счетного множества счетно.

Теорема 2. Множество иррациональных чисел имеет мощность континуума.

Теорема 3. Множество всех точек n-мерного пространства при любом n имеет мощность континуума.

Теорема 4. Множество всех комплексных чисел имеет мощность континуума.

Теорема 5. Множество всех непрерывных функций, определенных на отрезке [a, b] имеет мощность континуума.

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

Теорема о множествах высшей мощности. Множество всех подмножеств данного множества имеет более высокую мощность, чем данное множество.

Из этой теоремы следует, что множеств с максимально большой мощностью не существует.

Практические задания

 

Вариант № 1

1. Фирма имеет 100 предприятий, причем каждое предприятие выпускает хотя бы одну продукцию вида А, В, С. Продукцию всех трех видов выпускают 10 предприятий, продукцию А и В – 18 предприятий, продукцию А и С – 15 предприятий, продукцию В и С – 21 предприятие. Число предприятий, выпускающих продукцию А  равно числу предприятий, выпускающих продукцию В и равно числу предприятий, выпускающих продукцию С. Найти число всех предприятий.

2. Упростить:   È  È.

3. Является ли множество А = {1, 2, 3} подмножеством множества  В = {{1}, {2, 3}}?

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

5. Эквивалентны ли множества A = {x: x2 – 8x + 15= 0} и B = {2, 3}?

Вариант № 2

1. В группе спортсменов 30 человек. Из них 20 занимаются плаванием, 18 – легкой атлетикой и 10 – лыжами. Плаванием и легкой атлетикой занимаются 11 человек, плаванием и лыжами – 8, легкой атлетикой и лыжами – 6 человек. Сколько спортсменов занимаются всеми тремя видами спорта?

2. Упростить:  AÇ(AÈB)

3. В каком случае ААÇВ?

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

5. Какое из множеств A = {1, 4, 9, 16, 25,…} и B = {1,  1/2, 1/4, 1/6, 1/8,…} имеет большую мощность?

Вариант № 3

1. В студенческой группе 20 человек. Из них 10 имеют оценку “отлично” по английскому языку, 8 - по математике, 7 - по физике, 4 - по английскому языку и по математике, 5 - по английскому языку и по физике, 4 - по математике и по физике, 3 - по английскому языку, по математике и по физике. Сколько студентов группе не имеют отличных оценок?

2. Упростить:  (A\B) È (A\B).

3. Найти все подмножества множества  A= {1, 2, 3, 4).

                                                                4

4. Пусть  An = {0,   1/2n}. Найти      U  An.

                                                              n=1

5. Доказать, что множества точек контуров всех треугольников эквивалентны.                  

Вариант № 4

1. В классе 20 человек. На экзаменах по истории, математике и литературе 10 учеников не получили ни одной пятерки, 6 учеников получили 5 по истории, 5 – по математике и 4 – по литературе; 2 - по истории и математике, 2  - по истории и литературе, 1 - по математике и литературе. Сколько учеников получили 5 по всем предметам?

2. Упростить: (AÇB) È (AÇB).

3. Является ли множество А = {1, 2, 3} подмножеством множества  В = {{1}, {2, 3}}?

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

5. Эквивалентны ли множества A = {2x, 0<x< ¥} и B = {2n, n = 1, 2, …}?

Вариант № 5

1. В спортивном лагере 100 человек, занимающихся плаванием, легкой атлетикой и лыжами.  Из них 10 занимаются и плаванием, и легкой атлетикой, и лыжами, 18 – плаванием и легкой атлетикой, 15 – плаванием и лыжами, 21 – легкой атлетикой и лыжами. Число спортсменов, занимающихся плаванием, равно числу спортсменов, занимающихся легкой атлетикой, и равно числу спортсменов, занимающихся лыжами. Найти это число.

2. Упростить:  (AÈB) È(AÈB).

3. Найти все подмножества множества  A= {1, 2, 3, 4).

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

5. Доказать, что множества точек контуров всех треугольников эквивалентны.                  

Вариант № 6

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

2. Верно или неверно равенство: (A \ B) È(AÇB) = A?

 

3. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

5. Эквивалентны ли множества A = {x: x2-8x+15= 0} и B = {2, 3}?

Вариант № 7

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

2. Упростить:  (AÈB) È (AÇB).

3. Доказать, что множество точек  A= {(x, y): y = ½x½, -,  – 1 £ x £ 1}  несчетно.

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

5. Эквивалентны ли множества A = {y: yx3, 1< x <2} и B = {y: y = 3x, 3< x < ¥}?

Вариант № 8

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

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А  \ (В È С) = (А \ В) È С?

3. В каком случае ААÇВ?

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

5. Эквивалентны ли множества A = {xx2 –3x + 2 = 0} и B = {1, 3}?

Вариант № 9

1. Опрос группы студентов показал, что 70% из них любят ходить в кино, 60% в театр, 30% на концерты. В кино и театр ходят 40% студентов, в кино и на концерты – 20%, в театр и на концерты – 10%. Сколько студентов (в %)  ходят в кино, театр и на концерты?

2. Верно или неверно равенство: (AÇB) Ç (A È В) = В?

3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ  = С.

5. Эквивалентны ли множества A = {xx3 – 1 = 0} и B = {x: x2 – 3x + 2 = 0}?

Вариант № 10

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

2. Упростить:  (È) \ (A È B).

3. Верно или неверно равенство: (AÇB) Ç (A È В) = В?

4. Найти все подмножества множества  O= { c, d}.

5. Эквивалентны ли множества A = {(x, y): y = lnx, 0 < x < ¥} и B = {(x, y): y = sinx,  –¥ <x < ¥}?

Вариант № 11

1. При обследовании рынка спроса инспектор указал в опросном листе следующие данные. Из 1000 опрошенных 811 покупают жевательную резинку "Дирол", 752 – "Орбит" , 418 – "Стиморол", 570 – "Дирол" и "Орбит", 356 – "Дирол" и "Стиморол", 348 – "Орбит" и "Стиморол", 297 – все виды жевательной резинки. Показать, что инспектор ошибся.

2. Упростить: È(B \ (AÈB)).

3. Придумать пример множеств А, В, С, так, чтобы выполнялось равенство: А È В  = С, причем А – конечное множество, В  и С – счетные множества.

4. Найти все подмножества множества  A= {a, b, c, d}.

5. Пусть A – множество целых чисел, а B – множество четных чисел. Какие из следующих отношений справедливы: а) A =B; б) A ~ B; в) A ÉB; г) A ÊB; д) A ËB; е) A Î B.

Вариант № 12

1. Всем участникам автопробега не повезло. 12 из них увязли в песке – пришлось толкать машину, 8 понадобилась замена колеса,  у шестерых перегрелся мотор, пятеро и толкали машину и меняли колесо, четверо толкали машину и остужали мотор, трое меняли колесо и остужали мотор. Одному пришлось испытать все виды неполадок. Сколько было участников?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В ÇС) = (А \В) ÇС?

3. Доказать, что множество точек  A = {y: y = 2n, n = 1, 2, …} счетно.

4. Найти все подмножества множества  A= {m, n, h, d}.

5. Эквивалентны ли множества A = {(x, y): yx3, 1< x <2} и B = {(x, y): y = 3x, 3< x < ¥}?

Вариант № 13

1. Из 10 участников ансамбля шестеро умеют играть на гитаре, пятеро – на ударных инструментах, пятеро – на духовых. Двумя инструментами владеют: гитарой и ударными – трое, ударными и духовыми – двое, гитарой и духовыми – четверо. Один человек играет на всех трех  инструментах. Остальные участники ансамбля только поют. Сколько певцов в ансамбле?

2. Верно или неверно равенство: ÇС) = ÇС ÈÇС ?

3. Записать решение системы неравенств

   x-2 > 0

   x-5 < 0

в виде пересечения двух множеств.

4. Найти все подмножества множества  G= {a, c, d}.

5. Доказать, что множества A = {(x, y): yx3, 1< x <2} и B = {y: y = 3x, 3< x < ¥} эквивалентны.

Вариант № 14

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

2. Верно или неверно соотношение: AÇÇC Ì A È В?

3. Придумать пример множеств А, В, С, так, чтобы выполнялось равенство: А È В  = С, причем А, В, и С – счетные множества.

4. Найти все подмножества множества  P= {a, d}.

5. Эквивалентны ли множества A = {y: y = 3x, 0<x< ¥} и B = {y: y = 3n, n = 1, 2, …}?

Вариант № 15

1. В день авиации на аэродроме всех желающих катали на самолете, планере, дельтаплане. На самолете прокатились 30 человек, на планере – 20, на дельтаплане – 15. И на самолете, и на планере каталось 10 человек, на самолете и дельтаплане – 12, На планере и дельтаплане – 5. Два человека прокатились и на самолете, и на планере, и на дельтаплане. Сколько было желающих прокатиться?

2. Верно или неверно равенство: (A È B) \ A = B \ A ?

3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Найти все подмножества множества  H= { c, d}.

5. Доказать, что множества A = {y: y = lnx, 0 < x < ¥} и B = {y: y = sinx,  –¥ <x < ¥} эквивалентны.

Вариант № 16

1. Все грибники вернулись домой с полными корзинами. У десятерых из них в  корзинах были белые грибы, у восемнадцати – подберезовики, у двенадцати – лисички. Белые и подберезовики были в шести корзинах, белые и лисички – в четырех, Подберезовики и лисички – в пяти. Все три вида грибов были у двух грибников. Сколько было грибников?

2. Верно или неверно равенство: (A È B) \ (AÇB) = AÇÈÇB?

3. Доказать, что множество точек  A= {(x, y): y = ½x½, -,  – 1 £ x £ 1}  несчетно.

4. Найти все подмножества множества  A= {a, b, c, d}.

5. Пусть A – множество точек отрезка [0, 1], а B – множество всех точек числовой оси. Какие из следующих отношений справедливы: а) A =B; б) A ~ B; в) A ÉB; г) A ÊB; д) A ËB; е) A Î B.

Вариант № 17

1. Все туристы взяли в поход консервы. Шесть человек взяли тушенку, пять – сгущенку, восемь – кашу (с мясом). У троих в рюкзаках была тушенка и сгущенка, у двоих – тушенка и каша, у троих – сгущенка и каша, и только в одном рюкзаке лежали все три вида консервов. Сколько было туристов?

2. Верно или неверно равенство: ÇС = С \ (С Ç (AÈB))?

3. Пусть A – множество решений уравнения x2 – 3x + 2 = 0. Записать это множество двумя различными способами.

4. Найти все подмножества множества  A= {a, d}.

5. Эквивалентны ли множества A = {xx2 –3x + 2 = 0} и B = {2, 3}?

Вариант № 18

1. Было опрошено 70 человек. В результате опроса выяснили, что 45 человек знают английский язык, 29 – немецкий и 9 – оба языка. Сколько человек из опрошенных не знает ни английского, ни немецкого языков?

2. Верно или неверно равенство: (A È B) \ (AÇB) = AÇÈÇB?

3. Найти все подмножества множества  F= {a,b,c,d,e,f}.

4. Пусть A – множество решений уравнения x2 – 3x + 2 = 0. Записать это множество двумя различными способами.

5. Счетно ли множество {(x, y):  y = 3x, 0<x< ¥}?

Вариант № 19

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

2. Упростить .

3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Найти все подмножества множества  A= {x, y, r, f, d}.

5. Эквивалентны ли множества A = { 2n, n = 1, 2, …} и B = {n2, n = 1, 2, …}?

Вариант № 20

1. Предприятие объявило набор рабочих на должности токаря, слесаря и сварщика. В отдел кадров обратились 25 человек. Из них 10 человек владели профессией токаря, 15 – слесаря, 12 – сварщика. Профессией и токаря и слесаря владели 6 человек, и токаря, и сварщика – 5 человек, и слесаря и сварщика – 3 человека. Сколько человек владеют всеми тремя профессиями?

2. Верно или неверно равенство: \  = \ ?

3. Привести примеры множеств А, В и С , для которых одновременно выполняются равенства А È В È С = А   и    А Ç В Ç С = С.

4. Найти все подмножества множества  A= {x, z}.

5. Можно ли построить взаимно-однозначное соответствие между множеством рациональных чисел отрезка  [0, 1] и множеством рациональных чисел из этого интервала? Ответ обосновать.

Вариант № 21

1. Оказалось, что в группе туристов 15 человек были раньше во Франции, 19 – в Италии, 8 – в Германии. 9 туристов были во Франции и  в Италии, 7 – во Франции и  в Германии, 6 –  и  в Италии, и в Германии. 4 туриста были во всех трех странах. Сколько туристов были хотя бы в одной из трех стран?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А  \ (В Ç С) = (А \ В) Ç ?

3. Привести примеры множеств А и В, для которых равенство È В =

а) выполняется; б) не выполняется.

4. Найти все подмножества множества  S= {x, y, z, t, e}.

5. Найти мощность множества точек окружности с центром в точке (0, 0) и радиусом 1.

Вариант № 22

1. Группе студентов из 30 человек была предложена контрольная работа из трех задач. Первую задачу решили 15 студентов, вторую – 13, третью – 12. Первую и вторую задачи решили 7 человек, первую и третью – 6, вторую и третью – 5 человек. Все три задачи решили 2 студента. Сколько студентов из группы не решили ни одной задачи?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство:  А  \ (В  È С) = (А \ В) Ç ?

3. Привести пример двух бесконечных множеств А и В, таких, что мощность множества А больше мощности множества В.

4. Найти все подмножества множества  D= { y, z}.

5. Найти мощность множества точек гиперболы   y =   при  x Î ( 3, ¥).

Вариант № 23

1. Анализ историй болезней  группы из 20 детей показало, что 10 детей  болели ветрянкой, 6 – корью, 5 – свинкой. Ветрянкой и корью болели 3 ребенка, ветрянкой и свинкой – 3, корью и свинкой – 2. Всеми тремя болезнями болел один ребенок. Сколько детей не болели ни одной из перечисленных болезней?

2. Верно или неверно равенство: ÇС) =  ÇÇ С?

3. Доказать, что множество точек  A= {(x, y): y = ½x+1½,  – 1 £ x £ 1}  несчетно.

4. Найти все подмножества множества  A= {xz}.

5. Пусть A – множество точек отрезка [1, 2], а B – множество  точек интервала (0, 3). Какие из следующих отношений справедливы: а) A =B; б) A ~ B; в) A Ì B; г) A Ê B; д) A ËB; е) A Î B.

Вариант № 24

1. В книжный киоск привезли для продажи 100 книг Пушкина, Лермонтова и Тургенева. Книги Пушкина купили 60 человек, книги Лермонтова – 50, книги Тургенева – 30 человек. Книги Пушкина и Лермонтова купили  40 человек, книги Пушкина и Тургенева – 20, книги Лермонтова и Тургенева – 10 человек. Пять человек купили книги всех трех писателей. Сколько человек не купили ни одной из перечисленных книг?

2. Верно или неверно равенство: \  = \ ?

3. Привести примеры множеств А, В и С таких, что равенство А È В È С = С

а) справедливо; б) несправедливо.

4. Найти все подмножества множества  В= {x, y, z, k}.

5. Можно ли построить взаимно-однозначное соответствие между множеством натуральных чисел N  и множеством действительных чисел отрезка  [0, 1]? Ответ обосновать.

Вариант № 25

1. Группа научных работников состоит из 100 человек. Из них 70 человек владеют английским языком, 50 – немецким, 40 – французским, 30 – английским и немецким, 25 – английским и французским, 15 – французским и немецким. Хотя бы один язык знает каждый научный работник. Сколько человек владеют всеми тремя языками?

2. Упростить: (A \ (AÇB)) È В.

3. Привести примеры множеств А, В и С так, чтобы A Î B, В Ì С.

4. Найти все подмножества множества  С= {x, y}.

5. Можно ли утверждать, что множество всех положительных пятизначных чисел счетно? Ответ обосновать.

Вариант № 26

1. На курсы иностранных языков записалось 100 человек. Оказалось, что 70 человек будут изучать английский язык, 60 человек – французский и 30 человек  - немецкий. Английский и французский собираются изучать 40 человек, английский и немецкий – 20, французский и  немецкий – 10. Сколько студентов будут изучать все три языка?

2. Упростить равенство: (A Ç С )\ (С Ç (A ÈB)).

3. Привести пример двух различных бесконечных множеств А и В, таких, что мощность множества А равна мощности множества В.

4. В каком случае A ÈB  = А Ç В?

5. Эквивалентны ли множества A = {xx3 – 1 = 0} и B = {x: x2 – 3x + 2 = 0}?

Вариант № 27

В команде бегунов десять спортсменов бегают на длинные дистанции, восемнадцать – на средние, двенадцать – на короткие. На длинные и средние дистанции бегают пять спортсменов, на средние и короткие – шесть. На длинные и короткие дистанции не бегает никто. Сколько бегунов в команде?

2. Верно или неверно равенство: ÈС) =  ÈÈ С?

3. В каком случае A ÈB  = А Ç В?

4. Эквивалентны ли множества A = {xx3 – 1 = 0} и B = {x: x2 – 3x + 2 = 0}?

5. Можно ли утверждать, что множество всех положительных чисел имеет меньшую мощность, чем множество всех действительных чисел? Ответ обосновать.

Вариант № 28

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

2. Упростить:  Ç  (È).

3. Привести пример двух бесконечных множеств А и В, таких, что мощность множества А меньше мощности множества В.

4. Доказать, что множество точек  A = {y: y = 2n, n = 1, 2, …} счетно.

5. Эквивалентны ли множество рациональных чисел отрезка  [0, 1] и множество рациональных чисел из этого интервала? Ответ обосновать.

Вариант № 29

1. В классе 20 детей. Из них 10  дополнительно занимаются в музыкальной школе, 6 – теннисом, 5 – китайским языком. Музыкальную школу и занятия по теннису посещают три ребенка, музыкой и китайским языком занимаются трое, теннисом и китайским языком двое. Всеми тремя видами дополнительных занятий занимается один ребенок. Сколько детей не занимается ни одним из перечисленных занятий?

2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В ÈС) = (А \В) Ç?

3. Доказать, что множество точек  A = {y: y = 2n, n = 1, 2, …} счетно.

4. Привести примеры множеств А, В и С , для которых одновременно выполняются равенства А È В È С = А   и    А Ç В Ç С = С.

5. Эквивалентны ли множества A = {(x, y): yx2, 1< x <2} и B = {(x, y): y = 2x, 3< x < ¥}?

Вариант № 30

1. В цеху имеется 25 станков, которые могут выполнять три вида операций: А, В и С. Из них 10 станков выполняют операцию А, 15 – В, 12 – С. Операции А и В могут быть выполнены на 6 станках, А и С – на 5, В и С – на 3 станках. Сколько станков могут выполнять все три операции?

2. Верно или неверно равенство: \  = \ ?

3. Привести примеры множеств А, В и С , для которых одновременно выполняются равенства А È В È С = А   и    А Ç В Ç С = С.

4. Доказать, что множество точек  A = {y: y = 2n, n = 1, 2, …} счетно.

5.Можно ли построить взаимно-однозначное соответствие между множеством действительных чисел отрезка  [0, 1] и множеством действительных чисел интервала (0, 1)? Ответ обосновать.

 

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

1. Пусть a Î А. Следует ли отсюда, что {a} А?

2. В каком случае ААÇВ?

3. Назовите множество, которое является подмножеством любого множества.

4. Может ли быть множество эквивалентно своему подмножеству?

5. Мощность какого множества больше: множества натуральных чисел  или  множества точек  отрезка [0, 1]?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Практическое занятие 5. Кванторные операции над предикатами.

 

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

Время выполнения: 2 часа.

Теоретические основы

1.      Кванторные операции.

 

Пусть имеется предикат Р(х), определенный на мно­жестве М. Если а - некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает

этот предикат в высказывание - Р(а). Такое высказыва­ние называется единичным. Наряду с образованием из предикатов единичных высказываний в логике преди­катов рассматривается еще две операции, которые пре­вращают одноместный предикат в высказывание.

 Квантор всеобщности. Пусть Р(х) — предикат, определенный на множестве М. Под выражением " х Р(х) понимают высказывание, истинное, когда Р(х) истинно

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

Соответствующее ему словесное выражение будет: «Для всякого х Р(х) истинно». Символ " называют кванто­ром всеобщности.

Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании " х Р(х)  переменную х называют связанной квантором ".

Квантор существования. Пусть Р(х) — предикат, определенный на множестве М. Под выражением $х Р(х) понимают высказывание, которое является истинным, если  существует элемент х Î М, для которого Р(х) истинно, и ложным в противном случае. Это высказывание уже не зависит от х.

 Соответствующее ему словесное выражение будет: «Существует х, при котором Р(х) истинно». Символ $ называют квантором существования. В высказывании  $х Р(х)  переменная х связана квантором $.

Приведем пример употребления кванторов. Пусть на множестве N натуральных чисел задан предикат Р(х): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания: "хÎ N Р(х) - «Все натуральные числа кратны 5»; $хÎN P(x) — «Су­ществует натуральное число, кратное 5». Очевидно, пер­вое из этих высказываний ложно, а второе истинно.

Ясно, что высказывание " х Р(х) истинно только в том единственном случае, когда Р(х) - тождественно истинный предикат, а высказывание $х Р(х)   ложно только в том единственном случае, когда Р(х) — тождествен­но ложный предикат.

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат Р(х,у). Применение кванторной операции к предикату Р(х,у) по переменной х ста­вит в соответствие двухместному предикату Р(х,у) одноместный предикат "x P(x, у} (или одноместный предикат $х Р(х, у)), зависящий от переменной у и не зависящий от переменной х. К ним можно применить кванторные операции по переменной у, которые приведут уже к высказываниям следующих видов:

"y"xP(x,y), $y"xP(x,y), "y$xP(x,y), $у$хР(х,у).

Например, рассмотрим предикат Р(х, у): « х кратно у », определенный на множестве N. Применение кванторных операций к предикату Р(х,у) приводит к восьми воз­можным высказываниям:

1. "y"xP(x,y) - «Для всякого у и для всякого х  у является делителем х».

2. $y"xP(x,y) - «Существует у, которое является делителем всякого х».

3. "y$xP(x,y)- «Для всякого у существует х такое, что х делится на у».

4. $у$хР(х,у) - «Существует у и существует х такие, что у является делителем х».

5. "х"уP(x,y) - «Для всякого х и для всякого у у является делителем х».

6. "х$уP(x,y) - «Для всякого х существует такое у, что х делится на у».

7. $х$уP(x,y) - «Существует х и существует у такие, что у является делителем х».

 8. $х"уР(х,у)  - «Существует х такое, что для всякого у х делится на у».

 Высказывания 1, 5 и 8 ложны, а высказывания 2, 3, 4, 6 и 7 истинны.

Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит, и его логическое значение (например, высказывания 3 и 8).

Рассмотрим предикат – Р(х), определенный на мно­жестве М = {a1, a2,…, an}, содержащем конечное число элементов. Если предикат Р(х) является тождественно истинным, то истинными будут высказывания P(a1), P(a2),…, P(an). При этом истинными будут высказывание "хР(х) и конъюнкция P(a1) P(a2)… P(an).

Если хотя бы для одного элемента akÎM P(ak) окажется ложным, то ложными будут высказывание "хР(х) и конъюнкция P(a1) P(a2)… P(an). Значит, справедлива равносильность:

"хР(х) º P(a1) P(a2)… P(an).

Аналогичным образом можно доказать справедливость равносильности:

$хР(х) º P(a1)V P(a2)V…VP(an).

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

Примеры:

1.              Какие из следующих высказываний тождественно ложные , а какие тождественно истинные, если область определения М = R?

а) $х (х +5 = х + 3) – тождественно ложное высказывание, т.к. ни при каком х равенство неверно;

б) "х (х2 +х + 1 > 0) – тождественно истинное высказывание: левую часть неравенства перепишем в виде (х + ½)2 + ¾ , эта сумма больше нуля при любом х;

в) $х ((х2 – 5х +6 ³ 0)(х2 – 2х + 1 >0)) – высказывание тождественно истинное, если пересечение областей истинности логически умножаемых предикатов не пусто, и ложное, в противном случае.

Первое неравенство представим в виде (х –2)(х – 3)³ 0, решением которого являются   хÎ(-¥; 2]È [3; +¥).

Второе неравенство представим в виде (х – 1)2> 0 . решением которого являются все х ¹ 0.

Пересечение областей истинности: (-¥; 0)È(0; 2]È[3; +¥)¹Æ, значит, высказывание тождественно истинное.

2.              Предикат Р(х, у): «x<y» определен на множестве М=N´N.

а) какие из предикатов тождественно истинные, какие тождественно ложные: $хР(х, у), "хР(х, у), $уР(х, у), "уР(х, у)?

$хР(х, у) – не является ни тождественно истинным, ни тождественно ложным: при у =1 $хР(х, у) = 0, т.к. нет натурального числа меньше 1; при у >1 $хР(х, у) = 1, например, х =1. значит, область истинности предиката у>1.

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

$уР(х, у) – тождественно истинный, т.к. для всякого каждого натурального числа можно найти большее натуральное число.

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

б) какие из высказываний  истинные, какие  ложные:

$х"уР(х, у); "х$уР(х, у).

$х"уР(х, у) – ложное высказывание, т.к. не существует натурального х меньшего любого натурального у (для у =1).

"х$уР(х, у) – истинное высказывание, т.к. для любого натурального х существует большее натуральное число у.

3.              Предикаты А(х, у) и В(у, z) определены на множестве МхМ, где М={a, b, c}. Записать формулу $xA(x, y)"zB(y, z) без кванторных операций. Предикат $xA(x, y) равносилен дизъюнкции A(a, y) vA(b, y) vA(c, y). Предикат )"zB(y, z) равносилен конъюнкции              B(y, a)L B(y, b) LB(y, c). Тогда справедлива равносильность:

 $xA(x, y)"zB(y, z)º( A(a, y) vA(b, y) vA(c, y))L B(y, a)L B(y, b) LB(y, c).

2. Формулы логики предикатов.

В логике предикатов будем пользоваться следующей символикой:

1.               Символы р, q, r, ... — переменные высказывания, принимающие два значения: 1 - истина, 0 — ложь.

2.               Предметные переменные - х, у, z, .... которые пробегают значения из некоторого множества М; x°, у°, z°, ... -предметные константы, то есть значения предметных пере­менных.

4.               Р( .), F( .) - одноместные предикатные переменные; q(.,.,...,.), R(.,.,...,.)   n-местные предикатные переменные. P0(.), Q0(. , . , …,.) - символы постоянных предика­тов.

5.              Символы логических операций:L, v, ®,- .

6.              Символы кванторных операций: "x , $x.

7.              Вспомогательные символы: скобки, запятые.

Определение формулы логики предикатов:

1.              Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).

2.              Если F( .,.,...,.) – n- местная предикатная переменная или постоянный предикат, а х1, х2, …, хn - предметные переменные или предметные постоянные (не обяза­тельно все различные), то F(х1, х2, …, хn) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.

3.              Если А и В — формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой - свободной, то слова А v В , А& В, А®В есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, являются свободными, а те, которые были связанными, являются связанными.

4.              Если А - формула, то  - формула, и характер предметных переменных при переходе от формулы А к формуле  не меняется.

5.              Если А(х) - формула, в которую предметная переменная х входит свободно, то слова "xA(х) и $хА(х) являются формулами, причем предметная переменная входит в них связанно.

6.              Всякое слово, отличное от тех, которые названы формулами в пунктах 1-5, не является формулой.

Например, если Р(х) и Q(x, у) - одноместный и двухместный предикаты, а q, r -  переменные высказывания, то  формулами будут слова: q, Р(х), P(x)Q(x°,y),

"хР(х)® $xQ(x, у),

Не является формулой слово: "xQ(x, y) ® Р(х). Здесь нарушено условие п.3, так как в формулу"xQ(x, y)  пе­ременная х входит связано, а в формулу Р(х) переменная х входит свободно.

Выражение "у($уР(х,у))VQ(x) не является формулой, т.к. квантор всеобщности на у навешан на формулу $уР(х,у), в которой переменная у уже связана квантором существования.

Выражение "у, хР(х, у) не является формулой, т.к. переменной х не присвоен квантор.

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

3.               Значение формулы логики предикатов.

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множе­ство М, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.

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

 Рассмотрим формулу $y"z(P(x,y)®P(y,z)).  Двухместный предикат Р(х,у) определен на множестве М х М , где М = {0,l,2,...,n,..} . В формулу  входит переменный предикат Р(х,у), предметные переменные х, у, z, две из которых у и zсвязанные кванторами, а х - свободная.

Возьмем за конкретное значение предиката Р(х,у) фиксированный предикат Р°(х,у): «х<у», а свободной переменной х придадим значение х0 = 5 ÎМ . Тогда при значениях у, меньших х° = 5 предикат Р00,y) при­нимает значение ложь, а импликация Р(х, у) ® Р(у, z) при всех z Î М принимают значение истина, то есть высказывание $y"z(P0(x,y)®P0(y,z)) имеет значение «истина».

Рассмотрим еще пример на вычисление значения формулы.

Дана формула "x(P(x)Q(x)®R(x)), где предикаты определены на множестве N. Найти ее значение , если P(x): «х делится на 3», Q(x): «х делится на 4», R(x): «х делится на 2».

Данная формула является высказыванием, т.к. х связанная переменная. Следовательно, значение формулы будет зависеть только от значений предикатных переменных. P(x)Q(x)- означает, что х делится на 12. Тогда предикат P(x)Q(x)®R(x) : «если х делится на 12, то х делится на 2» - тождественно истинный, следовательно формула "x(P(x)Q(x)®R(x) принимает значение «истина».

4.  Равносильные формулы логики предикатов.

Определение 1. Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М.

Определение 2. Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области.

Здесь, как в алгебре высказываний, для равносильных формул принято обозначение  А º В .

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей. Пусть А(х) и В(х) - переменные предикаты, а С - переменное высказывание. Тогда:

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

Пример: Найти отрицание формул

Докажем справедливость какой-либо из остальных равносильностей, например, равносильности 10: $х(А(х)vB(x))º$xA(x)v$xB(x).

Для доказательства достаточно рассмотреть два случая:

1.              Пусть А(х) и В(х) – тождественно ложны. Тогда будет тождественно ложным предикат А(х)vB(x) и будут ложными высказывания $хА(х)v$xB(x), $х(А(х)vB(x)).

2.              Пусть теперь хотя бы один из предикатов не тождественно ложный, например, А(х). Тогда не будет тождественно ложным предикат А(х)vB(x), и будут истинными высказывания $хА(х), $х(А(х)vB(x)), а значит истинны и исходные формулы.

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

Отметим, что формула "х[А(х) v В(х)] не равносильна формуле "хА(х) v "xB(x), а формула

$х[А(х)L В(х)] не равносильна формуле $хА(х)L $хВ(х) . Однако, справедливы равносильности:

Рассмотрим еще примеры применения равносильных преобразований.

На множестве М определены предикаты А(х) и В(х). Доказать, что высказывание "хА(х) ложно, если истинно высказывание

Преобразуем формулу:

значит, "хА(х)=0.

Каким условиям удовлетворяют области истинности предикатов А(х) и В(х), определенных на множестве М, если истинно высказывание: .

тогда $хА(х)=0, значит, IA = Æ, IB – любое подмножество области определения М.

Практические задания

1.              Какие из следующих выражений являются формулами? В каждой формуле выделить свободные и связанные переменные:

2.              Даны утверждения А(n):«число п делится на 3», В(n): «число п делится на 2», С(n): «число п делится на 4», D(n): «число п делится на 6», Е(n): «число п делится на 12». Укажите, какие из следующих утверж­дений истинны, какие ложны:

3.    Доказать равносильности :

1)      "х(А(х)®с)º$хА(х)®с;

2)      $хА(х)$уВ(у)º$х$у(А(х)В(х)).

4.Каким условиям удовлетворяют области истинности предикатов А(х) и В(х), определенных на множестве М, если истинно высказывание:

5. Предикаты А(х, у) и В(у, z) определены на множестве МхМ, где М={a, b, c}. Записать формулу $x$уA(x, y)®$у"хB(х, у) без кванторных операций.

6. Дан предикат Q(x,y): «х делится на у». Какие из предикатов тождественно истинные и какие тождественно ложные: "хQ(x,y), $уQ(x,y), "уQ(x,y), $хQ(x,y). Найти значения высказываний: $х$уQ(x,y): "у$хQ(x,y): $у"хQ(x,y): "х"уQ(x,y).

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

1.      Как одноместный предикат можно превратить в единичное высказывание?

2.      Что понимают под выражением "хР(х)?

3.      Что понимают под выражением $хР(х)?

4.      Каким образом двухместный предикат превратить в одноместный и - в высказывание?

5.      Какой символикой можно пользоваться в логике предикатов?

6.      Сформулировать определение формулы логики предикатов.

7.      От чего зависит значение формулы логики предикатов?

8.      Сформулировать оба определения равносильных формул логики предикатов.

9.      Какие равносильности используются при построении отрицаний формул?

Практическое занятие 6. Операции над графами.

 

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

 

Время выполнения: 2 часа.

 

Теоретические основы

 

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

Всякий простой граф может быть представлен не только в виде рисунка, но и аналитически. Пусть Е – множество ребер графа, тогда можно записать (рис. 1):

  где Е – множество двухэлементных подмножеств множества V, каждое из которых определяет ребро, соединяющее вершины  и .

Объединением графов  и  называют граф , где  

Пересечением двух графов  и  называется граф , где  .

 

Пример 1.

Графы G1, G2 и G3 представлены в виде:

А) , где

Б) , где  

В) , где  

Найдите число вершин и число ребер графа .

Решение.

,

 

Практическое задание

 

Задание1. Найдите число вершин и число ребер графа: а)  и укажите его вершины.

Задание 2

I вариант

II вариант

1. Даны множества: , , , . Выполните следующие операции:

Графы G1, G2 и G3 представлены в виде:

А) , где

Б) , где  

В) , где  

2. Найдите число вершин, число ребер графа и изобразите его:

3. Укажите вершины графа

 

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

1.      Что называют объединением графов?

2.&nbs