Здесь: 1 - истина, 0 - ложь.

• 1. Х: треугольник АВС - остроугольный. Х: неверно, что треугольник АВС - остроугольный. Это все равно, что: Х: треугольник АВС - прямоугольный или тупоугольный
• 2. А: Иванова М. На экзамене по математике получила 4. : Неверно, что Иванова М. по математике получила 4.

Определение: Дизъюнкцией высказывания А и В называется высказывание АВ, истинное при условии, что хотя бы одно из высказываний А или В истинно.

Его читают «А или В».

Таблица истинности для АВ

Пример: 1. На этот раз ответчик явился и суд состоялся. - истина

2. В прямоугольном треугольнике сумма двух любых углов больше или равна третьего угла и гипотенуза меньше катета. - ложь

Определение: Импликацией высказываний А и В называется высказывание АВ, ложное лишь при условии, что А истинно, а В ложно.

Его читают: «Если А, то В».

Таблица истинности

Пример: 1. Если я сдам зачет, то пойду в кино.

2. Если треугольник равнобедренный, то углы при его основании равны. Определение: Эквиваленцией высказываний А и В называется высказывание АВ, истинное в том и только в том случае, когда А и В имеют одну и ту же истинность (т.е. либо оба истинны, либо оба ложны).

Читают: «А тогда и только тогда, когда В» или «А необходимо и достаточно для В»

Таблица истинности

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

Пример: Если Саратов расположен на берегу Невы, то в Африке обитают белые медведи.

А: Саратов расположен на берегу реки Невы;

В: В Африке обитают белые медведи

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

Определение: Формулы F 1 и F 2 называются равносильными, если их эквиваленция - тавтология.

Определение: Если формулы F 1 и F 2 равносильны, то предложения Р 1 и Р 2 , которые инициируют эти формулы, называются равносильными в логике высказываний.

Основные, наиболее часто встречающиеся равносильности, называют законами логики. Перечислим некоторые из них:

• 1. Х Х - закон тождества
• 2. Х Л - закон противоречия
• 3. Х И - закон исключения третьего
• 4. Х - закон двойного отрицания

• 5. законы коммутативности
• 6. Х (У Z) (Х У) Z закон ассоциативности

Х (У Z) (Х У) Z закон дистрибутивности

7. законы Де Моргана

8. законы сочленения переменной с константой

Используя законы логики, можно преобразовывать формулы.

4. Из множества формул, равносильных между собой, рассмотрим две. Это - совершенная конъюнктивная нормальная форма (СКНФ) и совершенная дизъюнктивная нормальная форма (СДНФ). Они строятся для данной формулы на основе ее таблицы истинности.

Построение СДНФ:

• -- выбираются строки, соответствующие значениям истинности (1) данной формулы;
• -- для каждой выделенной строки составляем конъюнкцию переменных или их отрицаний так, чтобы наборам значений переменных, представленных в строке, соответствовали истинные значения конъюнкции (для этого надо переменные, которые в этой строке принимали значения ложь (0) взять со знаком отрицания, а переменные, принимающие значения истинности (1) без отрицания);
• -- составляется дизъюнкция полученных конъюнкций.

Из алгоритма следует, что для любой формулы можно составить СДНФ, и притом единственную, если формула не является тождественно ложной, т.е. принимающей только ложные значения.

Составление СКНФ осуществляется по следующему алгоритму:

• -- выделить те строки таблицы, в которых формула принимает значение ложь (0);
• -- из переменных, стоящих в каждой такой строке, составить дизъюнкцию, которая должна принимать значения - ложь (0). Для этого все переменные должны войти в нее со значением ложь, следовательно те, которые истинны (1), надо заменить их отрицанием;
• -- из полученных дизъюнкций составить конъюнкцию.

Очевидно, что любая формула, не являющаяся тавтологией, имеет СКНФ.

СДНФ и СКНФ используются для получения следствий из данной формулы.

Пример: Составить таблицу истинности СДНФ и СКНФ для формулы: .

