Множества, отображения, логика



страница4/6
Дата26.11.2012
Размер0.77 Mb.
ТипДокументы
1   2   3   4   5   6

4.14. Отрицание предиката с кванторами. Отрицание предиката можно записать в «категоричной» форме:

,

а можно записать в более мягкой форме, заменив:

квантор  — на квантор ,

квантор  — на квантор ,

предикат — на его отрицание:

= .

Пример 3. Высказывание «Неверно, что у всех студентов есть мобильные телефоны» можно записать в равносильной — с точки зрения математической логики — форме: «Существует студент, у которого нет мобильника», или, иначе, «Не у всех студентов есть мобильники».■

Упражнение. Как будет выглядеть отрицание фразы «Каждому — свое»?

4.15. Операции над предикатами — конъюнкция, дизъюнкция, импликация, эквиваленция, отрицание — выполняются по аналогии с операциями над высказываниями.

4.16. Теоремы. Теорему можно записать в виде «Для любого х, если Р(х), то Q(х)» или (х) Р(х)  Q(x). Это означает, что получившееся высказывание является истинным, т.е. теорема верна. Высказывание (х) Р(х) называется посылкой, а высказывание (х) Q(x) — заключением теоремы.

Для данной теоремы, которую мы условно запишем , можно записать

  • обратную ,

  • противоположную

  • обратную противоположной .

С помощью таблицы истинности легко доказать закон контрапозиции:

.

Это означает, что если верна теорема , то верна и теорема, обратная противоположной, .

4.17. Пример 4. Рассмотрим (см. п. 1.
7) два одноместных предиката: А(n) = «Целое число n делится на 4», В(n) = «Целое число n делится на 2». Предикат является тождественно истинным на множестве Z целых чисел, т.е. высказывание (nZ) A(n)  B(n) истинное. Записав четыре теоремы:

(1) ,

(2) ,

(3) ,

(4) ,

видим, что (1) и (4) — верные, а (2) и (3) — неверные теоремы. Таким образом, для данной теоремы обратная теорема не всегда верна.■

4.18. Необходимые и достаточные условия. Рассмотрим импликацию A(n)  B(n) предикатов A(n), B(n) из примера 4.17. Прежде всего, заметим, что множество истинности предиката А(n) есть множество

,

состоящее из целых чисел, кратных 4, множество истинности предиката В(n) есть множество

,

элементами которого являются все четные числа. Легко убедиться, что [A(n)]  [B(n)]. В таких случаях говорят, что A(n) является достаточным условием для B(n), а В(n) является необходимым условием для А(n).

Таким образом, если теорема сформулирована в виде АВ, то ее можно прочесть словесно следующими равносильными способами:

  • если А, то В

  • для того чтобы В, достаточно А

  • для того чтобы А, необходимо В

  • из А с необходимостью следует В.

Если предикат А является одновременно необходимым и достаточным условием для В, то верна теорема АВ и обратная ей теорема ВА, т.е. теорема (АВ)  (ВА), которая равносильна (см. п. 4.8) теореме АВ; последняя читается одним из следующих способов:

  • для того чтобы А, необходимо и достаточно В

  • А, если и только если В

  • А в том и только в том случае, когда В.

4.19. Правила вывода. Доказательства теорем выполняются по правилам, по которым из истинных посылок получают, выводят истинные заключения и которые принимаются в начале теории.

Примем два (исходных) правила вывода:

  1. из А и АВ выводимо В,

  2. из Р(х) выводимо (х) Р(х).

Правило 1) называется Modus Ponens или правилом заключения, правило 2) — правилом обобщения или правилом связывания квантором общности. Правило заключения символически записывается следующим образом:

.

Пример 5. Металл — проводник; железо — металл. Следовательно, железо — проводник. Это умозаключение символически запишется так:
металл — проводник, железо — металл

железо — проводник.■
Из основных правил вывода 1), 2) можно вывести и другие правила, которые упростят доказательства:

  1. правило введение конъюнкции

  2. правило удаления конъюнкции

  3. правило силлогизма

  4. правило отрицания

  5. правило контрапозиции

  6. правило расширенной контрапозиции

  7. правило удаления дизъюнкции

  8. правило сведения к абсурду .

