МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

фгбоуИ во «московский государтвенный гуманитарно-экономический УНИВЕРСИТЕТ»

калмыцкий филиал

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

по дисциплине «Элементы математической логики»

для специальности

09.02.03 Программирование в компьютерных системах

Элиста, 2016г.

Утверждено научно-методическим советом КФ МГГЭУ

«___»___________________ 2016г.

Председатель: ____________________

Новгородова В.В.

Рассмотрено на заседании кафедры информационных технологий

Протокол № ___ от ______ 2016г.

Зав. кафедрой ____________________

Катрикова Ц.Ю.

Разработчик УМК: Кукаева Е.Б.

преподаватель КФ ФГБОУИ ВО «МГГЭУ»

Рецензенты: ________ Очирова Т.Л.

преподаватель КФ ФГБОУИ ВО

«МГГЭУ»

________ ______________________________

______________________________

РЕЦЕНЗИЯ

на УМК по дисциплине «Элементы математической логики»

для специальности 09.02.03 Программирование в компьютерных системах, разработанную преподавателем КФ ФГБОУИ ВО «МГГЭУ» Кукаевой Е.Б.

Данный учебно-методический комплекс по дисциплине «Элементы математической логики» предназначен для студентов группы П-2 специальности среднего профессионального образования 09.02.03 Программирование в компьютерных системах и рассчитан на 96 часов.

УМК разработан на основе рабочей программы по дисциплине «Элементы математической логики» в соответствии с Федеральным государственным образовательным стандартом СПО, утвержденном Департаментом государственной политики и нормативно­-правового регулирования в сфере образования Министерства образования и науки Российской Федерации по специальности 09.02.03 «Программирование в компьютерных системах».

В УМК имеются:

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

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

• Выписка из ФГОС СПО по специальности 09.02.03 «Программирование в компьютерных системах», содержащая требования к результатам освоения основной профессиональной образовательной программы;

• Учебно-методическую карту к каждому уроку;

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

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

Рецензент: ________________ Очирова Т.Л.

преподаватель КФ ФГБОУИ ВО «МГГЭУ»

РЕЦЕНЗИЯ

на УМК по дисциплине «Элементы математической логики»

для специальности 09.02.03 Программирование в компьютерных системах, разработанную преподавателем КФ ФГБОУИ ВО «МГГЭУ» Кукаевой Е.Б.

Данный учебно-методический комплекс по «Элементы математической логики» предназначен для студентов группы П-2 специальностей среднего профессионального образования 09.02.03 Программирование в компьютерных системах и рассчитан на 96 часов.

УМК разработан на основе рабочей программы по дисциплине «Элементы математической логики» в соответствии с Федеральным государственным образовательным стандартом СПО, утвержденном Департаментом государственной политики и нормативно­-правового регулирования в сфере образования Министерства образования и науки Российской Федерации по специальности 09.02.03 Программирование в компьютерных системах.

Целью создания УМК является познакомить студентов с основными понятиями математической логики.

В УМК рассчитан на 96 часов и содержит:

• пояснительную записку;

• выписку из тематического плана рабочей программы;

• выписку из ФГОС СПО по специальности 09.02.03 Программирование в компьютерных системах;

• учебно-методическую карту к каждому уроку;

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

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

Формализованное исчисление предикатов рассматривается как расширение исчисление высказываний.

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

Рецензент: ________________ ____________________________________

____________________________________

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

Данный учебно-методический комплекс по «Элементы математической логики» предназначен для студентов группы П-2 специальностей среднего профессионального образования 09.02.03 Программирование в компьютерных системах

Целью создания УМК является познакомить студентов с основными понятиями математической логики.

В УМК рассчитан на 96 часов и содержит:

• пояснительную записку;

• выписку из тематического плана рабочей программы;

• выписку из ФГОС СПО по специальности 09.02.03 Программирование в компьютерных системах;

• учебно-методическую карту к каждому уроку;

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

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

Формализованное исчисление предикатов рассматривается как расширение исчисление высказываний.

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

Выписка из тематического плана рабочей программы «Элементы математической логики»

Наименование разделов и тем

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

Объем часов

Уровень усвоения

1

2

3

4

Тема 1. Элементы теории множеств

Содержание учебной дисциплины

12

1

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

2

1

2

Операции над множествами. Разбиение множества на классы.

2

1,2

3

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

2

1,2

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

1

Операции над множествами: объединение, пересечение, разность, симметрическая разность, дополнение. Свойства операций над множествами.

2

2,3

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

4

Тема 2. Элементы алгебры логики

Содержание учебной дисциплины

60

1

Алгебра логики. Понятие высказывания. Логические операции.

2

1,2

2

Логические формулы, таблицы истинности.

2

1,2

3

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

4

Булевы функции. Функции алгебры логики. Представление произвольной функции в виде формулы алгебры логики.

2

1,2

5

Совершенные нормальные формы. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма.

2

1,2

6

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

2

1,2

7

Метод минимизирующих карт. Метод Квайна.

1,2

8

Метод минимизирующих карт. Метод Карно.

1,2

9

Метод Квайна. Метод Карно.

1,2

10

Логические основы построения ЭВМ

1,2

11

Некоторые логические операции. Двоичное сложение.

1,2

12

Полином Жегалкина.

2

1,2

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

1

Применение алгебры логики (решение текстовых логических задач или алгебра переключательных схем).

2

2,3

2

Решение логических задач средствами алгебры логики

2

2,3

3

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

2

2,3

4

Построение СДНФ и ее минимизация

2,3

5

Метод минимизирующих карт. Метод Квайна.

2,3

6

Метод минимизирующих карт. Метод Карно.

7

Логические основы построения ЭВМ

2

2,3

8

Полином Жегалкина

2

2,3

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

20

Тема 3. Предикаты

Содержание учебной дисциплины

24

1

Понятие предиката.

2

1,2

2

Логические операции над предикатами.

1,2

3

Логические операции над предикатами.

1,2

4

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

2

1,2

5

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

2

1,2

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

1

Логические операции над предикатами.

2

2,3

2

Запись математических предложений в виде формул логики предикатов.

2

2,3

3

Построение противоположных утверждений.

2,3

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

8

Всего

96

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

1. - ознакомительный (узнавание ранее изученных объектов, свойств);

2. - репродуктивный (выполнение деятельности по образцу, инструкции или под руководством)

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

Выписка из ФГОС СПО ОПОП по специальности 09.02.03 Программирование в компьютерных системах

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

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

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

• компьютерные системы;

• автоматизированные системы обработки информации и управления;

• программное обеспечение компьютерных систем (программы, программные комплексы и системы);

• математическое, информационное, техническое, эргономическое, организационное и правовое обеспечение компьютерных систем;

• первичные трудовые коллективы.

Основные виды профессиональной деятельности

Техник программист готовится к следующим видам деятельности:

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

• разработка и администрирование баз данных;

• участие в интеграции программных модулей;

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

Требования к результатам освоения ОПОП СПО по специальности 09.02.03 Программирование в компьютерных системах

Общие компетенции

Техник-программист должен обладать общими компетенциями, включающими в себя способность:

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

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

ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.

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

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

ОК 6. Работать в коллективе и в команде, эффективно общаться с коллегами, руководством, потребителями.

ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), за результат выполнения заданий.

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

ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.

Профессиональные компетенции

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

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

ПК 1.1. Выполнять разработку спецификаций отдельных компонент.

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

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

ПК 1.4. Выполнять тестирование программных модулей.

ПК 1.5. Осуществлять оптимизацию программного кода модуля.

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

Разработка и администрирование баз данных:

ПК 2.1. Разрабатывать объекты базы данных.

ПК 2.2. Реализовывать базу данных в конкретной системе управления базами данных (далее - СУБД).

ПК 2.3. Решать вопросы администрирования базы данных.

ПК 2.4. Реализовывать методы и технологии защиты информации в базах данных.

Участие в интеграции программных модулей:

ПК 3.1. Анализировать проектную и техническую документацию на уровне взаимодействия компонент программного обеспечения.

ПК 3.2. Выполнять интеграцию модулей в программную систему.

ПК 3.3. Выполнять отладку программного продукта с использованием специализированных программных средств.

ПК 3.4. Осуществлять разработку тестовых наборов и тестовых сценариев.

ПК 3.5. Производить инспектирование компонент программного продукта на предмет соответствия стандартам кодирования.

ПК 3.6. Разрабатывать технологическую документацию.

Выписка из паспорта комплекта контрольно-оценочных средств

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

Результаты обучения

(освоенные умения, усвоенные знания)

Основные показатели оценки результатов

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

Определение значения истинности высказываний. Построение составных высказываний. Составление таблиц истинности для формул. Приведение формул к совершенным нормальным формам. Упрощение формул логики до минимальной ДНФ. Приведение формул к совершенным нормальным формам. Решение логических задач. Исследование релейно-контактных схем при помощи алгебры логики. Выполнение логических операций над предикатам. Выполнение операций с кванторами. Применение логики предикатов

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

Формулировка высказывания и высказывательных форм. Формулировка основных операций: отрицание, конъюнкция и дизъюнкция. Союзы языка и логические операции (Язык и логика). Импликанция, эквиваленция, сумма по модулю два, штрих Шеффера, стрелка Пирса. Таблицы истинности

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

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

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

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

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

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

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

1.1.Область применения программы

Рабочая программа учебной дисциплины- является частью основной профессиональной образовательной программы в соответствии с ФГОС по специальности СПО 09.02.03 «Программирование в компьютерных системах» в части освоения основного вида профессиональной деятельности (ВДП): «Элементы математической логики» и соответствующих умений и знаний:

уметь:

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

знать:

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

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

• основы языка и алгебры предикатов.

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

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

Результаты обучения

(освоенные умения, усвоенные знания)

Формы и методы контроля и оценки результатов обучения

1

2

Умения:

строить таблицы истинности для формул логики упрощать формулы логики;

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

Текущий контроль в форме:

- устного опроса

- тестирования

- практических занятий

- самостоятельных работ по темам дисциплины

- решение задач

- контрольные работы.

Экзамен по дисциплине.

формулировать задачи логического характера;

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

выполнять операции над множествами;

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

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

Знания:

основных принципов математической логики;

основных принципов теории множеств и теории алгоритмов;

формул алгебры высказывания;

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

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

Информационное обеспечение обучения

Основная учебная литература:

1. Ершов Юрий Леонидович. Математическая логика [Текст] : Учебное пособие для вузов / Ю.Л. Ершов, Е.А. Палютин, 2010. - 336 с.

2. Зайцев, Иван Антонович. Высшая математика [Текст] : Учеб. для неинж. спец. с.-х. вузов / И.А. Зайцев, 2011. - 400 с.

Дополнительная учебная литература:

3. Яблонский С.В. Введение в дискретную математику. - М.: Высшая школа, 2010 г.

4. Шестаков А.А., Дружинина О.В. Дискретная математика. Элементы нечеткой логики: Учеб. пос. - М: РГОТУПС, 2012 г.

5. Мендельсон Э. Введение в математическую логику. - М.: Наука, 2010 г.

Интернет-ресурсы:

1. moi.aspinf.ru

2. intuit.ru/department/expert/logicpr/1/

3. studfiles.ru/dir/cat14/subj266/file9092/view94463.html

4. studfiles.ru/dir/cat14/subj266/file9092/view94463.html

Тема 1. Элементы теории множеств

Лекция №1.Понятие множества и элементы множества. Способы задания множеств

Понятие множества является неопределяемым понятием. Его смысл разъясняется на примерах. Можно говорить о множестве жителей города Саратова, о множестве домов на конкретной улице, о множестве букв в слове «командир», о множестве натуральных чисел, меньших 20 и т. д.

Проказница-Мартышка,

Осел,

Козел

Да косолапый Мишка

Затеяли сыграть Квартет.

Достали нот, баса, альта, две скрипки

И сели на лужок под липки, -

Пленять своим искусством свет.

Ударили в смычки, дерут, а толку нет.

"Стой, братцы, стой! - кричит Мартышка. -

Погодите!

Как музыке идти? Ведь вы не так сидите.

Ты с басом, Мишенька, садись против альта,

Я, прима, сяду против вторы;

Тогда пойдет уж музыка не та:

У нас запляшут лес и горы!"

Расселись, начали Квартет;

Он все-таки на лад нейдет.

"Постойте ж, я сыскал секрет? -

Кричит Осел, - мы, верно, уж поладим,

Коль рядом сядем".

Послушались Осла: уселись чинно в ряд;

А все-таки Квартет нейдет на лад.

Вот пуще прежнего пошли у них разборы

И споры,

Кому и как сидеть.

Случилось Соловью на шум их прилететь.

Тут с просьбой все к нему, чтоб их решить сомненье.

"Пожалуй, - говорят, - возьми на час терпенье,

Чтобы Квартет в порядок наш привесть:

И ноты есть у нас, и инструменты есть,

Скажи лишь, как нам сесть!" -

"Чтоб музыкантом быть, так надобно уменье

И уши ваших понежней, -

Им отвечает Соловей, -

А вы, друзья, как ни садитесь;

Всё в музыканты не годитесь".

Множества принято обозначать большими латинскими буквами, например, А, В, С, … , Х, Y, Z. Объекты, из которых состоит множество, называются его элементами . Их принято обозначать маленькими латинскими буквами: a , b , c , d . Если множество А состоит из элементов a , c , k , то записывают это так: А = { a , c , k }.

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

Множество может быть задано перечислением всех его элементов или описанием характеристического свойства его элементов. Характеристическим свойством называется такое свойство, которым обладают все элементы данного множества и не обладают никакие другие объекты. Например, запись А = { х | х - житель Саратова } означает, что множество А состоит из жителей Саратова.

Множества, состоящие из чисел, называют числовыми множествами.

N - множество натуральных чисел,

Z - множество целых чисел,

N _о или Z _о - множество целых неотрицательных чисел,

Q - множество рациональных чисел,

R - множество действительных чисел.

Задания для самостоятельной работы к лекции №1:

Назовите и запишите множество зверей из басни

И.А. Крылова «Квартет», используя способ:

а) перечисления элементов;

б) задания характеристического свойства.

Принадлежит ли Соловей этому множеству?

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

а)неодушевленные предметы,

б)геометрические фигуры,

в)животные,

г)растения.

Задайте множество с помощью перечисленных элементов:

X={x/x N, 0 x 4}

X={x/x N, -2 x 6}