Таблица истинности СДНФ и СКНФ

5. Рассмотрим высказывательные форму «Река впадает в Черное море». Она содержит одну переменную и может быть представлена в виде «Река х впадает в Черное море».

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

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

Определение: Функция, все значения которой принадлежат множеству, называется предикатом.

Буквы, обозначающие предикаты, называют предикатными символами.

Предикаты могут задаваться:

a) высказывательной формулой,

b) формулой, т.е. задавая интерпретацию предикатного символа,

c) таблицей.

1) Р - «впадать в Черное море».

Эта формула означает, что «Река а впадает в Черное море».

• 2) Предикат Р задан высказывательной формулой: «быть простым числом на множестве первых 15 натуральных чисел».
• 3) В табличной форме предикат имеет вид:

Областью определения предикатов может быть любое множество.

Если предикат при каком-либо наборе входящих переменных теряет смысл, то принято считать, что этому набору соответствует значение Л.

Если предикат содержит одну переменную, то его называют одноместным, две переменные - двуместным, n переменных - n-местным предикатом.

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

Над предикатами выполняются так же операции: отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции.

Определение: Подмножество множества М, на котором задан предикат Р, состоящий из тех и только тех элементов М, которым соответствует значение И предиката Р, называется множеством истинности предиката Р.

Множество истинности обозначается.

Определение: Отрицанием предиката Р называется предикат, ложный при тех наборах значений переменных, которые обращают Р в истинный, и истинный при тех наборах значений переменных, которые обращают Р в ложный предикат.

Обозначается отрицание.

Быть студентом АБиК.

Не быть студентом АБиК.

Если, то множество, где М - множество, на котором заданы предикаты Р и Q .

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

Быть футболистом

Быть студентом

: быть футболистом и быть студентом.

Определение: дизъюнкцией предикатов и называется предикат ложный при тех наборах входящих в него переменных, которые обращают оба предиката в ложные

Быть четным натуральным числом

Быть нечетным натуральным числом

: быть натуральным числом.

Определение: Импликацией предикатов называется предикат, ложный при тех и только тех наборах входящих в него переменных, которые обращают в истинный предикат, а - в ложный.

Обозначается:

Быть простым числом на множестве N

Быть нечетным числом

Ложен при и истинным при других натуральных числах.

Определение: Эквиваленцией предикатов и называется предикат, который становится истинным, если оба предиката и истинны, или оба ложны.

Обозначается:

- «выигрывать», т.е. х выигрывает у

Лучше знать шахматную историю, х знает лучше у

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

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

Обозначаются следования: .

Быть студентом

Ходить в институт

Для превращения предиката в высказывание существуют 2 пути:

1) придание переменной конкретного значения

; х - студент

Иванов - студент.

2) Навешивание кванторов - любой, всякий, каждый

Существует, имеется.

Запись, где обладает свойством Р означает, что всякий предмет х обладает свойством Р. Или по другому, «все х обладают свойством Р».

Запись означает, что существует предмет х, обладающий свойством Р.

Пример 1. Установить истинность высказывания · С
Решение. В состав сложного высказывания входят 3 простых высказывания: А, В, С. В таблице заполняются колонки значениями (0, 1). Указываются все возможные ситуации. Простые высказывания от сложных отделяются двойной вертикальной чертой.
При составлении таблицы надо следить за тем, чтобы не перепутать порядок действий; заполняя столбцы, следует двигаться “изнутри наружу”, т.е. от элементарных формул к более и более сложным; столбец, заполняемый последним, содержит значения исходной формулы.

Из таблицы видно, что данное высказывание истинно только в случае, когда А=0, В=1, С=1. Во всех остальных случаях оно ложно.

Эквивалентность высказываний.

С помощью таблиц истинности можно установить эквивалентность двух или нескольких высказываний.

Высказывания называются эквивалентными, если соответствующие значения каждого из них совпадают в таблице истинности.

Пример 2. Утверждается, что высказывание А+В· С эквивалентно высказыванию (А+В)· (А+С)
Решение. Проверка ведется путем составления таблицы истинности.

