42414

Компьютерная дискретная математика

Книга

Информатика, кибернетика и программирование

Высказывание  повествовательное утверждение которое имеет значение истинности т. Простое высказывание называется атомом сложное молекулой. Например: не Р это высказывание земля не плоская; Р или Q земля плоская или Маша доктор; Р и Q земля плоская и Маша доктор. Обозначим через Р высказывание логика забава а через Q сегодня пятница.

Русский

2013-10-29

180.5 KB

21 чел.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ХЕРСОНСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к практическим занятиям

по дисциплине «Компьютерная дискретная математика»

для студентов 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.

Алфавит языка логики высказываний:

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

  1.  A,B,C,D,… символы для обозначения высказываний;
  2.  1, 0 символы, обозначающие логические константы «истина» и «ложь»;
  3.   - символы логических операций;
  4.  (,) - скобки.

Словом в данном алфавите называется произвольная конечная последовательность символов. Слово v называется подсловом слова w, если w = vbu, для некоторых слов v и u.

Основные логические операции (связки). Таблицы истинности.

1. Конъюнкция  логическое умножение.

Конъюнкцией высказываний А и В, называется высказывание  (“А и В”), которое истинно тогда, когда истинны оба эти высказывания.

2. Дизъюнкция - логическое сложение.

Дизъюнкцией высказываний А и В, называется высказывание  (“А или В”), которое истинно тогда, когда истинно хотя бы одно из этих высказываний.

3. Импликация.

Импликацией высказываний А и В, называется высказывание  (“если А, то В”), которое ложно тогда, когда А - истинно, а В - ложно.

  1.  Эквиваленция (двойная импликация).

Эквиваленцией высказываний А и В называется высказывание  (“если и только если А, то В”), которое истинно тогда, когда А и В одновременно истинны или одновременно ложны.

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. Это, конечно, не так: не существует вещественного числа у, обладающего указанным свойством. Следовательно, высказывание ложно.

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

  1.  Дайте определение высказыванию? Как образуются составные высказывания?
  2.  Составьте таблицы истинности основных логических операций.
  3.  Как определяется алфавит логики высказываний?
  4.  Что такое предикат? Дайте характеристику кванторам.

Индивидуальные задания

  1.  Высказывания А, В, С имеют соответственно значения истинности – 1, 0, 0. Определите значение высказывания, не составляя полных таблиц истинности:

  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.  Постройте полные таблицы истинности следующих формул:

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.  Постройте сложное высказывание, имеющее значение истинности, которое приведено в таблице:

№ варианта

А

В

С

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.


 

А также другие работы, которые могут Вас заинтересовать

43195. СУДОВАЯ ЭНЕРГЕТИЧЕСКАЯ УСТАНОВКА 1.54 MB
  Для судовой энергетической установки характерна сложная структура. В ее состав в основном входит оборудование энергетических систем и трубопроводов. Между которыми существуют сложные физические, параметрические и технико-экономические связи. Для процессов, протекающих в энергетическом оборудовании, характерны значительные изменения параметров – температуры, давления, скорости, сил и моментов, напряжений и деформаций, турбулентности, шума и вибрации, теплопередачи и др.
43196. Проект ПТБ автопредприятия среднего бизнеса в г.Михайловске 365 KB
  Указанные расчеты выполняются с использованием следующих исходных данных (задание из разделов коммерческой эксплуатации):- тип подвижного состава –ВАЗ-2114 среднесписочное количество автомобилей – 200 шт.; реднесуточный пробег автомобилей – 312 км; время в наряде – 24,0 ч; количество дней работы АТП в году – 365; категория условий эксплуатации – III; природно-климатическая зона эксплуатации – умеренно холодный средний пробег автомобиля в долях пробега с начала эксплуатации до капитального ремонта – 0,8; способ хранения: на закрытой площадке.
43197. Решение системы линейных уравнений методом Гаусса 723 KB
  Метод Гаусса— классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которого последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.
