II. Равносильности, выражающие одни логические операции через другие.

Стр 1 из 6Следующая ⇒

Оглавление

1 Занятие №1. 4

1.1 Алгебра логики. Высказывания и логические операции над ними. Формулы алгебры логики 4

2 Занятие №2. 9

2.1 Алгебра логики. Равносильные формулы алгебры логики. 9

3 Занятие №3. 12

3.1 Функции алгебры логики. Совершенные нормальные формы 12

3.2 Приложения алгебры логики. 16

3.3 Домашняя работа. 20

4 Занятие №4. 21

4.1 Контрольная работа по темам: Равносильные преобразования. СКНФ, СДНФ, РКС 21

5 Занятие №5. 22

5.1Решение логических задач с помощью алгебры логики. 22

5.2 Области истинности. 26

5.3 Домашнее задание. 27

6 Занятие №6. 28

6.1 Множества. Область истинности. Диаграммы Эйлера – Венна 28

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

6.3 Векторы, прямые произведения, проекции векторов. 34

6.4 Домашнее задание. 35

7 Занятие №7. 36

7.1 Контрольная работа по темам: Диаграммы, решение задач, операции над множествами 36

8 Занятие №8. 40

8.1 Предикаты. 40

8.2 Понятие формулы логики предикатов. Равносильные формулы логики предикатов 48

8.3 Домашнее задание. 54

9 Занятие №9. 55

9.1 Графы. 55

10 Занятие №10. 66

10.1 Комбинаторика. Задачи по комбинаторике. 66

1 Занятие №1

1.1 Алгебра логики. Высказывания и логические операции над ними. Формулы алгебры логики

Понятие высказывания является основным неопределяемым понятием математической логики. Под высказыванием понимают любое повествовательное предложение, о котором можно сказать истинно оно или ложно в данных условиях места и времени. Логическое значение высказывания «истина» («ложь») обозначается буквой и, (л)или цифрой 1, (0). Высказывания обычно обозначают латинскими буквами.

Отрицанием высказывания а называется высказывания ā, которое истинно, если а ложно, и ложно, если аистинно. Высказывание āчитается так: «Не а». Таблица истинности для ā имеет вид:

а	ā
1	1
0	0

Конъюнкцией высказывания a,b называется высказывание a b (a &b ), которое истинно, если a и b истинны и ложно, если хотя бы одно из них ложно. Высказывание a b читается: «a и b».

Дизъюнкцией высказываний a,b называется высказыванием a b, которое истинно, если хотя бы одно из высказываний a или b истинно, и ложно, если оба они ложны. Читается: «a или b».

Импликация высказываний a,b называется высказывание a b, которое ложно, если a истинно и b ложно, и истинно во всех остальных случаях. Читается: «Если a, то b».

Эквивалентностью (или эквиваленцией) высказываний a,b называется высказывание a b, которое истинно, если оба высказывания a и b одновременно истинны или ложны, и ложно во всех остальных случаях.

Читается: «a тогда и только тогда, когда b».

Таблица истинности для этих логических операций такова:

a	b	a b	a b	a b	a b
1	1	1	1	1	1
1	0	0	1	0	0
0	1	0	1	1	0
0	0	0	0	1	1

Все высказывания можно разделить на простые (или элементарные) и составные (или сложные).

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

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

Формула А, всегда истинная, называется тождественно истинной формулой или тавтологией и запивается А 1. Формула В, всегда ложная, называется тождественно ложной формулой и записывается В 0.

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

река Волхов впадает в озеро Ильмень;

всякий человек имеет брата;

пейте томатный сок!;

существует человек, который моложе своего отца;

который час?;

ни один человек не весит более 1000 кг;

23<5;

Для всех действительных чисел x и y равенство x+y=y+x;

;

Решение. Легко видеть, что высказывания 4), 6), 8) – истинные, а высказывания 1), 2), 7 - ложные. Предложения 3), 5), 9), 10) не являются высказываниями.

Пример 2. Пустьa – высказывание «Студент Иванов изучает английский язык», b - высказывание «Студент Иванов успевает по математической логике». Дать словесную формулировку высказываний:

1) ; 2)a b; 3) .

Решение. а) «Студент Иванов изучает английский язык и не успевает по математической логике»; в) «Студент Иванов не успевает по математической логике тогда и только тогда, когда он не изучает английский язык».

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

Решение. Таблица истинности для высказывания имеет вид:

a	b
1	1	0	1
1	0	1	1
0	1	0	0
0	0	1	1

1.7. Обозначьте элементарные высказывания буквами и запишите следующие высказывания с помощью символов алгебры логики:

1) 45 кратно 3 и 42 кратно 3;

2) 45 кратно 3 и 12 не кратно;

5) если число 212 делится на 3 и 4, то оно делится на 12;

1.13. Найдите логическое значения x и y, при которых выполняется равенства:

1.14.

1) Известно, что импликация истинна, а эквивалентность ложна. Что можно сказать о значении импликации ?

2) Известно, что эквивалентность истинна. Что можно сказать о значениях импликации ?

1.15. Пусть x=0, y=0, z=1. Определить логические значения нижеследующих сложных высказываний:

1.16. Показать, что логические связки , , , , где л – фиксированное ложное высказывание, имеют ту же таблицу истинности, что и импликация .

1.18. Составить таблицы истинности для формул:

1) ;

2) ;

3) ;

4) ;

1.19. Установить, какие из следующих формул являются тождественно истинными, тождественно ложными:

;

Домашнее задание по первому уроку.:

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

Москва – столица России;

Студент физико-математического факультета;

;

Луна есть спутник Марса;

a>0.

2. Известно, что имеет значения 1. Что можно сказать о значениях ?

3. Установить, какие из следующих формул являются тождественно истинными, тождественно ложными:

;

4. Пусть p и q обозначают высказывания:

p – «Я учусь в школе»,

q – «Я люблю математику».

Прочитайте следующие сложные высказывания:

1) 2) 3) 4) ; 5) 6)

2 Занятие №2.

2.1 Алгебра логики. Равносильные формулы
алгебры логики

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