Элементы математической логики и теории множеств. Коробков С.С.

1 Министерство общего и профессионального образования Российской Федерации Уральский государственный педагогический университет С.С. Коробков ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ И ТЕОРИИ

Элементы математической логики и теории множеств. Коробков С.С.

Книги по всем темамPages:     || 2 | 3 | 4 | 5 |   …   | 6 | Министерство общего и профессионального образования Российской Федерации Уральский государственный педагогический университет С.С.

Коробков ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ И ТЕОРИИ МНОЖЕСТВ Учебное пособие Екатеринбург 1999 С.С. Коробков. Элементы математической логики и теории множеств:

Учебное пособие/ Урал. гос. пед. ун-т.

Екатеринбург, 1999, 63 с.

В предлагаемом учебном пособии, предназначенном для студентов первого курса очного и заочного отделений математического факультета, разобран весь основной материал первой темы курса “Алгебра и теория чисел”.

Все определяемые в пособии понятия сопровождаются примерами, а утверждения — подробными доказательствами. В конце каждого пункта сформулированы вопросы для самопроверки, отражающие обязательный минимум знаний.

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

Пособие будет полезно учителям математики и учащимся старших классов.

Рецензент: к.ф.-м.н., доцент Е.А. Перминов © С.С. Коробков, 1999 Оглавление Предисловие 5 1 Элементы математической логики 7 1.1 Высказывания. Логические операции………… 7 1.1.1 Понятие высказывания……………. 7 1.1.2 Логические операции…………….. 8 1.1.3 Формулы логики высказываний……….. 9 1.1.4 Вопросы для самопроверки…………. 15 1.1.5 Упражнения……..

………….. 15 1.2 Логическое следствие. Методы доказательств……. 16 1.2.1 Логическое следствие…………….. 16 1.2.2 Методы доказательств……………. 17 1.2.3 Вопросы для самопроверки…………. 21 1.2.4 Упражнения…………………. 21 1.3 Предикаты. Кванторы………………… 21 1.3.1 Предикаты………………….. 21 1.3.2 Кванторы…………………… 1.

3.3 Вопросы для самопроверки…………. 1.3.4 Упражнения…………………. 1.4 Формулы логики предикатов…………….. 1.4.1 Формулы логики предикатов…………. 1.4.2 Запись математических предложений на языке логики предикатов………………. 1.4.3 Вопросы для самопроверки………….. 1.4.4 Упражнения…………………. 1.5 Виды теорем.

Необходимость и достаточность……. 1.5.1 Вопросы для самопроверки………….. 1.5.2 Упражнения…………………. 2 Элементы теории множеств 2.1 Понятие множества…………………. 2.1.1 Понятие множества. Способы задания множеств. 2.1.2 Пустое и универсальное множества……… 2.1.3 Вопросы для самопроверки………….. 2.1.4 Упражнения…………………. 2.

2 Операции над множествами…………….. 2.2.1 Определение операций над множествами…… 2.2.2 Свойства операций над множествами…….. 2.2.3 Вопросы для самопроверки………….. 2.2.4 Упражнения…………………. 2.3 Бинарные отношения………………… 2.3.1 Определение и примеры бинарных отношений… 2.3.2 Виды бинарных отношений………….. 2.3.

3 Вопросы для самопроверки………….. 2.3.4 Упражнения…………………. 2.4 Отношение эквивалентности…………….. 2.4.1 Отношение эквивалентности…………. 2.4.2 Разбиение множества…………….. 2.4.3 Вопросы для самопроверки………….. 2.4.4 Упражнения…………………. 2.5 Функции и отображения……………….. 2.5.1 Определения функции и отображения….

…. 2.5.2 Виды отображений……………… 2.5.3 Вопросы для самопроверки………….. 2.5.4 Упражнения…………………. Список литературы Предисловие Предлагаемое учебное пособие является вторым изданием работы автора “Элементы математической логики и теории множеств”, опубликованной в Свердловском государственном педагогическом институте в 1988 году.

По своему содержанию новое издание не многим отличается от предыдущего. В него внесено лишь несколько исправлений и незначительных дополнений.

