МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ПРАКТИЧЕСКИХ РАБОТ по учебной дисциплине «Элементы математической логики»


Государственное бюджетное образовательное учреждение
среднего профессионального образования
«АРМАВИРСКИЙ МАШИНОСТРОИТЕЛЬНЫЙ ТЕХНИКУМ»
Краснодарского края
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
ПО ВЫПОЛНЕНИЮ ПРАКТИЧЕСКИХ РАБОТ
по учебной дисциплине
«Элементы математической логики»
для студентов 2 курса очной формы обучения
по специальности «Программирование в компьютерных системах»
Автор: Беляева Татьяна Юрьевна
Содержание
1. Введение………………………………………………………………. 3
2. Порядок проведения практического занятия……………………….. 3
3. Оформление практической работы…………………………………. 3
4. Критерии выставления оценок………………………………………. 3
5. Практическая работа № 1. «Множества. Выполнение теоретико-множественных операций»…………………………………………. 5
6. Практическая работа № 2. «Бинарные отношения и их свойства. Выполнение операций над бинарными отношениями. Подстановки»…………………………………………………………………….. 8
7. Практическая работа № 3. «Логические формулы. Построение их таблиц истинности. Проверка двух формул на равносильность»…………………………………………………………………. 11
8. Практическая работа № 4. «Упрощение формул логики с помощью равносильных преобразований»……………………………… 13
9. Практическая работа № 5. «Булевы функции и их представление в совершенной дизъюнктивной и конъюнктивной нормальных формах»……………………………………………………………….. 15
10. Практическая работа № 6. «Построение контактных и логических схем»…………………………………………………………………. 17
11. Практическая работа № 7. «Предикаты. Выполнение операций над предикатами………………………………………….…………… 19
12. Список рекомендуемой литературы……………………………….. 23

1. Введение
Цель методических указаний - обеспечить четкую организацию проведения практических занятий по дисциплине «Элементы математической логики» и предоставить возможность обучающимся, отсутствовавшим на практическом занятии, самостоятельно выполнить работу.
Отсутствовавшие на практических занятиях обучающиеся при выполнении практических работ самостоятельно имеют право на получение консультаций у преподавателя.
Неудовлетворительная оценка, полученная обучающимся при выполнении практической работы, должна быть исправлена и повторно проверена преподавателем.
Обучающийся, имеющий к концу семестра более 75% практических работ, написанных на неудовлетворительную оценку, не может иметь положительную оценку при зачете по дисциплине.
2. Порядок проведения практического занятия
1. Опрос обучающихся по теме практической работы в различных формах
2. Краткое сообщение преподавателя о целях практического занятия, порядке его проведения и оформления работы
3. Выдача вариантов заданий
4. Выполнение обучающимися практической работы
5. Подведение итогов практического занятия преподавателем
3. Оформление практической работы
1. Задания выполняются в специально отведенной тетради.
2. Указывается тема практической работы и вариант.
3. Условия заданий переписываются полностью, выполняется решение, в конце которого записывается ответ.
4. Все рисунки и схемы выполняются карандашом, с помощью линейки.
5. Задания можно выполнять в произвольном порядке.
4. Критерии выставления оценок
Оценка «5» ставится, если:
• работа выполнена полностью;
• в логических рассуждениях и обоснованиях решения нет пробелов и ошибок;
• в решении нет математических ошибок (возможна одна неточность, описка, не являющаяся следствием незнания или непонимания учебного материала).
Оценка «4» ставится, если:
• работа выполнена полностью, но обоснования шагов решения недостаточны (если умение обосновывать рассуждения не являлось специальным объектом проверки);
• допущена одна ошибка или два-три недочета в выкладках, рисунках, чертежах или графиках (если эти виды работы не являлись специальным объектом проверки).
Оценка «3» ставится, если:
• допущены более одной ошибки или более двух-трех недочетов в выкладках, чертежах или графиках, но учащийся владеет обязательными умениями по проверяемой теме.
Оценка «2» ставится, если:
• допущены существенные ошибки, показавшие, что учащийся не владеет обязательными умениями по данной теме в полной мере.