4.20. Доказательство методом от противного основано на правиле отрицания. Пусть мы хотим доказать теорему АВ, исходя из того что А — истина. Делаем предположение, что — истина. Затем логическими средствами приходим к тому, что — истина. Появление двух противоречащих друг другу высказываний А и свидетельствует о наличии противоречия, которое может быть снято только отказом от сделанного предположения: — ложь, следовательно, В — истина.

4.21. Определения. Как отмечалось в п. 1.2, определения имеют специальную структуру. Для формулировки определения понятия математического объекта (например, прямоугольника) должны быть выполнены следующие условия:

1) выбирается множество (род) М объектов (всех параллелограммов), обладающих родовым признаком  определяемого объекта (четырехугольника, у которого противоположные стороны попарно параллельны)

2) формулируется характеристическое свойство, видовое отличие,  (наличие прямого угла в параллелограмме)

3) выделяется подмножество KМ объектов (называемых прямоугольниками) со свойством .

Другой пример: животное и лошадь; понятие «животное» — род, а понятие «лошадь» — вид. Прикольный пример: люди и зайцы; люди — род, зайцы — вид.

С теоретико-множественной точки зрения множество K определяемых объектов (всех прямоугольников) является подмножеством множества М (всех параллелограммов):

х обладает свойством },

при этом слева от вертикальной черты указан родовой признак (х является параллелограммом), а справа — видовое отличие, характеристическое свойство  (параллелограмм х имеет прямой угол).

Логическая структура определения имеет вид высказывания:

(xM) A(x)  B(x),

где М — род — множество всех параллелограммов, А(х) = «х называется прямоугольником» — предикат, вводящий новое понятие, В(х) = «в параллелограмме х все углы — прямые» — предикат, содержащий характеристическое свойство. Это высказывание звучит так: «Параллелограмм х называется прямоугольником тогда и только тогда, когда у параллелограмма х имеется прямой угол». После литературной обработки определение становится более благозвучным: «Прямоугольником называется параллелограмм с прямым углом».

Определения должны удовлетворять трем требованиям:

  • они не должны приводить к порочному кругу,

  • каждое понятие должно определяться один раз,

  • определение не должно быть ни слишком узким, ни чрезвычайно широким для определяемого понятия.

4.22. Двоичная арифметика. В позиционной системе счисления с основанием р любое натуральное число хN записывается последовательностью цифр (см. п. 3.14), что означает

.

Для десятичной системы р = 10; например,

5092 = .

Для двоичной системы р = 2. В двоичной записи используются только две цифры 0 и 1. Например, первые несколько натуральных чисел мы для сравнения запишем в десятичной и двоичной системах счисления:

0 = 02, 1 = 12,

2 = 102, 3 = 112,

4 = 1002, 5 = 1102, 6 = 1102, 7 = 1112,

8 =10002, 9 = 10012, 10 = 10102, 11 = 10112,

12 = 11002, 13 = 11012, 14 = 11102, 15 = 11112,

16 = 100002, и т.д.

Алгоритм перехода от десятичной записи натурального числа х к двоичной х = (х1х2хn)2 основан на вычислении остатков при многократном делении на 2. Действительно, пусть , или, равносильно, . Тогда при делении числа х на 2 частное будет равно у, а остаток — хn. При делении же числа у на 2 получится остаток и т.д. Таким образом, полученные остатки, записанные в обратном порядке их получения, дают искомую двоичную запись числа х. Например:
_26 | 2

26 _13 | 2

12 _6 | 2

6 _3 | 2 2610 = 110102.

2 _1 | 2

0 0

Действительно, проверяя полученный результат, получаем:

110102 = 1  24 + 1  23 + 0  22 + 1  21 + 0  20 = 16 + 8 + 2 = 26.

Дробное число переводится в двоичную систему счисления методом последовательного умножения на 2. При этом каждый раз после запятой двоичного числа записывается 0 или 1 соответственно целой части результата умножения. Последовательное умножение продолжается до тех пор, пока дробная часть не обратится в нуль или пока не получится требуемое количество двоичных знаков после запятой.

Пример 6. Двоичное представление числа 0,312510 получается следующим образом:



0,3125