Существенные различия можно обнаружить в оформлении этих двух изданий: если первое из них автор печатал на пишущей машинке, а затем от руки вписывал формулы, то второе издания было подготовлено им с использованием издательской A системы LTEX 2, специально предназначенной для подготовки к печати математических текстов.

Данное учебное пособие адресовано в первую очередь студентампервокурсникам математического факультета педагогического университета. Оно состоит из двух частей. Первая часть целиком посвящена элементам математической логики. В ней изучаются операции над высказываниями, свойства этих операций, рассматриваются различные методы доказательств и приводятся их логические обоснования.

Кроме этого, здесь вводятся различные виды теорем и такие понятия, как “необходимое условие”, “достаточное условие” и “необходимое и достаточное условие”, с которыми студенты встретятся в дальнейшем в самых различных математических дисциплинах.

В этой же части рассмотрены правила записи математических предложений на специальном языке — языке логики предикатов и правила построения отрицаний.

Вторая часть пособия посвящена элементам теории множеств.

Здесь вводятся операции над множествами (пересечение, объединение, разность и дополнение) и изучаются их свойства, рассматриваются бинарные отношения и отображения множеств. Все новые понятия сопровождаются определениями, а все определения — многочисленными примерами.

Данное пособие можно рассматривать как введение в математику, хотя оно не охватывает всех аспектов введения (в нем не говорится о методе математической индукции и нет элементов комбинаторики).

Главные его цели — 1) познакомить с логическими операциями и основными способами доказательств теорем, 2) показать возможности использования языка логики предикатов для записи математических предложений, 3) научить выполнять основные операции над множествами.

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

В работе использованы следующие обозначения: буквами N, Z, Q и R обозначены соответственно множества натуральных, целых, рациональных и действительных чисел. Значком обозначается конец доказательства и конец решения задачи.

Глава Элементы математической логики 1.1 Высказывания. Логические операции 1.1.1 Понятие высказывания Под высказыванием понимается повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Высказывания будем обозначать заглавными латинскими буквами. Примеры высказываний:

D : 5 — простое число, E : 12 = 22 · 3, F : Земля — спутник Луны, G : Функция y = cos x является четной, H : если a и b — различные векторы, то a – b = b – a.

Каждое высказывание кроме своего смыслового значения имеет и истинностное значение, которое есть истина (сокращенно И) или ложь (сокращенно Л). Так в предыдущих примерах истинностные значения высказываний D, E, G, H равны И, а истинностное значение высказывания F равно Л.

Высказывания D, E, F, G являются примерами простых высказываний, высказывание H — пример сложного высказывания. Сложные высказывания образуются из простых с помощью логических операций (связок).

Определим следующие логические операции: отрицание, конъюнкцию, дизъюнкцию, импликацию и эквиваленцию.

1.1.2 Логические операции Опpеделение 1.1.1 Отрицанием высказывания A называется высказывание ¬A1 (читается «не А»), которое истинно тогда и только тогда, когда высказывание А ложно.

Опpеделение 1.1.2 Конъюнкцией высказываний А и В называется высказывание A B (читается «А и B»), которое истинно тогда и только тогда, когда оба высказывания А и В истинны.

Опpеделение 1.1.3 Дизъюнкцией высказываний А и В называется высказывание A B (читается «А или B»), которое ложно тогда и только тогда, когда оба высказывания А и В ложны.

Опpеделение 1.1.4 Импликацией высказываний А и В называется высказывание A B (читается «если А, то B»), которое ложно тогда и только тогда, когда высказывание А истинно, а высказывание В ложно.

Высказывания A и В в импликации имеют специальные названия: А называется посылкой или условием, а В называется следствием или заключением.

Опpеделение 1.1.5 Эквиваленцией высказываний А и В называется высказывание A B (читается «А тогда и только тогда, когда В»), которое истинно тогда и только тогда, когда оба высказывания А и В одновременно истинны или ложны.

Примеры. Пусть буквы D, E, F, G, H имеют тот же смысл, что и выше.

Тогда высказывание (¬D) G является истинным, так как высказывание G истинно; высказывание (E (¬G)) F истинно, так как высказывания (E (¬G)) и F одновременно ложны; высказывание D ¬G ложно, так как высказывание D истинно, а высказывание ¬G ложно.