5. Практическая работа № 1
Тема: «Множества. Выполнение теоретико-множественных операций»
Цель: 1) усвоить понятие множества и способы его задания; 2) приобрести практические навыки по: выполнению операций над множествами, заданными своими элементами, а также с применением тождеств алгебры множеств, иллюстрированию операций на диаграммах Эйлера.
Методические указания
Множество – это совокупность объектов, объединенных по какому-либо признаку.
Множество В называется подмножеством множества А, если всякий элемент множества В является элементом множества А. Обозначается В ⊂ А.
Множество всех подмножеств некоторого множества А называется его булеаном. Обозначается В(А).
Способы задания множеств
1) Перечислением (списком) его элементов
2) Порождающей процедурой
3) Указанием характеристического свойства
4) Графически (с помощью диаграмм Эйлера-Венна)
ПР. Прочитайте запись М = х∈ Z x2+4х<0. Задайте это множество перечислением элементов. Запишите все подмножества множества М.
/ М – множество целых чисел, удовлетворяющих неравенству x2+4х<0.Решим неравенство: x(x+4)<0
+ - +
1653540171450090551017145004533903429000
- 4 0 х
М = -3;-2; -1В(М) = Ø; -3; -2; -1; -3;-2; -2; -1; -3; -1; -3;-2; -1 /Операции над множествами
Объединением множеств А и В называется множество, элементы которого принадлежат хотя бы одному из множеств А и В.
Обозначается А ∪ В.Напр.: {1; 2; 3} ∪ {2; 3; 4} = {1: 2; 3; 4}
869315528320А
00А
71691528067000716915280670001650365575945В
00В
122174022352000
Пересечением множеств А и В называется множество С, элементы которого принадлежат каждому из множеств А и В.
Обозначается А ∩ В.Напр.: {1; 2; 3} ∩ {2; 3; 4} = {2; 3}

Разностью множеств А и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В. Обозначается А \ В.
Напр.: {1; 2; 3} \ {2; 3; 4} = { 1 }
1198245347980001474470469900В
00В
769620517525А
00А
56959524193500112204518478500
АВ называется дополнением множества А до множества В, если А ⊂ В и АВ = В \ А.
1331595494665А
00А
569595357505В
00В
112204535750500742956350000
Дополнение множества А до универсального множества обозначается А.1407795531495А
00А
11982453790950096012037909500569595121920 U
00 U

Дизъюнктивной суммой множеств А и В называется множество, элементы которого принадлежат или множеству А, или множеству В, но не обоим вместе.
Обозначается А ⊕ В.
Напр: { 1; 2; 3 } ⊕ { 2; 3; 4 } = { 1; 4 }

Прямым (декартовым) произведением 2-х множеств А и В называется множество, элементами которого являются все упорядоченные пары (a; b), первые компоненты которых принадлежат множеству А, а вторые – множеству В.
Обозначается А ⨯ В.Напр: А = {1; 2; 3}, B = {2; 4}
А × В = {(1; 2), (1; 4), (2; 2), (2; 4), (3; 2), (3; 4)}
А2 = {(1; 1), (1; 2), (1; 3), (2; 1), (2; 2), (2; 3), (3; 1), (3; 2), (3; 3)}
В3 = {(2; 2; 2), (2; 2; 4), (2; 4; 2), (2; 4; 4), (4; 2; 2), (4; 2; 4), (4; 4; 2), (4; 4; 4)}
Таблица основных тождеств алгебры множеств
А ∪ В = В ∪ АА ∩ В = В ∩ А
А ∪ (В ∪ С) = (А ∪ В) ∪ С А ∩ (В ∩ С) = (А ∩ В) ∩ С
А ∪ (В ∩ С) = (А ∪ В) ∩ (А ∪ С) А ∩ (В ∪ С) = (А ∩ В) ∪ (А ∩ С)
А ∪ Ø = А А ∩ Ø = Ø
А ∪ U = U А ∩ U = А
А ∪ А = А А ∩ А = А
А ∪ (А ∩ В) = А А ∩ (А ∪В) = А
А ∪ Ā = U А ∩ Ā = Ø
Ø = U U = Ø
А∪В= А ∩ВА∩В= А ∪ ВА=А
А \ В = А ∩ В
А ⊕ В = (А ∩ В) ∪ А ∩ВПР. Упростите:
1) (А ∩ В ∩ С) U (Ā ∩ В ∩ С)
/ (А U Ā) ∩ (В ∩ С) = U ∩ (В ∩ С) = В ∩ С/
2) (А ∩ В ∩ С) ∪ (Ā ∩ С) ∪ (В ∩ С)
/ ((А ∩ В) ∩ С) ∪ ((Ā ∪ В) ∩ С) = ((А ∩ В) ∪ (Ā ∪ В)) ∩ С = ((А ∩ В) ∪ А∩В ) ∩ С = U ∩ С = С/
3) Х\У∩Х∪У
/ Х∩У∩Х∩У = Х∩У ∪ Х∩У = (Х ∩ У) ∪ (Х ∩ У) = Х ∩(У ∪У) = Х ∩U = Х/
ПР. Докажите с помощью тождественных преобразований: А \ (А \ В) = А ∩ В
/ Л.ч. А \ (А ∩ В) = А ∩ А ∩ В = А ∩ (Ā ∪В) = (А ∩ Ā) ∪А ∩В= Ø ∪ А ∩В = А ∩ В, ч.т.д./
Содержание задания
Задание 1. Прочитайте запись М = х∈ N | 0≤х<6. Задайте это множество перечислением элементов. Запишите все подмножества множества М.
Задание 2. Найдите В ∪ К, А ∩ С, В \ М, МК , А ⊕ В, М2 и М × С, если А = 1;3;7;9, В = 1;2;3;4;5, С = {1; 5; 9}, М = {4; 6}, К = {2; 4; 5; 6; 8}.
Задание 3. Осуществите шаг за шагом построение диаграммы Эйлера для множества (А∩ В) ∪ (В \ А).Задание 4. Используя основные тождества алгебры множеств, докажите, что (А \ В)∩В= Ø. Проиллюстрируйте результат с помощью кругов Эйлера.
Задание 5. С помощью тождественных преобразований упростите:
((А∩ В) ∪А ∩ В∪В) ∩ А.
6. Практическая работа № 2
Тема: «Бинарные отношения и их свойства. Выполнение операций над бинарными отношениями. Подстановки»
Цель работы: закрепить: 1) понятия бинарных отношений и подстановок п–ой степени, способов их задания; 2) навыки выполнения над ними операций обращения и композиции.
Методические указания
Подмножество R прямого произведения А на В называется бинарным отношением.
Обозначается R ⊂ А × В
Множество первых координат в упорядоченных парах, составляющих бинарное отношение R, составляет область определения DomR, а множество вторых координат – область значений ImR этого отношения.
Матрица бинарного отношения - это прямоугольная таблица, строки которой соответствуют элементам множества А, а столбцы - элементам множества В. На пересечении i - ого столбца и j - ой строки матрицы ставится «1», если ai R bj, в противном случае ставится «0».