Сравнивая 5-ю и 8-ю колонки убеждаемся, что все значения, получаемые по формуле А+В· С, совпадают со значениями, получаемыми по формуле (А+В)· (А+С), т.е. высказывания эквивалентны (равносильны). Одно может заменить другое.
Эквивалентные (равносильные) высказывания соединяют знаком º А + В·Сº (А+В)· (А+С).
Отметим различие между эквивалентностью и эквиваленцией.
Эквиваленция является логической операцией, позволяющей по двум заданным высказываниям А и В построить новое А« В.
Эквивалентность же является отношением между двумя составными высказываниями, состоящим в том, что их значения истинности всегда одни и те же.

Тавтология.

Пусть дано высказывание А· и необходимо составить таблицу истинности.
Высказывание А· ложно, истинность его не зависит от истинности высказывания А.

Рассмотрим высказывание В+ .
В этом случае высказывание В+ всегда истинно, независимо от истинности В.

Высказывания, истинность которых постоянна и не зависит от истинности входящих в них простых высказываний, а определяется только их структурой, называются тождественными или тавтологиями.
Различают тождественно-истинные и тождественно-ложные высказывания.
В формулах каждое тождественно-истинное высказывание заменяется 1, а тождественно-ложное - 0. Закон исключенного третьего.
A· º 0
В+ º 1

Пример 3. Докажите тавтологию (XÙ Y)® (XÚ Y)
Решение.

Т.к. высказывание (XÙ Y)® (XÚ Y) всегда истинно, то оно является тавтологией.

Пример 4. Докажите тавтологию ((X® Y)Ù (Y® Z))® (X® Z)
Решение.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ F1 _ _ _ _ F2 _ _ _ _ _ F

Из таблицы видно, что исследуемое высказывание - тавтология, т.к. оно истинно постоянно.

Вопросы и задания.

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

а) (A+C); б) +B; в) +C); г) A+ ;
эквивалентно высказывание (B+C)

2. Установите с помощью таблиц истинности, какие из следующих формул - тавтологии:
а) « ); б) ; в) ;

г) ; д) (X® Y)« (Y® X); е) (X® Y)« ;

ж) (X® Y)« .

3. Установить истинность высказывания

4. Эквивалентны ли высказывания:
и ?

5. Установить, является ли данное высказывание тавтологией:
а) ; б)

6. Для каждой формулы придумайте формализуемые ими предложения:
а) ; б) ; в) .

7. Из простых высказываний: “Виктор хороший пловец” - А; “Виктор хорошо ныряет” - В; “Виктор хорошо поет” - С, составлено сложное высказывание, формула которого имеет вид:
X=(A+C)· (A+B). Установить, эквивалентно ли высказывание Х высказыванию: “Виктор - хороший пловец и Виктор хорошо поет”.

8.
а) ; б) ;
в) ((X1® X2)® X3)Ù (X3« X1); г) ((X® Y)Ù (Y® Z))® (X® Z).

9. Установить истинность высказываний:
а) , , ;
б) , , ;
в) , , ;
г) , , .

Законы логики

Равносильности формул логики высказываний часто называют законами логики.
Знание законов логики позволяет проверять правильность рассуждений и доказательств.
Нарушения этих законов приводят к логическим ошибкам и вытекающим из них противоречиям.
Перечислим наиболее важные из них:
1. Xº X Закон тождества
2. Закон противоречия
3. Закон исключенного третьего
4. Закон двойного отрицания
5. XÙ Xº X , XÚ Xº C Законы идемпотентности
6. C Ù U º U Ù C , C Ú U º U Ú C Законы коммутативности (переместительности)
7 . (C Ù U) Ù Z ºC Ù (U Ù Z) , (C Ú U) Ú Z º C Ú (U Ú Z) - Законы ассоциативности (сочетательности)
8. C Ù (U Ú Z) º (C Ù U) Ú (C Ù Z) , C Ú (U Ù Z) º (C Ú U) Ù (C Ú Z) - Законы дистрибутивности (распределительности)
9. , Законы де Моргана
10. XÙ 1º C , C Ú 0 º C
11. C Ù 0 º 0 , C Ú 1 º 1
12. C Ù (C Ú U) º C , C Ú (C Ù U) º C Законы поглощения
13. (C Ú U) Ù ( Ú U) º U , (C Ù U) Ú ( Ú U) º U Законы склеивания