X={x/x Z, -3 x 5}

X={x/x Z, 0 x 4}

В данном множестве все элементы, кроме одного, обладают некоторым свойством. Опишите это свойство и найдите элемент, не обладающий им: а) { треугольник, квадрат, трапеция, круг, правильный шестиугольник }; б) { лев, лисица, гиена, слон, рысь }; в) { бежать, смотреть, синий, знать, читать }; г) {2, 6, 15, 84, 156}; д) {1, 9, 67, 81, 121}.

Тема 1. Элементы теории множеств

Лекция №2.Операции над множествами. Разбиение множества на классы.

Между двумя множествами существует пять видов отношений. Если множества А и В не имеют общих элементов, то говорят, что эти множества не пересекаются и записывают этот факт в виде А∩В =∅ . Например, А = { a , c , k }, В = { d , e , m , n }, общих элементов у этих множеств нет, поэтому множества не пересекаются.

Если множества А и В имеют общие элементы, т.е. элементы, принадлежащие одновременно А и В, то говорят, что эти множества пересекаются и записывают А∩В≠∅ . Например, множества А = { a , c , k } и В = { c , k , m , n } пересекаются, т. к. у них есть общие элементы c , k .

Множество В является подмножеством множества А, если каждый элемент множества В является также элементом множества А. Пустое множество является подмножеством любого множества. Само множество является подмножеством самого себя. (пишут В⊂ А)

Пустое множество и само множество называют несобственными подмножествами . Остальные подмножества множества А называются собственными. Для каждого множества, состоящего из n элементов можно образовать 2 ⁿ подмножеств. Если рассматривают лишь подмножества некоторого множества U, то U называют универсальным множеством.

Если множества А и В состоят из одних и тех же элементов, то они называются равными.

Например, А = { a , c , k , m , n } и В = { m , n , a , c , k }, А = В.

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

а) б) в) г) д)

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

Пересечение множеств А и В обозначают А∩ В. Таким образом, по определению, А ∩ В = { х | х ∈ А и х ∈ В}.

Например, если А = { a , c , k , m , n } и В = { a , b , c , d , e }, то А ∩ В = { a , c }.

Если изобразить множества А и В при помощи кругов Эйлера-Венна, то пересечением данных множеств является заштрихованная область (рис. 3).

Для пересечения множеств выполняются следующие свойства.

1) Переместительное или коммутативное свойство: А ∩ В = В ∩ А.

2) Сочетательное или ассоциативное свойство:(А ∩ В) ∩ С = А ∩ (В ∩ С).

3) А ∩ ∅ = ∅ (пустое множество является поглощающим элементом).

4) А ∩ U = А (универсальное множество является нейтральным элементом).

5) Если В ⊂А, то А∩В = В

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

Объединение множеств А и В обозначают А∪ В. Таким образом, по определению, А ∪ В = { х | х ∈А или х∈В}. Например, если А = { a , c , k , m , n } и В = { a , b , c , d , e }, то А ∪ В = { a , c , k , m , n , b , d , e }.

Если изобразить А и В при помощи кругов Эйлера-Венна, то объединением данных множеств является заштрихованная область (рис. 4).

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

1) Переместительное или коммутативное свойство: А ∪ В = В ∪ А.

2) Сочетательное или ассоциативное свойство:(А ∪ В)∪ С = А ∪ (В ∪ С).

3) А ∪ ∅= А (пустое множество является нейтральным элементом).

4) А ∪ U = U (универсальное множество является поглощающим элементом).

5) Если В ⊂А, то А∪В = В

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

(А ∪ В) ∩С = (А∩С) ∪ (В∩С) и (А∩В) ∪ С = (А ∪ С) ∩(В ∪ С).

П р и м е р 1. Пусть А - множество различных букв в слове «математика», а В - множество различных букв в слове «стереометрия». Найти пересечение и объединение множеств А и В.

Р е ш е н и е. Запишем множества А и В, перечислив их элементы: А = { м, а, т, е, и, к }, В = { с, т, е, р, о, м, и, я }. Буквы м, т, е, и принадлежат и множеству А, и множеству В, поэтому они войдут в пересечение этих множеств: А∩В = { м, т, е, и }. В объединение этих множеств войдут все элементы множества А и несовпадающие с ними элементы из множества В: А ∪ В = { м, а, т, е, и, к, с, р, о, я }.

П р и м е р 2 . В классе английский язык изучают 25 человек, а немецкий - 27 человек, причем 18 человек изучают одновременно английский и немецкий языки. Сколько всего человек в классе изучают эти иностранные языки? Сколько человек изучают только английский язык? Только немецкий язык?

Р е ш е н и е. Через А обозначим множество школьников, изучающих английский язык, через В - множество школьников, изучающих немецкий язык. Изобразим эту ситуацию с помощью диаграммы. Два языка изучают 18 школьников, поставим это число в пересечение множеств А и В. Английский язык изучают 25 человек, но среди них 18 человек изучают и немецкий язык, значит, только английский язык изучают 7 человек, укажем это число на диаграмме. Рассуждая аналогично, получим, что только немецкий язык изучают 27 - 18 = 9 человек. Поместим и это число на диаграмму. Теперь известно количество элементов в каждой части множеств, изображенных на диаграмме. Чтобы ответить на главный вопрос задачи, нужно сложить все числа: 7 + 18 + 9 = 34. Ответ: 34 человека в классе изучают иностранные языки.

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

Разность множеств А и В обозначают А \ В. Таким образом, по определению разности А \ В = { х | х ∈ А и х ∉В}.

Например, если А = { a , c , k , m , n } и В = { a , b , c , d , e }, то А \ В = { k , m , n }.

Если изобразить А и В при помощи кругов Эйлера-Венна, то разность данных множеств является заштрихованная область (рис. 5).

Определение. Пусть В является подмножеством множества А. В этом случае разность множеств А и В называют дополнением подмножества В до множества А и обозначают В'_А. Дополнение можно изобразить как показано на рис. 5. Если В - подмножество универсального множества U, то дополнение подмножества В до U обозначают В'.

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

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

1) (А \ В) \ С = (А \ С) \ В.

2) (А∪В) \ С = (А \ С) ∪ (В \ С).

3) (А \ В) ∩ С = (А ∩С) \ (В ∩ С).

4) (А ∪ В)' = А' ∩ В'.

5) (А ∩ В)' = А' ∪В'.

Четвертое свойство формулируется так: дополнение к объединению двух множеств равно пересечению дополнений к этим множествам. Пятое свойство формулируется аналогично.

П р и м е р 1. А - множество натуральных чисел, кратных 3, В - множество натуральных чисел, кратных 5. Задать описанием характеристического свойства множество А \ В и назвать три числа, принадлежащих этому множеству.

Р е ш е н и е. По определению разность данных множеств состоит из натуральных чисел, кратных 3 и не кратных 5. Поэтому разности множеств А и В принадлежат числа 9, 24, 33.

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

а) А = { х | х = 2 k + 1, k∈N };

б) А = { х | х = 3 k , k ∈ N }.

Р е ш е н и е. а) Числа вида х = 2 k + 1, k ∈ N представляют собой нечетные натуральные числа, следовательно, дополнение А' - это четные натуральные числа: А' = { х | х = 2 k , k ∈ N }.

б) В виде х = 3 k , k∈N записаны натуральные числа, кратные 3, или числа, дающие при делении на 3 остаток 0. В дополнение к этому множеству войдут числа, не кратные 3, или дающие при делении на 3 остаток 1 или 2. Запишем А' = { х | х = 3 k + 1 или х = 3 k + 2, k ∈ N _о }.

Говорят, что множество Х разбито на попарно непересекающиеся подмножества или классы , если выполнены следующие условия:

1) любые два подмножества попарно не пересекаются;

2) объединение всех подмножеств совпадает с исходным множеством Х.

Разбиение множества на классы называют классификацией.

Классификацию можно выполнять при помощи свойств элементов множества. Если выбирается только одно свойство, то такую классификацию называют дихотомической . Например, натуральные числа можно разбить на четные и нечетные. Буквы русского языка можно разбить на гласные и не гласные. Вообще, если на множестве Х задано одно свойство А, то это множество разбивается на два класса: первый класс - объекты, обладающие свойством А, второй класс - объекты, не обладающие свойством А.

Если элементы множества обладают двумя независимыми свойствами, то все множество разбивается на 4 класса. Например, на множестве натуральных чисел заданы два свойства: «быть кратным 2» и «быть кратным 3». При помощи этих свойств в множестве N можно выделить два подмножества А и В. Эти множества пересекаются, но ни одно из них не является подмножеством другого (рис. 6). Тогда в первый класс войдут числа, кратные 2 и 3, во второй - кратные 2, но не кратные 3, в третий - кратные 3, но не кратные 2, в четвертый - не кратные 2 и не кратные 3.

Рис. 6

П р и м е р 1. Пусть Х - множество четырехугольников, А, В и С - его подмножества. Можно ли говорить о разбиении множества Х на классы А, В и С, если:

а) А - множество параллелограммов, В - множество трапеций, С - множество четырехугольников, противоположные стороны которых не параллельны;

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

Р е ш е н и е. а) Множества А, В и С попарно не пересекаются. Действительно, если у четырехугольника, противоположные стороны не параллельны, то он не может быть параллелограммом или трапецией. В параллелограмме противоположные стороны попарно параллельны, поэтому он не может принадлежать ни множеству В, ни множеству С. Наконец, в трапеции две противоположные стороны параллельны, а две другие не параллельны, поэтому трапеция не может принадлежать ни множеству А, ни множеству С. Объединение множеств А, В и С даст все множество четырехугольников. Условия классификации выполнены, множество всех четырехугольников можно разбить на параллелограммы, трапеции и четырехугольники, противоположные стороны которых не параллельны.

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

Задания для самостоятельной работы к лекции №2:

1. Приведите примеры множеств А, В, С, если отношения между ними таковы:

2. Образуйте все подмножества множества букв в слове «крот». Сколько подмножеств получилось?

3. Даны множества А = { a , b , c , d , e , f , k } и В = { a , c , e , k , m , p }. Найдите А ∪ В , А ∩ В , А \ В , В \ А .

4. Из множества N выделили два подмножества: А - подмножество натуральных чисел, кратных 3, и В - подмножество натуральных чисел, кратных 5. Постройте круги Эйлера для множеств N , A , B ; установите, на сколько попарно непересекающихся множеств произошло разбиение множества N ; укажите характеристические свойства этих множеств.

5. Имеется множество блоков, различающихся по цвету (красные, желтые, зеленые), форме (круглые, треугольные, прямоугольные), размеру (большие, маленькие). На сколько классов разбивается множество, если в нем выделены подмножества: А - круглые блоки, В - зеленые блоки, С - маленькие блоки? Сделайте диаграмму Эйлера и охарактеризуйте каждый класс.

6. Известно, что А - множество спортсменов класса, В - множество отличников класса. Сформулируйте условия, при которых: а) А ∩В=Ø б)А U В=А

7. Пусть Х= { x N/ 1 x 15}. Задайте с помощью перечисления следующие его подмножества:

А - подмножество всех четных чисел;

В - подмножество всех нечетных чисел;

С - подмножество всех чисел, кратных 3;

D - подмножество всех чисел, являющихся квадратами;

E - подмножество всех простых чисел.

В каких отношениях они находятся?

Тема 1. Элементы теории множеств

Лекция №3. Операции над множествами. Свойства операций над множествами

Всякий математический объект обладает определенными свойствами. Например, квадрат имеет четыре стороны, четыре прямых угла и др. Различают свойства существенные и несущественные.

Существенное свойство - свойство, без которого объект не может существовать.

Несущественное свойство - свойство, отсутствие которого не влияет на существование объекта.

Для квадрата: АВСД существенные свойства: АВ = ВС = СД =ДА, АВ║ ДС, АД ║ ВС;

несущественные свойства: АВ, ДС - горизонтальны, АД, ВС - вертикальны.

Если квадрат повернуть, сохранятся только существенные свойства, именно они и составляют понятие об объекте.

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

Диалог:

- Опиши фигуру.

- Маленький черный треугольник.

- Большой белый треугольник.

- Чем фигуры похожи?

- Формой.

- Чем фигуры отличаются?

- Цветом, величиной.

- Что есть у треугольника?

- 3 стороны, 3 угла.

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

Совокупность всех существеннных свойств объекта называют содержанием понятия.

Совокупность всех объектов, обозначаемая одним термином, составляет объем понятия.

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

Итак, любое понятие характеризуется:

- термином (название);

- объемом (совокупность всех объектов, называемых этим термином);

- содержанием (совокупность всех существенных свойств объектов, входящих в объем понятия).

Между объемом понятия и его содержанием существует связь: чем "больше" объем понятия, тем "меньше" его содержание, и наоборот. Объем понятия «треугольник» "больше", чем объем понятия "прямоугольный треугольник", так как все объекты второго понятия являются и объектами первого понятия. Содержание понятия "треугольник" "меньше", чем содержание понятия "прямоугольный треугольник", так как прямоугольный треугольник обладает всеми свойствами любого треугольника и еще другими свойствами, присущими только ему.

ОПРЕДЕЛЕНИЕ ПОНЯТИЙ

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

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

Различают явные и неявные определения. Явные определения имеют форму равенства двух понятий. Одно из них называют определяемым другое определяющим.

Например: "Квадрат - это прямоугольник, у которого все стороны равны". Здесь определяемое понятие - «квадрат», а определяющее - "прямоугольник, у которого все стороны равны".

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

Следует иметь в виду, что понятия рода и вида относительны. Так, "прямоугольник" - это родовое к понятию "квадрат", но видовое по отношению к понятию «четырехугольник».

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

Таким образом, определение через род и видовое отличие имеет следующую структуру:

Определяемое = Род + Видовое

К явным определениям предъявляются определенные требования.

1) Определение должно быть соразмерным. Например, нельзя говорить, что окружность - это линия, которая начинается и кончается в одной точке. Этому определению удовлетворяют много линий, не являющихся окружностями.

2) В определении (или их системе) не должно быть порочного круга. Это означает, что нельзя определять понятие через само себя. Например, содержит порочный круг определение: «Касательная к окружности - это прямая, которая касается окружности».