Подчеркнем, что логические операции определяются над любыми высказываниями и потому истинными могут оказаться совершенно бессмысленные высказывания, например, такие как F G: если Земля — спутник Луны, то 12 = 22 · 3.

В некоторых учебниках высказывание A.

1.1.3 Формулы логики высказываний Логические операции над высказываниями обладают рядом общих свойств. Применение этих свойств позволяет, с одной стороны, сводить анализ сложных высказываний к анализу более простых высказываний, а с другой стороны — преобразовывать длинные цепочки высказываний в более короткие.

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

Изучение свойств логических операций естественно проводить не на конкретных высказываниях, а на особых выражениях, содержащих переменные, принимающие значения И и Л (такие переменные называются пропозициональными переменными), знаки логических операций и круглые скобки для указания порядка выполнения действий.

Пропозициональные переменные будем обозначать малыми латинскими буквами и называть их просто переменными. Сформулируем определение формулы логики высказываний:

Опpеделение 1.1.6 1) Пропозициональные переменные, буквы И и Л являются формулами логики высказываний;

2) если A и B — формулы логики высказываний, то формулами логики высказываний являются также выражения: (¬A), (A B), (A B), (A B), (A B);

3) выражение является формулой логики высказываний тогда и только тогда, когда оно удовлетворяет первому или второму пункту данного определения.

Примеры формул логики высказываний: (¬A (A (B C))), ((A B) ((¬A) C)), (A ¬(B C)). Следующие выражения не являются формулами логики высказываний: (), (¬A)¬B, (¬ B), (A B), (A¬ B).

Из определения 1.1.6 следует, что формулы логики высказываний имеют внешнее сходство с буквенными выражениями элементарной алгебры. Они содержат конечное число переменных, то есть элементарных формул, левых и правых скобок, знаков логических операций и букв И и Л.

В дальнейшем там, где не возникает двусмыслия, для сокращения речи мы вместо слов «формула логики высказываний» будем говорить просто «формула». Как правило, формула логики высказываний, содержащая пять или более знаков логических операций, — это громоздкое и трудно читаемое выражение.

Формулу можно упростить за счет уменьшения числа скобок в ней, приняв следующие соглашения:

1) внешние скобки в формуле можно опускать;

2) внутренние скобки в формуле можно опускать с учетом следующего порядка выполнения действий: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.

Пример такого упрощения: формулу (A (B (C (D (¬E))))) можно записать более коротко: A B C D ¬E. Очевидно, что совсем без скобок обойтись нельзя. Действительно, в формулах A (B C) и A B C различные порядки выполнения действий.

Подставляя в формулу вместо переменных их значения и выполняя указанные в ней действия, находим истинностное значение формулы.

Зависимость истинностных значений формулы от значений входящих в нее переменных наглядно иллюстрируют истинностные таблицы. С использованием этих таблиц основные логические операции можно было бы определить так:

p q ¬p p q p q p q p q И И Л И И И И И Л Л Л И Л Л Л И И Л И И Л Л Л И Л Л И И Существуют формулы, истинностные значения которых не зависят от значений входящих в них переменных. Такие формулы имеют специальные названия.

Опpеделение 1.1.7 Формула логики высказываний называется тождественно истинной (тождественно ложной), если при любых значениях входящих в нее переменных ее истинностное значение равно истине (лжи).

Тождественно истинностные формулы называют также тавтологиями, а тождественно ложные — противоречиями.

Примерами тождественно истинных формул являются формулы p ¬p, p (p q) q, p p q, а примерами тождественно ложных — формулы p ¬p, (p (¬p q)) ¬q. Для того, чтобы убедиться в этом, достаточно составить для каждой из формул таблицу истинности.

Покажем это на примере формулы p (p q) q. Переменными в этой формуле являются буквы p и q. Порядок выполнения действий таков:

импликация (в скобках), конъюнкция, импликация. В соответствии с этим выделяем части, из которых состоит формула: p q, p (p q) и составляем таблицу истинности:

p q p q p (p q) p (p q) q И И И И И И Л Л Л И Л И И Л И Л Л И Л И Существуют формулы, которые не являются ни тождественно истинными, ни тождественно ложными. Такие формулы принимают истинностные значения И и Л. Примеры таких формул: p, p ¬q, p ¬q.