1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием.
“Это яблоко спелое” и “Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание.
“ Неверно, что 2× 2¹ 4”

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках:
- отрицание логического произведения эквивалентно логической сумме отрицаний множителей.
- отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

Доказать законы логики можно:
1) с помощью таблиц истинности;
2) с помощью равносильностей.
Докажем законы склеивания и поглощения с помощью равносильностей:
1) (C Ú U) Ù ( Ú U) º (C + U) × ( + U) º C × + U × + U × U + C × U ºU × + U + C × U º U × +U (1 + C) º U × + U º U ( + 1) º U (Закон склеивания)

2) C Ù (C Ú U) º C × C +C × U º C +C × U º C (1 + U) º C (Закон поглощения)

Задание. Доказать законы логики с помощью таблиц истинности.

Тождественные преобразования

Упрощение формул.

Пример 1. Упростить формулу (АÚВ)· (АÚС)
Решение.
а) Раскроем скобки (A Ú B) · (A ÚC) º A · A Ú A · C Ú B · A Ú B · C
б) По закону равносильности A · A º A , следовательно,
A · A Ú A · C ÚB · A Ú B · C º A ÚA · C Ú B · A Ú B · C
в) В высказываниях А и А· C вынесем за скобки А и используя свойство АÚ1º 1, получим АÚА· СÚ B · A Ú B · C º A ·(1 ÚС) Ú B · A Ú B · Сº A ÚB · A Ú B· С
г) Аналогично пункту в) вынесем за скобки высказывание А.
AÚB · A Ú B · Сº A (1ÚB)ÚB · Сº A Ú B · С
Таким образом, мы доказали закон дистрибутивности.

2. Преобразования “поглощение” и “склеивание”

Пример 2. Упростить выражение АÚ A · B

Решение. A ÚA · B º A (1 Ú B) º A - поглощение

Пример 3. Упростить выражение A · B Ú A · - знаки логического сложения;
- знаки логического умножения.
А будут использованы:
- знаки отрицания и логического умножения;
- знаки отрицания и логического сложения.

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

Пример 6. Преобразовать формулу так, чтобы в ней не использовались знаки логического умножения.
Решение. Используя формулы де Моргана и закон двойного отрицания получим:

Установление истинности сложных высказываний.

Пример 1. Установить истинность высказывания · С

Решение. В состав сложного высказывания входят 3 простых высказывания: А, В, С. В таблице заполняются колонки значениями (0, 1). Указываются все возможные ситуации. Простые высказывания от сложных отделяются двойной вертикальной чертой.
При составлении таблицы надо следить за тем, чтобы не перепутать порядок действий; заполняя столбцы, следует двигаться “изнутри наружу”, т.е. от элементарных формул к более и более сложным; столбец, заполняемый последним, содержит значения исходной формулы.

Из таблицы видно, что данное высказывание истинно только в случае, когда А=0, В=1, С=1. Во всех остальных случаях оно ложно.

13. Равносильные формулы.

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

Равносильность обозначается знаком « ». Для преобразования формул в равносильные важную роль играют основные равносильности, выражающие одни логические операции через другие, равносильности, выражающие основные законы алгебры логики.

Для любых формул А , В , С справедливы равносильности.

I. Основные равносильности

закон идемпотентности

1-истина

0-ложь

Закон противоречия

Закон исключенного третьего

закон поглощения

формулы расщепления

закон склеивания

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

закон де Моргана

III. Равносильности, выражающие основные законы алгебры логики.

коммутативный закон

ассоциативный закон

дистрибутивный закон

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