3) Определение должно быть ясным и минимальным. Нельзя определять прямоугольник как параллелограмм с прямым углом, если понятие «параллелограмм» еще не рассмотрено. В определении не должно быть лишних свойств. Например, неправильным будет определение: «Параллелограммом называется четырехугольник, у которого противоположные стороны попарно параллельны и равны». Равенство сторон в определении не нужно указывать, так как оно вытекает из свойств параллелограмма.

Существуют неявные определения. В их структуре нельзя выделить определяемое и определяющее понятия. Среди них выделяют контекстуальные и остенсивные определения.

В контекстуальных определениях содержание нового понятия раскрывается через отрывок текста, через контекст, через анализ конкретной ситуации, описывающей смысл вводимого понятия. Например, в начальной школе понятие уравнения можно ввести так: «К какому числу надо прибавить 6, чтобы получилось 15? Обозначим неизвестное число латинской буквой х (икс): х + 6 = 15 - это уравнение. Решить уравнение - значит найти неизвестное число. В данном уравнении неизвестное число равно 9, так как 9 + 6 = 15».

Остенсивные определения - это определения путем показа. Например, таким способом можно определить в начальной школе понятия равенства и неравенства:

3·8 > 2·8 5·8 = 40

65 + 9 < 82 - 5 6·8 = 5·8 + 8

48 : 8 < 48 18 : 9 = 16 - 14

Это неравенства. Это равенства.

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

П р и м е р 1. Назовите несколько свойств, принадлежащих содержанию понятия «треугольник». Принадлежит ли содержанию этого понятия свойство «иметь две равные стороны»?

Р е ш е н и е. В содержание понятия «треугольник» входят только те свойства, которые являются общими для всех треугольников, например, такие: 1) имеет три вершины, 2) имеет три угла, 3) имеет три стороны, 4) ограничен замкнутой ломаной линией. Свойство «иметь две равные стороны» в содержание понятия «треугольник» не входит, так как этим свойством обладают не все треугольники.

Задания для самостоятельной работы к лекции №3:

1. Каков объем понятий: «цифра», «автомобиль», «снегурочка», «волк», «столица России», «двузначное число».

2. Решите анаграммы. Исключите лишнее слово. Ответ обоснуйте:

Каут, кабоса, цикурка, кайнеди;

Релоказ, начик, меро, лекосо;

Вианд, лексор, слот, самик, фебут.

3. Дополните определение:

Портной - это …., который шьет одежду.

…. - это человек, который рисует картины.

Врач - ….

Масленка - …

Улей - …

Тема 1. Элементы теории множеств

Практическое занятие №1.Операции над множествами: объединение, пересечение, разность, симметрическая разность, дополнение. Свойства операций над множествами.

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

Блок 1. Множества и операции над ними.

Презентация. (Слайд 2) Вопросы к слайду 2:

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

а) арабских цифр; (0; 1; 2; 3; 4; 5; 6; 7; 8; 9)

б) натуральных чисел; (1; 2; 3; 4;…)

в) целых чисел (…-2; -1; 0; 1; 2;…).

2. Как называется множество цветов, стоящих в вазе? (букет).

3. Перечислите элементы множества планет солнечной системы. (Меркурий, Венера, Земля,

Марс, Юпитер, Сатурн, Уран, Нептун).

4.Как называется множество фруктовых деревьев и кустарников растущих у дома? (сад).

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

6. Какие названия применяют для обозначения множеств животных? (млекопитающие,

земноводные, хладнокровные и т.п.).

7. Перечислите элементы множества видов спорта (футбол, теннис, волейбол и т. п.).

8. Какие названия применяют для обозначения множеств кораблей? (флотилия, эскадра).

Задайте сами множество описанием.

(Слайд 3) Множества обычно обозначают большими буквами латинского алфавита: А, В,

С, Д, и т. д. Некоторые числовые множества столь часто встречающиеся в различных

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

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

Z - множество целых чисел;

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

I - множество иррациональных чисел;

R - множество действительных чисел.

(Слайд 4) Чтобы не забыть, что перечисляемые элементы объединены вместе в

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

Например, цифры десятичной системы счисления задаются множеством

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Если множество состоит из чисел, то при их перечислении иногда удобнее использовать

не запятую, а знак препинания « ; » - точку с запятой. Так как «перечислительную» запятую

можно спутать с «десятичной» запятой.

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

перечисления элементов само множество не меняется. Например, множество гласных букв

русского алфавита задается {А, Е, Ё, И, О, У, Ы, Э, Ю, Я} или {Э, Е, А, Ё, Я, О, Ы, И, У, Ю}.

Эти множества состоят из одних и тех же элементов, их называют равными, а для записи

равенства двух множеств употребляют знак « = ».

{А, Е, Ё, И, О, У, Ы, Э, Ю, Я} = {Э, Е, А, Ё, Я, О, Ы, И, У, Ю}.

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

Например, запись А = {2; 3; 5; 7; 11; 13} означает, что множество А состоит из первых шести

простых чисел.

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

случае, когда их число невелико. Если число элементов множества достаточно велико или

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

Способы задания, описания множеств весьма разнообразны. Например, множество

всех квадратов натуральных чисел можно записать {1; 4; 9; 16; 25; …}, а множество всех

чисел, которые больше 5 и меньше 12 записать {х | 5< х <12} или (5; 12). В примерах

использован оборот « … и так далее» и символ « | » внутри фигурных скобок заменяющий

комбинацию слов « … таких, что …». (Множество всех х таких, что 5< х <12).

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

объект, отвечающий этому описанию. Предположим, о множестве С сказано, что оно состоит

из чисел, делящихся на 6, но не делящихся на 3. Таких чисел просто нет. В подобных

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

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

(Слайд 5) Задание 1. [3]

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

а) 3254; б) 8797; в) 11000; г) 555555.

2) Задайте множество А описанием:

а) А = {1, 3, 5, 7, 9}; б) А = {- 2, - 1, 0, 1, 2}; в) А = {11, 22, 33, 44, 55, 66, 77, 88, 99};

г) А = {0,1; 0,01; 0,001; 0,0001; …}; д) А = {1/2, 2/3, 3/4, 4/5, … }.

3) Задание с выбором ответа. Даны множества: М = {5,4,6}, Р = {4,5,6}, Т = {5,6,7},

S = {4, 6}. Какое из утверждений неверно?

а) М = Р. б) Р ≠ S. в) М ≠ Т. г) Р = Т.

(Слайд 6) Словесные обороты, как «элемент х принадлежит множеству А» или «х - элемент

множества А», достаточно длинны и не всегда удобны в записи решений конкретных задач.

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

Например, 5N, лучше читать не буквально, а в «литературном переводе», «5 - число

натуральное». Наряду со знаком принадлежит используют и его «отрицание» - знак

(знак не принадлежит). Запись 0 N означает, что нуль не натуральное число.

(Слайд 7) Задание 2. [3; 1]

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

а) число 10 - натуральное;

б) число - 7 не является натуральным;

в) число - 100 является целым;

г) число 2,5 - не целое.

2. Верно ли, что:

а) - 5 N; б) -5 Z; в) 2,(45) Q?

3. Верно ли, что:

а) 0,7 {х | х² - 1 < 0}; б) - 7 {х | х² + 16х ≤ - 64}?

(Слайд 8) Возьмем множество А = {2; 4; 6} и В = {1; 2; 3; 4; 5; 6; 7}. Каждый элемент

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

является подмножеством множества В, и пишут: А В.

Знак «» называют знаком включения.

Соотношения между множествами А и В можно проиллюстрировать на рисунке с помощью

так называемых кругов Эйлера (Леонард Эйлер российский ученый - математик, механик,

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

изображаются точками этого круга (рис 1).

Пустое множество считают подмножеством любого множества. А В

Будем считать, что все элементы рассматриваемых множеств Рис. 1

взяты из некоторого одного и того же «универсального» множества К. Это множество будем

изображать квадратом, а рассматриваемые множества А, В, С, … - подмножества множества

К - кругами (или другими полученными из них фигурами, которые выделим штриховкой).

(Слайд 9) Задание 3. [3; 1]

1. Даны множества: А = {10}, В = {10, 15}, С = {5, 10, 15}, D = {5, 10, 15, 20}.

Поставьте вместо … знак включения ( или ) так, чтобы получилось верное

утверждение: а) А… D; б) А…В; в) С…А; г) С…В.

2. Даны три множества А = {1, 2, 3,…, 37}, В = {2, 4, 6, 8, …}, С = {4, 8, 12, 16,…,36}.

Верно ли, что: а) А В; б) В С; в) С А; г) С В?

(Слайд 10) Из данных множеств с помощью специальных операций можно образовывать

новые множества:

1) Пересечением множества А и В называют множество, состоящие из всех общих

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

и множеству А, и множеству В (рис. 2). Пересечение множеств А и В

обозначают так: А∩В. Это определение можно записать и так:

А∩В = {х | х А и х В}. Иными словами, пересечение двух А∩В К

множеств - это их общая часть. Например, если А = {3; 9; 12} и Рис. 2

В = {1; 3; 5; 7; 9; 11}, то А∩В = {3; 9}. Если А = {10; 20; …90; 100} и В = {6; 12; 18;…}, то

А∩В = {30; 60; 90}. Можно рассматривать пересечение не только двух, но трех, четырех и

т. д. множеств. Пересечение множеств В, С и D обозначают так: В∩С∩D.

(Слайд 11) Задание 4. [3; 1]

1. Даны множества: А = {2; 3; 8}, В = {2; 3; 8; 11}, С = {5; 11}.

Найдите: а) А∩В; б) А∩С; в) С∩В.

2. Даны множества: А - множества всех натуральных чисел, кратных 10, В = {1; 2; 3;…, 41}.

Найдите А∩В.

3. Даны множества: А = {a, b, c, d}, B = {c, d, e, f}, C = {c, e, g, k}.

Найдите (А∩В)∩С.

(Слайд 12)

2) Объединением множеств А и В называют множество, состоящее из всех элементов,

которые принадлежат хотя бы одному из этих множеств - или

множеству А, или множеству В (рис. 3). Объединение множеств

А и В обозначают так: АUВ.

Это определение можно записать и так:

АUВ = {х | х А или х В}. Например, если А = {3; 9; 12} и

В = {1; 3; 5; 7; 9; 11}, то АUВ = {1; 3; 5; 7; 9; 11; 12}. Можно АUВ К

рассматривать объединение не только двух, но трех, четырех и т. д. Рис. 3

множеств. Объединение множеств В, С и D обозначают так: ВUСUD.

(Слайд 13) Задание 5. [3; 1]

1. Даны множества: А = {2; 3; 8}, В = {2; 3; 8; 11}, С = {5; 11}.

Найдите: а) АUВ; б) АUС; в) СUВ.

2. Даны множества: А = {a, b, c, d}, B = {c, d, e, f}, C = {c, e, g, k}.

Найдите (АUВ)UС.

3. Даны три числовых промежутка: А = (7,7; 11), В = [; ], С = (; 13].

Найдите (АUВ)UС.

(Слайд 14)

3) Разность А и В это множество элементов А, не принадлежащих В

(рис.4). Разность А и В обозначают так: А\ В. Например,

если А = {2; 4; 6; 8; 10} и В = {5; 10; 15; 20}, то А\ В={2; 4; 6; 8}.

А\ В К

(Слайд 15) Рис. 4

4) Дополнение множества А обозначают так: Ā (рис. 5).

Дополнение множества до множества К: Ā = К\А.

Например, если А = {3; 6; 9; 12} и

К = {1; 2; 3; 4; 5; 6; …}, то Ā = {1; 2; 4; 5; 7; 8; 10; 11; 13; …}.

Ответы: Рис. 5

Задание 1.

1. а) {2; 3; 4; 5}; б) {7; 8; 9}; в) {0; 1}; г) {5}. 3. г).

Задание 2.

1. а) 10N; б) -7 N; в) -10 Z; г) 2,5 Z . 2. а) нет; б) да; в) да; 3. а) да; б) нет.

Задание 3.

1. а) А D; б)А В; в)С А; г)С В. 2. а) нет; б) нет; в) да; г) да.

Задание 4.

1. а) А∩В = {2; 3; 8}; б) А∩С = Ø; в) С∩В ={11}. 2. А∩В = {10;20;30;40}. 3. (А∩В)∩С={с}.

Задание 5.

1. а) АUВ = {2; 3; 8; 11}; б) АUС = {2; 3; 5; 8; 11}; в) СUВ = {2; 3; 5; 8; 11}.

2. (АUВ)UС = {a, b, c, d, e, f, g, k}. 3. (АUВ)UС = (7,7; 13].

Приложение

Блок 2. Решение задач с помощью кругов (диаграмм) Эйлера.

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

Презентация. (Слайд 16) Портрет Леонарда Эйлера (1707-1783).

(Слайд 17) Задача 1.[3]

Расположите 4 элемента в двух множествах так, чтобы в каждом из них было по 3 элемента.

(Слайд 18) Задача 2.[3]

Множества А и В содержат соответственно 5 и 6 элементов, а множество А ∩ В - 2 элемента.

Сколько элементов в множестве А U В?

(Слайд 19) Задача 3.[2]

Каждая семья, живущая в нашем доме, выписывает или газету, или журнал, или и то и

другое вместе. 75 семей выписывают газету, а 27 семей выписывают журнал и лишь

13 семей выписывают и журнал, и газету. Сколько семей живет в нашем доме?

(Слайд 20) Задача 4.[1]

На школьной спартакиаде каждый из 25 учеников 9 -го класса выполнил норматив или по

бегу, или по прыжкам в высоту. Оба норматива выполнили 7 человек, а 11 учеников

выполнили норматив по бегу, но не выполнили норматив по прыжкам в высоту. Сколько

учеников выполнили норматив: а) по бегу; б) по прыжкам в высоту; в) по прыжкам при

условии, что не выполнен норматив по бегу?

(Слайд 21) Задача 5.[3]

Из 52 школьников 23 собирают значки, 35 собирают марки, а 16 - и значки, и марки.

Остальные не увлекаются коллекционированием. Сколько школьников не увлекаются

коллекционированием?

(Слайд 22) Задача 6.[1]

Каждый из учеников 9-го класса в зимние каникулы ровно два раза был в театре, посмотрев

спектакли А, В или С. При этом спектакли А, В, С видели соответственно 25, 12 и 23

ученика. Сколько учеников в классе?

(Слайд 23) Задача 7.[2]

В воскресенье 19 учеников нашего класса побывали в планетарии, 10 - в цирке и 6 - на