Опpеделение 1.1.8 Две формулы логики высказываний A и B называются равносильными, если при любом наборе значений переменных, входящих в эти формулы, истинностные значения формул A и B равны.

То, что формулы A и B равносильны, будем записывать так: A B.

Понятия равносильности и эквиваленции тесно связаны между собой.

Эта связь отражена в следующей теореме:

Теоpема 1.1.1 Формулы логики высказываний A и B равносильны тогда и только тогда, когда формула A B является тождественно истинной.

Доказательство. Пусть формулы A и B зависят от переменных p1, p2,…, pn. Предположим сначала, что формулы A и B равносильны, и докажем, что A B — тождественно истинная формула. Возьмем произвольный набор значений переменных p1, p2,…, pn.

При этом наборе формулы A и B будут иметь какие-то истинностные значения, причем, если истинностное значение формулы A равно И, то истинностное значение формулы B также равно И, а если истинностное значение формулы A равно Л, то истинностное значение формулы B также равно Л.

Это означает, что формула A B при любом наборе значений входящих в нее переменных p1, p2,…, pn принимает истинностное значение, равное И, то есть является тождественно истинной.

Пусть теперь A B — тождественно истинная формула. Докажем, что A и B — равносильные формулы. При произвольном наборе значений переменных p1, p2,…, pn, входящих в формулу A B, ее истинностное значение равно И. Согласно определению эквиваленции это означает, что формулы A и B принимают одинаковые истинностные значения, то есть являются равносильными.

Теоpема 1.1.2 Пусть формулы A и B зависят от переменных p1, p2,…, pn. Предположим, что формулы A и B получены из формул A и B соответственно подстановкой произвольных формул A1, A2,…, An вместо переменных p1, p2,…, pn. Тогда если A B, то A B.

Доказательство. Пусть формулы A1, A2,…, An зависят от переменных q1, q2,…, qm. Тогда ясно, что формула A B, полученная из формулы A B заменой переменных p1, p2,…, pn формулами A1, A2,…, An соответственно, зависит от переменных q1, q2,…, qm.

Пусть A B. Докажем, что формула A B является тождественно истинной. Для этого возьмем произвольный набор значений переменных q1, q2,…, qm. При этом наборе формулы A1, A2,…, An примут какието истинностные значения. Обозначим их буквами a1, a2,…, an соответственно. Положим p1 = a1, p2 = a2,…, pn = an.

Тогда формулы A B и A B будут иметь одинаковые истинностные значения. По теореме 1.1.1 A B — тождественно истинная формула. Следовательно, формула A B принимает значение И при любом наборе значений переменных q1, q2,…, qm, то есть является тождественно истинной формулой. Применяя теорему 1.1.

1 теперь уже к формуле A B, заключаем, что A B.

Теоpема 1.1.3 (Законы логики высказываний) Пусть A, B, C — произвольные формулы логики высказываний. Тогда справедливы следующие утверждения:

Pages:     || 2 | 3 | 4 | 5 |   …   | 6 | Книги по всем темам

Источник: http://knigi.dissers.ru/books/pedagogika/4744-1.php

лекции (2)

Элементы математической логики и теории множеств. Коробков С.С.

С.С. Коробков

Основы математической обработки информации

Часть I. Элементы математической логики и теории множеств

Коробков С.С. Основы математической обработки информации. Урал. гос. пед. ун-т. Екатеринбург, 2012.

Данное учебное пособие предназначено для студентов, изучающих дисциплину «Основы математической обработки информации» Материал первой части изложен в форме лекций. В конце каждой лекции приведен список вопросов для самопроверки, а также набор упражнений, необходимый для усвоения основных понятий. В приложении приведена зачетная работа.

Рецензент: к.ф.-м.н., доцент Ершова Т.И.

c С.С. Коробков, 2012

1

Высказывания. Логические операции

4

1.1

Понятие высказывания . . . . . . . . . . . . . . . . . . . . .

4

1.2

Логические операции . . . . . . . . . . . . . . . . . . . . . .

4

1.3

Формулы логики высказываний . . . . . . . . . . . . . . . .

5

1.4

Вопросы для самопроверки . . . . . . . . . . . . . . . . . . .

10

1.5

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2

Предикаты. Кванторы

12

2.1Предикаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2Кванторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3

