Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к практическим занятиям
по дисциплине «Компьютерная дискретная математика»
для студентов I курса
специальность 050103
направление подготовки 6.050103 - Программная инженерия
факультета кибернетики
Херсон 2011
Методические рекомендации к выполнению практических работ по дисциплине «Компьютерная дискретная математика».
Составители д.т.н., профессор Ходаков В.Е., к.т.н., доцент Козуб Н.А.
количество страниц
Рецензент:________________
Утверждено
на заседании кафедры ИТ
протокол № 1 от 15.01.2011
Заведующий кафедрой ИТ ______________Ходаков В.Е.
Введение
В связи с задачей формирования специалистов широкого профиля и развития у них аналитического и творческого мышления, а также в связи с компьютеризацией образования, производства и других сфер жизни, острой необходимостью становится существенное улучшение всех сторон изучения современной логики в высшей школе.
Действующая ныне программа, стремясь привести курс формальной логики в соответствие с современным состоянием логической науки, вводит в него многие фундаментальные понятия математической логики.
Главной целью данного учебного пособия, предназначенного для студентов младших курсов, является содействие глубокому пониманию и усвоению курса основ компьютерной дискретной математики.
Пособие включает в себя основные понятия, теоретические и практические результаты, методы и алгоритмы решения ряда прикладных задач по всем темам предусмотренного академической программой курса.
Задачи дискретной математики характеризуются следующими особенностями:
- их решение эффективно развивает логическое мышление и помогает активному овладению всеми основными методами математической логики;
- они способствуют приобретению самостоятельных навыков в решении логических задач, что даёт возможность почувствовать в той или иной мере радость открытия;
- они чрезвычайно разнообразны, что развивает умение построения математических моделей ряда прикладных задач.
В пособии предусмотрены индивидуальные задания. Для их решения необходимо знание лекционного материала. Рекомендуется иметь дополнительную литературу, поскольку часть курса вынесена на самостоятельное изучение.
Пособие содержит ряд детально разъясняемых примеров решения задач. Если вы достигнете их полного понимания, то не встретите принципиальных трудностей при решении индивидуальных задач.
Практическое занятие №1
Тема: Высказывания. Таблицы истинности.
Предикаты и кванторы.
Занятие рассчитано на 2 академ. часа.
Цель: познакомимся с логикой высказываний, имеющей дело с истинностью (или ложностью) простых описательных утверждений, что можно рассматривать как короткое введение в логику предикатов.
Теоретический материал
Логика необходима в любой формальной дисциплине и состоит из правил получения обоснованного вывода (заключения). Предметом математической логики является разработка методов доказательства математических утверждений с помощью умозаключений на основе законов человеческого мышления.
Стандартными блоками формальной логики являются высказывания. Высказывание повествовательное утверждение, которое имеет значение истинности, т. е. может быть истинным (обозначается буквой И) или ложным (обозначается Л).
Например: Земля плоская; Маша доктор; 11 — простое число.
Высказывания обозначаются строчными или прописными буквами латинского алфавита: A, B, C, …, X, Y, Z,… a, b, c,… или одной буквой с индексом – A1, A2,… An. Используя логические операции не, или, и, можно построить новые составные высказывания, компонуя простые. Простое высказывание называется атомом, сложное молекулой. Образование новых высказываний из исходных посредством логических союзов называют логическими операциями. Истинностное значение полученных высказываний определяется только истинностным значением составляющих высказываний, а не их смыслом.
Например: (не Р) — это высказывание «земля не плоская»; (Р или Q) — «земля плоская или Маша — доктор»; (Р и Q) — «земля плоская и Маша — доктор».
Обозначим через Р высказывание «логика — забава», а через Q — «сегодня пятница». Требуется выразить каждое из следующих составных высказываний в символьной форме.
1) Логика — не забава, и сегодня пятница.
2) Сегодня не пятница, да и логика — не забава.
3) Либо логика — забава, либо сегодня пятница.
Решение: 1) (не Р) и Q, 2) (не Р) и (не Q), 3) Р или Q.
Алфавит языка логики высказываний:
Алфавитом логики высказываний называется любое непустое множество, где:
Словом в данном алфавите называется произвольная конечная последовательность символов. Слово v называется подсловом слова w, если w = vbu, для некоторых слов v и u.
Основные логические операции (связки). Таблицы истинности.
1. Конъюнкция логическое умножение.
Конъюнкцией высказываний А и В, называется высказывание (“А и В”), которое истинно тогда, когда истинны оба эти высказывания.
2. Дизъюнкция - логическое сложение.
Дизъюнкцией высказываний А и В, называется высказывание (“А или В”), которое истинно тогда, когда истинно хотя бы одно из этих высказываний.
3. Импликация.
Импликацией высказываний А и В, называется высказывание (“если А, то В”), которое ложно тогда, когда А - истинно, а В - ложно.
Эквиваленцией высказываний А и В называется высказывание (“если и только если А, то В”), которое истинно тогда, когда А и В одновременно истинны или одновременно ложны.
5. Отрицание.
Отрицанием высказывания А, называется высказывание (“не верно, что А”), которое истинно, когда А - ложно, и ложно, когда А- истинно.
6. Операция сильная дизъюнкция А В (сумма по модулю 2).
Эта функция отвечает разделительному "или''. Она принимает значение ложь, если А и В одновременно истинны или ложны.
7. Операцией Шеффера (штрих Шеффера) над высказываниями А и В называется высказывание А|B (А↑В) (читается "А и В - несовместимые"), которое ложно тогда и только тогда, когда А и В оба истинны.
8. Символом Лукасевича для высказываний А и В называется высказывание АВ (читается "Ни А, ни В"), которое истинно тогда и только тогда, когда А и В оба ложны.
Чтобы уметь определять значение истинности составных высказываний, нам необходимо разобраться со смыслом логических операций, т. е. какой эффект они оказывают на истинностное значение простых высказываний. Это можно сделать с помощью таблиц истинности. Если в молекулу входят n атомов, то для них возможны 2n различных значений истинности:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
|
конъюнкция |
дизъюнкция |
импликация |
эквиваленция |
отрицание |
сложение по модулю 2 |
штрих Шеффера |
стрелка Пирса |
||
|
A |
B |
|
|
|
|
() |
АВ |
А|B (А↑В) |
АВ |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
Скобки - это разделительные знаки, для определения порядка операций. Для уменьшения количества скобок используют определенные договоренности. Можно опускать скобки, придерживаясь следующего порядка операций: считается, что связка &(конъюнкция) связывает сильнее чем все другие, связка (дизъюнкция) сильнее, чем . То есть приоритет логических операций такой: (&), , , . Все остальные связки можно выразить через приведенные.
Предикаты и кванторы
Логика высказываний применяется к простым декларативным высказываниям, где базисные высказывания — либо истинны, либо ложны. Утверждения, содержащие одну и более переменных, могут быть верными при некоторых значениях переменных и ложными при других.
Предикат это утверждение, содержащее переменные величины, принимающее значение истины или лжи в зависимости от значений переменных.
Например, выражение «х целое число, удовлетворяющее соотношению х = x2» является предикатом, поскольку оно истинно при х = 0 или х = 1 и ложно в любом другом случае.
На предикаты переносятся все операции (логические связки), которые мы проделывали с высказываниями. Истинность составного предиката зависит от значений входящих в него переменных.
Пример:
- высказывание, содержащее переменную.
- предметная область предиката.
Понятие квантора
Существуют логические операторы кванторы, применение которых к предикатам превращает их в ложные или истинные высказывания.
Утверждениями о том, что некоторое свойство имеет место «для всех» рассматриваемых объектов, называют квантором «общности» и обозначают .
Утверждениями о том, что «найдется (существует)» по крайней мере один объект, обладающий данным свойством, называют квантором «существования» и обозначают .
Включая в предикат кванторы, мы превращаем его в высказывание. Поэтому предикат с кванторами может быть истинным или ложным.
Высказывание x P(x) означает, что область истинности предиката P(x) совпадает с областью значений переменной x. («При всех значениях (x) утверждение верно»).
Высказывание x P(x) означает, что область истинности предиката P(x) непуста («Существует (x) при котором утверждение верно»).
Примеры:
1) , k – связанная переменная, n – свободная переменная
2) , t – свободная, x – связанная.
3) , a,b,y – свободные переменные, x – связанная.
Методические указания
В основе компьютерной образованности лежит логическая грамотность. Фундаментом логическая грамотность есть умение производить равносильные преобразования формул, а для этого необходимо твёрдо усвоить язык логики высказываний.
Любой язык программирования обязательно содержит логические связки-операторы, т.е. содержит в себе логику высказываний. Компьютеры любого назначения и сложности содержат логические блоки: дизъюнктивный, конъюнктивный и др., конструирование, синтез, функционирование которых основаны на законах логики высказываний.
Пример 1: Найти высказывание, состоящее из трёх атомов, таблица истинности которого:
|
№ строки |
A |
B |
C |
f(A,B,C) |
Основные конъюнкции |
|
1 |
1 |
1 |
1 |
1 |
C |
|
2 |
1 |
1 |
0 |
1 |
С |
|
3 |
1 |
0 |
1 |
0 |
C |
|
4 |
1 |
0 |
0 |
0 |
C |
|
5 |
0 |
1 |
1 |
0 |
C |
|
6 |
0 |
1 |
0 |
0 |
C |
|
7 |
0 |
0 |
1 |
0 |
C |
|
8 |
0 |
0 |
0 |
1 |
C |
Решение. Чтобы найти высказывание с заданной таблицей истинности, нужно взять дизъюнкцию основных конъюнкций из тех строк, которым в заданной таблице истинности соответствует значение 1. В данном примере искомое высказывание будет:
(С)( С)( C) строки 1, 2, 8.
Этот метод решения может быть перенесён на случай n переменных.
Пример 2: Пусть Р(х) — предикат: «х — вещественное число и
х2+1 = 0». Выразите словами высказывание: х : Р(х) и определите его истинностное значение.
Решение. Данное высказывание можно прочитать так: существует
вещественное число х, удовлетворяющее уравнению х2+1=0. Поскольку квадрат любого вещественного числа неотрицателен, т. е. х2 0, мы получаем, что х2 + 1 1. Следовательно, утверждение х : Р(х) ложно.
Отрицание высказывания из этого примера записывается в виде:
не х : Р(х). Это, естественно, истинное высказывание, которое означает, что не существует вещественного числа х, удовлетворяющего условию х2 + 1 = 0. Иными словами, каково бы ни было вещественное х,
х2 + 1 0. В символьной форме это можно записать как х не Р(х).
Для общего предиката Р(х) есть следующие логические эквивалентности:
не х : Р(х) х не Р(х);
не х Р(х) х : Р(х).
Некоторые трудности возникают, когда в высказывании участвует более одного квантора.
Пример 3: Предположим, что х и у — вещественные числа, а Р(х,у) обозначает предикат х + у = 0. Выразите каждое из высказываний словами и определите их истинность.
1)) ху: Р(х,у);
2) у: х Р(х,у).
Решение.
1) Высказывание xy: Р(х, у) говорит о том, что для любого вещественного числа х найдется такое вещественное число у, что х+у=0. Оно, очевидно, верно, поскольку какое бы число х мы ни взяли, число у = х обращает равенство х + у = 0 в верное тождество.
2) Высказывание у : х Р(х, у) читается следующим образом: существует такое вещественное число у, что для любого вещественного числа х выполнено равенство х + у = 0. Это, конечно, не так: не существует вещественного числа у, обладающего указанным свойством. Следовательно, высказывание ложно.
8 СС 18) СС 28) С
9) С 19) С 29) С
10) СС 20) С; 30) С.
1) С 11)С 21) С
2) С 12)С 22) СС
3) С 13)С 23) С
4) С 14)С 24) С|С
5) С15)С 25) С
6) СС 16)С 26) СС
7) СС 17)СС 27) С
8) С 18)С 28) |С
9) С 19)С 29) С
10) С 20)С; 30) С.
|
№ варианта |
||||||||||||||||||||||||||||||||
|
А |
В |
С |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
4. Из следующих предикатов с помощью кванторов постройте всевозможные высказывания и определите, какие из них истинны, а какие ложны (хR):
1) х2 + 2х+1=(х+1)2;
2) (х - 3) (х + 3) < х2;
3)
4) (x2+l=0)((x=l)v(x=2));
5) (x<0)v(x = 0)v(x>0);
6) |х-y|||х|-|y||;
7) sin х = sin у;
8) х2 = у2 х = у;
9) (х + у)2 = х2 + 2ху + у2;
10) |ху|3;
11) х2 = 25;
12) х2 + у2 = 16.
5. Найдите множества истинности следующих предикатов, заданных над указанными множествами:
1) «х кратно 3», М= {1, 2, 3, 4, 5, 6, 7, 8, 9};
2) «х кратно 3», М = (3, 6, 9, 12};
3) «х кратно 3», М= {2, 4, 8};
4) «х2 + 4 > 0», М= R;
5) «sin x > 1», М= R;
6) «х2 + х6 = 0», М= R;
7) «х21 + х22 = 0», M1=M2=R;
8) «x1 < х2», М1 = {1, 2, 3, 4, 5}, М2 = {3, 5, 7};
9) «х1, делит х2», М1 = M2 = {2, 3, 4, 6};
10) «| х1| + х2 > 12», М1 = {-2, 4, 8}, M2 = {0, 7, 9, 11};
11) «х1 + х2 < О», М1 = {-3, -2, -1, 0, 1, 2, 3}, M2 = {-3, 1, 2};
12) «cos x > 1», М= R.