ПР. Пусть даны два множества А = {2; 3}, B = {3; 4; 5; 6}. Тогда А × В = {(2; 3), (2; 4), (2; 5), (2; 6), (3; 3), (3; 4); (3; 5); (3; 6)}
Рассмотрим отношение R - «быть делителем», т.е. запись а R в означает, что а – делитель в. Очевидно, R = 2;4;2;6;3;3;(3;6).Dom R = {2; 3} = A, Im R = {3; 4; 6} ⊂ В
3 4 5 6
2 0 1 0 1
3 1 0 0 1
Матрица отношения R имеет вид:
Операции над бинарными отношениями
Обращение отношения R (R-1): Переход от R к R-1 осуществляется взаимной перестановкой координат каждой упорядоченной пары. При этом область определения становится областью значений и наоборот. Матрица обратного отношения получается транспонированием исходной матрицы, т.е. заменой строк матрицы ее столбцами при сохранении нумерации.
ПР. Пусть R – « а – делитель b» (R1 = 2;4;2;6;3;3;(3;6)).
Тогда R-1 – «b делится на а» (R1-1 = 4;2;6;2;3;3;(6;3)).
2 3
3 0 1
4 1 0
5 0 0
6 1 1
Матрица отношения R1-1 будет иметь вид:
Композиция бинарных отношений R и S (R ○ S)Матрица композиции S ○ R получается как произведение матриц отношений S и R (в порядке их следования), которое выполняется по обычному правилу умножения прямоугольных матриц с последующей заменой отличных от нуля элементов результирующей матрицы единицей.
ПР. Пусть А = 2;3, В = 3;4;5;6, С = 6;7;8 и R = 2;4, 2;6, 3;3, 3;6, S = 3;6, 4;8,6;6.
R: S:
3 4 5 6
2 0 1 0 1
3 1 0 0 1
6 7 8
3 1 0 0
4 0 0 1
5 0 0 0
6 1 0 0
01011001 ·100001010000 = 101200 →
R ○ S:
6 7 8
2 1 0 1
3 1 0 0
Свойства бинарных отношений
Пусть R – бинарное отношение в А, т.е. R ⊂ А2.
1) Отношение R называется рефлексивным, если ∀а ∈А а R а.
2) Отношение R называется антирефлексивным, если ∀а∈А а R а.
3) Отношение R называется симметричным, если ∀ ai;aj ∈А из того, что ai R aj , следует, что aj R ai.
4) Отношение R называется я антисимметричным, если из соотношений ai R aj и aj R ai следует, что ai = aj.
5) Отношение R называется асимметричным, если ни для одной пары ai;aj ∈А не выполняются одновременно соотношения ai R aj и aj R ai.
6) Отношение R называется транзитивным, если из того, что ai R aj и aj R aк, следует, что ai R aк.
7) Отношение R называется антитранзитивным, если оно не обладает свойством 6).
Подстановки. Действия над подстановками
Взаимно-однозначное отображение множества N = 1;2;…;n на себя называется подстановкой n-ой степени.
ПР. Пусть а = 12342431 и в = 12341432, тогда
а-1 = 24311234= 123441322472690166370001024890139700010248901397000а ○ в = 12342431 ○ 12341432 = 12344231.
Содержание задания
Задание 1. Дано: отношение R – «иметь наибольший общий делитель, отличный от каждого из чисел в паре» во множестве К = 3, 5, 15, 18, 36. Опишите матрицей данное отношение R, а также обратное ему отношение R-1. Сформулируйте его. Определите, какими свойствами обладают R и R-1.
Задание 2. Дано: А = 2;3, В = 7;8;9, С = 8;12, R⊂А×В, S⊂В×С,
R = 2;7, 2;9, 3;7, 3;8, S = 7;8, 7;12, 9;8. Получите матрицу композиции отношений R ○ S.Задание 3. Найдите а-1, а ○ в, в ○ а, в2 и а3, если
а = 1234541532 и в = 1234554231.