Формулы логики предикатов . . . . . . . . . . . . . . . . . .

16

2.4

Запись предложений на языке логики предикатов . . . . . .

18

2.5

Вопросы для самопроверки . . . . . . . . . . . . . . . . . . .

19

2.6

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3 Множества

22

3.1

Понятие множества . . . . . . . . . . . . . . . . . . . . . . .

22

3.2

Способы задания множеств . . . . . . . . . . . . . . . . . . .

22

3.3Подмножество . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.4

Пустое и универсальное множества . . . . . . . . . . . . . .

24

3.5

Диаграмма подмножеств. . . . . . . . . . . . . . . . . . . . .

25

3.6

Операции над множествами. . . . . . . . . . . . . . . . . . .

26

3.7

Вопросы для самопроверки . . . . . . . . . . . . . . . . . . .

31

3.8

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4 Приложения

34

4.1

Задания для контрольной работы . . . . . . . . . . . . . . .

34

4.2

Пример решения варианта контрольной работы . . . . . . .

39

Литература

41

1Высказывания. Логические операции

1.1Понятие высказывания

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

D :

5 — простое число,

E :

12 = 22 · 3,

F :

Земля — спутник Луны,

G :

Функция y = cos x является четной,

H :

~

~

~ ~ ~ ~

если a

и b — различные векторы, то a − b 6= b − a.

Каждое высказывание кроме своего смыслового значения имеет и истинностное значение, которое есть истина (сокращенно И) или ложь (сокращенно Л). Так в предыдущих примерах истинностные значения высказываний D, E, G, H равны И, а истинностное значение высказывания F равно Л.

Высказывания D, E, F , G являются примерами простых высказываний, высказывание H — пример сложного высказывания. Сложные высказывания образуются из простых с помощью логических операций (связок).

Определим следующие логические операции: отрицание, конъюнкцию, дизъюнкцию, импликацию и эквиваленцию.

1.2Логические операции

Опpеделение 1.1 Отрицанием высказывания A называется высказывание ¬A1 (читается «не А»), которое истинно тогда и только тогда, когда высказывание А ложно.

Опpеделение 1.2 Конъюнкцией высказываний А и В называется высказывание A B (читается «А и B»), которое истинно тогда и только тогда, когда оба высказывания А и В истинны.

Опpеделение 1.3 Дизъюнкцией высказываний А и В называется высказывание A B (читается «А или B»), которое ложно тогда и только тогда, когда оба высказывания А и В ложны.

Опpеделение 1.4 Импликацией высказываний А и В называется высказывание A B (читается «если А, то B»), которое ложно тогда и только тогда, когда высказывание А истинно, а высказывание В ложно.

1В некоторых учебниках высказывание A.

Высказывания A и В в импликации имеют специальные названия: высказывание А называется посылкой или условием, а высказывание В называется

следствием или заключением.

Опpеделение 1.5 Эквиваленцией высказываний А и В называется высказывание A B (читается «А тогда и только тогда, когда В»), которое истинно тогда и только тогда, когда оба высказывания А и В одновременно истинны или ложны.

Примеры. Пусть буквы D, E, F , G, H имеют тот же смысл, что и выше. Тогда высказывание (¬D) G: «5 — не простое число или функция y = cos x является четной», является истинным, так как высказывание G истинно.

Высказывание (E (¬G)) F : «12 = 22 · 3 и функция y = cos x является четной тогда и только тогда, когда Земля — спутник Луны », не смотря на свою бессмысленность истинно, так как высказывания (E (¬G)) и F одновременно ложны.

Высказывание D ¬G: «если 5 — простое число, то функция y = cos x не является четной» ложно, так как высказывание D истинно, а высказывание ¬G ложно.

1.3Формулы логики высказываний

Логические операции над высказываниями обладают различными свойствами.

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

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

Изучение свойств логических операций естественно проводить не на конкретных высказываниях, а на особых выражениях, содержащих переменные, принимающие значения И и Л (такие переменные называются логическими переменными), знаки логических операций и круглые скобки для указания порядка выполнения действий. Логические переменные будем обозначать малыми латинскими буквами и называть их просто переменными. Сформулируем определение формулы логики высказываний:

Опpеделение 1.6 1) Логические переменные, буквы И и Л являются формулами логики высказываний;

