42414

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

Книга

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

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

Русский

2013-10-29

180.5 KB

24 чел.

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

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

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

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

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

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

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


 

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

29865. Порядок формирования и финансирования венчурных,инновационных и инвестиционных фондов 46 KB
  Фактически венчурное финансирование может быть охарактеризовано как источник долгосрочных инвестиций предоставляемых обычно на 5 7 лет предприятиям находящимся на ранних этапах своего становления а также действующим предприятиям для их расширения и модернизации. Отличие венчурного финансирования от других видов финансирования Источники финансирования Банки Стратегические партнеры Венчурное финансирование Инвестиции в акционерный капитал Кредиты Долгосрочныеинвестиции Рисковый бизнес Участие инвестора в управлении...
29866. Финансовый механизм предприятия 15.5 KB
  Рассмотрим более подробно один из методов финансового механизма финансовый анализ совершенствование которого позволит снизить расходную часть бюджета предприятия и повысить доходную. Финансовое состояние предприятия характеризуется совокупностью показателей отражающих процесс формирования и использования его финансовых средств. В рыночной экономике финансовое состояние предприятия по сути дела отражает конечные результаты его деятельности.
29867. Рынок ценных бумаг РФ: структура и основныек тенденции развития 28.63 KB
  Совокупность экономических отношений между его участниками по поводу выпуска и обращения ценных бумаг. Ценные бумаги в основе которых лежат деньги как капитал и которые опосредуют отношения связанные с движением денежного капитала образуют фондовый рынок как часть рынка ценных бумаг. Ценные бумаги опосредующие товарные отношения формируют рынок товарных ценных бумаг являющийся второй составной частью рынка ценных бумаг.
29868. Бюджетная система РФ 19.67 KB
  10 бюджетная система Российской Федерации состоит из трех уровней: Федерального бюджета и бюджетов государственных внебюджетных фондов; Бюджетов субъектов Российской Федерации региональных бюджетов и бюджетов территориальных государственных внебюджетных фондов; Местных бюджетов. Бюджетная система Российской Федерации включает: федеральный бюджет 21 республиканский бюджет республик в составе РФ 55 краевых и областных бюджетов и бюджеты Москвы и СанктПетербурга один областной бюджет автономной области 10 окружных бюджетов автономных...
29869. Бюджетный процесс и концепция его реформации 16.35 KB
  6 Бюджетного Кодекса РФ бюджетный процесс регламентируемая законодательством Российской Федерации деятельность органов государственной власти органов местного самоуправления и иных участников бюджетного процесса по составлению и рассмотрению проектов бюджетов утверждению и исполнению бюджетов контролю за их исполнением осуществлению бюджетного учета составлению внешней проверке рассмотрению и утверждению бюджетной отчетности. Все стадии жестко регламентированы процессуальными нормами бюджетного права призванными обеспечить четкое...
29870. Инвестиции – вложения средств в промышленность, сельское хозяйство и другие отрасли экономики внутри страны и за границей в целях получения прибыли 15.64 KB
  Прямые инвестиции осуществляются с целью непосредственного управления объектом инвестиций через контрольный пакет акций или в иной форме контрольного участия.Портфельные инвестиции осуществляются в форме покупки ценных бумаг принадлежащих различным эмитентам и не обеспечивающих контрольное участие и прямое управление объектом инвестиций. Цель подобных инвестиций в отличие от прямых получение прибылей от роста курсовой стоимости портфеля от созданных ими стабильных денежных потоков дивидендов процентов при диверсификации...
29871. РИСК-МЕНЕДЖМЕНТ 16.75 KB
  на свой страх и риск. В связи с этим появляются различные методы управления риском и повышается роль страхования как основного метода снижения степени риска. Риск это финансовая категория. Снижение величины риска осуществляется через финансовые методы: диверсификацию лимитирование самострахование страхование и др.
29872. Структура капитала 16.72 KB
  Структура капитала соотношение собственных и заемных финансовых средств используемых в хозяйственной деятельности. Она влияет на коэффициент рентабельности активов и собственного капитала определяет систему коэффициентов финансовой устойчивости и платежеспособности и формирует соотношение доходности и риска.Структура капитала представляет собой соотношение собственных и заемных средств долгосрочного характера. Управление структурой капитала заключается в создании смешанной структуры капитала представляющей такое оптимальное сочетание...
29873. Долгосрочная финансовая политика РФ 35 KB
  Очевидно что от должной организации финансовой политики коренным образом зависит благополучие предприятия. Безусловно российские предприятия имеют большой опыт в области разработки финансовой политики прогнозной и плановой работы оценок экономической эффективности проектов который не следует игнорировать. Финансовая политика предприятия совокупность мероприятий по целенаправленному формированию организации и использованию финансов для достижения целей предприятия. Финансовая политика наиболее важный составной элемент общей политики...