стадионе. Планетарий и цирк посетили 5 учеников; планетарий и стадион-3; цирк и

стадион -1. Сколько учеников в нашем классе, если никто не успел посетить все три места, а

три ученика не посетили ни одного места?

(Слайд 24) Задача 8.[2]

В одном классе 25 учеников. Из них 7 любят груши, 11 - черешню. Двое любят груши и

черешню; 6 - груши и яблоки; 5 - яблоки и черешню. Но есть в классе два ученика,

которые любят всё и четверо таких, что не любят фруктов вообще. Сколько учеников этого

класса любят яблоки?

(Слайд 25; слайд 26) Задача 9.[1]

На уроке литературы учитель решил узнать, кто из 40 учеников 9 -го класса читал книги А,

В, С. Результаты опроса выглядели так: книгу А прочитали 25 учеников, книгу В - 22

ученика, книгу С - 22 ученика; одну из книг А или В прочитали 33 ученика, одну из книг А

или С прочитали 32 ученика, одну из книг В или С - 31 ученик. Все три книги прочитали 10

учеников. Сколько учеников: а) прочитали только по одной книге; б) прочитали ровно две

книги; в) не прочили ни одной из указанных книг?

(Слайд 27) Задача 10.

На зимних каникулах из 36 учащихся класса только двое просидели дома, а 25 ребят ходили

в кино, 15 - в театр, 17 - в цирк. Кино и театр посетили 11 человек, кино и цирк - 10, театр и

цирк - 4. Сколько ребят побывало и в кино, и в театре, и в цирке?

Ответы:

Задача 2. 9 элементов.

Задача 3. 89 семей.

Задача 4. а) 18 учеников; б) 14 учеников; в) 7 учеников.

Задача 5. 10 школьников.

Задача 6. 30 учеников.

Задача 7. 29 учеников.

Задача 8. 14 учеников.

Задача 9. а) 15 учеников; б) 12 учеников; в) 3 ученика.

Задача 10. 2 ученика.

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №1. Алгебра логики. Понятие высказывания. Логические операции.

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

Термин «логика» - наука о способах доказательств и опровержений - происходит от греч. (логос), что означает «слово», «понятие», «смысл».

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

Основоположником логики как науки является древнегреческий философ и ученый Аристотель (384-322 гг. до н. э.). Он впервые разработал теорию дедукции, т.е. теорию логического вывода. Именно он обратил внимание на то, что в рассуждениях конкретного содержания утверждений, а из определенной взаимосвязи между их формами и структурами, большой вклад в развитие математической логики внесли такие ученные как:

Древнегреческий математик Евклид (330-275 гг. до н.э.) впервые

предпринял попытку упорядочить накопившиеся к тому времени обширные сведения по геометрии;

На протяжении многих веков различными философами и целыми

философскими школами дополнялась, усовершенствовалась и изменялась логика Аристотеля.

Немецкий философ и математик Г. Лейбниц (1646 - 1716). Он пытался построить универсальный язык, с помощью которого можно было бы решать споры между людьми, а затем и вовсе все «идеи заменить вычислениями».

Важный период становления математической логики начинается

с появления работ английского математика и логика Джорджа Буля (1815-1864). Он применил к логике методы современной ему алгебры -язык символов и формул, составление и решение уравнений. Им была создана своеобразная алгебра -алгебра логики. Создание алгебры логики явилось заключительным звеном в развитии формальной логики: алгебра логики поставила и решила в самом общем виде те задачи, которые рассматривались

в аристотелевой логике. Формальная логика в результате использования в ней развитого символического языка окончательно оформилась как логика символическая.

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

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

Приведем примеры высказываний.

1) «Москва - столица России»;

2) «Число 6 делится на 4 и на 2»;

3) «Все люди смертны»;

4) «Сократ - великий ученный современности»;

5) «7 < 4»;

6) Если юноша окончил среднюю школу, то он получает аттестат зрелости.

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

Очевидно, предложение «Да здравствуют наши спортсмены!» не является высказыванием.

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

Примерами элементарных высказываний могут служить высказывания 1) и 3),4).

Высказывания, которые получаются из элементарных с помощью грамматических связок «не», «и», «или», «если ..., то ...», «тогда и только тогда», принято называть сложными или составными. Так, высказывание 2) образовано из элементарных высказываний «Число 6 делится на 4», «Число 6 делится на 2», соединенных союзом «и». Высказывание 6) получается из простых высказываний «Юноша окончил среднюю школу», «Юноша получает аттестат зрелости» с помощью грамматической связки «если ..., то ...». Аналогично сложные высказывания могут быть получены из простых высказываний с помощью грамматических связок «или», «тогда и только тогда».

Договоримся обозначать конкретные высказывания начальными

заглавными и малыми буквами латинского алфавита А, В, С, D, ...; a,b,c,d,….. истинное значение высказывания - буквой и или цифрой 1, а ложное значение - буквой л или

цифрой 0. Если высказывание А истинно, то будем писать А = 1, а если А ложно, то А = 0 .

Логические операции над высказываниями

Определение2. Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.

Отрицание высказывания х обозначается х и читается «не х» или «неверно, что х».

Логические значения высказывания х можно описать с помощью таблицы

Таблицы такого вида принято называть таблицами истинности.

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

Пример 1. Применим операцию отрицания к высказыванию A: «Волга впадает в Каспийское море». Данное отрицание можно читать

так: «Неверно, что А» т.е. «Неверно, что Волга впадает в Каспийское море». Или же частицу «не» переносят на такое место (чаще всего ставят перед сказуемым), чтобы получилось правильно составленное предложение: «Волга не впадает в Каспийское

море». Таблица из определения 1. дает для данного высказывания

следующее логическое значение: ,

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

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

Конъюнкция высказываний х, у обозначается символом х&у или ( х ^у ), читается «х и у». Высказывания х, у называются членами конъюнкции.

Логические значения конъюнкции описываются следующей таблицей истинности:

Пример 2. Для высказываний «6 делится на 2», «6 делится на 3» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на 3», которое, очевидно, истинно.

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

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

Дизъюнкция высказываний х, у обозначается символом , читается «х или у ≫. Высказывания х, у называются членами дизъюнкции.

Логические значения дизъюнкции описываются следующей таблицей истинности:

Пример 3. Высказывание «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый».

В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.

Из определения операции дизъюнкции и отрицания ясно, что высказывание всегда истинно.

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

Импликация высказываний х, у обозначается символом , читается «если х, то у» или «из х следует у». Высказывание х называют условием или посылкой, высказывание у - следствием или заключением, высказывание - следованием или импликацией.

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

Пример 4. Высказывание «Если число 12 делится на 6, то оно делится на 3», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».

Употребление слов «если ..., то ...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание х ложно, то высказывание «Если х, то у» вообще не имеет смысла.

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

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

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

Эквиваленция высказываний х, у обозначается символом , читается «для того, чтобы х, необходимо и достаточно, чтобы у или х тогда и только тогда, когда у». Высказывания х, у называются членами эквиваленции.

Логические значения операции эквиваленции описываются следующей таблицей истинности:

Пример 5. Эквиваленция «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда ZP = ZQ» является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ ZP = ZQ либо одновременно истинны, либо одновременно ложны.

Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности.В этом случае, зная об истинности илиложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.

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

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

• Если металл нагревается, он плавится.

• Неправда, что философские споры неразрешимы.

• Деньги - продукт стихийного развития товарных отношений, а не результат договоренности или какого-либо иного сознательного акта.

2. Записать логической формулой следующие высказывания:

а) если на улице дождь, то нужно взять с собой зонт или остаться дома;

б) если - прямоугольный и стороны - равны, то

3. Проверить истинность высказывания:

а) , если , .

б) , если , .

в) , если , , .

4. Проверить истинность высказывания:

а) Чтобы завтра пойти на занятия, я должен встать рано. Если я сегодня пойду в кино, то лягу спать поздно. Если я лягу спать поздно, то встану поздно. Следовательно, либо я не пойду в кино, либо не пойду на занятия.

б) Я пойду либо в кино, либо в бассейн. Если я пойду в кино, то получу эстетическое удовольствие. Если я пойду в бассейн, то получу физическое удовольствие. Следовательно, если я получу физическое удовольствие, то не получу эстетического удовольствия.

5. . На вопрос: «Кто из трех студентов изучал дискретную математику?» получен верный ответ: «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий». Кто изучал дискретную математику?

6. Определите, кто из четырех студентов сдал экзамен, если известно:

если первый сдал, то и второй сдал;

если второй сдал, то третий сдал или первый не сдал;

если четвертый не сдал, то первый сдал, а третий не сдал;

если четвертый сдал, то и первый сдал.

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №2. Логические формулы, таблицы истинности.

Упражнение 1

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

1. Число 17 нечетное и двузначное

2. Неверно, что корова - хищное животное

3. На уроке физики ученики выполняли лабораторную работу и сообщали результаты исследований учителю

4. Если число делится на 2, то - нечетное.

5. Переходи улицу только на зеленый свет

6. На уроке информатики необходимо соблюдать особые правила поведения

7. При замерзании воды выделяется тепло

8. Если Маша - сестра Саши, то Саша - брат маши

9. если компьютер включен, то можно на нем работать

10. Водительские права можно получить тогда и только тогда, когда тебе исполниться 18 лет

11. Компьютер выполняет вычисления, если он включен

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

13. Тише едешь - дальше будешь

Упражнение 2

Составьте и запишите истинные сложные высказывания из простух с использованием логических операций

1. Неверно, что и

2. Z является min(Z,Y)

3. А является max(A,B,C)

4.Любое из чисел А,В,С положительно

5. Любое из чисел А,В,С отрицательно

6. Хотя бы одно из чисел А,В,С не отрицательно

7. Хотя бы одно из чисел А,В,С не меньше 12

8. Все числа А,В,С равны 12

9. Если Х делится на 9 то Х делится на 3

10. если Х делится на 2, то оно четное.

Упражнении 3.

Найдите значения логических выражений:

1. F=(00)(11)

2. F=(11)(10)

3. F=(0^0) ^(1^1)

4. F= ¬1^(11) (¬0^1)

5. F=(¬11) ^(1¬1) ^(¬10)

Построение таблиц истинности

Приоритет логических операций

1) инверсия 2) конъюнкция 3) дизъюнкция 4) импликация и эквивалентность

Как составить таблицу истинности?

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

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

(0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

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

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

Для составление таблицы истинности необходимо (алгоритм записать в тетрадь)

1. выяснить количество сток в таблице (вычисляется как 2ⁿ, где n- количество переменных)

2. выяснить количество столбцов = количеству переменных + количество логических операций

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

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

5. заполнить таблицу истинности

Пример: В классе оказалось разбито стекло. Учитель объясняет директору: это сделал Коля или Саша. Но Саша этого на делал, т.к. в это время сдавал мне зачет. Следовательно, это сделал Коля.

Решение:

Формализуем данное сложное высказывание.

К - это сделал Коля

С - это сделал Саша

Кол-во простых высказываний n = 2.

Форма высказывания: Е = ( К C ) & С К

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

Т.к. каждое из простых высказываний может принимать всего два значения (0 или 1), то количество разных комбинаций значений n высказываний - 2 ⁿ .

Количество строк в таблице = 2 ⁿ + строка на заголовок.

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

В нашем примере: количество строк - 2² + 1 = 5 ,

столбцов - 2 + 4 = 6

2. Начертить таблицу и заполнить заголовок

Первая строка - номера столбцов.

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

3. Заполнить первые n столбцов.

В нашем примере сначала заполняем 1-й и 2-й столбцы.

4. Заполнить остальные столбцы.

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

Итак, вычисляем значения 3-го столбца по значениям 2-го, потом значения 4-го - по значениям 1-го и 2-го…

К

С

С

К C

( К C ) & С

( К C ) & С К

1

1

0

1

0

1

0

1

0

1

0

1

1

0

1

1

1

1

0

0

1

0

0

1

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

Примеры.

1. Составим таблицу истинности для формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах - значения промежуточных формул и в последнем столбце - значение формулы. В результате получим таблицу:

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.

2. Таблица истинности для формулы :

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.

2. Таблица истинности для формулы :

Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых - 0, то есть является выполнимой.

Задачи:

1. Построить таблицу истинности для выражения F=(A B) ^( ¬A B), определить количество строк, столбцов и указать порядок действий

2. Построить таблицу истинности для выражения F=X Y ^ ¬Z

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №3. Законы алгебры логики.

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

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

Любой из этих законов может быть легко доказан с помощью таблиц истинности.

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

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

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

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

часть истинна, и что если левая часть истинна, то и правая часть истинна. Пусть истинна правая часть, т. е. х = 1, тогда в левой части дизъюнкция истинна по определению дизъюнкции. Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула х, или формула или обе эти формулы одновременно. Если х ложна, тогда (х & у) ложна, следовательно, х может быть только истинной. □

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

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

Пример 4. Тавтологией является формула х v х, выражающая закон исключенного третьего. □

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

Для логических операций установлен следующий порядок вычислений: 1) отрицание; 2 ) конъюнкция; 3) дизъюнкция (строгая и нестрогая); 4) импликация и эквивалентность.

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

фиксированный по умолчанию. Например, выражение трактуется как

Вопросы и задания:

1. Какие из рассмотренных логических законов аналогичны законам алгебры чисел, а какие нет?

2. Докажите второй закон де Моргана с помощью таблиц истинности.

3. Рассмотрите два сложных высказывания: F₁ = {если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3}; F₂- {если одно слагаемое делится на 3, а другое не делится на 3, то сумма не делится на 3}. Формализуйте эти высказывания, постройте таблицы истинности для каждой из полученных формул и убедитесь, что результирующие столбцы совпадают.

4. Формализуйте следующие высказывания и постройте для них таблицы истинности: F₁ = {если все стороны четырехугольника равны и один из его углов прямой, то этот четырехугольник является квадратом}; F₂ = {если все стороны четырехугольника равны, а он не является квадратом, то один из его углов не является прямым}.

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №4. Булевы функции. Функции алгебры логики. Представление произвольной функции в виде формулы алгебры логики.

