42414

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

Книга

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

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

Русский

2013-10-29

180.5 KB

22 чел.

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

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

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

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

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

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

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


 

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

39116. ИССЛЕДОВАНИЕ КОРОННОГО РАЗРЯДА. Отрицательный коронный разряд 85 KB
  Кроме того критические потенциалы коронного разряда и искрового пробоя Uп неодинаковы. Возникновение коронного разряда объясняется появлением вблизи коронирующего электрода резкой неоднородности электрического поля значительно превосходящей напряженность электрического поля на других участках воздушного промежутка между электродами. Для возникновения коронного разряда напряженность поля у электрода должна превосходить электрическую прочность воздуха.
39117. ПСИХОФИЗИОЛОГИЧЕСКИЕ ПОДХОДЫ И ТЕОРИИ, ОКАЗАВШИЕ ЗНАЧИТЕЛЬНОЕ ВЛИЯНИЕ НА РАЗВИТИЕ ОТЕЧЕСТВЕННОЙ ПСИХОЛОГИИ 102.5 KB
  Основным фактором детерминирующим развитие и функционирование живых организмов а также отдельных физиологических систем в составе организма выступает не прошлое событие а подготовка к еще не наступившим событиям которая обеспечивается прогнозированием результатов предстоящих действий на основе опережающего отражения и механизмами целеполагания. Любой поведенческий акт живого организма обеспечивается рядом системных механизмов и процессов которые организуются в функциональную систему: механизм афферентного синтеза...
39118. АЛЬТЕРНАТИВНЫЕ ОБЩЕПСИХОЛОГИЧЕСКИЕ ТЕОРИИ И ТЕОРЕТИЧЕСКИЕ ПОДХОДЫ К ОБЪЯСНЕНИЮ ПСИХИЧЕСКИХ ЯВЛЕНИЙ 63.5 KB
  Строгий естественнонаучный подход к анализу и объяснению психических явлений в психологии поведения. В качестве одного из основателей объективной психологии поведения называют российского физиолога И. Вместе с тем это направление имеет множество научных достижений которые составляют золотой фонд мировой психологии: исследована эффективность различных типов подкрепления поощрения и наказания в процессах научения разработано множество тонких методов позволяющих регистрировать различные формы поведения животных установлено...
39119. КУЛЬТУРНО-ИСТОРИЧЕСКИЙ И СИСТЕМНО-ДЕЯТЕЛЬНОСТНЫЙ ПОДХОДЫ К АНАЛИЗУ И ОБЪЯСНЕНИЮ ПСИХИЧЕСКИХ ЯВЛЕНИЙ 172 KB
  Культурное развитие человека представляет собой формирование и развитие в совместной деятельности и общении высших психических функций ВПФ. Источник развития человеческой психики находится во внешней идеальной форме в фиксированных в человеческой культуре средствах и способах деятельности и общения которыми необходимо овладеть. Формирование ВПФ выделяет человека из животного мира и заключается в присвоении культурноисторического опыта человечества что обеспечивает изменение структуры деятельности и психики человека. При этом...
39120. ТЕОРИИ ЭМОЦИОНАЛЬНЫХ ЯВЛЕНИЙ. ТЕОРИИ МОТИВАЦИОННОЙ И ВОЛЕВОЙ РЕГУЛЯЦИИ 155 KB
  Состояние когнитивного диссонанса возникает тогда: когда человек воспринимает самого себя в качестве причины возникшей когнитивной несогласованности; когда действия субъекта основаны на свободном выборе и разрушают Яконцепцию; когда люди чувствуют личную ответственность за свои неверные действия и поступки; когда такие действия и поступки имеют серьезные последствия. Когда свои действия или поступки которые вызывают когнитивный диссонанс человек не может оправдать и объяснить внешними факторами уменьшение диссонанса...
39121. СТРУКТУРНЫЕ, ФУНКЦИОНАЛЬНЫЕ И ГЕНЕТИЧЕСКИЕ ТЕОРИИ МЫШЛЕНИЯ (ИНТЕЛЛЕКТА) ЧЕЛОВЕКА 163.5 KB
  Такие возможности реализуются на основе эмпирического опыта и воздействий социального окружения; эмпирическим опытом который включает: формирование двигательных навыков путем упражнения извлечение информации из опыта взаимодействия с физическим миром логикоматематический опыт организации и координации познавательных действий; воздействием социального окружения. Взаимодействие субъекта и объекта это источник любого знания который складывается из двух типов опыта: координации действий и операций которые строятся...
39122. СТРУКТУРНЫЕ, ФУНКЦИОНАЛЬНЫЕ И ГЕНЕТИЧЕСКИЕ ТЕОРИИ ПАМЯТИ ЧЕЛОВЕКА 104.5 KB
  СТРУКТУРНЫЕ ФУНКЦИОНАЛЬНЫЕ И ГЕНЕТИЧЕСКИЕ ТЕОРИИ ПАМЯТИ ЧЕЛОВЕКА План 1. Теории и модели памяти в когнитивной психологии 1. Модели организации процессов памяти в когнитивной психологии Кратковременная память Ограниченность объема: в среднем 57 единиц информации. На самых глубоких уровнях: а происходит когнитивная семантическая обработка путем установления различных связей с информацией в долговременной памяти; б устанавливается смысл и содержание информации осуществляется ее субъективная оценка.
39123. Структурные, функциональные и генетические теории внимания человека 63.5 KB
  Теории и модели внимания в когнитивной психологии Д. Модель внимания на основе избирательного ослабления сигналов Существует перцептивный фильтр расположенный между входными сенсорными сигналами и вербальным семантическим анализом сообщения. Стадия предвнимания: происходит быстрое извлечение и обработка информации полученной рецепторами позволяющие выделить простые и наиболее заметные признаки объектов; обработка информации производится автоматически быстро параллельно; обработка информации происходит без сознательных усилий и...
39124. ТЕОРИИ СОЗНАНИЯ ЧЕЛОВЕКА 86.5 KB
  ТЕОРИИ СОЗНАНИЯ ЧЕЛОВЕКА План Структурное и функциональное определение и объяснение сознания сохраняет свою актуальность в психологии до настоящего времени. Попытки объяснить сознание человека в истории психологии были связаны: с анализом организации процессов внимания с анализом осознаваемых и неосознаваемых мотивов человека с описанием сознания как сцены на которой представлен феноменологический опыт субъекта ассоциативная психология гештальтпсихология с трактовкой сознания как активного начала организующего в единство...