2) если A и B — формулы логики высказываний, то формулами логики высказываний являются также выражения: (¬A), (A B), (A B), (A B),

(A B);

3) выражение является формулой логики высказываний тогда и только тогда, когда оно удовлетворяет первому или второму пункту данного определения.

Примеры формул логики высказываний:

(¬A (A (B C))) , ((A B) ((¬A) C)) , (A ¬(B C)) .

Следующие выражения не являются формулами логики высказываний:

( ), (¬A)¬B, ( A B), (A¬ B).

Из определения 1.6 следует, что формулы логики высказываний внешне схожи с буквенными выражениями элементарной алгебры, а именно: содержат конечное число переменных, то есть элементарных формул, левых и правых скобок, знаков логических операций и букв И и Л.

В дальнейшем там, где не возникает двусмыслия, для сокращения речи мы слова «формула логики высказываний» будем заменять словом «формула». Как правило, формула логики высказываний, содержащая пять или более знаков логических операций, — это громоздкое и трудно читаемое выражение.

Формулу можно упростить за счет уменьшения числа скобок в ней, приняв следующие соглашения:

1)внешние скобки в формуле можно опускать;

2)внутренние скобки в формуле можно опускать с учетом следующего порядка выполнения действий: отрицание, конъюнкция,

дизъюнкция, импликация, эквиваленция.

Пример такого упрощения: формулу (A (B (C (D (¬E))))) можно записать более коротко: A B C D ¬E. Очевидно, что совсем без скобок обойтись нельзя. Действительно, в формулах A (B C) и A B C различные порядки выполнения действий.

Подставляя в формулу вместо переменных их допустимые значения и выполняя указанные в ней действия, находим истинностное значение формулы. Зависимость истинностных значений формулы от значений входящих в нее переменных наглядно иллюстрируют истинностные таблицы. С использованием этих таблиц основные логические операции можно было бы определить так:

p

q

¬p

p q

p q

p q

p q

И

И

Л

И

И

И

И

И

Л

Л

Л

И

Л

Л

Л

И

И

Л

И

И

Л

Л

Л

И

Л

Л

И

И

Существуют формулы, истинностные значения которых не зависят от значений входящих в них переменных. Такие формулы имеют специальные названия.

Опpеделение 1.7 Формула логики высказываний называется тождественно истинной (тождественно ложной), если при любых значениях входящих в нее переменных ее истинностное значение равно истине (лжи).

Тождественно истинные формулы называют также тавтологиями, а тождественно ложные — противоречиями. Примерами тождественно истинных формул являются формулы p ¬p, p (p q) q, p p q, а примерами тождественно ложных — формулы p¬p, (p (¬p q)) ¬q.

Для того, чтобы убедиться в этом, достаточно составить для каждой из формул таблицу истинности. Покажем это на примере формулы p (p q) q. Переменными в этой формуле являются буквы p и q. Порядок выполнения действий таков: импликация (в скобках), конъюнкция, импликация.

В соответствии с этим выделяем части, из которых состоит формула: p q, p (p q) и составляем таблицу истинности:

p

q

p q

p (p q)

p (p q) q

И

И

И

И

И

И

Л

Л

Л

И

Л

И

И

Л

И

Л

Л

И

Л

И

Существуют формулы, которые не являются ни тождественно истинными, ни тождественно ложными. Такие формулы принимают истинностные значения И и Л. Примеры таких формул: p, p ¬q, p ¬q.

Опpеделение 1.8 Две формулы логики высказываний A и B называются равносильными, если при любом наборе значений переменных, входящих в эти формулы, истинностные значения формул A и B равны.

То, что формулы A и B равносильны, будем записывать так: A ≡ B.

Теоpема 1.1 (Законы логики высказываний) Пусть буквы A, B, C

обозначают произвольные формулы логики высказываний. Тогда истинны следующие утверждения:

)

1. A A ≡ A,

— свойства идемпотентности

2. A A ≡ A,

3. A

B

B

A,

— свойства коммутативности

4. A

B ≡ B

A,)

5. A (B C)

(A B)

C,

6. A

(B

C)

(A

B)

C,) — свойства ассоциативности

C),)

8. A

(B

C)

(A

B)