43198. Рентабельность производства продукции, пути ее роста 322.5 KB
  Прибыль характеризует конечные экономические показатели не только в сфере производства сельскохозяйственной продукции, но и в сфере обращения, реализации. Она является как бы фокусом, в котором находят отражение все слагаемые эффективности производства. С ростом прибыли неразрывно связан рост рентабельности производства. В свою очередь когда идёт речь о том, что то или иное хозяйство рентабельно, это означает, что в этом хозяйстве не только возмещают затраты, связанные с производством и реализацией продукции, но и получают определённую прибыль, позволяющую вести хозяйство на расширенной основе.
43199. ЭКОНОМИКО-СТАТИСТИЧЕСКИЙ АНАЛИЗ СЕБЕСТОИМОСТИ ЗЕРНОВЫХ В СПК «ТАТАРСКОЕ» ЧЕРЛАКСКОГО РАЙОНА ОМСКОЙ ОБЛАСТИ 674 KB
  Целью работы является углубление теоретических знаний в области статистики и приобретение практических навыков сбора и анализа статистической информации, для проведения экономико-статистического анализа. Для достижения данной цели поставим перед собой последовательный ряд задач, которые более полно и наглядно охарактеризуют производственную деятельность предприятия: сбор статистических данных; обработка собранных данных статистическими методами (представление данных в табличном и графическом виде, расчет относительных величин структуры, показателей интенсивности и средних показателей динамики, выравнивание рядов динамики, корреляционно-регрессионный анализ связи, анализ вариации, факторный анализ с помощью индексов); проведение экономико-статистического анализа результатов обработки данных.
43200. Монтаж одноэтажного промышленного здания 148.5 KB
  Перемещение и монтаж элементов и конструкций над перекрытиями, под которыми находятся люди, допускаются в исключительных случаях по письменному распоряжению I главного инженера генподрядной строительно-монтажной организации при возведении зданий, имеющих более пяти этажей, после разработки мероприятии, обеспечивающих безопасное производство работ. При монтажных работах на высоте должна быть определена и хорошо обозначена видимыми предупредительными знаками опасная зона для нахождения и перемещения людей. В необходимых случаях, кроме этого, подают предупредительные звуковые сигналы.
43201. Проектування приводу до стрічкового конвеєра за схемою та графіком навантаження 1.3 MB
  Курсовий проект з деталей машин – перша самостійна розрахунково-конструкторська робота, під час виконанні якої, студент набуває навичок практичного прикладання своїх теоретичних знань, що були отримані при вивченні фундаментальних та загально технічних дисциплін. На перших етапах роботи над проектом дуже важливо опанувати досвід проектування, що був накопичен в промисловості та відображен в ГОСТах та ДСТУ.
43202. Проектирование смесителя лопастного 3.17 MB
  В гравитационных смесителях в результате подъема и сбрасывания смеси внутри вращающегося барабана рисунок 1. В смесителях непрерывного действия поступление компонентов и выход готовой смеси происходит непрерывно. При переналадке на :смесь новой марки они уступают смесителям циклического действия. а схема смесителя; 1 двигатель; 2 клиноременная передача; 3 редуктор; 4 зубчатая передача; 5 разгрузочный затвор; 6 лопастные валы; 7 лопасть; 8 корыто смесителя.
43203. Синтез и расчёт кулисного механизма 631 KB
  В механизмах привода поперечно строгальных станков используется механизм, обеспечивающий главное возвратно-поступательное движение резания. Основная масса механизмов использующихся в данных станках это кулисные механизмы. Они обеспечивают заданную скорость рабочего хода и повышенную скорость холостого хода. Расчёт и проектирование данных механизмов является важным этапом в образовании инженера. В курсе предмета «Теория машин, механизмов и манипуляторов» получаются навыки расчёта механизмов машин. Комплексным подходом к закреплению полученных знаний является выполнение курсового проекта по данному курсу. В курсовом проекте осуществляется синтез и расчёт кулисного механизма, построение и расчёт зубчатого зацепления и кулачкового механизма. При выполнении работы используются все знания, полученные за курс предмета.