7. Практическая работа № 3
Тема: «Логические формулы. Построение их таблиц истинности. Проверка двух формул на равносильность»
Цель работы: 1) освоить методику построения таблиц истинности формул логики; 2) приобрести и закрепить навык проверки двух формул на равносильность.
Методические указания
Высказыванием называется такое повествовательное предложение, для которого имеет смысл говорить, истинно оно или ложно, и которое не является одновременно истинным и ложным.
Истина (1) и ложь (0) называются истинностными значениями высказываний.
Операции над высказываниями и их таблицы истинности
А Отрицание высказывания А1 0
0 1
A B Конъюнкция высказываний A BДизъюнкция высказываний A BИмпликация высказываний A BЭквиваленция высказываний A BИсключающая дизъюнкция высказываний A B1 1 1 1 1 1 0
1 0 0 1 0 0 1
0 1 0 1 1 0 1
0 0 0 0 1 1 0
Всякое простое высказывание (логическая переменная или логическая постоянная), а также всякое сложное высказывание, образованное из простых с помощью логических операций, называется логической формулой.
Рангом формулы Ф называется число всех логических операций, с помощью которых эта формула образована.
Обозначается r(Ф).
Правила чтения формул
Если скобки отсутствуют, то логические операции выполняются в следующей очередности: отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция.
Если без скобок записаны друг за другом несколько одинаковых операций, то они выполняются последовательно слева направо.
Операция отрицания записывается без скобок и применяется ко всей формуле, записанной под символом отрицания.
При необходимости изменить естественный порядок действий часть формулы заключается в скобки.
Если для данной формулы необходимо вычислить ее значения при всевозможных наборах значений логических переменных, то составляют таблицу истинности. Такая таблица имеет всегда 2п строк, где п – число входящих в формулу переменных, и n + r(Ф) столбцов.
ПР. Построим таблицу истинности для формулы А \/ (В→А).
А В ВВ→АА\/ В→А1 1 0 1 1
1 0 1 1 1
0 1 0 1 1
0 0 1 0 0
Формула называется выполнимой, если она принимает значение «1» хотя бы при одном наборе значений входящих в нее переменных.
Формула называется тождественно истинной (тавтологией, законом логики), если она принимает значение «1» при любом наборе значений переменных, и тождественно ложной (противоречием), если при любом наборе значений переменных она принимает значение «0».
Две формулы Ф1 и Ф2 называются равносильными, если они принимают одинаковые значения при каждом наборе значений переменных.
ПР. Докажем с помощью таблицы истинности равносильность Х → У ≡ Х \/ У
Х У Х→У ХХ \/ У
1 1 36639510795001 0 36639510795001
1 0 0 0 0
0 1 1 1 1
0 0 1 1 1
Содержание задания
Задание 1. Постройте таблицы истинности формул логики и определите, к какому из видов они относятся:
а) Ф(Х;У) = X ↔ X Y;
б) Ф(А, В) = А →(А→ В );
в) Ф(X1, X2, X3) = (X1→ X2) → (Х1 Х2 Х3).
Задание 2. Докажите с помощью таблицы истинности равносильность
А ↔ В ≡А В A В.