Булева функция (логическая функция, функция алгебры логики)- это функция одной или нескольких переменных I, гдеZ - логические переменные, ' т.е. и значения аргументов, и значение функции - ноль или единица . Тем самым, булева функция п переменных есть функция на•_г множестве п -мерных векторов, компоненты которых'равны 0 или 1:. Можно применять векторные обозначения |для сокращения записи. Пользуясь другими терминами, можно f[считать областью определения булевой функции множество вершин i п -мерного единичного куба. На рис.19 изображена Г функция 3 переменных ff принимающая значение 1 на t¹наборах (001), (011), (100) [Обратите внимание на допустимую форму записи: можно не разделять запятыми значения аргументов -все они однозначные числа.

_;Если число переменных равно п и любая из них может независимо от других принимать 2 :значения, то число различных п - векторов равно. Относительно

T каждой функциивсе множество разбивается на два класса // -векторов прообраз значения 0 и прообраз значения 1 функции Z Мы будем рассматривать только всюду определенные функции

Если считать, что переменныеобозначают истинность (значение 1) или ложность (значение 0) высказываний-аргументов, то функция Z выражает истинность или ложность определенного сложного высказывания при различных сочетаниях значений аргументов Например, конъюнкция двух высказываний - это сложное высказывание, истинное тогда и только тогда, когда истинны оба составляющих простых высказывайся. С функциональной точки зрения конъюнкцию можно рассматривать как булеву функцию двух логических переменных, принимающую значение 1 тогда и только тогда, когда оба аргумента равны 1.

Для задания логической функции нужно указать каким-либо образом, какое значение принимает функция на тех или иных наборах значений аргументов. Поэтому естественным является табличное представление булевых функций -для функции - таблица изстрок - п -мерных булевых векторов в алфавитном порядке, каждому из которых сопоставлено значение функции Z , равное 0 или 1. Заметим, что булева функция Z является на характеристической функцией того множества точек , для которых Z = 1 . В таблице 5 представлены все функции одной переменной - их 4 В 1 -м столбце - значения переменной X ; в каждом из последующих -значения соответствующей функции, обозначение функции - в 1-й строке Во 2-м столбце - функция-константа , в 5-м - функция-

константа. В 3-м столбце тождественная функция Z = X , в 4-м - функция , которую обозначают также и называют отрицанием.

Второй способ обозначения подчеркивает, что отрицание- одноместная функция аргумента X .

Аналогично могут быть заданы функции нескольких переменных Некоторые из них - для двух переменных - в табл.6 Сравните их (столбцы 3-5) с таблицами истинности основных логических операций конъюнкции, дизъюнкции, импликации, эквивалентности,'для которых значения аргументов и результатов операций обозначались буквамиИ, Л Отметим также, что с арифметической точки зрения,т.е. если рассматривать 0 и 1 как натуральные числа с обычными операциями

арифметики,выполнены равенства:

Поэтому конъюнкциюназывают умножением и записывают

со знаком произведения: или вообще - как в алгебре - без

знака: XY . Дизъюнкцию иногда удобно называть логическим сложением, а связываемые ею члены - логическими, или дизъюнктивными слагаемыми. Однако следует иметь в виду, что, во-первых, на наборе (1, 1) значение дизъюнкции не совпадает с арифметической суммой, а, во-вторых, термин "сумма" для логических переменных употребляется и в другом значении, представленном в той же табл.6. В двух последних столбцах табл.6 представлены функции, которые не встречались раньше, а именно:

Сумма по модулю 2- функция двух переменных, равная 0, если значения аргументов совпадают, и 1 в противном случае; ее обозначение -. Арифметическое значение-остаток от деления числа (X + Y) на 2, - отсюда название. Другое название - неэквивалентность, поскольку выполнено тождество:

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

Штрих Шеффера- функция двух переменных, равная 0 тогда и только тогда, когда оба аргумента равны 1. Обозначение:, условное название " X несовместно с Y". Выполнены тождества:

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

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

представляет функцию трех переменных, заданную в последнем столбце табл.7. Для получения таблицы нужно приписать слева к столбцу значений стандартный (для каждого п ) перечень всех /; -наборов, расположенных в алфавитном порядке, т.е. описанную в §4 гл 2 таблицу

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

Например, функциюиз табл.7 можно задать кортежем: [3,5,6,7], а функциюиз той же таблицы - [0, 1, 4, 5]. Это особенно удобно, если функция принимает значение Ь на небольшом числе наборов, по сравнению с их общим количеством.

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

Важный пример применения булевых функций дают арифметические действия над двоичными числами: поскольку возможные знаки в двоичной системе суть 0 и 1, то зависимости знаков результата от знаков слагаемых/сомножителей выражаются булевыми функциями. При сложении двух однозначных двоичных чисел А и В знак суммы в младшем разряде равен, а знак переноса возникает только если оба слагаемых равны 1, т.е.Умножение однозначных двоичных чисел тождественно конъюнкции, что фактически отмечено выше.

В табл.7 представлены 3 функции трех переменных. Первую из них

называют иногда функцией большинства - ее значение

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

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

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

от аргумента Y , а функцияот аргументов X, Z . Действительно, если, например, X = 0,7 = 1, то и при Y = О (набор 001), и при Y = (набор 011) выполнено равенство . Таким же образом проверяются

остальные 3 сочетания переменных X и Z . Введем определение Несущественные (фиктивные) переменные:для функции

переменная называется

несущественной, если выполнено

при всех значениях

Таким образом, для функциинесущественной переменной является Y, а для функции- несущественные переменные X и Z . Если относить к функциям п переменных и функции, существенно

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

булевых векторов длины, т.е.. Для одной переменной это число равно 4 (см.

табл.5); для двух переменных - 2⁴ =16; сщя трех переменных - 2⁸ = 256 ; для

нетырех переменных -2^|6 = 65536и т.д. Таблица всех 16 функций 2 переменных содержится в файле материалов. Множество всех логических функций, от любого конечного числа

переменных обозначается

Если- фиктивная переменная функции

то первая половина задающего ее столбца значений совпадает со второй, и если отбросить вторую половину таблицы этой функции и затем удалить 1-й столбец (состоящий из нулей), то останется таблица

некоторой функции ( п -1) переменных. Аналогично, если

- фиктивная переменная функции и вычеркнуть

из таблицы столбец переменной и все строки с единичным

значением (т е строки, в которых ), то останется таблица

функции . Будем говорить, что g

получается изудалением, а- введениемфиктивной

переменной

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

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

функций. В этом смысле, использованные выше записи

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

функции одной переменной Y , имеющей столбец значений

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

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №5. Совершенные нормальные формы. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма.

Для одной и той же формулы можно составить множество равносильных ей КНФ. Но среди них существует единственная КНФ со свойствами совершенства.

Перечислим свойства совершенства для КНФ:

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

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

3. Ни один множитель не содержит одновременно переменную и ее отрицание.

4. Ни один множитель не содержит одну и ту же переменную дважды.

КНФ, для которой выполняются свойства совершенства называется совершенной КНФ (СКНФ).

Любая не тождественно истинная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в использовании таблицы истинности для :

1. Составляют СДНФ.

2. Для получения СКНФА строят отрицание СДНФ, т.е.

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

Другой способ основан на равносильных преобразованиях

Приведем соответствующий алгоритм:

1. Путем равносильных преобразований получить какую - либо КНФ.

2. Если какая-либо элементарная дизъюнкция В не содержит переменную х_i , то вводят ее, используя равносильность . И используют свойство дистрибутивности.

3. Если в КНФ входят две одинаковые дизъюнкции В, то лишнюю отбрасывают, используя свойство идемпотентности В B º B.

4. Если какая-либо дизъюнкция содержит x_i вместе с отрицанием, то В º 1. И В исключают из КНФ.

5. Если какая-либо дизъюнкция содержит переменную x_i дважды, то одну из них отбрасывают, используя свойство x_iv x_i º x_i.

Примеры.

1. Составить СКНФ для формулы по таблице истинности и путем равносильных преобразований.

Составим таблицу истинности, которая содержит 4 строки, для

Тогда

Такую же формулу мы получили бы, строя СКНФА на наборах, при которых А ложна.

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

2.Аналогичное задание для формулы

Таблица истинности имеет вид:

Составим СКНФА на наборах, при которых А=0:

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

3. Путем равносильных преобразований получить СКНФА.

Задачи для самостоятельного решения.

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

2. Найдите СДНФ для всякой тождественно ис­тинной формулы, содержащей: 1) одно переменное, 2) два переменных, 3) три переменных.

3.Найдите СКНФ для всякой тождественно лож­ной формулы, содержащей: 1) одно переменное, 2) два переменных, 3) три переменных.

4. Докажите равносильность формул и сравнением их совершенных нормальных форм (конъюнктивных или дизъюнктивных).

5. Найдите более простой вид формул, имеющих следующие совершенные нормальные формы:

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

1. Перечислить свойства совершенства для ДНФ.

2. Перечислить свойства совершенства для КНФ.

3. Сколько для одной формулы можно составить СДНФ и СКНФ?

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

5. Связь между СДНФА и СКНФА.

6. Как путем равносильных преобразований составить СДНФ и СКНФ формулы?

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №6. Минимизация в классе дизъюктивных нормальных форм. Формула номера набора в таблице истинности. Понятие минимальной ДНФ.

1. Формула номера набора в таблице истинности.

Для удобства задания булевой функции введем формулу, связывающую номер набора в таблице истинности со значениями переменных в наборе: , n - количество переменных в функции, i - порядковый номер единицы или нуля в наборе. Рассмотрим пример: f() или f(3,5,6,7)=1. Найдем наборы при которых функция равна 1, тогда на остальных наборах функция равна 0: функция от трех переменных, значит, n =3,

3=21+20=23-2+23-3 : (011);

5=22+20=2 3-1+23-3 : (101);

7=22+21+20 = 2 3-1+2 3-2 + 2 3-3 :(111);

Для N =8 : (000).

Заметим, что предпоследний набор состоит из единиц, последний - из нулей.

2.Понятие минимальной ДНФ. Метод минимизирующих карт.

Любую булеву функцию моно представить в виде ДНФ или КНФ. Равносильными преобразованиями можно представить формулу с меньшим количеством переменных. Например:

первое преобразование не выводит формулу из класса ДНФ, а последнее - выводит. Будем минимизировать формулы только в классе ДНФ.

ДНФ формулы А называется минимальной. Если она содержит наименьшее число вхождений переменных по сравнению с остальными ДНФ этой формулы.

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

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

Булева функция должна быть задана таблицей истинности или какой -либо совершенной нормальной формой. Составляют карту, которая имеет вид:

далее используют утверждение:

если какая - либо конъюнкция, содержащая все переменные и принадлежащая j - той строке карты, не входит в СДНФ, выражающую функцию, то любая конъюнкция этой строки не входит ни в какую ДНФ, выражающую исходную функцию.

Опираясь на данное утверждение, получаем алгоритм построения минимальной ДНФ.

1. Отметим в карте строки, в которых конъюнкция (в последнем столбце) не принадлежит СДНФ формулы;

2. Вычеркнем все конъюнкции в этих строках и во всех остальных строках карты;

3. В каждой строке выберем из оставшихся конъюнкций конъюнкции с наименьшим числом переменных, остальные вычеркнем;

4. В каждой строке выберем по одному оставшемуся элементу и составим из них ДНФ;

5. Из всех составленных ДНФ выберем минимальную.

Пример: Составим карту:

x

y

z

xy

xz

yz

xyz

-

x

y

xy

x

y

xy

+

x

z

x

xz

z

xz

+

y

z

y

z

yz

yz

-

y

y

y

y

-

z

z

z

z

+

х

x

x

x

+

-

Вычеркнем конъюнкции, отсутствующие в формуле и соответствующие строки. Вычеркнутые конъюнкции вычеркнуть и в остальных строках.

Составим всевозможные ДНФА, выбирая из каждой строки по одной оставшейся конъюнкции:ДНФ2А является минимальной.

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №7. Метод минимизирующих карт. Метод Квайна.

Метод Квайна.

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

Рассмотрим этот метод на примере. Пусть заданы номера наборов из 4-х переменных, на которых функция равна единице : f(2,5,6,7,10,12,13,14) = 1. Необходимо составить СДНФ:

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

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

abcd

1V

0

1V

0

1V

0

0

1V

0

1V

0

1V

0

0

0

0

0

1

0

0

0

0

1

0

0

0

1

1

0

0

0

0

0

0

0

0

0

1V

1V

0

0

0

0

0

0

1

0

1

Выбранные ячейки отметим знаком «V». На последнем этапе минимизации получаем ДНФ:

Отметим, что в общем случае решений может быть несколько.

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №8. Метод минимизирующих карт. Метод Карно.

Метод Карно.

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

00

01

10

11

000

010

011

001

100

110

111

101

0000

0010

0011

0001

0100

0110

0111

0101

1100

1110

1111

1101

1000

1010

1011

1001

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

0

c

1

0

d

0

0

1

1

1

a

1

1

0

1

0

1

0

0

Получим такую же ДНФ:

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

1. Определение минимальной ДНФ.

2. Что собой представляет минимизирующая карта?

3. Сформулировать утверждение, которое используется в методе минимизирующих карт.

4. Алгоритм построения минимальной ДНФ с помощью минимизирующей карты.

5. Этапы минимизации СДНФ при применении метода Квайна.

6. Что представляет собой карта Карно?

7. Сколько ячеек можно включать в контуры и почему?

8. Что представляет собой единичный n-мерный куб?

9. Какие наборы входят в множество Nf?

10. Что называется (n-r)- мерной гранью? Как определяется ранг конъюнкции и ранг ДНФ?

11. Задача минимизации в геометрической форме.

12. Какая грань называется максимальной? Что такое простая импликанта? Какая ДНФ называется сокращенной?

13. Методика построения сокращенной ДНФ.

14. Какое покрытие называется неприводимым? Какие ДНФ называются тупиковыми?

15. Алгоритм построения ДНФ Квайна.

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №10. Логические основы построения ЭВМ

Логические схемы и логические функции

Любую сложную логическую функцию можно реализовать, имея простой набор базовых логических операций. Простейшие логические элементы (ЛЭ) реализованы аппаратно (схемно). Условные обозначения базовых логических элементов приведены на рис. 2.1.

Замечание 1. Ввиду технологических особенностей наиболее просто реализуются логические элементы НЕ, И-НЕ, ИЛИ-НЕ.

Переход от логической схемы к формуле логической функции

Переход от логической схемы (ЛС), построенной из логических элементов, требует знания булевых функций, реализуемых ЛЭ. Начиная от входов ЛС, используя принцип суперпозиции (подстановки функций в качестве аргументов в другие функции), получаем на выходе функцию, реализуемую всей ЛС.