Виды формул классической логики высказываний – в логике высказываний различают следующие виды формул:

1. Законы (тождественно-истинные формулы) – формулы, которые при любых интерпретациях пропозициональных переменных принимают значение «истинно» ;

2. Противоречия (тождественно-ложные формулы) – формулы, которые при любых интерпретациях пропозициональных переменных принимают значение «ложно» ;

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

Основные законы классической логики высказываний:

1. Закон тождества: ;

2. Закон противоречия: ;

3. Закон исключенного третьего: ;

4. Законы коммутативности и : , ;

5. Законы дистрибутивности относительно ,и наоборот: , ;

6. Закон удаления истинного члена конъюнкции: ;

7. Закон удаления ложного члена дизъюнкции: ;

8. Закон контрапозиции: ;

9. Законы взаимовыразимости пропозициональных связок: , , , , , .

Процедура разрешимости – метод, позволяющий для каждой формулы установить является она законом, противоречием или выполнимой формулой. Самой распространенной процедурой разрешимости является метод истинностных таблиц. Однако он не единственный. Эффективным методом разрешимости является метод нормальных форм для формул логики высказываний. Нормальной формой формулы логики высказываний является форма, не содержащая знака импликации « ». Различают конъюнктивную и дизъюнктивную нормальные формы. Конъюнктивная форма содержит только знаки конъюнкции « ». Если в формуле, приведенной к конъюнктивной нормальной форме, встречается подформула вида , то вся формула в этом случае является противоречием . Дизъюнктивная форма содержит только знаки дизъюнкции « ». Если в формуле, приведенной к дизъюнктивной нормальной форме, встречается подформула вида , то вся формула в этом случае является законом . Во всех остальных случаях формула является выполнимой формулой .

15. Предикаты и операции над ними. Кванторы.

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

В зависимости от числа переменных, входящих в предложение, различают одноместные, двухместные, трехместные и т.д. предикаты, обозначаемые соответственно: А(х ), В(х , у ), С(х , у , z ).

Если задан некоторый предикат, то с ним связаны два множества:

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

2. Множество истинности Т, состоящее из всех тех значений переменных, при подстановке которых в предикат получается истинное высказывание.

Множество истинности предиката всегда является подмножеством его области определения, то есть .

Над предикатами можно совершать те же операции, что и над высказываниями.

1. Отрицанием предиката А(х ), заданного на множестве Х, называется предикат , истинный при тех значениях , при которых предикат А(х ) обращается в ложное высказывание, и наоборот.

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

Множество истинности предиката является дополнением к множеству истинности предиката А(х ). Обозначим через Т А множество истинности предиката А(х ), а через Т - множество истинности предиката . Тогда .

2. Конъюнкцией предикатов А(х ) и В(х х ) В(х х Х, при которых оба предиката обращаются в истинные высказывания.

Множество истинности конъюнкции предикатов есть пересечение множеств истинности предиката А(х ) В(х ). Если обозначить множество истинности предиката А(х) через Т А, а множество истинности предиката В(х) через Т В и множество истинности предиката А(х) В(х) через , то

3. Дизъюнкцией предикатов А(х) и В(х ), заданных на множестве Х, называется предикат А(х ) В(х ), обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых хотя бы один из предикатов обратился в истинное высказывание.

Множество истинности дизъюнкции предикатов есть объединение множеств истинности образующих ее предикатов, т.е. .

4.Импликацией предикатов А(х ) и В(х ), заданных на множестве Х, называется предикат А(х ) В(х ), который ложен при тех и только тех значениях переменной, при которых первый предикат обращается в истинное высказывание, а второй – в ложное.

Множество истинности импликации предикатов есть объединение множества истинности предиката В(х ) с дополнением к множеству истинности предиката А(х ), т.е.

5. Эквиваленцией предикатов А(х ) и В(х ), заданных на множестве Х, называется предикат , который обращается в истинное высказывание при всех тех и только тех значениях переменной, при которых оба предиката обращаются либо в истинные высказывания, либо в ложные высказывания.

Множество истинности эквиваленции предикатов есть пересечение множества истинности предиката с множеством истинности предиката .

Кванторные операции над предикатами

Предикат можно перевести в высказывание способом подстановки и способом «навешивание квантора».

Про числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 можно сказать: а) все данные числа простые; б) некоторые из данных чисел четные.