8. Практическая работа № 4
Тема: «Упрощение формул логики с помощью равносильных преобразований»
Цель работы: закрепить навык упрощения формул логики, а также доказательства законов логики с применением основных тождеств алгебры логики.
Методические указания
Основные равносильности алгебры логики
1) Законы идемпотентности:
А  А  АА  А  А
2) Законы коммутативности:
А В  В  А (конъюнкции)
А  В  В  А (дизъюнкции)
3) Законы ассоциативности:
А  (В  С)  (А  В)  С (конъюнкции)
А  (В  С)  (А  В)  С (дизъюнкции)
4) Законы дистрибутивности:
А  (В  С)  (А  В)  (А  С) (конъюнкции относительно дизъюнкции)
А  (В  С)  (А  В)  (А  С) (дизъюнкции относительно конъюнкции)
5) Законы констант:
А  Т  АА  F  FА  Т  TА  F  А
6) Закон противоречия:
А  А  F
7) Закон исключенного третьего:
А  А  Т
8) Закон снятия двойного отрицания:
А  А
9) Законы поглощения:
А  (В  А)  А
А  (В  А)  А
10) Законы де Моргана:
А В  A В
А В  A В
11) Закон отмены импликации:
А → В  А  В
12) Закон отмены эквиваленции:
А ↔ В  (А  В)  (А  В)
Используя вышеприведенные равносильности, можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными. Они используются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул.
ПР. Упростите формулу с помощью равносильных преобразований:
1) X ˅ Y→X ˅ Y ≡ X ˅ Y ˅ X ˅ Y ≡ (X ˅ Y) ˄ (X ˅ Y) ≡ Х ↔ У
2) (X → Y) → ((Y → Z) → (X \/ Y → Z)) ≡ (X ˅ Y) → ((Y ˅ Z) → (X ˅ Y ˅ Z)) ≡ (X ˅ Y) → (Y ˅ Z ˅ (X ˅ Y ˅ Z)) ≡ X ˅ Y ˅ (Y ˅ Z ˅ (X ˅ Y ˅ Z)) ≡ (Х ˄ У) ˅ ((У ˄ Z) ˅ ((X ˄ Y) ˅ Z)) ≡ ((X ˅ X) ˄ Y) ˅ ((Y ˅ Z) ˄ (Z ˅ Z)) ≡ (T ˄ Y) ˅ ((Y ˅ Z) ˄ T) ≡ Y ˅ (Y ˅ Z) ≡ (Y ˅ Y) ˅ Z ≡ T ˅ Z ≡ Т
Содержание задания
Задание 1. Упростите:
а) А В →А;
б) X Х У У;
в) (X Y) (X →Y) (Y →X).
Задание 2. Докажите равносильность:
А→В ≡В → АЗадание 3. Докажите закон «modus ponens» (утверждающий модус):
А (А → В) → В