Пример 1. Рассмотрим переход от ЛС к формуле логической функции для ЛС, изображенной на рис. 2.

Переход от алгоритма работы к логической схеме

Таблица 2.1

Таблица истинности

полусумматора

а

s

p

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1Такой переход осуществляется в следующей последовательности: задача →

алгоритм → таблица истинности → формула функции → логическая схема.

Пример 2. Построить логическую схему полусумматора. Эта схема должна суммировать два одноразрядных двоичных числа и вырабатывать их сумму s и перенос в следующий разряд р. Следует отметить, что в двоичной системе счисления 0 + 0 = 1, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10. Перенос в старший разряд возникает только в последнем случае. Алгоритм сложения записан таблицей истинности - табл. 2.1.

Анализ таблицы истинности полусумматора показывает, что логическая функция s двух аргументов a и b - это неравнозначность или «исключающее ИЛИ» (см. табл. 1.4), а p - это конъюнкция (см. табл. 1.2). Имеем формулы:

Логическая схема полусумматора изображена на рис. 2.3, а ее условное обозначение - на рис. 2.4.

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

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №10. Некоторые логические операции. Двоичное сложение.

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

Штрих Шеффера - это новое высказывание , обозначаемое х|y, ложное тогда и только тогда, когда оба высказывания х и у истинны. Приведем таблицу истинности:

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

Используя основные равносильности, можно эту операцию выразить и через другие, например:

Отрицание высказывания можно представить в виде :

Стрелка Пирса - это новое высказывание, обозначаемое х¯ у, истинное тогда и только тогда, когда оба высказывания ложны. Приведем таблицу истинности:

Стрелка Пирса - это отрицание дизъюнкции или конъюнкция отрицаний х и у:

Стрелку Пирса можно прочесть так: не х и не у.

Отрицание высказывания выражается через стрелку Пирса:

Пример: составить КНФ и ДНФ для формулы

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

Полученная формула является одновременно ДНФ и КНФ.

Двоичное сложение - это новое высказывание, обозначаемое х+у, ложное тогда и только тогда. Когда оба высказывания имеют одинаковые логические значения. Приведем таблицу истинности:

Двоичное сложение - это отрицание эквиваленции:

Познакомимся с законами для двоичного сложения:

1. коммутативность: х+у º у+х;

2. ассоциативность: х+у+z º x+(y+z);

3. дистрибутивность: x(y+z) º xy +xz;

4. х+0 º х;

5.

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

Тема 2. Основные понятия и аксиомы алгебры логики.

Лекция №12. Полином Жегалкина.

Познакомимся с определением полинома˸

Любую булеву функцию можно представить в виде двоичной суммы различных одночленов (конъюнкций), в которые все переменные входят не выше, чем в первой степени и константы 1 или 0, ᴛ.ᴇ. булева функция представима в виде˸

Причем, такое представление единственное.

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

Существует два способа представления булевой функции в виде полинома˸ метод неопределенных коэффициентов и метод построения полином по формуле. Опишем каждый метод подробно.

Метод неопределенных коэффициентов.

Перепишем полином в виде ˸

где K_i - конъюнкции, число которых равно 2ⁿ - 1, - вектор коэффициентов, где b_I Î{0,1}.

Коэффициент b_I указывает на присутствие или отсутствие соответствующей конъюнкции в полиноме.

Алгоритм поиска вектора коэффициентов и составления полинома.

1. по таблице истинности составить систему уравнений ,где (a₁ , a₂ , …, a_n) - все наборы значений переменных таблицы истинности для данной булевой функции (вместо переменных в полином подставить их соответствующие значения, в левой части уравнения - соответствующее этому набору значение функции).

3. пользуясь таблицей истинности для двоичного сложения и конъюнкции, вычислить коэффициенты b_I ;

4. подставить в полином значения коэффициентов и составить полином.

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

Рассмотрим пример.

Разложить функцию f(x, y, z) = (01101000).

Составим полином

Cоставляя уравнения, нулевые конъюнкции будем исключать˸

№1 = 2^3-3˸ (001)˸ 0 = b₀+ b₃;

№2 = 2^3-2 ˸ (010)˸ 1= b₀+b₂;

№3 = 2^3-2+2^3-3˸ (011)˸ 1= b₀+b₂+b₃+b₆;

№4 = 2^3-1˸ (100)˸ 0= b₀+b₁;

№5 = 2^3-1+2^3-3˸ (101)˸ 1 = b₀+b₁+b₃+b₅;

№6 = 2^3-1+2^3-2˸ (110)˸ 0 = b₀+b₁+b₂+b₄;

№7˸ (111)˸ 0= b₀+b₁+b₂+b₃+b₄+b₅+b₆+b₇;

№8˸ (000)˸ 0 = b₀.

Решая систему , получим вектор коэффициентов˸ (0,0,1,0,1,1,0,1), тогда функция раскладывается в полином˸

P(x,y,z) = 0 + y +xy + xz +xyz.

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

Построение полинома по формуле.

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

Алгоритм построения полинома по формул˸

1. заменить формулу равносильной, содержащей только операции конъюнкцию и отрицание;

2. снять отрицания, пользуясь равносильностью˸

3. раскрыть скобки˸

4. упростить, используя идемпотентность ˸ х+х =0, равносильность х+0=х.

Рассмотрим примеры.

Задачи для самостоятельного решения.

1. Построить таблицу истинности для формулы Составить для данной формулы КНФ и ДНФ.

2. Методом неопределенных коэффициентов разложить функции в полиномы˸ а) f(x,y,z)= (01001110); б) f(x,y,z) = (11000101); в) f(x,y)= (0101); г) f(x,y)=(1011)

3. Методом неопределенных коэффициентов и путем равносильных преобразований построить полиномы для формул˸ а) х®у; б) (х|y)¯z; в) (x®y)(y¯z); г) ((x®y)v)|x.

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

1. Привести таблицу истинности для штриха Шеффера. Выразить штрих Шеффера через отрицание и конъюнкцию. Выразить отрицание через штрих Шеффера.

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

3. Привести таблицу истинности для двоичного сложения. Выразить двоичное сложение через отрицание и эквиваленцию.

4. Перечислить свойства двоичного сложения.

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

6. Алгоритм построения полинома методом неопределенных коэффициентов.

7. Алгоритм построения полинома по формуле.

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

0

Тема 2. Основные понятия и аксиомы алгебры логики.

Практическое занятие №1. Применение алгебры логики (решение текстовых логических задач или алгебра переключательных схем).

Тема 2. Основные понятия и аксиомы алгебры логики.

Практическое занятие №2. Решение логических задач средствами алгебры логики

1. Методика решения логических задач

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

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

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

Формальный способ решения логических задач предполагает несколько шагов:

1. Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.

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

3. Составить единое логическое выражение для всех требований задачи (иногда единое выражение составлять не требуется).

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

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

6. Проверить, удовлетворяет ли полученное решение условию задачи.

Замечание 1. Логическая задача может иметь не одно, а несколько решений. При этом построенное логическое выражение является истинным для нескольких наборов значений простых высказываний.

Примеры

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

Иногда задано или получено в процессе решения задачи несколько простых или сложных высказываний, истинность которых известна. В этом случае обычно достаточно взять конъюнкцию этих высказываний и определить набор простых высказываний, на котором эта конъюнкция принимает значение ИСТИНА (см. пример 1). Этот набор и будет решением задачи. Решение может отсутствовать, и решений может быть несколько.

Пример 1. На вопрос, кто из трех студентов изучал логику, был получен ответ: «Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из студентов изучал логику?

Для решения этой задачи обозначим Р1, Р2, Р3 простые высказывания, что соответственно первый, второй, третий студенты изучали логику. Из условия задачи следует истинность высказывания . Строим таблицу истинности для полученного выражения (табл. 3.1):

Таблица 1

Таблица истинности функции

Из таблицы истинности видно, что логику изучал только третий студент.

2. Применение логических операций при решении задач на ЭВМ

В MS Excel есть встроенные логические константы ЛОЖЬ и ИСТИНА и встроенные булевы функции НЕ, И, ИЛИ. Как любые другие функции, логические функции удобно вводить с помощью Мастера функций.

Примеры

Пример 1 Составим таблицу истинности для функции из примера 1.9 с помощью MS Excel.

Можно сразу задать выражение для функции у(a,b), но удобнее (как сделано ранее в параграфе 1.3.1) разбить выражение на отдельные части. Выразим значения вспомогательных переменных p и r через булевы функции: , .

Таблица истинности в MS Excel в режиме отображения формул - рис. 3.1, а в режиме отображения значений - рис. 2

Рис. 1. Таблица истинности в MS Excel (в режиме отображения формул)

Рис. 3.Таблица истинности в MS Excel (в режиме отображения значений)

Получили тот же результат: константа ИСТИНА.

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

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

Преобразование логических схем (ЛС) можно выполнить так. Записать логическую функцию, реализуемую ЛС, затем упростить полученное выражение и составить новую ЛС, реализующую его.

Примеры

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

По закону дистрибутивности вынесем a за скобки:

.

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

.

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

.

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

Введем вспомогательный логический множитель :

.

На основании дистрибутивного закона раскрываем скобки и комбинируем (в соответствии с переместительным законом) два крайних и два средних логических слагаемых:

Используем закон поглощения:

.

Пример 3.Требуется упростить: .

Способ 1. Применим закон дистрибутивности:

.

К выражению в скобках применим закон противоречия:

.

Применим закон исключения констант:

.

Способ 2. Перемножим скобки (как в обычной алгебре чисел) на основании дистрибутивного закона:

.

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

.

Используем законы исключенного третьего и исключения констант:

.

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

.

Применяем закон идемпотентности

.

Пример 4. Упростить ЛС из примера 2.1 (рис. 2.2). Логическое выражение, описывающее ЛС, имеет вид: .

Применим ко второму слагаемому закон де Моргана:

.

Применяем закон двойного отрицания:

.

Последнее выражение это неравнозначность относительно логических выражений и . Поэтому имеем:

.

Осталось нарисовать ЛС.

Пример 5. Составить логическую схему, реализующую логическую функцию f(x, y, z), заданную таблицей истинности (табл. 3.5).

Таблица 5

Таблица f(x, y, z)

x

y

z

f

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

0Выберем строки таблицы, где значения функции равны 1. Таких строк 3, т. е. функция равна 1 только для этих трех наборов переменных. Отсюда выражение для функции можно записать так:

.

Замечание 3 Последнее выражение называется совершенной дизъюнктивной нормальной формой (СДНФ).

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

.

Применяя законы исключенного третьего и исключения констант, имеем:

.

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

.

Применяя закон де Моргана имеем:

.

Получилась очень простая логическая схема (рис. 3.5):

Тема 2. Основные понятия и аксиомы алгебры логики.

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

1. Определите, является ли последовательность символов формулой:

Р еш е н и е: л) Данная последовательность не является формулой. В самом деле, пропозициональные переменные согласно п. а) определения формулы являются формулами. Следовательно, согласно п. б) этого определения последовательность

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

м) Согласно пп. а) и б) определения формулы пропозициональные переменные Р, Q, R и выражения будут формулами. Далее, формулами будут выражения

Наконец выражение представляющее

собой данную последовательность, также является формулой.

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

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

ное высказывание. Следовательно, формула не является ни тавтологией, ни тождественно ложной формулой.

4. Составив таблицы истинности следующих формул, докажите, что они являются тавтологиями:

Задания для самостоятельной работы:

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

1 вариант:

2 вариант:

3 вариант:

4 вариант:

5 вариант:

6 вариант:

7 вариант:

8 вариант:

9 вариант:

10 вариант:

11 вариант:

12 вариант:

Р еш е н и е : 7) Пользуясь определениями логических связок (операций над высказываниями), составим таблицу истинности данной формулы (логические значения этой формулы записаны в последнем столбце таблицы, где сама формула обозначена

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

2. Составив соответствующие таблицы истинности, докажите, что все следующие формулы являются тавтологиями:

1 вариант: a) b)

2 вариант: a) b)

3 вариант: a) b)

4 вариант: a) b)

5 вариант: a) b)

6 вариант: a) b)

7 вариант: a) b)

8 вариант: a) b)

9 вариант: a) b)

10 вариант:a) b)

3. Установите следующие равносильности:

1. вариант:

2 вариант:

3 вариант:

4 вариант:

5 вариант:

6 вариант:

7 вариант:

8 вариант:

9 вариант:

10 вариант:

Тема 2. Основные понятия и аксиомы алгебры логики.

Практическое занятие 4. Построение СДНФ и ее минимизация

Для данной формулы булевой функции

а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований;

б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте "а");

в) указать минимальную ДНФ и соответствующую ей переключательную схему.

Варианты заданий

Тема 2. Основные понятия и аксиомы алгебры логики.

Практическое занятие 5. Метод минимизирующих карт. Метод Квайна.

Записать формулу функции f(x1,x2,x3) и минимизировать ее графическим методом,

методом неопределенных коэффициентов,

методом минимизирующих карт Карно,

методом Квайна.

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

Для метода минимизирующих карт вывести на экран последовательность минимизирующих карт, СДНФ и МДНФ.

Сравнить полученные результаты.

x₁

x₂

x₃

f

0

0

0

1

0

0

1

1

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

Решение:

Графический метод минимизации функции:

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

При количестве переменных не более 4-х все возможные тупиковые и саму минимальную формы можно просто увидеть на пространственной диаграмме - n-мерном (в нашем примере - 3-х мерном) кубе - декартовом графике (рисунок), где на осях, соответствующих переменным, отображены точки их возможных состояний (0 или 1). Точки-состояния, в которых (согласно таблице истинности) функция принимает единичные значения, изобразим более крупными:

(у нас точки (0,0,0), (0,0,1), (0,1,1), (1,0,1), (1,1,1))

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

Ребро ^┐x ·^┐y соединяет точки ^┐x·^┐y·^┐z и ^┐x·^┐y·z

:

( ^┐x·^┐y·^┐z )+( ^┐x·^┐y·z) = ^┐x·^┐y ·( ^┐z + z) =^┐x·^┐y

А грань будет соответствовать z

По диаграмме задача минимизации сводится к объединению максимума вершин, на которых функция принимает единичные значения, в минимум ребер.

В нашем случае, минимальная ДНФ равна:

f(x,y,z)=

перейдем к исходным переменным х1,х2 и х3,