Так как относительно этих предложений можно сказать, что они истинны или ложны, то полученные предложения – высказывания.

Если из предложения «а» убрать слово «все», а из предложения «б» - слово «некоторые», то получим следующие предикаты: «данные числа простые», «данные числа нечетные».

Слова «все» и «некоторые» называются кванторами. Слово «квантор» латинского происхождения и означает «сколько», т. е. квантор показывает, о скольких (всех или некоторых) объектах говорится в том или ином предложении.

Различают два основных вида кванторов: квантор общности и квантор существования.

Термины «всякий», «любой», «каждый» носят название – квантор всеобщности. Обозначается .

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

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

16. Определение бинарного отношения между множествами А и В.

Бинарным отношением между множествами A и B называется подмножество R прямого произведения . В том случае, когда можно просто говорить об отношении R на A .

Пример 1 . Выпишите упорядоченные пары, принадлежащие бинарным отношениям R 1 и R 2 , заданными на множествах A и : , . Подмножество R 1 состоит из пар: . Подмножество .

Область определения R на есть множество всех элементов из A таких, что для некоторых элементов имеем . Иными словами область определения R есть множество всех первых координат упорядоченных пар из R .

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

В примере 1 для R 1 область определения: , множество значений - . Для R 2 область определения: , множество значений: .

Во многих случаях удобно использовать графическое изображение бинарного отношения. Оно осуществляется двумя способами: с помощью точек на плоскости и с помощью стрелок.

В первом случае выбирают две взаимно перпендикулярные линии в качестве горизонтальной и вертикальной осей. На горизонтальной оси откладывают элементы множества A и через каждую точку проводят вертикальную линию. На вертикальной оси откладывают элементы множества B , через каждую точку проводят горизонтальную линию. Точки пересечения горизонтальных и вертикальных линий изображают элементы прямого произведения

17. Способы задания бинарных отношений.

Всякое подмножество декартова произведения A×B называется бинарным отношением, определенным на паре множеств A и B (по латыни «бис» обозначает «дважды»). В общем случае по аналогии с бинарными можно рассматривать и n-арные отношения как упорядоченные последовательностиn элементов, взятых по одному из n множеств.

Для обозначения бинарного отношения применяют знак R. Поскольку R- это подмножество множества A×B, то можно записать R⊆A×. Если же требуется указать, что (a, b) ∈ R, т. е. между элементами a ∈ A и b ∈ B существует отношение R, то пишут aRb.

Способы задания бинарных отношений:

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

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

На (рисунке 1.16) изображена координатная сетка для множеств. Точкам пересечения трех вертикальных линий с шестью горизонтальными соответствуют элементы множества A×B. Кружочками на сетке отмечены элементы отношения aRb, где a ∈ A и b ∈ B, R обозначает отношение «делит».

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

3. Способ задания отношений с помощью сечений используется реже, поэтому рассматривать его не будем.

18. Рефлексивность бинарного отношения. Пример.

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

Свойство рефлексивности при заданных отношениях матрицей характеризуется тем, что все диагональные элементы матрицы равняются 1; при заданных отношениях графом каждый элемент имеет петлю - дугу (х, х).

Если это условие не выполнено ни для какого элемента множества, то отношение называется антирефлексивным.

Если антирефлексивное отношение задано матрицей, то все диагональные элементы являются нулевыми. При задании такого отношения графом каждая вершина не имеет петли - нет дуг вида (х, х).

Формально антирефлексивность отношения определяется как: .

Если условие рефлексивности выполнено не для всех элементов множества, говорят, что отношение нерефлексивно.

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

а) Москва  столица России.

б) Студент физико-математического факультета педагогического института.