9. Практическая работа № 5
Тема: «Булевы функции и их представление в совершенной дизъюнктивной и конъюнктивной нормальных формах»
Цель работы: закрепить навыки представления произвольной булевой функции в виде СДНФ и СКНФ по имеющейся таблице истинности и с помощью равносильных преобразований.
Методические указания
Алгоритмом представления произвольной булевой функции в виде СДНФ
Если функция f(x1,…,xn) задана таблицей истинности, то для каждого набора значений переменных, на котором функция принимает значение 1, запишем конъюнкцию переменных либо их отрицаний: в качестве члена конъюнкции возьмем саму xк, если xк в данном наборе равно 1, и отрицание xк, если xк в данном наборе равно 0. Дизъюнкция всех таких конъюнкций и даст нам искомую формулу.
ПР. Рассмотрим таблицу истинности функции 3-х переменных:
x1 x2 x3 f(x1,x2,x3)
1 1 1 1
1 1 0 0
1 0 1 1
1 0 0 0
0 1 1 0
0 1 0 1
0 0 1 1
0 0 0 0
Согласно изложенному алгоритму получим СДНФ:
f(x1,x2,x3) = (x1 x2 x3) (x1 x2 x3) (x1 x2 x3) ( x1 x2 x3)
Алгоритм представления произвольной булевой функции в виде СКНФ
Для получения СКНФ весь алгоритм меняется с точностью до «наоборот».
ПР. Составим для приведенного выше примера СКНФ:
f(x1,x2,x3) = (x1 x2 x3) ( x1 x2 x3) (x1 x2 x3) (x1 x2 x3)
Представление булевых функций в совершенной форме
с помощью равносильных преобразований
ПР. Пусть булева функция задана в ДНФ: f (x,y,z) = (x y z) (x y) ДНФ → СДНФ
f (x,y,z) = (x y z) (x y 1) = (x y z) (x y ( z z)) = (x y z) (x y z) (x y z)
ПР. Преобразовать КНФ в СКНФ для функции f(х1, х2, х3) = (х1 х2) (х1 х2) (х1 х2 х3)
f(х1, х2, х3) = (х1 х2 0) (х1 х2 0) (х1 х2 х3) = (х1 х2 (х3 х3)) (х1 х2 (х3 х3)) (х1 х2 х3) = (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) = (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) (х1 х2 х3)
Содержание задания
Задание 1. По таблице истинности найдите формулу, определяющую функцию f (x1, x2, x3), и придайте ей более простой вид:
x1 x2 x3 f(x1,x2,x3)
1 1 1 0
1 1 0 1
1 0 1 1
1 0 0 1
0 1 1 1
0 1 0 1
0 0 1 0
0 0 0 1
Задание 2. Для булевой функции f (x, y, z) = x z → y x найдите СДНФ и СКНФ путем составления таблицы истинности.
Задание 3. С помощью равносильных преобразований запишите для данных булевых функций их совершенные нормальные формы:
a) f (x; y) = у x→y;
b) f (x1; x2; x3) = (x1 x2) ( x1 x2 х3).
10. Практическая работа № 6
Тема: «Построение контактных и логических схем»
Цель работы: закрепить навыки построения контактных и логических схем, упрощения контактных схем и определения значения булевой функции на выходе схемы.
Методические указания
Контактная схема – это устройство из проводников и контактов.
Контакты называются замыкающими, если они в рабочем состоянии замыкают цепь, и размыкающими, если замыкают цепь в нерабочем состоянии.
Обозначения на схемах
255587514223900192976514223900 Замыкающий контакт: х
254508014731900192976514731900 Размыкающий контакт: хОтрицание: 1524017399000131064017335500 х
Конъюнкция: 1524016764000240601516764000120586516764000 х1 х2
Дизъюнкция: 1415415203200001129665203200004629152032000046291520320000 х1
1415415130175002476513017500
11296651085850046291510858500 х2
Импликация: 1129665199390004629151993900014154151993900046291519939000 х11415415130175002476513017500
46291511366500112966511366500 х2
Эквиваленция: х1 х1
15240149225002948940158750002948940-3175002596515-3175001967865-3175001967865-3175001567815158750001567815-3175001320165-317500624840-317500624840-317500
25965151162050019678651162050013201651162050062484011620500 х2 х22596515175895002272665175895001320165175895006248401758950062484017589500 х1 х2
2476518415000259651519367500
22726651917700013201651917700062484019177000 х1 х2Дискретный преобразователь, который после обработки входных двоичных сигналов выдает на выходе сигнал, являющийся значением одной из логических операций, называется логическим элементом.
Конъюнктор (элемент «И») Дизъюнктор(элемент «ИЛИ») Инвертор:
(элемент «НЕ»)
35242515875&
00&
х
66421012255400-69850507900
-692151396900у351790158751
001
х63055512255400-7302519430900-69850507900
у 3517901587500
59118555880006369055587900-641355587900х
Элемент «И-НЕ» Элемент «ИЛИ-НЕ»
35242518415&
00&
х748030107314007023105461000-69850507900
-69215253900у352425158751
001
х7150101073140066992510731500-69850507900
-69215253900уАлгоритм построения контактных и логических схем
1) Определить число переменных
2) Определить количество логических операций и их порядок
3) Построить для каждой логической операции свою схему (если это возможно)
4) Объединить схемы в порядке выполнения логических операций
ПР. Упростим переключательную схему:
 
(х ˄ у) ˅ (у ˄ х) = х ˄ (у ˅ у) = х ˄ 1 = х
Упрощенная схема:

Содержание задания
Задание 1. Составьте контактную схему для логической формулы:
a) f (x; y; z) = х (y z у х);
б) f (x; y) = у x → у.
Задание 2. Упростите контактную схему:
206692512192000110998010096400109918512192000276796412192000 x
27686001968490080200519621400
3119119-381000801369-381000206692516255900109982016255900 y41846514477900451231014922400384302015366900311975514922400x у
8020056095900270446510096400169481510096400 x yЗадание 3. Постройте логическую схему булевой функции
f(x; y; z) = x (y z).
Задание 4. Составьте логическую функцию по схеме:

Задание 5. Придумайте логическую схему для двух переменных. Составьте по ней логическое выражение.
11. Практическая работа № 7
Тема: «Предикаты. Выполнение операций над предикатами»
Цель работы: закрепить навыки идентифицирования различных предложений, определения вида предиката, нахождения его области определения и области истинности, а также определения логических значений высказываний, содержащих кванторы общности и существования.
Методические указания
Предложения с переменными, дающие высказывания в результате замены переменных их допустимыми значениями, называется предикатами.
Предикат одной переменной называется одноместным (или свойством), двух и более переменных – соответственно, двуместным, трехместным и т.д. (или отношением).
(!!) Высказывание – нульместный предикат
Областью определения предиката Р(х) называется множество допустимых значений переменной х. Обозначается U.
Множество тех значений х ∈ U, при которых данный предикат является истинным высказыванием, называется областью истинности предиката. Обозначается I.Предикат называется тождественно истинным, если он становится истинным высказыванием при любых допустимых значениях переменных.
Предикат называется тождественно ложным, если его множество истинности является пустым.
Предикат, который не является тождественно истинным или тождественно ложным, называется выполнимым.
ПР. Определить вид данных предикатов:
«п – четное число» - выполнимый одноместный предикат
U = N и I = nn=2k, k∈N «sin2x + cos2x = 1» - тождественно истинный одноместный предикат
U = R и I = R
«cos x = 0» - выполнимый одноместный предикат
U = R и I = xx= π2+ πn,n∈Z «x2 + y2 = z2» - выполнимый трёхместный предикат
U = R3 и I = x;y;z x2+ y2= z2;x,y,z∈R«х + у = 2х» - выполнимый двуместный предикат
U =R2 и I = x;yy= x ;x,y∈Rх + 1 = х – тождественно ложный одноместный предикат
U = R и I = ∅(х – у)(х + у) = х2 – у2 – тождественно истинный двуместный предикат
Отрицанием предиката Р(х), определенного на множестве U, называется предикат Р(х), определенный на том же множестве, который становится истинным высказыванием только для тех значений х, при которых предикат Р(х) является ложным высказыванием и наоборот.
(!!) Множество истинности предиката Р(х) является дополнением множества истинности предиката Р(х) до мн-ва U.
Конъюнкцией 2-х предикатов P(x) и Q(x) называется предикат P(x) Q(x), который становится истинным высказыванием лишь при тех значениях х, при которых оба предиката становятся истинными высказываниями.
(!!) Множество истинности предиката P(x) Q(x) – есть пересечение множеств истинности исходных предикатов, т.е. IP ∩ IQ.
Дизъюнкцией 2-х предикатов P(x) и Q(x) называется предикат P(x) Q(x), который становится ложным высказыванием лишь при тех значениях х, при которых оба предиката становятся ложными высказываниями.
(!!) Для дизъюнкции P(x) Q(x) множеством истинности является объединение множеств IP ∪ IQ.
Импликацией 2-х предикатов P(x) и Q(x) называется предикат P(x)→Q(x), который становится ложным высказыванием лишь при тех значениях х, при которых Р(х) является истинным высказыванием, а Q(x) - ложным.
(!!) Область истинности предиката P(x)→Q(x) - есть множество U \ (IP \ IQ).
Эквиваленцией 2-х предикатов P(x) и Q(x) называется предикат P(x)↔Q(x), который становится истинным высказыванием лишь при тех значениях х, при которых Р(х) и Q(x) являются высказываниями с одинаковыми истинностными значениями.
(!!) Множество истинности предиката P(x) ↔ Q(x) можно описать формулой IP ∩ IQ ∪ IP∪IQ.
ПР. На множестве А = 1;2;3;4;…;10 заданы предикаты Р(х) = «х – нечетное число», Q(х) = «х делится на 3» и S(х) = «х – составное число». Найти области истинности предикатов Р, P S, Q S, P → S, S ↔ Q.
/ IP = 1;3;5;7;9, IQ = 3;6;9, IS = 4;6;8;9;10IP = 2;4; 6;8;10IP ˄ S = IP ∩ IS = 9IQ ˅ S = IQ ∪ IS = 3;4;6;8;9;10IP \ IS = 1;3;5;7IP→S = 2;4;6;8;9;10IS ∩ IQ = 6; 9А \ IS ∪ IQ = 1;2;5;7IS↔Q = 1;2;5;6;7;9Переход от одноместного предиката Р(х) к высказыванию ∀х Р(х) называется операцией связывания предметной переменной х квантором общности.
Переход от одноместного предиката Р(х) к высказыванию ∃х Р(х) называется операцией связывания предметной переменной х квантором существования.
ПР. Пусть Р(х) – «п – четное число», тогда
∀х Р(х) – ложное высказывание ∃х Р(х) – истинное высказывание
(!!) Высказывание ∀х Р(х) является истинным тогда и только тогда, когда Р(х) – тождественно истинный предикат. Высказывание ∃х Р(х) является ложным тогда и только тогда, когда Р(х) – тождественно ложный предикат.
ПР. Определите истинность высказываний, найдя области истинности предикатов.
∀х(x2- 3х+2=0) – ложное высказывание
Рх – выполнимый предикат (I = {1; 2})
∃x(x2- 3x+2 >0) - истинное высказывание
Рх - выполнимый предикат (I = (- ∞;1) ∪(2;+∞))
ПР. Пусть Р(х; у) – « х >у».
∀хР(х;у) – «Любое число х больше у» – тождественно ложный предикат от у
∃уР(х;у) – «Существует число у, меньшее х» - тождественно истинный предикат от у
∀х ∀уР(х;у) – «Каждое число х больше любого числа у» – ложное высказывание
∀у ∃хР(х;у) – «Для любого числа у найдется большее его число х» – истинное высказывание
∃х ∀уР(х;у) – «Существует такое число х, которое больше любого числа у» – ложное высказывание
Свойства кванторных операций
1. Если предикат определен на конечном множестве М = a1;a2;…;an, то
а) ∀х Р(х) ≡ Р(а1) Р(а2) … Р(ап);
б) ∃х Рх ≡ Р(а1) Р(а2) … Р(ап).
2. Знак отрицания можно внести под знак квантора, изменив квантор на двойственный, т.е.:
а) ∀хР(х) ≡ ∃хР(х); б) ∃хР(х) ≡ ∀хР(х).
3. Квантор общности обладает распределительным свойством относительно конъюнкции, т.е.: ∀x(Px Q(x)) ≡ ∀х Р(х) ∀х Q(х).4. Квантор существования обладает распределительным свойством относительно дизъюнкции, т.е.: ∃x(Px Q(x)) ≡ ∃х Р(х) ∃х Q(х).5. Одноименные кванторы можно менять местами, т.е.:
а) ∀х ∀уР(х;у) ≡ ∀у ∀хР(х;у); б) ∃х ∃уР(х;у) ≡ ∃у ∃хРх;у.Содержание задания
Задание 1. Идентифицируйте следующие предложения:
«при а = –1 верно равенство а3 + 2 = 1»;
25 = – 5»;
«х2 + у2 >0»;
«3х – 5 = 4х + 1»;
«n – кратно 5».
Задание 2. Установите истинность высказываний, найдя области истинности предикатов:
1) ∀х (x2+ х+1 <0); 2) ∃х х+5=2х-3.Задание 3. На множестве натуральных чисел заданы предикаты А(п) – «п ⋮3», В(п) – «п ⋮5», С(п) – «п ⋮15». Определите истинность высказываний, сформулировав каждое из них:
1) ∀n (С(n) → В(n)); 2) ∃n (А(n) C(n)); 3) ∀n (С(n) → А(n) В(n)).
Задание 4. Пусть предикат Р(х; у) определен на множестве N2 и означает «х >у». Определите истинность высказываний, сформулировав каждое из них:
1)∃х∃уР(х;у); 2) ∀х∀уР(х;у); 3) ∃у∀хР(х;у); 4) ∀у∃хР(х;у).
Задание 5. На множестве А = 1;2;3;4;…;20 заданы предикаты Р(х) = «х – четное число», Q(х) = «х делится на 7» и S(х) = «х – составное число». Найдите области истинности предикатов Р, P S, Q S, P → S, S ↔ Q.
Задание 6. Найдите отрицания следующих формул:
1)∃х(Px Q(x)); 2) ∀x(Pх↔Q(х)); 3) ∃x∀y(Px;y Qx;y).

12. Список рекомендуемой литературы
М.С. Спирина, П.А. Спирин. Дискретная математика /Учебник/ - М.: «Академия», 2007
Игошин В.И. Математическая логика и теория алгоритмов /Учебное пособие/ - М.: «Академия», 2010

Приложенные файлы

  • docx file8.doc
    Размер файла: 227 kB Загрузок: 10