им соответствуют переменные x,y,z

МДНФ: f(x₁,х₂,х₃)=

Минимизация методом неопределенных коэффициентов:

Метод неопределенных коэффициентов.

Суть метода состоит в преобразовании ДСНФ в МДНФ.

На основании теоремы Жегалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):

Алгоритм определения коэффициентов:

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

2. Напротив каждого выражения поставить соответствующее значение функции.

3. Выбрать строку, в которой значение функции и приравнять все к нулю.

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

5. Проанализировать оставшиеся коэффициенты в единичных строках.

6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно.

7. Записать исходный вид функции.

Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.

Представим функцию f(x₁,x₂,x₃) в виде следующей

СДНФ:

Составляем схему:

Приравняем 0 в каждом уравнении все коэффициенты,

кроме тех, которые отвечают конъюнкциям,

которые содержат, наименьше число переменных:

Итак, получим МДНФ

Тема 2. Основные понятия и аксиомы алгебры логики.

Практическое занятие 6. Метод минимизирующих карт. Метод Карно.

Метод Квайна:

Составим СДНФ функции:

-сокращенная ДНФ

И построим матрицу Квайна

Матрица Квайна:

Выписываем

тупиковая ДНФ:

(для столбцов, где стоит одна *)

\/

Выбираем из тупиковых минимальную: \/

Минимизация, с помощью карт Карно:

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

х2

х3

-

х1

0

0

0

1

1

1

1

0

0

000

001

011

010

1

100

101

111

110

Подставив значения функции, получим

х2

х3

-

x1

0

0

0

1

1

1

1

0

0

1

1

1

0

1

0

1

1

0

СДНФ функции состоит из пяти слагаемых:

Выписываем тупиковые ДНФ:

\/.

Выбираем из тупиковых минимальную ДНФ: \/.

ВЫВОД:

Сравнивая МДНФ, полученную разными способами (графическим методом,

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

Тема 2. Основные понятия и аксиомы алгебры логики.

Практическое занятие 7. Логические основы построения ЭВМ

В электронных таблицах ECXEL определены несколько операций: И, ИЛИ, ЕСЛИ-ТО ИНАЧЕ, (следование), НЕ.

Логическая функция И

Синтаксис И (ВЫСК1,ВЫСК2,...)

Здесь и далее (ВЫСК1,ВЫСК2,...)- это от 1 до 30 проверяемых условий, которые могут иметь значение либо ИСТИНА, либо ЛОЖЬ.

Пример 1

• И(ИСТИНА; ИСТИНА) равняется ИСТИНА

• И(ИСТИНА; ЛОЖЬ) равняется ЛОЖЬ

• И(2+2=4; 2+3=5) равняется ИСТИНА

Логическая функция ИЛИ

Синтаксис ИЛИ(ВЫСК1,ВЫСК2,...)..)

Пример 2

• ИЛИ(ИСТИНА;ЛОЖЬ) равняется ИСТИНА

• ИЛИ(1+6=1;2+6=5) равняется ЛОЖЬ

Логическая функция НЕ

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

Синтаксис НЕ(ВЫСК)

Пример 3

• НЕ(ЛОЖЬ) равняется ИСТИНА

• НЕ(1+1=2) равняется ЛОЖЬ

Логическая функция ЕСЛИ

Возвращает одно значение, если заданное условие при вычислении дает значение ИСТИНА, и другое значение, если ЛОЖЬ.

Функция ЕСЛИ используется для условной проверки значений и формул.

Синтаксис ЕСЛИ(ВЫСК; значение_если_истина; значение_если_ложь)

Пример 4

В следующем примере, если значение ячейки A1=10, то лог_выражение имеет значение ИСТИНА и вычисляется сумма для ячеек B1:B5. В противном случае, лог_выражение имеет значение ЛОЖЬ и возвращается пустой текст ("НЕВЕРНО".

ЕСЛИ(A1=10;СУММ(B1:B5); "НЕВЕРНО")

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

1. Проработать примеры, указанные в теории.

2. Привести примеры записи логических функций в электронных таблицах ECXEL для высказываний на формализованном языке математики.

3. Привести примеры записи логических функций в электронных таблицах ECXEL для высказываний на формализованном языке математики вида: 5=7, 2*3=8, 2*8=16 и т. д.

4. Решить в электронных таблицах квадратное уравнение.

Тема 3. Предикаты

Лекция №1. Понятие предиката.

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

Например, в рассуждении «Всякий ромб - паралле­лограмм;ABCD - ромб; следовательно, ABCD - парал­лелограмм» посылки и заключение являются элемен­тарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следова­тельно, алгебра логики, будучи важной частью логи­ки, оказывается недостаточной в анализе многих рассуждений.

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

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

Логика предикатов расчленяет элементарное высказывание на субъект (буквально - подлежащее, хотя оно и может играть роль дополнения) и предикат (буквально - ска­зуемое, хотя оно может играть и роль определения).

Субъект - это то, о чем что-то утверждается в выс­казывании; предикат - это то, что утверждается о субъекте.

Например, в высказывании «7 - простое число», «7» -субъект, «простое число» - предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х - простое чис­ло». При одних значенияхх, (например, х = 13, х =17 ) эта форма дает истинные высказывания, а при других значениях х (например, х = 10 , х = 18 ) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множе­стве N, и принимающую значения из множества {1,0}.

Здесь предикат становится функцией субъекта и выра­жает свойство субъекта.

Определение. Одноместным предикатом Р(х) на­зывается произвольная функция переменного х, опреде­ленная на множестве М и принимающая значения из

множества {1,0}.

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

Множество всех элементов х Î М , при которых преди­кат принимает значение «истина», называется множеством истинности предиката Р(х), то есть множество истиннос­ти предиката Р(х) - это множество 1р = {х| х Î М, Р(х) = 1}.

Так, предикат -Р(х) - «х - простое число» определен на множестве N, а множество Iр для него есть множест­во всех простых чисел.

Предикат Q{x} - « sin х = 0 » определен на множествеR, а его множество истинности I_q= {x| x = pk; kÎ Z}.

Предикат F(x) - «Диагонали паралле­лограмма х перпендикулярны» определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.

Приведенные примеры одноместных предикатов вы­ражают свойства предметов.

Рассмотрим примеры предикатов:

Р(х): «х² + 1> 0, xÎ R»; область определения предиката М= R и область истинности - тоже R, т.к. неравенство верно для всех действительных чисел. Таким образом, для данного предиката М = I_p . Такие предикаты называются тождественно истинными.

В(х): «х² + 1< 0, xÎ R»; область истинности I_p =Æ, т.к. не существует действительных чисел, для которых выполняется неравенство. Такие предикаты называются тождественно ложными.

Определение. Предикат Р(х), определенный на мно­жестве М, называется тождественно истинным (тож­дественно ложным), если 1р = М (1р = Æ).

Предикат sin²x+cos²x=1 - тождественно истинный, предикат - тождественно ложный.

Естественным обобщением понятия одноместного предиката является понятие многоместного предика­та, с помощью которого выражаются отношения меж­ду предметами.

Примером отношения между двумя предметами является отношение «меньше» («больше»). Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной фор­мой «х < у»(«х > y») , где х, у Î Z , то есть является функцией двух переменных Р(х, у), определенной на множестве Z х Z с множеством значений {1,0}.

Определение. Двухместным предикатом Р(х,у) на­зывается функция двух переменных х и у (субъекты предиката), определенная на множестве М =М₁ ´ М₂ (хÎ М₁ , уÎ М₂ ) и принимающая значения из множества {1,0}.

Найдем значения предиката «х < у» , где х, у Î Z для пар (2,1), (4,4), (3,7):

Вместо х и у подставим указанные значения: Р(2,1) = 0, т.к. 2>1; Р(4,4)=0, т.к. 4 = 4; Р(3,7)=1, т.к. 3<7. областью истинности этого предиката является множество всех пар целых чисел, удовлетворяющих данному неравенству.

Рассмотрим этот же предикат, но с областью определения M = R², тогда область его истинности можно представить графически: это все точки части плоскости (открытая, бесконечная область), лежащей ниже прямой у = х.

В числе примеров двухместных предикатов можно назвать предикаты: Q(х, у): « х = у » -предикат равенства, определенный на множестве М = R х R , область истинности которого - все точки прямой у = х :

Предикат F(x,y) : «х//у»- прямая х параллельна прямой у, определенный на множе­стве прямых, лежащих на данной плоскости.

Аналогично определяется n -местный предикат.

Определение : n - местным предикатом называется функция Q(x₁, x₂,…,x_n), определенная на множестве М = М₁´ М₂´…´М_n и принимающая на этом множестве значение из множества {1, 0}.

Предикат Р(х) является следствием предиката Q(x) (Q(x)®P(x)), если I_QÌI_P.

Предикаты P(x) и Q(x) равносильны (Q(x)«P(x)), если I_Q=I_P .

Для n -местных предикатов вводятся аналогичные понятия .

Примеры:

1. На множестве М= {3,4,5,6,7,8} заданы предикаты P(x) : «х - простое число», Q(x): «х - нечетное число». Составить таблицы истинности. Равносильны ли предикаты на множестве а) М; б) L = {2,3,4,5,6,7,8}; в) К = {3,4,5,6,7,8,9}?

На множестве М I_P = I_Q, следовательно на этом множестве предикаты равносильны. На множествах L и К условие равносильности не соблюдается.

Тема 3. Предикаты

Лекция №2-3. Логические операции над предикатами.

1. Операция отрицания.

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

2. Операция конъюнкции.

Конъюнкцией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат Р(х)Q(x), заданный на том же множестве и обращающийся в истинное высказывание при тех и только тех значениях хХ, при которых оба предиката принимают значения истины.

Если обозначить ТР - множество истинности предиката Р(х), ТQ - множество истинности предиката Q(х), а множество истинности их конъюнкции TPÙQ, то, по всей видимости, TPÙQ = TP Ç TQ.

Докажем это равенство.

1. Пусть а - произвольный элемент множества Х и известно, что а Î TPÙQ . По определению множества истинности это означает, что предикат Р(х)Q(x) обращается в истинное высказывание при х = а, т.е. высказывание Р(а)Q(а) истинно. Так как данное высказывание конъюнкция, то по определению конъюнкции получаем, что каждое из высказываний Р(а) и Q(а) также истинно. Это означает, что а ТР и а ТQ . Таким образом, мы показали, что TPÙQ Ì ТР Ç ТQ .

2. Докажем обратное утверждение. Пусть а - произвольный элемент множества Х и известно, что а Î TP Ç TQ . По определению пересечения множеств это означает, что а ТР и а ТQ , откуда получаем, что Р(а) и Q(а) - истинные высказывания, поэтому конъюнкция высказываний Р(а)Q(а) также будет истинна. А это означает, что элемент а принадлежит множеству истинности предиката Р(х)Q(x), т.е. а Î TPÙQ .

Из 1 и 2 в силу определения равных множеств вытекает справедливость равенства TPÙQ = ТР Ç ТQ , что и требовалось доказать.

Наглядно это можно изобразить следующим образом.

3. Операция дизъюнкции.

Дизъюнкцией предикатов Р(х) и Q(x) называется предикат Р(х)Q(x), определенный на том же множестве Х и обращающийся в истинное высказывание при тех и только тех значениях хХ, при которых принимает значение истины хотя бы один из предикатовР(х) или Q(x).

Аналогично доказывается, что TPÚQ = TP È TQ.

4. Операция импликации.

Импликацией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат Р(х) Q(x), определенный на том же множестве Х и обращающийся в ложное высказывание при тех и только тех значениях хХ, при которых Р(х) принимает значение истины, а Q(x) - значение лжи.

5 .Операция эквиваленции.

Эквиваленцией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат Р(х) Q(x), определенный на том же множестве Х и принимающий значение истины при тех и только тех значениях хХ, при которых значения каждого из предикатов либо истинны либо ложны. Множество истинности в таком случае выглядит так:

Пример. На множестве М={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} заданы предикаты: А(х) - «число х не делится на 5», В(х) - «х - число четное», С(х) - «х - число простое», D(x) - «число х кратно 3». Найти множество истинности следующих предикатов:

a) А(х)В(х); b) A(x); c) C(x)A(x); d) B(x)D(x) и изобразить их при помощи диаграмм Эйлера-Венна.

Решение: a) Найдем множество истинности предикатов.

А(х): T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19};

В(х): Т = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}.

Множество истинности конъюнкции А(х)В(х) есть пересечение множеств истинности T и Т.

Т = {2, 4, 6, 8, 12, 14, 16, 18}

b) Множествa истинности А(х): T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19}; : T ={1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20}.

Тогда множество истинности A(x) будет следующим:

Т={1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19}.

с) Множествa истинности С(х): Т ={1, 2, 3, 5, 7, 11, 13, 17, 19}; А(х): T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19}.

Множество истинности импликации есть объединение множества истинности второго предиката с множеством истинности отрицания первого.

Значит множество истинности импликации C(x)A(x) будет следующим: Т = {1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,

d) Множества истинности В(х): Т1= {2, 4, 6, 8, 10, 12, 14, 16, 18, 20} и D(x): T = {3, 6, 9, 12, 15, 18}. Тогда множество истинности дизъюнкции B(x)D(x) есть объединение множеств истинности Т1 и T2 и будет следующим: Т = {2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}.

Тема 3. Предикаты

Лекция №4. Кванторные операции.

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

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

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

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

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

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

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

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

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

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

yxP(x,y), yxP(x,y), yxP(x,y), ухР(х,у).

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

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

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

3. yxP(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).

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

Если хотя бы для одного элемента a_kM P(a_k) окажется ложным, то ложными будут высказывание хР(х) и конъюнкция P(a₁) P(a₂)… P(a_n). Значит, справедлива равносильность:

хР(х) P(a₁) P(a₂)… P(a_n).

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

хР(х) P(a₁)V P(a₂)V…VP(a_n).

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

Примеры:

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

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

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

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

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

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

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

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

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

хР(х, у) - не является ни тождественно истинным, ни тождественно ложным: при у =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) B(y, b) B(y, c). Тогда справедлива равносильность:

xA(x, y)zB(y, z)( A(a, y) vA(b, y) vA(c, y)) B(y, a) B(y, b) B(y, c).

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

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

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

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

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

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

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

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

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

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