в) Треугольник ABC подобен треугольнику А"В"С".

г) Луна есть спутник Марса.

е) Кислород  газ.

ж) Каша  вкусное блюдо.

з) Математика  интересный предмет.

и) Картины Пикассо слишком абстрактны.

к) Железо тяжелее свинца.

л) Да здравствуют музы!

м) Треугольник называется равносторонним, если его стороны равны.

н) Если в треугольнике все углы равны, то он равносторонние.

о) Сегодня плохая погода.

п) В романе А. С. Пушкина «Евгений Онегин» 136 245 букв.

р) Река Ангара впадает в озеро Байкал.

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

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

ж) Предложение не является высказыванием, так как понятие «вкусное блюдо» слишком неопределенно.

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

1.2. Укажите, какие из высказываний предыдущей задачи истинные, а какие  ложные.

1.3. Сформулируйте отрицания следующих высказываний; укажите значения истинности данных высказываний и их отрицаний:

а) Волга впадает в Каспийское море.

б) Число 28 не делится на число 7.

д) Все простые числа нечетны.

1.4. Установите, какие из высказываний в следующих парах являются отрицаниями друг друга и какие  нет (объясните почему):

а) 2 < 0, 2 > 0. -

б) 6 < 9, 6  9.

в) «Треугольник ABC прямоугольный», «Треугольник ABC тупоугольный».

г) «Натуральное число n четно», «Натуральное число n нечетно».

д) «Функция f нечетна», «Функция f четна».

е) «Все простые числа нечетны», «Все простые числа четны».

ж) «Все простые числа нечетны», «Существует простое четное число».

з) «Человеку известны все виды животных, обитающих на Земле», «На Земле существует вид животных, не известный человеку».

и) «Существуют иррациональные числа», «Все числа рациональные».

Решение. а) Высказывание «2 > 0» не является отрицанием "высказывания «2 < 0», потому что требование не быть меньше 0 оставляет две возможности: быть равным 0 и быть больше 0. Таким образом, отрицанием высказывания «2 < 0» является высказывание «2  0».

1.5. Следующие высказывания запишите без знака отрицания:

а)
; в)
;

б)
; г)
.

1.6.

а) Ленинград расположен на Неве и 2 + 3 = 5.

б) 7  простое число и 9  простое число.

в) 7  простое число или 9  простое число.

г) Число 2 четное или это число простое.

д) 2  3, 2  3, 2 2  4, 2 2  4.

е) 2 2 = 4 или белые медведи живут в Африке.

ж) 2 2 = 4, и 2 2  5, и 2 2  4.

Решение. а) Так как оба простых высказывания, к которым применяется операция конъюнкции, истинны, поэтому на основании определения этой операции и их конъюнкция есть истинное высказывание.

1.7. Определите значения истинности высказываний А, В, С, D и Е, если:

 истинные высказывания, а

 ложные.

Решение. в) Дизъюнкция высказываний есть истинное высказывание лишь в случае, когда по меньшей мере одно из входящих в дизъюнкцию составляющих высказываний (членов дизъюнкции) истинно. В нашем случае второе составляющее высказывание «2 2 = 5» ложно, а дизъюнкция двух высказываний истинна. Поэтому первое составляющее высказывание С истинно.

1.8. Сформулируйте и запишите в виде конъюнкции или дизъюнкции условие истинности каждого предложения (а и b - действительные числа):

а)
г)ж)

б)
д)
з)

в)
е)
и)

Решение. г) Дробь равна нулю лишь в случае, когда числитель равен нулю и знаменатель не равен нулю, т. е. (а = 0) & (b  0).

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

а) Если 12 делится на 6, то 12 делится на 3.

б) Если 11 делится на 6, то 11 делится на 3.

в) Если 15 делится на 6, то 15 делится на 3.

г) Если 15 делится на 3, то 15 Делится на 6.

д) Если Саратов расположен на Неве, то белые медведи обитают в Африке.

е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3.

ж) 11 делится на 6 тогда и только тогда, когда 11 делится на 3.

з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3.

