42414

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

Книга

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

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

Русский

2013-10-29

180.5 KB

20 чел.

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

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

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

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

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

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

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


 

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

50313. Дослідження цифрового комутаційного поля (SN) системи EWSD 402.5 KB
  Мета роботи: Вивчити принципи побудови з’єднувальних шляхів в ЦКП системи EWSD. У процесі самопідготовки вивчити призначення апаратних засобів ЦСК EWSD. Ознайомитися з варіантами побудови КП ЦСК EWSD.
50315. Дослідження підсистеми комутації та керування системи Alcatel 1000 E-10 759.5 KB
  Мета роботи: Вивчити принципи побудови функції підсистеми комутації та керування ОСВ283 lctel 1000 E10 призначення мультипроцесорних станцій. У процесі самопідготовки вивчити призначення апаратних засобів ОСВ283. Ознайомитися з функціональною архітектурою ОСВ283.3 Розглянути програмні засоби ОСВ283 lctel 1000 E10.
50317. Учбова установка АТСЕ «КАРПАТИ» 498.5 KB
  Призначення основних блоків структурної схеми АТСЕ КАРПАТИ.Привести структурну схему АТСЕ КАРПАТИ ємністю менше 720 абонентів з призначенням її основних блоків. Структурна схема учбової установки АТСЕ КАРПАТИ†ємністю менше 720 АЛ БАЛ – блок абонентських ліній; САК – блок спарених абонентських комплектів; БФСЛ1 БФЗЛ1 – блок фізичних з’єднувальних ліній...
50319. Построение простейших экспертных систем 315.5 KB
  Задание к работе: составить программу, содержащую сведения о лучшей десятке фильмов. Данные для построения вывода: название, режиссер, сценарист, год выпуска, киностудия, страна-производитель. В программе должна быть реализована возможность получения следующей информации: по порядковому номеру – фамилия режиссера, название фильма, страны-производителя; все фильмы одного годы выпуска или одной киностудии; все фильмы одной страны.
50320. ЗНАЙОМСТВО ІЗ ПАКЕТОМ СИМУЛЯЦІЇ ЕЛЕКТРОННИХ СХЕМ «PROTEUS» 488 KB
  Proteus - це пакет програм класу САПР, який поєднує в собі дві основні програми: ISIS - засіб розробки і налагодження в режимі реального часу електронних схем та контролерів і ARES - засіб розробки друкованих плат.
50321. ІНТЕГРОВАНЕ СЕРЕДОВИЩЕ РОЗРОБКИ ПРОГРАМ AVR STUDIO 1.54 MB
  Початок роботи При програмуванні в середовищі VR Studio необхідно виконати стандартну послідовність дій: створення проекту; написання програми; компіляція; симуляція. Натискаємо завершити Finish на цьому проект створений і ми потрапляємо в головне вікно програми. Загальний вид вікна програми Вікно розділене на 4 частини. Трохи нижче ліворуч розташовується вкладки Диспетчер проекту Project Перегляд вводу виводу I O View Інформація Info праворуч Текст програми.