(A

тивности

7. A

(B

C)

(A

B)

(A

C),

— свойства дистрибу-

)

9. ¬(A B) ≡ ¬A ¬B,

— свойства де Моргана

10. ¬(A B) ≡ ¬A ¬B,

)

11. A (A B) ≡ A,

— свойства поглощения

12. A (A B) ≡ A,

13. ¬(¬A) ≡ A, — свойство двойного отрицания

14. A B ≡ ¬B ¬A, — свойство контрапозиции

15. ¬(A B) ≡ A ¬B, — свойство отрицания импликации

16. A ¬A ≡ Л, — свойство противоречия

17. A ¬A ≡ И, — свойство исключенного третьего

18. A B ≡ ¬A B,

19. A B ≡ (A B) (B A),

20. A И ≡ A,

21. A И ≡ И,

22. A Л ≡ Л,

23. A Л ≡ A.

Для доказательства теоремы достаточно проверить выполнимость сформулированных свойств для пропозициональных переменных. Такую проверку удобно осуществить с помощью истинностных таблиц. Покажем как это сделать на примере свойства 7.

p

q

r

q r

p q

p r

p (q r)

(p q) (p r)

И

И

И

И

И

И

И

И

И

И

Л

И

И

Л

И

И

И

Л

И

И

Л

И

И

И

Л

И

И

И

Л

Л

Л

Л

И

Л

Л

Л

Л

Л

Л

Л

Л

И

Л

И

Л

Л

Л

Л

Л

Л

И

И

Л

Л

Л

Л

Л

Л

Л

Л

Л

Л

Л

Л

Сравнивая два последних столбца, заключаем, что p (q r) ≡ (p q) (p r). Применение свойств логических операций позволяет выполнять различные действия: преобразовывать и упрощать формулы, определять вид формулы, устанавливать равносильность формул. Иллюстрацией этому

служат следующие две задачи.

Задача 1.1. Доказать, что формула p (p q) q является тождественно истинной.

18 7 16

Решение: p (p q) q ≡ p (¬p q) ≡ (p ¬p) (p q) q ≡

Л

(p

q)

q 3 (p

q)

Л

q

23 p

q

q

18

(p

q)

q 9 (

¬

p q)

q 6

17≡

≡ ¬

¬

¬p (¬q q) ≡ ¬p И

21

≡ И.

Числа, стоящие над знаками равносильности, означают номера примененных свойств из теоремы 1.1.

Задача 1.2. Доказать равносильность формул p ¬(q p) ¬(r q) и

¬(p (q r)).

Решение: p

¬

(q

p)

(r

q)

9

p

¬

((q

p)

(r

q))

4 p

¬

¬

8

¬5

18

¬

1

9

7

((q

p)

(q

r))

p

(p

r))

≡ ¬

(p

≡ ¬

(q

(p

r)))

(q

p

(q

r))

(p

7

¬((p q) (p (p r))) ≡ ¬((p q) ((p p) r))) ≡ ¬((p q) (p r)) ≡ ¬(p (q r)).

Решения задач 1.1 и 1.2 проведены подробно, каждому знаку равносильности соответствует применение одного свойства логических операций. На

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

Очевидно, что метод преобразования формул наиболее экономичен по сравнению с методом истинностных таблиц.

Однако без метода истинностных таблиц совсем обойтись нельзя, так как на его использовании основано доказательство свойств логических операций.

1.4Вопросы для самопроверки

1.Что понимается под высказыванием?

2.Сформулируйте определения логических операций.

3.Что называется формулой логики высказываний?

4.Каков порядок выполнения логических операций в формуле?

5.Какая формула называется тождественно истинной (тождественно ложной)?

6.В чем заключается метод истинностных таблиц?

7.Какие две формулы называются равносильными?

8.Сформулируйте и докажите основные свойства логических операций.

1.5Упражнения

1.Определить какие из следующих предложений являются высказываниями:

(a)Число 1001 не делится на 13.

(b)Если a > b>0, то a2 > b2.

(c)Если a > b и c > d, то ac > bd.

(d)Привет всем!

(e)2 + 2 = 5.

(f)Который час?

(g)Сегодня 7-е сентября.

Источник: https://studfile.net/preview/3538061/

Biz-books
Добавить комментарий