и) 15 делится на 5 тогда и только тогда, когда 15 делится на 4.

к) Тело массой m обладает потенциальной энергией mgh тогда и только тогда, когда оно находится на высоте h над поверхностью земли.

Решение. а) Так как высказывание-посылка «12 делится на 6» истинно и, высказывание-следствие «12 делится на 3» истинно, то и составное высказывание на основании определения импликации также истинно.

ж) Из определения эквивалентности видим, что высказывание вида
истинно, если логические значения высказыванийР и Q совпадают, и ложно в противном случае. В данном примере оба высказывания к которым применяется связка «тогда и только тогда», ложны. Поэтому все составное высказывание истинно.

1.10. Пусть через А обозначено высказывание «9 делится на 3», а через В  высказывание «8 делится на 3». Определите значения истинности следующих высказываний:

а)
г)
ж)
к)

б)
д)
з)
л)

в)
е)
и)
м)

Решение. е) Имеем
,
. Поэтому

1.11.

а) Если 4  четное число, то А.

б) Если В, то 4  нечетное число.

в) Если 4  четное число, то С.

г) Если D, то 4  нечетное число.

Решение. а) Импликация двух высказываний есть ложное высказывание лишь в единственном случае, когда посылка истинна, а заключение ложно. В данном случае посылка «4  четное число» истинна и по условию все высказывание также истинно. Поэтому заключение А ложным быть не может, т. е. высказывание А истинно.

1.12. Определите значения истинности высказываний А, В, С и D в следующих предложениях, из которых первые два истинны, а последние два ложны:

а)
; б)
;

в)
; г)
.

1.13. Пусть через А обозначено высказывание «Этот треугольник равнобедренный», а через В  высказывание «Этот треугольник равносторонний». Прочитайте следующие высказывания:

а)
г)

б)
д)

в)
е)

Решение. е) Если треугольник равнобедренный и неравносторонний, то неверно, что он неравнобедренный.

1.14. Следующие составные высказывания расчлените на простые и запишите символически, введя буквенные обозначения для простых их составляющих:

а) Если 18 делится на 2 и не делится на 3, то оно не делится на 6.

б) Произведение трех чисел равно нулю тогда и только тогда, когда одно из них равно нулю.

в) Если производная функция в точке равна нулю и вторая производная этой функции в той же точке отрицательна, то данная точка есть точка максимума этой функции.

г) Если в треугольнике медиана не является высотой и биссектрисой, то этот треугольник не равнобедренный и не равносторонний.

Решение. г) Выделим и следующим образом обозначим простейшие составляющие высказывания:

А: «В треугольнике медиана является высотой»;

В: «В треугольнике медиана является биссектрисой»;

С: «Этот треугольник равнобедренный»;

D: «Этот треугольник равносторонний».

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

1.15. Из двух данных высказываний А и В постройте составное высказывание с помощью операций отрицания, конъюнкции и дизъюнкции, которое было бы:

а) истинно тогда и только тогда, когда оба данных высказывания ложны;

б) ложно тогда и только тогда, когда оба данных высказывания истинны.

1.16. Из трех данных высказываний А, В, С постройте составное высказывание, которое истинно, когда истинно какое-либо одно из данных высказываний, и только в этом случае.

1.17. Пусть высказывание
истинно. Что можно сказать о логическом значении высказывания?

1.18. Если высказывание
истинно (ложно), то что можно сказать о логическом значении высказываний:

а)
; б)
; в)
; г)
?

1.19. Если высказывание
истинно, а высказывание
ложно, то что можно сказать о логическом значении высказывания
?

1.20. Существуют ли три таких высказывания А, В, С, чтобы одновременно высказывание
было истинным, высказывание
 ложным и высказывание
 ложным?

1.21. Для каждого из помещенных ниже высказываний определите, достаточно ли приведенных сведений, чтобы установить его логическое значение. Если достаточно, то укажите это значение. Если недостаточно, то покажите, что возможны и одно, и другое истинностные значения:

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

Значение истинности