0
2

0,6250




1
2

0,2500 0,312510 = 0,01012.




0
2

0,5000


1
2

0,0000

Проверка полученного результата дает:

0,01012 = 0  2–1 + 1  2–2 + 0  2–3 + 1  2–4 = = 0,3125.■

Если число х является смешанным, т.е. его целая часть [х] и дробная часть {x} = х – [х] отличны от нуля, то оно переводится в двоичную систему раздельно: целая часть — последовательным делением, а дробная — последовательным умножением.

Арифметические операции над числами сводятся к операциям сложения и умножения одноразрядных чисел. В двоичной системе счисления умножение задается по правилу: 0  0 = 0, 0  1 = 0, 1  0 = 0, 1  1 = 1, а сложение — по правилу: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 102. Операции над двоичными числами выполняются по правилам, аналогичным для десятичных чисел, но эти правила предельно упрощаются (особенно для умножения).

Пример 7. Десятичные операции 41 + 27 = 68 и 41  5 = 205 выглядят следующим образом:
101001

101001 101

11011 101001 .■

1000100 101001

11001101



Задание 3. Даны (см. табл. 2) десятичные числа a, b, c, d:
1) Выполните в двоичной системе вычисление по формуле:

.

2) Переведите в двоичную систему счисления с точностью до пяти знаков после запятой число: .■


Таблица 2



a

b

c

d



a

b

c

d



a

b

c

d



a

b

c

d



a

b

c

d

1

3

7

3

2

7

1

3

3

9

13

3

9

7

5

19

3

9

3

7

25

3

3

9

8

2

1

6

4

3

8

2

7

4

8

14

4

3

9

7

20

4

6

2

6

26

2

7

4

9

3

4

3

7

4

9

3

6

5

7

15

5

7

3

6

21

1

3

3

8

27

1

6

7

7

4

1

7

3

2

10

4

9

3

8

16

3

6

4

5

22

3

7

7

5

28

4

9

2

3

5

2

3

5

7

11

5

3

5

5

17

1

9

5

8

23

5

7

2

4

29

5

7

3

7

6

4

6

7

8

12

4

9

2

4

18

2

7

6

9

24

1

9

4

6

30

6

9

3

4
1   2   3   4   5   6

Похожие:

Множества, отображения, логика iconФакультет
Отображения множеств. Счетные и несчетные множества. Функции множества. Мера множества. Измеримые множества и функции. Интеграл Лебега....
Множества, отображения, логика iconУчебно-методическое пособие Саранск 2012 Отображения. Функции Сведения из теории
Пусть даны некоторые множества и. Бинарное соответствие из в называется отображением множества в множество, если
Множества, отображения, логика iconМатематический анализ
Множества. Декартово произведение двух множеств. Отображения функции, обратная функция. Эквивалентность множеств. Счетность множества...
Множества, отображения, логика iconПрограмма курса дифференциальная топология и риманова геометрия
Топология, топологическое пространство. Гомеоморфизм, сравнение топологий. Открытые и замкнутые множества. Внутренность, замыкание...
Множества, отображения, логика iconГруппы: мк-301, мт-301
Понятия множества и отображения, способы задания множеств. Алгебра множеств и подмножеств. Теорема об отображении множества самого...
Множества, отображения, логика icon1 Содержание дисциплины
Множества, подмножества. Булевы операции над множествами и их свойства. Законы Д’Моргана. Отношения, функциональные отношения, отображения....
Множества, отображения, логика iconМножества и операции со множествами. Понятие множества и мультимножества
Цель таких описаний отразить важнейшие (атрибутные) свойства множества, а именно: разли­чимость всех частей множества, неупорядоченность...
Множества, отображения, логика iconПрограмма государственного экзамена Направление подготовки 230400 «Прикладная математика»
Отображения. Инъективные, сюръективные и биективные отображения. Теорема о произведении (композиции) отображений. Критерий существования...
Множества, отображения, логика icon1-й и 2-й семестры Множества и отображения
Множество и его элементы. Примеры множеств. Отношение включения и его свойства. Операции над множествами: пересечение, объединение,...
Множества, отображения, логика iconРоберт столл множества. Логика. Аксиоматические теории

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org