2. Если F( ^.,^.,...,^.) - n- местная предикатная переменная или постоянный предикат, а х₁, х₂, …, х_n - предметные переменные или предметные постоянные (не обяза­тельно все различные), то F(х₁, х₂, …, х_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) значений предикатных переменных.

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

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

Возьмем за конкретное значение предиката Р(х,у) фиксированный предикат Р°(х,у): «х<у», а свободной переменной х придадим значение х⁰ = 5 М . Тогда при значениях у, меньших х° = 5 предикат Р⁰(х⁰,y) при­нимает значение ложь, а импликация Р(х, у) Р(у, z) при всех z М принимают значение истина, то есть высказывание yz(P⁰(x,y)P⁰(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)vxB(x).

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

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

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

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

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

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

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

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

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

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

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

тогда хА(х)=0, значит, I_A = , I_B - любое подмножество области определения М.

Тема 3. Предикаты

Практическое занятие №1. Логические операции над предикатами.

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. Какие равносильности используются при построении отрицаний формул?

10. Закончите равносильности:

    1. х(А(х)В(х))…;

    2. х(А(х)vB(x))…;

    3. Cvx(B(x))…;

    4. Cx (B(x))…;

    5. Cx(B(x))…;

Тема 3. Предикаты

Практическое занятие №2. Запись математических предложений в виде формул логики предикатов.

1. Запись математических предложений в виде формул логики предикатов.

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

1) Определение предела числовой последовательности.

Здесь использован трехместный предикат Q( ,n,n_o):

2). Определение предела функции в точке.

Здесь использован трехместный предикат Р( , ,х):

3). Определение непрерывности функции в точке.

Функция f(x), определенная на множестве Е, непрерывна в точке х₀ Е , если

Здесь также использован трехместный предикат Р( , ,х).

4). Определение возрастающей функции.

Функция f(x), определенная на множестве Е, возрастает на этом множестве, если

Здесь использован двухместный предикат B(x₁ , x₂):

5). Определение ограниченной функции.

Функция f(х), определенная на множестве Е, ограничена на этом множестве, если

Здесь использован двухместный предикат L(x,M):(|f(x)|M).

Как известно, многие теоремы математики допускают формулировку в виде условных предложений. Например, рассмотрим следующую теорему: «Если точка лежит на биссектрисе угла, то она равноудалена от сторон этого угла». Условием этой теоремы является предложение «Точка лежит на биссектрисе угла», а заключением - предложение «Точка равноудалена от сторон угла». Видим, что и условие, и заключение теоремы представляют собой предикаты, заданные на множестве R². Обозначая эти предикаты

соответственно через Р(х) и Q(x), где х R², теорему можем записать в виде формулы:

В связи с этим, говоря о строении теоремы, можно выделить в ней три части: 1) условие теоремы: предикат Р(х), заданный на множестве R²; 2) заключение теоремы: предикат Q(x), заданный на множестве R²; 3) разъяснительная часть: в ней описывается множество объек­тов, о которых идет речь в теореме.

2. Построение противоположных утверждений.

Пусть дано некоторое математическое утверждение А. Ему противоположным будет утверждение .

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

Так, например, определение ограниченной функции дается формулой:

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

Последняя формула дает не негативное, а положительное определение неограниченной функции.

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

Так, утверждение, что даст формула:

Особый интерес представляет построение утверждения, отрицающего справедливость некоторой теоремы: хE(P(x)Q(x)).

Это будет утверждение:

Следовательно, чтобы доказать, что теорема хE(P(x)Q(x)) неверна, достаточно указать такой эле­мент х Е, для которого Р(х) - истина, a Q(x) - ложь, то есть привести контрпример.

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

1. 1. «Если дифференцируемая функция y = f(x) имеет в точке х₀ производную, равную нулю (y'=0), то то точка х₀ - точка экстремума.» достаточно указать один пример, опровергающий утверждение теоремы. Функция y = x³ в точке х=0 имеет производную у'=3х² = 0, но эта точка не является точкой экстремума. Значит, теорема не верна.

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

3. Прямая, обратная и противоположная теоремы.

Рассмотрим четыре теоремы:

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

Так, теоремы (1) и (2) , а также (3) и (4) - взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.

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

Так, теоремы (1) и (3), а также теоремы (2) и (4) являются взаимно противоположными теоремами.

Например, для теоремы «Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником» (1) обратной является теорема «Если четырехугольник является прямоугольником, то его диагонали равны» (2). Для теоремы (1) противоположной является теорема «Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником» (3), а для теоремы (2) противоположной является теорема «Если четырехугольник не является прямоугольником, то его диагонали не равны» (4).

В рассмотренном примере теоремы (1) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными. Контр примером к теореме (1) является равнобокая трапеция.

Ясно, что прямая и обратная теоремы, вообще говоря, не равносильны, то есть одна из них может быть истинной, а другая ложной. Однако легко показать, что теоремы (1) и (4), а также теоремы (2) и (3) всегда равносильны. Действительно,

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

Из этих равносильностей следует, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).

4. Необходимые и достаточные условия.

Рассмотрим теорему

Множество истинности предиката Р(х) Q(x) есть множество CIp U Iq . Но тогда множеством ложности этого предиката будет C(С1р U Iq )= Iр CI_Q. Последнее множество будет пустым лишь в случае, когда Iр Iq .

I_P

Итак, предикат Р(х) Q(x) является истинным для всех х Е в том и только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката Q(x). При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат называют необходимым условием для предиката Р(х), а предикат Р(х) - достаточным условием для Q(x). Так, в теореме «Если х - число натуральное, то оно целое» предикат Q(x):«х - число целое» логически следует из пре­диката Р(х): «х - число натуральное», а предикат «х - число натуральное» является достаточным условием для предиката «х - число целое».

Часто встречается ситуация, при которой истинные взаимно обратные теоремы:

Это возможно при условии, что Ip = Iq , т.к. одновременно выполняются два условия: I_PI_Q и I_QI_P . В таком случае из теоремы (1) следует, что условие Р(х) является достаточным для Q(x), а из теоремы (2) следует, что условие Р(х) является необходимым для Q(x).

Таким образом, если истинны теоремы (1) и (2), то условие Р(х) является и необходимым, и достаточным для Q(x). Аналогично в этом случае условие Q(x) является необходимым и достаточным для Р(х).

Иногда вместо логической связки «необходимо и достаточно» употребляют логическую связку «тогда и только тогда».

Так как здесь истинны высказывания (1) и (2), то истинно высказывание:

Рассмотрим примеры.

1) Теорема «Если число l делится на 12, то оно делится на 3» истинна. Поэтому здесь делимость числа l на 12 является достаточным условием для делимости числа l на 3, а делимость числа l на 3 является необходимым условием для делимости числа l на 12. В то же время обратная теорема «Если число l делится на 3, то оно делится на 12» не верна. Поэтому делимость числа l на 3 не является достаточным условием делимости числа l на 12, а делимость числа l на 12 не является необходимым условием делимости числа l на 3.

2) Теоремы «В описанном четырехугольнике суммы длин противоположных сторон равны между собой» и «Если в четырехугольнике суммы длин противоположных сторон равны между собой, то в этот четыреху­гольник можно вписать окружность» взаимно обратны. Обе они истинны, и, следовательно, здесь можно употребить логическую связку «необходимо и достаточно»:

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

3) Для каждого из условий выясните, является ли оно необходимым и является ли оно достаточным, чтобы выполнялось неравенство х² - 2х - 8 0: а) х=0, б) -1 х 3, в) х -3, г) х> -2, д) -1 х 10, е) -2 х 4.

Неравенство перепишем в виде (х+2)(х-4) 0, его решением являются х[-2, 4].

а) х=0 - достаточное условие для выполнения неравенства, т.к. 0[-2, 4].

б) [-1, 3] [-2, 4]. Значит -1 х 3 - достаточное условие .

в) [-3, +)[-2, 4], следовательно, является необходимым условием.

г) (-2, +)[-2, 4] и [-2, 4](2, +), значит, не является ни необходимым, ни достаточным условием.

д) [-1, 10] [-2, 4] и [-2, 4] [-1, 10], значит, не является ни необходимым, ни достаточным условием.

е) [-2, 4]=[-2, 4] , следовательно, является и необходимым и достаточным условием.

5. Доказательство методом от противного.

Д

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

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

Действительно, предположение о том, что теорема (1) не справедлива, означает истинность формулы

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

Легко видеть, что эта формула равносильна фор­муле (1).

Действительно,

Задачи для самостоятельного решения

1. Доказать несправедливость утверждений:

а) «Если дифференцируемая функция у= f(x) имеет в точке х₀ вторую производную, равную нулю, то точка х₀ - точка перегиба графика функции».

б) «Если числовая последовательность ограничена, то она имеет предел».

в) «Если функция непрерывна в точке х₀, то она имеет производную в этой точке».

2. Для каждого из условий выясните, является ли оно необходимым и является ли оно достаточным, чтобы выполнялось неравенство х² - 3х - 18 0: а) х=1, б) -2 х 5, в) х -3, г) х> -3, д) -1 х 10, е) -3 х 6.

3. Запишите на языке логики предикатов определение: «Функция f(x) называется ограниченной на множестве М, если существует такое неотрицательное число L, что для всех х М, справедливо неравенство |f(x)| M.»

4. В предложениях вместо многоточия поставьте слова «необходимо, но не достаточно», «достаточно, но не необходимо», «не необходимо и недостаточно», «необходимо и достаточно»:

а) Для того, чтобы четырехугольник был прямоугольным…, чтобы длины его диагоналей были равны;

б) Для того, чтобы х2 - 5х + 6 = 0…, чтобы х=3;

в) Для того, чтобы сумма четного числа натуральных чисел была четным числом, чтобы каждое слагаемое было четным;

г) Для того, чтобы окружность можно было вписать в четырехугольник, чтобы сумма длин суммы длин его противоположных сторон были равны;

д) Для того, чтобы множество было счетным, чтобы его элементы можно было записать в виде занумерованной последовательности;

е) Для того, чтобы числовая последовательность имела предел, чтобы она была ограниченной.

5.Сформулируйте:

а) Необходимый, но недостаточный признак параллелограмма;

б) Необходимый и достаточный признак параллелограмма;

в) Достаточное, но не необходимое условие, чтобы уравнение sinx = a имело решение.

г) Необходимое, но не достаточное условие, чтобы уравнение sinx = a имело решение.

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

1. Записать в виде формулы логики предикатов определение: а) непрерывности функции в точке; б) предела числовой последовательности; в) ограниченной функции.

2. Как выполняется построение противоположного утверждения к утверждению, заданному в виде формулы логики предикатов? Постройте противоположные утверждения для утверждений из первого пункта контрольных вопросов.

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

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

5. Каким должно быть отношение между областями истинности предикатов Р(х) и Q(x), чтобы теорема была истинной? Какой в этом случае из предикатов необходимое и какой достаточное условие?

6. Какое отношение должно быть между областями истинности предикатов Р(х) и Q(x), чтобы для теоремы была справедлива и обратная теорема? Какой теоремой можно заменить в этом случае прямую и обратную?

Докажите равносильность формул и .

Тема 3. Предикаты

Практическое занятие №3. Построение противоположных утверждений.

Запись математических предложений и определений в виде формул логики предикатов.

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

Пример 1.Определение предела "" функции ƒ(х), определенной в области E, в точке x₀: . Используя трехмесиный предикат , запишем: ,

где .

Пример 2.

Определение непрерывности функции в точке.

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

Пример 3.

Определение возрастающей функции.

Функция , определенная на множестве E возрастает на этом множестве, если .

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

2. Построение противоположный утверждений.

Пусть дано некоторое математическое утверждение А. Ему будет противоположным будет утверждение .

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

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

Последняя формула дает не негативное, а положительное определение неограниченной функции.

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

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

3 Прямая, обратная и противоположная теоремы.

Рассмотрим четыре теоремы:

, (1)

, (2)

, (3)

. (4)

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

Так, теоремы (1)и (2), а также (3) и (4)- взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.

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

Так, теоремы (1) и (3), а также (2) и (4) являются взаимно противоположными теоремами.

Например, для теоремы "Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником " (1) обратной является теорема "Если четырехугольник является прямоугольником, то его диагонали равны" (2). Для теоремы (1) противоположной является теорема "Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником " (3), а для теоремы (2) противоположной является теорема "Если четырехугольник не является прямоугольником, то его диагонали не равны " (4).

В рассмотренном примере теоремы (1) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными. Контрпримером к теореме (1) является равнобочная трапеция.

Ясно, что прямая и обратная теоремы , вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая - ложной. Однако легко показать, что теоремы (1) и (4), а также (2) и (3) всегда равносильны.

Действительно: .

Из этих равносильностей следует, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).

4 Необходимые и достаточные условия.

Рассмотрим теорему

(1)

Как отмечалось, множество истинности предиката есть множество . Но тогда множеством ложности этого предиката будет . Последнее множество будет пустым лишь в случае, когда (см. рисунок).

Итак, предикат является истинным для всех том и в только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката Q(x). При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат Q(x) называют необходимым условием для предиката Р(х), а предикат Р(х) - достаточным условием для Q(x).

Рис. 28

Так, в теореме "Если х - число натуральное, то оно целое " предикат Q(x): " х - число целое " логически следует из предиката Р(х): "х - число натуральное" , а предикат "х- число натуральное" является достаточным условием для предиката " х - целое число".

Часто встречается ситуация, при которой истинны взаимно обратные теоремы (1)

.(2)

Это, очевидно, возможно при условии, что .

В таком случае из теоремы (1)следует, что условия Р(х)являются достаточными для Q(x), а из теоремы (2) следует, что условие Р(х)является необходимым для Q(x).

Таким образом, если истинны теоремы (1) и (2), то условие Р(х) является и необходимым, и достаточным для Q(x). Аналогично в этом случае условие Q(х)является необходимым и достаточным для Р(x).

Иногда вместо логической связки "необходимо и достаточно " употребляют логическую связку "тогда и только тогда".

Так как здесь истинны высказывания (1) и (2), то истинно высказывание

.

5. Доказательство теорем методом от противного.

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

(1)

не верна, т. е. , существует такой объект х, что условие Р(х) истинно, а заключение Q(x) - ложно. Если из этих предложений путем логических рассуждений приходят к противоречивому утверждению, то делают вывод о том, что исходное предположение неверно, и верна теорема (1).

Покажем, что такой подход дает доказательство истинности теоремы (1).

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